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

[Fr via Digitalmars-d-learn]

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.


> 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.

OK that's what I was suspecting... Thanks for checking that.

> 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.

Yes it seems this is the way to go in my case.

As far as I know, true (efficient) random access on a RB tree is 
not a "natural" thing and I would nto have expected that ranges 
coming from those trees would support it. However it's curious 
that random access was required by SortedSet, but as far as I 
understand, this constraint has been recently dropped.

> RandomAccessFinite is in the same family as InputRange [...]
> 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.

Of course ! I'm sorry I retyped it incorrectly, I tested so many 
things... 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: [...]

> [...] 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.

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.


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

Yes, of course, stupid question, sorry...


Thank you very much for your help !!

Best regards,
Frédérik