Re: AVL Tree Implementation

[John Howard <jhoward@sky.net>]

Reusing operations while allowing variant abstract data types is the focus 
of this CS 460 lecture notes book:

"A Systematic Catalogue of Reusable Abstract Data Types" by Jurgen Uhl & 
Hans Albrecht Schmid.  ISBN 0-387-53229-3.  Publ. 1990, pp. 344. 
Springer-Verlag 1-800-777-4643 [New York].  Cost $42.00

It relies upon a variant programming approach to component based software 
construction.  It also relies upon some capable brand of Ada 87 and a C
preprocessor based syntax translation tool.

I bought this book in 1995.  I was happy with the new way of thinking 
presented.  Their catalogue of reusable components is a great idea.  
Unfortunately, the presentation is unusable without further substantial
work from the reader.  Variant programming seems crippling compared to 
classwide programming.  They chose to present their ideas with Ada because 
C++ could not satisfy the dynamic storage requirement.

I was disappointed because: body implementations were not provided; their 
Ada specifications were copyrighted; and their variant programming focus 
necessitated a special syntax preprocessor which mostly precludes code 
sharing for different variants.  Consequently their code specs (115 pages)
cannot be readily used by the readers.  They provide one case study (17 
pages) to demonstrate using their catalogue.

Still their catalogue concept of reusable abstract data types is a 
tremendous influence.  They emphasize the "level of abstraction" for a
problem depends upon the available operations.  An implementor can switch 
ADT's as needed to enhance performance without a major rewrite of source
code.  The completeness of implementation variants is the key to providing
efficiency.

The structure of their reusable ADT catalogue:
List, Stack, Queue and Deque, Tree, Order, Set, Map, and Bag.

The structure of their building blocks:
Linked collections; Tabular collections; Hash tables; Lists, Linked Lists,
Tabular Lists; Stacks; Queues and Deques; Trees, Linked Trees, Tabular
Trees; Orders, Sets; Maps; and Bags.

The building blocks employ structure sharing, compact and dispersed
representations, and recursive composition.  Generic parameters are used
and operations are mostly in-common.

I wish they would release a source code version updated for Ada 95 and
classwide programming with the intention of making their catalogue
popularly used.

-- John Howard <jhoward@sky.net>               -- Team Ada  Team OS/2 --