path: root/Assign5/table.cpp

#include<iostream>
#include"table.hpp"

Table::Table(bool useChaining = false) {
	/* This constructor takes in a boolean value as a parameter. 
	The boolean value useChaining represents 
	whether or not the user intends on using separate chaining 
	as their hashing method. When set to true, the constructor 
	will create a table object represented by an array of pointers
	to the heads of linked lists, a structure more appropriate
	for separate chaining. When useChaining is false, the 
	constructor defaults to a simple array-based hash table.
	*/

	if (useChaining) {
	
		// initialize array of linked list heads
		for (int i = 0; i < 10; i++) {
			tableHeads[i] = NULL;
		}

	}
	else {
		unhashable = false;
		
		// initialize array with 'empty' values
		for (int i = 0; i < 10; i++) {
			tableArray[i] = EMPTY;
			unhashableList[i] = EMPTY;
		}
		
	}
	
}	

void Table::hashLinear(int intList[]) {
	/* Implementation of hash table insertion using linear probing.
	This method takes in an array of integers (10 items max) and hashes
	them into a table object using linear probing for conflict resolution.
	This means that the probe distance is equal to the number of probing 
	attempts, or, f(i) = i. An item cannot be hashed into the table if the probing 
	results in cycling around to the original insertion location again. 
	*/
	int count = 0;
	int slotIndex = 0;
	int originalSlotIndex;
	bool probeFinished;
	
	while (intList[count] != EMPTY && count < 10) {
		slotIndex = intList[count] % 10;
		
		if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item
			tableArray[slotIndex] = intList[count];
		}
		else { // slot taken; must probe
			originalSlotIndex = slotIndex;
			probeFinished = false; 
			
			while (!probeFinished) {
				slotIndex++; // f(i) = i
				
				if (slotIndex > 9) { // wrap around array
					slotIndex = slotIndex - 10;
				}
				
				if (slotIndex == originalSlotIndex) { // gone over whole array; end probing
					unhashable = true;
					unhashableList[count] = intList[count];
					probeFinished = true;
				}
				
				if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item
					tableArray[slotIndex] = intList[count];
					probeFinished = true;
				}
								
			}
			
		}
			
		count++;
	}
	
}

void Table::hashQuad(int intList[]) {
	/* Implementation of hash table insertion using quadratic probing.
	This method takes in an array of integers (10 items max) and hashes
	them into a table object using quadratic probing for conflict resolution.
	This means that the probe distance is equal to the number of probing
	attempts squared, or, f(i) = i^2. An item cannot be hashed into the table if the probing 
	results in cycling around to the original insertion location again. 
	*/
	int count = 0;
	int probeCount = 0;
	int slotIndex = 0;
	int originalSlotIndex;
	bool probeFinished;
	
	while (intList[count] != EMPTY && count < 10) {
		slotIndex = intList[count] % 10;
		
		if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item
			tableArray[slotIndex] = intList[count];
		}
		else { // slot taken; must probe
			originalSlotIndex = slotIndex;
			probeCount = 0;
			probeFinished = false; 
			
			while (!probeFinished) { 
				probeCount++;
				slotIndex = originalSlotIndex + (probeCount * probeCount); // f(i) = i^2
				
				while (slotIndex > 9) { // wrap around array multiple times
					slotIndex = slotIndex - 10;
				}
				
				if (probeCount > 5) { 
					unhashable = true;
					unhashableList[count] = intList[count];
					probeFinished = true;
				}
				
				if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item
					tableArray[slotIndex] = intList[count];
					probeFinished = true;
				}
								
			}
			
		}
			
		count++;
	}
	
}

void Table::hashDouble(int intList[]) {
	/* Implementation of hash table insertion using double hashing. 
	This method takes in an array of integers (10 items max) and hashes
	them into a table object using a second hash function for conflict resolution. 
	The second hash function is equivalent to f(x) = 7 - x % 7. An item cannot be 
	hashed into the table if the probing results in cycling around to the original 
	insertion location again. 
	*/
	int count = 0;
	int probeCount = 0;
	int slotIndex = 0;
	int originalSlotIndex;
	bool probeFinished;
	
	while (intList[count] != EMPTY && count < 10) {
		slotIndex = intList[count] % 10;
		
		if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item
			tableArray[slotIndex] = intList[count];
		}
		else { // slot taken; must probe
			originalSlotIndex = slotIndex;
			probeCount = 0;
			probeFinished = false; 
			
			while (!probeFinished) {
				probeCount++;
				slotIndex = originalSlotIndex + (probeCount * (7 - intList[count] % 7)); // f(x) = 7 - x % 7
				
				while (slotIndex > 9) { // wrap around array 
					slotIndex = slotIndex - 10;
				}
				
				if (slotIndex == originalSlotIndex) { // gone over whole array; end probing
					unhashable = true;
					unhashableList[count] = intList[count];
					probeFinished = true;
				}
				
				if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item
					tableArray[slotIndex] = intList[count];
					probeFinished = true;
				}
								
			}
			
		}
			
		count++;
	}
	
}

void Table::hashChaining(int intList[]) {
	/* Implementation of hash table insertion using separate chaining. 
	This method takes in an array of integers (10 items max) and hashes 
	the items into a table object using separate chaining for conflict
	resolution. This means for each insertion index, a linked list exists
	where all of the values that hash to that index are inserted at the head
	of the linked list.
	*/
	int count = 0;
	int slotIndex = 0;
	NODE *newHead;
	
	while (intList[count] != EMPTY && count < 10) {
		newHead = new NODE();
		slotIndex = intList[count] % 10;
		newHead->key = intList[count];
		newHead->next = tableHeads[slotIndex];
		tableHeads[slotIndex] = newHead;
		count++;
	}

}

void Table::printTable(bool useChaining = false) {
	/* A method for printing out the contents of a hash table object
	that creates a visual representation of the hash table and its
	contents and prints them to the console (or a file if directed).
	This method takes in a boolean value letting the method know 
	whether or not to print a separately-chained linked hash table
	with a linke list or a hash table based on an array (ex. linear 
	probing).
	*/
	if (useChaining) {
		NODE *node = new NODE();
		
		// print visual hash table of items from linked lists
		for (int i = 0; i < 10; i++) {
			std::cout << "[" << i << "]" << "-> ";
			
			for (node = tableHeads[i]; node != NULL; node = node->next) {
				std::cout << node->key << " -> ";
				delete node; // have to clean up nodes from memory
			}
			
			std::cout << "_\n";
		}
		
	}	
	else {
		// print visual hash table of items from array
		for (int i = 0; i < 10; i++) {
			std::cout << "[" << i << "]" << "   ";
	
			if (tableArray[i] != EMPTY) {
				std::cout << tableArray[i];
			}
		
			std::cout << "\n";
		}
	
		// print items that could not be inserted
		if (unhashable) {
			std::cout << "The following item(s) could not be inserted:  ";
	
			for (int i = 0; i < 10; i++) {
			
				if (unhashableList[i] != EMPTY) {
					std::cout << unhashableList[i] << " ";
				}
						
			}
		
			std::cout << "\n";
		}
	}
}