1--  Copyright 1994 Grady Booch
2--  Copyright 1994-1997 David Weller
3--  Copyright 1998-2014 Simon Wright <simon@pushface.org>
4
5--  This package is free software; you can redistribute it and/or
6--  modify it under terms of the GNU General Public License as
7--  published by the Free Software Foundation; either version 2, or
8--  (at your option) any later version. This package is distributed in
9--  the hope that it will be useful, but WITHOUT ANY WARRANTY; without
10--  even the implied warranty of MERCHANTABILITY or FITNESS FOR A
11--  PARTICULAR PURPOSE. See the GNU General Public License for more
12--  details. You should have received a copy of the GNU General Public
13--  License distributed with this package; see file COPYING.  If not,
14--  write to the Free Software Foundation, 59 Temple Place - Suite
15--  330, Boston, MA 02111-1307, USA.
16
17--  As a special exception, if other files instantiate generics from
18--  this unit, or you link this unit with other files to produce an
19--  executable, this unit does not by itself cause the resulting
20--  executable to be covered by the GNU General Public License.  This
21--  exception does not however invalidate any other reasons why the
22--  executable file might be covered by the GNU Public License.
23
24generic package BC.Containers.Trees is
25
26   pragma Preelaborate;
27
28   --  A binary tree is a rooted collection of nodes and arcs, where
29   --  each node has two children and where arcs may not have cycles
30   --  or cross-references (as in graphs). A multiway tree is a rooted
31   --  collection of nodes and arcs, where each node may have an
32   --  arbitrary number of children and where arcs may not have cycles
33   --  or cross-references. AVL trees are a form of balance tree
34   --  (following the algorithm of Adelson-Velskii and Landis) whose
35   --  behavior only exposes operations to insert, delete, and search
36   --  for items.
37
38   --  Binary and multiway trees are polylithic structures, and hence
39   --  the semantics of copying, assignment, and equality involve
40   --  structural sharing. Care must be taken in manipulating the same
41   --  tree named by more than one alias. AVL trees are monolithic.
42
43   --  These classes are not intended to be subclassed, and so provide
44   --  no virtual members.
45
46   --  These abstractions have been carefully constructed to eliminate
47   --  all storage leaks, except in the case of intentional
48   --  abuses. When a tree is manipulated, all items that become
49   --  unreachable are automatically reclaimed. Furthermore, this
50   --  design protects against dangling references: an item is never
51   --  reclaimed if there exists a reference to it.
52
53   --  Unreachable items are those that belong to a tree or a subtree
54   --  whose root is not designated by any alias. For example,
55   --  consider the tree (A (B C (D E))), with the root of the tree
56   --  designated by T1. T1 initially points to the root of the tree,
57   --  at item A. Invoking the operation Right_Child on T1 now causes
58   --  T1 to point to item C. Because A is now considered unreachable,
59   --  the storage associated with item A is reclaimed; the parent of
60   --  C is now null. Additionally, the sibling subtree rooted at B is
61   --  also now unreachable, and so is reclaimed (along with its
62   --  children, and recursively so). Similarly, consider the same
63   --  tree, with the root of the tree designated by both T1 and
64   --  T2. Both T1 and T2 are aliases that initially point to the root
65   --  of the tree at item A. Invoking the operation Right_Child on T1
66   --  now causes T1 to point to item C; T2 is unaffected. No storage
67   --  is reclaimed, since every element of the tree is still
68   --  reachable. Suppose we now invoke the member function Clear on
69   --  T2. The semantics of this operation are such that only
70   --  unreachable items are reclaimed. Thus, the storage associated
71   --  with item A is reclaimed, because it is no longer reachable;
72   --  additionally, the sibling B (and recursively so, its children)
73   --  is reclaimed, because it is also now unreachable; the subtree
74   --  denoted by T1 is unaffected. T2 is now null, and the parent of
75   --  C is now null.
76
77   --  It is possible, but not generally desirable, to produce
78   --  multi-headed trees. In such cases, the parent of the item at
79   --  the neck of a multi-headed tree points to the most recently
80   --  attached root.
81
82   --  The binary and multiway trees have a similar protocol, except
83   --  that the binary tree adds two operations, Left_Child and
84   --  Right_Child, and the multiway tree overloads the Append
85   --  operation and adds the operation Arity. The AVL tree has a
86   --  completely different protocol, with a much more limited set of
87   --  operations.
88
89end BC.Containers.Trees;
90