Safe Cursors and Ranges

[Pillsy]

Steven Schveighoffer Wrote:

> On Thu, 26 Aug 2010 11:17:32 -0400, Pillsy <pillsbury at gmail.com> 
> wrote:
[...]
> > If you don't mind me asking, what made you give up on it?

> A cursor that refers to one element is much more efficient to pass  
> around/copy.  

Ah, yes. If you just need the one element, I figure that you can use
a range. In most of the cases I'm familiar with, ranges are not 
distinctly less lightweight than array slices, and in D one tends to
blithely pass slices all over the place. Things could be different for 
iterating over trees---is that where you ran into trouble with the 
idea in dcollections?

> Plus the extra baggage was not needed in dcollections -- any  
> operations you perform on a cursor besides changing the value 
> require you  to have the container also (i.e. a cursor is mainly a 
> parameter to the  container).  I don't know how this relates to 
> three-legged algorithms and  straight ranges+cursors, dcollections 
> ranges+cursors would need some extra binding support to use 
> them, since you need the container to create a  
> range based on two cursors.

> > What's the advantage of not holding on to the range as part of
> > the cursor? I'm more focused on the typical value-type ranges, 
> > but I'm not seeing a lot of need for cursors that have lives 
> > independent of underlying ranges. Is the concern just one of 
> > more frequent invalidation?

> Because some cursors do not need the hard reference, it is trivial 
> to tell whether such cursors belong to a range.  For instance, it's
> trivial to tell that a pointer is part of an array.  So a cursor for an
> array would not need to refer the range it belongs to.

Ah, I see. That would make things harder to use for the specific use
case I'm thinking of, where one has a range one would like to split
at a certain element (which you might have found any number of 
ways). Basically, you can just pass around the cursor, instead of 
needing the cursor and the range. 

This strikes me as likely to be very helpful for three-legged races^W
cases.

> For instance, if I have an array, and a cursor in that array, it's trivial  
> for an allBefore operation to determine that the cursor is a member
> of the array. Now, let's say we have two slices that contain the 
> same cursor, in  your scheme, in order to use one cursor against 
> the other range, you need  to recompose the cursor, which seems
> unnecessarily awkward. 

The way I see it, two different slices can't contain the same cursor; 
a cursor into a slice will always be associated with that slice and no 
other. Maybe there are important use cases I'm missing by defining 
things this way, but I don't know what they might be.
[...]
> For example, if I want to store a link list element cursor so I can 
> change it later, why do I also have to carry around the baggage of 
> the range it came from?

You may not, but why not just hang on to the range it came from 
in the first place instead of using the cursor? What's in the link-list 
range besides a pointer to a node anyway?
[...]
> > What I'm thinking is that cursors aren't skinny ranges, they're 
> > ranges that are even fatter. You simply wouldn't use one
> > where a range would suffice. Allowing questions about whether
> > a range contains a cursor or not strikes me as just buying 
> > trouble.

> But you don't always care if a cursor is a part of a range.  For 
> example, to change or refer to a specific element of a range, 
> why do you need to refer to the range also? 

You don't, but what do you lose by referring to the range also? A 
few words on the stack (sticking with the idea that ranges are value
types)?
[...] 
> I don't have a problem with defining such a three-legged type,
> but can we call it something besides a cursor? 

Sure. How about Tripod? 8^)

I was thinking of calling them either Splitters, actually, 'cause that's
what they're there for: splitting ranges.

Cheers, 
Pillsy