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

[anonymous via Digitalmars-d-learn]

On Monday, 7 July 2014 at 12:06:21 UTC, Frédérik wrote:

I'm trying to achieve something like that (approximate D code):

interface MyObjectSet
{
     void add(MyObject o);
     void SortedRange!MyObject opSlice();
}

class SomeRedBlackBasedImplementation
{
     private RedBlackTree!MyObject sequence = new
RedBlackTree!MyObject();

     void add(MyObject o) { this.sequence.insert(o); }
     void SortedRange!MyObject opSlice() { XXXX? }
}


I would need to get the range that comes from the red black tree
(as returned by this.sequence[]) but I can't figure out how to
map it to a generic interface like SortedRange that would be
suitable to write a clean interface above.

SortedRange is not a generic interface. Its template parameter is
not the element type, but the type of the underlying range.

It seems to me that the Range used by RedBlackTree is a kind of
private struct that does not implement an interface but just

complies with some implicit contract about range properties. Am I right ?

yes (it's not `private`, but it's a type specific to RedBlackTree)

If so how is it possible to make it fit in a more generic framework ?

Use inputRangeObject(sequence[]) to get an instance of the
InputRange interface over the range. Then use assumeSorted to get
a SortedRange!(InputRange!MyObject). Of course, only use
assumeSorted when the range is already sorted. Otherwise, use
std.algorithm.sort.

Such interface/Object oriented style is not very popular in D,
though, as far as I can tell. Static duck typing through
templates seems to be more fashionable, e.g. what you called
"some implicit contract about range properties".

Full, compiling example:

import std.container: RedBlackTree;
import std.range;

alias MyObject = int;

interface MyObjectSet
{
     void add(MyObject o);
     SortedRange!(InputRange!MyObject) opSlice();
}

class SomeRedBlackBasedImplementation : MyObjectSet
{
     private RedBlackTree!MyObject sequence;
     this()
     {
         sequence = new RedBlackTree!MyObject();
     }

     void add(MyObject o) { this.sequence.insert(o); }
     SortedRange!(InputRange!MyObject) opSlice()
     {
         InputRange!MyObject r = inputRangeObject(sequence[]);
         return assumeSorted(r);
     }
}

void main()
{
     MyObjectSet x = new SomeRedBlackBasedImplementation;
     x.add(1);
     x.add(3);
     x.add(2);
     import std.algorithm: equal;
     assert(equal(x[], [1, 2, 3]));
}