/*
   Bintree.h
   CIS 250
   Dave Klick
   2012-04-11

   Templated binary search tree implementation
*/

#ifndef __Bintree_H__
#define __Bintree_H__

#include <iostream>
using std::ostream;
using std::cout;

template<typename T>
struct Node {
    // *** If you plan on storing duplicates by keeping a count:
    // *** 1. Add a private integer variable to this class to keep a count
    // *** 2. Make sure all the constructors initialize the count
    // *** 3. Create a getCount() accessor function
    // *** 4. Create an increment() method to increase the count by 1 and return its value
    // *** 5. Create a decrement() method to decrease the count by 1 and return its value
    // *** 6. Modify the operator<< overload to display a count in parentheses after the data
public:
    T data;
    Node* left;
    Node* right;
    Node() : count(1), left(NULL), right(NULL) {}
    Node(const T data) : count(1), data(data), left(NULL), right(NULL) {}
    T getData() const { return data; }
    friend ostream& operator<<(ostream& strm, const Node<T>& node) {
        return strm << node.data;
    }
};

template<typename T>
class Bintree {
private:
    Node<T>* root;
    void inOrder(const Node<T>* p) const;
    void preOrder(const Node<T>* p) const;
    void postOrder(const Node<T>* p) const;
    void deleteTree(Node<T>*);
public:
    Bintree() { root = NULL; }
    ~Bintree();
    bool remove(const T&);
    bool insert(const T&);
    bool find(const T&) const;
    void inOrder() const { inOrder(root); }
    void preOrder() const { preOrder(root); }
    void postOrder() const { postOrder(root); }
};

template<typename T>
void Bintree<T>::deleteTree(Node<T>* p) {
    if (p != NULL) {
        if (p->left) deleteTree(p->left);
        if (p->right) deleteTree(p->right);
        delete p;
    }
}

template<typename T>
void Bintree<T>::inOrder(const Node<T>* p) const {
    if (p != NULL) {
        inOrder(p->left);
        cout << *p << '\n';
        inOrder(p->right);
    }
}

template<typename T>
void Bintree<T>::preOrder(const Node<T>* p) const {
    if (p != NULL) {
        cout << *p << '\n';
        preOrder(p->left);
        preOrder(p->right);
    }
}

template<typename T>
void Bintree<T>::postOrder(const Node<T>* p) const {
    if (p != NULL) {
        postOrder(p->left);
        postOrder(p->right);
        cout << *p << '\n';
    }
}

template<typename T>
Bintree<T>::~Bintree() {
    deleteTree(root); root = NULL;
}

template<typename T>
bool Bintree<T>::remove(const T& data) {
    Node<T> *parent, *delNode, *succ, *parentSucc;
    bool isLeftChild = true;
    if (root == NULL) return false;

    // find node to be deleted
    parent = NULL;
    delNode =  root;
    while (data != delNode->data) {
        parent = delNode;
        if (data < delNode->data) {
            if (delNode->left == NULL) return false;
            delNode = delNode->left;
            isLeftChild = true;
        } else {
            if (delNode->right == NULL) return false;
            delNode = delNode->right;
            isLeftChild = false;
        }
    }
    
    // *** If you plan on storing duplicates by keeping a count:
    // *** Check to see if the current count is greater than 1
    // *** If it is, then decrement the count and return true
    // *** Otherwise, let the code continue on

    if (delNode->left == NULL && delNode->right == NULL) {
        // do delete for node with no children
        if (delNode == root) root = NULL;
        else if (isLeftChild) parent->left = NULL;
        else parent->right = NULL;
    } else if (delNode->right == NULL || delNode->left == NULL) {
        // do delete for node with one child
        succ = delNode->right == NULL ? delNode->left : delNode->right;
        if (delNode == root) root = succ;
        else if (isLeftChild) parent->left = succ;
        else parent->right = succ;
    } else {
        // do delete for node with two children
        parentSucc = delNode;
        succ = delNode->right; // once to right
        while (succ->left != NULL) { // left as far as possible
            parentSucc = succ;
            succ = succ->left;
        }
        if (delNode == root) root = succ;
        else if (isLeftChild) parent->left = succ;
        else parent->right = succ;
        if (parentSucc != delNode) parentSucc->left = succ->right;
        succ->left = delNode->left;
        if (delNode->right != succ) succ->right = delNode->right;
    }

    delete delNode;
    return true;
}

template<typename T>
bool Bintree<T>::insert(const T& data) {
    Node<T> *newNode, *prev, *curr;
    newNode = new Node<T>(data);
    if (root == NULL) root = newNode;
    else {
        curr = root;
        while (curr != NULL) {
            prev = curr;
            if (data == curr->data) {
                // *** If you plan on storing duplicates by keeping a count:
                // *** Increment the count on the current  node
                // *** Delete the new node that was created when this function started
                // *** Return true instead of false (since duplicates are now allowed)
                return false;
            } else {
                curr = (data < curr->data) ? curr->left : curr->right;
            }
        }
        if (data < prev->data) prev->left = newNode;
        else prev->right = newNode;
    }
    return true;
}

template<typename T>
bool Bintree<T>::find(const T& data) const {
    Node<T> *curr;
    bool found = false;

    if (root != NULL) {
        curr = root;
        while (curr != NULL && !found) {
            if (data == curr->data) found = true;
            else if (data < curr->data) curr = curr->left;
            else curr = curr->right;
        }
    }

    return found;
}

#endif