www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - =?UTF-8?B?U2NocsO2ZGluZ2VyJ3M=?= Stride

reply Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Currently the contents of Stride depend on from which end we look at it:

auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
auto col = stride(m, 4);
assert(equal(col, [1, 1, 1]));
assert(equal(retro(col), [4, 4, 4]));

Is the quantum behavior intended?

-- 
Tomek
Oct 10 2010
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 10/10/10 7:34 PM, Tomek Sowiński wrote:

 Currently the contents of Stride depend on from which end we look at it:

 auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
 auto col = stride(m, 4);
 assert(equal(col, [1, 1, 1]));
 assert(equal(retro(col), [4, 4, 4]));

 Is the quantum behavior intended?



Hmm, that does seem counter-intuitive, but I can't see any other way for 
it to work.

Consider a doubly-linked list with the same data as above. How could 
Stride implement back() without first computing the length of the list? 
You could implement it correctly and efficiently for (non-infinite) 
random access ranges, but then you'd have inconsistent behavior between 
random access ranges and non-RA bidirectional ranges.

The solution I believe is to make Stride a forward range for directional 
ranges, and give it the correct semantics for back() when used on a 
random access range i.e. use ((length-1) - (length-1) % stride) to get 
the back element index so that the retro traversal is actually the 
reverse of the forward traversal.

For bidirectional ranges, people can always just use stride(retro(r), n) 
to get a backwards traversing stride.
Oct 10 2010
parent reply Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Peter Alexander napisał:


 On 10/10/10 7:34 PM, Tomek Sowiński wrote:

 Currently the contents of Stride depend on from which end we look at it:

 auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
 auto col = stride(m, 4);
 assert(equal(col, [1, 1, 1]));
 assert(equal(retro(col), [4, 4, 4]));

 Is the quantum behavior intended?



 Hmm, that does seem counter-intuitive, but I can't see any other way for
 it to work.
 
 Consider a doubly-linked list with the same data as above. How could
 Stride implement back() without first computing the length of the list?



I don't know but that wouldn't work now anyway -- popBack() and back() is
defined if 
isBidirectionalRange!(R) && hasLength!(R), where R is the underlying.


 You could implement it correctly and efficiently for (non-infinite)
 random access ranges, but then you'd have inconsistent behavior between
 random access ranges and non-RA bidirectional ranges.



It's not about random access, but length. Having length, it's trivial to
calculate how many 
popBack()s one needs to prime the stride. For ranges without length it doesn't
matter 
because the above.


 The solution I believe is to make Stride a forward range for directional
 ranges, and give it the correct semantics for back() when used on a
 random access range i.e. use ((length-1) - (length-1) % stride) to get
 the back element index so that the retro traversal is actually the
 reverse of the forward traversal.

 For bidirectional ranges, people can always just use stride(retro(r), n)
 to get a backwards traversing stride.



Actually I see in Stride's ctor an attempt to pop slack items off the input's
back:

    this(R input, size_t n)
    {
        _input = input;
        _n = n;
        static if (hasLength!(R))
        {
            auto slack = _input.length % _n;
            if (slack) slack--;
            if (!slack) return;

Since retro'ing isn't unittested, I can't tell if it was to address this issue
or not. I think it's 
just a matter of fixing the 'slack' number. Phobos people?

-- 
Tomek
Oct 10 2010
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 10/10/10 9:45 PM, Tomek Sowiński wrote:

 Peter Alexander napisał:


 On 10/10/10 7:34 PM, Tomek Sowiński wrote:

 Currently the contents of Stride depend on from which end we look at it:

 auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
 auto col = stride(m, 4);
 assert(equal(col, [1, 1, 1]));
 assert(equal(retro(col), [4, 4, 4]));

 Is the quantum behavior intended?



 Hmm, that does seem counter-intuitive, but I can't see any other way for
 it to work.

 Consider a doubly-linked list with the same data as above. How could
 Stride implement back() without first computing the length of the list?



 I don't know but that wouldn't work now anyway -- popBack() and back() is
defined if
 isBidirectionalRange!(R)&&  hasLength!(R), where R is the underlying.


 You could implement it correctly and efficiently for (non-infinite)
 random access ranges, but then you'd have inconsistent behavior between
 random access ranges and non-RA bidirectional ranges.



 It's not about random access, but length. Having length, it's trivial to
calculate how many
 popBack()s one needs to prime the stride. For ranges without length it doesn't
matter
 because the above.


 The solution I believe is to make Stride a forward range for directional
 ranges, and give it the correct semantics for back() when used on a
 random access range i.e. use ((length-1) - (length-1) % stride) to get
 the back element index so that the retro traversal is actually the
 reverse of the forward traversal.

 For bidirectional ranges, people can always just use stride(retro(r), n)
 to get a backwards traversing stride.



 Actually I see in Stride's ctor an attempt to pop slack items off the input's
back:

      this(R input, size_t n)
      {
          _input = input;
          _n = n;
          static if (hasLength!(R))
          {
              auto slack = _input.length % _n;
              if (slack) slack--;
              if (!slack) return;

 Since retro'ing isn't unittested, I can't tell if it was to address this issue
or not. I think it's
 just a matter of fixing the 'slack' number. Phobos people?



Sorry, yeah, you're absolutely right. I don't know why I was fixated on 
random access ranges.
Oct 10 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/10/10 13:34 CDT, Tomek Sowiński wrote:

 Currently the contents of Stride depend on from which end we look at it:

 auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
 auto col = stride(m, 4);
 assert(equal(col, [1, 1, 1]));
 assert(equal(retro(col), [4, 4, 4]));

 Is the quantum behavior intended?



Bug!

Andrei
Oct 10 2010
parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Andrei Alexandrescu napisał:


 On 10/10/10 13:34 CDT, Tomek Sowiński wrote:

 Currently the contents of Stride depend on from which end we look at it:

 auto m = [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]; // 3 rows, 4 columns
 auto col = stride(m, 4);
 assert(equal(col, [1, 1, 1]));
 assert(equal(retro(col), [4, 4, 4]));

 Is the quantum behavior intended?



 Bug!



http://d.puremagic.com/issues/show_bug.cgi?id=5035

-- 
Tomek
Oct 10 2010