From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,8e7ac81a215f128c
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII
Path: 
 g2news2.google.com!news4.google.com!feeder.news-service.com!85.214.198.2.MISMATCH!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: "Alex Mentis" <foo@invalid.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Using Red-Black Trees
Date: Tue, 16 Nov 2010 17:17:19 +0000 (UTC)
Organization: A noiseless patient Spider
Message-ID: <ibueau$aac$1@news.eternal-september.org>
References: <2419e829-6f45-4075-9005-b9876beb8aaa@r6g2000vbf.googlegroups.com>
 <ibm2op$m1i$1@news.eternal-september.org> <ibsd7q$nru$1@munin.nbi.dk>
 <46306fd9-21dc-40df-88e7-fc7e568399a4@k11g2000vbf.googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 16 Nov 2010 17:17:19 +0000 (UTC)
Injection-Info: mx02.eternal-september.org;
 posting-host="2mHI2HcCGxZ3pXcuTAHRZQ";
	logging-data="10572"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX197sfmRvRq8YAXXsArKNjz+7nxWqkdLKho="
User-Agent: XanaNews/1.19.1.269
Cancel-Lock: sha1:dYlrnfR6d8w0rMR1lQhzApRz1mY=
Xref: g2news2.google.com comp.lang.ada:16492
Date: 2010-11-16T17:17:19+00:00
List-Id: <comp.lang.ada>

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.