digitalmars.D.learn - Ranges & containers : is it possible to get a SortedRange from a
- =?UTF-8?B?IkZyw6lkw6lyaWsi?= (31/31) Jul 07 2014 Hi all,
- Meta (35/68) Jul 07 2014 There are a few problems with your code. Here and here:
- bearophile (5/6) Jul 07 2014 I think SortedRange was recently improved, and now accepts more
- bearophile (11/17) Jul 07 2014 std.containers is still primitive, it needs to be improved and
- anonymous (45/68) Jul 07 2014 SortedRange is not a generic interface. Its template parameter is
- =?UTF-8?B?IkZyw6lkw6lyaWsi?= (13/13) Jul 07 2014 Thank you very much to all of you for these very quick and
- Fr (31/31) Jul 07 2014 Hi again,
- anonymous (40/68) Jul 07 2014 No array is created in the example. Where do you think an array
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
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, FredThere 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
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
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
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
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
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
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 definedNote that `sequence` is declared as RedBlackTree!MyObject, not just RedBlackTree. There is no RedBlackTree.Range, but there is RedBlackTree!MyObject.Range.
Jul 07 2014
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
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
On Monday, 7 July 2014 at 19:20:24 UTC, Fr wrote:On Monday, 7 July 2014 at 16:58:51 UTC, anonymous wrote:Ah, you're referring to Meta's response. Didn't catch that. Yes, .array does create an array. Yes, it has a significant cost.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.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