View mode: basic / threaded / horizontal-split · Log in · Help
January 15, 2013
Re: The rfind challenge
On Tue, Jan 15, 2013 at 07:54:12AM -0500, Andrei Alexandrescu wrote:
> On 1/15/13 1:31 AM, H. S. Teoh wrote:
> >Hmm. What about introducing a new primitive takeUntil, that returns the
> >initial segment of the range until a given predicate becomes true? Then
> >you could implement rfind thus:
> >
> >	auto rfind(alias pred, R)(R range)
> >		if (isBidirectionalRange!R)
> >	{
> >		return range.retro()
> >			.takeUntil!pred()
> >			.retro();
> >	}
> 
> That works, but returns a different type. Ideally rfind would return
> the same type as the initial range, R.
[...]

Hmm. Then it is indeed impossible with the current primitives, because
to iterate from the back, one would have to pop off the back, so by
definition you can't reach the back anymore.


T

-- 
Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.
January 15, 2013
Re: The rfind challenge
On Tue, Jan 15, 2013 at 06:03:06PM +0100, Phil Lavoie wrote:
[...]
> An addition to this solution could be another new primitive:
> reverse:
> 
> Pseudo:
>   original = range.save
>   reversed = range.reverse //Permanently invert start an end. I
> think this is feasible for all bidirectional ranges. Still a
> bidirectional range.
[...]

I like this very much, actually. I think .reverse is much more useful
than .back and .popBack. I mean, how many algorithms actually use .back
and .popBack? Probably less than a handful, if any. Most algorithms use
.front and popFront().

Viewed in that light, what then is a bidirectional range, if not a range
where you can swap the direction of iteration? That is, we can redefine
a bidirectional range to be one that implements .reverse, with the
property that R.reverse.reverse == R. Get rid of .back and .popBack,
which hardly anybody uses anyway. It simplifies the range API
significantly, and makes rfind implementable in terms of primitives.


T

-- 
Ruby is essentially Perl minus Wall.
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 17:57:07 UTC, Andrei Alexandrescu 
wrote:
> On 1/15/13 2:20 AM, monarch_dodra wrote:
>> auto l = cutBefore(a, b); //Gets the part of a that is before b
>> auto r = cutAfter(a, b); //Gets the part of a that is after b
>
> I think cutBefore is sufficient. No? Ideas for better names?
>
> Andrei

I've been trying to brainstorm a couple of ideas. Here is one:

//----
Tuple(R, R) cut(R other); //Returns both parts of the
                          //current range that are
                          //Before and After other

usage:
//----
Tuple(R, R) slices = a.cut(b); //Cuts a in two pieces, relative 
to b.
assert(equal(a, chain(slices[0], b, slices[1])));

From there, we adding just the "merge" primitive would give us:

//----
R result = merge(b, slices[1]);

The neat thing here is that we have consistent typing the entire 
algorithm through. Yay!

That's two extra functions, which can provide slicing and merging 
for bidirectional ranges. And they can be provided without 
breaking anything existing. Not too shabby (IMO).

This is still very sketchy of course, so don't destroy too hard ;)
January 15, 2013
Re: The rfind challenge
>   bool empty() { return _start is null || _end is null; } //The
This would have to be corrected.

I agree that there are too many primitives.
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 18:19:48 UTC, H. S. Teoh wrote:
> On Tue, Jan 15, 2013 at 06:03:06PM +0100, Phil Lavoie wrote:
> [...]
>> An addition to this solution could be another new primitive:
>> reverse:
>> 
>> Pseudo:
>>   original = range.save
>>   reversed = range.reverse //Permanently invert start an end. I
>> think this is feasible for all bidirectional ranges. Still a
>> bidirectional range.
> [...]
>
> I like this very much, actually. I think .reverse is much more 
> useful
> than .back and .popBack. I mean, how many algorithms actually 
> use .back
> and .popBack? Probably less than a handful, if any. Most 
> algorithms use
> .front and popFront().
>
> Viewed in that light, what then is a bidirectional range, if 
> not a range
> where you can swap the direction of iteration? That is, we can 
> redefine
> a bidirectional range to be one that implements .reverse, with 
> the
> property that R.reverse.reverse == R. Get rid of .back and 
> .popBack,
> which hardly anybody uses anyway. It simplifies the range API
> significantly, and makes rfind implementable in terms of 
> primitives.
>
>
> T

+1

I was about to suggest a solution based on Reversible ranges 
instead of bidirectional ranges, but I have yet to polish it.
January 15, 2013
Re: The rfind challenge
And, if ever needed, popBack could become this:

void popBack( R )( ref R r ) if( isReversibleRange!R ) {
  auto reversed = r.reverse.popFront();
  r = reversed.reverse;
}
January 15, 2013
Re: The rfind challenge
Continuing with reversible ranges:

struct ForwardRange {
 _start;
 _end;

 BackwardRange reverse() { return BackwardRange( _end, _start ); }
}

struct BackwardRange {
 _start;
 _end;

 //guess what reverse is.
}

That would give the power to mimick bidirectional ranges (see 
post on popBack before)

Now, we still need a way to move one of those pointers to a given 
place to fulfill rfind:

auto rfind( R, E )( R r, E e ) if( isReversibleRange!R ) {
 auto original = r.save; //For the end purpose;
 auto found = find( r.reverse, e ); //found is reversed and 
starts on e.
 //What we want now is a range of type typeof( original ) 
starting on found but ending on original. Therefore, we need an 
additional primitive. Suggestion: jumpTo.
 return original.jumpTo( found ); //Keeps the ordering, only move 
the start.
}

struct ForwardRange {
...
void jumpTo( ForwardRange r )( _start = r._start; }
void jumpTo( BackwardRange r )( _start = r._start; }

}
January 15, 2013
Re: The rfind challenge
It'd be nicer if we could use an operator, but this is wishful 
thinking:

auto r = r2.jumpTo( d2 ); //r2d2, yes.
Equivalent to:
auto r = r2[ d2 .. $ ];
Or:
auto r = r2[ d2 ... ];

Again, wishful thinking.
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 19:11:43 UTC, Phil Lavoie wrote:
> It'd be nicer if we could use an operator, but this is wishful 
> thinking:
>
> auto r = r2.jumpTo( d2 ); //r2d2, yes.
> Equivalent to:
> auto r = r2[ d2 .. $ ];
> Or:
> auto r = r2[ d2 ... ];
>
> Again, wishful thinking.

What about startOn instead?

That makes two additional primitives and one additional range 
type( -Bidirectional + Reversible + StartableOn??!?!??!?!?!)
January 15, 2013
Re: The rfind challenge
On 2013-01-15 19:00, Andrei Alexandrescu wrote:
> That's too many. Simpler approaches?


Let me give an outside perspective of someone that doesn't work with D all day.
For forward ranges the original method is fine, but for bidirectional r and e I 
would expect the following code to somehow just work, but it doesn't:

    auto rfind(R1 r, R2 e) {
        return retro(findSplitAfter(retro(r), retro(e))[0]);
    }

Other than the tiny detail of this not working, existing stuff like findSplit, 
findSplitBefore and findSplitAfter would be enough to define their r* versions.
1 2 3 4 5
Top | Discussion index | About this forum | D home