Trie.hpp

#pragma once

#include <string>
#include <algorithm>
#include <array>

const int ALPHABET_SIZE = 26;

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

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;
        }
    }

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

    U getMeaning() const {
        return meaning;
    }

    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->getMeaning();
        else throw std::runtime_error("The word is not a meaning");
    }

//    void makeNewTrie(TrieInt<T> &node) {
//        this->insert(node.isEndOfWord, node.meaning);
//
//        for (size_t i = 0; i < BINARY_SIZE; i++) {
//            if (node.character[i] != nullptr)
//                makeNewTrie(node);
//        }
//    }

    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> {
    TrieChar<T> *character[ALPHABET_SIZE];
public:
    TrieChar() {
        for (size_t i = 0; i < ALPHABET_SIZE; i++) {
            character[i] = nullptr;
        }
    }

    TrieChar(const TrieChar &other) {
        TrieChar<T> node = other;
        makeNewTrie(node);
    }

    ~TrieChar() {
        for (size_t i = 0; i < ALPHABET_SIZE; i++) {
            if (character[i] == nullptr)
                delete character[i];
        }
    }

    void newWord(const std::string &str, const T *pMeaning) {
        TrieChar<T> *temp = this;
        for (size_t i = 0; i < str.length(); i++) {
            if (temp->character[str[i] - 'a'] == nullptr)
                temp->character[str[i] - 'a'] = new TrieChar<T>();
            temp = temp->character[str[i] - 'a'];
        }
        temp->isEndOfWord = true;
        temp->meaning = new char[str.length()];
        for (size_t i = 0; i < ((std::string) pMeaning).length() + 1; i++) {
            temp->meaning[i] = pMeaning[i];
        }
    }

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

    bool haveChildren(const TrieChar<T> *curr) const {
        for (size_t i = 0; i < ALPHABET_SIZE; i++) {
            if (curr->character[i]) {
                return true;
            }
        }
        return false;
    }

    const T *getMeaning(const std::string &str) const {
        const TrieChar<T> *temp = this;
        for (size_t i = 0; i < str.length(); i++) {
            temp = temp->character[str[i] - 'a'];
            if (temp == nullptr)
                return " ";
        }

        if (temp->isEndOfWord)
            return temp->meaning;
        return " ";
    }

    void makeNewTrie(TrieChar<T> &node) {
        this->insert(node.getIsEndOfWord(), node.getMeaning());

        for (size_t i = 0; i < ALPHABET_SIZE; i++) {
            if (node.character[i] != nullptr)
                makeNewTrie(node);
        }
    }

    void search(TrieChar<T> *&curr, const std::string &key, TrieChar<T> *&parent) {
        for (size_t i = 0; i < key.length(); i++) {
            for (size_t j = 0; j < ALPHABET_SIZE; j++) {
//              if (curr->character[j] == key[i])
                {
                    parent = curr;
                    curr = curr->character[i];
                    break;
                }
            }
        }
    }

    bool deleteWord(TrieChar<T> *&root, const std::string &key) {
        TrieChar<T> *parent = nullptr;
        TrieChar<T> *curr = root;
        search(curr, key, parent);
        if (curr == nullptr)
            return false;
        if (haveChildren(curr)) {
            curr->isEndOfWord = false;
            curr->meaning = NULL;
            return true;
        }
        while (!haveChildren(curr)) {
            if (curr != root) {
                for (size_t i = 0; i < ALPHABET_SIZE; i++) {
                    if (parent->character[i] == curr)
                        parent->character[i] = nullptr;
                }
            } else
                root = nullptr;
            delete root;
            curr = parent;
            //parent = &curr; //wrong
        }
        return true;
    }

    TrieChar<T> &operator=(const TrieChar<T> &rhs) {
        if (this != &rhs) {
            for (size_t i = 0; i < ALPHABET_SIZE; i++) {
                if (rhs.character[i] != nullptr) {
                    delete this->character[i];
                    this->character[i] = new TrieChar<T>();
                    this->character[i] = rhs.character[i];
                }
            }
        }
        return *this;
    }

    TrieChar<T> &operator+(const TrieChar<T> &rhs) {
        if (this != &rhs) {
            for (size_t i = 0; i < ALPHABET_SIZE; i++) {
                if (this->character[i] != nullptr && rhs.character[i] == nullptr) {
                    this->character[i] = new TrieChar<T>();
                    this->character[i] = rhs.character[i];
                }
            }
        }
        return *this;
    }

    TrieChar<T> &operator+=(const TrieChar<T> &rhs) {
        return *this = *this + rhs;
    }
};