// Source: "Software Design ...", John A Robinson, Newnes, 2004, page 217.
//
//
// C++ Program to implement ADT table of pairs
// using unordered array
//
//
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

struct ipair {
	int key;
	int other_stuff;
	};

class table_of_pairs {
	int table_size;
	ipair *ptable;
	int num_in_table;
public:
	table_of_pairs(const int size) 	{				
		num_in_table = 0; 
		ptable = new ipair[(table_size = size)+1];
		// Set up an array of the requested size
		};
	~table_of_pairs() 		{delete [] ptable;};
	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);};
	void print_table() const;
	};
//
// Methods for the class table_of_pairs follow
//

int table_of_pairs::add_to_table(const int key, const int other)
	{
	remove_from_table(key);		// Remove any existing entry with this key value
	if (num_in_table == table_size)
		return(-1);		// table is full
	ptable[num_in_table].key = key;	// Add new item at the end of the list
	ptable[num_in_table++].other_stuff = other;
	return(0);
	}
int table_of_pairs::remove_from_table(const int member)
	{
	int offset = 0;
	ptable[num_in_table].key = member;	// sentinel
	while (ptable[offset].key != member)
		offset++;// Keep going until find something with this key value
	if (offset == num_in_table)	// The one I found was the sentinel -
		return(-1);		// - so member is not in table
	// If member is in table, copy down final element in its place (to overwrite it)
	ptable[offset] = ptable[num_in_table - 1];
	num_in_table--;
	return(0);
	}
int table_of_pairs::get_other_stuff(const int member, int& other) const
	{
	int offset = 0;
	ptable[num_in_table].key = member;	// sentinel
	ptable[num_in_table].other_stuff = 0;	// set up, so that if key is not in table, this zero
						// value of other_stuff will get put into other 
	while(ptable[offset].key != member)
		offset++;
	other = ptable[offset].other_stuff;
	return(offset != num_in_table);		// returns 0 if the one found was the sentinel
	}

void table_of_pairs::print_table() const
	{
	int offset;
	for (offset = 0; offset < num_in_table; offset++)
		cout << ptable[offset].key << "," << ptable[offset].other_stuff << " ";
	cout << "\n";
	}


//
// The main program here is just a simple test loop
// The commands q, a, r, c, p are available, to quit, add element,
// remove element, check for element, and print table repectively.
//
int main()
	{
	char c;
	int key, other;
	table_of_pairs mytable(8); 
	// Here saying that 8 is max num of elements I will use in 
	// any run of this test program (A bit restrictive).
	while(1)
		{
		cout << ": "; // Prompt
		cin >> c;
		switch(c)
			{
			case 'q':
				return 0;
			case 'a':
				cin >> key >> other;
				mytable.add_to_table(key, other);
				break;
			case 'r':
				cin >> key;
				mytable.remove_from_table(key);
				break;
			case 'c':
				cin >> key;
				if (mytable.get_other_stuff(key, other))
					cout << "Item labelled " << key << " has value " << other << " in mytable\n";
				else
					cout << "There is no item labelled " << key << " in mytable\n";
				break;
			case 'p':
				mytable.print_table();
				break;
			default:
				cout << "Use q, a, r, c or p only\n";
				break;
			}
		cout << mytable.number_in() << " items in table\n";
		}
	}