SHARE
TWEET

Untitled

a guest Nov 17th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. using namespace std;
  5. ifstream fin("linkedmap.in");
  6. ofstream fout("linkedmap.out");
  7. struct item {
  8.     item* prev = NULL;
  9.     item* prev_key = NULL;
  10.     string key;
  11.     string value;
  12.     item* next_key = NULL;
  13.     item* next = NULL;
  14. };
  15.  
  16. vector<item*> HashTable = vector<item*>(1000003);
  17.  
  18. item* CreateNode(string key, string value) {
  19.     auto node = new item;
  20.     node->prev = NULL;
  21.     node->prev_key = NULL;
  22.     node->key = key;
  23.     node->value = value;
  24.     node->next_key = NULL;
  25.     node->next = NULL;
  26.     return node;
  27. }
  28.  
  29. item* AddNode(item* tail, string key, string value) {
  30.     item* node = CreateNode(key, value);
  31.     node->prev = tail;
  32.     tail->next = node;
  33.     return node;
  34. }
  35.  
  36. long long GetHash(string key) {
  37.     const int p = 31;
  38.     long long hash = 0, p_pow = 1;
  39.     for (char i : key)
  40.     {
  41.         hash += (i - 'a' + 1) * p_pow;
  42.         p_pow *= p;
  43.     }
  44.  
  45.     long long m = 1000003;
  46.  
  47.     if (hash >= 0) {
  48.         return hash % m;
  49.     }
  50.     else {
  51.         return (m - abs(hash) % m) % m;
  52.     }
  53. }
  54.  
  55. item* Put(string key, string value, item* LastKey) {
  56.     item* head = HashTable[GetHash(key)];
  57.     if (head == NULL) {
  58.         HashTable[GetHash(key)] = CreateNode(key, value);
  59.         HashTable[GetHash(key)]->prev_key = LastKey;
  60.  
  61.         if (LastKey != NULL)
  62.             LastKey->next_key = HashTable[GetHash(key)];
  63.  
  64.         return HashTable[GetHash(key)];
  65.     }
  66.     else {
  67.         item* pointer = head;
  68.         while (pointer->next != NULL) {
  69.             if (pointer->key == key) {
  70.                 pointer->value = value;
  71.                 return NULL;
  72.             }
  73.             pointer = pointer->next;
  74.         }
  75.  
  76.         if (pointer->key != key) {
  77.             // Новая РЅРѕРґР°
  78.             item* new_node = AddNode(pointer, key, value);
  79.             new_node->prev_key = LastKey;
  80.             if (LastKey != NULL)
  81.                LastKey->next_key = new_node;
  82.             return new_node;
  83.         }
  84.         else {
  85.             pointer->value = value;
  86.             return NULL;
  87.         }
  88.     }
  89. }
  90.  
  91. void Delete(string key, item* LastKey) {
  92.     item* pointer = HashTable[GetHash(key)];
  93.  
  94.     while (pointer != NULL) {
  95.         if (pointer->key == key) {
  96.  
  97.             if (LastKey == pointer)
  98.                 LastKey = pointer->prev_key;
  99.              
  100.             if (pointer->prev_key != NULL)
  101.                 pointer->prev_key->next_key = pointer->next_key;
  102.  
  103.             if (pointer->next_key != NULL)
  104.                 pointer->next_key->prev_key = pointer->prev_key;
  105.  
  106.             if (pointer->prev != NULL)
  107.                 pointer->prev->next = pointer->next;
  108.  
  109.             if (pointer->next != NULL)
  110.                 pointer->next->prev = pointer->prev;
  111.  
  112.             if (pointer == HashTable[GetHash(key)])
  113.                 HashTable[GetHash(key)] = NULL;
  114.  
  115.             free(pointer);
  116.             return;
  117.         }
  118.         pointer = pointer->next;
  119.     }
  120.  
  121. }
  122.  
  123. bool Get(string key) {
  124.     item* pointer = HashTable[GetHash(key)];
  125.  
  126.     while (pointer != NULL) {
  127.         if (pointer->key == key) {
  128.             fout << pointer->value << "\n";
  129.             return true;
  130.         }
  131.         pointer = pointer->next;
  132.     }
  133.  
  134.     fout << "none\n";
  135.     return false;
  136. }
  137.  
  138. item* Find(string key) {
  139.     item* pointer = HashTable[GetHash(key)];
  140.  
  141.     while (pointer != NULL) {
  142.         if (pointer->key == key)
  143.             return pointer;
  144.          
  145.         pointer = pointer->next;
  146.     }
  147.  
  148.     return NULL;
  149. }
  150.  
  151. void Prev(string key) {
  152.     item* element = Find(key);
  153.     if (element != NULL && element->prev_key != NULL)
  154.         fout << element->prev_key->value << "\n";
  155.     else
  156.         fout << "none\n";
  157. }
  158.  
  159. void Next(string key) {
  160.     item* element = Find(key);
  161.     if (element != NULL && element->next_key != NULL)
  162.         fout << element->next_key->value << "\n";
  163.     else
  164.         fout << "none\n";
  165. }
  166.  
  167. int main() {
  168.     ios_base::sync_with_stdio(false);
  169.     fin.tie(NULL);
  170.  
  171.     item* LastKey = NULL;
  172.     string line;
  173.     string key, value;
  174.  
  175.     while (fin >> line) {
  176.         fin >> key;
  177.         if (line == "put") {
  178.             fin >> value;
  179.             item* pointer = Put(key, value, LastKey);
  180.             if (pointer != NULL) LastKey = pointer;
  181.         }
  182.         else if (line == "delete") {
  183.             Delete(key, LastKey);
  184.         }
  185.         else if (line == "get") {
  186.             Get(key);
  187.         }
  188.         else if (line == "prev") {
  189.             Prev(key);
  190.         }
  191.         else if (line == "next") {
  192.             Next(key);
  193.         }
  194.     }
  195.  
  196.     return 0;
  197. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top