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.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,effb80d4bb7716dd
X-Google-Attributes: gid103376,public
From: mfb@mbunix.mitre.org (Michael F Brenner)
Subject: Re: Wanted: Ada STL.  Reward: Ada's Future
Date: 1999/02/08
Message-ID: <79nalr$9lj@top.mitre.org>#1/1
X-Deja-AN: 442044612
References: <790f4q$3l@bgtnsc01.worldnet.att.net>
 <36B5C5A0.4426B904@spam.innocon.com>
Organization: The MITRE Corporation, Bedford Mass.
Newsgroups: comp.lang.ada
Date: 1999-02-08T00:00:00+00:00
List-Id: <comp.lang.ada>

> 1.  Linked lists
> 2.  Trees
> 3.  Queues
> 4.  Sets
> ...            

I agree with Jeff in that I use skip lists instead of most tree
structures used for lookups. Code for skip lists has been posted 
here several times. An extensible (unlimited size) vector (also
called long_array) package that divides an array up into 
contiguous banks of memory (effectively a linked list of
blocks of objects) can be the basis of many kinds of sets, 
the data storage for trees and graphs, and be the entire basis
of linked lists, stacks, and queues of any fixed length objects.

That is the easy part. 

The medium part is variable length objects. To do this, you need
to simulate string sliceing, only not on characters, but on 
complex objects. That can be done by adding a layer of
heap management that does the slicing and reallocates storage
within your pool (or, if your run-time has memory leaks or an
insufficiently powerful garbage collector, then within you
heap of heaps). This could use a free list, for example, to
reclaim storage within the heap of heaps.

The hard part might be complex, highly nested structures of
variable length objects nested within variable length objects
to many levels of nesting. I am about to implement a 
heap-of-heaps reclamation on exactly such a datastructure
(the SJ Neural Net, I guess we should call it). I will let you
know how it goes.

Where do you get this code? Most of it is on-line for downloading,
but if you have specific needs, post them here and ask specific 
questions.