Thread overview | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
December 04, 2015 Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
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 |
December 04, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 |
December 04, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jacob Carlborg | On Friday, 4 December 2015 at 20:01:10 UTC, Jacob Carlborg wrote:
> 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?
+ 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.
|
December 04, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jacob Carlborg | On 12/04/2015 03:01 PM, Jacob Carlborg wrote:
> 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?
Try it! -- Andrei
|
December 04, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to wobbles | 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
|
December 04, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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? |
December 04, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sebastiaan Koppe | On 12/04/2015 06:09 PM, Sebastiaan Koppe wrote:
> 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?
Forward ranges.
|
December 05, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 2015-12-04 23:33, Andrei Alexandrescu wrote: >> retro + take? > > Try it! -- Andrei One would need another "retro" as well. But I see now that you have replied it doesn't work for forward ranges. -- /Jacob Carlborg |
December 05, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Saturday, 5 December 2015 at 01:03:05 UTC, Andrei Alexandrescu wrote:
>> What exactly doesn't work?
>
> Forward ranges.
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?
|
December 05, 2015 Re: Another cool mini-project: advance a range within n steps from its end | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Friday, 4 December 2015 at 16:37:36 UTC, Andrei Alexandrescu wrote: > Takers? https://github.com/D-Programming-Language/phobos/pull/3855 |
Copyright © 1999-2021 by the D Language Foundation