lezsakdomi

Trie.hpp

May 11th, 2021
500
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2.  
  3. #include <string>
  4. #include <stdexcept>
  5.  
  6. template<class T, class U>
  7. class TrieBase {
  8. private:
  9.     bool isEndOfWord = false;
  10.     U meaning;
  11.  
  12. protected:
  13.     int characterSize;
  14.     TrieBase<T, U> **character;
  15.  
  16.     explicit TrieBase(int characterSize) : characterSize(characterSize),
  17.                                            character(new TrieBase<T, U> *[characterSize]) {
  18.         for (size_t i = 0; i < characterSize; i++) {
  19.             character[i] = nullptr;
  20.         }
  21.     }
  22.  
  23.     U getMeaningUnchecked() const {
  24.         return meaning;
  25.     }
  26.  
  27. public:
  28.     bool haveChildren() const {
  29.         for (size_t i = 0; i < characterSize; i++) {
  30.             if (this->character[i]) {
  31.                 return true;
  32.             }
  33.         }
  34.         return false;
  35.     }
  36.  
  37.     void setMeaning(const U &newMeaning) {
  38.         if (this->isEndOfWord) {
  39.             throw std::runtime_error("Trie already has a meaning");
  40.         } else {
  41.             this->isEndOfWord = true;
  42.             this->meaning = newMeaning;
  43.         }
  44.     }
  45.  
  46.     bool getIsEndOfWord() const {
  47.         return isEndOfWord;
  48.     }
  49.  
  50.     TrieBase<T, U> &operator=(const TrieBase<T, U> &rhs) {
  51.         if (this != &rhs) {
  52.             for (size_t i = 0; i < this->characterSize; i++) {
  53.                 if (rhs.character[i] != nullptr) {
  54.                     this->character[i] = rhs.character[i];
  55.                 }
  56.             }
  57.         }
  58.  
  59.         return *this;
  60.     }
  61.  
  62.     TrieBase<T, U> &operator+=(const TrieBase<T, U> &rhs) {
  63.         if (this != &rhs) {
  64.             for (size_t i = 0; i < this->characterSize /* == rhs.characterSize */; i++) {
  65.                 if (rhs.character[i] == nullptr) {
  66.                     // noop
  67.                 } else {
  68.                     if (this->character[i] == nullptr) {
  69.                         this->character[i] = new TrieBase<T, U>(characterSize);
  70.                         this->character[i] = *rhs.character[i];
  71.                     } else {
  72.                         this->character[i] += *rhs.character[i];
  73.                     }
  74.                 }
  75.             }
  76.         }
  77.  
  78.         return *this;
  79.     }
  80.  
  81.     virtual ~TrieBase() {
  82.         for (size_t i = 0; i < characterSize; i++) {
  83.             if (character[i] == nullptr)
  84.                 delete character[i];
  85.         }
  86.     }
  87. };
  88.  
  89. class TrieInt : public TrieBase<int, int> {
  90. private:
  91.     static int arraySize(int n) {
  92.         int db = 1;
  93.         while (n >= 2) {
  94.             n /= 2;
  95.             db++;
  96.         }
  97.         return db;
  98.     }
  99.  
  100.     static int getBit(const int &n, const size_t &i) {
  101.         // magic
  102.         return (n >> i) % 2;
  103.     }
  104.  
  105. public:
  106.     TrieInt() : TrieBase<int, int>(2) {} // NOLINT(modernize-use-equals-default)
  107.  
  108.     ~TrieInt() override {} // NOLINT(modernize-use-equals-default)
  109.  
  110.     void newWord(const int &word, const int &meaning) {
  111.         TrieInt *currentTree = this;
  112.  
  113.         for (size_t i = 0; i < TrieInt::arraySize(meaning); i++) {
  114.             const int pos = TrieInt::getBit(word, i);
  115.             if (currentTree->character[pos] == nullptr) {
  116.                 currentTree->character[pos] = new TrieInt();
  117.             }
  118.             currentTree = (TrieInt *) currentTree->character[pos];
  119.         }
  120.  
  121.         currentTree->setMeaning(meaning);
  122.     }
  123.  
  124.     int getMeaning(const int &word) const {
  125.         TrieInt const *currentTree = this;
  126.  
  127.         for (size_t i = 0; i < TrieInt::arraySize(word); i++) {
  128.             const int pos = TrieInt::getBit(word, i);
  129.             currentTree = (TrieInt *) currentTree->character[pos];
  130.             if (currentTree == nullptr) {
  131.                 throw std::runtime_error("The word has no meaning");
  132.             }
  133.         }
  134.  
  135.         if (currentTree->getIsEndOfWord()) return currentTree->getMeaningUnchecked();
  136.         else throw std::runtime_error("The word is not a meaning");
  137.     }
  138.  
  139.     void deleteWord(const int &word) {
  140.         auto **thisPointer = new TrieInt *(this);
  141.         TrieInt **currentTreePointer = thisPointer;
  142.  
  143.         for (size_t i = 0; i < TrieInt::arraySize(word); i++) {
  144.             TrieInt *&currentTree = *currentTreePointer;
  145.  
  146.             if (currentTree == nullptr) {
  147.                 throw std::runtime_error("The word has no meaning");
  148.             }
  149.  
  150.             if (currentTree->getIsEndOfWord()) {
  151.                 delete currentTree;
  152.                 currentTree = nullptr;
  153.             }
  154.  
  155.             const int pos = TrieInt::getBit(word, i);
  156.             if (currentTree->character[1 - pos] == nullptr) {
  157.                 delete currentTree->character[pos];
  158.                 currentTree->character[pos] = nullptr;
  159.  
  160.                 if (this != currentTree) {
  161.                     delete currentTree;
  162.                     currentTree = nullptr;
  163.                 }
  164.  
  165.                 return;
  166.             }
  167.  
  168.             currentTreePointer = (TrieInt **) &currentTree->character[pos];
  169.         }
  170.  
  171.         delete thisPointer;
  172.     }
  173. };
  174.  
  175. class TrieChar : public TrieBase<char, std::string> {
  176. public:
  177.     TrieChar() : TrieBase<char, std::string>(2) {} // NOLINT(modernize-use-equals-default)
  178.  
  179.     ~TrieChar() override {} // NOLINT(modernize-use-equals-default)
  180.  
  181.     void newWord(const std::string &word, const std::string &meaning) {
  182.         TrieChar *currentTree = this;
  183.  
  184.         for (int i = 0; i < word.size(); i++) { // NOLINT(modernize-loop-convert)
  185.             char c = word[i];
  186.  
  187.             if (currentTree->character[c] == nullptr) {
  188.                 currentTree->character[c] = new TrieChar();
  189.             }
  190.             currentTree = (TrieChar *) currentTree->character[c];
  191.         }
  192.  
  193.         currentTree->setMeaning(meaning);
  194.     }
  195.  
  196.     std::string getMeaning(const std::string &word) const {
  197.         TrieChar const *currentTree = this;
  198.  
  199.         for (size_t i = 0; i < word.size(); i++) { // NOLINT(modernize-loop-convert)
  200.             const int pos = (unsigned char) word[i];
  201.             currentTree = (TrieChar *) currentTree->character[pos];
  202.             if (currentTree == nullptr) {
  203.                 throw std::runtime_error("The word has no meaning");
  204.             }
  205.         }
  206.  
  207.         if (currentTree->getIsEndOfWord()) return currentTree->getMeaningUnchecked();
  208.         else throw std::runtime_error("The word is not a meaning");
  209.     }
  210.  
  211.     void deleteWord(const std::string &word) {
  212.         auto **thisPointer = new TrieChar *(this);
  213.         TrieChar **currentTreePointer = thisPointer;
  214.  
  215.         for (size_t i = 0; i < word.size(); i++) {
  216.             TrieChar *&currentTree = *currentTreePointer;
  217.  
  218.             if (currentTree == nullptr) {
  219.                 throw std::runtime_error("The word has no meaning");
  220.             }
  221.  
  222.             if (currentTree->getIsEndOfWord()) {
  223.                 delete currentTree;
  224.                 currentTree = nullptr;
  225.             }
  226.  
  227.             const int pos = (unsigned char) word[i];
  228.  
  229.             int childCount = 0;
  230.             for (int j = 0; j < currentTree->characterSize; j++) {
  231.                 if (currentTree->character[j] != nullptr) childCount++;
  232.             }
  233.  
  234.             if (childCount == 0) {
  235.                 delete currentTree->character[pos];
  236.                 currentTree->character[pos] = nullptr;
  237.  
  238.                 if (this != currentTree) {
  239.                     delete currentTree;
  240.                     currentTree = nullptr;
  241.                 }
  242.  
  243.                 return;
  244.             }
  245.  
  246.             currentTreePointer = (TrieChar **) &currentTree->character[pos];
  247.         }
  248.  
  249.         delete thisPointer;
  250.     }
  251. };
  252.  
RAW Paste Data