-- Copyright 1994 Grady Booch
-- Copyright 1998-2002 Simon Wright <simon@pushface.org>
-- This package is free software; you can redistribute it and/or
-- modify it under terms of the GNU General Public License as
-- published by the Free Software Foundation; either version 2, or
-- (at your option) any later version. This package 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 GNU General Public License for more
-- details. You should have received a copy of the GNU General Public
-- License distributed with this package; see file COPYING. If not,
-- write to the Free Software Foundation, 59 Temple Place - Suite
-- 330, Boston, MA 02111-1307, USA.
-- As a special exception, if other files instantiate generics from
-- this unit, or you link this unit with other files to produce an
-- executable, this unit does not by itself cause the resulting
-- executable to be covered by the GNU General Public License. This
-- exception does not however invalidate any other reasons why the
-- executable file might be covered by the GNU Public License.
-- $RCSfile: bc-support-hash_tables.ads,v $
-- $Revision: 1.9.2.3 $
-- $Date: 2002/12/26 14:48:14 $
-- $Author: simon $
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;
type Item_Ptr is access all Item;
with function "=" (L, R : Item) return Boolean is <>;
with function Hash (V : Item) return Natural is <>;
type Item_Container is private;
-- The <> subprograms for Items are provided by one of
-- BC.Support.Bounded, Dynamic or Unbounded as appropriate.
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 Item_At
(C : Item_Container; Index : Positive) return Item_Ptr is <>;
with function Location
(C : Item_Container; I : Item; Start : Positive) return Natural 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;
-- The <> subprograms for Values are provided by one of
-- BC.Support.Bounded, Dynamic or Unbounded as appropriate.
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 <>;
package Value_Signature is end Value_Signature;
generic
with package Items is new Item_Signature (<>);
with package Values is new Value_Signature (<>);
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.
type Item_Array is array (Positive range <>) of Items.Item_Container;
type Value_Array is array (Positive range <>) of Values.Value_Container;
type Table (Number_Of_Buckets : Positive) is record
Items : Item_Array (1 .. Number_Of_Buckets);
Values : Value_Array (1 .. Number_Of_Buckets);
Size : Natural := 0;
end record;
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.
-- Iterator support
procedure Reset (T : Table;
Bucket : out Positive;
Index : out Positive);
function Is_Done (T : Table;
Bucket : Positive;
Index : Positive) return Boolean;
function Current_Item_Ptr (T : Table;
Bucket : Positive;
Index : Positive) return Items.Item_Ptr;
function Current_Value_Ptr (T : Table;
Bucket : Positive;
Index : Positive) return Values.Value_Ptr;
procedure Delete_Item_At (T : in out Table;
Bucket : in out Positive;
Index : in out Positive);
procedure Next (T : Table;
Bucket : in out Positive;
Index : in out Positive);
end Tables;
end BC.Support.Hash_Tables;
syntax highlighted by Code2HTML, v. 0.9.1