Advertisement
Guest User

Hash.h

a guest
Jun 18th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.24 KB | None | 0 0
  1.  
  2. /*Constructor*/
  3. template <class T>
  4. HashTable<T>::HashTable()
  5. {
  6.     srand(time(NULL));
  7.     keyGenerator = rand() % 3 + 1;
  8.     tableSize = 25;
  9.     table = new List<T>[tableSize]; //array of lists
  10.     size = 0;
  11.     listCount = 0;
  12. }
  13.  
  14. /*Setter*/
  15. template <class T>
  16. int HashTable<T>::setHashKey(T Data)
  17. {
  18.     int temp = Data.getEnemyID();
  19.     temp *= 2;
  20.     temp *= 5137;
  21.  
  22.     std::string tempS = to_string(temp);
  23.     std::string tempS2 = tempS;
  24.     if (tempS.length() > 2)
  25.     {
  26.         tempS[0] = tempS2[tempS2.length() - 1];
  27.         tempS[tempS.length() - 1] = tempS2[0];
  28.  
  29.         temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
  30.     }
  31.     else if (tempS.length() <= 2)
  32.     {
  33.         tempS += "000";
  34.         tempS[0] = tempS2[tempS2.length() - 1];
  35.         tempS[tempS.length() - 1] = tempS2[0];
  36.         temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
  37.     }
  38.     else
  39.         temp = temp % tableSize;
  40.     return temp;
  41. }
  42.  
  43. /*Setter*/
  44. template <class T>
  45. int HashTable<T>::setHashKey(int Data)
  46. {
  47.     int temp = Data;
  48.     temp *= 2;
  49.     temp *= 5137;
  50.  
  51.     std::string tempS = to_string(temp);
  52.     std::string tempS2 = tempS;
  53.     if (tempS.length() > 2)
  54.     {
  55.         tempS[0] = tempS2[tempS2.length() - 1];
  56.         tempS[tempS.length() - 1] = tempS2[0];
  57.  
  58.         temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
  59.     }
  60.     else if (tempS.length() <= 2)
  61.     {
  62.         tempS += "000";
  63.         tempS[0] = tempS2[tempS2.length() - 1];
  64.         tempS[tempS.length() - 1] = tempS2[0];
  65.         temp = (std::stoi(tempS) + std::stoi(tempS2)) % tableSize;
  66.     }
  67.     else
  68.         temp = temp % tableSize;
  69.     return temp;
  70. }
  71.  
  72. /*Adds new data to hash table
  73.     Pre: - generic type value data
  74.     Post: - new value is inserted into hash table*/
  75. template <class T>
  76. void HashTable<T>::insertData(T Data)
  77. {
  78.     int key = setHashKey(Data);
  79.     Node<T> *temp = new Node<T>;
  80.     temp->setData(Data);
  81.     table[key].sortInsert(temp);
  82.     size++;
  83. }
  84.  
  85. /*Removes existing data from hash table
  86.     Pre: - generic type value data
  87.     Post: - removes user defined value from hash table*/
  88. template <class T>
  89. void HashTable<T>::removeData(T Data)
  90. {
  91.     int key = setHashKey(Data);
  92.     int exists = table[key].findAny(Data);
  93.     if (exists != -1)
  94.     {
  95.         table[key].deleteAny(exists);
  96.         size--;
  97.     }
  98.     else
  99.         std::cout << "Data does not exists in hash.\n";
  100. }
  101.  
  102. /*Retrieves value corresponding to hash key from table
  103.     Pre: - integer hash key
  104.     Post: - locates value related to hash key
  105.     Return: - Generic data type value corresponding to hash key*/
  106. template <class T>
  107. T HashTable<T>::fetchData(int hkey) //general fetch
  108. {
  109.     int key = setHashKey(hkey);
  110.     T hashData;
  111.     int count = table[key].getCount();
  112.     if (table[key].getFirst() == NULL) //if the list is empty
  113.     {
  114.         std::cout << "No Data exists returning default value.";
  115.     }
  116.     else
  117.     {
  118.         int pos = 1;
  119.         hashData = table[key].getData(pos);
  120.         while (hashData.getEnemyID() != hkey && pos <= table[key].getCount())
  121.         {
  122.             hashData = table[key].getData(pos);
  123.             pos++;
  124.         }
  125.     }
  126.     return hashData;
  127. }
  128.  
  129. /*Retrieves value corresponding to user defined value from table
  130.     Pre: - Generic data type data
  131.     Post: - locates value matching Data
  132.     Return: - Generic data type value matching user defined Data value*/
  133. template <class T>
  134. T HashTable<T>::fetchData(T Data)
  135. {
  136.     int exists = -1;
  137.     for (int i = 0; i < tableSize; i++)
  138.     {
  139.         for (int j = 0; j < table[i].getCount(); j++)
  140.         {
  141.             exists = table[i].findAny(Data);
  142.             if (exists != -1)
  143.             {
  144.                 Data = table[i].getData(exists);
  145.                     break;
  146.             }
  147.         }
  148.         if (exists != -1)
  149.             break;
  150.     }
  151.     return Data;
  152. }
  153.  
  154. /*Retrieves value corresponding to hash key and position within list from table
  155.     Pre: - integer hash key
  156.          - integer position within list
  157.     Post: located value corresponding to hash key and position within list
  158.     Return: - Generic data type value from table*/
  159. template <class T>
  160. T HashTable<T>::fetchData(int hkey, int pos) //fetch for finding a specific item in the list
  161. {
  162.     int key = setHashKey(hkey);
  163.     T hashData;
  164.     int count = table[key].getCount();
  165.     if (pos > table[key].getCount()) //if the position exceeds the list size /possibly redundant in this context
  166.         pos = rand() % count + 1; //return a random value from the list
  167.     if (table[key].getFirst() == NULL) //if the list is empty
  168.     {
  169.         std::cout << "No Data exists returning default value.";
  170.     }
  171.     else
  172.         hashData = table[key].getData(pos);
  173.     return hashData;
  174. }
  175.  
  176. /*Displays the hash table values in key sequence
  177.     Pre: void
  178.     Post: void*/
  179. template <class T>
  180. void HashTable<T>::OutputKeySequence()
  181. {
  182.     std::cout << "____________________________________________________________________\n";
  183.     for (int i = 0; i < tableSize; i++)
  184.     {
  185.         std::cout << "Key Location " << i << ": " << std::endl;
  186.         if (table[i].getFirst() != NULL)
  187.             table[i].printNumList();
  188.         std::cout << std::endl;
  189.     }
  190.     std::cout << "____________________________________________________________________\n";
  191. }
  192.  
  193. /*Displays the hash table values in inorder sequence
  194.     Pre: void
  195.     Post: void*/
  196. template <class T>
  197. 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;
  198. {
  199.     List<T> *collisionList = new List<T>;
  200.     std::cout << "____________________________________________________________________\n";
  201.     std::cout << "Sorted by Enemy ID: \n";
  202.     for (int i = 0; i < tableSize; i++) //5 because 4 is max enemy difficulty so far
  203.     {
  204.         if (table[i].getCount() > 0)
  205.         {
  206.             for (int j = 1; j <= table[i].getCount(); j++) //stores all data sorted into a new list
  207.             {
  208.                 Node<T> *temp = new Node<T>;
  209.                 temp->setData(table[i].getData(j));
  210.                 collisionList->sortInsert(temp);
  211.             }
  212.         }
  213.     }
  214.     collisionList->printList();
  215.     delete collisionList;
  216.     std::cout << "____________________________________________________________________\n";
  217. }
  218.  
  219.  
  220. /*Getter*/
  221. template <class T>
  222. int HashTable<T>::getLargestList()
  223. {
  224.     int high = 0, cur = 0;
  225.     for (int i = 0; i < tableSize; i++)
  226.     {
  227.  
  228.         cur = getCurrentListSize(i);
  229.         if (cur > high)
  230.             high = cur;
  231.     }
  232.     return high;
  233. }
  234.  
  235. /*Setter*/
  236. template <class T>
  237. void HashTable<T>::setListCount()
  238. {
  239.     listCount = 0;
  240.     for (int i = 0; i < tableSize; i++)
  241.     {
  242.         if (table[i].getCount() > 0)
  243.             listCount++; //how many lists are actually in use in this table.
  244.     }
  245. }
  246.  
  247. //works mainly with pointer data bucket version
  248. /*template <class T>
  249. class HashTable
  250. {
  251. int bucketCount;
  252. int bucketSize;
  253. int tableSize;
  254. int tableMAx;
  255. int keyGenerator;
  256. T ***table;
  257. int setHashKey(T Data);
  258. int setHashKey(int Data);
  259. public:
  260. HashTable();
  261. ~HashTable() { clearTable(); }
  262. int getTableSize() { return tableSize; }
  263. void clearTable();
  264. void insertData(T *Data);
  265. T *fetchData(int hkey);
  266. T *GamefetchData(int hkey, int pos);
  267. void deleteData(T *Data);
  268. void collisionResolution(T *Data, int key);
  269. };
  270. template <class T>
  271. HashTable<T>::HashTable()
  272. {
  273. bucketCount = 10;
  274. bucketSize = 5;
  275. tableMAx = bucketCount * bucketSize;
  276. table = new T**[bucketCount];
  277. for (int i = 0; i < bucketCount; i++)
  278. {
  279. table[i] = new T*[bucketSize];
  280. for (int j = 0; j < bucketSize; j++)
  281. {
  282. table[i][j] = nullptr;
  283. }
  284. }
  285. srand(time(NULL));
  286. keyGenerator = rand() % 3 + 1;
  287. tableSize = 0;
  288. }
  289. template <class T>
  290. int HashTable<T>::setHashKey(T Data)
  291. {
  292. return (Data * keyGenerator) % 10;// needs to be changed
  293. }
  294. template <class T>
  295. int HashTable<T>::setHashKey(int Data)
  296. {
  297. return (Data * keyGenerator) % 10;
  298. }
  299. template <class T>
  300. void HashTable<T>::insertData(T *Data)
  301. {
  302. int key = setHashKey(*Data);
  303. for (int i = 0; i < bucketCount; i++)//there are no catches of inserting the same data twice
  304. {
  305. if (table[key][i] == NULL)
  306. {
  307. table[key][i] = Data;
  308. break;
  309. }
  310. else if (i == 4) //if we reached the end of this bucket, spill over into the spare
  311. {
  312. collisionResolution(Data, key + 1);
  313. }
  314. tableSize++;
  315. }
  316. }
  317. template <class T>
  318. void HashTable<T>::collisionResolution(T *Data, int key)
  319. {
  320. for (int j = 0; j < bucketCount; j++) //there are no catches of inserting the same data twice
  321. {
  322. if (table[key][j] == NULL)
  323. {
  324. table[key][j] = Data;
  325. break;
  326. }
  327. else if (j == 4)
  328. std::cout << "Both buckets of this type filled.\n"; //can add more collision resolution here
  329. }
  330. }
  331. template <class T>
  332. void HashTable<T>::deleteData(T *Data)
  333. {
  334. int key = setHashKey(*Data);
  335. int index = 0;
  336. T* hashData = new T;
  337. bool isFound = false;
  338. while (index < bucketCount && isFound == false)
  339. {
  340. hashData = table[key][index];
  341. if (*hashData == *Data)
  342. {
  343. isFound = true;
  344. index--; //offset the i++
  345. }
  346. index++;
  347. }
  348. delete table[key][index];
  349. table[key][index] = nullptr;
  350. }
  351. template <class T>
  352. T* HashTable<T>::fetchData(int hkey) //for fetchiung specific data from hash //will fetch the first data in the bucket.
  353. {
  354. int key = setHashKey(hkey);
  355. T* hashData = new T;
  356. hashData = table[key][0];
  357. return hashData;
  358. }
  359. template <class T>
  360. T* HashTable<T>::GamefetchData(int hkey, int pos) //unique function for Game, random position check //where pos is a value between 0 and bucketmax
  361. {
  362. int key = setHashKey(hkey);
  363. T* hashData = new T;
  364. if (pos >= bucketSize) //check for if outofbounds
  365. pos = 0;
  366. hashData = table[key][pos];
  367. pos = 0;
  368. while(hashData == NULL && pos < bucketCount) //if hash has no data in it.
  369. {
  370. hashData = table[key][pos];
  371. pos++;
  372. }
  373. return hashData;
  374. }
  375. template <class T>
  376. void HashTable<T>::clearTable()
  377. {
  378. for (int i = 0; i < bucketCount; i++)
  379. {
  380. for (int j = 0; j < bucketSize; j++)
  381. {
  382. delete table[i][j];
  383. table[i][j] = nullptr;
  384. }
  385. }
  386. }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement