View mode: basic / threaded / horizontal-split · Log in · Help
January 15, 2013
Re: The rfind challenge
On 01/15/2013 02:30 PM, Timon Gehr wrote:
>
> /+pure+/ R tail(R)(R r)out(result){
>      assert(result=={
>          auto a=r;
>          a.popFront();
>          return a;
>      }());
> }body{
>      auto a=r;
>      a.popFront();
>      return a;
> }

Obviously, this should be

/+pure+/ R tail(R)(R r)out(result){
    assert(result=={
        auto a=r.save;
        a.popFront();
        return a;
    }());
}body{
    auto a=r.save;
    a.popFront();
    return a;
}
January 15, 2013
Re: The rfind challenge
On 2013-01-15 14:30, Timon Gehr wrote:
> That is buggy too.

Thanks for adding the necessary check for element being at position 0.
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 05:51:16 UTC, Andrei Alexandrescu 
wrote:
> (Warning: this assumes a fair bit of background with ranges and 
> the STL.)
>
> We've had a long-standing weakness of ranges when compared with 
> STL iterators: in a find() call we get to access the balance of 
> the range from the found position (if any) through the end of 
> the initial range. In contrast, STL's find returns an iterator 
> that can be combined with the beginning of the initial range or 
> the end of the initial range, thus offering two ranges instead 
> of one.
>
> D offers the findSplit family which partially deals with this, 
> but in an arguably imperfect way because the range from the 
> beginning of the initial range to the found element has a 
> different type than the initial range.
>
> In spite of that, things have worked out well.
>
> Nowadays I've been thinking (inspired by an exchange on a C=+ 
> mailing list) that STL's rfind (http://goo.gl/Btg8s) is a real 
> challenge for D's ranges.
>
> In D, r.rfind(e) should return a range starting with the last 
> occurrence of e in r and spanning through the rest of r.
>
> If r is a forward range but not better, this is rather simple:
>
> R rfind(R, E)(R range, E element)
> {
>     for (;;)
>     {
>         auto ahead = range.save.find(element);
>         if (ahead.empty) return range;
>         range = ahead;
>     }
> }
>
> If the range is random-access, the algorithm is easy to 
> implement efficiently by scanning from the end and using 
> indexing.
>
> The tricky case is with bidirectional range. I was unable to 
> define an algorithm using the current primitives that: (a) 
> scans the range from the end, and (b) returns a range from the 
> found position through the end.
>
> Looks like rfind() would need one extra primitive for 
> bidirectional ranges. What would be a good one? I have a few 
> starters, but don't want to bias anyone. Please chime in!
>
>
> Thanks,
>
> Andrei

Interesting problem. One possibility would be to add a CLASS 
primitive like this: Range.merge( Range start, Range end ) 
//Takes the start of the start and the end of end.

Pseudo:
  original = range.save
  resPos = range.retro.find
  return Range.merge( resPos, original ) //DOES NOT WORK

The problem with this solution is that:
Retro returns a different range type and it would be more 
complicated to
have the merge function work with this type.

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.
  reversed.find( needle ) //In haystack :)
  return Range.merge( reversed, original ) //Ok, start of 
reversed is on needle and end of original hasn't moved. The order 
of the range returned is the same as the one received.

This is just a suggestion and any primitive could be renamed. 
However, I think reverse is a good place to start.

Phil
January 15, 2013
Re: The rfind challenge
On 1/15/13 12:03 PM, Phil Lavoie wrote:
> Pseudo:
> original = range.save
> resPos = range.retro.find
> return Range.merge( resPos, original ) //DOES NOT WORK
>
> The problem with this solution is that:
> Retro returns a different range type and it would be more complicated to
> have the merge function work with this type.

This would be difficult to implement safely, which is an important 
disadvantage.

> 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.
> reversed.find( needle ) //In haystack :)
> return Range.merge( reversed, original ) //Ok, start of reversed is on
> needle and end of original hasn't moved. The order of the range returned
> is the same as the one received.
>
> This is just a suggestion and any primitive could be renamed. However, I
> think reverse is a good place to start.

Reverse is really cool and immediate to implement safely for a lot of 
ranges I can think of. How would you define rfind assuming reverse?


Andrei
January 15, 2013
Re: The rfind challenge
> The order of the range returned is the same as the one received.
Not true. It should default to the genuine bidirectional range's 
direction.
If it was reversed before calling rfind we could: let the user 
reverse the result again or add the possibility to query the 
range to know it it's already been reversed (compared to original 
ordering):

@property bool reversed() {}

In fact, this is to be known anyways if the range has to keep 
internal data to know in which direction it has to move. Meaning, 
reverse should be implemented like that:

VOID reverse() {
 _reversed = true;
}

instead of

ReversedBidirectionalRange reverse() {
  return blablabla...
}

There truly are multiple ways to implement a solution to this 
problem. We could also have merge decide the direction of the 
range based on the "end" range (since we are moving towards this 
one).
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 17:14:32 UTC, Andrei Alexandrescu 
wrote:
> On 1/15/13 12:03 PM, Phil Lavoie wrote:
>> Pseudo:
>> original = range.save
>> resPos = range.retro.find
>> return Range.merge( resPos, original ) //DOES NOT WORK
>>
>> The problem with this solution is that:
>> Retro returns a different range type and it would be more 
>> complicated to
>> have the merge function work with this type.
>
> This would be difficult to implement safely, which is an 
> important disadvantage.
>
>> 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.
>> reversed.find( needle ) //In haystack :)
>> return Range.merge( reversed, original ) //Ok, start of 
>> reversed is on
>> needle and end of original hasn't moved. The order of the 
>> range returned
>> is the same as the one received.
>>
>> This is just a suggestion and any primitive could be renamed. 
>> However, I
>> think reverse is a good place to start.
>
> Reverse is really cool and immediate to implement safely for a 
> lot of ranges I can think of. How would you define rfind 
> assuming reverse?
>
>
> Andrei

Ok then, imagine we use @reverse, @reversed and @merge primitives:

auto rfind( Range, E )( Range r , E e ) if( blablabla... ) {
  auto original = r.save;
  auto reversed = r.reverse;
  auto found = find( reversed, e );
  auto res = Range.merge( found, original );
  return original.reversed ? res : res.reverse;
}

And correcting what I said previously:

void reverse() {
 _reversed = !reversed;
}
January 15, 2013
Re: The rfind challenge
>   return original.reversed ? res : res.reverse;
And correcting again, invert both to:
 return original.reversed? res.reverse: res;
January 15, 2013
Re: The rfind challenge
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
January 15, 2013
Re: The rfind challenge
On 1/15/13 12:24 PM, Phil Lavoie wrote:
> Ok then, imagine we use @reverse, @reversed and @merge primitives:

That's too many. Simpler approaches?

Andrei
January 15, 2013
Re: The rfind challenge
Ok, so to sum it up:
rfind should return the same type as provided.
Its direction (popFront()) should be the same.

auto rfing( Range, E )( Range r, E e ) if (blablabla) {
  auto original = r.save; //This is to remember the end of the 
orginal range.
  r.reverse; //Reverse it. The range keeps track of its direction.
  auto found = find( r, e ); //Now front() shall give us e, and 
popFront() moves toward original's beginning.
  auto res = Range.merge( found, original ); //Take the start of 
found, which is on e and take the end of original, which has not 
moved.
  //Where does popFront() goes now? Depends: either expect merge 
to decide for us or make sure its just dumb.
  //If it is dumb, then the assumption we make about the 
direction of the returned range is that popFront() goes in the 
not reversed direction (reversed returns false). Therefore, we 
have start on e and end where we want it, we only need to move in 
the proper direction, which is the one of the original.
  if( original.reversed ) { res.reverse; }
  return res;
}

struct DListRange {
  Node * _start;
  Node * _end; //Initialized to the lists'end.
  bool _reversed = false;

  bool empty() { return _start is null || _end is null; } //The 
user has seen it all.

  void popBack() {
    if( _reversed ) {
     _start = _start.next;
    } else {
     _end = _end.previous;
    }
  }

  ...

  @property bool reversed() { return _reversed; }
  void reverse() { _reversed = !_reversed; }

  //Dumb version.
  static typeof( this ) merge( typeof( this ) sr, typeof( this ) 
er ) {
   return typeof( this )( sr._start, er._end );
  }
}
1 2 3 4 5
Top | Discussion index | About this forum | D home