// Chap 11, pp 523 - 526
// Rename this file as TableA.h

// *********************************************************
// 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.
// *********************************************************
#include "boolean.h"
const int MAX_TABLE = 100;

typedef int keyType;  // desired-type-of-search-key
struct dataItem
{  keyType Key;
   //... and probably other data members
};  // end struct
typedef dataItem tableItemType;
typedef void (*functionType)(tableItemType& AnItem);

class tableClass
{
public:
// constructors and destructor:
   tableClass();
   tableClass(const tableClass& T);
   virtual ~tableClass();

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

   virtual boolean TableIsEmpty();
   // Determines whether a table is empty.
   // Postcondition: Returns TRUE if the table was empty,
   // otherwise returns FALSE.

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

   virtual void TableInsert(tableItemType NewItem, 
                            boolean& 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,
                            boolean& 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 is deleted 
   // and Success is TRUE. Otherwise, the table is unchanged
   // and Success is FALSE.

   virtual void TableRetrieve(keyType SearchKey,
                              tableItemType& TableItem, 
                              boolean& Success);
   // 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.

// overloaded operator:
	virtual void operator=(const tableClass T);

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

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

   int Position(keyType SearchKey);
   // 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.
   // Calls: KeyIndex.

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

   int KeyIndex(int First, int Last, keyType SearchKey);
   // 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 
   // Items[First].Key <= Items[First+1].Key <= ... <= 
   // Items[Last].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.