#include "trie.h"

struct Trie::Node
{
    // Noden som representerar om nästa tecken är en nolla.
    Node* zero { nullptr };

    // Noden som representerar om nästa tecken är en etta.
    Node* one { nullptr };

    // Sant om denna nod representerar en komplett sträng, falskt om denna nod
    // bara är en del av ett prefix.
    bool  valid { false };
};

void insert_node(Trie::Node*& node, std::string const& digits);
Trie::Node const* find_node(Trie::Node const* node, std::string const& digits);
void deallocate_node(Trie::Node* node);

void find_all(Trie::Node const* node, std::string const& prefix, std::vector<std::string>& result)
{
    // Implementera denna funktion
}

void insert_node(Trie::Node*& node, std::string const& digits)
{
    if (node == nullptr)
        node = new Trie::Node;

    if (digits.empty())
        node->valid = true;
    else
    {
        std::string next { digits.substr(1) };

        if (digits.front() == '0')
            return insert_node(node->zero, next);
        
        if (digits.front() == '1')
            return insert_node(node->one, next);
    }
}

Trie::Node const* find_node(Trie::Node const* node, std::string const& digits)
{
    if (node == nullptr)
        return nullptr;

    if (digits.empty())
        return node;

    std::string next { digits.substr(1) };

    if (digits.front() == '0')
        return find_node(node->zero, next);
    
    if (digits.front() == '1')
        return find_node(node->one, next);

    return nullptr;
}

void deallocate_node(Trie::Node* node)
{
    if (node == nullptr)
        return;

    deallocate_node(node->zero);
    deallocate_node(node->one);

    delete node;
}

Trie::~Trie()
{
    deallocate_node(root);
}

void Trie::insert(std::string const& digits)
{
    insert_node(root, digits);
}

bool Trie::contains(std::string const& digits) const
{
    Node const* node { find_node(root, digits) };
    return node != nullptr and node->valid;
}

std::vector<std::string> Trie::all_with_prefix(std::string const& prefix) const
{
    std::vector<std::string> result { };
    find_all(find_node(root, prefix), prefix, result);
    return result;
}