File : bc-containers-trees-avl.ads
-- Copyright (C) 1994-1999 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-avl.ads,v 1.3.2.3 1999/12/31 15:14:40 simon Exp $
with Ada.Finalization;
with BC.Support.Nodes;
with System.Storage_Pools;
generic
with function "<" (L, R : Item) return Boolean is <>;
type Storage_Manager (<>)
is new System.Storage_Pools.Root_Storage_Pool with private;
Storage : in out Storage_Manager;
package BC.Containers.Trees.AVL is
pragma Elaborate_Body;
type AVL_Tree is private;
function "=" (L, R : AVL_Tree) return Boolean;
-- return True if both trees contain the same Elements.
procedure Clear (T : in out AVL_Tree);
-- Make the tree null and reclaim the storage associated with its items.
procedure Insert (T : in out AVL_Tree;
Element : Item;
Not_Found : out Boolean);
-- Add the item to the tree, preserving the tree's balance. Not_Found is
-- set to True if the item had not previously existed in the tree, and
-- to False otherwise.
procedure Delete
(T : in out AVL_Tree; Element : Item; Found : out Boolean);
-- Remove the item from the tree, preserving the tree's balance. Found is
-- set to True if the item was in fact found in the tree and removed, and
-- to False otherwise.
function Extent (T : AVL_Tree) return Natural;
-- Return the number of items in the tree.
function Is_Null (T : AVL_Tree) return Boolean;
-- Return True if and only if the tree has no items.
function Is_Member (T : AVL_Tree; Element : Item) return Boolean;
-- Return True if and only if the item exists in the tree.
generic
with procedure Apply (Elem : in out Item);
procedure Access_Actual_Item (In_The_Tree : AVL_Tree;
Elem : Item;
Found : out Boolean);
-- If an Item "=" to Elem is present in the Tree, call Apply for it and
-- set Found to True; otherwise, set Found to False.
-- Apply MUST NOT alter the result of the ordering operation "<".
generic
with procedure Apply (Elem : in Item; OK : out Boolean);
procedure Visit (Over_The_Tree : AVL_Tree);
-- Call Apply with a copy of each Item in the Tree, in order. The
-- iteration will terminate early if Apply sets OK to False.
generic
with procedure Apply (Elem : in out Item; OK : out Boolean);
procedure Modify (Over_The_Tree : AVL_Tree);
-- Call Apply for each Item in the Tree, in order. The iteration will
-- terminate early if Apply sets OK to False.
-- Apply MUST NOT alter the result of the ordering operation "<".
private
package Nodes is new BC.Support.Nodes (Item, Storage_Manager, Storage);
type AVL_Tree is new Ada.Finalization.Controlled with record
Rep : Nodes.AVL_Node_Ref;
Size : Natural := 0;
end record;
procedure Initialize (T : in out AVL_Tree);
procedure Adjust (T : in out AVL_Tree);
procedure Finalize (T : in out AVL_Tree);
end BC.Containers.Trees.AVL;