// FILE: sequence_test.cxx
// An interactive test program for the new sequence class
#include <cctype>       // Provides toupper
#include <iostream>     // Provides cout and cin
#include <cstdlib>      // Provides EXIT_SUCCESS
using namespace std;
// PROTOTYPES for functions used by this test program:
void print_menu( );
// Postcondition: A menu of choices for this program has been written to cout.

char get_user_command( );
double get_number(string prompt);
// Postcondition: The user has been prompted to enter a real number. The
// number has been read, echoed to the screen, and returned by the function.


int main( )
{
keyed_bag3 test; // A sequence that we’ll perform tests on
keyed_bag3 test2;
char choice;   // A command character entered by the user
double retkey;
double ret;
bool result;
cout << "I have initialized an empty sequence of real numbers." << endl;
print_menu( );
do
{
   
   choice = toupper(get_user_command( ));
   
   switch (choice)
   {
       case '?': print_menu( );
                 break;
       case 'S': 
		cout << "Size is " << test.size( ) << '.' << endl;
       break;
       case 'C': 
		retkey = get_number("Search for what entry? ");
		 ret = int(test.count(retkey));
		cout << retkey << " was found " << ret << endl;
       break;
       case 'I': 
		test.insert(get_number("Insert which value? "),int(get_number("Insert into which key? ")));
       break;
       case 'R': 
			retkey = get_number("Delete which key? ");
			test.erase(int(retkey));
                 cout << retkey << " has been removed." << endl;
                 break;
       case 'G':
			retkey = get_number("Which key do you want to retreive? ");
			ret = test.get(int(retkey));
			cout << "Value of key " << retkey << " is " << ret << endl;
		break;
	  case 'H':
			result = test.has_key(int(get_number("Which key do you whish to check? ")));
			if(result == true)
				cout << "Key exists " <<endl;
			else
				cout << "Key doesn't exist" << endl;
		break;
       case 'Q':
	  	cout << "Transfering bags..." << endl;
       	system("PAUSE");
       break;
     
	  default:  cout << choice << " is invalid." << endl;
   }
}
while ((choice != 'Q'));

return EXIT_SUCCESS;
}

void print_menu( )
// Library facilities used: iostream.h
{
cout << endl; // Print blank line before the menu
cout << "The following choices are available: " << endl;
cout << " ?   Shows this message" << endl;
cout << " C   Searches for a matching values" << endl;
cout << " R   Removes a key from the bag" << endl;
cout << " G   Gets the value of a key from the get(...) function" << endl;
cout << " S   Print the result from the size( ) function" << endl;
cout << " I   Insert a new number with the insert(...) function" << endl;
cout << " Q   Quit this test program" << endl;
cout <<" H   Check to see if the key is currently in use" << endl;
}

char get_user_command( )
// Library facilities used: iostream
{
char command;

cout << "Enter choice: ";
cin >> command; // Input of characters skips blanks and newline character
return command;
}

double get_number(string prompt){
	double result;
	cout << prompt;
	cin  >> result;
	return result;
}

class record_type {
  public:
    typedef double value_type;
    void setKey(int k) { key = k; }
    int getKey() const { return key; }
    void setData(value_type d) { data = d; }
    value_type getData() const { return data; }
    bool operator ==(record_type rv) const {
      return (key == rv.key) && (data == rv.data); }
  private:
    int key;
    value_type data;
};
class node {
  public:
	node(){
		link_field = NULL;
		data_field.setData(value_type());
		data_field.setKey(int());
	}
    typedef double value_type;
    void set_data(const value_type& data, const int& key){ 
		data_field.setData(data);
		data_field.setKey(key);
	}
    void set_link(node* new_link) { link_field = new_link; }
    int getKey( ) const { return data_field.getKey(); }
    value_type getData ( ) const { return data_field.getData();};
    const node* link( ) const { return link_field; }
    node* link( ) { return link_field; }
  private:
    record_type data_field;
    node* link_field;
};
class keyed_bag3 {
	public:
		typedef double value_type;
		typedef std::size_t size_type;
		keyed_bag3();
		keyed_bag3(const keyed_bag3& source);
		~keyed_bag3();
		keyed_bag3& operator =(const keyed_bag3& source);
		void insert(const value_type& entry, int key);
		bool erase(int key);
		value_type get(int key) const;
		size_type size() const;
		size_type count(const value_type& target) const;
		bool has_key(int key) const;
	private:
		node* head_ptr;
		node * prev_ptr;
		int counter;
		void setHead(node* ptr){head_ptr = ptr;}
		void setCounter(int ct){counter = ct;}
};
keyed_bag3::keyed_bag3() {
	head_ptr = NULL;
	prev_ptr = NULL;
	counter = 0;
}
keyed_bag3::~keyed_bag3(){
	node *cursor = head_ptr;
	node *tmp;
	while(cursor != NULL){
		tmp = cursor;
		cursor = cursor->link();
		delete tmp;
	}
}
keyed_bag3::keyed_bag3(const keyed_bag3& source){
	head_ptr = source.head_ptr;
	insert(head_ptr->getData(),head_ptr->getKey());
	node *cursor;
	cursor = source.head_ptr->link();
	while (cursor != NULL)
	{
	    insert(cursor->getData(), cursor->getKey());
	    cursor = cursor->link( );
	}
	counter = source.counter;
}
std::size_t keyed_bag3::count(const value_type& target) const{
	node *cursor;
	size_t ct =0;

	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )){
	    if (target == cursor->getData( )){
			ct++;
		}


	}
	return ct;
}
bool keyed_bag3::erase(int key){
	node *cursor;
	node * prev_ptr=NULL;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )){
		    if (key == cursor->getKey( )){
			if(prev_ptr == NULL){
				//This is the head ptr
				head_ptr = cursor->link();
				delete cursor;
			}else{
				prev_ptr->set_link(cursor->link());
				delete cursor;
			}
			counter--;
			return true;
		}
	}
	return false;
}
void keyed_bag3::insert(const value_type& data, int key){
	if(head_ptr == NULL){
		//Ok its null just create a node
		head_ptr = new node;
		head_ptr->set_link(NULL);
		head_ptr->set_data(data,key);
		counter++;
	}else{
		node *cursor;
		//Check for a key
		for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )){
		    if (key == cursor->getKey( )){
				cursor->set_data(data,key);
				return;
			}
		}
		cursor = new node;
		cursor->set_link(head_ptr);
		cursor->set_data(data,key);
		head_ptr = cursor;
		counter++;
	}
}
keyed_bag3::value_type keyed_bag3::get(int key) const{
	node *cursor;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )){
	    if (key == cursor->getKey( )){
			return cursor->getData();
		}
	}
	return double();
}
bool keyed_bag3::has_key(int key) const {
	node *cursor;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )){
	    if (key == cursor->getKey( )){
			return true;
		}
	}
	return false;
}
size_t keyed_bag3::size() const{
	return counter;
}
keyed_bag3& keyed_bag3::operator =(const keyed_bag3& source){
	if (this == &source)
	    return *this;
	keyed_bag3 *n_keyed_bag = new keyed_bag3;
	n_keyed_bag->setHead(source.head_ptr);
	n_keyed_bag->insert(head_ptr->getData(),head_ptr->getKey());
	// Copy the rest of the nodes one at a time, adding at the tail of new list.
	node *cursor;
	cursor = head_ptr->link();
	while (cursor != NULL)
	{
	    n_keyed_bag->insert(cursor->getData(), cursor->getKey());
	    cursor = cursor->link( );
	}
	n_keyed_bag->setCounter(counter);
	return *this;
}