/*
       *      Code modified from Weiss Textbook: http://users.cis.fiu.edu/~weiss/dsaa_c++/Code
       *      Version author: A. Kalyanaraman
       *      Date:  11/22/2011
       *      For use in Cpt S 223, School of EECS, WSU
       */
 
	 
	 #include <iostream>
        #include "Chaining.h"

		using namespace std;



        /**
         * Construct the hash table.
         */
        HashTable_chaining::HashTable_chaining( const string & notFound, int size )
          : ITEM_NOT_FOUND( notFound ), theLists( nextPrime( size ) )
        {
        }

        /**
         * Insert item x into the hash table. If the item is
         * already present, then do nothing.
         */
        void HashTable_chaining::insert( const string & x )
        {
            list<string>&  whichList = theLists[ hash( x, theLists.size( ) ) ];

			// search to make sure element not present
			for(list<string>::iterator itr=whichList.begin();itr!=whichList.end();itr++) {
				if(*itr==x) {
					//cout << "Element already present\n";
					return;
				}
			}
			whichList.push_back(x);
        }

        /**
         * Remove item x from the hash table.
         */
        void HashTable_chaining::remove( const string & x )
        {
			int hash_index = hash( x, theLists.size( ) ) ;

            list<string>&  whichList = theLists[ hash_index ];

			// search to make sure element not present
			for(list<string>::iterator itr=whichList.begin();itr!=whichList.end();itr++) {
				if(*itr==x) {
           			theLists[hash_index].erase(itr);
					return;
				}
			}
			// element not found - so nothing to remove
        }

        /**
         * Find item x in the hash table.
         * Return the matching item or ITEM_NOT_FOUND if not found
         */
        const string & HashTable_chaining::find( const string & x ) const
        {
			int hash_index = hash( x, theLists.size( ) ) ;

            const list<string>&  whichList = theLists[ hash_index ];

			// search to make sure element not present
			for(list<string>::const_iterator itr=whichList.begin();itr!=whichList.end();itr++) {
				if(*itr==x) {
					return *itr;
				}
			}
			// element not found 
            return ITEM_NOT_FOUND;
        }

        /**
         * Make the hash table logically empty.
         */
        void HashTable_chaining::makeEmpty( )
        {
            for( int i = 0; i < theLists.size( ); i++ )
                theLists[ i ].clear( );
        }

        /**
         * Deep copy.
         */
        const HashTable_chaining &
        HashTable_chaining::operator=( const HashTable_chaining & rhs )
        {
            if( this != &rhs )
                theLists = rhs.theLists;
            return *this;
        }