/** Binary Search Tree Implementation
 *  Dale Haverstock
 *  2002-04
 */
#include "bst.h"
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

                                   // utility functions
static int log2floor(int num);

//= BSTnode ===================================================================

std::ostream&
operator<< (std::ostream& os, const BSTnode& n)
{
    os << '(' << n._item.first << ", " << n._item.second << ')';
    return os;
}

//= BSTiterator ===============================================================
                                              // BSTiterator member functions
BSTiterator::BSTiterator(BSTnode* cur = 0) : _cur(cur) {}
 
BSTiterator& BSTiterator::operator++()
{
    _cur = successor(_cur);
    return *this;
}
 
BSTiterator BSTiterator::operator++(int)
{
    BSTiterator tmp(*this);   // get copy of this
    _cur = successor(_cur);   // move this to next
    return tmp;               // return old value
}
 
ValueType& BSTiterator::operator*()
  { return _cur->_item.second; }
 
bool BSTiterator::operator!=(BSTiterator rhs) const
  { return _cur != rhs._cur; }
 
BSTnode* BSTiterator::get_address() const
  { return _cur; }

BSTnode*  BSTiterator::successor(BSTnode* nptr)
{
       // If there is a right child ...
    if (nptr->_right)
    {
	    // Find min of right subtree.
        nptr = nptr->_right;
        while (nptr->_left)
           nptr = nptr->_left;
        return nptr;
    }
    else
    {      // No right child, find tree for which this is the greatest
	   // and choose that tree's parent.
        while (nptr->_parent && nptr->_parent->_right == nptr)
           nptr = nptr->_parent;
        if (nptr)
            return nptr->_parent;
        else
            return nptr;
        
    }
}

//= BST =======================================================================

BSTnode* BST::find(KeyType key)
// Search tree for key, return node* if found else 0.
{
      // Binary tree search.
    BSTnode* cur = _root;
    while (cur && cur->getKey() != key)
    {
        if (key < cur->getKey())
            cur = cur->_left;
        else
            cur = cur->_right;
    }
    return cur;
}

//----------------------------------------------------------------------------
BSTnode BST::min()
{
   BSTnode* cur  = _root; 
   BSTnode* prev; 
   while (cur)
   {
       prev = cur;
       cur  = cur->_left;
   }
   return *prev;
}

//----------------------------------------------------------------------------
bool BST::empty()
{
    if (!_root) return true;
    else        return false;
}

//----------------------------------------------------------------------------
BSTnode& BST::insert(KeyType key, ValueType value)
// lookup key, create key/value if not present
// return reference to node with key
{
    BSTnode& node = getNode(key);
    node._item.second = value;
    return node;
}

//----------------------------------------------------------------------------
BSTnode& BST::getNode(KeyType key)
// lookup key, create key/value if not present
// return reference to node with key
{
    BSTnode* ptr;

    if (!_root)
    {
            // Empty tree.
            // create pair, create new BST node, make new node root
        std::pair<KeyType, ValueType> p(key, 0);
        BSTnode* new_node = new BSTnode(0, 0, 0, p);
        _root = new_node;
        return *new_node;
    }
    else if (ptr = find(key))
    {
            // Item is in tree.
            // Return the node
        return *ptr;
    }
    else
    {
            // Item is not in tree. Do an insert.
            // Search for insert location.
        BSTnode* cur = _root;
        BSTnode* parent;
        while (cur)
        {
            parent = cur;               // save cur's parent
            if ( key < cur->getKey() )
                cur = cur->_left;
            else
                cur = cur->_right;
        }

            // Create a pair and new mode.
        std::pair<KeyType, ValueType> p(key, 0);
        BSTnode* new_node = new BSTnode(0, 0, parent, p);

            // Insert the node.
        if (key < parent->getKey())
            parent->_left  = new_node;
        else
            parent->_right = new_node;

        return *new_node;
    }
}

//----------------------------------------------------------------------------
void BST::delete_node(KeyType key)       // XXX won't work for root
{
    BSTnode* del = find(key);
    if (!del)
        return;           // not in tree
    else
    {                     // is in tree
        if (del->_left == 0 && del->_right == 0)
        {
            if (del->_parent)
            {                             // not root
                bool is_left = (del->_parent->_left == del) ? true : false;

                    // remove as parent's child
                if (is_left) del->_parent->_left  = 0;
                else         del->_parent->_right = 0;
            }
            else                          // del is root
                _root = 0;
        }
        else if (del->_left != 0 && del->_right == 0)
        {
            if (del->_parent)
                del->_parent->_left = del->_left;      // splice out of left
            else
                _root = del->_left;
        }
        else if (del->_left == 0 && del->_right != 0)
        {
            if (del->_parent)
                del->_parent->_right = del->_right;    // splice out of right
            else
                _root = del->_right;
        }
        else
        {

            BSTnode* r_min = del->_right; // find min of right subtree
            while (r_min->_left)
                r_min = r_min->_left;

            if (r_min->_parent == del)
            {                                 // r_min has del as parent
                   // del's left child becomes r_min's left child
                   // (r_min had no left child)
                r_min->_left          = del->_left;
                r_min->_left->_parent = r_min;
                   // del's parent becomes r_min's parent 
                r_min->_parent = del->_parent;
                if (del->_parent)
                {
                    bool is_left = (del->_parent->_left == del) ? true : false;
                    if (is_left) del->_parent->_left  = r_min; 
                    else         del->_parent->_right = r_min;
                }
                else
                    _root = r_min;
            }
            else
            {      // r_min dosesn't have del as parent
                   // r_min's parent's left child gets r_min's right child
                r_min->_parent->_left  = r_min->_right;
                r_min->_right->_parent = r_min->_parent;
                 
                   // del's left child becomes r_min's left child
                   // (r_min had no left child)
                r_min->_left          = del->_left;
                r_min->_left->_parent = r_min;
                   // del's right child becomes r_min's right child
                r_min->_right          = del->_right;
                r_min->_right->_parent = r_min;
                   // del's parent becomes r_min's parent 
                r_min->_parent = del->_parent;
                if (del->_parent)
                {
                    bool is_left = (del->_parent->_left == del) ? true : false;
                    if (is_left && del->_parent) del->_parent->_left  = r_min; 
                    else                         del->_parent->_right = r_min;
                }
                else
                    _root = r_min;
            }
        }
        delete del;
    }
}

//----------------------------------------------------------------------------
BST::iterator BST::begin()
{
    BSTnode* nptr = _root;
    while (nptr->_left)
        nptr = nptr->_left;
    return BST::iterator(nptr);
}

//----------------------------------------------------------------------------
BST::iterator BST::end()
{
    return BST::iterator(0);
}

//----------------------------------------------------------------------------
void BST::showTree1()
{
    std::cerr << '\n';
    showTree1(_root, 0, ' ');
}

//----------------------------------------------------------------------------
void BST::showTree1(BSTnode* node, int depth, char c)
{
    std::string indent(depth * 4, ' ');

    if (node)
    {
        std::cerr << indent << c << "-- "                 // preorder
                  << node->getKey() << ','
                  << node->getValue() << '\n';
    
        showTree1(node->_left,  depth + 1, 'L');
        showTree1(node->_right, depth + 1, 'R');
    }
    else
    {
        std::cerr << indent << c << "-- *\n";
    }
}

//----------------------------------------------------------------------------
void BST::showTree2()
// Displays the contents of a vector as a binary tree.
// Uses data member vector named vec
// Abbreviation: lvl == level
{
    std::vector<std::pair<KeyType, ValueType>* > vec = data_in_vector();

    if (!vec.size())  
    {
        std::cerr << '\n';
        return;
    }

    const int greatest_lvl          = log2floor(vec.size());
    const int items_in_greatest_lvl = static_cast<int>(pow(2, greatest_lvl));

    int items_in_lvl = 1;
    int ctr = 0;
    for ( int lvl = 0; lvl <= greatest_lvl; ++lvl, items_in_lvl *= 2)
    {
        int field = 2 * items_in_greatest_lvl / items_in_lvl;
        for ( int j = 0; j < items_in_lvl && ctr < vec.size(); ++j)
        {
              {
                  int field_width = (j == 0) ? field : 2 * field;
                  if (vec[ctr])
                      std::cerr << std::setw(field_width) << vec[ctr]->first;
                  else
                  {
                      std::string str(field_width, ' ');
                      std::cerr << str;
                  }
              }
               ++ctr;
        }
        std::cerr << "\n";
    }
    std::cerr << "\n";
}

//----------------------------------------------------------------------------
std::vector<std::pair<KeyType, ValueType>* >
BST::data_in_vector()
{
    std::vector<std::pair<KeyType, ValueType>* > vec;  // for binary tree items
    int node_count = size();

    std::queue<BSTnode*> q;             // level-order traversal
    q.push(_root);
    int count = 0;
    while (count < node_count)
    {
        assert(!q.empty());
        BSTnode* ptr = q.front();
        q.pop();
        if (ptr != 0)
        {
            ++count;
            q.push(ptr->_left);
            q.push(ptr->_right);
            vec.push_back(&(ptr->_item));
        }
        else
        {
            q.push(0);
            vec.push_back(0);
        }
    }
    return vec;
}

//----------------------------------------------------------------------------
int BST::size()
{
    return count(_root);
}

//----------------------------------------------------------------------------
int BST::count(BSTnode* n)
{
    if (!n)
        return 0;
    else
    {
        int left_cnt  = count(n->_left);
        int right_cnt = count(n->_right);
        return 1 + left_cnt + right_cnt;
    }
}

//----------------------------------------------------------------------------
int log2floor(int num)
{
        // See how many times we can divide by 2 without going below 0.
    int count = 0;
    while (num > 0)
    {
        num >>= 1;
        ++count;
    }
    return count - 1;
}