Guest User

Untitled

a guest
Nov 17th, 2019
59
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