fueanta

HashTable :: Hash.cpp

May 17th, 2017
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // Created by Taqui on 5/13/2017.
  3. //
  4.  
  5. #include <iostream>
  6.  
  7. #define PI 3.14159265359
  8.  
  9. #include "Hash.h"
  10.  
  11. using namespace std;
  12.  
  13. Hash::Hash()
  14. {
  15.     for (int i = 0; i < SIZE; i++)
  16.     {
  17.         hashArray[i] = NULL;
  18.     }
  19. }
  20.  
  21. int Hash::hashFunction(string key)
  22. {
  23.     int hashIndex = 0;
  24.     double sum = 0;
  25.     for (int i = 0; i < key.length(); i++)
  26.     {
  27.         sum = (sum * PI) + (int) key[i];
  28.     }
  29.     hashIndex = (int) sum % SIZE;
  30.     return hashIndex;
  31. }
  32.  
  33. void Hash::addItem(string name, string phoneNumber)
  34. {
  35.     int hashIndex = hashFunction(name);
  36.     Item *newItem = new Item(name, phoneNumber);
  37.     newItem->next = hashArray[hashIndex];
  38.     hashArray[hashIndex] = newItem;
  39. }
  40.  
  41. void Hash::showBucket(int index)
  42. {
  43.     if (hashArray[index] != NULL)
  44.     {
  45.         cout << "\n---------BEGINNING OF THE BUCKET---------" << endl;
  46.         for(Item *curr = hashArray[index]; curr != NULL; curr = curr->next)
  47.         {
  48.             cout << endl;
  49.             curr->show();
  50.         }
  51.         cout << "\n------------END OF THE BUCKET------------" << endl;
  52.     }
  53.     else
  54.     {
  55.         cout << "\nBucket is empty." << endl;
  56.     }
  57. }
  58.  
  59. void Hash::showBucketFromKey(string key)
  60. {
  61.     int hashIndex = hashFunction(key);
  62.     Item *item = searchItem(key);
  63.    
  64.     if (item == NULL)
  65.     {
  66.         cout << "\nInvalid Key : Item could not be found." << endl;
  67.     }
  68.     else
  69.     {
  70.         showBucket(hashIndex);
  71.     }
  72. }
  73.  
  74. void Hash::showHashTable()
  75. {
  76.     cout << "\n--------------------Hash Table Entries--------------------" << endl;
  77.     for (int i = 0; i < Hash::SIZE; i++)
  78.     {
  79.         showBucket(i);
  80.     }
  81.     cout << "\n--------------------END OF THE TABLE--------------------" << endl;
  82. }
  83.  
  84. Item* Hash::searchItem(string key)
  85. {
  86.     cout << "\n------------Searching For "<< key <<"------------" << endl;
  87.     int hashIndex = hashFunction(key);
  88.     Item *bucketPtr = NULL;
  89.     for (bucketPtr = hashArray[hashIndex]; bucketPtr != NULL; bucketPtr = bucketPtr->next)
  90.     {
  91.         if (bucketPtr->getName() == key)
  92.         {
  93.             cout << "Item " << key << " has been found at Index no: " << hashIndex << endl;
  94.             /*cout << "\n#ITEM DETAILS :" << endl;
  95.             bucketPtr->show();*/
  96.             break;
  97.         }
  98.     }
  99.     if (bucketPtr == NULL)
  100.     {
  101.         cout << "Item " << key << " could not be found in the Hash Table." << endl;
  102.     }
  103.     return bucketPtr;
  104. }
  105.  
  106. void Hash::deleteItem(string key)
  107. {
  108.     int hashIndex = hashFunction(key);
  109.     Item *bucketPtr = hashArray[hashIndex];
  110.  
  111.     if (bucketPtr == NULL)
  112.     {
  113.         cout << "\nItem " << key << " could not be found to delete. In fact the bucket corresponding to the KEY: " << key <<" is empty." << endl;
  114.         return;
  115.     }
  116.  
  117.     else
  118.     {
  119.         if (bucketPtr->getName() == key)
  120.         {
  121.             hashArray[hashIndex] = bucketPtr->next;
  122.             delete bucketPtr;
  123.             cout << "\nItem " << key << " has been deleted." << endl;
  124.         }
  125.         else if (bucketPtr->next != NULL)
  126.         {
  127.             while(bucketPtr->next != NULL)
  128.             {
  129.                 if (bucketPtr->next->getName() == key)
  130.                 {
  131.                     break;
  132.                 }
  133.                 bucketPtr = bucketPtr->next;
  134.             }
  135.             if (bucketPtr->next == NULL)
  136.             {
  137.                 cout << "\nItem " << key << " could not be found to delete." << endl;
  138.             }
  139.             else
  140.             {
  141.                 Item *deletePtr = bucketPtr->next;
  142.                 bucketPtr->next = deletePtr->next;
  143.                 delete deletePtr;
  144.                 cout << "\nItem " << key << " has been deleted." << endl;
  145.             }
  146.         }
  147.         else
  148.         {
  149.             cout << "\nThere is only one item in this bucket( no: " << hashIndex << " ) and this item does not posses the same key as given( Key: " << key << " ). So, Item could not be found to delete." << endl;
  150.         }
  151.     }
  152. }
RAW Paste Data