1 files changed, 267 insertions, 0 deletions
diff --git a/Assign5/table.cpp b/Assign5/table.cpp
new file mode 100644
index 0000000..33a44de
--- /dev/null
+++ b/Assign5/table.cpp
@@ -0,0 +1,267 @@
+#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";
+		}
+	}
+}