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