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

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.

Frédérik:

> Especially I can't figure out how std.containers can connect
> properly with std.ranges :

std.containers is still primitive, it needs to be improved and fleshed out, after Andrei's memory allocators.


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

In Phobos there are very few true interfaces. Most "interfaces" are instead compile-time protocols for templates, that create different types. But in std.range there are also (rarely used) class-based range adaptors to do what you want.

Regarding RedBlackTree not already returning SortedRange, I think this could be fixed.

Bye,
bearophile

Meta:

> (a SortedRange needs a range with random access,

I think SortedRange was recently improved, and now accepts more than just random access ranges.

Bye,
bearophile

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

Thank you very much to all of you for these very quick and precise answers !! As well as for tour recommendations about D's idiomatisms, it seems very important to me since there are so many available paradigms in D.

I'll try these solutions and I'll be able to go ahead with my first D project ;)

For the time being I like D very much, I think this language deserves much more audience and I hope it will continue to grow ! No doubt that having more "polished" std.streams and std.containers will really help, especially for people coming from Java where these API are quite clean.

Best regards,
Frédérik

Hi again,

The solution of making an array from the range works, but I'm concerned about the cost of instantiating a (potentially very large) array each time I need to walk across the set. Unless doing that is costless in D for any reason, it does not seem practical in my case.

And when trying to compile the above example I got the following error:

Error: template instance std.range.SortedRange!(InputRange!int) does not match template declaration SortedRange(Range, alias pred = "a < b") if (isRandomAccessRange!Range && hasLength!Range)

I tried to replace SortedRange!InputRange thing with the following :

RandomAccessFinite!(InputRange!MyObject) opSlice();

But then I got the folowing error:

Error: template std.range.assumeSorted cannot deduce function from argument types !()(InputRange!int), candidates are: [...]

And I must admit that I'm stuck on that...

Beside that I understand that range interfaces like SorteRange are not idiomatic at all in D. So I don't mind using something else, but I can't see how a could make an "abstract" range from a RedBlackTree.Range struct.

I wouldn't mind encapsulating it in another struct or class I would define myself, but it seems I cannot access the RedBlackTree.Range struct from outside... For exemple with:

RedBlackTree.Range rbtRange = this.sequence[];

I get:

Error: identifier 'Range' of 'RedBlackTree.Range' is not defined

Or is it a syntax-related problem ?

Thanks again for your help !
Fred

On Monday, 7 July 2014 at 14:51:37 UTC, Fr wrote:
> The solution of making an array from the range works, but I'm concerned about the cost of instantiating a (potentially very large) array each time I need to walk across the set. Unless doing that is costless in D for any reason, it does not seem practical in my case.

No array is created in the example. Where do you think an array
is created?

> And when trying to compile the above example I got the following error:
>
> Error: template instance std.range.SortedRange!(InputRange!int) does not match template declaration SortedRange(Range, alias pred = "a < b") if (isRandomAccessRange!Range && hasLength!Range)

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.

RedBlackTree's range is sorted, of course, but it's not a random
access range. The documentation says that "SortedRange could
accept ranges weaker than random-access, but it is unable to
provide interesting functionality for them". I don't know what to
do about this. 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.

> I tried to replace SortedRange!InputRange thing with the following :
>
> RandomAccessFinite!(InputRange!MyObject) opSlice();
>
> But then I got the folowing error:
>
> Error: template std.range.assumeSorted cannot deduce function from argument types !()(InputRange!int), candidates are: [...]
>
> And I must admit that I'm stuck on that...

RandomAccessFinite is in the same family as InputRange: an
`interface` that defines/requires a set of range primitives
(front, popFront, etc). The template parameter is the element
type (e.g. MyObject).
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.

> Beside that I understand that range interfaces like SorteRange are not idiomatic at all in D. So I don't mind using something else, but I can't see how a could make an "abstract" range from a RedBlackTree.Range struct.

SortedRange is not an interface. It's one of those
static-duck-typing wrappers. Different SortedRange instances are
incompatible types, even when the element types of the wrapped
ranges are the same.
In contrast, different instances of InputRangeObject all
implement the InputRange interface (and other more advanced
interfaces like RandomAccessFinite when possible). So, different
instances of InputRangeObject are compatible through those
interfaces, given that the element types match.

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.

> I wouldn't mind encapsulating it in another struct or class I would define myself, but it seems I cannot access the RedBlackTree.Range struct from outside... For exemple with:
>
> RedBlackTree.Range rbtRange = this.sequence[];
>
> I get:
>
> Error: identifier 'Range' of 'RedBlackTree.Range' is not defined

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

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

On Monday, 7 July 2014 at 19:20:24 UTC, Fr wrote:
> It's in the example above :
>
> SortedRange!(MyObject[]) opSlice() { sequence[].array.assumeSorted; }
>
> I thought that that using ".array" would lead to instantiating something.

Yes, this *will* instantiate an array and copy all of the items from the RedBlackTree into it. There's not really a way around it (unless you upgrade to 2.066 so assumeSorted will accept the result of sequence[] without having the intermediate array).