SHARE
TWEET

Untitled

a guest Dec 9th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3.  
  4. template <typename T>
  5. class Array {
  6. private:
  7.     const int multip = 2;
  8.  
  9.     void increase()
  10.     {
  11.         this->MAX_CAP *= this->multip;
  12.         T* new_array = new T[MAX_CAP];
  13.  
  14.         for (unsigned int i = 0; i < this->counter; i++)
  15.             new_array[i] = this->array[i];
  16.  
  17.         delete[] this->array;
  18.         array = new_array;
  19.     }
  20.  
  21.     void set(unsigned int number, T data)
  22.     {
  23.         if (number < this->counter)
  24.             this->array[number] = data;
  25.     }
  26.  
  27. public:
  28.     T* array;
  29.     unsigned int counter;
  30.     unsigned int MAX_CAP;
  31.     Array()
  32.     {
  33.         this->MAX_CAP = 1;
  34.         this->counter = 0;
  35.         this->array = new T[MAX_CAP];
  36.     }
  37.  
  38.     virtual ~Array()
  39.     {
  40.         //for (unsigned int i = 0; i < this->counter; i++)
  41.             //delete array[i];
  42.         delete[] array;
  43.     }
  44.  
  45.     void add_(T data)
  46.     {
  47.         if (this->counter < this->MAX_CAP)
  48.         {
  49.             this->array[this->counter] = data;
  50.             counter++;
  51.         }
  52.         else
  53.         {
  54.             this->increase();
  55.             this->array[this->counter] = data;
  56.             counter++;
  57.         }
  58.     }
  59.  
  60.     T return_(unsigned int number)
  61.     {
  62.         if (number < this->counter)
  63.             return this->array[number];
  64.         else
  65.             return NULL;
  66.     }
  67.  
  68.     std::string to_string()
  69.     {
  70.         std::string str;
  71.         if (this->counter == 0)
  72.             return "empty";
  73.  
  74.         for (unsigned int i = 0; i < this->counter && i < 5; i++)
  75.             str = str + array[i].to_string() + " -> ";
  76.         return str;
  77.     }
  78.  
  79.     void reset_()
  80.     {
  81.         this->MAX_CAP = 1;
  82.         this->counter = 0;
  83.  
  84.         T* new_array = new T[MAX_CAP];
  85.  
  86.         delete[] this->array;
  87.         this->array = new_array;
  88.     }
  89. };
  90.  
  91. template<typename T>
  92. class Node
  93. {
  94. public:
  95.     std::string name;
  96.     T data;
  97.  
  98.     std::string to_string()
  99.     {
  100.         return name + " " + std::to_string(data);
  101.     }
  102.  
  103.     Node()
  104.     {
  105.  
  106.     }
  107.  
  108.     Node(std::string str, T data)
  109.     {
  110.         this->name = str;
  111.         this->data = data;
  112.     }
  113.  
  114.     bool operator==(Node data)
  115.     {
  116.         if (this->data == data.data && this->name == data.name)
  117.             return true;
  118.         else
  119.             return false;
  120.     }
  121. };
  122.  
  123. template<typename T>
  124. class Hasz
  125. {
  126. private:
  127.  
  128.     int Max_cap;
  129.     int Act_cap;
  130.  
  131.     void rehash()
  132.     {
  133.         int newmax = Max_cap * 2;
  134.         Array<T>* newtab = new Array<T>[newmax];
  135.  
  136.         for (int i = 0; i < this->Act_cap; i++)
  137.         {
  138.             for (int j = 0; j < table[i].counter; j++)
  139.             {
  140.                 T tmp = table[i].array[j];
  141.  
  142.                 std::string nazwa = tmp.name;
  143.                 int lenght = nazwa.length();
  144.                 int suma = 0;
  145.  
  146.                 for (int i = 0; i < lenght; i++)
  147.                 {
  148.                     int x = lenght - i - 1;
  149.                     suma = suma + nazwa[i] * pow(31, x);
  150.                 }
  151.                 suma = suma % newmax;
  152.                 newtab[abs(suma)].add_(tmp);
  153.             }
  154.         }
  155.         delete[] table;
  156.         Max_cap = newmax;
  157.         table = newtab;
  158.     }
  159.  
  160.     int getHash(std::string data)
  161.     {
  162.         int lenght = data.length();
  163.         int suma = 0;
  164.  
  165.         for (int i = 0; i < lenght; i++)
  166.         {
  167.             int x = lenght - i - 1;
  168.             suma = suma + data[i] * pow(31, x);
  169.         }
  170.         suma = suma % Max_cap;
  171.         return abs(suma);
  172.     }
  173.  
  174. public:
  175.     Array<T>* table;
  176.     Hasz()
  177.     {
  178.         Max_cap = 2;
  179.         Act_cap = 0;
  180.         table = new Array<T>[Max_cap];
  181.     }
  182.  
  183.     void add(T data)
  184.     {
  185.         if (Act_cap >= (float)Max_cap * 0.75)
  186.             this->rehash();
  187.  
  188.         std::string nazwa = data.name;
  189.         int lenght = nazwa.length();
  190.         int suma = 0;
  191.         for (int i = 0; i < lenght; i++)
  192.         {
  193.             int x = lenght - i - 1;
  194.             suma = suma + nazwa[i] * pow(31, x);
  195.         }
  196.         suma = suma % Max_cap;     
  197.  
  198.         table[abs(suma)].add_(data);
  199.         Act_cap++;
  200.     }
  201.  
  202.     std::string to_string()
  203.     {
  204.         std::string str;
  205.  
  206.         for (int i = 0; i < Max_cap && i < 10; i++)
  207.         {
  208.             str = str + table[i].to_string() + "\n";
  209.         }
  210.         return str;
  211.     }
  212.  
  213.     T* findHash(T data)
  214.     {
  215.         int hasz = getHash(data.name);
  216.         for (int i = 0; i < table[hasz].counter; i++)
  217.         {
  218.             if (table[hasz].array[i] == data)
  219.                 return &table[hasz].array[i];
  220.         }
  221.     }
  222.  
  223.     bool deleteHash(T data)
  224.     {
  225.         int hasz = getHash(data.name);
  226.         int i;
  227.         if (table[hasz].counter == 0)
  228.             return false;
  229.         for (i = 0; i < table[hasz].counter; i++)
  230.         {
  231.             if (table[hasz].array[i] == data)
  232.                 break;
  233.             return false;
  234.         }      
  235.  
  236.         table[hasz].array[i] = table[hasz].array[table[hasz].counter-1];
  237.         table[hasz].counter--;
  238.         return true;
  239.     }
  240. };
  241.  
  242. int main()
  243. {
  244.     Node<int> data("string", 6);
  245.     Node<int> data1("kusi", 1);
  246.     Node<int> data2("kek", 2);
  247.     Node<int> data3("XD", 69);
  248.     Node<int> nowy("nowy", 10);
  249.  
  250.     Hasz<Node<int>>* hasz = new Hasz<Node<int>>;
  251.  
  252.     hasz->add(data);
  253.     std::cout << hasz->to_string() << std::endl << std::endl;
  254.     hasz->add(data1);
  255.     std::cout << hasz->to_string() << std::endl << std::endl;
  256.     hasz->add(data2);
  257.     std::cout << hasz->to_string() << std::endl << std::endl;
  258.     hasz->add(data3);
  259.     std::cout << hasz->to_string() << std::endl << std::endl;
  260. }
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