generic

  type Element is private;     -- assignment and equality predefined
  type KeyType is range <>;    -- must be an integer-valued type!

  Capacity: in Positive;       -- maximum table size

  -- These generic parameters specify how to
  -- retrieve the key from an element, compare elements
  with function KeyOf (Item: Element) return KeyType is <>;

  -- WITH FUNCTION "<"   (Key1, Key2: KeyType) RETURN Boolean IS <>;
  -- This no longer must be a parameter; we know the key is integer

  -- This parameter specifies what to do with each element during
  -- a traversal of a table;
  with procedure Visit (Item: Element);

package Tables_Generic_Hash is
------------------------------------------------------------------------
--| Specification of the abstract data type for an ordered table of
--| element records, each containing a key.
--| This version has type definitions to implement the table as a
--| hash table. The client cannot see or use these types
--| because Table is LIMITED PRIVATE.
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: February 1996
------------------------------------------------------------------------
  
-- Data Structure   

  type TableType is limited private;

-- Exported exceptions

  UninitializedTable: exception;
  NoSpaceLeft       : exception;

-- Operators   

  procedure InitializeTable (Table : in out TableType);
  -- Pre : None
  -- Post: Table is an initialized TableType
     
  function SizeOfTable (Table : TableType) return Natural;
  -- Pre : Table is an initialized TableType
  -- Post: Returns the number of elements in Table

  procedure Search (Table   : TableType;
                    Target  : KeyType;
                    Success : out Boolean);
  --  Pre : Table is an initialized TableType
  --  Post: Success is True if Target is found; otherwise,
  --        Success is False.
     
  procedure Insert (Table   : in out TableType;
                    Item    : Element;
                    Success : out Boolean);
  --  Pre : Table and Item are defined; Table is initialized.
  --  Post: Success is True if insertion is performed; Success is False
  --        if insertion is not performed because there is already
  --        an element with the same key as Item.
  --  Raises: NoSpaceLeft if there is no space available for Item.
     
  procedure Delete (Table   : in out TableType;
                    Target  : KeyType;
                    Success : out Boolean);
  --  Pre : Table and Target are defined; Table is initialized.
  --  Post: Success is True if deletion is performed; Success is False
  --        if deletion is not performed because there is no element
  --        whose key is Target.
     
  procedure Replace (Table   : in out TableType;
                     Item    : Element;
                     Success : out Boolean);
  --  Pre : Table and Item are defined; Table is initialized.
  --  Post: Success is True if the replacement is performed; Success is
  --        False if there is no element with the same key as Item.
     
  procedure Retrieve (Table   : TableType;
                      Target  : KeyType;
                      Item    : out Element;
                      Success : out Boolean);
  --  Pre : Table is an initialized TableType.
  --  Post: Success is True if the copy is performed; Success is False
  --        if there is no element whose key is Target.

  procedure Traverse (Table : TableType);
  --  Pre : Table is an initialized TableType.
  --  Post: Each element is operated on in turn by procedure Visit.

private

  subtype TableIndex is Positive range 1..Capacity;
  subtype TableSize  is Natural  range 0..Capacity;

  type OccupancyIndicator is 
    (NeverOccupied, FormerlyOccupied, CurrentlyOccupied);  
  
  type ElementRecord is record
    Info    : Element;
    Occupied: OccupancyIndicator;
  end record;
    
  type TableData is array(TableIndex range <>) of ElementRecord;

  type TableType is record
    CurrentSize : TableSize := 0;
    Data        : TableData(TableIndex);
  end record;

end Tables_Generic_Hash;