Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*Constructor*/
- template <class T>
- HashTable<T>::HashTable()
- {
- srand(time(NULL));
- keyGenerator = rand() % 3 + 1;
- tableSize = 25;
- table = new List<T>[tableSize]; //array of lists
- size = 0;
- listCount = 0;
- }
- /*Setter*/
- template <class T>
- int HashTable<T>::setHashKey(T Data)
- {
- int temp = Data.getEnemyID();
- temp *= 2;
- temp *= 5137;
- std::string tempS = to_string(temp);
- std::string tempS2 = tempS;
- if (tempS.length() > 2)
- {
- tempS[0] = tempS2[tempS2.length() - 1];
- tempS[tempS.length() - 1] = tempS2[0];
- temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
- }
- else if (tempS.length() <= 2)
- {
- tempS += "000";
- tempS[0] = tempS2[tempS2.length() - 1];
- tempS[tempS.length() - 1] = tempS2[0];
- temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
- }
- else
- temp = temp % tableSize;
- return temp;
- }
- /*Setter*/
- template <class T>
- int HashTable<T>::setHashKey(int Data)
- {
- int temp = Data;
- temp *= 2;
- temp *= 5137;
- std::string tempS = to_string(temp);
- std::string tempS2 = tempS;
- if (tempS.length() > 2)
- {
- tempS[0] = tempS2[tempS2.length() - 1];
- tempS[tempS.length() - 1] = tempS2[0];
- temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
- }
- else if (tempS.length() <= 2)
- {
- tempS += "000";
- tempS[0] = tempS2[tempS2.length() - 1];
- tempS[tempS.length() - 1] = tempS2[0];
- temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
- }
- else
- temp = temp % tableSize;
- return temp;
- }
- /*Adds new data to hash table
- Pre: - generic type value data
- Post: - new value is inserted into hash table*/
- template <class T>
- void HashTable<T>::insertData(T Data)
- {
- int key = setHashKey(Data);
- Node<T> *temp = new Node<T>;
- temp->setData(Data);
- table[key].sortInsert(temp);
- size++;
- }
- /*Removes existing data from hash table
- Pre: - generic type value data
- Post: - removes user defined value from hash table*/
- template <class T>
- void HashTable<T>::removeData(T Data)
- {
- int key = setHashKey(Data);
- int exists = table[key].findAny(Data);
- if (exists != -1)
- {
- table[key].deleteAny(exists);
- size--;
- }
- else
- std::cout << "Data does not exists in hash.\n";
- }
- /*Retrieves value corresponding to hash key from table
- Pre: - integer hash key
- Post: - locates value related to hash key
- Return: - Generic data type value corresponding to hash key*/
- template <class T>
- T HashTable<T>::fetchData(int hkey) //general fetch
- {
- int key = setHashKey(hkey);
- T hashData;
- int count = table[key].getCount();
- if (table[key].getFirst() == NULL) //if the list is empty
- {
- std::cout << "No Data exists returning default value.";
- }
- else
- {
- int pos = 1;
- hashData = table[key].getData(pos);
- while (hashData.getEnemyID() != hkey && pos <= table[key].getCount())
- {
- hashData = table[key].getData(pos);
- pos++;
- }
- }
- return hashData;
- }
- /*Retrieves value corresponding to user defined value from table
- Pre: - Generic data type data
- Post: - locates value matching Data
- Return: - Generic data type value matching user defined Data value*/
- template <class T>
- T HashTable<T>::fetchData(T Data)
- {
- int exists = -1;
- for (int i = 0; i < tableSize; i++)
- {
- for (int j = 0; j < table[i].getCount(); j++)
- {
- exists = table[i].findAny(Data);
- if (exists != -1)
- {
- Data = table[i].getData(exists);
- break;
- }
- }
- if (exists != -1)
- break;
- }
- return Data;
- }
- /*Retrieves value corresponding to hash key and position within list from table
- Pre: - integer hash key
- - integer position within list
- Post: located value corresponding to hash key and position within list
- Return: - Generic data type value from table*/
- template <class T>
- T HashTable<T>::fetchData(int hkey, int pos) //fetch for finding a specific item in the list
- {
- int key = setHashKey(hkey);
- T hashData;
- int count = table[key].getCount();
- if (pos > table[key].getCount()) //if the position exceeds the list size /possibly redundant in this context
- pos = rand() % count + 1; //return a random value from the list
- if (table[key].getFirst() == NULL) //if the list is empty
- {
- std::cout << "No Data exists returning default value.";
- }
- else
- hashData = table[key].getData(pos);
- return hashData;
- }
- /*Displays the hash table values in key sequence
- Pre: void
- Post: void*/
- template <class T>
- void HashTable<T>::OutputKeySequence()
- {
- std::cout << "____________________________________________________________________\n";
- for (int i = 0; i < tableSize; i++)
- {
- std::cout << "Key Location " << i << ": " << std::endl;
- if (table[i].getFirst() != NULL)
- table[i].printNumList();
- std::cout << std::endl;
- }
- std::cout << "____________________________________________________________________\n";
- }
- /*Displays the hash table values in inorder sequence
- Pre: void
- Post: void*/
- template <class T>
- void HashTable<T>::OutputInorder() //works specifically for game //DOES NOT ACCOUNT FOR THE ITEMS IN INDEX 0 CAUSE THAT IS THE BOSS INDEX //WORKS UNDER THE LOGIC THAT ALL NEW IDS ARE GREATER THAN THE OG 25;
- {
- List<T> *collisionList = new List<T>;
- std::cout << "____________________________________________________________________\n";
- std::cout << "Sorted by Enemy ID: \n";
- for (int i = 0; i < tableSize; i++) //5 because 4 is max enemy difficulty so far
- {
- if (table[i].getCount() > 0)
- {
- for (int j = 1; j <= table[i].getCount(); j++) //stores all data sorted into a new list
- {
- Node<T> *temp = new Node<T>;
- temp->setData(table[i].getData(j));
- collisionList->sortInsert(temp);
- }
- }
- }
- collisionList->printList();
- delete collisionList;
- std::cout << "____________________________________________________________________\n";
- }
- /*Getter*/
- template <class T>
- int HashTable<T>::getLargestList()
- {
- int high = 0, cur = 0;
- for (int i = 0; i < tableSize; i++)
- {
- cur = getCurrentListSize(i);
- if (cur > high)
- high = cur;
- }
- return high;
- }
- /*Setter*/
- template <class T>
- void HashTable<T>::setListCount()
- {
- listCount = 0;
- for (int i = 0; i < tableSize; i++)
- {
- if (table[i].getCount() > 0)
- listCount++; //how many lists are actually in use in this table.
- }
- }
- //works mainly with pointer data bucket version
- /*template <class T>
- class HashTable
- {
- int bucketCount;
- int bucketSize;
- int tableSize;
- int tableMAx;
- int keyGenerator;
- T ***table;
- int setHashKey(T Data);
- int setHashKey(int Data);
- public:
- HashTable();
- ~HashTable() { clearTable(); }
- int getTableSize() { return tableSize; }
- void clearTable();
- void insertData(T *Data);
- T *fetchData(int hkey);
- T *GamefetchData(int hkey, int pos);
- void deleteData(T *Data);
- void collisionResolution(T *Data, int key);
- };
- template <class T>
- HashTable<T>::HashTable()
- {
- bucketCount = 10;
- bucketSize = 5;
- tableMAx = bucketCount * bucketSize;
- table = new T**[bucketCount];
- for (int i = 0; i < bucketCount; i++)
- {
- table[i] = new T*[bucketSize];
- for (int j = 0; j < bucketSize; j++)
- {
- table[i][j] = nullptr;
- }
- }
- srand(time(NULL));
- keyGenerator = rand() % 3 + 1;
- tableSize = 0;
- }
- template <class T>
- int HashTable<T>::setHashKey(T Data)
- {
- return (Data * keyGenerator) % 10;// needs to be changed
- }
- template <class T>
- int HashTable<T>::setHashKey(int Data)
- {
- return (Data * keyGenerator) % 10;
- }
- template <class T>
- void HashTable<T>::insertData(T *Data)
- {
- int key = setHashKey(*Data);
- for (int i = 0; i < bucketCount; i++)//there are no catches of inserting the same data twice
- {
- if (table[key][i] == NULL)
- {
- table[key][i] = Data;
- break;
- }
- else if (i == 4) //if we reached the end of this bucket, spill over into the spare
- {
- collisionResolution(Data, key + 1);
- }
- tableSize++;
- }
- }
- template <class T>
- void HashTable<T>::collisionResolution(T *Data, int key)
- {
- for (int j = 0; j < bucketCount; j++) //there are no catches of inserting the same data twice
- {
- if (table[key][j] == NULL)
- {
- table[key][j] = Data;
- break;
- }
- else if (j == 4)
- std::cout << "Both buckets of this type filled.\n"; //can add more collision resolution here
- }
- }
- template <class T>
- void HashTable<T>::deleteData(T *Data)
- {
- int key = setHashKey(*Data);
- int index = 0;
- T* hashData = new T;
- bool isFound = false;
- while (index < bucketCount && isFound == false)
- {
- hashData = table[key][index];
- if (*hashData == *Data)
- {
- isFound = true;
- index--; //offset the i++
- }
- index++;
- }
- delete table[key][index];
- table[key][index] = nullptr;
- }
- template <class T>
- T* HashTable<T>::fetchData(int hkey) //for fetchiung specific data from hash //will fetch the first data in the bucket.
- {
- int key = setHashKey(hkey);
- T* hashData = new T;
- hashData = table[key][0];
- return hashData;
- }
- template <class T>
- T* HashTable<T>::GamefetchData(int hkey, int pos) //unique function for Game, random position check //where pos is a value between 0 and bucketmax
- {
- int key = setHashKey(hkey);
- T* hashData = new T;
- if (pos >= bucketSize) //check for if outofbounds
- pos = 0;
- hashData = table[key][pos];
- pos = 0;
- while(hashData == NULL && pos < bucketCount) //if hash has no data in it.
- {
- hashData = table[key][pos];
- pos++;
- }
- return hashData;
- }
- template <class T>
- void HashTable<T>::clearTable()
- {
- for (int i = 0; i < bucketCount; i++)
- {
- for (int j = 0; j < bucketSize; j++)
- {
- delete table[i][j];
- table[i][j] = nullptr;
- }
- }
- }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement