// Source: "Software Design ...", John A Robinson, Newnes, 2004, page 293.
//
//
// ADT table of pairs
// using hash table with separate chaining
//
//
struct ipair {
	int key;
	int other_stuff;
	ipair *next;
	};
class table_of_pairs {
	int table_size;
	ipair hasht[997];	// Zeroth list entries - only the pointers matter here
	int num_in_table;
	int hashf(int key) const
            { return(key%997); };
public:
	table_of_pairs();
        ~table_of_pairs();
	int add_to_table(const int, const int);
	int remove_from_table(const int);
	int get_other_stuff(const int, int&) const;
	int number_in() const
            {return(num_in_table);};
	};

//
// Methods for the class table_of_pairs follow
//
table_of_pairs::table_of_pairs()
      {
      for (int i=0; i < 997; i++)		// Initialize everything to empty
        {
        hasht[i].key = hasht[i].other_stuff = 0;
        hasht[i].next = 0;
        }
      };
table_of_pairs::~table_of_pairs()  // Destructor has to deallocate memory
      {
      for (int i=0; i < 997; i++)
          {
          if (hasht[i].next)
             {
             ipair *p = hasht[i].next;
             ipair *q;
             while(q = p->next)
                 {
                 delete p;
                 p = q;
                 }
             delete p;
             }
          }
      }


int table_of_pairs::add_to_table(const int key, const int other)
	{
	remove_from_table(key);			// To prevent double entries with this key
	ipair *p = &hasht[hashf(key)];
	ipair *q = new ipair;			// Set up new item
	q->key = key;
	q->other_stuff = other;
	q->next = p->next;			// Hook new item at beginning of list
	p->next = q;
	num_in_table++;
	return(0);
	}
int table_of_pairs::remove_from_table(const int key)
	{
	ipair *p = &hasht[hashf(key)];
	while(p->next)
		{
		if (p->next->key == key)
			{
			ipair *q = p->next;	// Unhook this item from the linked list
			p->next = q->next;
			delete q;
			num_in_table--;
			return(1);
			}
		p = p->next;
		}
	return(0);	// Key not in table
	}
int table_of_pairs::get_other_stuff(const int key, int &other) const
	{
	const ipair *p = &hasht[hashf(key)];
	while(p->next)
		{
		p = p->next;
		if (key == p->key)
			{
			other = p->other_stuff;
			return(1);
			}
		}
	return(0);	// Not found
	}



#include <iostream>
using namespace std;
int main()
    {
    cout << "This program exercises a table of pairs.\n";
    cout << "In the instructions below, m and n are integers\n";
    cout << "Enter a m n to store integers m/n as a key/value pair\n";
    cout << "Enter f m to retrieve a value associated with key m\n";
    cout << "Enter r m to remove a pair with key m\n";
    cout << "Enter q to quit\n";
    table_of_pairs table;
    while(1)
            {
            char c;
            int m, n;
            cout << "\n> ";
            cin >> c;
            switch (c)
                   {
                   case 'q':
                        return 0;
                   case 'a':
                        cin >> m >> n;
                        table.add_to_table(m, n);
                        break;
                   case 'f':
                        cin >> m;
                        if (table.get_other_stuff(m, n))
                           cout << "value associated with key " << m << " is " << n;
                        else
                           cout << "Cannot find key " << m << " in the table";
                        break;
                   case 'r':
                        cin >> m;
                        if (table.remove_from_table(m))
                           cout << "Item with key " << m << " removed";
                        else
                           cout << "Cannot find key " << m << " in the table";
                        break;
                   default:
                        cout << "Invalid input\n";
                        break;
                   }

            }
    }