January 15, 2013
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
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
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
>   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
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
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
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
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
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
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.