www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Ranges & containers : is it possible to get a SortedRange from a

reply =?UTF-8?B?IkZyw6lkw6lyaWsi?= <fbp xineo.net> writes:
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
Jul 07 2014
next sibling parent reply "Meta" <jared771 gmail.com> writes:
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.
Jul 07 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Jul 07 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Jul 07 2014
prev sibling parent reply "anonymous" <anonymous example.com> writes:
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])); }
Jul 07 2014
next sibling parent =?UTF-8?B?IkZyw6lkw6lyaWsi?= <fbp xineo.net> writes:
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
Jul 07 2014
prev sibling parent reply "Fr" <fbp xineo.net> writes:
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
Jul 07 2014
parent reply "anonymous" <anonymous example.com> writes:
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.
Jul 07 2014
parent reply "Fr" <fbp xineo.net> writes:
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
Jul 07 2014
next sibling parent "Meta" <jared771 gmail.com> writes:
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).
Jul 07 2014
prev sibling parent "anonymous" <anonymous example.com> writes:
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.
Jul 07 2014