SHARE
TWEET

Untitled

a guest Dec 11th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <string>
  5. #include <memory>
  6. #include <list>
  7.  
  8. using namespace std;
  9.  
  10. class Set
  11. {
  12. private:
  13.     vector<list<string>> hashTable;
  14.  
  15.     unsigned hash(string key)
  16.     {
  17.         unsigned hash = 0;
  18.         int charCode;
  19.         const int k = 199;
  20.         for (char i : key)
  21.         {
  22.             charCode = tolower(i) - 'a';
  23.             hash = (hash * k + charCode) % hashTable.size();
  24.         }
  25.         return hash;
  26.     }
  27.  
  28. public:
  29.     Set(unsigned size)
  30.     {
  31.         hashTable.resize(size);
  32.     }
  33.  
  34.     bool exists(string key)
  35.     {
  36.         unsigned index = hash(key);
  37.         for (string i : hashTable[index])
  38.         {
  39.             if (i == key)
  40.                 return true;
  41.         }
  42.         return false;
  43.     }
  44.  
  45.     void insert(string key)
  46.     {
  47.         if (!exists(key))
  48.             hashTable[hash(key)].push_back(key);
  49.     }
  50.  
  51.     void remove(string key)
  52.     {
  53.         unsigned index = hash(key);
  54.         for (auto i = hashTable[index].begin(); i != hashTable[index].end(); i++)
  55.         {
  56.             if (*i == key)
  57.             {
  58.                 hashTable[index].erase(i);
  59.                 return;
  60.             }
  61.         }
  62.     }
  63.  
  64.     vector<string> getAll()
  65.     {
  66.         vector<string> result;
  67.         for (list<string> values : hashTable)
  68.         {
  69.             for (string value : values)
  70.             {
  71.                 result.push_back(value);
  72.             }
  73.         }
  74.         return result;
  75.     }
  76.  
  77.     void reset()
  78.     {
  79.         unsigned size = hashTable.size();
  80.         hashTable.clear();
  81.         hashTable.resize(size);
  82.     }
  83. };
  84.  
  85. class Map
  86. {
  87. private:
  88.     struct Node
  89.     {
  90.         string key;
  91.         shared_ptr<Set> values;
  92.     };
  93.  
  94.     vector<list<Node>> hashTable;
  95.  
  96.     unsigned valueSetSize;
  97.  
  98.     unsigned hash(string key)
  99.     {
  100.         unsigned hash = 0;
  101.         int charCode;
  102.         const int k = 199;
  103.         for (char i : key)
  104.         {
  105.             charCode = tolower(i) - 'a';
  106.             hash = (hash * k + charCode) % hashTable.size();
  107.         }
  108.         return hash;
  109.     }
  110.  
  111.     shared_ptr<Set> getValueSet(string key)
  112.     {
  113.         unsigned index = hash(key);
  114.         for (Node &Node : hashTable[index])
  115.         {
  116.             if (Node.key == key)
  117.             {
  118.                 return Node.values;
  119.             }
  120.         }
  121.         return nullptr;
  122.     }
  123.  
  124. public:
  125.     Map(unsigned mapSize, unsigned valueSetSize)
  126.     {
  127.         hashTable.resize(mapSize);
  128.         this->valueSetSize = valueSetSize;
  129.     }
  130.  
  131.     void put(string key, string value)
  132.     {
  133.         shared_ptr<Set> valueSet = getValueSet(key);
  134.         if (valueSet != nullptr)
  135.             valueSet->insert(value);
  136.         else
  137.         {
  138.             Node newNode;
  139.             newNode.key = key;
  140.             newNode.values = make_shared<Set>(valueSetSize);
  141.             newNode.values->insert(value);
  142.             hashTable[hash(key)].push_back(newNode);
  143.         }
  144.     }
  145.  
  146.     vector<string> get(string key)
  147.     {
  148.         shared_ptr<Set> valueSet = getValueSet(key);
  149.         if (valueSet != nullptr)
  150.             return valueSet->getAll();
  151.         else
  152.             return vector<string>(0);
  153.     }
  154.  
  155.     void remove(string key, string value)
  156.     {
  157.         shared_ptr<Set> valueSet = getValueSet(key);
  158.         if (valueSet != nullptr)
  159.             valueSet->remove(value);
  160.     }
  161.  
  162.     void removeAll(string key)
  163.     {
  164.         unsigned index = hash(key);
  165.         for (auto i = hashTable[index].begin(); i != hashTable[index].end(); i++)
  166.         {
  167.             if (i->key == key)
  168.             {
  169.                 hashTable[index].erase(i);
  170.                 return;
  171.             }
  172.         }
  173.     }
  174. };
  175.  
  176. int main()
  177. {
  178.     Map Map(100003, 233);
  179.     ifstream inputf("multimap.in");
  180.     ofstream outputf("multimap.out");
  181.     string command, x, y;
  182.     while (!inputf.eof())
  183.     {
  184.         command = "";
  185.         inputf >> command >> x;
  186.         if (command == "put")
  187.         {
  188.             inputf >> y;
  189.             Map.put(x, y);
  190.         }
  191.         else if (command == "get")
  192.         {
  193.             vector<string> values = Map.get(x);
  194.             outputf << values.size() << " ";
  195.             for (string value : values)
  196.                 outputf << value << " ";
  197.             outputf << '\n';
  198.         }
  199.         else if (command == "delete")
  200.         {
  201.             inputf >> y;
  202.             Map.remove(x, y);
  203.         }
  204.         else if (command == "deleteall")
  205.         {
  206.             Map.removeAll(x);
  207.         }
  208.     }
  209.     inputf.close();
  210.     outputf.close();
  211. }
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