/**
 * @file trie.cpp
 *
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */

#include <cassert>
#include <sstream>
#include "utf8_utils.hpp"
#include "trie.hpp"

Trie::Trie()
{
    root_=nullptr;
    prefix_="";

    assert(is_empty());
}

Trie::Trie(TrieNode::Ref root_node, std::string const &pref)
{
    root_=root_node;
    prefix_=pref;

    assert(prefix() == pref);
}

bool Trie::is_empty() const
{
    if(root_==nullptr){
        return true;
    }
    return false;
}

const std::string &
Trie::prefix() const
{
    return prefix_;
}

void Trie::set_prefix(const std::string &new_p)
{
    prefix_=new_p;

    assert(prefix() == new_p);
}

bool Trie::is_key() const
{
    assert(!is_empty());

    return root_->is_key();
}

const TrieNode::Ref &
Trie::root() const
{
    return root_;
}

void Trie::set_root(TrieNode::Ref const &new_r)
{
    root_=new_r;

    assert(root() == new_r);
}

bool Trie::has(std::string const &k) const
{
    assert(!is_empty());
    bool found = false;

    typename TrieNode::Ref node=find_node(k);
    found=(node!=nullptr)&&(node->is_key());
    
    return found;
}

/**
 * @brief Helper function to retrieve the keys.
 *
 * This function does a recursive preorder traversal of the trie's nodes
 * keeping the current prefix and the retrieved keys as functions parameters.
 *
 * @param[in] node is the current node.
 * @param[in] prefix is the current prefix.
 * @param[in,out] keys are the retrieved keys.
 */
static void
preorder_traversal(TrieNode::Ref node, std::string prefix,
                   std::vector<std::string> &keys)
{
    if (node->is_key()){
        keys.push_back(prefix);
    }

    node->goto_first_child();
    while (node->current_exists())
    {
        preorder_traversal(node->current_node(), prefix+node->current_symbol(),keys);
        node->goto_next_child();
    }
    
}

void Trie::retrieve(std::vector<std::string> &keys) const
{
    assert(!is_empty());

    if(root()!=nullptr){
        preorder_traversal(root(),prefix(),keys);
    }
}

Trie Trie::child(std::string const &postfix) const
{
    assert(!is_empty());

    auto node = find_node(postfix);

    // Calculamos el prefijo correcto (vacío si no existe, o el acumulado si existe)
    std::string new_pref = (node == nullptr) ? "" : (prefix() + postfix);

    // Usamos new_pref en el constructor, no postfix
    Trie ret_v(node, new_pref);

    assert(ret_v.is_empty() || ret_v.prefix() == (prefix() + postfix));
    return ret_v;
}

bool Trie::current_exists() const
{
    assert(!is_empty());
    bool ret_val = false;

    ret_val=root_->current_exists();

    return ret_val;
}

Trie Trie::current() const
{
    assert(current_exists());

    Trie ret_v(root_->current_node(), prefix() + root_->current_symbol());
    
    return ret_v;
}

const std::string &Trie::current_symbol() const
{
    assert(current_exists());

    return root_->current_symbol();
}

void Trie::insert(std::string const &k)
{
    assert(k != "");

    if(is_empty()){
        root_=TrieNode::create();
    }

    size_t i=0;
    auto node=root();
    while (i < k.size()) {
        std::string sym = get_utf8_char(k, i);
        if(node->has(sym)){
            node = node->child(sym);
        } else {
            auto new_node = TrieNode::create();
            node->set_child(sym, new_node);
            node = new_node;
        }
        i += sym.size(); // <-- ESTA ES LA CLAVE
    }
    node->set_is_key_state(true);
    

    assert(!is_empty());
    assert(has(k));
}

TrieNode::Ref
Trie::find_node(std::string const &pref) const
{
    assert(!is_empty());
    
    TrieNode::Ref node = root_;
    TrieNode::Ref next_node;
    size_t i = 0;
    std::string edge;
    bool matched;

    // Mientras no hayamos consumido todo el prefijo y el nodo exista
    while (i < pref.size() && node != nullptr) {
        matched = false;
        next_node = nullptr;
        
        // Empezamos a mirar los hijos del nodo actual
        node->goto_first_child();

        while (node->current_exists() && !matched) {
            edge = node->current_symbol();

            // CASO 1: El edge coincide exactamente con el siguiente trozo del prefijo
            if (edge == pref.substr(i, edge.size())) {
                i = i + edge.size();
                next_node = node->current_node();
                matched = true;
            }
            // CASO 2: Lo que nos queda de prefijo es el inicio de este edge (Nodo ficticio)
            else if (edge.substr(0, pref.size() - i) == pref.substr(i)) {
                next_node = TrieNode::create();
                
                // Extraemos lo que sobra del edge (Ej: de "panteon" quitamos "pan", queda "teon")
                std::string resto_edge = edge.substr(pref.size() - i);
                
                // Colgamos el nodo original del nodo ficticio usando lo que sobró
                next_node->set_child(resto_edge, node->current_node());
                
                i = pref.size(); // Ya hemos encontrado todo el prefijo
                matched = true;
            }
            // CASO 3: No hay coincidencia, probamos con el siguiente hermano
            else {
                node->goto_next_child();
            }
        }
        // Avanzamos al siguiente nivel del árbol (o al ficticio, o a nullptr si no hubo match)
        node = next_node;
    }

    return node;
}
std::ostream &
operator<<(std::ostream &out, const Trie &trie) noexcept
{
    if (trie.is_empty())
        out << "[]";
    else
        out << "[ '" << trie.prefix() << "' " << *trie.root() << " ]";
    return out;
}

std::istream &
operator>>(std::istream &in, Trie &trie) noexcept(false)
{
    char c;
    if (!(in >> c) || c != '[')
        throw std::runtime_error("Wrong input format");

    if (!(in >> c))
        throw std::runtime_error("Wrong input format");

    if (c == ']') {
        trie = Trie();
        return in;
    }

    if (c != '\'')
        throw std::runtime_error("Wrong input format");
    in.putback(c);

    std::string prefix;
    if (!read_quoted_string(in, prefix))
        throw std::runtime_error("Wrong input format");

    auto root_node = TrieNode::create();
    if (!(in >> *root_node))
        throw std::runtime_error("Wrong input format");

    if (!(in >> c) || c != ']')
        throw std::runtime_error("Wrong input format");

    trie = Trie(root_node, prefix);
    return in;
}

bool Trie::find_symbol(const std::string &symbol)
{
    assert(!is_empty());
    bool found = false;

    found=root_->find_child(symbol);

    assert(!found || current_exists());
    assert(found || !current_exists());
    assert(!current_exists() || current_symbol() == symbol);
    return found;
}

void Trie::goto_first_symbol()
{
    assert(!is_empty());
    
    root_->goto_first_child();

    assert(!current_exists() ||
           current().prefix() == (prefix() + current_symbol()));
}

void Trie::goto_next_symbol()
{
    assert(current_exists());

    root_->goto_next_child();

}

void Trie::compact()
{
    if(root()!=nullptr){
        root_->compact();
    }
}