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

[anonymous via Digitalmars-d-learn]

On Monday, 7 July 2014 at 19:20:24 UTC, Fr wrote:
> On Monday, 7 July 2014 at 16:58:51 UTC, anonymous wrote:
>> No array is created in the example. Where do you think an array
>> is created?
>
> It's in the example above :
>
> SortedRange!(MyObject[]) opSlice() { 
> sequence[].array.assumeSorted; }
>
> I thought that that using ".array" would lead to instantiating 
> something.

Ah, you're referring to Meta's response. Didn't catch that. Yes,
.array does create an array. Yes, it has a significant cost.

> The actual code was the following, which seems to make sense if 
> SortedRange expects random access:
>
> SortedRange!(RandomAccessFinite!MyObject) opSlice();
>
> But then I have this error on assumeSorted() :
>
> template std.range.assumeSorted cannot deduce function from 
> argument types !()(InputRange!int), candidates are: [...]

RedBlackTree's Range is not a random access range. So, at some
point the attempt to feed such a range to SortedRange must fail.

At first, it failed at SortedRange!(InputRange!MyObject). Then
you changed InputRange to RandomAccessFinite here. This passes
then.

But I guess you forgot to make the change when calling
assumeSorted:
        InputRange!MyObject r = inputRangeObject(sequence[]);
        return assumeSorted(r);
Here, instantiation of assumeSorted fails, because r is a
InputRange!MyObject. This is the "cannot deduce function" error.

If you now tried to change r's type to
RandomAccessFinite!MyObject, assumeSorted would be satisfied, but
the initialization of r would fail, because sequence[] is no
random access range.

> For various reasons I'm very attached to interface-oriented 
> design, and although I understand that this is not very 
> "D"-like, I'll try a little bit more in this way ;) I really 
> like the D language itself but for me it's almost mandatory to 
> manipulate abstract interface such as "ordered set" and then to 
> be able to switch easily between particular implementations.

Sure, go ahead. And keep asking for help when you need it. It may
not be the most popular style, but it's not exactly discouraged
either. After all, the interfaces in std.range are there
specifically to aid it. "Templated everything" has the same goal
of being able to "switch easily between particular
implementations", though.