Class/Interface Modeling of Ranges

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Fri Nov 20 20:00:22 PST 2009


dsimcha wrote:
> I'm thinking about what the best way might be to model ranges in an
> OO/inheritance style for collections/containers, and needless to say it's
> pretty complicated and virtually impossible to model well.  (As an aside, this
> is why I like duck typing, be it compile time or traditional, so much.)
> 
> At the top of the hierarchy is forward ranges, or maybe input ranges.
> Bidirectional ranges are obviously a subclass of input ranges.  Then things
> get ugly.

I'm very glad you opened discussion on this matter!

A possible starting point is 
http://erdani.com/publications/on-iteration.html. If we take that route, 
then instead of input ranges we have one-pass ranges which may be used 
for input, output, or both. Another thing is that ranges must be 
parameterized on the iterated type and also on the reference type. 
Here's how I think we can do it:

interface OnePassRange(T, alias Ref) {
     @property bool empty();
     @property Ref!T front();
     void popFront();
}

So now we can read and write stuff. For forward ranges there's the 
save() extra operation:

interface ForwardRange(T, alias Ref) : OnePassRange!(T, Ref) {
     ForwardRange!(T, Ref) save();
}

Double-ended range adds back and popBack:

interface DoubleEndedRange(T, alias Ref) : ForwardRange!(T, Ref) {
     @property Ref!T back();
     void popBack();
}

Finally we have two kinds of random access ranges:

interface InfiniteRandomAccessRange(T, alias Ref)
         : ForwardRange!(T, Ref) {
     Ref!T opIndex(size_t);
}

interface RandomAccessRange(T, alias Ref)
         : DoubleEndedRange!(T, Ref) {
     Ref!T opIndex(size_t);
     RandomAccessRange!(T, alias Ref) opSlice(size_t, size_t);
}

Things get a bit more difficult when opDollar enters the stage. I 
haven't thought that through completely yet.

> 1.  Random access ranges must also be bidirectional and define back() and
> popBack() iff the range is finite.  Does iRandomAccessRange(T) inherit from
> iForwardRange(T), iBidirectionalRange(T), or neither?

I think the notions of infinite random-access range is distinct from 
that of finite random-access range.

> 2.  How about length and assignable elements?  How do we fit these into the
> hierarchy?  We get combinatorial explosion.  We can't have an
> iRandomAccessRangeWithLengthAndAssignableElements(T), an
> iRandomAccessRange(T), an iRandomAccessRangeWithAssignableElements(T), ad nauseum.

Length is a separate interface I think. Whether elements are assigned or 
not is decided by Ref. If we still have combinatorial issues, encoding 
capabilities as policies should help.

> 3.  Can we simplify this by using runtime exceptions instead of compile time
> errors for some of this stuff?  For example, every range would have a
> hasLength() method and a length() method.  If hasLength() is false, length()
> would throw.  Though this sacrifices compile time error checking, it might be
> better in some ways.  For example, if a given compile time type may or may not
> have length depending on its runtime type, you could check at runtime whether
> it has a length and adapt your handling of it accordingly.

Would be great to avoid that.


Andrei



More information about the Digitalmars-d mailing list