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

[Meta via Digitalmars-d-learn]

On Monday, 7 July 2014 at 12:06:21 UTC, Frédérik wrote:
> Hi all,
>
> I'm discovering the D language that seems very nice in many
> aspects, but I'm quite confused by the container and range APIs
> while trying to design a very simple interface-oriented API.
>
> Especially I can't figure out how std.containers can connect
> properly with std.ranges :
>
> 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.
>
> 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 ? If so how is it possible to make it fit in a more 
> generic
> framework ?
>
> Thank you all for your help
>
> Best regards,
> Fred

There are a few problems with your code. Here and here:

void SortedRange!MyObject opSlice();
void SortedRange!MyObject opSlice() { XXXX? }

You have specified two return types; both void and 
SortedRange!MyObject. I'm assuming you probably want the latter. 
Furthermore, you can't pass just MyObject as a template argument 
to SortedRange. SortedRange is a struct that must be instantiated 
with a type that supports the range interface, and a sorting 
function (the default is function(a, b) { return a < b; }).

However, you also can't instantiate a SortedRange with 
RedBlackTree, as it doesn't implement the range interface that is 
a convention in D. You can get a range interface from 
RedBlackTree, but that *also* doesn't implement the proper 
interface (a SortedRange needs a range with random access, which 
RedBlackTree's range view doesn't support). Therefore, the 
simplest way is probably to make an array out of the 
RedBlackTree's elements and then wrapping it in a SortedRange. 
Your function would become:

import std.array;
import std.range;

SortedRange!(MyObject[]) opSlice() { 
sequence[].array.assumeSorted; }

assumeSorted is a function in std.range that assumes its argument 
is already sorted and wraps it in a SortedRange. The array 
function from std.array converts its argument into an array, 
which is in this case a range view of sequence, which you can get 
by slicing it as shown.

It seems like a lot of annoyance to go through just to get a 
SortedRange like you want, which mostly stems from the fact that 
RedBlackTree doesn't expose a random access range interface for 
implementation reasons. Maybe this will be changed in the future; 
I don't know.

As for your other question, it's more subjective and 
philosophical, so I'll leave that for someone else to answer.