Mihailus2000

bloom filter1

Oct 27th, 2020
856
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <map>
  5.  
  6. class ParseExceptions : public std::exception {
  7. private:
  8.     std::string _error;
  9. public:
  10.     ParseExceptions() = default;
  11.  
  12.     explicit ParseExceptions(std::string error) : _error(std::move(error)) {}
  13.  
  14.     ~ParseExceptions() override = default;
  15.  
  16.     [[nodiscard]] const char *what() const noexcept override {
  17.         return _error.c_str();
  18.     }
  19. };
  20.  
  21. class BloomFilter {
  22. public:
  23.  
  24.     BloomFilter() = default;
  25.  
  26.     ~BloomFilter() {
  27.         if(_bitset) {
  28.             _bitset->clear();
  29.             delete _bitset;
  30.         }
  31.  
  32.     }
  33.  
  34.     std::pair<std::string,std::string> init (uint64_t amount, long double falsePositiveProbability) {
  35.         _probability = falsePositiveProbability;
  36.         _sizeOfBitset = uint64_t(-std::round(amount * std::log2(falsePositiveProbability) / log(2)));
  37.         _amountOfHF = uint64_t(-std::round(std::log2(_probability)));
  38.         if(_sizeOfBitset > 0 && _amountOfHF > 0)
  39.             _bitset = new std::vector<bool>(_sizeOfBitset, false);
  40.         else
  41.             throw ParseExceptions();
  42.         return std::make_pair(std::to_string(_sizeOfBitset),std::to_string(_amountOfHF));
  43.     }
  44.  
  45.     void addElement(uint64_t key) {
  46.         for (uint64_t indexOfHF = 0; indexOfHF < _amountOfHF; indexOfHF++) {
  47.             uint64_t hash = hashFunc(key, indexOfHF);
  48.             _bitset->at(hash) = true;
  49.         }
  50.     }
  51.  
  52.     bool searchElement(uint64_t key) {
  53.         for (uint64_t indexOfHF = 0; indexOfHF < _amountOfHF; indexOfHF++) {
  54.             uint64_t hash = hashFunc(key, indexOfHF);
  55.             if (!_bitset->at(hash))
  56.                 return false;
  57.         }
  58.         return true;
  59.     }
  60.  
  61.     std::string printBitset() {
  62.         std::string bitSetStr;
  63.         for (const auto &bit : *_bitset) {
  64.             if (bit)
  65.                 bitSetStr += "1";
  66.             else
  67.                 bitSetStr += "0";
  68.         }
  69.         return bitSetStr;
  70.     }
  71.  
  72. private:
  73.  
  74.     const uint64_t _mersenne = 2147483647;
  75.  
  76.     uint64_t hashFunc(uint64_t key, uint64_t index) {
  77.         return (((index + 1) * key + _firstPrimeNumbers.at(index)) % _mersenne) % _sizeOfBitset;
  78.     }
  79.  
  80.     std::vector<bool> *_bitset = nullptr;
  81.     std::vector<int> _firstPrimeNumbers = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
  82.                                                 67, 71,
  83.                                                 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
  84.                                                 151, 157, 163, 167, 173,
  85.                                                 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
  86.                                                 257, 263, 269, 271, 277, 281,
  87.                                                 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373,
  88.                                                 379, 383, 389, 397, 401, 409,
  89.                                                 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
  90.                                                 499, 503, 509, 521, 523, 541,
  91.                                                 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619,
  92.                                                 631, 641, 643, 647, 653, 659,
  93.                                                 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757,
  94.                                                 761, 769, 773, 787, 797, 809,
  95.                                                 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
  96.                                                 907, 911, 919, 929, 937, 941,
  97.                                                 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031,
  98.                                                 1033, 1039, 1049, 1051, 1061, 1063, 1069};
  99.     long double _probability = 0.0;
  100.     uint64_t _amountOfHF = 0;
  101.     uint64_t _sizeOfBitset = 0;
  102. };
  103.  
  104.  
  105.  
  106. void tokenize(const std::string &str, std::vector<std::string> &tokens, const std::string &delimiters = ".") {
  107.     std::string::size_type lastPos = str.find_first_not_of(delimiters, 0);
  108.     std::string::size_type pos = str.find_first_of(delimiters, lastPos);
  109.     while (pos != std::string::npos ||lastPos != std::string::npos ) {
  110.         tokens.push_back(str.substr(lastPos, pos - lastPos));
  111.         lastPos = str.find_first_not_of(delimiters, pos);
  112.         pos = str.find_first_of(delimiters, lastPos);
  113.     }
  114. }
  115.  
  116. void runParse(BloomFilter *filter) {
  117.     bool setConfig = false;
  118.     std::string inputStr;
  119. //        std::chrono::time_point<std::chrono::high_resolution_clock> beg, endd/*, parseBeg, parseEnd*/;
  120. //        beg = std::chrono::system_clock::now();
  121.     while (std::getline(std::cin,inputStr)) {
  122.         try {
  123.             if (inputStr.length() > 0) {
  124.                 std::vector<std::string> tokens;
  125.                 tokenize(inputStr, tokens, " ");
  126.                 auto size = tokens.size();
  127.                 if (size <= 3 && size > 0) {
  128.                     auto key = tokens.at(0);
  129.                     switch (size) {
  130.                         case 3:
  131.                             if (key == "set" && !setConfig) {
  132.                                 uint64_t amount = std::stoul(tokens.at(1));
  133.                                 long double probability = std::stod(tokens.at(2));
  134.                                 if(probability > 0.0 && probability < 1.0 && amount > 0) {
  135.                                     auto res = filter->init(amount, probability);
  136.                                     std::cout << res.first << " " << res.second << std::endl;
  137.                                     setConfig = true;
  138.                                 }
  139.                                 else throw ParseExceptions();
  140.                             } else throw ParseExceptions();
  141.                             break;
  142.                         case 2:
  143.                             if (key == "add" && setConfig) {
  144.                                 uint64_t number;
  145.                                 number = std::stoull(tokens.at(1));
  146.                                 filter->addElement(number);
  147.                             } else if (key == "search" && setConfig) {
  148.                                 uint64_t number;
  149.                                 number = std::stoull(tokens.at(1));
  150.                                 bool result = filter->searchElement(number);
  151.                                 std::cout << result << std::endl;
  152.                             } else throw ParseExceptions();
  153.                             break;
  154.                         case 1:
  155.                             if (key == "print" && setConfig) {
  156.                                 std::string output = filter->printBitset();
  157.                                 std::cout << output << std::endl;
  158.                             } else throw ParseExceptions();
  159.                             break;
  160.                         default:
  161.                             throw ParseExceptions();
  162.                     }
  163.                 }
  164.             }
  165.         }
  166.         catch (ParseExceptions &exc) {
  167.             std::cout << "error\n";
  168.         }
  169.         catch (std::exception &exc) {
  170.             std::cout << "error\n";
  171.         }
  172.         catch (...) {
  173.             std::cout << "ERROR: " << "Unexpected error in search!\n";
  174.         }
  175.     }
  176.  
  177.  
  178. }
  179.  
  180.  
  181. int main() {
  182.     auto *newFilter_p = new BloomFilter();
  183.     runParse(newFilter_p);
  184.     delete newFilter_p;
  185.     return 0;
  186. }
RAW Paste Data