ASU CSE310 Assignment #5 Spring 2023

// ASU CSE310 Assignment #5 Spring 2023 // Name of Author: // ASU ID: // Description: this is the main program that reads input from a text file, // it then call hash functions to execute hash commands given in the input. // —- is where you need to add your own code /***************************************************************************** //(1)Describe here what is your hash function? How do you get an input Employee // object's hash value. //(2)Did your hash function work well? For each of the four test cases, list here // your hash function's performance ratio and the longest LinkedList size. //(3)If you had to change your hash function to reduce the number of collisions, // how will you change it? ****************************************************************************** **/ #include "Hash.h" #include <sstream> using namespace std; //This function used to get an Employee key which is the combination of firstName, lastName and id void getKey(string oneLine, string&firstName, string& lastName, int& id); int main() { int size = 0 ; int numOfCommand = 0; string firstName, lastName; int id; double salary; //declare any other necessary variables here //—- cout << "Enter the size of the hash table: "; cin >> size; cin.ignore(20, 'n'); //Instantiate the hash table with the relevant number of slots //—-

do { //use this do..while loop to repeatly get one line Employee info. and extract tokens //create one Employee object and insert it inside the hashTable until seeing the message //"InsertionEnd", then terminate //—- //—- } while(true); cout << "nEnter number of commands: "; //***need to comment out in submitting cin >> numOfCommand; cin.ignore(20, 'n'); for(int i= 0; i < numOfCommand; i++) { //get one line command, extract the first token, if only one token if(firstToken.compare("hashDisplay") == 0) { //—- //—- } else //more than one tokens, check the command name, extract the remaining tokens { //—- //—- if(command.compare("hashSearch")==0) //—- //—- else if(command.compare("hashDelete")==0) //—- //—- else if(command.compare("hashLoadFactor")==0) //—- //—- else cout<<"Invalid command"<<endl; } } //end for loop return 0; } //**************************************************************************** ************ //Given one line, this function extracts firstName, lastName, id info. of an Employee

//This function is completed and given here as a study guide for extracting tokens void getKey(string oneLine, string& firstName, string& lastName, int& id) { string delimiter = ","; int pos=oneLine.find(delimiter); string token = oneLine.substr(0,pos); string command = token; oneLine.erase(0, pos+delimiter.length()); pos=oneLine.find(delimiter); token = oneLine.substr(0,pos); firstName = token; oneLine.erase(0, pos+delimiter.length()); pos=oneLine.find(delimiter); token = oneLine.substr(0,pos); lastName = token; oneLine.erase(0, pos+delimiter.length()); pos=oneLine.find(delimiter); token = oneLine.substr(0,pos); id = stoi(token); oneLine.erase(0, pos+delimiter.length()); }

// ASU CSE310 Assignment #5 Spring 2023 // Name of Author: // ASU ID: // Description: A simple linked list that implements a list of Employee objects. A user can // perform searching, insertion or deletion on the linked list. // //—- is where you should add your own code #include <iostream> #include <iomanip> #include <string> using namespace std; struct Employee { string firstName, lastName; int id; double salary; struct Employee* next; }; class LinkedList { private: struct Employee* head; int size; //a variable represents number of Employees inside the list public: LinkedList(); ~LinkedList(); Employee* getHead(); int getSize(); bool searchEmployee(int id); bool insertEmployee(string firstName, string lastName, int id, double salary); bool deleteEmployee(int id); void displayList(); };

//Constructor LinkedList::LinkedList() { head = NULL; //initialising it to null size = 0; } //Destructor LinkedList::~LinkedList() { Employee* current = head; while (current != nullptr) { Employee* next = current->next; delete current; current = next; } } Employee* LinkedList::getHead() { return head; } //Return number of Employees inside the Linked list int LinkedList::getSize() { Employee* temp = head;

int size = 0; while(temp != nullptr) { size ++; temp = temp->next; } return size; } //This function does a linear search on the Employee list with the given Employee id //it returns true if the corresponding Employee is found, otherwise it returns false. bool LinkedList::searchEmployee(int id) { Employee* curr = head; while(curr!= NULL) { if(curr->id == id) { return true; } else { curr = curr->next; } } return false;

} //Insert the parameter Employee at the head of the linked list. //return true if it is inserted successfully and false otherwise bool LinkedList::insertEmployee(string firstName, string lastName, int id, double salary) { Employee* newEmp = new Employee; //creating new Employee newEmp -> firstName = firstName; newEmp -> lastName = lastName; newEmp -> id = id; newEmp -> salary = salary; newEmp -> next = nullptr; if(head == nullptr) { head = newEmp; } else { newEmp -> next = head; head = newEmp; } size ++; return true; } //Delete the Employee with the given id from the linked list. //Return true if it is deleted successfully and false otherwise bool LinkedList::deleteEmployee(int id)

{ if(head == NULL) { return false; } if(head->id == id)//to delete the head where the head is the employee to be deleted { Employee* temp = head; head = head->next; delete temp; size–; return true; } Employee* curr = head; while((curr->next != nullptr) && (curr->next->id != id)) { curr = curr->next; } if(curr->next == NULL) { return false; } Employee* temp = curr->next; curr->next = temp->next;

delete temp; size–; return true; } //This function displays the content of the linked list. void LinkedList::displayList() { struct Employee *temp = head; if(head == NULL) { //empty linked list, print nothing here } else { while(temp != NULL) { cout << left << setw(18) << temp->firstName << left << setw(18) << temp->lastName << right << setw(8) << temp->id << setw(10) << fixed << setprecision(2) << temp->salary << "n"; temp = temp->next; } } }

// ASU CSE310 Assignment #5 Spring 2023 // Name of Author: // ASU ID: // Description: this is where you need to design functions on Hash hashTable, // such as hashInsert, hashDelete, hashSearch and hashDisplay // —- is where you should add your own code #include "LinkedList.h" using namespace std; class Hash { private: LinkedList* hashTable; //hashTable is a one-dimensional array of LinkedList int m; //slots number of the hash table int tableSize; public: Hash(int size); ~Hash(); bool hashSearch(string firstName, string lastName, int id); bool hashInsert(string firstName, string lastName, int id, double salary); bool hashDelete(string firstName, string lastName, int id); int hashLoadFactor(); void hashDisplay(); int hashFunction(string key); }; //constructor Hash::Hash(int size) { m = size; hashTable = new LinkedList[m]; } //Destructor Hash::~Hash() { delete[] hashTable; }

//This function searches for a key inside the hash table and //return true if it is found and false otherwise //Note: key is the combination of firstName, lastName and id bool Hash::hashSearch(string firstName, string lastName, int id) { bool found = false; int hash_ind = hashFunction(firstName+lastName+to_string(id)) LinkedList* emp1 = hashTable[hash_ind].searchEmployee(id); if(emp1!=NULL && emp1->getFirstName() == firstName && emp1->getLastName()== lastName) { if (found == true) { cout << "n" << left << setw(18) << firstName << setw(18) << lastName << setw(8) << id << " is found inside the hash table." << endl; } else { cout << "n" << left << setw(18) << firstName << setw(18) << lastName << setw(8) << id << " is NOT found inside the hash table." << endl; } return found; } } //hashInsert inserts an Employee with the relevant info. into the hashTable. //it returns true if the data is inserted successfully and false otherwise bool Hash::hashInsert(string firstName, string lastName, int id, double salary) {

int hash_ind = hashFunction(firstName+lastName+to_string(id)); bool ins = hashTable[hash_ind].insertEmployee(firstName, lastName, id, salary); if(ins == true) { tableSize++; return true; } else { return false; } //—- //—- } //hashDelete deletes an Employee with the relevant key from the hashTable. //it returns true if it is deleted successfully and false otherwise //Note: key is the combination of firstName, lastName and id bool Hash::hashDelete(string firstName, string lastName, int id) { int hash_ind = hashFunction(firstName+lastName+to_string(id)); bool remove = hashTable[hash_ind].deleteEmployee(id); if(remove == true) { //—- //—- cout << "n"; cout << setw(18) << firstName << setw(18) << lastName << setw(8) << id << " is deleted from hash table." << endl; } else { cout << "n";

cout << setw(18) << firstName << setw(18) << lastName << setw(8) << id << " is NOT deleted from hash table." << endl; } //—- //—- //—- //—- return remove; } //This function computes your hash table real load factor //it is the longest linked list size int Hash::hashLoadFactor() { //—- //—- } //This function prints all elements from the hashTable. void Hash::hashDisplay() { int i = 0; for(i=0; i<tableSize; i++) { cout << "HashTable[" << i << "], size = " << linkedListSize[i] << endl; if(LinkedListSize[i] == 0) { continue; } Employee* temp1 = hashTable[i]; do { cout << temp1->firstName << "t" << temp1->lastName << "t" << temp1->id << "t" << temp1->salary << endl;

temp1 = temp1->next; } while (temp1 != NULL); cout << endl; } //—- //—- } //This is the hash function you need to design. Given a //string key, the function should return the slot number //where we should hash the key to int Hash::hashFunction(string key) { int hash = 0; int ind; int i = 0; for(i=0; i< key.length(); i++) { hash = hash + (int) key[i]; } ind = hash % tableSize; return ind; //—- //—- }