// *********************************************************
// Header file TableA.h for the ADT table. 
// Sorted array-based implementation.
// Assumption: A table contains at most one item with a 
//             given search key at any time.
// *********************************************************
const int MAX_TABLE = maximum-size-of-table;

typedef desired-type-of-search-key keyType;
#include "Data.h"  // definition of itemClass

typedef itemClass tableItemType;
typedef void (*functionType)(tableItemType& AnItem);

class tableClass
{
public:
   tableClass();  // default constructor
   // copy constructor and destructor are
   // supplied by the compiler

// table operations:
// Precondition for all operations: 
// No two items of the table have the same search key.
// The table's items are sorted by search key.

   virtual bool TableIsEmpty() const;
   // Determines whether a table is empty.
   // Postcondition: Returns true if the table is empty;
   // otherwise returns false.

   virtual int TableLength() const;
   // Determines the length of a table.
   // Postcondition: Returns the number of items in the 
   // table.

   virtual void TableInsert(const tableItemType& NewItem, 
                            bool& Success);
   // Inserts an item into a table in its proper sorted
   // order according to the item's search key.
   // Precondition: The item to be inserted into the table 
   // is NewItem, whose search key differs from all search 
   // keys presently in the table.
   // Postcondition: If the insertion was successful, 
   // NewItem is in its proper order in the table and 
   // Success is true. Otherwise, the table is unchanged 
   // and Success is false.


   virtual void TableDelete(keyType SearchKey, 
                            bool& Success);
   // Deletes an item with a given search key from a table.
   // Precondition: SearchKey is the search key of the item 
   // to be deleted.
   // Postcondition: If the item whose search key equals
   // SearchKey existed in the table, the item was deleted 
   // and Success is true. Otherwise, the table is unchanged
   // and Success is false.


   virtual void TableRetrieve(keyType SearchKey,
                              tableItemType& TableItem, 
                              bool& Success) const;
   // Retrieves an item with a given search key from a 
   // table.
   // Precondition: SearchKey is the search key of the item 
   // to be retrieved.
   // Postcondition: If the retrieval was successful,
   // TableItem contains the retrieved item and Success is
   // true. If no such item exists, TableItem and the table 
   // are unchanged and Success is false.


   virtual void TraverseTable(functionType Visit);
   // Traverses a table in sorted search-key order, calling 
   // function Visit once for each item.
   // Precondition: The function represented by Visit
   // exists outside of the ADT implementation.
   // Postcondition: Visit's action occurs once for each 
   // item in the table.
   // Note: Visit can alter the table.


protected:
   void SetSize(int NewSize);
   // Sets the private data member Size to NewSize.

   void SetItem(const tableItemType& NewItem, int Index);
   // Sets Items[Index] to NewItem.

   int Position(keyType SearchKey) const;
   // Finds the position of a table item or its insertion 
   // point.
   // Precondition: SearchKey is the value of the search key
   // sought in the table.
   // Postcondition: Returns the index (between 0 and 
   // Size - 1) of the item in the table whose search key 
   // equals SearchKey. If no such item exists, returns the 
   // position (between 0 and Size) that the item would 
   // occupy if inserted into the table. The table is 
   // unchanged.

private:
   tableItemType Items[MAX_TABLE];  // table items
   int           Size;              // table size

   int KeyIndex(int First, int Last, keyType SearchKey) const;
   // Searches a particular portion of the private array 
   // Items for a given search key by using a binary search.
   // Precondition: 0 <= First, Last < MAX_TABLE, where
   // MAX_TABLE = max size of the array, and the array
   // Items[First..Last] is sorted in ascending order by 
   // search key.
   // Postcondition: If SearchKey is in the array, returns
   // the index of the array element that contains 
   // SearchKey; otherwise returns the index (between First 
   // and Last) of the array element that the item would 
   // occupy if inserted into the array in its proper order.
   // The array is unchanged.
};  // end class
// End of header file.