Ranges & containers : is it possible to get a SortedRange from a RedBlackTree ?
Meta via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Mon Jul 7 05:59:22 PDT 2014
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.
More information about the Digitalmars-d-learn
mailing list