#include "trie.hpp"
#include <iostream>
#include <vector>
#include <algorithm>

bool hasAnotherWord = false;

trie_node* find(const std::string &str,trie_node* root) {
    trie_node* currentNode = root;
    const char* sptr = str.c_str();
    while (*sptr) {
        if(currentNode->children[*sptr] == nullptr) {
            throw 20;
        }
        currentNode = currentNode->children[*sptr];
        sptr++;
    }
    return currentNode;
}

trie_node* addChild(trie_node* node,char child,bool terminal,size_t &size) {
    trie_node* newNode = new trie_node;
    newNode->payload = child;
    newNode->is_terminal = terminal;
    newNode->parent = node;
    if(terminal) {
        size++;
    }
    node->children[child] = newNode;
    hasAnotherWord = true;
    return newNode;
}

bool trie::contains(const std::string& str) const {
    if(str.empty() && m_root->is_terminal == true) {
        return true;
    } else if(str.empty()) {
        return false;
    }
    try {
        trie_node* node = find(str,m_root);
        if(node->is_terminal) {
            return true;
        } else {
            return false;
        }
    }catch(int e) {
        if(e ==20) {
            return false;
        }
    }
    return false;
}


bool trie::insert(const std::string& str) {
    if(contains(str)) {
        return false;
    } else {
        if(str.empty()) {
            m_root->is_terminal = true;
            m_size++;
            return true;
        }
        trie_node* currentNode = m_root;
        const char* sptr = str.c_str();
        int length = 1;

        while (*sptr) {
            if(currentNode->children[*sptr] == nullptr) {
                currentNode = addChild(currentNode,*sptr,length==str.length(),m_size);
                length++;
            }else {
                currentNode = currentNode->children[*sptr];
                if(length == str.length()) {
                    currentNode->is_terminal = true;
                    m_size++;
                }
                length++;
            }
            sptr++;
        }
        return true;
    }
}

void deallocate_node(trie_node* node) {
    for(int i = 0;i<128;i++) {
        if(node->children[i] != nullptr) {
            deallocate_node(node->children[i]);
        }
    }
    delete node;
}




bool trie::erase(const std::string& str) {
    try {
        trie_node* nodeToErase = find(str,m_root);
        if(nodeToErase->is_terminal == true) {
            nodeToErase->is_terminal = false;
            m_size--;
        } else {
            return false;
        }
    }catch(int e) {
        if(e == 20)
            return false;
    }
    return true;
}

std::vector<std::string> trie::search_by_prefix(const std::string& prefix) const {
    std::vector<std::string> foundWords;
    trie_node* currentNode = find(prefix,m_root);
    word_cursor* cursor = new word_cursor(currentNode);
    if(!currentNode->is_terminal) {
        cursor->move_to_next_word();
    }
    while(cursor->has_word()) {
        foundWords.push_back(cursor->read_word());
        cursor->move_to_next_word();
    }
    delete cursor;
    return foundWords;
}
std::vector<std::string> trie::get_prefixes(const std::string& str) const {
    std::vector<std::string> prefixes;
    trie_node* currentNode;
    std::string workingString = str;
    getprefixes:
    try {
        currentNode = find(workingString,m_root);
    } catch(int e) {
        if(e ==20) {
            workingString = workingString.substr(0,workingString.length()-2);
            goto getprefixes;
        }
    }
    int index = 0;
    while(true) {
        if(currentNode->is_terminal) {
            prefixes.push_back(workingString.substr(0,workingString.length()-index));
        }
        currentNode = currentNode->parent;
        if(currentNode == m_root) {
            break;
        }
        index++;
    }
    return prefixes;
}


word_cursor trie::get_word_cursor() const {
    word_cursor cursor = word_cursor(m_root);
    if(!m_root->is_terminal) {
        cursor.move_to_next_word();
    }
    return cursor;
}


size_t trie::size() const {
    return m_size;
}

bool trie::empty() const {
    return m_size == 0;
}

trie::trie(const std::vector<std::string>& strings) :
m_root(new trie_node)
{
    for(size_t i= 0;i<strings.size();i++) {
        insert(strings[i]);
    }
}


trie::trie() :
m_root(new trie_node) {

}


trie::~trie() {
    deallocate_node(m_root);
    m_size = 0;

}
word_cursor::word_cursor(const trie_node* word_ptr):
m_ptr(word_ptr){


}
bool word_cursor::has_word() const {
    return hasAnotherWord;
}
std::string word_cursor::read_word() const {
    const trie_node* currentNode = m_ptr;
    std::string word = "";
    while(true) {
        if(currentNode->payload ==  '\0') {
            break;
        }
        word += currentNode->payload;
        currentNode = currentNode->parent;

    }
    std::reverse(word.begin(),word.end());
    return word;
}

void word_cursor::move_to_next_word() {
    nextword:
    std::string word = read_word();

    for(int i = 0;i<128;i++) {
        if(m_ptr->children[i] != nullptr) {
            m_ptr = m_ptr->children[i];
            if(!m_ptr->is_terminal) {
                goto nextword;
                return;
            } else if(m_ptr->is_terminal){
                return;
            }
        }
    }
    int index = 1;
    while(m_ptr->payload != '\0') {
        m_ptr = m_ptr->parent;
        // m_ptr = return_to_root(m_ptr);
        for(int i = 0;i<128;i++) {
            if(m_ptr->children[i] != nullptr) {
                if(m_ptr->children[i]->payload <= word[word.length()-index]) {
                    continue;
                } else if(!m_ptr->children[i]->is_terminal) {
                    m_ptr = m_ptr->children[i];
                    goto nextword;
                } else if(m_ptr->children[i]->is_terminal) {
                    m_ptr = m_ptr->children[i];
                    return;
                }
            }
        }
        index++;
    }
    hasAnotherWord = false;
}