#ifndef FXTREE_H
#define FXTREE_H

#include <queue>
#include <stack>
#include "exception.h"

namespace fx
{

    template<class Key, class Value> class Tree;

    /**
     * @brief Класс узла Node
     *
     *        |--------------|
     *        |    _key      | - Ключ
     *        |--------------|
     *        |   _value     | - Значение
     *        |--------------|
     *        | Node* _left  | - Левый подузел
     *        |--------------|
     *        | Node* _right | - Правый подузел
     *        |--------------|
     *
     *        Узел - лист: _left == _right == 0;
     *        Узел - однопутевой: (_left == 0) xor (_right == 0)
     *        Узел - двупутевой: (_left != 0) и (_right != 0)
     */
    template<class Key, class Value> class Node
    {
    public:
        typedef Key key_type;
        typedef Value value_type;
        typedef Node<key_type, value_type> self;

        friend class Tree<Key, Value>;

    private:
        /**
         * @var Ключ
         */
        key_type _key;

        /**
         * @var Значение
         */
        value_type _value;

        /**
         * @var Левый сын
         */
        self* _left;

        /**
         * @var Правый сын
         */
        self* _right;

    public:

        /**
         * @brief       Создает узел с ключем k, значением v, левывм сыном left и правым сыном right
         * @param k     Ключ
         * @param v     Значение
         * @param left  Левый сын
         * @param right Правый сын
         */
        Node(const key_type& k = key_type(), const value_type& v = value_type())
        {
            _key   = k;
            _value = v;
            _left  = 0;
            _right = 0;
        }

        /**
         * @brief       Создает лист с ключем node._key, значением node._value
         * @param node  Существующий узел
         */
        Node(const self& node)
        {
            _key   = node._key;
            _value = node._value;
            _left  = 0;
            _right = 0;
        }

        /**
         * @brief       Присваивает узлу ключ node._key, значение node._value, делает текущий узел листом
         * @param node  Существующий узел
         */
        self& operator = (const self& node)
        {
            _key   = node._key;
            _value = node._value;
            delete _left;  _left  = 0;
            delete _right; _right = 0;
            return *this;
        }

        /**
         * @brief       Меняет местами значения элементов, учитывая подузлы
         * @param node  Существующий узел
         */
        self& swap(self& node)
        {
            std::swap(_key, node._key);
            std::swap(_value, node._value);
            std::swap(_left, node._left);
            std::swap(_right, node._right);
            return *this;
        }

        /**
         * @brief Удаляет узел со всеми сыновьями
         */
        ~Node()
        {
            delete _left;
            delete _right;
        }

        /**
         * @return Указатель на правого сына
         */
        inline self* right()
        {
            return _right;
        }

        inline const self* right() const
        {
            return _right;
        }

        /**
         * @return Указатель на левого сына
         */
        inline self* left()
        {
            return _left;
        }

        inline const self* left() const
        {
            return _left;
        }

        /**
         * @return Ключ
         */
        inline const key_type& key() const
        {
            return _key;
        }

        /**
         * @return Значение
         */
        inline value_type& value()
        {
            return _value;
        }

        inline const value_type& value() const
        {
            return _value;
        }

        /**
         * @brief   проверяет, является ли узел листом
         * @return  true, если узел является листом
         *          false, если не является
         */
        inline bool leaf() const
        {
            return !_left && !_right;
        }

        /**
         * @brief   проверяет, является ли узел однопутевым
         * @return  true, если узел является однопутевым
         *          false, если не является
         */
        inline bool node_one() const
        {
            return (_left && !_right) || (!_left && _right);
        }

        /**
         * @brief   проверяет, является ли узел двупутевым
         * @return  true, если узел является двупутевым
         *          false, если не является
         */
        inline bool node_two() const
        {
            return _left && _right;
        }

    private:
        void assign(const self& node)
        {
            operator = (node);

            if(node._left) {
                _left = new self();
                _left->assign(*(node._left));
            }

            if(node._right) {
                _right = new self();
                _right->assign(*(node._right));
            }
        }
    };

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если у n1 и n2 равны ключи и значения, сыновья не учитываются
     *          false, в противном случае
     */
    template<class Key, class Value> bool operator == (Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return (n1.key() == n2.key()) && (n1.value() == n2.value());
    }

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если у n1 и n2 не равны ключи или значения, сыновья не учитываются
     *          false, в противном случае
     */
    template<class Key, class Value> inline bool operator != (Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return !(n1 == n2);
    }

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если ключ n1 > ключа n2
     *          false, в противном случае
     */
    template<class Key, class Value> bool operator > (Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return n1.key() > n2.key();
    }

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если ключ n1 >= ключа n2
     *          false, в противном случае
     */
    template<class Key, class Value> bool operator >= (Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return n1.key() >= n2.key();
    }

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если ключ n1 < ключа n2
     *          false, в противном случае
     */
    template<class Key, class Value> bool operator < (Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return n1.key() < n2.key();
    }

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если ключ n1 <= ключа n2
     *          false, в противном случае
     */
    template<class Key, class Value> bool operator <= (Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return n1.key() <= n2.key();
    }

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если n1 == n2, и их сыновья равны рекурсивно
     *          false, в противном случае
     */
    template<class Key, class Value> bool equal(Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return (n1 == n2)
                && ( (n1.left()  == n2.left() ) || ( (n1.left()  && n2.left() ) && equal(*(n1.left()),  *(n2.left()) ) ) )
                && ( (n1.right() == n2.right()) || ( (n1.right() && n2.right()) && equal(*(n1.right()), *(n2.right())) ) );
    }

    /**
     * @brief   Сравнивает узлы n1 и n2
     * @param n1
     * @param n2
     * @return  true, если n1 != n2, или их сыновья не равны рекурсивно
     *          false, в противном случае
     */
    template<class Key, class Value> inline bool not_equal(Node<Key, Value>& n1, Node<Key, Value>& n2)
    {
        return !equal(n1, n2);
    }

    /**
     * @brief Класс дерева Tree
     *
     *        Дерево представляет собой совокупность узлов Node. Каждый узел может иметь не более 2 подузлов.
     *        В дереве хранится указатель на корень этого дерева.
     *
     *        |-------------|
     *        | Node* _root |
     *        |-------------|
     *
     *        Для любого узла node этого дерева: node->left()->key() <= node->key() <= node->right()->key();
     *        Дерево пустое/непустое: _root == 0 / _root != 0;
     */
    template<class Key, class Value> class Tree
    {

        template<class N = Node<Key, Value> > class Iterator_Depth;
        template<class N = Node<Key, Value> > class Iterator_Width;

    public:
        typedef Tree<Key, Value> self;
        typedef Node<Key, Value> Node;
        typedef Key key_type;
        typedef Value value_type;

        typedef Iterator_Width<> iterator_width;
        typedef const Iterator_Width<const Node> const_iterator_width;
        typedef Iterator_Depth<> iterator_depth;
        typedef const Iterator_Depth<const Node> const_iterator_depth;
        typedef iterator_width iterator;
        typedef const_iterator_width const_iterator;


    public:

        /**
         * @brief   Создает пустое дерево
         */
        Tree();

        /**
         * @brief   Создает дерево с корневым узлом Node(k, v)
         * @param k Ключ корня
         * @param v Значение корня
         */
        Tree(const key_type&, const value_type&);

        /**
         * @brief       Создает дерево с корневым узлом Node(node)
         * @param node
         */
        Tree(const Node& node);
        self& operator = (const Node&);

        /**
         * @brief       Создает копию дерева tree
         * @param tree
         */
        Tree(const self& tree);
        self& operator = (const self&);

        /**
         * @brief       Обменивает значения узлов
         * @param tree
         */
        self& swap(self&);

        /**
         * @brief   Уничтожает обьект
         */
        ~Tree();


        /**
         * @return  Указатель на корневой узел
         */
        Node* root();
        const Node* root() const;

        /**
         * @brief   Поиск узла по ключу
         * @param k Ключ узла
         * @return  Ссылка на узел с ключом k
         * @throw   Tree_Exception, если ключ не будет найден
         */
        Node& find(const key_type&);
        const Node& find(const key_type&) const;

        /**
         * @brief   Добавление узла (k, v) в дерево
         * @param k Ключ узла
         * @param v Значение узла
         * @return  Ссылка на себя
         */
        self& add(const key_type&, const value_type&);

        /**
         * @brief   Добавление узла (k, v) в корень дерева
         * @param k Ключ узла
         * @param v Значение узла
         * @return  Ссылка на себя
         */
        self& add_to_root(const key_type&, const value_type&);

        /**
         * @brief   Удаление узла по ключу
         * @param k Ключ узла
         * @return  Ссылка на себя
         */
        self& remove(const key_type&);

        /**
         * @brief   Очистка дерева - удаляет все узлы дерева, оставляя дерево пустым
         * @return  Ссылка на себя
         */
        self& clear();

        /**
         * @return Количество узлов в дереве
         */
        inline unsigned int count() const;

        /**
         * @param   type :
         *          &Node::leaf      - лист
         *          &Node::node_one  - узел с одним сыном
         *          &Node::node_two  - узел с двумя сыновьями
         *          0                - узел (аналог count())
         * @return  Количество узлов в дереве, удовлетворяющих параметру type
         */
        unsigned int count_if(bool (Node::*type)() const) const;

        /**
         * @param n Уровень в дереве, начиная с 1-го
         * @return  Количество узлов в дереве
         */
        unsigned int on_level(unsigned int n) const;

        /**
         * @param n Уровень в дереве, начиная с 1-го
         * @param   type :
         *          &Node::leaf      - лист
         *          &Node::node_one  - узел с одним сыном
         *          &Node::node_two  - узел с двумя сыновьями
         *          0                - узел (аналог on_level(n))
         * @return  Количество узлов в дереве на уровне n, удовлетворяющих параметру type
         */
        unsigned int on_level_if(unsigned int n, bool (Node::*type)() const) const;

        /**
         * @return  true, если дерево пустое
         *          false, если дерево непустое
         */
        bool empty() const;

        /**
         * @return  Высота дерева
         */
        unsigned int height() const;

        /**
         * @return  Ширина дерева
         */
        unsigned int width() const;

        /**
         * @brief   Является ли дерево деревом поиска
         * @return  true, если является
         *          false, если не является
         */
        bool search_tree() const;

        /**
         * @brief   Поиск самого длинного вырожденного поддерева
         * @return  Высота (длинна) самого длинного вырожденного поддерева
         */
        unsigned int degenerated() const;

        /**
         * @brief   Поиск самого длинного полного поддерева
         * @return  Высота (длинна) самого длинного полного поддерева
         */
        unsigned int full() const;

        /**
         * @brief   Поиск самого длинного сбалансированного поддерева
         * @return  Высота (длинна) самого сбалансированного полного поддерева
         */
        unsigned int balanced() const; // ToDo

        /**
         * @brief   Поиск самого длинного идеально сбалансированного поддерева
         * @return  Высота (длинна) самого длинного идеально сбалансированного поддерева
         */
        unsigned int balanced_ideal() const; // ToDo

        /**
         * @brief   Обход дерева в глубину (ЛКП)
         * @param   Фунция, определяющая, что нужно сделать с узлом:
         *          void f(const Node&);
         */
        template<class Function> inline const self& infix_traverse(Function&) const;
        template<class Function> inline self& infix_traverse(Function&);

        /**
         * @brief   Обход дерева в глубину (KЛП)
         * @param   Фунция, определяющая, что нужно сделать с узлом:
         *          void f(const Node&);
         */
        template<class Function> inline const self& prefix_traverse(Function&) const;
        template<class Function> inline self& prefix_traverse(Function&);

        /**
         * @brief   Обход дерева в глубину (ЛПК)
         * @param   Фунция, определяющая, что нужно сделать с узлом:
         *          void f(const Node&);
         */
        template<class Function> inline const self& postfix_traverse(Function&) const;
        template<class Function> inline self& postfix_traverse(Function&);

        /**
         * @brief   Обход дерева в ширину
         * @param   Фунция, определяющая, что нужно сделать с узлом:
         *          void f(const Node&);
         */
        template<class Function> inline const self& width_traverse(Function&) const;
        template<class Function> inline self& width_traverse(Function&);

        /**
         * @brief   Итератор, обход в ширину
         * @return  Итератор, указывающий на начало дерева
         */
        iterator begin();
        const_iterator begin() const;

        /**
         * @brief   Итератор, обход в ширину
         * @return  Итератор, указывающий на конец дерева
         */
        iterator end();
        const_iterator end() const;

        /**
         * @brief   Итератор, обход в глубину
         * @return  Итератор, указывающий на начало дерева
         */
        iterator_depth begin_depth();
        const_iterator_depth begin_depth() const;

        /**
         * @brief   Итератор, обход в глубину
         * @return  Итератор, указывающий на конец дерева
         */
        iterator_depth end_depth();
        const_iterator_depth end_depth() const;

        /**
         * @brief   Итератор, обход в ширину
         * @return  Итератор, указывающий на начало дерева
         */
        iterator_width begin_width();
        const_iterator_width begin_width() const;

        /**
         * @brief   Итератор, обход в ширину
         * @return  Итератор, указывающий на конец дерева
         */
        iterator_width end_width();
        const_iterator_width end_width() const;

    private:

        /**
         * @var     Корень дерева
         */
        Node* _root;

    private:

        /**
         * @brief Итератор, обход в ширину, слева направо
         */
        template<class N> class Iterator_Width
        {
        public:
            typedef Iterator_Width<N> self;
            typedef Tree<Key, Value> Tree;
            //typedef Node<Key, Value> Node;

            /**
             * @brief       Создает итератор
             * @param tree  Дерево, которое будем обходить
             * @param end   true - итератор находится в конце дерева
             *              false - итератор находится в начале дерева
             */
            Iterator_Width(Tree& tree, bool end = false): _tree(tree)
            {
                if(!end && !_tree.empty()) {
                    _queue.push(tree.root());
                }
            }

            Iterator_Width(const Tree& tree, bool end = false): _tree(tree)
            {
                if(!end && !_tree.empty()) {
                    _queue.push(_tree.root());
                }
            }

            /**
             * @brief       Возвращает значение текущего узла
             * @return      Значение текущего узла
             */
            Value& operator * ()
            {
               return _queue.front()->value();
            }

            const Value& operator * () const
            {
               return _queue.front()->value();
            }

            /**
             * @brief       Возвращает указатель на текущий узел
             * @return      Указатель на текущий узел
             */
            Node* operator -> ()
            {
                return _queue.front();
            }

            const Node* operator -> () const
            {
                return _queue.front();
            }

            /**
             * @brief       Переход на следующий элемент (префиксный ++)
             */
            const self& operator ++ () const
            {
                N* p = _queue.front();
                _queue.pop();
                if(p->left()) { _queue.push(p->left()); }
                if(p->right()) { _queue.push(p->right()); }
                return *this;
            }

            /**
             * @brief       Равенство другому итератору
             * @return      true - если равны
             *              false - если не равны
             */
            bool operator == (const self& i) const
            {
                return (&_tree == &i._tree) && (_queue.size() == i._queue.size());
            }

            /**
             * @brief       Неравенство другому итератору
             * @return      true - если не равны
             *              false - если равны
             */
            bool operator != (const self& i) const
            {
                return !(*this == i);
            }

        private:
            const Tree& _tree;
            mutable std::queue< N* > _queue;

        };

        /**
         * @brief Итератор, обход в глубину, ПЛК
         */
        template<class N> class Iterator_Depth
        {
        public:
            typedef Iterator_Depth<N> self;
            typedef Tree<Key, Value> Tree;
            //typedef Node<Key, Value> Node;

            /**
             * @brief       Создает итератор
             * @param tree  Дерево, которое будем обходить
             * @param end   true - итератор находится в конце дерева
             *              false - итератор находится в начале дерева
             */
            Iterator_Depth(Tree& tree, bool end = false): _tree(tree)
            {
                if(!end && !_tree.empty()) {
                    _stack.push(tree.root());
                }
            }

            Iterator_Depth(const Tree& tree, bool end = false): _tree(tree)
            {
                if(!end && !_tree.empty()) {
                    _stack.push(_tree.root());
                }
            }

            /**
             * @brief       Возвращает значение текущего узла
             * @return      Значение текущего узла
             */
            Value& operator * ()
            {
               return _stack.top()->value();
            }

            const Value& operator * () const
            {
               return _stack.top()->value();
            }

            /**
             * @brief       Возвращает указатель на текущий узел
             * @return      Указатель на текущий узел
             */
            Node* operator -> ()
            {
                return _stack.top();
            }

            const Node* operator -> () const
            {
                return _stack.top();
            }

            /**
             * @brief       Переход на следующий элемент (префиксный ++)
             */
            const self& operator ++ () const
            {
                N* p = _stack.top();
                _stack.pop();
                if(p->left()) { _stack.push(p->left()); }
                if(p->right()) { _stack.push(p->right()); }
                return *this;
            }

            /**
             * @brief       Равенство другому итератору
             * @return      true - если равны
             *              false - если не равны
             */
            bool operator == (const self& i) const
            {
                return (&_tree == &i._tree) && (_stack.size() == i._stack.size());
            }

            /**
             * @brief       Неравенство другому итератору
             * @return      true - если не равны
             *              false - если равны
             */
            bool operator != (const self& i) const
            {
                return !(*this == i);
            }

        private:
            const Tree& _tree;
            mutable std::stack< N* > _stack;

        };

        class _count
        {
            bool (Node::*type)() const;
        public:
            unsigned int count;
            _count(bool (Node::*t)() const = 0): type(t), count(0) {}
            void operator () (const Node& node)
            {
                if(type) {
                    if((node.*type)()) ++count;
                } else {
                     ++count;
                }
            }
        };

        Node& _find(Node* node, const key_type& k);
        void _add(Node* node, const key_type& k, const value_type& v);
        void _remove(Node* node, const key_type& k, Node* prev = 0);
        unsigned int _on_level(unsigned int n, Node* node, bool (Node::*f)() const = 0) const;
        unsigned int _height(Node* node) const;
        void _width(Node* node, unsigned int i, unsigned int* array) const;
        bool _search_tree(Node* node, key_type min, key_type max) const;
        unsigned int _degenerated(Node* node, unsigned int& max) const;
        unsigned int _full(Node* node, unsigned int& max) const;
        unsigned int _balanced(Node* node, unsigned int& max) const;
        unsigned int _balanced_ideal(Node* node, unsigned int& max) const;
        void _cut_left(Node* node, key_type k, Node* cur, Node* prev);
        void _cut_right(Node* node, key_type k, Node* cur, Node* prev);

        template<class Function> void _infix_traverse(const Node* node, Function& f) const;
        template<class Function> void _infix_traverse(Node* node, Function& f);
        template<class Function> void _prefix_traverse(const Node* node, Function& f) const;
        template<class Function> void _prefix_traverse(Node* node, Function& f);
        template<class Function> void _postfix_traverse(const Node* node, Function& f) const;
        template<class Function> void _postfix_traverse(Node* node, Function& f);
        template<class Function> void _width_traverse(const Node* node, Function& f, std::queue< const Node* >& q) const;
        template<class Function> void _width_traverse(Node* node, Function& f, std::queue< Node* >& q);
    };

    template<class Key, class Value> inline bool operator == (Tree<Key, Value>& n1, Tree<Key, Value>& n2)
    {
        return equal(*(n1.root()), *(n2.root()));
    }

    template<class Key, class Value> inline bool operator != (Tree<Key, Value>& n1, Tree<Key, Value>& n2)
    {
        return !(n1 == n2);
    }



    template<class Key, class Value> bool operator == (Tree<Key, Value>&, Tree<Key, Value>&);
    template<class Key, class Value> bool operator != (Tree<Key, Value>&, Tree<Key, Value>&);

    template<class Key, class Value> Node<Key, Value>& Tree<Key, Value>::_find(Node* node, const key_type& k)
    {
        if(node->key() > k) {
            if(node->left()) {
                return _find(node->left(), k);
            } else {
                throw fx::exception(1, "There is no node with such key");
            }
        } else if(node->key() < k) {
            if(node->right()) {
                return _find(node->right(), k);
            } else {
                throw fx::exception(1, "There is no node with such key");
            }
        } else {
            return *node;
        }
    }

    template<class Key, class Value> void Tree<Key, Value>::_add(Node* node, const key_type& k, const value_type& v)
    {
        if(node->_key > k) {
            if(node->_left) {
                _add(node->_left, k, v);
            } else {
                node->_left = new Node(k, v);
            }
        } else if(node->_key < k) {
            if(node->_right) {
                _add(node->_right, k, v);
            } else {
                node->_right = new Node(k, v);
            }
        }
    }

    template<class Key, class Value> void Tree<Key, Value>::_remove(Node* node, const key_type& k, Node* prev)
    {
        if(node->_key == k) {

            if( node->node_one() ) {
                // Один из подузлов существует, второй - нет
                // Сдвигаем существующий узел на место текущего

                Node* exist = node->_right ? node->_right : node->_left;
                *node = *exist;

                operator delete(exist);
            } else if(node->node_two()) {
                // Оба подузла существуют
                // Помещаем самый левый узел прового подузла на место текущего

                Node* cur = node->_right;
                if(!cur->_left) {
                    node->_key = cur->_key;
                    node->_value = cur->_value;
                    node->_right = cur->_right;

                    operator delete(cur);
                } else {

                    while(cur->_left->_left)
                        cur = cur->_left;

                    Node* last = cur->_left;

                    node->_key = last->_key;
                    node->_value = last->_value;

                    cur->_left = last->_right;
                    operator delete(last);
                }
            } else {
                // Подузлов не существует, удаляем текущий элемент
                if(prev) {
                    if(prev->_left == node) {
                        delete prev->_left;
                        prev->_left = 0;
                    } else {
                        delete prev->_right;
                        prev->_right = 0;
                    }
                } else {
                    delete _root;
                    _root = 0;
                }
            }
        } else if(node->_key > k) {
            if(node->_left) {
                _remove(node->_left, k, node);
            }
        } else {
            if(node->_right) {
                _remove(node->_right, k, node);
            }
        }
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::_on_level(unsigned int n, Node* node, bool (Node::*f)() const) const
    {
        if(n <= 1) {
            if((f && (node->*f)()) || !f) {
                return 1;
            } else {
                return 0;
            }
        }
        int l = node->left()  ? _on_level(n - 1, node->left(), f) : 0;
        int r = node->right() ? _on_level(n - 1, node->right(), f) : 0;
        return l + r;
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::_height(Node* node) const
    {
        if(node->leaf()) { return 1; }
        int l = node->left() ? _height(node->left()) : 1;
        int r = node->right() ? _height(node->right()) : 1;
        return ((r > l) ? r : l) + 1;
    }

    template<class Key, class Value> void Tree<Key, Value>::_width(Node* node, unsigned int i, unsigned int* array) const
    {
        array[i++]++;
        if(node->left()) {
            _width(node->left(), i, array);
        }
        if(node->right()) {
            _width(node->right(), i, array);
        }
    }

    template<class Key, class Value> bool Tree<Key, Value>::_search_tree(Node* node, key_type min, key_type max) const
    {
        if(node->key() > min && node->key() < max) {
            if(node->leaf()) {
                return true;
            } else {
                bool l = node->left() ? _search_tree(node->left(), min, node->key()) : true;
                bool r = node->right() ? _search_tree(node->right(), node->key(), max) : true;
                return l && r;
            }
        } else {
            return false;
        }
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::_degenerated(Node* node, unsigned int& max) const
    {
        if(node->leaf()) {
            return 1;
        } else if(node->node_two()) {
            unsigned int l = _degenerated(node->left(), max);
            unsigned int r = _degenerated(node->right(), max);
            unsigned int m = (r > l) ? r : l;
            max = (max > m) ? max : m;
            return 0;
        } else {
            Node* exist = node->left() ? node->left() : node->right();
            return _degenerated(exist, max) + 1;
        }
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::_full(Node* node, unsigned int& max) const
    {
        if(node->leaf()) {
            return 1;
        } else if(node->node_two()) {
            unsigned int l = _full(node->left(), max);
            unsigned int r = _full(node->right(), max);
            unsigned int m = (r > l) ? l : r;
            return m + 1;
        } else {
            Node* exist = node->left() ? node->left() : node->right();
            unsigned int m = _full(exist, max);
            max = (max > m) ? max : m;
            return 0;
        }
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::_balanced(Node* node, unsigned int& max) const
    {
        return 0;
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::_balanced_ideal(Node* node, unsigned int& max) const
    {
        return 0;
    }

    template<class Key, class Value> void Tree<Key, Value>::_cut_left(Node* node, key_type k, Node* cur, Node* prev)
    {
        while(cur && k < cur->_key) {
            prev = cur;
            cur = cur->_left;
        }
        if(!cur) {
            if(node->_key == k) {
                node->_left = 0;
            } else {
                node->_right = 0;
            }
        } else {
            if(node->_key == k) {
                node->_left = cur;
            } else {
                node->_right = cur;
            }
            if(cur->_right) {
                _cut_right(prev, k, cur->_right, cur);
            } else {
                prev->_left = 0;
            }
        }
    }

    template<class Key, class Value> void Tree<Key, Value>::_cut_right(Node* node, key_type k, Node* cur, Node* prev)
    {
        while(cur && k > cur->_key) {
            prev = cur;
            cur = cur->_right;
        }
        if(!cur) {
            if(node->_key == k) {
                node->_right = 0;
            } else {
                node->_left = 0;
            }
        } else {
            if(node->_key == k) {
                node->_right = cur;
            } else {
                node->_left = cur;
            }
            if(cur->_left) {
                _cut_left(prev, k, cur->_left, cur);
            } else {
                prev->_right = 0;
            }
        }
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_infix_traverse(const Node* node, Function& f) const
    {
        if(node->left()) _infix_traverse(node->left(), f);
        f(*node);
        if(node->right()) _infix_traverse(node->right(), f);
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_infix_traverse(Node* node, Function& f)
    {
        if(node->left()) _infix_traverse(node->left(), f);
        f(*node);
        if(node->right()) _infix_traverse(node->right(), f);
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_prefix_traverse(const Node* node, Function& f) const
    {
        f(*node);
        if(node->left()) _prefix_traverse(node->left(), f);
        if(node->right()) _prefix_traverse(node->right(), f);
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_prefix_traverse(Node* node, Function& f)
    {
        f(*node);
        if(node->left()) _prefix_traverse(node->left(), f);
        if(node->right()) _prefix_traverse(node->right(), f);
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_postfix_traverse(const Node* node, Function& f) const
    {
        if(node->left()) _postfix_traverse(node->left(), f);
        if(node->right()) _postfix_traverse(node->right(), f);
        f(*node);
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_postfix_traverse(Node* node, Function& f)
    {
        if(node->left()) _postfix_traverse(node->left(), f);
        if(node->right()) _postfix_traverse(node->right(), f);
        f(*node);
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_width_traverse(const Node* node, Function& f, std::queue< const Node* >& q) const
    {
        f(*node);
        if(node->left()) { q.push(node->left()); }
        if(node->right()) { q.push(node->right()); }

        if(!q.empty()) {
            const Node* p = q.front();
            q.pop();
            _width_traverse(p, f, q);
        }
    }

    template<class Key, class Value> template<class Function> void Tree<Key, Value>::_width_traverse(Node* node, Function& f, std::queue< Node* >& q)
    {
        f(*node);
        if(node->left()) { q.push(node->left()); }
        if(node->right()) { q.push(node->right()); }

        if(!q.empty()) {
            Node* p = q.front();
            q.pop();
            _width_traverse(p, f, q);
        }
    }

    template<class Key, class Value> Tree<Key, Value>::Tree(): _root(0) {}

    template<class Key, class Value> Tree<Key, Value>::Tree(const key_type& k, const value_type& v)
    {
        _root = new Node(k, v);
    }

    template<class Key, class Value> Tree<Key, Value>::Tree(const Node& node)
    {
        _root = new Node(node._key, node._value);
    }

    template<class Key, class Value> Tree<Key, Value>& Tree<Key, Value>::operator = (const Node& node)
    {
        delete _root;
        _root = new Node(node._key, node._value);
        return *this;
    }

    template<class Key, class Value> Tree<Key, Value>::Tree(const self& tree): _root(0)
    {
        if(!tree.empty()) {
            _root = new Node();
            _root->assign(*(tree._root));
        }
    }

    template<class Key, class Value> Tree<Key, Value>& Tree<Key, Value>::operator = (const self& tree)
    {
        if(!tree.empty()) {
            delete _root;
            _root = new Node();
            _root->assign(*(tree._root));
        }
        return *this;
    }

    template<class Key, class Value> Tree<Key, Value>& Tree<Key, Value>::swap(self& tree)
    {
        std::swap(_root, tree._root);
        return *this;
    }

    template<class Key, class Value> Tree<Key, Value>::~Tree()
    {
        delete _root;
    }

    template<class Key, class Value> Node<Key, Value>& Tree<Key, Value>::find(const key_type& k)
    {
        if(!empty()) {
            return _find(_root, k);
        }
        throw fx::exception(1, "There is no node with such key");
    }

    template<class Key, class Value> const Node<Key, Value>& Tree<Key, Value>::find(const key_type& k) const
    {
        return (const_cast< self& >(*this)).find(k);
    }

    template<class Key, class Value> Tree<Key, Value>& Tree<Key, Value>::add(const key_type& k, const value_type& v)
    {
        if(!empty()) {
            _add(_root, k, v);
        } else {
            _root = new Node(k, v);
        }
        return *this;
    }

    template<class Key, class Value> Tree<Key, Value>& Tree<Key, Value>::remove(const key_type& k)
    {
        _remove(_root, k);
        return *this;
    }

    template<class Key, class Value> Tree<Key, Value>& Tree<Key, Value>::clear()
    {
        delete _root;
        _root = 0;
        return *this;
    }

    template<class Key, class Value> inline unsigned int Tree<Key, Value>::count() const
    {
        return count_if(0);
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::count_if(bool (Node::*f)() const) const
    {
        _count p(f);
        infix_traverse(p);
        return p.count;
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::on_level(unsigned int n) const
    {
        if(empty()) { return 0; }
        return _on_level(n, _root);
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::on_level_if(unsigned int n, bool (Node::*f)() const) const
    {
        if(empty()) { return 0; }
        return _on_level(n, _root, f);
    }

    template<class Key, class Value> bool Tree<Key, Value>::empty() const
    {
        return (_root == 0);
    }

    template<class Key, class Value> const Node<Key, Value>* Tree<Key, Value>::root() const
    {
        return _root;
    }

    template<class Key, class Value> Node<Key, Value>* Tree<Key, Value>::root()
    {
        return _root;
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::height() const
    {
        if(empty()) { return 0; }
        return _height(_root);
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::width() const
    {
        unsigned int size = height();
        unsigned int* array = new unsigned int[size];
        //std::vector<unsigned int> array(height());
        _width(_root, 0, array);
        unsigned int max = 0;
        for(unsigned int i = 0; i < size; ++i)
        {
            if(max < array[i]) {
                max = array[i];
            }
        }
        delete[] array;
        return max;
    }

    template<class Key, class Value> bool Tree<Key, Value>::search_tree() const
    {
        return _search_tree(_root, std::numeric_limits<key_type>::min(), std::numeric_limits<key_type>::max());
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::degenerated() const
    {
        if(empty()) { return 0; }
        unsigned int max = 0;
        unsigned int res = _degenerated(_root, max);
        return res > max ? res : max;
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::full() const
    {
        if(empty()) { return 0; }
        unsigned int max = 0;
        unsigned int res = _full(_root, max);
        return res > max ? res : max;
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::balanced() const
    {
        // ToDo
        if(empty()) { return 0; }
        unsigned int max = 0;
        unsigned int res = _balanced(_root, max);
        return res > max ? res : max;
    }

    template<class Key, class Value> unsigned int Tree<Key, Value>::balanced_ideal() const
    {
        // ToDo
        if(empty()) { return 0; }
        unsigned int max = 0;
        unsigned int res = _balanced_ideal(_root, max);
        return res > max ? res : max;
    }

    template<class Key, class Value> Tree<Key, Value>& Tree<Key, Value>::add_to_root(const key_type& k, const value_type& v)
    {
        Node* node = new Node(k, v);
        if(_root->_key > k) {
            node->_right = _root;
            if(_root->_left) {
                _cut_left(node, k, _root->_left, _root);
            }
        } else if (_root->_key < k) {
            node->_left = _root;
            if(_root->_right) {
                _cut_right(node, k, _root->_right, _root);
            }
        }
        _root = node;

        return *this;
    }

    template<class Key, class Value> template<class Function> inline const Tree<Key, Value>& Tree<Key, Value>::infix_traverse(Function& f) const
    {
        if(!empty()) _infix_traverse(_root, f);
        return *this;
    }

    template<class Key, class Value> template<class Function> inline Tree<Key, Value>& Tree<Key, Value>::infix_traverse(Function& f)
    {
        if(!empty()) _infix_traverse(_root, f);
        return *this;
    }

    template<class Key, class Value> template<class Function> inline const Tree<Key, Value>& Tree<Key, Value>::prefix_traverse(Function& f) const
    {
        if(!empty()) _prefix_traverse(_root, f);
        return *this;
    }

    template<class Key, class Value> template<class Function> inline Tree<Key, Value>& Tree<Key, Value>::prefix_traverse(Function& f)
    {
        if(!empty()) _infix_traverse(_root, f);
        return *this;
    }

    template<class Key, class Value> template<class Function> inline const Tree<Key, Value>& Tree<Key, Value>::postfix_traverse(Function& f) const
    {
        if(!empty()) _postfix_traverse(_root, f);
        return *this;
    }

    template<class Key, class Value> template<class Function> inline Tree<Key, Value>& Tree<Key, Value>::postfix_traverse(Function& f)
    {
        if(!empty()) _infix_traverse(_root, f);
        return *this;
    }

    template<class Key, class Value> template<class Function> inline const Tree<Key, Value>& Tree<Key, Value>::width_traverse(Function& f) const
    {
        if(!empty()) {
            std::queue< const Node* > q;
            _width_traverse(_root, f, q);
        }
        return *this;
    }

    template<class Key, class Value> template<class Function> inline Tree<Key, Value>& Tree<Key, Value>::width_traverse(Function& f)
    {
        if(!empty()) {
            std::queue< Node* > q;
            _width_traverse(_root, f, q);
        }
        return *this;
    }

    template<class Key, class Value> typename Tree<Key, Value>::iterator Tree<Key, Value>::begin()
    {
        return iterator(*this);
    }

    template<class Key, class Value> typename Tree<Key, Value>::const_iterator Tree<Key, Value>::begin() const
    {
        return const_iterator(*this);
    }

    template<class Key, class Value> typename Tree<Key, Value>::iterator Tree<Key, Value>::end()
    {
        return iterator(*this, true);
    }

    template<class Key, class Value> typename Tree<Key, Value>::const_iterator Tree<Key, Value>::end() const
    {
        return const_iterator(*this, true);
    }

    template<class Key, class Value> typename Tree<Key, Value>::iterator_depth Tree<Key, Value>::begin_depth()
    {
        return iterator_depth(*this);
    }

    template<class Key, class Value> typename Tree<Key, Value>::const_iterator_depth Tree<Key, Value>::begin_depth() const
    {
        return const_iterator_depth(*this);
    }

    template<class Key, class Value> typename Tree<Key, Value>::iterator_depth Tree<Key, Value>::end_depth()
    {
        return iterator_depth(*this, true);
    }

    template<class Key, class Value> typename Tree<Key, Value>::const_iterator_depth Tree<Key, Value>::end_depth() const
    {
        return const_iterator_depth(*this, true);
    }

    template<class Key, class Value> typename Tree<Key, Value>::iterator_width Tree<Key, Value>::begin_width()
    {
        return iterator_width(*this);
    }

    template<class Key, class Value> typename Tree<Key, Value>::const_iterator_width Tree<Key, Value>::begin_width() const
    {
        return const_iterator_width(*this);
    }

    template<class Key, class Value> typename Tree<Key, Value>::iterator_width Tree<Key, Value>::end_width()
    {
        return iterator_width(*this, true);
    }

    template<class Key, class Value> typename Tree<Key, Value>::const_iterator_width Tree<Key, Value>::end_width() const
    {
        return const_iterator_width(*this, true);
    }

}

#endif // FXTREE_H