Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <stdlib.h>
- #include <vector>
- #include <utility>
- using namespace std;
- struct node {
- string key;
- string data;
- node *next;
- };
- int hashfunc(string s)
- {
- const int p = 31;
- const int m = 1e9 + 9;
- long long hash_value = 0;
- long long p_pow = 1;
- for (int i = 0; i < s.length();i++ ) {
- hash_value = (hash_value + (s[i] - 'a' + 1) * p_pow) % m;
- p_pow = (p_pow * p) % m;
- }
- hash_value = hash_value % 1000000;
- return hash_value;
- }
- bool key_inchain(vector < node > &arr, string k)
- {
- int x = hashfunc(k);
- if (arr[x].key == k) //if key is in data
- {
- return true;
- } else if (arr[x].key != k && arr[x].next == NULL) //if key not in data & no chain
- {
- return false;
- } else { //key not in data, chain
- node *cur = arr[x].next;
- while (cur->next != NULL)
- {
- if (cur->key == k)
- {
- return true;
- }
- cur = cur->next;
- }
- if (cur->key == k)
- {
- return true;
- }
- }
- return false;
- }
- string key_val(vector < node > &arr, string k)
- {
- int x = hashfunc(k);
- if (arr[x].key == k) //if key in data
- {
- return arr[x].data;
- } else { //key not in data
- if ( arr[x].next == NULL) //no chain
- {
- return "none";
- }
- node *cur = arr[x].next;
- while (cur->next != NULL)
- {
- if (cur->key == k)
- {
- return cur->data;
- }
- cur = cur->next;
- }
- if (cur->key == k)
- {
- return cur->data;
- }
- }
- return "none";
- }
- void add(vector < node > &arr, string k, string y)
- {
- int x = hashfunc(k);
- if (arr[x].data != "") //hash taken
- {
- if(arr[x].key == k) //key is in data
- {
- arr[x].data = y;
- } else if (key_inchain(arr, k)) //key is in chain
- {
- node *cur = arr[x].next;
- if (cur->key == k)
- {
- cur->data = y;
- } else {
- while (cur->next != NULL)
- {
- if (cur->key == k)
- {
- cur->data = y;
- }
- }
- if (cur->key == k)
- {
- cur->data = y;
- }
- }
- } else { //no such key, not in data, not in chain
- if (arr[x].next == NULL) //if no chain
- {
- node *q;
- q = new node();
- q->key = k;
- q->data = y;
- } else {
- node *cur = arr[x].next;
- while (cur->next != NULL)
- {
- cur = cur->next;
- }
- node *q;
- q = new node();
- q->key = k;
- q->data = y;
- cur->next = q;
- }
- }
- } else { //hash free
- arr[x] = node();
- arr[x].data = y;
- arr[x].key = k;
- }
- }
- void del(vector < node > &arr, string k)
- {
- int x = hashfunc(k);
- if (key_inchain(arr, k))
- {
- if (arr[x].key == k && arr[x].next == NULL) //if key is in data
- {
- if (arr[x].next == NULL)
- {
- arr[x].data = "";
- arr[x].key = "";
- } else {
- arr[x].key = arr[x].next->key;
- arr[x].data = arr[x].next->data;
- arr[x].next = arr[x].next->next;
- }
- } else if (arr[x].key != k) //key is in chain somewhere
- {
- node *cur = arr[x].next; //cur is 1st in chain
- if (cur->key == k) //...if match
- {
- if (cur->next == NULL)
- {
- arr[x].next = NULL;
- free(cur);
- } else {
- arr[x].next = cur->next;
- free(cur);
- }
- } else if(cur->key != k)//if not
- {
- node *curprev = cur;
- while(cur->next != NULL)
- {
- cur = cur->next;
- if (cur->key == k)
- {
- curprev->next = cur->next;
- free(cur);
- break;
- }
- curprev = curprev->next;
- }
- }
- }
- }
- }
- int main()
- {
- node default_node;
- default_node.key = "";
- default_node.data = "";
- default_node.next = NULL;
- vector < node > arr (1000000, default_node);
- ifstream fin("map.in");
- ofstream fout("map.out");
- string command;
- string key;
- string value;
- while (fin >> command)
- {
- if (command == "put")
- {
- fin >> key;
- fin >> value;
- add(arr, key, value);
- } else if (command == "get")
- {
- fin >> key;
- fout << key_val(arr, key) << endl;
- } else if (command == "delete")
- {
- fin >> key;
- del(arr, key);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement