File : bc-support-hash_tables.ads
-- Copyright (C) 1994-2000 Grady Booch 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-support-hash_tables.ads,v 1.2.2.2 2000/02/12 14:43:51 simon Exp $
with Ada.Finalization;
package BC.Support.Hash_Tables is
pragma Elaborate_Body;
-- In the generic signature packages, Item denotes the universe
-- from which the hash table draws its items. Value denotes the
-- universe from which the hash table draws its values. Items and
-- Values may be either primitive types or user-defined
-- non-limited types.
-- Item_Container and Value_Container provide the concrete container
-- for each bucket. These types will normally be provided by
-- instantiations of the bounded, dynamic, and unbounded support
-- packages defined for this library.
generic
type Item is private;
with function "=" (L, R : Item) return Boolean is <>;
with function Hash (V : Item) return Positive is <>;
type Item_Container is private;
type Item_Container_Ptr is access all Item_Container;
-- The <> subprograms for Items are provided by one of
-- BC.Support.Bounded, Dynamic or Unbounded as appropriate.
with function Create (From : Item_Container) return Item_Container_Ptr is <>;
with procedure Clear (C : in out Item_Container) is <>;
with procedure Insert (C : in out Item_Container; I : Item) is <>;
with procedure Append (C : in out Item_Container; I : Item) is <>;
with procedure Remove (C : in out Item_Container; From : Positive) is <>;
with procedure Replace
(C : in out Item_Container; Index : Positive; I : Item) is <>;
with function Length (C : Item_Container) return Natural is <>;
with function Item_At
(C : Item_Container; Index : Positive) return Item is <>;
with function Location
(C : Item_Container; I : Item; Start : Positive) return Natural is <>;
with procedure Free (C : in out Item_Container_Ptr) is <>;
package Item_Signature is end Item_Signature;
generic
type Value is private;
type Value_Ptr is access all Value;
with function "=" (L, R : Value) return Boolean is <>;
type Value_Container is private;
type Value_Container_Ptr is access all Value_Container;
-- The <> subprograms for Values are provided by one of
-- BC.Support.Bounded, Dynamic or Unbounded as appropriate.
with function Create
(From : Value_Container) return Value_Container_Ptr is <>;
with procedure Clear (C : in out Value_Container) is <>;
with procedure Insert (C : in out Value_Container; V : Value) is <>;
with procedure Append (C : in out Value_Container; V : Value) is <>;
with procedure Remove (C : in out Value_Container; From : Positive) is <>;
with procedure Replace
(C : in out Value_Container; Index : Positive; V : Value) is <>;
with function Length (C : Value_Container) return Natural is <>;
with function Item_At
(C : Value_Container; Index : Positive) return Value is <>;
with function Item_At
(C : Value_Container; Index : Positive) return Value_Ptr is <>;
with function Location
(C : Value_Container; V : Value; Start : Positive) return Natural is <>;
with procedure Free (C : in out Value_Container_Ptr) is <>;
package Value_Signature is end Value_Signature;
generic
with package Items is new Item_Signature (<>);
with package Values is new Value_Signature (<>);
Buckets : Natural;
package Tables is
-- The type Table represents an open hash table whose buckets may be
-- formed by bounded, dynamic, or unbounded containers. Each table
-- contains n buckets, wherein each bucket is a container of item/value
-- pairs. To insert, remove, or locate a pair in the table, the operation
-- first generates a hash value upon the item to select a specific
-- bucket, and then the given operation is performed upon the selected
-- container.
-- This is a low-level abstraction that specifies no policies for the
-- order in which items may be added and removed from the container. This
-- class is not intended to be subclassed.
-- The parameter Buckets signifies the static number of buckets in the
-- hash table.
type Table is new Ada.Finalization.Controlled with private;
function "=" (L, R : Table) return Boolean;
procedure Clear (T : in out Table);
-- Empty the hash table of all item/value pairs.
procedure Bind (T : in out Table; I : Items.Item; V : Values.Value);
-- Generate a hash value for the item to select a bucket. If the item
-- already exists in that bucket, raise BC.Duplicate; otherwise, insert
-- the Item/value pair in the selected container.
procedure Rebind (T : in out Table; I : Items.Item; V : Values.Value);
-- Generate a hash value for the item to select a bucket. If the item
-- already exists in that bucket, change the item's corresponding value;
-- otherwise, raise BC.Not_Found.
procedure Unbind (T : in out Table; I : Items.Item);
-- Generate a hash value for the item to select a bucket. If the item
-- already exists in that bucket, remove the item/value pair; otherwise,
-- BC.Not_Found.
function Extent (T : Table) return Natural;
-- Return the number of item/value pairs in the hash table.
function Is_Bound (T : Table; I : Items.Item) return Boolean;
-- Return True if the item has a binding in the hash table; otherwise,
-- return False.
function Value_Of (T : Table; I : Items.Item) return Values.Value;
-- If the item does not have a binding in the hash table, raise
-- BC.Not_Found; otherwise, return the value corresponding to this item.
function Value_Of (T : Table; I : Items.Item) return Values.Value_Ptr;
-- If the item does not have a binding in the hash table, raise
-- BC.Not_Found; otherwise, return a pointer to the value corresponding
-- to this item.
function Item_Bucket
(T : Table; Bucket : Positive) return Items.Item_Container_Ptr;
function Value_Bucket
(T : Table; Bucket : Positive) return Values.Value_Container_Ptr;
private
type Item_Array is array (1 .. Buckets) of Items.Item_Container_Ptr;
type Value_Array is array (1 .. Buckets) of Values.Value_Container_Ptr;
type Table is new Ada.Finalization.Controlled with record
Items : Item_Array;
Values : Value_Array;
Size : Natural := 0;
end record;
procedure Initialize (T : in out Table);
procedure Adjust (T : in out Table);
procedure Finalize (T : in out Table);
end Tables;
end BC.Support.Hash_Tables;