Re: Another cool mini-project: advance a range within n steps from its end

[Sebastiaan Koppe via Digitalmars-d]

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?

Re: Another cool mini-project: advance a range within n steps from its end

[Jakob Ovrum via Digitalmars-d]

On Friday, 4 December 2015 at 16:37:36 UTC, Andrei Alexandrescu 
wrote:

Takers?


https://github.com/D-Programming-Language/phobos/pull/3855

Re: Another cool mini-project: advance a range within n steps from its end

[Jacob Carlborg via Digitalmars-d]

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

Re: Another cool mini-project: advance a range within n steps from its end

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Another cool mini-project: advance a range within n steps from its end

[Sebastiaan Koppe via Digitalmars-d]

On Saturday, 5 December 2015 at 20:52:23 UTC, Andrei Alexandrescu 
wrote:

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


I know, but it makes half the range primitive calls. Ain't that 
worth something? Well, it depends I suppose.

Another cool mini-project: advance a range within n steps from its end

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Another cool mini-project: advance a range within n steps from its end

[Sebastiaan Koppe via Digitalmars-d]

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?

Re: Another cool mini-project: advance a range within n steps from its end

[Jacob Carlborg via Digitalmars-d]

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

Re: Another cool mini-project: advance a range within n steps from its end

[wobbles via Digitalmars-d]

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.

Re: Another cool mini-project: advance a range within n steps from its end

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Another cool mini-project: advance a range within n steps from its end

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Another cool mini-project: advance a range within n steps from its end

[Andrei Alexandrescu via Digitalmars-d]

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.