* Using Red-Black Trees @ 2010-11-13 11:20 Björn 2010-11-13 12:14 ` Phil Thornley ` (3 more replies) 0 siblings, 4 replies; 32+ messages in thread From: Björn @ 2010-11-13 11:20 UTC (permalink / raw) I need a self-balancing binary search tree (for a Bentley/Ottmann implementation), such as the red-black tree that is now part of Ada.Containers. I need basic operations like insert/remove, next/prev and find. However, the GNAT implementation of this data structure seems a bit scary to me and I'm not really sure how to instantiate the generics and what operations to use. Would someone be able to provide some example of usage? And yes, I'am aware of that a lot of the other container implementations uses this structure. I was hoping for something a bit more boiled down. Regards, Björn ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 11:20 Using Red-Black Trees Björn @ 2010-11-13 12:14 ` Phil Thornley 2010-11-13 13:10 ` Alex Mentis ` (2 subsequent siblings) 3 siblings, 0 replies; 32+ messages in thread From: Phil Thornley @ 2010-11-13 12:14 UTC (permalink / raw) On Nov 13, 11:20 am, Björn <ssh9...@hotmail.com> wrote: > I need a self-balancing binary search tree (for a Bentley/Ottmann > implementation), such as the red-black tree that is now part of > Ada.Containers. I need basic operations like insert/remove, next/prev > and find. However, the GNAT implementation of this data structure > seems a bit scary to me and I'm not really sure how to instantiate the > generics and what operations to use. Would someone be able to provide > some example of usage? And yes, I'am aware of that a lot of the other > container implementations uses this structure. I was hoping for > something a bit more boiled down. > > Regards, > Björn Have a look at the stuff under Data Structures on http://www.eternallyconfuzzled.com/jsw_home.aspx There's a lot of good stuff in there (all in C) including iterative algorithms for red-black trees that was used for a SPARK project. Cheers, Phil ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 11:20 Using Red-Black Trees Björn 2010-11-13 12:14 ` Phil Thornley @ 2010-11-13 13:10 ` Alex Mentis 2010-11-13 13:23 ` Björn ` (2 more replies) 2010-11-13 21:53 ` Jeffrey Carter 2010-11-13 23:51 ` robin 3 siblings, 3 replies; 32+ messages in thread From: Alex Mentis @ 2010-11-13 13:10 UTC (permalink / raw) Bj�rn wrote: > I need a self-balancing binary search tree (for a Bentley/Ottmann > implementation), such as the red-black tree that is now part of > Ada.Containers. I need basic operations like insert/remove, next/prev > and find. However, the GNAT implementation of this data structure > seems a bit scary to me and I'm not really sure how to instantiate the > generics and what operations to use. Would someone be able to provide > some example of usage? And yes, I'am aware of that a lot of the other > container implementations uses this structure. I was hoping for > something a bit more boiled down. > > Regards, > Bj�rn There's a Red-Black Tree in Ada.Containers?! Can someone tell me where to find it in the ARM? ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 13:10 ` Alex Mentis @ 2010-11-13 13:23 ` Björn 2010-11-13 13:53 ` Alex Mentis 2010-11-15 8:49 ` Stephane Carrez 2010-11-15 22:46 ` Randy Brukardt 2 siblings, 1 reply; 32+ messages in thread From: Björn @ 2010-11-13 13:23 UTC (permalink / raw) > There's a Red-Black Tree in Ada.Containers?! Can someone tell me where > to find it in the ARM? My misstake. Apparently it is an internal GNAT unit. /Björn ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 13:23 ` Björn @ 2010-11-13 13:53 ` Alex Mentis 2010-11-13 14:06 ` Björn 2010-11-13 16:31 ` Simon Wright 0 siblings, 2 replies; 32+ messages in thread From: Alex Mentis @ 2010-11-13 13:53 UTC (permalink / raw) Bj�rn wrote: > > There's a Red-Black Tree in Ada.Containers?! �Can someone tell me > > where to find it in the ARM? > > My misstake. Apparently it is an internal GNAT unit. > > /Bj�rn I found a red-black tree implementation here, but I haven't used it, so I can't vouch for its correctness/functionality: http://users.cis.fiu.edu/~weiss/ada.html If an AVL tree will work for you, there appears to be a wider selection of those implemented in Ada on the Internets. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 13:53 ` Alex Mentis @ 2010-11-13 14:06 ` Björn 2010-11-13 16:31 ` Simon Wright 1 sibling, 0 replies; 32+ messages in thread From: Björn @ 2010-11-13 14:06 UTC (permalink / raw) > I found a red-black tree implementation here, but I haven't used it, so > I can't vouch for its correctness/functionality: > > http://users.cis.fiu.edu/~weiss/ada.html Thank you for the pointer. I have never seen that page before. It seems to have a lot of interesting resources and it saves me from starting from scratch. /Björn ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 13:53 ` Alex Mentis 2010-11-13 14:06 ` Björn @ 2010-11-13 16:31 ` Simon Wright 1 sibling, 0 replies; 32+ messages in thread From: Simon Wright @ 2010-11-13 16:31 UTC (permalink / raw) "Alex Mentis" <foo@invalid.invalid> writes: > If an AVL tree will work for you, there appears to be a wider > selection of those implemented in Ada on the Internets. One is BC.Containers.Trees.AVL at http://sourceforge.net/projects/booch95/. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 13:10 ` Alex Mentis 2010-11-13 13:23 ` Björn @ 2010-11-15 8:49 ` Stephane Carrez 2010-11-15 15:32 ` John B. Matthews 2010-11-15 22:46 ` Randy Brukardt 2 siblings, 1 reply; 32+ messages in thread From: Stephane Carrez @ 2010-11-15 8:49 UTC (permalink / raw) To: Alex Mentis Hi! On 11/13/2010 02:10 PM, Alex Mentis wrote: > Bj�rn wrote: > >> I need a self-balancing binary search tree (for a Bentley/Ottmann >> implementation), such as the red-black tree that is now part of >> Ada.Containers. I need basic operations like insert/remove, next/prev >> and find. However, the GNAT implementation of this data structure >> seems a bit scary to me and I'm not really sure how to instantiate the >> generics and what operations to use. Would someone be able to provide >> some example of usage? And yes, I'am aware of that a lot of the other >> container implementations uses this structure. I was hoping for >> something a bit more boiled down. >> >> Regards, >> Bj�rn > > There's a Red-Black Tree in Ada.Containers?! Can someone tell me where > to find it in the ARM? GNAT uses the Red-Black tree for the implementation of ordered maps and sets. You should use Ada.Containers.Ordered_Maps instead. Instantiation is similar to the Hashed_Maps but you should need to specify the comparison operator "<". See http://www.adaic.org/standards/05rm/html/RM-A-18-6.html (Likewise for the Indefinite_Ordered_* packages) Stephane ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-15 8:49 ` Stephane Carrez @ 2010-11-15 15:32 ` John B. Matthews 0 siblings, 0 replies; 32+ messages in thread From: John B. Matthews @ 2010-11-15 15:32 UTC (permalink / raw) In article <4CE0F407.6090101@gmail.com>, Stephane Carrez <Stephane.Carrez@gmail.com> wrote: > > There's a Red-Black Tree in Ada.Containers?! Can someone tell me > > where to find it in the ARM? > > GNAT uses the Red-Black tree for the implementation of ordered maps > and sets. > > You should use Ada.Containers.Ordered_Maps instead. Instantiation is > similar to the Hashed_Maps but you should need to specify the > comparison operator "<". > > See http://www.adaic.org/standards/05rm/html/RM-A-18-6.html > (Likewise for the Indefinite_Ordered_* packages) Here's a simple example that uses an instance of Ordered_Maps to examine collisions that would occur in an instance of Hashed_Maps: <http://home.roadrunner.com/~jbmatthews/jumble.html#sec2> -- John B. Matthews trashgod at gmail dot com <http://sites.google.com/site/drjohnbmatthews> ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 13:10 ` Alex Mentis 2010-11-13 13:23 ` Björn 2010-11-15 8:49 ` Stephane Carrez @ 2010-11-15 22:46 ` Randy Brukardt 2010-11-16 16:10 ` Gene 2010-11-17 22:38 ` Yannick Duchêne (Hibou57) 2 siblings, 2 replies; 32+ messages in thread From: Randy Brukardt @ 2010-11-15 22:46 UTC (permalink / raw) "Alex Mentis" <foo@invalid.invalid> wrote in message news:ibm2op$m1i$1@news.eternal-september.org... ... > There's a Red-Black Tree in Ada.Containers?! Can someone tell me where > to find it in the ARM? It's not explicit. One of the possible implementations of the ordered sets and maps is to use a Red-Black tree; presumably this is what GNAT's implementation is doing. Randy. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-15 22:46 ` Randy Brukardt @ 2010-11-16 16:10 ` Gene 2010-11-16 17:17 ` Alex Mentis 2010-11-17 22:38 ` Yannick Duchêne (Hibou57) 1 sibling, 1 reply; 32+ messages in thread From: Gene @ 2010-11-16 16:10 UTC (permalink / raw) On Nov 15, 5:46 pm, "Randy Brukardt" <ra...@rrsoftware.com> wrote: > "Alex Mentis" <f...@invalid.invalid> wrote in message > > news:ibm2op$m1i$1@news.eternal-september.org... > ... > > > There's a Red-Black Tree in Ada.Containers?! Can someone tell me where > > to find it in the ARM? > > It's not explicit. One of the possible implementations of the ordered sets > and maps is to use a Red-Black tree; presumably this is what GNAT's > implementation is doing. > > Randy. Indeed, here is a fragment of the GNAT ordered map implementation via rb trees: type Node_Type is limited record Parent : Node_Access; Left : Node_Access; Right : Node_Access; Color : Red_Black_Trees.Color_Type := Red_Black_Trees.Red; Key : Key_Type; Element : Element_Type; end record; ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-16 16:10 ` Gene @ 2010-11-16 17:17 ` Alex Mentis 2010-11-16 19:51 ` Randy Brukardt 0 siblings, 1 reply; 32+ messages in thread From: Alex Mentis @ 2010-11-16 17:17 UTC (permalink / raw) Gene wrote: > On Nov 15, 5:46�pm, "Randy Brukardt" <ra...@rrsoftware.com> wrote: > > "Alex Mentis" <f...@invalid.invalid> wrote in message > > > > news:ibm2op$m1i$1@news.eternal-september.org... > > ... > > > > > There's a Red-Black Tree in Ada.Containers?! �Can someone tell me > > > where to find it in the ARM? > > > > It's not explicit. One of the possible implementations of the > > ordered sets and maps is to use a Red-Black tree; presumably this > > is what GNAT's implementation is doing. > > > > � � � � � � � � � � � � � � � � � � Randy. > > Indeed, here is a fragment of the GNAT ordered map implementation via > rb trees: > > type Node_Type is limited record > Parent : Node_Access; > Left : Node_Access; > Right : Node_Access; > Color : Red_Black_Trees.Color_Type := Red_Black_Trees.Red; > Key : Key_Type; > Element : Element_Type; > end record; In the case of the OP, he wanted a specific data structure (rb tree). Since the ARM doesn't specify exactly how a container must be implemented, he could go sleuthing through the library code like this to find out, and in this case he would be lucky enough to determine that there is, in fact, a container using rb trees, so hooray! Of course that doesn't guarantee that GNAT will continue to use red-black trees for these containers in future versions. It might be nice if, since they're alreay implementing the rb tree for the ordered sets and maps, GNAT just went ahead and made the library more visible by documenting it and placing it in the GNAT package namespace. I mean, they have a Bubble Sort package in there (Bubble sort? Really?), so why not some commonly-used tree structures? I think we're getting Multi-Way Trees in 2012, but...meh. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-16 17:17 ` Alex Mentis @ 2010-11-16 19:51 ` Randy Brukardt 2010-11-16 21:24 ` Colin Paul Gloster 2010-11-17 2:50 ` Alex Mentis 0 siblings, 2 replies; 32+ messages in thread From: Randy Brukardt @ 2010-11-16 19:51 UTC (permalink / raw) "Alex Mentis" <foo@invalid.invalid> wrote in message news:ibueau$aac$1@news.eternal-september.org... ... > In the case of the OP, he wanted a specific data structure (rb tree). Unless you are a student, worrying about a specific data structure is silly in 99% of the cases. What you care about is that you use a data structure which has sufficient performance for your app. One presumes that implementations will provide high-performance implementations, tuned to the specific target. Programming to the standard containers is the easiest first step. In the rare case where the performance isn't sufficient, then a custom data structure will be needed -- but it is almost certain that you'll need to program that structure yourself (because you'll want to squeeze out any overhead from features that you don't need). > Since the ARM doesn't specify exactly how a container must be > implemented, he could go sleuthing through the library code like this > to find out, and in this case he would be lucky enough to determine > that there is, in fact, a container using rb trees, so hooray! Or he could just use the standard containers, and find out that in fact the performance is good enough for his application, so hooray, he doesn't need to worry about it further. I don't know what data structures this newsreader and browser use, but they're good enough for the application, so why should I care?? Same goes for the standard containers. Randy. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-16 19:51 ` Randy Brukardt @ 2010-11-16 21:24 ` Colin Paul Gloster 2010-11-17 2:50 ` Alex Mentis 1 sibling, 0 replies; 32+ messages in thread From: Colin Paul Gloster @ 2010-11-16 21:24 UTC (permalink / raw) Randy Brukardt <randy@rrsoftware.com> sent on November 16th, 2010: |------------------------------------------------------------------------| |""Alex Mentis" <foo@invalid.invalid> wrote in message | |news:ibueau$aac$1@news.eternal-september.org... | |... | |> In the case of the OP, he wanted a specific data structure (rb tree). | | | |[..] | | | |[..] In the | |rare case where the performance isn't sufficient, then a custom data | |structure will be needed -- but it is almost certain that you'll need to| |program that structure yourself (because you'll want to squeeze out any | |overhead from features that you don't need). | | | |[..]" | |------------------------------------------------------------------------| Indeed. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-16 19:51 ` Randy Brukardt 2010-11-16 21:24 ` Colin Paul Gloster @ 2010-11-17 2:50 ` Alex Mentis 2010-11-17 5:10 ` Adam Beneschan 1 sibling, 1 reply; 32+ messages in thread From: Alex Mentis @ 2010-11-17 2:50 UTC (permalink / raw) Randy Brukardt wrote: > Unless you are a student, worrying about a specific data structure is > silly in 99% of the cases. Some students do use Ada. > I don't know what data > structures this newsreader and browser use, but they're good enough > for the application, so why should I care?? Same goes for the > standard containers. Ah, ignorance is bliss! "It just works." We should call it iAda and sell it to Steve Jobs. :-) Implementation matters to some people, and it's not my job to decide when it should and shouldn't matter to them. Of course, maybe that *is* your job...I don't want to be presumptuous. :-) Sometimes, when you're not building an airplane, you just want to use a data structure you know works and not have to do a lot of performance benchmarking. In this case, the ARM only guarantees O((log n)**2) performance for particular operations, but a red-black tree should perform significantly better, so awareness of the implementation might be nice. I don't really disagree with your philosphy of "trust the container" all that much, though, and I'm not trying to start an argument. So, hopefully the smiley emoticons did their job in conveying that. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-17 2:50 ` Alex Mentis @ 2010-11-17 5:10 ` Adam Beneschan 2010-11-17 22:59 ` Yannick Duchêne (Hibou57) 0 siblings, 1 reply; 32+ messages in thread From: Adam Beneschan @ 2010-11-17 5:10 UTC (permalink / raw) On Nov 16, 6:50 pm, "Alex Mentis" <f...@invalid.invalid> wrote: > Randy Brukardt wrote: > > Unless you are a student, worrying about a specific data structure is > > silly in 99% of the cases. > > Some students do use Ada. > > > I don't know what data > > structures this newsreader and browser use, but they're good enough > > for the application, so why should I care?? Same goes for the > > standard containers. > > Ah, ignorance is bliss! "It just works." We should call it iAda and > sell it to Steve Jobs. :-) > > Implementation matters to some people, and it's not my job to decide > when it should and shouldn't matter to them. Of course, maybe that > *is* your job...I don't want to be presumptuous. :-) > > Sometimes, when you're not building an airplane, you just want to use a > data structure you know works and not have to do a lot of performance > benchmarking. In this case, the ARM only guarantees O((log n)**2) > performance for particular operations, but a red-black tree should > perform significantly better, so awareness of the implementation might > be nice. > > I don't really disagree with your philosphy of "trust the container" > all that much, though, and I'm not trying to start an argument. So, > hopefully the smiley emoticons did their job in conveying that. I think that in a case like this, the truth is somewhere in between. Like Randy said, in most cases you should not need to care about the exact implementation. However, often one does care that an implementation works well for certain patterns of operations. For example, you might have a container-type package that supports "insert" and "search" operations; but a user that wants to insert all the data first, calling the Insert operation on data that's already sorted, and then do searches, would probably prefer a different implementation than a user that is going to be using the Insert operation interspersed with searches throughout the program. In my view, the OP shouldn't have said "I need a self-balancing binary search tree" or "I need a red-black tree", but simply saying "I need something that represents an ordered set of data" isn't always good enough, either. Sometimes it is. But ideally it should be something like "I need something that represents an ordered map, that is optimized for arbitrary sequences of insertions, deletions, and lookups" or whatever the needs are. (And to *really* dream, an implementation could provide an operation in a child package to allow the caller to select from a set of optimization options and then provide alternate implementations. No, I'm not volunteering to do the work :) ) -- Adam ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-17 5:10 ` Adam Beneschan @ 2010-11-17 22:59 ` Yannick Duchêne (Hibou57) 2010-11-17 23:15 ` Vinzent Hoefler 0 siblings, 1 reply; 32+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-11-17 22:59 UTC (permalink / raw) Le Wed, 17 Nov 2010 06:10:22 +0100, Adam Beneschan <adam@irvine.com> a écrit: > (And to *really* dream, an > implementation could provide an operation in a child package to allow > the caller to select from a set of optimization options and then > provide alternate implementations. No, I'm not volunteering to do the > work :) ) > > -- Adam How do you get, with Ada, something similar to what you have with SML, I mean multiple structures all implementing a same signature ? Unfortunately, with Ada, there is no way to do it without tagged/interface types (if a package interface specifies operations, then it must a package body which implements, … in one way only). Would be nice to be able with Ada to have this SML feature: “for that package specification, use that or this implementation.” I don't see a way to do that using child packages, as the implementation of an operation specified in a package interface cannot be deferred to a (or multiple) child package. Child package can only extent. -- Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour les chiens. “I am fluent in ASCII” [Warren 2010] ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-17 22:59 ` Yannick Duchêne (Hibou57) @ 2010-11-17 23:15 ` Vinzent Hoefler 2010-11-17 23:39 ` Yannick Duchêne (Hibou57) 0 siblings, 1 reply; 32+ messages in thread From: Vinzent Hoefler @ 2010-11-17 23:15 UTC (permalink / raw) Yannick Duchêne (Hibou57) wrote: > How do you get, with Ada, something similar to what you have with SML, I > mean multiple structures all implementing a same signature ? > Unfortunately, with Ada, there is no way to do it without tagged/interface > types (if a package interface specifies operations, then it must a package > body which implements, … in one way only). There are still separates. Of course, it's a compile time decision and it would be part of the build system, not the language itself. > Would be nice to be able with > Ada to have this SML feature: “for that package specification, use that or > this implementation.” > I don't see a way to do that using child packages, as the implementation > of an operation specified in a package interface cannot be deferred to a > (or multiple) child package. Child package can only extent. So where's the problem? Provide an abstract type with the proper operation set and let the user call a factory function which selects between different implementations provided by the different children. This probably introduces code bloat, because all possible implementation would need to be included in the final executable, but well, you can't have everything, can you? Vinzent. -- Mail address temporary, use domain to filter. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-17 23:15 ` Vinzent Hoefler @ 2010-11-17 23:39 ` Yannick Duchêne (Hibou57) 2010-11-18 0:13 ` Vinzent Hoefler 2010-11-18 6:27 ` J-P. Rosen 0 siblings, 2 replies; 32+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-11-17 23:39 UTC (permalink / raw) Le Thu, 18 Nov 2010 00:15:11 +0100, Vinzent Hoefler <0439279208b62c95f1880bf0f8776eeb@t-domaingrabbing.de> a écrit: >> How do you get, with Ada, something similar to what you have with SML, I >> mean multiple structures all implementing a same signature ? >> Unfortunately, with Ada, there is no way to do it without >> tagged/interface >> types (if a package interface specifies operations, then it must a >> package >> body which implements, … in one way only). > > There are still separates. Of course, it's a compile time decision and it > would be part of the build system, not the language itself. You can have only one at a time. If you select an implementation, you select it system-wide, and you cannot select one for that usage and another for another usage in the same system. > So where's the problem? Provide an abstract type with the proper > operation > set and let the user call a factory function which selects between > different > implementations provided by the different children. This probably > introduces > code bloat, because all possible implementation would need to be > included in > the final executable, but well, you can't have everything, can you? The problem is that this is a lack of orthogonality, which is surprisingly an Ada famous feature (Ada forget this one). This is the same issue as the one you get with language with which classes is the only way to achieve encapsulation. With these, you end to use classes when you do not need it at the first place and indeed needed package instead. Here, I would like to be able to do something which has nothing at all to deal with polymorphism, and I cannot do it without polymorphism because Ada do not provide orthogonality here. This is not better than some usage of classes in C++ to workaround the lack of packages in C++. Would be nice to not be forced to use polymorphism for something which has nothing of polymorphism. Would like package specification, to be the specification of any one implementation, instead of the specification of only one implementation. In less words, would like Ada package specification to be more abstract; just like you can have multiple entities, all instance of a type, would be nice to be able to have multiple implementations, all instance of a specification. -- Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour les chiens. “I am fluent in ASCII” [Warren 2010] ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-17 23:39 ` Yannick Duchêne (Hibou57) @ 2010-11-18 0:13 ` Vinzent Hoefler 2010-11-18 6:27 ` J-P. Rosen 1 sibling, 0 replies; 32+ messages in thread From: Vinzent Hoefler @ 2010-11-18 0:13 UTC (permalink / raw) Yannick Duchêne (Hibou57) wrote: > Le Thu, 18 Nov 2010 00:15:11 +0100, Vinzent Hoefler > <0439279208b62c95f1880bf0f8776eeb@t-domaingrabbing.de> a écrit: >> >> There are still separates. Of course, it's a compile time decision and it >> would be part of the build system, not the language itself. > You can have only one at a time. If you select an implementation, you > select it system-wide, and you cannot select one for that usage and > another for another usage in the same system. Sure. I wouldn't propose it as a perfect solution. But we use that feature quite often to provide different implementations depending on the target. So it doesn't seem totally useless in the given context. > The problem is that this is a lack of orthogonality, which is surprisingly > an Ada famous feature (Ada forget this one). This is the same issue as the > one you get with language with which classes is the only way to achieve > encapsulation. With these, you end to use classes when you do not need it > at the first place and indeed needed package instead. Here, I would like > to be able to do something which has nothing at all to deal with > polymorphism, and I cannot do it without polymorphism because Ada do not > provide orthogonality here. Well, isn't providing different implementations with a common interface equivalent to "polymorphism"? I mean, if you don't look at the implementation how can you tell the difference? ;) For instance, instead of using an abstract tagged type and dispatching you could also use "delegation" (I hope that's the right term) to different implementations under a common interface without reverting to tagged types. I still would consider that polymorphism (actually, we do that with the communication subsystem, the implementation decides at run-time which sort of communication is the most efficient, depending on the physical location of sender and receiver). > implementation. In less words, would like Ada package specification to be > more abstract; just like you can have multiple entities, all instance of a > type, would be nice to be able to have multiple implementations, all > instance of a specification. You mean like - let me quickly think of a syntax ... - non-Ada, of course - -- 8< spec -- package Foo -- Some notion to hint the compiler there may be different bodies. select Implementation_Choice is (Binary_Tree, Linked_List); is type Bar is ...; procedure Implementation_Specific (X : Bar) with Implementation_Choice; procedure Common (X : Bar); end Foo; -- 8< -- -- 8< body -- package body Foo is procedure Foobar (X : Bar) case Implementation_Choice when Binary_Tree => is ... begin ... binary tree. end Foobar (Binary_Tree); when Linked_List => is ... begin ... linked list. end Foobar (Linked_List); end case; end Foobar; end Foo; -- 8< -- -- 8< usage -- with Foo; for Foo.Implementation_Choice use Foo.Binary_Tree; -- 8< -- Vinzent. -- Mail address temporary, use domain to filter. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-17 23:39 ` Yannick Duchêne (Hibou57) 2010-11-18 0:13 ` Vinzent Hoefler @ 2010-11-18 6:27 ` J-P. Rosen 2010-11-18 7:08 ` Yannick Duchêne (Hibou57) 2010-11-18 9:02 ` Dmitry A. Kazakov 1 sibling, 2 replies; 32+ messages in thread From: J-P. Rosen @ 2010-11-18 6:27 UTC (permalink / raw) Le 18/11/2010 00:39, Yannick Duchêne (Hibou57) a écrit : > You can have only one at a time. If you select an implementation, you > select it system-wide, and you cannot select one for that usage and > another for another usage in the same system. > If that's really what you want, there is an easy solution. Provide two packages with identical (or compatible enough for your purpose) specifications: package Binary_Tree is.... package Linked_List is.... Then declare at library level: with Binary_Tree; package My_Structure renames Binary_Tree; And then, use My_Structure all over the place. By changing two words in one two-line file, you can switch your entire project to the other implementation. -- --------------------------------------------------------- J-P. Rosen (rosen@adalog.fr) Adalog a déménagé / Adalog has moved: 2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00 ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-18 6:27 ` J-P. Rosen @ 2010-11-18 7:08 ` Yannick Duchêne (Hibou57) 2010-11-18 10:47 ` stefan-lucks 2010-11-18 9:02 ` Dmitry A. Kazakov 1 sibling, 1 reply; 32+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-11-18 7:08 UTC (permalink / raw) Le Thu, 18 Nov 2010 07:27:20 +0100, J-P. Rosen <rosen@adalog.fr> a écrit: > Le 18/11/2010 00:39, Yannick Duchêne (Hibou57) a écrit : >> You can have only one at a time. If you select an implementation, you >> select it system-wide, and you cannot select one for that usage and >> another for another usage in the same system. >> > If that's really what you want, there is an easy solution. > Provide two packages with identical (or compatible enough for your > purpose) specifications: > > package Binary_Tree is.... > package Linked_List is.... > > Then declare at library level: > with Binary_Tree; > package My_Structure renames Binary_Tree; > > And then, use My_Structure all over the place. By changing two words in > one two-line file, you can switch your entire project to the other > implementation. I know that one, but this is a workaround, not a language support (the so called “static polymorphism”). Formally speaking, you do not have multiple implementations of a single specification. The closest thing actually is generic package. But that is not easy to do with generics: you will have to give the generic instance all of its custom implementation via generic parameters (methods and others). -- Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour les chiens. “I am fluent in ASCII” [Warren 2010] ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-18 7:08 ` Yannick Duchêne (Hibou57) @ 2010-11-18 10:47 ` stefan-lucks 2010-11-18 10:45 ` Yannick Duchêne (Hibou57) 0 siblings, 1 reply; 32+ messages in thread From: stefan-lucks @ 2010-11-18 10:47 UTC (permalink / raw) [-- Attachment #1: Type: TEXT/PLAIN, Size: 1846 bytes --] On Thu, 18 Nov 2010, Yannick Duch�ne (Hibou57) wrote: > Formally speaking, you do not have multiple > implementations of a single specification. The closest thing actually is > generic package. But that is not easy to do with generics: you will have to > give the generic instance all of its custom implementation via generic > parameters (methods and others). Why is that a big deal? The instance of a polymorphic data structure must somehow be told which operations to use, anyway. Here is, how it should look like (not checked by a compiler). ----------- The specification: generic procedure Insert(Container: in out Store; Key: Key_Type; Item: Payload; Did_Overwrite: out Boolean) procedure Lookup(Container: Store; Key: Key_Type; Item: out Payload; Found: out Boolean); procedure Delete(Container: in out Store; Key: Key_Type; Found: out Boolean); package Do_Something is ... end Do_Something; ----------- Two possible instantiations: package Do_Something_Simple is new Do_Something(Linked_List.Insert, Linked_List.Lookup, Linked_List.Delete); -- use a linked list as the internal data struture -- constant time insert, linear time lookup and delete package Do_Something_Fast is new Do_Something(AVL.Insert, AVL.Lookup, AVL.Delete); -- use an AVL tree, as the internal data structure -- logarithmic time for all of insert, lookup and delete To me, it seems that generics are quite good for eactly that purpose ... Stefan -- ------ Stefan Lucks -- Bauhaus-University Weimar -- Germany ------ Stefan dot Lucks at uni minus weimar dot de ------ I love the taste of Cryptanalysis in the morning! ------ ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-18 10:47 ` stefan-lucks @ 2010-11-18 10:45 ` Yannick Duchêne (Hibou57) 0 siblings, 0 replies; 32+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-11-18 10:45 UTC (permalink / raw) Le Thu, 18 Nov 2010 11:47:03 +0100, <stefan-lucks@see-the.signature> a écrit: > On Thu, 18 Nov 2010, Yannick Duchêne (Hibou57) wrote: > >> Formally speaking, you do not have multiple >> implementations of a single specification. The closest thing actually is >> generic package. But that is not easy to do with generics: you will >> have to >> give the generic instance all of its custom implementation via generic >> parameters (methods and others). > > Why is that a big deal? The instance of a polymorphic data structure must > somehow be told which operations to use, anyway. Yes, except that it should be in the implementation. One of the matter with the use of generic in that purpose, is that you must re-create another package specification for the implementation package. You have the abstract interface, you have an implementation package, which come with an interface and a body, and you must bind this with another package, which is to be an instantiation of the first one with parameters provided by the second one. With SML (as I did a comparison with that language), you have an interface, ex. signature MY_INTERFACE = sig ... (* some specifications *) end then an implementation among multiple others (if you wish, and typically, there will be multiple): structure My_Interface_Implementation_1 :> MY_INTERFACE = struct ... (* implementation *) end ( the “:>” is for opaque instance, you may use “:” for non-opaque) No more, because it does not need more. The abstract interface behave like a type definition, and you declare an implementation instance, just like an entity instance. You can have multiple instance simultaneously, so that if you want This implementation of a container for This purpose, and That implementation of the same container for That usage, you can. Yes, this is feasible with generics (the closest thing available with Ada), or with static polymorphism (as do the ARM and as Jean-Pierre suggested). At least, the generic way do some checks and ensure consistency; the static polymorphism way does not at all (so I would recommend generics). What I feel is not clean with the generic way, is the need to create an un-useful second interface (un-useful duplication) for each implementation, a framework body for the generic (non-sense here), and the need for an explicit instantiation (this instantiation is a second un-useful copy of stuffs). All of this forms noise and weight the design, disturb the comprehension and does not express what it should express (too many steps for such a simple things does not help to understand what is important). I am sure Ada could support this, as it already have all of what is needed for that (separation of implementation and interface, just not separated enough). We may declare an interface like for any generic package; this generic would *not have any body*. We may declare the existence of an implementation instance in a terse way with something as short as a renaming package or package instantiation; this one would come *with a body* (which would be checked against the specification of the abstract interface) and the client side would reference this package which would implicitly import the interface of the first one (the abstract one). This would only use things which are already there with Ada, just the way to bind these together would need to be updated. This could be done in a way which could preserve compatibility, as this would touch nothing else. -- Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour les chiens. “I am fluent in ASCII” [Warren 2010] ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-18 6:27 ` J-P. Rosen 2010-11-18 7:08 ` Yannick Duchêne (Hibou57) @ 2010-11-18 9:02 ` Dmitry A. Kazakov 2010-11-18 12:36 ` J-P. Rosen 1 sibling, 1 reply; 32+ messages in thread From: Dmitry A. Kazakov @ 2010-11-18 9:02 UTC (permalink / raw) On Thu, 18 Nov 2010 07:27:20 +0100, J-P. Rosen wrote: > Le 18/11/2010 00:39, Yannick Duch�ne (Hibou57) a �crit : >> You can have only one at a time. If you select an implementation, you >> select it system-wide, and you cannot select one for that usage and >> another for another usage in the same system. >> > If that's really what you want, there is an easy solution. > Provide two packages with identical (or compatible enough for your > purpose) specifications: > > package Binary_Tree is.... > package Linked_List is.... > > Then declare at library level: > with Binary_Tree; > package My_Structure renames Binary_Tree; Yes of course it is a simple, but non-Ada solution. BTW, I am using it for years, with a small addition that the implementation is selected by the gpr-file. But it is not Ada it is pure C, because nothing is checked. An Ada way would be abstract packages, i.e. a package that describes the public part of some other package. The program could be developed in terms of the abstract package(s) required to be substituted by an implementation package. Upon substitution the actual package specification would be checked. This is close to a formal generic packages but "typed." In effect you have a package type and packages are values of. Something of this sort could be done in existing Ada, but in a quite ugly way: generic type T is private; -- The formal parameters play role with procedure F; -- of a "specification" of Abstract_P type package Abstract_P is -- Nothing here end Abstract_P; generic with package Concrete_P is new Abstract_P; package My_Stuff is ... -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-18 9:02 ` Dmitry A. Kazakov @ 2010-11-18 12:36 ` J-P. Rosen 2010-11-18 13:23 ` Dmitry A. Kazakov 0 siblings, 1 reply; 32+ messages in thread From: J-P. Rosen @ 2010-11-18 12:36 UTC (permalink / raw) Le 18/11/2010 10:02, Dmitry A. Kazakov a �crit : >> Provide two packages with identical (or compatible enough for your >> purpose) specifications: >> >> package Binary_Tree is.... >> package Linked_List is.... >> >> Then declare at library level: >> with Binary_Tree; >> package My_Structure renames Binary_Tree; > > Yes of course it is a simple, but non-Ada solution. BTW, I am using it for > years, with a small addition that the implementation is selected by the > gpr-file. > > But it is not Ada it is pure C, because nothing is checked. Come on, any incorrect usage will not compile! You may argue that it would be nice to check that both structures are compatible, but I challenge you to define the compatibility rules for packages. In practice, two packages are compatible if the *user* uses only compatible subprograms from both... -- --------------------------------------------------------- J-P. Rosen (rosen@adalog.fr) Adalog a d�m�nag� / Adalog has moved: 2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00 ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-18 12:36 ` J-P. Rosen @ 2010-11-18 13:23 ` Dmitry A. Kazakov 0 siblings, 0 replies; 32+ messages in thread From: Dmitry A. Kazakov @ 2010-11-18 13:23 UTC (permalink / raw) On Thu, 18 Nov 2010 13:36:57 +0100, J-P. Rosen wrote: > Le 18/11/2010 10:02, Dmitry A. Kazakov a �crit : >>> Provide two packages with identical (or compatible enough for your >>> purpose) specifications: >>> >>> package Binary_Tree is.... >>> package Linked_List is.... >>> >>> Then declare at library level: >>> with Binary_Tree; >>> package My_Structure renames Binary_Tree; >> >> Yes of course it is a simple, but non-Ada solution. BTW, I am using it for >> years, with a small addition that the implementation is selected by the >> gpr-file. >> >> But it is not Ada it is pure C, because nothing is checked. > Come on, any incorrect usage will not compile! So is any incorrect usage of a C++ template. It is exactly the same use case. The point is that the implementation shall be checked when compiled, separately from the instantiation/use point(s). > You may argue that it would be nice to check that both structures are > compatible, but I challenge you to define the compatibility rules for > packages. In practice, two packages are compatible if the *user* uses > only compatible subprograms from both... Rules similar to ones for matching formal generic parameters should suffice. I don't think this is a problem. What is a potential problem is children packages, i.e. children of abstract packages vs. children of their implementations and how they mess up with each other. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-15 22:46 ` Randy Brukardt 2010-11-16 16:10 ` Gene @ 2010-11-17 22:38 ` Yannick Duchêne (Hibou57) 1 sibling, 0 replies; 32+ messages in thread From: Yannick Duchêne (Hibou57) @ 2010-11-17 22:38 UTC (permalink / raw) Le Mon, 15 Nov 2010 23:46:16 +0100, Randy Brukardt <randy@rrsoftware.com> a écrit: > It's not explicit. One of the possible implementations of the ordered > sets > and maps is to use a Red-Black tree; presumably this is what GNAT's > implementation is doing. And there are even other ways to get a balanced tree, which are not red-black-trees (I use something else for long, which do a kind of layout analysis, this work nice). -- Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour les chiens. “I am fluent in ASCII” [Warren 2010] ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 11:20 Using Red-Black Trees Björn 2010-11-13 12:14 ` Phil Thornley 2010-11-13 13:10 ` Alex Mentis @ 2010-11-13 21:53 ` Jeffrey Carter 2010-11-14 8:20 ` Björn 2010-11-13 23:51 ` robin 3 siblings, 1 reply; 32+ messages in thread From: Jeffrey Carter @ 2010-11-13 21:53 UTC (permalink / raw) On 11/13/2010 04:20 AM, Bj�rn wrote: > I need a self-balancing binary search tree (for a Bentley/Ottmann > implementation), such as the red-black tree that is now part of > Ada.Containers. I need basic operations like insert/remove, next/prev > and find. However, the GNAT implementation of this data structure > seems a bit scary to me and I'm not really sure how to instantiate the > generics and what operations to use. Would someone be able to provide > some example of usage? And yes, I'am aware of that a lot of the other > container implementations uses this structure. I was hoping for > something a bit more boiled down. Are you sure you need a tree? Skip lists serve the same function, are just as fast as balanced trees for searching, and faster than the typical tree implementations for insert and delete. There's a skip-list implementation in the PragmAda Reusable Components: http://pragmada.x10hosting.com/pragmarc.htm -- Jeff Carter "Unix and C are the ultimate computer viruses." Richard Gabriel 99 ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 21:53 ` Jeffrey Carter @ 2010-11-14 8:20 ` Björn 2010-11-14 8:37 ` Dmitry A. Kazakov 0 siblings, 1 reply; 32+ messages in thread From: Björn @ 2010-11-14 8:20 UTC (permalink / raw) > Are you sure you need a tree? Skip lists serve the same function, are just as > fast as balanced trees for searching, and faster than the typical tree > implementations for insert and delete. I am not as familiar with skip lists as with trees. Although I would expect both of them to work as they seem to have similar properties and performance. When the rest of my implementation is finished I hope to make a little comparison of which one that performs best for my application. I will definitly have a look at PragmARC. Thanks! /Björn ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-14 8:20 ` Björn @ 2010-11-14 8:37 ` Dmitry A. Kazakov 0 siblings, 0 replies; 32+ messages in thread From: Dmitry A. Kazakov @ 2010-11-14 8:37 UTC (permalink / raw) On Sun, 14 Nov 2010 00:20:06 -0800 (PST), Bj�rn wrote: >> Are you sure you need a tree? Skip lists serve the same function, are just as >> fast as balanced trees for searching, and faster than the typical tree >> implementations for insert and delete. > > I am not as familiar with skip lists as with trees. Although I would > expect both of them to work as they seem to have similar properties > and performance. Hmm, if you are not familiar with them, how do you know if you need some? Why not a map, a kd-tree, a suffix-tree and so on? > When the rest of my implementation is finished I hope > to make a little comparison of which one that performs best for my > application. I would not care. I mean that in most cases performance does not play very sufficient role (OK, assuming that we don't make stupid mistakes like O(n**2) sorting of a 10**9 list). Cleaner design is usually more important. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Using Red-Black Trees 2010-11-13 11:20 Using Red-Black Trees Björn ` (2 preceding siblings ...) 2010-11-13 21:53 ` Jeffrey Carter @ 2010-11-13 23:51 ` robin 3 siblings, 0 replies; 32+ messages in thread From: robin @ 2010-11-13 23:51 UTC (permalink / raw) [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #1: Type: text/plain, Size: 818 bytes --] Bj�rn wrote in message <2419e829-6f45-4075-9005-b9876beb8aaa@r6g2000vbf.googlegroups.com>... >I need a self-balancing binary search tree (for a Bentley/Ottmann >implementation), such as the red-black tree that is now part of >Ada.Containers. I need basic operations like insert/remove, next/prev >and find. However, the GNAT implementation of this data structure >seems a bit scary to me and I'm not really sure how to instantiate the >generics and what operations to use. Would someone be able to provide >some example of usage? And yes, I'am aware of that a lot of the other >container implementations uses this structure. I was hoping for >something a bit more boiled down. For algorithms for Red-Black trees (inclding insert/delete/etc), see "Introduction to PL/I, Algorithms, and Structured Programming". ^ permalink raw reply [flat|nested] 32+ messages in thread
end of thread, other threads:[~2010-11-18 13:23 UTC | newest] Thread overview: 32+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2010-11-13 11:20 Using Red-Black Trees Björn 2010-11-13 12:14 ` Phil Thornley 2010-11-13 13:10 ` Alex Mentis 2010-11-13 13:23 ` Björn 2010-11-13 13:53 ` Alex Mentis 2010-11-13 14:06 ` Björn 2010-11-13 16:31 ` Simon Wright 2010-11-15 8:49 ` Stephane Carrez 2010-11-15 15:32 ` John B. Matthews 2010-11-15 22:46 ` Randy Brukardt 2010-11-16 16:10 ` Gene 2010-11-16 17:17 ` Alex Mentis 2010-11-16 19:51 ` Randy Brukardt 2010-11-16 21:24 ` Colin Paul Gloster 2010-11-17 2:50 ` Alex Mentis 2010-11-17 5:10 ` Adam Beneschan 2010-11-17 22:59 ` Yannick Duchêne (Hibou57) 2010-11-17 23:15 ` Vinzent Hoefler 2010-11-17 23:39 ` Yannick Duchêne (Hibou57) 2010-11-18 0:13 ` Vinzent Hoefler 2010-11-18 6:27 ` J-P. Rosen 2010-11-18 7:08 ` Yannick Duchêne (Hibou57) 2010-11-18 10:47 ` stefan-lucks 2010-11-18 10:45 ` Yannick Duchêne (Hibou57) 2010-11-18 9:02 ` Dmitry A. Kazakov 2010-11-18 12:36 ` J-P. Rosen 2010-11-18 13:23 ` Dmitry A. Kazakov 2010-11-17 22:38 ` Yannick Duchêne (Hibou57) 2010-11-13 21:53 ` Jeffrey Carter 2010-11-14 8:20 ` Björn 2010-11-14 8:37 ` Dmitry A. Kazakov 2010-11-13 23:51 ` robin
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox