Go to Package Implementation

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
  -- 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 IS
------------------------------------------------------------------
--| Specification of the abstract data type for a table of
--| element records, each containing a key.
--| This version has type definitions to implement the table as an
--| array. 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);
  --  Repeatedly calls procedure Visit (a generic parameter) to
  --    process each element of a Table.
  --  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 TableData IS ARRAY(TableIndex RANGE <>) OF Element;

  TYPE TableType IS RECORD
    CurrentSize : TableSize := 0;
    Data        : TableData(TableIndex);
  END RECORD;

END Tables_Generic;