with Lists_Generic;
generic

  type Element is private;     -- assignment and equality predefined
  type KeyType is private;     -- here too

  Capacity: in Positive;       -- maximum table size
  
  -- These generic parameters specify how to insert a key in an
  -- element, 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 parameter specifies what to do with each element during
  -- a traversal of a table;
  with procedure Visit (Item: Element);

package Tables_Generic_List 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 
--| singly-linked list. The client cannot see or use these types
--| because Table is LIMITED PRIVATE.
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------

-- Data Structure   

  type TableType is limited private;

-- Exported exceptions

  UninitializedTable: exception;
  NoSpaceLeft       : exception;

-- Operators   

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

  procedure Search (Table   : TableType;
                    Target  : KeyType;
                    Success : out Boolean);
  --  Searches a Table for Target.
  --  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);
  --  Inserts Item into a Table.
  --  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);
  --  Deletes the element with key Target from a Table.
  --  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);
  --  Replaces the element of a Table with the same key as
  --  Item by the contents of Item.
  --  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);
  --  Copies the element whose key is Target into Item.
  --  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;

  package Lists is 
    new Lists_Generic(ElementType => Element);

  type TableType is record
    CurrentSize: TableSize := 0;
    Data: Lists.List;
  end record;

end Tables_Generic_List;