Ranges & containers : is it possible to get a SortedRange from a RedBlackTree ?

[anonymous via Digitalmars-d-learn]

On Monday, 7 July 2014 at 14:51:37 UTC, Fr wrote:
> The solution of making an array from the range works, but I'm 
> concerned about the cost of instantiating a (potentially very 
> large) array each time I need to walk across the set. Unless 
> doing that is costless in D for any reason, it does not seem 
> practical in my case.

No array is created in the example. Where do you think an array
is created?

> And when trying to compile the above example I got the 
> following error:
>
> Error: template instance std.range.SortedRange!(InputRange!int) 
> does not match template declaration SortedRange(Range, alias 
> pred = "a < b") if (isRandomAccessRange!Range && 
> hasLength!Range)

Oh, must be a restriction that's going to be lifted in 2.066. I'm
using git head, so I didn't realize that it doesn't work in 2.065.

RedBlackTree's range is sorted, of course, but it's not a random
access range. The documentation says that "SortedRange could
accept ranges weaker than random-access, but it is unable to
provide interesting functionality for them". I don't know what to
do about this. Looks like you can't get binary search through
SortedRange over a Range of a RedBlackTree. If you don't need
that, you can just drop SortedRange (and assumeSorted) and use
InputRange directly.

> I tried to replace SortedRange!InputRange thing with the 
> following :
>
> RandomAccessFinite!(InputRange!MyObject) opSlice();
>
> But then I got the folowing error:
>
> Error: template std.range.assumeSorted cannot deduce function 
> from argument types !()(InputRange!int), candidates are: [...]
>
> And I must admit that I'm stuck on that...

RandomAccessFinite is in the same family as InputRange: an
`interface` that defines/requires a set of range primitives
(front, popFront, etc). The template parameter is the element
type (e.g. MyObject).
SortedRange is a different kind of template. The template
parameter is a range type (e.g. MyObject[] or
RedBlackTree!MyObject.Range).
Replacing the one with the other doesn't make sense, and doesn't
work.

> Beside that I understand that range interfaces like SorteRange 
> are not idiomatic at all in D. So I don't mind using something 
> else, but I can't see how a could make an "abstract" range from 
> a RedBlackTree.Range struct.

SortedRange is not an interface. It's one of those
static-duck-typing wrappers. Different SortedRange instances are
incompatible types, even when the element types of the wrapped
ranges are the same.
In contrast, different instances of InputRangeObject all
implement the InputRange interface (and other more advanced
interfaces like RandomAccessFinite when possible). So, different
instances of InputRangeObject are compatible through those
interfaces, given that the element types match.

Now, if you'd want to go the static-duck-typing route, you'd
ditch the MyObjectSet interface. Instead, you'd pass
RedBlackTree!MyObject or just RedBlackTree around as a template
argument, possibly implicitly.
Maybe you could give an example of how you would use MyObjectSet.
Then we could think about a template-based alternative.

> I wouldn't mind encapsulating it in another struct or class I 
> would define myself, but it seems I cannot access the 
> RedBlackTree.Range struct from outside... For exemple with:
>
> RedBlackTree.Range rbtRange = this.sequence[];
>
> I get:
>
> Error: identifier 'Range' of 'RedBlackTree.Range' is not defined

Note that `sequence` is declared as RedBlackTree!MyObject, not
just RedBlackTree. There is no RedBlackTree.Range, but there is
RedBlackTree!MyObject.Range.