Advertisement
snowywhitee

Untitled

Nov 22nd, 2019
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <stdlib.h>
  4. #include <vector>
  5. #include <utility>
  6. using namespace std;
  7.  
  8. struct node {
  9.     string key;
  10.     string data;
  11.     node *next;
  12. };
  13.  
  14. int hashfunc(string s)
  15. {
  16.     const int p = 31;
  17.     const int m = 1e9 + 9;
  18.     long long hash_value = 0;
  19.     long long p_pow = 1;
  20.     for (int i = 0; i < s.length();i++ ) {
  21.         hash_value = (hash_value + (s[i] - 'a' + 1) * p_pow) % m;
  22.         p_pow = (p_pow * p) % m;
  23.     }
  24.     hash_value = hash_value % 1000000;
  25.     return hash_value;
  26. }
  27.  
  28. bool key_inchain(vector < node > &arr, string k)
  29. {
  30.     int x = hashfunc(k);
  31.    
  32.     if (arr[x].key == k) //if key is in data
  33.     {
  34.         return true;
  35.     } else if (arr[x].key != k && arr[x].next == NULL) //if key not in data & no chain
  36.     {
  37.         return false;
  38.     } else { //key not in data, chain
  39.         node *cur = arr[x].next;
  40.         while (cur->next != NULL)
  41.         {
  42.             if (cur->key == k)
  43.             {
  44.                 return true;
  45.             }
  46.             cur = cur->next;
  47.         }
  48.         if (cur->key == k)
  49.         {
  50.             return true;
  51.         }
  52.     }
  53.     return false;
  54. }
  55.  
  56. string key_val(vector < node > &arr, string k)
  57. {
  58.     int x = hashfunc(k);
  59.    
  60.     if (arr[x].key == k) //if key in data
  61.     {
  62.         return arr[x].data;
  63.     } else { //key not in data
  64.         if ( arr[x].next == NULL) //no chain
  65.         {
  66.             return "none";
  67.         }
  68.         node *cur = arr[x].next;
  69.         while (cur->next != NULL)
  70.         {
  71.             if (cur->key == k)
  72.             {
  73.                 return cur->data;
  74.             }
  75.             cur = cur->next;
  76.         }
  77.         if (cur->key == k)
  78.         {
  79.             return cur->data;
  80.         }
  81.     }
  82.     return "none";
  83. }
  84.  
  85. void add(vector < node > &arr, string k, string y)
  86. {
  87.     int x = hashfunc(k);
  88.  
  89.     if (arr[x].data != "") //hash taken
  90.     {
  91.         if(arr[x].key == k) //key is in data
  92.         {
  93.             arr[x].data = y;
  94.         } else if (key_inchain(arr, k)) //key is in chain
  95.         {
  96.             node *cur = arr[x].next;
  97.             if (cur->key == k)
  98.             {
  99.                 cur->data = y;
  100.             } else {
  101.                 while (cur->next != NULL)
  102.                 {
  103.                     if (cur->key == k)
  104.                     {
  105.                         cur->data = y;
  106.                     }
  107.                 }
  108.                 if (cur->key == k)
  109.                 {
  110.                     cur->data = y;
  111.                 }
  112.             }
  113.         } else { //no such key, not in data, not in chain
  114.             if (arr[x].next == NULL) //if no chain
  115.             {
  116.                 node *q;
  117.                 q = new node();
  118.                 q->key = k;
  119.                 q->data = y;
  120.             } else {
  121.                 node *cur = arr[x].next;
  122.                 while (cur->next != NULL)
  123.                 {
  124.                     cur = cur->next;
  125.                 }
  126.                 node *q;
  127.                 q = new node();
  128.                 q->key = k;
  129.                 q->data = y;
  130.                 cur->next = q;
  131.             }
  132.         }
  133.     } else { //hash free
  134.         arr[x] = node();
  135.         arr[x].data = y;
  136.         arr[x].key = k;
  137.     }
  138.    
  139. }
  140.  
  141. void del(vector < node > &arr, string k)
  142. {
  143.     int x = hashfunc(k);
  144.    
  145.     if (key_inchain(arr, k))
  146.     {
  147.         if (arr[x].key == k && arr[x].next == NULL) //if key is in data
  148.         {
  149.             if (arr[x].next == NULL)
  150.             {
  151.                 arr[x].data = "";
  152.                 arr[x].key = "";
  153.             } else {
  154.                 arr[x].key = arr[x].next->key;
  155.                 arr[x].data = arr[x].next->data;
  156.                 arr[x].next = arr[x].next->next;
  157.             }
  158.         } else if (arr[x].key != k) //key is in chain somewhere
  159.         {
  160.             node *cur = arr[x].next; //cur is 1st in chain
  161.             if (cur->key == k) //...if match
  162.             {
  163.                 if (cur->next == NULL)
  164.                 {
  165.                     arr[x].next = NULL;
  166.                     free(cur);
  167.                 } else {
  168.                     arr[x].next = cur->next;
  169.                     free(cur);
  170.                 }
  171.             } else if(cur->key != k)//if not
  172.             {
  173.                 node *curprev = cur;
  174.                 while(cur->next != NULL)
  175.                 {
  176.                     cur = cur->next;
  177.                     if (cur->key == k)
  178.                     {
  179.                         curprev->next = cur->next;
  180.                         free(cur);
  181.                         break;
  182.                     }
  183.                     curprev = curprev->next;
  184.                 }
  185.             }
  186.         }
  187.     }
  188. }
  189.  
  190.  
  191. int main()
  192. {
  193.     node default_node;
  194.     default_node.key = "";
  195.     default_node.data = "";
  196.     default_node.next = NULL;
  197.     vector < node > arr (1000000, default_node);
  198.    
  199.     ifstream fin("map.in");
  200.     ofstream fout("map.out");
  201.    
  202.     string command;
  203.     string key;
  204.     string value;
  205.     while (fin >> command)
  206.     {
  207.         if (command == "put")
  208.         {
  209.             fin >> key;
  210.             fin >> value;
  211.             add(arr, key, value);
  212.         } else if (command == "get")
  213.         {
  214.             fin >> key;
  215.             fout << key_val(arr, key) << endl;
  216.         } else if (command == "delete")
  217.         {
  218.             fin >> key;
  219.             del(arr, key);
  220.         }
  221.     }
  222.    
  223.     return 0;
  224. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement