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
24with Ada.Finalization;
25with System.Storage_Pools;
26
27generic
28   type Item is private;
29   with function "=" (L, R : Item) return Boolean is <>;
30   with function "<" (L, R : Item) return Boolean is <>;
31   Storage : in out System.Storage_Pools.Root_Storage_Pool'Class;
32package BC.Support.AVL_Trees is
33
34   pragma Preelaborate;
35
36   type AVL_Node;
37   type AVL_Node_Ref is access AVL_Node;
38   for AVL_Node_Ref'Storage_Pool use Storage;
39
40   type Node_Balance is (Left, Middle, Right);
41
42   type AVL_Node is record
43      Element : Item;
44      Left, Right : AVL_Node_Ref;
45      Balance : Node_Balance := Middle;
46   end record;
47
48   type AVL_Tree is new Ada.Finalization.Controlled with record
49      Rep : AVL_Node_Ref;
50      Size : Natural := 0;
51   end record;
52
53   function "=" (L, R : AVL_Tree) return Boolean;
54   --  return True if both trees contain the same Elements.
55
56   procedure Clear (T : in out AVL_Tree);
57   --  Make the tree null and reclaim the storage associated with its items.
58
59   procedure Insert (T : in out AVL_Tree;
60                     Element : Item;
61                     Not_Found : out Boolean);
62   --  Add the item to the tree, preserving the tree's
63   --  balance. Not_Found is set to True if the item had not
64   --  previously existed in the tree, and to False otherwise.
65
66   procedure Delete
67     (T : in out AVL_Tree; Element : Item; Found : out Boolean);
68   --  Remove the item from the tree, preserving the tree's
69   --  balance. Found is set to True if the item was in fact found in
70   --  the tree and removed, and to False otherwise.
71
72   function Extent (T : AVL_Tree) return Natural;
73   --  Return the number of items in the tree.
74
75   function Is_Null (T : AVL_Tree) return Boolean;
76   --  Return True if and only if the tree has no items.
77
78   function Is_Member (T : AVL_Tree; Element : Item) return Boolean;
79   --  Return True if and only if the item exists in the tree.
80
81   procedure Adjust (T : in out AVL_Tree);
82
83   procedure Finalize (T : in out AVL_Tree);
84
85end BC.Support.AVL_Trees;
86