"Andrei Alexandrescu" wrote
> Steven Schveighoffer wrote:
>>> I am also sure that if I sat down long enough contemplating my navel I
>>> could come with more examples of iterators=good/ranges=bad.
>>> <snip>
>>
>> Now you're just being rude :)  Please note that I'm not attacking you personally.  All I'm pointing out is that your solution solves certain problems VERY well, but leaves other problems not solved.  I think allowing iterators/cursors would solve all the problems.  I might be proven wrong, but certainly I don't think you've done that so far.  I'd love to be proven wrong, since I agree that iterators are generally unsafe.
>
> Didn't mean to. You are making great points, and I hope (without being sure) they can be addressed. The "contemplating navel" thing is a fave quote of mine from Bjarne's book on C++.

Didn't know that :)  Sometimes when someone is not aware of a quote/joke, it seems more personally motivated.  I agree that our discussion is not bringing either of us to the other's side.  I'm also hopeful the points can be addressed with ranges.

-Steve

"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;

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);

I much prefer:

forward:
if(center != list.end)
    ++center;

reverse:
if(center != list.begin)
   --center;

get value:
*center;

Especially without all the extra overhead

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

-Steve

Sergey Gromov wrote:
> Sean Kelly <sean@invisibleduck.org> wrote:
>> Sergey Gromov wrote:
>>> Now the same algorithm in ranges:
>>>
>>>> Merge_backward(R1, R2, R3)(R1 s1, R2 s2, R3 dst)
>>>> {
>>>>     for (;;)
>>>>     {
>>>>         if (s1.isEmpty())
>>>>             dst[] = s2[];
>>>>         else if (s2.isEmpty())
>>>>             dst[] = s1[];
>> I'm not sure the above is correct.  It should return after the copy is performed, and the code also assumes that the size of dst is equal to the size of s2 and s1, respectively.
> 
> Of course there should be return statements, thank you.  I've never tested this code (obviously), just've thrown it together, so there ought to be stupid mistakes like this.
> 
> As to the destination size.  This is merge sort.  The size of destination buffer must be the sum of the sizes of source buffers.  As soon as one of the source buffers is empty, i.e. completely moved to the destination, there must be place exactly for what left in another source buffer.  If this condition doesn't hold then the arguments weren't correct in the first place.

Oops, of course.


Sean

On Thu, Sep 11, 2008 at 8:17 AM, Steven Schveighoffer <schveiguy@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;
>
> 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);
>
> I much prefer:
>
> forward:
> if(center != list.end)
>    ++center;
>
> reverse:
> if(center != list.begin)
>   --center;
>
> get value:
> *center;
>
> Especially without all the extra overhead
>
> I see both methods as being just as open to mistakes, the first more-so, and more difficult to comprehend (at least for me).
>

Well put.  I was trying to come up with a comparison like this last night.  But at 3am I was just too tired to pull it off.  Great example of the kind of cognitive overload that comes from this kind of scenario.

I really believe the point that ranges are good for std.algorithm is fine.  But when people use iterators in code they are often used like the above.  This whole shifting back and forth over a linked list was seeming very familiar to me last night and I recalled this morning that I had written some code to implement undo which worked in this very way.  The linked list was the undo stack.  And undo() moved the current iterator one direction, redo() moved it the other.

So far though we don't seem to be able to come up with a good example
other of where ranges are weak than traversing a list back and forth.
 Note that "move back and forth according to some user input" is not
clearly not an "algorithm" that would be in std.algorithm.  But it
does come up often enough in applications.  I don't think the fact
that it's not strictly an Algorithm-with-a-captial-A makes it any less
important.

But it is a little fishy that we can't come up with any other example besides sliding a bead on a wire back and forth.

--bb

On Thu, Sep 11, 2008 at 8:17 AM, Steven Schveighoffer <schveiguy@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

On Thu, Sep 11, 2008 at 9:32 AM, Bill Baxter <wbaxter@gmail.com> wrote:
> On Thu, Sep 11, 2008 at 8:17 AM, Steven Schveighoffer
>> 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?

Oh, I get it.  It's empty.  Duh.

Ok, so you can have third cursor function in the std lib:

T cursorValue(R,T)(R all, R center)
{
   return all.after(center).left;
}
... plus the
cursorAdvance and cursorRetreat.

--bb

Bill Baxter wrote:
> So far though we don't seem to be able to come up with a good example
> other of where ranges are weak than traversing a list back and forth.
>
> ...
>
> But it is a little fishy that we can't come up with any other example
> besides sliding a bead on a wire back and forth.

I dunno about that.

I can think of lots of examples where the "range" metaphor is an awkward interloper between the container and the iteration logic:

maps, sets, bags, markov models, graphs, trees (especially in a breadth-first traversal)

The word "range" and the idea of the range "moving", "shrinking", or being "empty" only matches my concept of "iteration" if I think strictly in terms of sequential containers (arrays, slices, lists, etc).

I think the range methaphor is a very cool way of connecting sequential containers with algorithms (especially divide-and-conquer algorithms, which seem particularly well-suited to the range metaphor).

But if I want to visit each <p> node in a DOM tree, I have a hard time visualizing how a "range" fits into that process.

Maybe it's just terminology. I'm not sure yet.

--benji

On Thu, Sep 11, 2008 at 9:41 AM, Benji Smith <dlanguage@benjismith.net> wrote:
> Bill Baxter wrote:
>>
>> So far though we don't seem to be able to come up with a good example other of where ranges are weak than traversing a list back and forth.
>>
>> ...
>>
>> But it is a little fishy that we can't come up with any other example besides sliding a bead on a wire back and forth.
>
> I dunno about that.
>
> I can think of lots of examples where the "range" metaphor is an awkward interloper between the container and the iteration logic:
>
> maps, sets, bags, markov models, graphs, trees (especially in a
> breadth-first traversal)

Iterators for maps, sets, bags, graphs, trees are usually either for
pointing to a found element or for iterating over the whole thing.
With ranges the former just becomes a degenerate range where only one
end is actually important.  The other end would probably be then end()
of the container in the STL sense.
The latter is no problem if you just want to forward iterate over everything.

> The word "range" and the idea of the range "moving", "shrinking", or being "empty" only matches my concept of "iteration" if I think strictly in terms of sequential containers (arrays, slices, lists, etc).

For the one-way ranges, the range is equivalent to a forward iterator plus an end().  You can do exactly the same things with it.  The end() may very happily not actually exist, though, if not needed, or if it depends on some dynamic condition, like for your HMM example.

> I think the range methaphor is a very cool way of connecting sequential containers with algorithms (especially divide-and-conquer algorithms, which seem particularly well-suited to the range metaphor).
>
> But if I want to visit each <p> node in a DOM tree, I have a hard time visualizing how a "range" fits into that process.

For that you just use a forward range, which is just forward iterator plus a stopping criterion, that's all.

> Maybe it's just terminology. I'm not sure yet.

Maybe.

There is one thing so far that we can point to and say "ranges aren't so great for this".  That's the case where you want to scan forward *and* backward over your data.  But I now believe that std lib functions can cover that usage case in a non-burdensome way, too.

--bb

Walter Bright wrote:

> But for many types, there is no such thing as an invalid value

Why can one then define

|   typedef int T=void; // T.init == void

-manfred

-- 
If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)

"Bill Baxter" wrote
> On Thu, Sep 11, 2008 at 9:32 AM, Bill Baxter <wbaxter@gmail.com> wrote:
>> On Thu, Sep 11, 2008 at 8:17 AM, Steven Schveighoffer
>>> 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?
>
> Oh, I get it.  It's empty.  Duh.
>
> Ok, so you can have third cursor function in the std lib:
>
> T cursorValue(R,T)(R all, R center)
> {
>   return all.after(center).left;
> }
> ... plus the
> cursorAdvance and cursorRetreat.

That is all fine and dandy in the world of "I don't care how well my iterators perform or how much code bloat is added because of them," but I usually work in a different world ;)

But if I were forced not to use an iterator model (which isn't the case, iterators should be very possible without compiler help), I would actually implement this as a wrapper struct:

struct Cursor(containerType)
{
   private Range!(containerType) _cur;
   private containerType owner;

   Cursor  moveLeft() {...}
   Cursor moveRight() {...}
   bool hasLeft() {...}
   etc.
}

Thus one can implement iterators on top of ranges, but I'd argue that ranges are much easier to implement on top of iterators.

In any case, I think there are benefits to having a range type that is not necessarily defined as two iterators.

-Steve