#include "tree.h"

#include <iomanip>
#include <queue>
#include <stack>

struct Tree::Node
{
    int key;
    Node* left { nullptr };
    Node* right { nullptr };
};

void inorder_add(Tree::Node const* node, std::vector<int>& result)
{
    // TODO: Implementera denna
}

void preorder_add(Tree::Node const* node, std::vector<int>& result)
{
    // TODO: Implementera denna
}

void postorder_add(Tree::Node const* node, std::vector<int>& result)
{
    // TODO: Implementera denna
}

Tree::~Tree()
{
    std::stack<Node*> nodes { };
    nodes.push(root);

    while (not nodes.empty())
    {
        Node* node { nodes.top() };
        nodes.pop();

        if (node->left != nullptr)
            nodes.push(node->left);

        if (node->right != nullptr)
            nodes.push(node->right);

        delete node;
    }
}

void Tree::insert(int key)
{
    Node** current { &root };
    while (*current != nullptr)
    {   
        // Gå vänster i trädet
        if (key < (*current)->key)
            current = &((*current)->left);

        // Gå höger i trädet
        else if (key > (*current)->key)
            current = &((*current)->right);

        // Om det redan finns så är vi klara
        else return;
    }

    *current = new Node { key };
}

bool Tree::contains(int key) const
{
    Node* current { root };
    while (current != nullptr)
    {
        if (key == current->key)
            return true;
        else if (key < current->key)
            current = current->left;
        else if (key > current->key)
            current = current->right;
    }
    return false;
}

void print_node(std::ostream& os, Tree::Node const* node, unsigned indent)
{
    if (node == nullptr)
        return;

    os << std::setfill(' ');
    if (node->right != nullptr)
    {
        print_node(os, node->right, indent + 4);
        os << std::setw(indent + 2) << "" << "/" << std::endl;
    }

    os << std::setw(indent) << "" << node->key << std::endl;

    if (node->left != nullptr)
    {
        os << std::setw(indent + 2) << "" << "\\" << std::endl;
        print_node(os, node->left, indent + 4);
    }
}

void Tree::print(std::ostream& os) const
{
    print_node(os, root, 0);
}

std::vector<int> Tree::inorder() const
{
    std::vector<int> result { };
    inorder_add(root, result);
    return result;
}

std::vector<int> Tree::preorder() const
{
    std::vector<int> result { };
    preorder_add(root, result);
    return result;
}

std::vector<int> Tree::postorder() const
{
    std::vector<int> result { };
    postorder_add(root, result);
    return result;
}