digitalmars.D - Another cool mini-project: advance a range within n steps from its
- Andrei Alexandrescu (10/10) Dec 04 2015 Like "tail" in Unix. Given a range R r and a number size_t n, return a
- Jacob Carlborg (4/12) Dec 04 2015 retro + take?
- wobbles (7/24) Dec 04 2015 + retro to turn it back the normal way?
- Andrei Alexandrescu (8/9) Dec 04 2015 Doesn't work. Try it!
- Sebastiaan Koppe (9/10) Dec 04 2015 void main()
- Andrei Alexandrescu (2/11) Dec 04 2015 Forward ranges.
- Sebastiaan Koppe (15/17) Dec 05 2015 I see; retro requires a bidirectional range.
- Andrei Alexandrescu (2/4) Dec 05 2015 That's O(n) space :o). -- Andrei
- Sebastiaan Koppe (4/10) Dec 05 2015 I know, but it makes half the range primitive calls. Ain't that
- Andrei Alexandrescu (2/17) Dec 04 2015 Try it! -- Andrei
- Jacob Carlborg (5/7) Dec 05 2015 One would need another "retro" as well. But I see now that you have
- Jakob Ovrum (3/4) Dec 05 2015 https://github.com/D-Programming-Language/phobos/pull/3855
Like "tail" in Unix. Given a range R r and a number size_t n, return a TakeExactly!R that's r at no more than n steps from its end: TakeExactly!R advanceWithin(R)(R r, size_t n) if (isForwardRange!R); Invariant: assert(r.advanceWithin(n).length <= n); Implementation would send a scout range ahead, etc. I didn't file an issue for it, but it's a great function to have. Takers? Andrei
Dec 04 2015
On 2015-12-04 17:37, Andrei Alexandrescu wrote:Like "tail" in Unix. Given a range R r and a number size_t n, return a TakeExactly!R that's r at no more than n steps from its end: TakeExactly!R advanceWithin(R)(R r, size_t n) if (isForwardRange!R); Invariant: assert(r.advanceWithin(n).length <= n); Implementation would send a scout range ahead, etc. I didn't file an issue for it, but it's a great function to have.retro + take? -- /Jacob Carlborg
Dec 04 2015
On Friday, 4 December 2015 at 20:01:10 UTC, Jacob Carlborg wrote:On 2015-12-04 17:37, Andrei Alexandrescu wrote:+ retro to turn it back the normal way? Also, I think this'd work? return r.takeExactly(r.walkLength - n); It wouldn't be particularly efficient though I wouldn't think - as you'd need to walk the whole range to find it's length. r.retro.take(n).retro seems like the easiest fit.Like "tail" in Unix. Given a range R r and a number size_t n, return a TakeExactly!R that's r at no more than n steps from its end: TakeExactly!R advanceWithin(R)(R r, size_t n) if (isForwardRange!R); Invariant: assert(r.advanceWithin(n).length <= n); Implementation would send a scout range ahead, etc. I didn't file an issue for it, but it's a great function to have.retro + take?
Dec 04 2015
On 12/04/2015 04:26 PM, wobbles wrote:r.retro.take(n).retro seems like the easiest fit.Doesn't work. Try it! The right solution is to send a scout range ahead. Once the scout got n steps ahead the initial range, advance both until the scout reaches the end. Then return the initial range. It's a nontrivial algorithm that can't be composed easily from existing ones. Andrei
Dec 04 2015
On Friday, 4 December 2015 at 22:53:01 UTC, Andrei Alexandrescu wrote:Doesn't work. Try it!void main() { import std.range : retro, take; import std.stdio : writeln; assert([1,2,3,4,5].retro.take(3).retro == [3,4,5]); } What exactly doesn't work?
Dec 04 2015
On 12/04/2015 06:09 PM, Sebastiaan Koppe wrote:On Friday, 4 December 2015 at 22:53:01 UTC, Andrei Alexandrescu wrote:Forward ranges.Doesn't work. Try it!void main() { import std.range : retro, take; import std.stdio : writeln; assert([1,2,3,4,5].retro.take(3).retro == [3,4,5]); } What exactly doesn't work?
Dec 04 2015
On Saturday, 5 December 2015 at 01:03:05 UTC, Andrei Alexandrescu wrote:I see; retro requires a bidirectional range. I was thinking about void main() { import std.algorithm : count; import std.range : drop; import std.stdio : writeln; auto a = [1,2,3,4,5]; writeln(a.drop(a.count-3)); } But it has the downside that it calls front/empty/pop 2*n times. What about using a rangified circular buffer of the same size you want the tail to be, and lazily fill it?What exactly doesn't work?Forward ranges.
Dec 05 2015
On 12/05/2015 11:22 AM, Sebastiaan Koppe wrote:What about using a rangified circular buffer of the same size you want the tail to be, and lazily fill it?That's O(n) space :o). -- Andrei
Dec 05 2015
On Saturday, 5 December 2015 at 20:52:23 UTC, Andrei Alexandrescu wrote:On 12/05/2015 11:22 AM, Sebastiaan Koppe wrote:I know, but it makes half the range primitive calls. Ain't that worth something? Well, it depends I suppose.What about using a rangified circular buffer of the same size you want the tail to be, and lazily fill it?That's O(n) space :o). -- Andrei
Dec 05 2015
On 12/04/2015 03:01 PM, Jacob Carlborg wrote:On 2015-12-04 17:37, Andrei Alexandrescu wrote:Try it! -- AndreiLike "tail" in Unix. Given a range R r and a number size_t n, return a TakeExactly!R that's r at no more than n steps from its end: TakeExactly!R advanceWithin(R)(R r, size_t n) if (isForwardRange!R); Invariant: assert(r.advanceWithin(n).length <= n); Implementation would send a scout range ahead, etc. I didn't file an issue for it, but it's a great function to have.retro + take?
Dec 04 2015
On 2015-12-04 23:33, Andrei Alexandrescu wrote:One would need another "retro" as well. But I see now that you have replied it doesn't work for forward ranges. -- /Jacob Carlborgretro + take?Try it! -- Andrei
Dec 05 2015
On Friday, 4 December 2015 at 16:37:36 UTC, Andrei Alexandrescu wrote:Takers?https://github.com/D-Programming-Language/phobos/pull/3855
Dec 05 2015