For this computer assignment, you are to write a C++ program to create, search, print, and sort an item inventory. The item inventory information will be kept in a sequentially allocated table with a given size of entries with default size TBLSZ = 31. Each table entry is described by the following structure, as specified in the header file Entry.h.

struct Entry { string key, desc; unsigned num; };

The key field is the item identifier, which is two uppercase letters followed by a decimal digit (e.g., AD5 or XR8). The desc field contains the item description, and the num field contains the number of copies of an item in the inventory. The item table can be accessed directly using the separate chaining technique to resolve the collisions. The private hash function expects an item key as the input argument, and it returns an integer in the range: 0 (TBLSZ1), which has the following prototype: int HT :: hash ( const string& key ). The object file hash.o, which is in the same directory with the header file Entry.h, contains the implementation of this function.

The item inventory system is defined as a class, named as HT, and its definition is given in the header file hTable.h, which is in the same directory with Entry.h. The hash table hTable (container of type vector < list < Entry > >) is used to store the entries of the item inventory, and the pointer table pTable (container of type vector < Entry* >) is used to store the addresses of the entries in hTable. The member functions of HT are described below.

HT :: HT ( const unsigned& hs ) : The hash table, which is a vector of list < Entry > containers, can be created dynamically for a given fixed size hs by its constructor. Initially, the pointer table, which is a vector of type Entry*, is empty but its size will increase dynamically after inserting a new Entry item in this table, which is the address of the inserted item in the corresponding list container.

HT :: ~HT ( ) : Since the hash table is implemented as a vector of list containers, the destructor of the hash table first frees the memory for all list containers and then frees the memory for the vector containers for the hash table and the pointer table.

void HT :: insert ( const Entry& e ) : This public function inserts the record of the item e : (key, desc, num) in the hash table. If the key already exists in the table, then the function prints an error message; otherwise, it prints the index value of the inserted record in the hash table and it also inserts the address of the record (in the hash table) into the pointer table. Since each element of the hash table is implemented as a list container with the data type Entry, in the case of a collision, simply insert the new record at the beginning of the corresponding list container. To check if the record e is already in the hash table, you can use the function find_if ( ) from the STL. To compare the key of the record e with the keys of the elements in the list container, list < Entry >& l = hTable [ i ], in hash table position i, Hashing with Separate Chaining and Indirect Sorting 2 you can use either a predicate or a lambda for the compare component of the find_if ( ) function. If the item is a new item, then the find_if ( ) function returns l.cend ( ).

void HT :: search ( const string& key ) : This public function searches the hash table for a record with a given key. As in the insert ( ) function, you can use the find_if ( ) function from the STL to search for a record in the hash table. If the search is successful, search ( ) function prints the information for the record; otherwise, it prints an error message.

void HT :: hTable_print ( ) : This public function prints the subscript and the contents of all (and only) the active records in the hash table.

void HT :: pTable_print ( ) : This public function prints the contents of all (and only) the active records in the hash table. Since the records need to be printed in alphabetical order with their key values, this function first sort the elements of the pointer table using the sort ( ) function from the STL. The cmp component for sorting, bool cmp ( Entry* p, Entry* q ), returns true if the key of the item in location p comes before the item in location q in alphabetical order.

The input data consists of three types of records, as described below:

Insertion records have the format A:item-key:item-number:item-description:

Search records have the format S: item-key:

Table print records have the format

P:

Program Note: The records stored in the inventory system have unique keys. Duplicate keys are not permitted.

The main ( ) routine in the driver program prog9.cc (provided), implements the following tasks:

1. Prints a header message.

2. Creates an empty hash table.

3. Reads the entire input file, and process each record as follows: if the record transaction code is:

A Searches the hash table for a record having the same key. If such a record is found, prints an appropriate duplicate key message, and ignores the information from the input record. Otherwise, inserts the record in the hash table, and places the address of the record in the pointer table.

S Searches the hash table for a record with a given key, and prints the key and other information for the record. If the record is not found in the table, it prints an appropriate key not found message.

P Prints the subscript and contents of each active record in the hash table. 3

4. After the data in the input file has been read, and the tables have been constructed, sorts the records in the pointer table, and then prints the records in the hash table in ascending order with the key field.

5. Prints a program termination message.

prog9.cc:

#include "/home/onyuksel/courses/340/progs/12s/p10/prog10.h" #include "/home/onyuksel/courses/340/progs/12s/p10/hTable.h"

// Hashing with linear probe and indirect sorting

int main ( ) { char c; // operation code Entry e; // holds input data HT h; // hash table

// print program header message cout << "\t*** Hashing with linear probe *** ";

while ( cin >> c ) { switch ( c ) { case 'A': // insert record in hash table read_rec1 ( e ); prnt_rec1 ( e ); h.insert ( e ); break;

case 'S': // search for record in hash table read_rec2 ( e ); cout << "search: key " << e.key; h.search ( e.key ); break;

case 'P': // print all active entries of hash table cin.ignore ( BUF_SZ, ':' ); cout << " hTable_print: "; cout << "entry key number description "; h.hTable_print ( ); break;

default: // illegal command cout << "error: invalid entry "; break; } }

// print hash table (in sorted order)

cout << " sort_print: sorted hash table: "; cout << " key number description "; h.pTable_print ( );

// print program termination message cout << " \t*** end of program termination *** "; return 0; }