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.

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?

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.

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.

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

dsimcha wrote:
...
> 
> 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.

[OT] fwiw this is used in .NET a lot to prevent factoring into loads of interfaces. They call it Optional Feature pattern (giving further credit to the idea that patterns are workarounds for weak spots in a language...)

Hello dsimcha,


> 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.
> 

make hasLength a static const variable and it can be used for reflection if you need polymorphism add a function that returns this.hasLength. Following that pattern, you could make much of the boiler plate into a mixin:

template Range()
{
   bool p_hasLength() { return this.hasLength; }
   int length() { static if(this.hasLength) return iLength() else thrown ... ; }
}

== Quote from BCS (none@anon.com)'s article
> Hello dsimcha,
> > 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.
> >
> make hasLength a static const variable and it can be used for reflection
> if you need polymorphism add a function that returns this.hasLength. Following
> that pattern, you could make much of the boiler plate into a mixin:
> template Range()
> {
>     bool p_hasLength() { return this.hasLength; }
>     int length() { static if(this.hasLength) return iLength() else thrown
> ... ; }
> }

Point of clarification, since I realized I omitted an important detail:  When I said "every range has a hasLength() method", I meant every range that inherits from the Range interface and is part of the class hierarchy.  This does **not** apply to struct based ranges that only use compile time duck typing and are not part of any class hierarchy.  These would be completely unaffected.