// ==========================================================================
// Author:  Yee Hsu
// Date:    2/2/2005
// File:    BST.cpp
//
// Desc:    BST is a binary search tree class. It does data storing,
//          retrieval and sorting using a BST. This is my attempted
//          implementation of a BST tree object.
// ==========================================================================

#include <iostream.h>
#include "Node.h"
#include "BST.h"

// ==========================================================================
// Identifier:  BST()
//
// Description: BST Constructor
// ==========================================================================

BST::BST() : root(NULL) {}

// ==========================================================================
// Identifier:  BST(const BST &b)
//
// Description: BST Copy Constructor
// ==========================================================================

BST::BST(const BST &b)
{
    this->CloneTree(b.root, root);
}

// ==========================================================================
// Identifier:  ~BST()
//
// Description: BST Destructor
// ==========================================================================

BST::~BST()
{
    this->RemoveTree(root);
}

// ==========================================================================
// Identifier:  operator =(const BST &b)
//
// Description: overloaded assignment = operator
// ==========================================================================

BST& BST::operator =(const BST &b)
{
    if (this != &b)
    {
        this->RemoveTree(root);
        this->CloneTree(b.root, root);
    }
    return *this;
}

// ==========================================================================
// Identifier:  operator ==(const BST &b)
//
// Description: overloaded comparison == operator
// ==========================================================================

bool BST::operator ==(const BST &b)
{
    bool same = true;
    this->IsEqual(b.root, root, same);
    return same;
}

// ==========================================================================
// Identifier:  IsEmpty()
//
// Description: Determines if the tree is empty
// ==========================================================================

bool BST::IsEmpty()
{
    return bool(root == NULL);
}

// ==========================================================================
// Identifier:  Insert()
//
// Description: Inserts a key into the BST
// ==========================================================================

void BST::Insert(const int key)
{
    this->Insert(root, key);
}

// ==========================================================================
// Identifier:  Search()
//
// Description: Searches for a value in the BST base on a key
// ==========================================================================

int BST::Search(const int key)
{
    return this->Search(root, key);
}

// ==========================================================================
// Identifier:  Delete()
//
// Description: Delete a value in the BST base on a key
// ==========================================================================

bool BST::Delete(const int key)
{
    return this->Delete(root, key);
}

// ==========================================================================
// Identifier:  Traverse()
//
// Description: Traverses the BST in order
// ==========================================================================

void BST::Traverse(const int order)
{
    switch (order)
    {
        case PREORDER:
            this->PreOrder(root);
            break;

        case INORDER:
            this->InOrder(root);
            break;

        case POSTORDER:
            this->PostOrder(root);
            break;

        default:
            cout << "Usage - Traverse(PREORDER | INORDER | POSTORDER)";
            cout << endl;
            break;
    }
}

// ==========================================================================
// Identifier:  PreOrder()
//
// Description: Traverses the BST in pre-order
// ==========================================================================

void BST::PreOrder(const pNode& p)
{
    if (p != NULL)
    {
        cout << p->key << " ";
        PreOrder(p->left);
        PreOrder(p->right);
    }
}

// ==========================================================================
// Identifier:  InOrder()
//
// Description: Traverses the BST in in-order
// ==========================================================================

void BST::InOrder(const pNode& p)
{
    if (p != NULL)
    {
        InOrder(p->left);
        cout << p->key  << " ";
        InOrder(p->right);
    }
}

// ==========================================================================
// Identifier:  PostOrder()
//
// Description: Traverses the BST in post-order
// ==========================================================================

void BST::PostOrder(const pNode& p)
{
    if (p != NULL)
    {
        PostOrder(p->left);
        PostOrder(p->right);
        cout << p->key << " ";
    }
}

// ==========================================================================
// Identifier:  Insert()
//
// Description: Inserts a node into the tree base on key value
// ==========================================================================

void BST::Insert(pNode &p, const int key)
{
    if (p == NULL)
        p = new Node(key);
    else
    {
        if (key < p->key)
            Insert(p->left, key);
        else if (key > p->key)
            Insert(p->right, key);
    }
}

// ==========================================================================
// Identifier:  Search()
//
// Description: Search a data node in the tree base on key value
// ==========================================================================

int BST::Search(pNode &p, const int key)
{
    int data = -1;

    if (p == NULL)
        data = -1;
    else
    {
        if (key == p->key)
            data = p->key;
        else if (key < p->key)
            data = Search(p->left, key);
        else
            data = Search(p->right, key);
    }
    return data;
}

// ==========================================================================
// Identifier:  Delete()
//
// Description: Delete a data node in the tree base on key value
// ==========================================================================

bool BST::Delete(pNode &p, const int key)
{
    bool del = false;

    if (p == NULL)
        del = false;
    else
    {
        if (key == p->key)
        {
            this->DeleteNode(p);
            del = true;
        }
        else if (key < p->key)
            del = Delete(p->left, key);
        else
            del = Delete(p->right, key);
    }
    return del;
}

// ==========================================================================
// Identifier:  DeleteNode()
//
// Description: Delets a node
// ==========================================================================

void BST::DeleteNode(pNode &p)
{
    pNode delptr;
    int key;

    if (p->left == NULL && p->right == NULL)
    {
        delete p;
        p = NULL;
    }
    else if (p->left == NULL)
    {
        delptr = p;
        p = p->right;
        delptr->right = NULL;
        delete delptr;
    }
    else if (p->right == NULL)
    {
        delptr = p;
        p = p->left;
        delptr->left = NULL;
        delete delptr;
    }
    else
    {
        this->GetSuccesser(p->right, key);
        p->key = key;
    }
}

// ==========================================================================
// Identifier:  GetSuccesser()
//
// Description: Gets the next data node base on key value
// ==========================================================================

void BST::GetSuccesser(pNode &p, int& key)
{
    if (p->left == NULL)
    {
        key = p->key;
        pNode delptr = p;
        p = p->right;
        delptr->right = NULL;
        delete delptr;
    }
    else
        GetSuccesser(p->left, key);
}

// ==========================================================================
// Identifier:  CloneTree()
//
// Description: Makes a duplicate copy of the BST tree
// ==========================================================================

void BST::CloneTree(const pNode p1, pNode& p2)
{
    if (p1 != NULL)
    {
        p2 = new Node(p1->key);

        CloneTree(p1->left, p2->left);
        CloneTree(p1->right, p2->right);
    }
    else
        p2 = NULL;
}

// ==========================================================================
// Identifier:  IsEqual()
//
// Description: Test is see if the tree has the same contents
// ==========================================================================

void BST::IsEqual(const pNode p1, const pNode p2, bool &same)
{
    if (p1 == NULL && p2 != NULL)
        same = false;
    else if (p1 != NULL && p2 == NULL)
        same = false;
    else if (p1 != NULL && p2 != NULL)
    {
        IsEqual(p1->left, p2->left, same);
        IsEqual(p1->right, p2->right, same);

        if (same == true)
        {
            if (p1->key == p2->key)
                same = true;
            else
                same = false;
        }
    }
}

// ==========================================================================
// Identifier:  RemoveTree()
//
// Description: Removes the tree base on node
// ==========================================================================

void BST::RemoveTree(pNode& p)
{
    if (p != NULL)
    {
        RemoveTree(p->left);
        RemoveTree(p->right);
        delete p;
        p = NULL;
    }
}