//binarytree.h
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
#include <queue>
#include <stack>
#include "player.h"

template<class T>
class Queue : public queue<T>
{
public:
    T dequeue()
    {
        T tmp = front();
        queue<T>::pop();
        return tmp;
    }
    void enqueue(const T& el)
    {
        push(el);
    }
};

template<class T>
class BSTNode
{
public:
    BSTNode()
    {
        left = right = 0;
    }
    BSTNode(const T& el, BSTNode *l = 0, BSTNode *r = 0)
    {
        key = el; left = l; right = r;
    }
    T key;
    BSTNode *left, *right;
};

class PlayerBST
{
public:
    PlayerBST()
    {
        root = 0;
    }
    ~PlayerBST()
    {
        clear();
    }
    void clear()
    {
        clear(root); root = 0;
    }
    bool isEmpty() const
    {
        return root == 0;
    }
    void inorder()
    { //default without input param
        inorder(root); //delegate to overload
    }
    void insert(Player&);
    Player* search(int searchForLevel) const
    {
        return search(root, searchForLevel);
    }

    void deleteByMerging(BSTNode<Player>*&);
    void findAndDeleteByMerging(Player&); //Wow, that's an ugly function name :3c
    void breadthFirst();

protected:
    BSTNode<Player>* root;
    void clear(BSTNode<Player>*);
    Player* search(BSTNode<Player>* p, int searchForLevel) const;
    void inorder(BSTNode<Player>*); //overloaed
    virtual void visit(BSTNode<Player>* p)
    {
        p->key.playerDisplay() ;
    }
};


void PlayerBST::clear(BSTNode<Player> *p)
{
    if (p != 0)
    {
        clear(p->left);
        clear(p->right);
        delete p;
    }
}


void PlayerBST::insert(Player& el)
{
    BSTNode<Player> *p = root, *prev = 0;
    while (p != 0)
    {
        prev = p;
        if (p->key.getLevel() < el.getLevel())
            p = p->right;
        else p = p->left;
    }
    if (root == 0) //tree is empty;
        root = new BSTNode<Player>(el);
    else if (prev->key.getLevel() < el.getLevel())
        prev->right = new BSTNode<Player>(el);
    else prev->left = new BSTNode<Player>(el);
}

Player* PlayerBST::search(BSTNode<Player>* p, int searchForLevel) const
{
    while (p != 0)
        if (searchForLevel == p->key.getLevel())
            return &p->key;
        else if (searchForLevel < p->key.getLevel())
            p = p->left;
        else p = p->right;
        return 0;
}


void PlayerBST::inorder(BSTNode<Player> *p)
{
    if (p != 0)
    {
        inorder (p->left); //note recursive call
        visit(p);
        inorder(p->right); //note recursive call
    }
}

void PlayerBST::deleteByMerging(BSTNode<Player>*& node)
{
    BSTNode<Player> *tmp = node;
    if (node != 0)
    {
        if (!node->right) //node has no right child
            node = node-> left; //child (if any) is attached to parent
        else if (node->left == 0) //no left child
            node = node->right; //child is attached to parent
        else
        { //be ready for merging subtrees
            tmp = node->left; //1. move left
            while (tmp->right != 0) //2. and then right as far as possible;
                tmp = tmp->right;
            tmp->right = node->right; //establish link between rightmost node of left subtree and right subtree
                tmp = node;
                node = node->left;
        }
        delete tmp;
    }
}

void PlayerBST::findAndDeleteByMerging(Player& el)
{
    BSTNode<Player> *node = root, *prev = 0;
    while(node != 0)
    {
        if (node->key.getLevel() == el.getLevel())
            break;
        prev = node;
        if (node->key.getLevel() < el.getLevel())
            node = node->right;
        else node = node->left;
    }
    if (node != 0 && node->key.getLevel() == el.getLevel())
        if (node == root)
            deleteByMerging(root);
        else if (prev->left == node)
            deleteByMerging(prev->left);
        else deleteByMerging(prev->right);
    else if (root != 0)
        cout << "Key not found in the tree\n";
    else cout << "The tree is empty\n";
}

void PlayerBST::breadthFirst()
{
    Queue<BSTNode<Player>*> queue;
    BSTNode<Player> *p = root;
    if (p != 0)
    {
        queue.enqueue(p);
        while (!queue.empty())
        {
            p = queue.dequeue();
            visit(p);
            if (p->left != 0)
                queue.enqueue(p->left);
            if (p->right != 0)
                queue.enqueue(p->right);
        }
    }
}

#endif