Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.83 KB | None | 0 0
  1. #include <fstream>
  2. #include <string>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. struct list{
  8. string element;
  9. string key;
  10. list* next;
  11. list* prevEl;
  12. list* nextEl;
  13. };
  14.  
  15. struct LinkedMap{
  16. list* a[500009];
  17. list* lastEl;
  18. LinkedMap(){
  19. for (int i = 0; i < 500009; i++)
  20. a[i] = nullptr;
  21. lastEl = nullptr;
  22. }
  23.  
  24. void put(string strKey, string el, int hashKey){
  25. list *findEl = a[hashKey];
  26. list *prevElement = findEl;
  27. while (findEl != nullptr && findEl->key != strKey) {
  28. prevElement = findEl;
  29. findEl = findEl->next;
  30. }
  31. if (findEl == nullptr) {
  32. list *newElement = new list;
  33. newElement->next = nullptr;
  34. newElement->element = el;
  35. newElement->key = strKey;
  36. newElement->nextEl = nullptr;
  37. if (prevElement == nullptr) {
  38. a[hashKey] = newElement;
  39. }
  40. else {
  41. prevElement->next = newElement;
  42. }
  43. if (lastEl != nullptr)
  44. lastEl->nextEl = newElement;
  45. newElement->prevEl = lastEl;
  46. lastEl = newElement;
  47. }
  48. else {
  49. findEl->element = el;
  50. }
  51. }
  52.  
  53. string get(string strKey, int hashKey) {
  54. list* findEl = a[hashKey];
  55. while (findEl != nullptr && findEl->key != strKey) {
  56. findEl = findEl->next;
  57. }
  58. if (findEl == nullptr)
  59. return "none";
  60. else
  61. return findEl->element;
  62. }
  63.  
  64. void del(string strKey, int hashKey){
  65. list* findEl = a[hashKey];
  66. list* prevElement = a[hashKey];
  67. while(findEl != nullptr && findEl -> key != strKey){
  68. prevElement = findEl;
  69. findEl = findEl -> next;
  70. }
  71. if (findEl != nullptr && findEl -> key == strKey){
  72. if (findEl == a[hashKey]) {
  73. a[hashKey] = findEl->next;
  74. }
  75. else {
  76. prevElement->next = findEl->next;
  77. }
  78. if (findEl->nextEl != nullptr) {
  79. findEl->nextEl->prevEl = findEl->prevEl;
  80. }
  81. if (findEl->prevEl != nullptr){
  82. findEl->prevEl->nextEl = findEl->nextEl;
  83. }
  84. if (findEl == lastEl)
  85. lastEl = findEl->prevEl;
  86. delete(findEl);
  87. }
  88. }
  89.  
  90. string next(string strKey, int hashKey){
  91. list* findEl = a[hashKey];
  92. while(findEl != nullptr && findEl -> key != strKey){
  93. findEl = findEl -> next;
  94. }
  95. if (findEl != nullptr && findEl -> key == strKey){
  96. if (findEl->nextEl == nullptr)
  97. return "none";
  98. else
  99. return (findEl->nextEl->element);
  100. }
  101. else
  102. return "none";
  103. }
  104.  
  105. string prev(string strKey, int hashKey){
  106. list* findEl = a[hashKey];
  107. while(findEl != nullptr && findEl -> key != strKey){
  108. findEl = findEl -> next;
  109. }
  110. if (findEl != nullptr && findEl -> key == strKey){
  111. if (findEl->prevEl == nullptr)
  112. return "none";
  113. else
  114. return (findEl->prevEl->element);
  115. }
  116. else
  117. return "none";
  118. }
  119. };
  120.  
  121. int primeNum[26] = {25013, 25031, 25033, 25037, 25057, 25073,
  122. 25087, 25097, 25111, 25117, 25121, 25127,
  123. 25147, 25153, 25163, 25169, 25171, 25183,
  124. 25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261};
  125.  
  126. int FindHashKey(string str){
  127. int ans = 0, degree = 1;
  128. for (int i = 0; i < str.size(); i++) {
  129. ans = (abs(ans + (int) str[i] * degree) % 500009);
  130. degree *= primeNum[(int)str[0] - (int)'a'];
  131. }
  132. return ans;
  133. }
  134.  
  135. int main(){
  136. ios_base::sync_with_stdio(false);
  137. ifstream in;
  138. ofstream out;
  139. in.open("linkedmap.in");
  140. out.open("linkedmap.out");
  141. in.tie(NULL);
  142. LinkedMap lMap;
  143. while(!in.eof()){
  144. string com, element, key;
  145. in >> com;
  146. if (com.size() == 0)
  147. break;
  148. if (com == "put"){
  149. in >> key >> element;
  150. lMap.put(key, element, FindHashKey(key));
  151. }
  152. if (com == "get"){
  153. in >> key;
  154. out << lMap.get(key, FindHashKey(key)) << "\n";
  155. }
  156. if (com == "delete"){
  157. in >> key;
  158. lMap.del(key, FindHashKey(key));
  159. }
  160. if (com == "next"){
  161. in >> key;
  162. out << lMap.next(key, FindHashKey(key)) << "\n";
  163. }
  164. if (com == "prev"){
  165. in >> key;
  166. out << lMap.prev(key, FindHashKey(key)) << "\n";
  167. }
  168. }
  169. in.close();
  170. out.close();
  171. return 0;
  172. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement