Using Red-Black Trees

Using Red-Black Trees

[Björn]

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

Re: Using Red-Black Trees

[Phil Thornley]

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

Re: Using Red-Black Trees

[Alex Mentis]

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?

Re: Using Red-Black Trees

[Björn]

> 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

Re: Using Red-Black Trees

[Alex Mentis]

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.

Re: Using Red-Black Trees

[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

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

Re: Using Red-Black Trees

[Simon Wright]

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

Re: Using Red-Black Trees

[Stephane Carrez]

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

Re: Using Red-Black Trees

[John B. Matthews]

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>

Re: Using Red-Black Trees

[Randy Brukardt]

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

Re: Using Red-Black Trees

[Gene]

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;

Re: Using Red-Black Trees

[Alex Mentis]

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.

Re: Using Red-Black Trees

[Randy Brukardt]

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

Re: Using Red-Black Trees

[Colin Paul Gloster]

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.

Re: Using Red-Black Trees

[Alex Mentis]

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.

Re: Using Red-Black Trees

[Adam Beneschan]

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

Re: Using Red-Black Trees

[Yannick Duchêne (Hibou57)]

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]

Re: Using Red-Black Trees

[Vinzent Hoefler]

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.

Re: Using Red-Black Trees

[Yannick Duchêne (Hibou57)]

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]

Re: Using Red-Black Trees

[Vinzent Hoefler]

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.

Re: Using Red-Black Trees

[J-P. Rosen]

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

Re: Using Red-Black Trees

[Yannick Duchêne (Hibou57)]

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]

Re: Using Red-Black Trees

[stefan-lucks]

[-- 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!  ------

Re: Using Red-Black Trees

[Yannick Duchêne (Hibou57)]

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]

Re: Using Red-Black Trees

[Dmitry A. Kazakov]

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

Re: Using Red-Black Trees

[J-P. Rosen]

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

Re: Using Red-Black Trees

[Dmitry A. Kazakov]

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

Re: Using Red-Black Trees

[Yannick Duchêne (Hibou57)]

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]

Re: Using Red-Black Trees

[Jeffrey Carter]

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

Re: Using Red-Black Trees

[Björn]

> 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

Re: Using Red-Black Trees

[Dmitry A. Kazakov]

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

Re: Using Red-Black Trees

[robin]

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