RFC on range design for D2

[Bill Baxter]

On Thu, Sep 11, 2008 at 8:17 AM, Steven Schveighoffer
<schveiguy at yahoo.com> wrote:
> "Sergey Gromov" wrote
>> You don't mention here which iterator usage pattern you are trying to
>> model with ranges.  I can think of at least two.
>>
>> 1.  You use a single bidirectional 'center' iterator, center == 5.  As
>> one would naturally do with iterators.  Note then that whenever you use
>> your center for, say, backward iteration, you reconstruct the actual
>> range by calling list.begin.  You do it on each iteration.  No wonder it
>> stays valid even if you remove the first element in the meantime: you're
>> constructing your range from scratch anyway.  If you want to model this
>> pattern with ranges---no problem, keep an empty 'center' range, center
>> == (5,5), and reconstruct backward iteration range,
>>
>> reverse = all.before(center);
>>
>> whenever you need to iterate, then
>>
>> center = reverse.end;
>>
>> This 'center' range, being slightly less efficient, stays valid and
>> becomes invalid in exactly the same conditions as your classical
>> iterator.
>
> This is exactly the pattern I use.  I agree that your example would solve
> the problem, I hadn't thought of an empty range to be a cursor, that is
> clever!
>
> The only missing piece to your solution is that I must construct the range
> after the center range in order to access the value to see where I need to
> go.
>
> What I see as the biggest downside is the cumbersome and verbose code of
> moving the 'iterator' around, as every time I want to move forward, I
> construct a new range, and every time I want to move backwards I construct a
> new range (and construct a new 'center' afterwards).  So a 'move back one'
> looks like:
>
> auto before = all.before(center);
> if(!before.isEmpty)
>  center = before.pop.end;
>
> And to move forward it's:
> auto after = all.after(center);
> if(!after.isEmpty)
>  center = after.next.begin;

Maybe all we need to neatly support this sliding cursor idiom is just
some functions in the std lib:

bool cursorRetreat(R)(R all, ref R center)
{
  auto before = all.before(center);
  if(!before.isEmpty) {
    center = before.pop.end;
    return true;
  }
  return false;
}

bool cursorAdvance(R)(R all, ref R center)
{
  auto after = all.after(center);
  if(!after.isEmpty) {
   center = after.next.begin;
   return true;
  }
  return false
}

> To get the value there, I have to do:
> all.after(center).left // or whatever gets decided as the 'get first value
> of range' member
> or if opStar is used:
>
> *all.after(center);

Why is all that necessary?  Can't you just do a  *center?

>
> I much prefer:
>
> forward:
> if(center != list.end)
>    ++center;
>
> reverse:
> if(center != list.begin)
>   --center;
>
> get value:
> *center;

With the functions it becomes

forward:
cursorAdance(list,center);

reverse:
cursorRetreat(list,center);

get value:
 *center  -- this works doesn't it?

> Especially without all the extra overhead

Since we haven't really come up with any examples where the speed with
which you can slide back and forth would make a whit of difference,
perhaps the extra overhead is a non-issue.

> I see both methods as being just as open to mistakes, the first more-so, and
> more difficult to comprehend (at least for me).

I'm optimistic that this use case can also be covered by some well
chosen std library functions, similar to the above.

--bb