[CISP430] Chaining Hash Table (table.h)

/*
 
	data
   |  1 | -> head of node1 linked list A 
   |  2 | -> head of node2 linked list B
 
			 data[]	 Node		Node
	key | table|  | key value paire |
		   |  1	| -> [*link] -> [*link] -> NULL
		   |  2 | -> NULL;
		   |  3 | -> [*link] -> NULL
 
*/
#include <assert.h>    // Provides assert
#include <stdlib.h>    // Provides NULL and size_t
#include <iostream>
#include "link2.h"
 
using namespace std;
template <class RecordType> // tamplate parameter is RecodeType
class Table
{
	private :
		static const size_t CAPACITY = 811;
		/**** Node stuff *****/
		int key; // Each record requres a unique identifying value
		// key is the stock number store in a member function 
		int var; // varriable for input 
		Node<RecordType> *data[CAPACITY]; // TABLE_SIZE show me how many capacity of data set in the data then ex. data[1] is the first set of array list  
		Node<RecordType> *curNote;		//to point to the current of node 
		Node<RecordType> *precursor;	//to point to the one before current node
		//Node<Item> *curNote;		//to point to the current of node 
		//Node<Item> *precursor;	//to point to the one before current node
		size_t total_records;		// like many_nodes	
	public:
		Table(); //constructor
	//	Table(const Table& source); // copy constructor
		~Table();// missing
		void insert(const RecordType& entry);
		void remove(int key);
	//	void print(int index)const;
	//  void operator =(const Table& source);
		bool is_present(const RecordType& target) const;	 // THIS LINE HAS ERROR 
		void find(int key, bool& found, RecordType& result) const;
		int getHash(int key){return(key % CAPACITY);}	// get table number  
		size_t size( ) const{ return this.total_recods;	}
		/*
		struct hotKey
		{ int key; };
			*/
		// EXTRA FUNCTION 
	//	void hashTable(int &var);
 
};
template <class RecordType> 
Table<RecordType>::~Table(){ }
template <class RecordType>
//Table<RecordType>::Table()
Table<RecordType>::Table()
//Postcondition: The Table has been initialized as an empty Table.
{
		int i =0;
		// WORNG DECLEARATION FOR TABLE 
		// ALL THE CELL OF THE DATA[CAPACITY] POINT TO NULL 
		for (i; i <CAPACITY;++i)
			data[i] = NULL; // DATA IS CONFUSING WITH NODE ITEM DATA 
		curNote=NULL;	
		precursor=NULL;	
		total_records=0;	
		key = 0; 
 
 
 
 
	/*
	table = new Node<RecordType>*[CAPACITY];
	for (int i =0;< i <CAPACITY;++i)
		table[i].key = NULL;
	*/
	/*
	size_t i;
	used = 0;
	for(i=0;i<CAPACITY;++i)
	{	data[i].key = NEVER_USED;	}
	*/
}
/*
template <class RecordType>
Table<RecordType>::Table(const RecordType& result)
{
	table = new LinkedHashEntry*[TABLE_SIZE];
    for (int i = 0; i < TABLE_SIZE; i++)
	{	table[i] = result.data[i];	}
}
 
template <class RecordType>
//void Table<RecordType>::hashTable(RecordType &var)
void Table<RecordType>::hashTable(int &var)
// HASHTABLE PASS DATA TO INSERT AND PRINT 
{	
		RecordType temp;
		const RecordType *entry = &temp;
 
		temp.key = var;
		temp.var = var;
		insert(entry);
}
*/
template <class RecordType>
void insert(const RecordType& entry)
 //	Precondition: entry>= 0. Also if entry is not already a key in the table,  
 // 	then the Table has space for another record.(i.e., size( ) < CAPACITY).
 // Postcondition: If the table already had a record with a key equal to //
 // entry, then that record is replaced by entry. Otherwise, the entry will be 
 // added as a new record of the Table.
 // A. DECLEAR EVERYTHING AS 0 // CONSTRUCTOR 
 // B. AFTER STEP 1 CREATE NEW NODE IF NESSESAY OTHERWISE DATA[INDEX]-> NULL
 //	1. FIND TABLE USING KEY 
 // 2. CHECK IF THERE IS ALREADY ITEM IN THE TABLE OR NOT 
 // 3-A. IF THERE IS NOT ITEM IN THE TABLE, INSERT NODE 
 // 3-B. IF THERE IS ITEM INSERT THE ITEM AFTER LAST NODE
 //
 // ** TABLE[HASH] IS ALREADY POINTER THEREFORE YOU CAN CONNECT TO NEWNDOE IN LINK 
 // ** BEFORE INSERT, I NEED TO CREATE KEY 
 // ** INEED TO CREATE NODE BEFORE ASSIGN TO TABLE[]
{
	int hash = getHash(entry.key);
	/* IF THERE IS NO ITEM CREATE NEW NODE IN THE HASH */
	//TABLE IS NOT DETECTED SO I MAY NEED TO CHANGE LATER 
	if( entry.data[hash].key == NULL ) // THERE IS NO ITEM IN THE HASH AREA -> CREATE NEW NODE IN THE HASH
	{	
		Node<RecordType> ptr = new Node<RecordType>;
		entry.data[hash].key = ptr; 	
	}// CREATED NEW NODE IN THE TABLE[HASH] PLACE 
	/*	IF THERE IS (ARE) ITEM(S)*/
	else 
	{
		// 1. FIND IF THERE IS MORE THAN 1 ITEM 
		// 2. IF THERE ARE MROE THAN 1 FIND END OF LINKED LIST 
		// 3. INSERT ITEM IN THE END OF LINKED LIST AND POINT NULL 
		// NEED TO RETHINK HERE 
 
		Node<RecordType>* newNode = entry.data[hash]; // CREATE NEW NODE
		while ((newNode != NULL) && (newNode.key != entry.key ))
			newNode = newNode->link;
		if(newNode.key == entry.key) // entry key and previous key are much 
		{	
			list_head_insert(newNode,newNode.key);	
			++entry.total_records;
		}
		else // there is not much key
		{	
			list_insert(newNode,newNode.key);			
			++entry.total_records;
		}
	}
}
 
template <class RecordType>
//void Table<RecordType>::remove(int key)
void remove(int key)
//	Postcondition: If a record was in the Table with the specified key, then that record has been removed; otherwise the table is unchanged.
{
	int hash = getHash(key);
	//IF DATA[HASH] IS NOT NULL FIND WHRE YOU NEED TO ELASE 
	if(data[hash] != NULL)
	{
		precursor = NULL;
		Node<RecordType>* newNode = data[hash];
		while((newNode->link != NULL)&&(newNode.key!= key))
		{
			precursor = newNode;
			newNode = newNode.link;
		}
		if(newNode.key == key)
		{
			if(precursor == NULL)
			{	
				// SUPPOSED TO BE NODE<ITEM>
				Node<RecordType>* tempNode = newNode.link;
				delete newNode;
				data[hash] = tempNode;
				--total_records;
			}
			else
			{
				Node<RecordType>* tempNode2 = newNode.link;
				delete newNode;
				precursor.link;
				--total_records;
			}
		}
	}
 
 
 
 
	/*
	bool fond;
	size_t index;
	assert(key >= 0);
	find_index(key,found,index);
	if(found)
	{
		// the key was found, so remove this record and reduce used by 1
		data[index].key=PREVIOUSLY_USED;
		--used;
	}*/
}
/*
template <class RecordType> 
//void Table<RecordType>::print(int index) const
void Table<RecordType>::print(int index) const
//Postcondition: If the Table with the index has data, then print the index and data in a chining format
//PRINT IS NOT PRINTING HOW MANY YET
{
	// INDEX WILL INPORT SO DATA HASH IS ALREADY SELECTED 
	//curNote = data[index]; // 
	cout << "data["<<index<<"] = ";
	if(data[index]!=NULL)
	{
		while(curNote != NULL)
		{
			cout <<"[" << curNote->data <<"] -> ";
		}
	}
	else if ((data[index]==NULL) || (curNote == NULL))
	{	cout << " NULL ";	}
	cout << endl;
}
 */
template <class RecordType>
//bool Table<RecordType>::is_present(const Item& target) const
//bool Table<RecordType>::is_present(const RecordType& target) const
bool Table<RecordType>::is_present(const RecordType& target) const
//Postcondition: The return value is true if there is a record in the Table with the specified key.
// Otherwise, the return value is false.
// YOU NEED TO USE FIND FUNCTION TO FIND RESULT 
// THIS FUNCTION ASK YOU IF THERE IS NODE OR NOT 
// QUOTING FROM TEXT BOOK :
//"HASHING CAN BE FIND IN THE AVERAGE CASE. ADDING AND DELETING ELEMENTS
//IS EASIER IN A CONTAINER THAT PROVIDES HASHING, BECAUSE A BINARY SEARCH REQUIRES THAT THE ITEMS REMAIN SORTED."
 
{
		int hash = getHash(target.key);
		if(data[hash] == NULL)
		{	return false;	}
		else 
		{	
			Node<RecordType>* newNode = data[hash];
			while((newNode!=NULL) && (newNode.key!=key))
			{	newNode = newNode.link; }
			if (newNode == NULL)
			{	return false;	}
			else
			{	return true;	}
		}
}
 
template <class RecordType>
//void Table<RecordType>::find(int key, bool& found, RecordType& result) const
void Table<RecordType>:: find(int key, bool& found, RecordType& result) const
//Postcondition: If a record is in the Table with the specified key, 
//then found is true and result is set to a copy of the record with that key. 
//Otherwise found is false and the result contains garbage.
{
	int hash = getHash(key);
	if(data[hash]==NULL)
	{	found = false;	}
	else
	{
		Node<RecordType>* newNode = data[hash];
		while((newNode!=NULL) && (newNode.key!=key))
		{	newNode = newNode.link; }
		if (newNode == NULL)
		{	found = false;	}
		else
		{	
			found = true;	
			// I NEED TO COPY NEWNODE TO RESULT * RESULT IS EMPTY NOW 
			result.key = newNode.key;	
		}
	}
 
}