// Created by Samvel Khalatyan on Jan 19, 2014
// Copyright (c) 2014 Samvel Khalatyan. All rights reserved
//
// Use of this source code is governed by a license that can be found in
// the LICENSE file.

#ifndef CONTAINER_BINARY_TREE
#define CONTAINER_BINARY_TREE

#include <ostream>
#include <utility>

namespace vs
{
    template<typename Key, typename T>
    class Node
    {
        public:
            inline Node(const Key &k):
                _key {k}
            {}

            ~Node();

            inline Key key() const noexcept { return _key; }

            inline T &value() noexcept { return _value; }
            inline const T &value() const noexcept { return _value; }

            inline Node *left() const noexcept { return _left; }
            inline void left(Node *l) noexcept { _left = l; }

            inline Node *right() const noexcept { return _right; }
            inline void right(Node *r) noexcept { _right = r; }

            size_t size() const;

            void print(std::ostream &) const;

        private:
            Key _key;
            T _value;

            Node *_left {nullptr};
            Node *_right {nullptr};
    };

    template<typename Key, typename T>
    class BinaryTree
    {
        public:
            using value_type = std::pair<Key, T>;

            inline BinaryTree() {};
            ~BinaryTree();

            T &operator[](const Key &);

            inline bool empty() const noexcept { return nullptr == _parent; }

            value_type min() const;
            value_type max() const;

            size_t size() const;

            void print(std::ostream &) const;

        private:
            using node_type = Node<Key, T>;

            node_type *_parent {nullptr};
    };

    template<typename Key, typename T>
    std::ostream &operator <<(std::ostream &, const BinaryTree<Key, T> &);

    template<typename Key, typename T>
    std::ostream &operator <<(std::ostream &, const Node<Key, T> &);

    template<typename Key, typename T>
    std::ostream &operator <<(std::ostream &, const std::pair<Key, T> &);
}

// -- Node
template<typename Key, typename T>
vs::Node<Key, T>::~Node()
{
    if (_left)
        delete _left;

    if (_right)
        delete _right;
}

template<typename Key, typename T>
void vs::Node<Key, T>::print(std::ostream &os) const
{
    if (_left)
        os << *_left;

    os << _key << ':' << _value << ' ';

    if (_right)
        os << *_right;
}

template<typename Key, typename T>
size_t vs::Node<Key, T>::size() const
{
    return (_left ? _left->size() : 0) +
           (_right ? _right->size() : 0) +
           1;
}

// -- Binary Tree
template<typename Key, typename T>
vs::BinaryTree<Key, T>::~BinaryTree()
{
    if (not empty())
        delete _parent;
}

template<typename Key, typename T>
T &vs::BinaryTree<Key, T>::operator[](const Key &k)
{
    if (empty())
    {
        _parent = new node_type{k};
        return _parent->value();
    }

    node_type *node {_parent};
    while(node->key() != k)
    {
        if (k < node->key())
        {
            if (node->left())
                node = node->left();
            else
            {
                node->left(new node_type{k});
                node = node->left();
            }
        }
        else
        {
            if (node->right())
                node = node->right();
            else
            {
                node->right(new node_type{k});
                node = node->right();
            }
        }
    }

    return node->value();
}

template<typename Key, typename T>
typename vs::BinaryTree<Key, T>::value_type vs::BinaryTree<Key, T>::min() const
{
    for(node_type *node {_parent}; node; node = node->left())
        if (not node->left())
            return std::make_pair(node->key(), node->value());

    return value_type{};
}

template<typename Key, typename T>
typename vs::BinaryTree<Key, T>::value_type vs::BinaryTree<Key, T>::max() const
{
    for(node_type *node {_parent}; node; node = node->right())
        if (not node->right())
            return std::make_pair(node->key(), node->value());

    return value_type{};
}

template<typename Key, typename T>
size_t vs::BinaryTree<Key, T>::size() const
{
    return empty() ? 0 : _parent->size();
}

template<typename Key, typename T>
void vs::BinaryTree<Key, T>::print(std::ostream &os) const
{
    if (not empty())
        os << *_parent;
}

// -- helpers
template<typename Key, typename T>
std::ostream &vs::operator <<(std::ostream &os, const BinaryTree<Key, T> &t)
{
    t.print(os);

    return os;
}

template<typename Key, typename T>
std::ostream &vs::operator <<(std::ostream &os, const Node<Key, T> &n)
{
    n.print(os);

    return os;
}

template<typename Key, typename T>
std::ostream &vs::operator <<(std::ostream &os, const std::pair<Key, T> &p)
{
    return os << p.first << ':' << p.second;
}

#endif
