/***************************************************
 * avltree.C                                       *
 *                                                 *
 *  Implem. for an AVL tree that is derived from   *
 *   our binary search tree class, BSTree.         *
 *  Adapted from Weiss, 1994.                      *
 *                                                 *
 *  Author:  Wendy L. Terry                        *
 *    Date:  1 Oct 1997                            *
 *  Update:  6 Oct 1997 by Wendy L. Terry          *
 *             -- added right rotations            *
 *  Update: 22 Mar 1999 by Jason Zych              *
 *             -- major restructuring:             *
 *                elimninated inheritance          *
 *                                                 *
 *                                                 *
 ***************************************************/

// *****************************************************
// *                                                   *
// *   Modified:  March 28 1999                        *
// *     Author:  Zaczek, Mariusz                      *
// *                                                   *
// *       - added to BSTree: operator<<, operator>>,  *
// *         counters: TotalCompares & RecentCompares. *
// *       - modified the Find, Insert and Remove fns. *
// *                                                   *
// *****************************************************


#include <stdlib.h>
#include "avltree.h"
#include "asserts.h"


// AVLTree
//    - default constructor
//    - initializes tree to be empty
template <class Etype>
AVLTree<Etype>::AVLTree() : root(NULL), lastFound(NULL), size(0), 
	 	            TotalCompares(0), RecentCompares(0)
{
   // no additional code needed
}



// AVLTree
//    - copy constructor
//    - parameters : origVal - previously allocated AVLTree object
//    - initializes object to be a copy of origVal
template <class Etype>
AVLTree<Etype>::AVLTree(const AVLTree<Etype>& origVal)
{
   root = Copy(origVal.root); 
   lastFound = root;
   size = origVal.size;
}



// ~AVLTree
//    - destructor
//    - deletes dynamically allocated memory
template <class Etype>
AVLTree<Etype>::~AVLTree()
{ 
   Make_Empty(root); 
   root = lastFound = NULL; 
   size = 0;
}



// operator=
//    - parameters : origVal - previously allocated AVLTree object
//    - return value - const reference to this object  
//    - sets object to be a copy of origVal
template <class Etype>
const AVLTree<Etype>& AVLTree<Etype>::operator=(const AVLTree<Etype>& origVal)
{
   if(this != &origVal) 
   {
      Make_Empty(root);
      root = Copy(origVal.root);
      lastFound = root;
      size = origVal.size;
   }
   return *this;
}




// Insert
//    - parameters : insElem - element to be inserted
//                 : TN - a treenode pointer
//    - recursively inserts insElem into tree (does nothing if
//         it is already there), and corrects balances
template <class Etype>
void AVLTree<Etype>::Insert(const Etype& insElem, AVLTreeNode<Etype>*& TN)
{
   if (TN == NULL) 
   {
      // Create and insert the node with value insElem
      TN = new AVLTreeNode<Etype>();
      TN->element = insElem;
      TN->height = 0; 
      size++; 
      return;
   }
   else if (insElem < TN->element )
   {
      RecentCompares++;

      // insert in the left subtree
      Insert(insElem, TN->left );

      // check balance condition
      if ( NodeHt(TN->left) - NodeHt(TN->right) == 2) 
      {

         // if unbalanced, determine type of rotation
         if (insElem< TN->left->element ) 
         {
            // if inserted in left-most subtree, do single
            SingleRightRotation(TN);
         }
         else 
         {
           // if inserted in interior subtree, do double
           DoubleRightRotation(TN);
         }

      }
      else 
      {
         // if balanced, recalculate height (because an
         //   insertion occured further down the tree)
         CalculateHeight(TN);
      }
   }
   else if (insElem > TN->element ) 
   {
      RecentCompares++;

      // insert in the right subtree
      Insert(insElem, TN->right );

      // check balance condition
      if ( NodeHt(TN->right) - NodeHt(TN->left) == 2) 
      {
         // if unbalanced, determine type of rotation
         if (insElem > TN->right->element) 
         {
            // if inserted in right-most subtree, do single
            SingleLeftRotation(TN);
         }
         else 
         {
            // if inserted in interior subtree, do double
            DoubleLeftRotation(TN);
         }
      }
      else 
      {
         // if balanced, recalculate height (because an
         //   insertion occured further down the tree)
         CalculateHeight(TN);
      } 
   }
   // else insElem is in the tree already--do nothing
}




// Remove
//    - parameters : remElem - element to be removed
//                 : TN - a treenode pointer
//    - recursively removes remElem from tree if it is in tree
//        and corrects balances 
template <class Etype>
void AVLTree<Etype>::Remove(const Etype& remElem, AVLTreeNode<Etype>*& TN)
{
   AVLTreeNode<Etype>* tmp_cell;

   if (TN == NULL) 
      return;
   else if (remElem < TN->element) 
   {
      RecentCompares++;

      // remove from the left subtree
      Remove(remElem, TN->left);

      // check balance condition
      if (NodeHt(TN->right) - NodeHt(TN->left) == 2) 
      {
         // if unbalanced, determine type of rotation
         if (NodeHt(TN->right->right) >= NodeHt(TN->right->left))
            SingleLeftRotation(TN);
         else 
            DoubleLeftRotation(TN);
      }
      else 
      {
         // if balanced, recalculate height (in case a removal
         //   and rotation occured further down the tree)
         CalculateHeight(TN);
      }
   }
   else if (remElem > TN->element) 
   {
      RecentCompares++;

      // remove from the right subtree
      Remove(remElem, TN->right);

      // check balance condition
      if (NodeHt(TN->right) - NodeHt(TN->left) == -2) 
      {
         // if unbalanced, determine type of rotation
         if (NodeHt(TN->left->left) >= NodeHt(TN->left->right)) 
            SingleRightRotation(TN);
         else 
            DoubleRightRotation(TN);
      }
      else 
      {
         // if balanced, recalculate height (in case a removal
         //   and rotation occured further down the tree)
         CalculateHeight(TN);
      }
   }
   else  // remElem == TN->element
   { 
      if ((TN->left != NULL) && (TN->right != NULL) ) 
      {
         RecentCompares++;
 
         // remElem has 2 children--replace TN with its inorder successor
         tmp_cell = Find_Min(TN->right);
         TN->element = tmp_cell->element;
         Remove(TN->element, TN->right);

         // rebalancing work
         if ((NodeHt(TN->right) - NodeHt(TN->left)) == 2)
         {
            if (NodeHt(TN->right->right) >= NodeHt(TN->right->left))
               SingleLeftRotation(TN);
            else
               DoubleLeftRotation(TN);
         }
         else if ((NodeHt(TN->right) - NodeHt(TN->left)) == -2)
         {
            if (NodeHt(TN->left->left) >= NodeHt(TN->left->right))
               SingleRightRotation(TN);
            else
               DoubleRightRotation(TN);
         }
         else // balance okay
            CalculateHeight(TN);

      }
      else 
      {
         // X has 0 children or 1 child
         tmp_cell =  TN;
         if (TN->left == NULL) // no left child or no children at all
	    TN = TN->right;
         else if (TN->right == NULL)   // no right child
	    TN = TN->left;
         delete tmp_cell;
         size--;
      }
   }
}



// Single left rotation
//   Performs a rotation between a node (k2) and its
//    right child, updating the heights of both.
//   Can be called only if k2 has a right child.
template <class Etype>
void AVLTree<Etype>::SingleLeftRotation( AVLTreeNode<Etype>* &k2 )
{
  AVLTreeNode<Etype> *k1 = k2->right;

  // rotate k1 up to "root" and k2 down to left
  k2->right = k1->left;
  k1->left = k2;

  CalculateHeight(k2);
  CalculateHeight(k1);

  // reset the root
  k2 = k1;
}


// Double left rotation
//   Performs a right-left rotation, also known as a
//    double left rotation.  Can only be called if k3
//    has a right child and k3's right child has a left
//    child.
template <class Etype>
void AVLTree<Etype>::DoubleLeftRotation( AVLTreeNode<Etype>* &k3 )
{
  SingleRightRotation(k3->right);
  SingleLeftRotation(k3);
}



template <class Etype>
void AVLTree<Etype>::CalculateHeight(AVLTreeNode<Etype>* P)
{
   if (NodeHt(P->left) > NodeHt(P->right))
      P->height = NodeHt(P->left) + 1;
   else
      P->height = NodeHt(P->right) + 1;
}



// Single right rotation
//   Performs a rotation between a node (k2) and its
//    left child, updating the heights of both.
//   Can be called only if k2 has a left child.
template <class Etype>
void AVLTree<Etype>::SingleRightRotation( AVLTreeNode<Etype>* &k2 )
{
  AVLTreeNode<Etype> *k1 = k2->left;

  // rotate k1 up to "root" and k2 down to right
  k2->left = k1->right;
  k1->right = k2;

  // recalculate heights for rotated nodes
  CalculateHeight(k2);
  CalculateHeight(k1);

  // reset the root
  k2 = k1;
}


// Double right rotation
//   Performs a left-right rotation, also known as a
//    double right rotation.  Can only be called if k3
//    has a left child and k3's left child has a right
//    child.
template <class Etype>
void AVLTree<Etype>::DoubleRightRotation(AVLTreeNode<Etype>* &k3 )
{
  SingleLeftRotation(k3->left);
  SingleRightRotation(k3);
}



// Last
//    - returns element in the last node looked up
template <class Etype>
Etype AVLTree<Etype>::Last() const
{
   if (lastFound != NULL)
      return lastFound->element;
   else
   {
      Etype x;
      return x;   // return default Etype; user needs to be able
                  //   to tell the difference
   }
}




template <class Etype>
AVLTreeNode<Etype>* AVLTree<Etype>::Copy(const AVLTreeNode<Etype> *T)
{
    if( T != NULL )
        return new AVLTreeNode<Etype>
            (T->element, Copy(T->left), Copy(T->right), T->height);
    else
        return NULL;
}


template <class Etype>
void AVLTree<Etype>::Make_Empty(AVLTreeNode<Etype>*& T)
{
   if(T != NULL)
   {
      Make_Empty(T->left);
      Make_Empty(T->right);
      delete T;
      T = NULL;
   }
}


template <class Etype>
void
AVLTree<Etype>::PreOrder(const AVLTreeNode<Etype> *T) const
{
   if (T == NULL)
      return;
   else
   {
      cout << T->element << endl;
      PreOrder(T->left);
      PreOrder(T->right);
   }
}

template <class Etype>
void AVLTree<Etype>::InOrder(const AVLTreeNode<Etype> *T) const
{
   if (T == NULL)
      return;
   else
   {
      InOrder(T->left);
      cout << T->element << endl;
      InOrder(T->right);
   }
}


template <class Etype>
void AVLTree<Etype>::PostOrder(const AVLTreeNode<Etype> *T) const
{
   if (T == NULL)
      return;
   else
   {
      PostOrder(T->left);
      PostOrder(T->right);
      cout << T->element << endl;
   }
}






template <class Etype>
AVLTreeNode<Etype>*
AVLTree<Etype>::Find( const Etype & X, AVLTreeNode<Etype> * T )
{
    if (T == NULL)
       return NULL;
    else if( X < T->element )
    {
       RecentCompares++;
       TotalCompares++;

       return Find( X, T->left );
    }
    else if( X > T->element )
    {
       RecentCompares++;
       TotalCompares++; 

       return Find( X, T->right );
    }
    else
       return T;
}


// This is a recursive version
template <class Etype>
AVLTreeNode<Etype>* AVLTree<Etype>::Find_Min( AVLTreeNode<Etype> *T ) const
{
    if (T == NULL )
       return NULL;
    else if( T->left == NULL )
       return T;
    else
       return Find_Min(T->left);
}



// This is the similar non-recursive version
template <class Etype>
AVLTreeNode<Etype>* AVLTree<Etype>::Find_Max(AVLTreeNode<Etype>* T ) const
{
   if (T != NULL)
      while(T->right != NULL)
         T = T->right;
   return T;
}



// operator<< 
// - parameters : Out - an ostream reference 
// : outputAVLTree - a AVL tree to write to output
//    - return value : an ostream reference
//    - writes the given AVL tree to the given output stream
template<class Etype>
ostream& operator<<(ostream& Out, const AVLTree<Etype>& outputAVLTree)
{
  AVLTree<Etype> treeCopy=outputAVLTree;  // Make a copy of the tree
  KeyPair<String, int> temp;


  // Remove KeyPairs from the AVL tree copy until it is empty and
  //   output them into a file.
  while( !treeCopy.IsEmpty() )
  {
    treeCopy.Find_Min();
    temp = treeCopy.Last();
    Out << "2 " << temp << endl;    // Ouput a "2" to signify AVL tree
    treeCopy.Remove(temp);
  }

  return Out;
}


// operator>>
// - parameters : In - an istream reference
// : inputAVLTree - a AVL tree to read from input
//    - return value : an istream reference
//    - reads a AVL tree from the given input stream
template<class Etype>
istream& operator>>(istream& In, AVLTree<Etype>& inputAVLTree)
{
  KeyPair<String, int> temp;
  int type;

  // While there is still data in the input file and the data
  //   corresponds to the AVK tree (i.e. type flag == 2) then
  //   continue to read in KeyPairs and insert them into the tree.   
  while( (In >> type >> temp) && (type == 2) )
  {
    inputAVLTree.Insert(temp);
  }

  // CLear the statistics
  inputAVLTree.ClearStats();

  return In;
}
