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
