File : bc-containers-trees.ads
-- Copyright (C) 1994-1998 Grady Booch, David Weller and Simon Wright.
-- All Rights Reserved.
--
-- This program is free software; you can redistribute it
-- and/or modify it under the terms of the Ada Community
-- License which comes with this Library.
--
-- This program is distributed in the hope that it will be
-- useful, but WITHOUT ANY WARRANTY; without even the implied
-- warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
-- PURPOSE. See the Ada Community License for more details.
-- You should have received a copy of the Ada Community
-- License with this library, in the file named "Ada Community
-- License" or "ACL". If not, contact the author of this library
-- for a copy.
--
-- $Id: bc-containers-trees.ads,v 1.6.2.1 1999/10/07 05:57:11 simon Exp $
generic package BC.Containers.Trees is
-- A binary tree is a rooted collection of nodes and arcs, where each
-- node has two children and where arcs may not have cycles or
-- cross-references (as in graphs). A multiway tree is a rooted
-- collection of nodes and arcs, where each node may have an arbitrary
-- number of children and where arcs may not have cycles or
-- cross-references. AVL trees are a form of balance tree (following the
-- algorithm of Adelson-Velskii and Landis) whose behavior only exposes
-- operations to insert, delete, and search for items.
-- Binary and multiway trees are polylithic structures, and hence the
-- semantics of copying, assignment, and equality involve structural
-- sharing. Care must be taken in manipulating the same tree named by
-- more than one alias. AVL trees are monolithic.
-- These classes are not intended to be subclassed, and so provide no
-- virtual members.
-- These abstractions have been carefully constructed to eliminate all
-- storage leaks, except in the case of intentional abuses. When a tree
-- is manipulated, all items that become unreachable are automatically
-- reclaimed. Furthermore, this design protects against dangling
-- references: an item is never reclaimed if there exists a reference to
-- it.
-- Unreachable items are those that belong to a tree or a subtree whose
-- root is not designated by any alias. For example, consider the tree (A
-- (B C (D E))), with the root of the tree designated by T1. T1 initially
-- points to the root of the tree, at item A. Invoking the operation
-- Right_Child on T1 now causes T1 to point to item C. Because A is now
-- considered unreachable, the storage associated with item A is
-- reclaimed; the parent of C is now null. Additionally, the sibling
-- subtree rooted at B is also now unreachable, and so is reclaimed
-- (along with its children, and recursively so). Similarly, consider the
-- same tree, with the root of the tree designated by both T1 and
-- T2. Both T1 and T2 are aliases that initially point to the root of the
-- tree at item A. Invoking the operation Right_Child on T1 now causes T1
-- to point to item C; T2 is unaffected. No storage is reclaimed, since
-- every element of the tree is still reachable. Suppose we now invoke
-- the member function Clear on T2. The semantics of this operation are
-- such that only unreachable items are reclaimed. Thus, the storage
-- associated with item A is reclaimed, because it is no longer
-- reachable; additionally, the sibling B (and recursively so, its
-- children) is reclaimed, because it is also now unreachable; the
-- subtree denoted by T1 is unaffected. T2 is now null, and the parent of
-- C is now null.
-- It is possible, but not generally desirable, to produce multi-headed
-- trees. In such cases, the parent of the item at the neck of a
-- multi-headed tree points to the most recently attached root.
-- The binary and multiway trees have a similar protocol, except that the
-- binary tree adds two operations, Left_Child and Right_Child, and the
-- multiway tree overloads the Append operation and adds the operation
-- Arity. The AVL tree has a completely different protocol, with a much
-- more limited set of operations.
end BC.Containers.Trees;