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