www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Range proposal

reply "Bill Baxter" <wbaxter gmail.com> writes:
The current range proposal may be putting too much emphasis on the
range being a contiguous linear entity.  As something which represents
a begin and and end and *everything in between*.  That is only true in
certain special cases.  Even with linked lists, you don't really have
that.  You just have two pointers that could be pointing to anywhere
in memory.  The range doesn't really represent everything in between
those pointers.  Other examples that contradict thinking of a range as
simply "here to there and everything in between" are infinite
generators, or random iterators (like the HMM example).

It may lead to a cleaner nomenclature if we acknowledge this fact, and
think of a range more as an iterator plus a sentinel, rather than
trying to emphasize the symmetry between the beginning and end items
that really only exists for special cases.

In this terminology the "left" thing points at the "value" and the
"right" thing is the "end".

Here's one way that could pan out:

** Basics
r.atEnd() -- instead of r.isEmpty()

** Input range/ Forward range
e = r.value      -- instead of r.left
r.next             -- still ok
r.moveTo(s)       -- instead of rightUnion
r.moveToEndOf(s)     -- instead of rightDiff

** Bidirectional range
r.last            -- instead of r.right
r.pop            -- ok as-is
r.moveEndToEndOf(s)             -- instead of leftUnion
   --> or just s.moveTo(r)
r.moveEndTo(s)                   -- instead of leftDiff

** Random access
ok as-is


So re-iterating, the basic idea is to think of a range as an iterator
with a current value, that happens to have an extra thing hanging
around, it's "end", a sentinel that marks a stopping condition.

Thoughts?
--bb
Sep 09 2008
next sibling parent reply "Bruce Adams" <tortoise_74 yeah.who.co.uk> writes:
On Wed, 10 Sep 2008 04:42:25 +0100, Bill Baxter <wbaxter gmail.com> wrote:


 The current range proposal...


What current range proposal? I'm interested in what you're saying but a  
little
context would be nice. The same with your post on bi-directional iterators.

I googled and found this:

http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html

The only thing that indicates that this is a proposal and not a full  
integrated
and implemented library is the tmp in the URL. So what discussion have I  
missed?

Regards,

Bruce.
Sep 10 2008
parent "Bill Baxter" <wbaxter gmail.com> writes:
On Wed, Sep 10, 2008 at 4:13 PM, Bruce Adams <tortoise_74 yeah.who.co.uk> wrote:

 On Wed, 10 Sep 2008 04:42:25 +0100, Bill Baxter <wbaxter gmail.com> wrote:


 The current range proposal...




Oh, seems it's actually taking place on digitalmars.d.announce.
You really can't omit d.announce if you're interested in discussions
about D's future.  For better or worse, mondo threads pop up there all
too often on the heels of big announcements.


 What current range proposal? I'm interested in what you're saying but a
 little
 context would be nice. The same with your post on bi-directional iterators.

 I googled and found this:

 http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html


That's the one.


 The only thing that indicates that this is a proposal and not a full
 integrated
 and implemented library is the tmp in the URL. So what discussion have I
 missed?


digitalmars.d.announce.

I suppose he wrote the proposal as if it were a done deal to avoid
having to rewrite it when it is a done deal.

--bb
Sep 10 2008
prev sibling parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Bill Baxter wrote:


 think of a range more as an iterator plus a sentinel


The problem with both models is, that there are canonical operators one 
both models, which are somehow frantically hidden. This is shown

1) by the deliberately constructed compound of `[left,right]
[Diff,Union]'
2) the missing definition of a "subrange"

Both seem undefinable without having some notion of "concatenation"---
and if one has concatenation, a request for the reverse operation 
"splitting" is unavoidable.

In fact the semantics of `r.moveTo(s)' seems not to be fully defined in 
both approaches.

In fact in your approach of thinking of `r.moveto(s)', the "iterator" 
of `s' turns into a "sentinel" for `r', thereby making sentinels and 
iterators to synonyms.

If there is indeed a structural similarity to Andrei's approach, the 
same problem must show up somewhere.

-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)
Sep 10 2008
parent "Bill Baxter" <wbaxter gmail.com> writes:
On Thu, Sep 11, 2008 at 2:04 AM, Manfred_Nowak <svv1999 hotmail.com> wrote:

 Bill Baxter wrote:


 think of a range more as an iterator plus a sentinel


 The problem with both models is, that there are canonical operators one
 both models, which are somehow frantically hidden. This is shown

 1) by the deliberately constructed compound of `[left,right]
 [Diff,Union]'
 2) the missing definition of a "subrange"

 Both seem undefinable without having some notion of "concatenation"---
 and if one has concatenation, a request for the reverse operation
 "splitting" is unavoidable.

 In fact the semantics of `r.moveTo(s)' seems not to be fully defined in
 both approaches.

 In fact in your approach of thinking of `r.moveto(s)', the "iterator"
 of `s' turns into a "sentinel" for `r', thereby making sentinels and
 iterators to synonyms.


Well not necessarily synonyms, because how that iterator is turned
into a sentinel is up to the moveTo method.  But yeh, in most cases
they probably would be implemented under the hood using the same type
-- that's how STL works, after all, and it turns out reasonably well.
And probably how boost's ranges are implemented, just as a pair of
iterators... (though I admit I haven't taken a look at those at all).

--bb
Sep 10 2008