Trie.hpp

#pragma once

#include <string>
#include <stdexcept>

template<class T, class U>
class TrieBase {
private:
    bool isEndOfWord = false;
    U meaning;

protected:
    int characterSize;
    TrieBase<T, U> **character;

    explicit TrieBase(int characterSize) : characterSize(characterSize),
                                           character(new TrieBase<T, U> *[characterSize]) {
        for (size_t i = 0; i < characterSize; i++) {
            character[i] = nullptr;
        }
    }

    U getMeaningUnchecked() const {
        return meaning;
    }

public:
    bool haveChildren() const {
        for (size_t i = 0; i < characterSize; i++) {
            if (this->character[i]) {
                return true;
            }
        }
        return false;
    }

    void setMeaning(const U &newMeaning) {
        if (this->isEndOfWord) {
            throw std::runtime_error("Trie already has a meaning");
        } else {
            this->isEndOfWord = true;
            this->meaning = newMeaning;
        }
    }

    bool getIsEndOfWord() const {
        return isEndOfWord;
    }

    TrieBase<T, U> &operator=(const TrieBase<T, U> &rhs) {
        if (this != &rhs) {
            for (size_t i = 0; i < this->characterSize; i++) {
                if (rhs.character[i] != nullptr) {
                    this->character[i] = rhs.character[i];
                }
            }
        }

        return *this;
    }

    TrieBase<T, U> &operator+=(const TrieBase<T, U> &rhs) {
        if (this != &rhs) {
            for (size_t i = 0; i < this->characterSize /* == rhs.characterSize */; i++) {
                if (rhs.character[i] == nullptr) {
                    // noop
                } else {
                    if (this->character[i] == nullptr) {
                        this->character[i] = new TrieBase<T, U>(characterSize);
                        this->character[i] = *rhs.character[i];
                    } else {
                        this->character[i] += *rhs.character[i];
                    }
                }
            }
        }

        return *this;
    }

    virtual ~TrieBase() {
        for (size_t i = 0; i < characterSize; i++) {
            if (character[i] == nullptr)
                delete character[i];
        }
    }
};

class TrieInt : public TrieBase<int, int> {
private:
    static int arraySize(int n) {
        int db = 1;
        while (n >= 2) {
            n /= 2;
            db++;
        }
        return db;
    }

    static int getBit(const int &n, const size_t &i) {
        // magic
        return (n >> i) % 2;
    }

public:
    TrieInt() : TrieBase<int, int>(2) {} // NOLINT(modernize-use-equals-default)

    ~TrieInt() override {} // NOLINT(modernize-use-equals-default)

    void newWord(const int &word, const int &meaning) {
        TrieInt *currentTree = this;

        for (size_t i = 0; i < TrieInt::arraySize(meaning); i++) {
            const int pos = TrieInt::getBit(word, i);
            if (currentTree->character[pos] == nullptr) {
                currentTree->character[pos] = new TrieInt();
            }
            currentTree = (TrieInt *) currentTree->character[pos];
        }

        currentTree->setMeaning(meaning);
    }

    int getMeaning(const int &word) const {
        TrieInt const *currentTree = this;

        for (size_t i = 0; i < TrieInt::arraySize(word); i++) {
            const int pos = TrieInt::getBit(word, i);
            currentTree = (TrieInt *) currentTree->character[pos];
            if (currentTree == nullptr) {
                throw std::runtime_error("The word has no meaning");
            }
        }

        if (currentTree->getIsEndOfWord()) return currentTree->getMeaningUnchecked();
        else throw std::runtime_error("The word is not a meaning");
    }

    void deleteWord(const int &word) {
        auto **thisPointer = new TrieInt *(this);
        TrieInt **currentTreePointer = thisPointer;

        for (size_t i = 0; i < TrieInt::arraySize(word); i++) {
            TrieInt *&currentTree = *currentTreePointer;

            if (currentTree == nullptr) {
                throw std::runtime_error("The word has no meaning");
            }

            if (currentTree->getIsEndOfWord()) {
                delete currentTree;
                currentTree = nullptr;
            }

            const int pos = TrieInt::getBit(word, i);
            if (currentTree->character[1 - pos] == nullptr) {
                delete currentTree->character[pos];
                currentTree->character[pos] = nullptr;

                if (this != currentTree) {
                    delete currentTree;
                    currentTree = nullptr;
                }

                return;
            }

            currentTreePointer = (TrieInt **) &currentTree->character[pos];
        }

        delete thisPointer;
    }
};

class TrieChar : public TrieBase<char, std::string> {
public:
    TrieChar() : TrieBase<char, std::string>(2) {} // NOLINT(modernize-use-equals-default)

    ~TrieChar() override {} // NOLINT(modernize-use-equals-default)

    void newWord(const std::string &word, const std::string &meaning) {
        TrieChar *currentTree = this;

        for (int i = 0; i < word.size(); i++) { // NOLINT(modernize-loop-convert)
            char c = word[i];

            if (currentTree->character[c] == nullptr) {
                currentTree->character[c] = new TrieChar();
            }
            currentTree = (TrieChar *) currentTree->character[c];
        }

        currentTree->setMeaning(meaning);
    }

    std::string getMeaning(const std::string &word) const {
        TrieChar const *currentTree = this;

        for (size_t i = 0; i < word.size(); i++) { // NOLINT(modernize-loop-convert)
            const int pos = (unsigned char) word[i];
            currentTree = (TrieChar *) currentTree->character[pos];
            if (currentTree == nullptr) {
                throw std::runtime_error("The word has no meaning");
            }
        }

        if (currentTree->getIsEndOfWord()) return currentTree->getMeaningUnchecked();
        else throw std::runtime_error("The word is not a meaning");
    }

    void deleteWord(const std::string &word) {
        auto **thisPointer = new TrieChar *(this);
        TrieChar **currentTreePointer = thisPointer;

        for (size_t i = 0; i < word.size(); i++) {
            TrieChar *&currentTree = *currentTreePointer;

            if (currentTree == nullptr) {
                throw std::runtime_error("The word has no meaning");
            }

            if (currentTree->getIsEndOfWord()) {
                delete currentTree;
                currentTree = nullptr;
            }

            const int pos = (unsigned char) word[i];

            int childCount = 0;
            for (int j = 0; j < currentTree->characterSize; j++) {
                if (currentTree->character[j] != nullptr) childCount++;
            }

            if (childCount == 0) {
                delete currentTree->character[pos];
                currentTree->character[pos] = nullptr;

                if (this != currentTree) {
                    delete currentTree;
                    currentTree = nullptr;
                }

                return;
            }

            currentTreePointer = (TrieChar **) &currentTree->character[pos];
        }

        delete thisPointer;
    }
};