#ifndef _TREE_H_
#define _TREE_H_

#include <list>

template<typename T>
class BinaryTree
{
public:
    //конструктор по умолчанию
	BinaryTree()
		: pkey(0), pleft(0), pright(0), pparent(0)
	{

	}

    //конструктор копирования
    BinaryTree(const BinaryTree<T>& other)
        : pkey(0), pleft(0), pright(0), pparent(0)
    {
        pparent = 0;
        if(other.hasKey())
        {
            pkey = new T(other.key());
            if(other.hasLeft())
            {
                pleft = new BinaryTree<T>(this, other.left());
            }
            if(other.hasRight())
            {
                pright = new BinaryTree<T>(this, other.right());
            }
        }
    }

    //деструктор
	~BinaryTree()
	{
		if(pleft)
		{
			delete pleft;
		}
		if(pright)
		{
			delete pright;
		}
		if(pkey)
		{
			delete pkey;
		}
	}

    //функция для вставки элементов из отрезка [begin, end]
    //Пример: int m[] = {1, 3, 2, 6, 7, -4}
    //        int* p = m;
    //        tree.insertFrom(p, p + 5);
    //Занесет в дерево tree пять первых элементов массива. Работает с любыми итераторами
    template<typename Iterator>
    void insertFrom(const Iterator& begin, const Iterator& end)
    {
        for(Iterator i = begin; i != end; ++i)
        {
            this->insert(*i);
        }
    }

    //Возвращает список, составленный из элементов дерева
    std::list<T> makeList() const
    {
        std::list<T> result;
        if(pkey)
        {
            result.push_back(*pkey);
        
            if(hasLeft())
            {
                result.splice(result.end(), pleft->makeList());
            }
            if(hasRight())
            {
                result.splice(result.end(), pright->makeList());
            }
        }
        return result;
    }

    //Вставляет элемент в дерево согласно правилам. Выделяет память, если нужно.
	void insert(const T& new_value)
	{
		if(!pkey)
		{
			pkey = new T(new_value);
		}
		if(new_value == *pkey)
		{
			return;
		}
		else if(new_value < *pkey)
		{
			if(!pleft)
			{
				pleft = new BinaryTree<T>(this);
			}
			pleft->insert(new_value);
		}
		else
		{
			if(!pright)
			{
				pright = new BinaryTree<T>(this);
			}
			pright->insert(new_value);
		}
	}

    //Возвращает true если у узла есть родитель, иначе false
    bool isRoot() const
    {
        return (pparent ? true : false);
    }

    //Возвращает ссылку на узел-родитель. Если родителя нет, кидает исключение
    BinaryTree<T>& parent() 
    {
        if(!pparent)
        {
            throw NoParent();;
        }
        return *pparent;
    }

    //Возвращает константную ссылку на узел-родитель. Если родителя нет, кидает исключение
    const BinaryTree<T>& parent() const
    {
        if(!pparent)
        {
            throw NoParent();;
        }
        return *pparent;
    }

    //Возвращает true, если у узла есть ключевое значение, иначе false
    bool hasKey() const
    {
        return (pkey ? true : false);
    }

    //Возвращает ссылку на ключевое значение узла. Если значения нет (указатель нулевой), кидает исключение
	T& key()
	{
		if(!pkey)
		{
			throw NoValue();
		}
        return *pkey;
	}

    //Возвращает константную ссылку на ключевое значение узла.
    //Если значения нет (указатель нулевой), кидает исключение
    const T& key() const
	{
		if(!pkey)
		{
			throw NoValue();
		}
        return *pkey;
	}

    //Устанавливает новое ключевое значение. В данном случае, дерево не перестраивается, поэтому эту
    //функцию нужно использовать очень аккуратно, чтобы не нарушить структуру дерева
	void setKey(const T& new_value)
	{
		if(pkey)
		{
			delete pkey;
		}
		pkey = new T(new_value);
	}
    
    //Возвращает ссылку на левое поддерево. Если левого поддерева нет (указатель нулевой),
    //то кидает исключение
	BinaryTree<T>& left() 
	{
		if(!pleft)
		{
			throw NoSubtree();
		}
		return *pleft;
	}

    //Возвращает константную ссылку на левое поддерево. Если левого поддерева нет (указатель нулевой),
    //то кидает исключение
	const BinaryTree<T>& left() const
	{
		if(!pleft)
		{
			throw NoSubtree();
		}
		return *pleft;
	}
        
    //Возвращает ссылку на правое поддерево. Если правого поддерева нет (указатель нулевой),
    //то кидает исключение
	BinaryTree<T>& right()
	{
		if(!pright)
        {
            throw NoSubtree();
        }
        return *pright;
	}

    //Возвращает константную ссылку на правое поддерево. Если правого поддерева нет (указатель нулевой),
    //то кидает исключение
	const BinaryTree<T>& right() const
	{
		if(!pright)
        {
            throw NoSubtree();
        }
        return *pright;
	}

    //Рекурсивный поиск по дереву. Возвращается указатель на констатное поддерево, 
    //ключевое значение коренного узла которого равно искомому
    //Если такого значения в дереве нет, возвращается ноль
    //Сложность по времени: в среднем O(logn), в худшем O(n)
    const BinaryTree<T>* find(const T& pattern) const
    {
        if(!pkey)
        {
            return 0;
        }
        if(pattern == *pkey)
        {
            return this;
        }
        if(pattern < *pkey)
        {
            if(!pleft)
            {
                return 0;
            }
            return pleft->find(pattern);
        }
        else
        {
            if(!pright)
            {
                return 0;
            }
            return pright->find(pattern);
        }
    }

    //Рекурсивный поиск по дереву. Возвращается указатель на поддерево, 
    //ключевое значение коренного узла которого равно искомому
    //Если такого значения в дереве нет, возвращается ноль
    BinaryTree<T>* find(const T& pattern)
    {
        if(!pkey)
        {
            return 0;
        }
        if(pattern == *pkey)
        {
            return this;
        }
        if(pattern < *pkey)
        {
            if(!pleft)
            {
                return 0;
            }
            return pleft->find(pattern);
        }
        else
        {
            if(!pright)
            {
                return 0;
            }
            return pright->find(pattern);
        }
    }

    //Удаляет правое поддерево
    void removeLeft()
    {
        if(pleft)
        {
            delete pleft;
            pleft = 0;
        }
    }

    //Удаляет левое поддерево
    void removeRight()
    {
        if(pright)
        {
            delete pright;
            pright = 0;
        }
    }

    //Удаляет выбранный элемент, если он находится в дереве.
    //Дерево перестраивается, чтобы соответствовать структуре двоичного дерева
    bool remove(const T& pattern)
    {
        BinaryTree<T>* psearchResult = find(pattern);
        if(!psearchResult)
        {
            return false;
        }
        else
        {
            BinaryTree<T>& searchResultParent = psearchResult->parent();
            bool searchResultIsRight = (psearchResult->key() > searchResultParent.key() ? true : false);
            if(psearchResult->isLeaf())
            {
                if(searchResultIsRight)
                {
                    searchResultParent.removeRight();
                    return true;
                }
                else
                {
                    searchResultParent.removeLeft();
                    return true;
                }
            }
            if(!psearchResult->hasLeft())
            {
                BinaryTree<T>& searchResultRight = psearchResult->right();
                (searchResultIsRight ? searchResultParent.pright : searchResultParent.pleft) 
                    = &searchResultRight;
                searchResultRight.pparent = &searchResultParent;
                pright = pleft = 0;
                delete this;
                return true;
            }
            else if(!psearchResult->hasRight())
            {
                BinaryTree<T>& searchResultLeft = psearchResult->left();
                (searchResultIsRight ? searchResultParent.pright : searchResultParent.pleft) 
                    = &searchResultLeft;
                searchResultLeft.pparent = &searchResultParent;
                pright = pleft = 0;
                delete this;
                return true;
            }
            else
            {
                std::list<T> leftList = psearchResult->left().makeList();
                std::list<T> rightList = psearchResult->right().makeList();
                std::list<T> leftAndRight;
                leftAndRight.splice(leftAndRight.end(), leftList);
                leftAndRight.splice(leftAndRight.end(), rightList);

                if(searchResultIsRight)
                {
                    searchResultParent.pright = 0;
                }
                else
                {
                    searchResultParent.pleft = 0;
                }
                searchResultParent.insertFrom(leftAndRight.begin(), leftAndRight.end());
                //TODO: Fix memory leaks
                return true;
            }

        }
    }

    //Возвращает true, если у дерева нет поддеревьев
    bool isLeaf() const
    {
        return !pleft && !pright;
    }

    //Возвращает true, если у дерева есть левое поддерево
    bool hasLeft() const
    {
        return (pleft ? true : false);
    }

    //Возвращает true, если у дерева есть правое поддерево
    bool hasRight() const
    {
        return (pright ? true : false);
    }

    //Возвращает true, если дерево пустое
    bool empty() const
    {
        return !(haskey() && isLeaf());
    }

    //Классы для исключений
	class NoValue{};
    class NoSubtree{};
    class NoParent{};
protected:
    //Приватный конструктор для удобства задания родителей 
    BinaryTree(BinaryTree<T> *new_parent, const BinaryTree<T>& other = BinaryTree<T>())
        : pkey(0), pleft(0), pright(0), pparent(new_parent)
    {
        if(other.hasKey())
        {
            pkey = new T(other.key());
            if(other.hasLeft())
            {
                pleft = new BinaryTree<T>(this, other.left());
            }
            if(other.hasRight())
            {
                pright = new BinaryTree<T>(this, other.right());
            }
        }
    }
private:
	T *pkey;    //указатель на ключевое значение
    BinaryTree<T> *pparent; //указатель на родителя
	BinaryTree<T> *pleft; //указатель на левое поддерево
	BinaryTree<T> *pright; //указатель на правое поддерево
};

#endif /*_TREE_H_*/