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]));
}