On Thu, 26 Aug 2010 11:17:32 -0400, Pillsy <pillsb...@gmail.com> wrote:
Steven Schveighoffer Wrote:
On Thu, 26 Aug 2010 10:18:51 -0400, Pillsy <pillsb...@gmail.com>
wrote:
[...]
> The key idea is that these cursors aren't a primitive part of a
> range; instead, they take a range and add a position *inside*
> the range. They're a perfect fit for all those "three-legged"
> operations out there because they actually have three legs.
[...]
The 'three-legged' cursor as you propose was an early idea of
mine too.
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. 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.
My view is that a cursor should be separate from a range, and a
range should either be able to tell if a cursor is part of it (@safe)
or be told that a cursor is a part of it (@system or @trusted).
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.
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. Such a scheme
is not possible on other ranges, but that just means those ranges don't
support safe calls for allBefore and the like. For those ranges, a
3-legged type would be appropriate, but the 3-legged thing could be a
combination of a cursor and a range, with the cursor proven to be part of
the range -- an invariant of the 3-legged type.
Having a cursor point to exactly one element allows more flexibility,
because you could use a cursor with multiple ranges. It also decouples
the cursor from a range that might be superfluous information. 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?
One of the drawbacks is the cursor cannot move to other elements or alter
topology, it's strictly a reference-only. Another reason to have the
3-legged type.
IME, three-legged operations are fairly common, but four- and more-
legged operations which can't be easily decomposed into consecutive
three-legged operations are very uncommon.
I have no experience with three-legged operations. I just looked at
cursors from the point of view of reference to a single element. Such an
ability is important for a container library.
I can see such an ability being important for simple operations as well,
not just algorithms.
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? The composition of a range and cursor together
can be guarded by @system or @trusted indicating the type system is taking
your word for it, but in some cases, it can be proven without assumption
(i.e. arrays).
I don't have a problem with defining such a three-legged type, but can we
call it something besides a cursor? Not that I have a trademark or
anything, but it would be really confusing to have it mean two different
things depending on context :)
As I said, I can see utility in having a three-legged beast that combines
a cursor and a range, but I see value in having a simple one-element
cursor as well.
-Steve
