Re: Using Red-Black Trees

["Alex Mentis" <foo@invalid.invalid>]

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.