/**************************************************************************************************/
/*                                                                                                */
/*  Name:  DarC KonQuesT                                                                          */
/*  Program:  #3                                                                                  */
/*  Date:  2005.11.07                                                                             */
/*  Purpose:                                                                                      */
/*         AVLTree.h - implementation of an AVLTree, based on STL bst.h                           */
/*         Allows for insertion, deletion, searching, etc an AVL tree, keeping balance.           */
/*                                                                                                */
/*                                                                                                */
/**************************************************************************************************/

#ifndef AVLTREE
#define AVLTREE

#include <iostream>
#include <functional>

using namespace std;

//AVLTress Class
template<class T, class Compare>
class AVLTree
{
  //operator overloading
    friend ostream& operator<< (ostream& out_stream, AVLTree<string, less<string> > tree)
    {
        for (Iterator itr = tree.begin(); itr != tree.end(); itr++)
            out_stream << *itr << endl;
        return out_stream;
    } // overloading <<

protected:
        Compare compare;
        unsigned node_count;
        struct tree_node
        {
            T item;
            tree_node* parent,
                     * left,
                     * right;
            bool isHeader;
            char balance_factor;
        }; // Node

        typedef tree_node* Link;
    
        Link header;

    public:

        class Iterator;
        friend class Iterator;

/*  Name: AVLTree()  - Constructor                                                                                    */
/*  Purpose: setup root                                                                                               */
/*  Parameters:                                                                                                       */
/*  Preconditions:  have variables declared                                                                           */
/*  Postconditions:  tree ready for insertion, root node setup                                                        */
        
        AVLTree ()
        {
            header = new tree_node;
            header -> parent = NULL;
            header -> left = header;
            header -> right = header;
            header -> isHeader = true;
            node_count = 0;
            header->balance_factor = '=';
        } //  default constructor

/*  Name:  ~AVLTree - destructor                                                                                      */
/*  Purpose: deallocate AVLTree memory                                                                                */
/*  Parameters:                                                                                                       */
/*  Preconditions:  destory() implemented                                                                             */
/*  Postconditions:  AVLTree deallocated                                                                              */
        
        ~AVLTree( )
        {
            destroy(header -> parent);
        }//destructor
        
/*  Name: destroy(Link link)                                                                                          */
/*  Purpose: deallocate memory                                                                                        */
/*  Parameters: Link link                                                                                             */
/*  Preconditions: link initialized                                                                                   */
/*  Postconditions: links deallocated                                                                                 */
        
        void destroy (Link link)
        {
    	     if (link != NULL)
    	     {
                destroy (link -> left);
        	destroy (link -> right);
        	delete (link);
    	      } // if
         } // destroy method


/*  Name: size()                                                                                                      */
/*  Purpose:  return size of AVLTree                                                                                  */
/*  Parameters:                                                                                                       */
/*  Preconditions:  node_count initalized and keep up to date                                                         */
/*  Postconditions: number of nodes returned                                                                          */
        unsigned size() const
        {
              return node_count;
        } // size


/*  Name: insert(const T& item)                                                                                       */
/*  Purpose:  insert an item into the tree                                                                            */
/*  Parameters:  T& item                                                                                              */
/*  Preconditions:  item initialized                                                                                  */
/*  Postconditions: item is inserted in the tree                                                                      */
        
        Iterator insert (const T& item)
        {
            if (header -> parent == NULL)
            {
                insertLeaf (item, header, header -> parent);
                header -> left = header -> parent;
                header -> right = header -> parent;
                return (header->parent);
             } // inserting at tree's root
             else
             {
                 Link parent = header;
                 Link child = header -> parent;
                 Link ancestor = NULL;

                 while (child != NULL)
                 { 
                     parent = child;
                     if (child -> balance_factor != '=')
                         ancestor = child;
                     if (compare(item, child->item))
                       child = child->left;
                     else
                         child = child -> right;
                 } // while
                 if (compare(item, parent -> item))
                 {
                     insertLeaf(item, parent, parent -> left);
                     fixAfterInsertion(ancestor, parent->left);
                     if (header -> left == parent) // parent -> item is smallest item
                          header -> left = parent -> left;
                     return (parent->left);
                 } // insert at left of parent
                 else
                 {
                     insertLeaf(item, parent, parent -> right);
                     fixAfterInsertion(ancestor, parent->right);
                     if (header -> right == parent) //parent -> item is largest item
                         header -> right = parent -> right; // child is rightmost
                     return (parent->right);
                 } // insert at right of parent
             } // tree not empty
         } // insert


/*  Name:  fixAfterInsertion(Link ancestor, Link inserted)                                                            */
/*  Purpose:  check balance and balance factors after insertion                                                       */
/*  Parameters: Link ancestor, Link inserted                                                                          */
/*  Preconditions:  ancestor and inserted correctly initialized                                                       */
/*  Postconditions:  balance factors corrected                                                                        */
        
   
  void fixAfterInsertion(Link ancestor, Link inserted)
  {
    Link root = header->parent;
    T item = inserted->item;

    // Case 1
    if(ancestor == NULL)
    {
      if(compare(item, root->item))
        root->balance_factor = 'L';
      else
        root->balance_factor = 'R';
      adjustPath(root, inserted);
    }

    //Case 2
    else if((ancestor->balance_factor == 'L' && !compare(item, ancestor->item)) || (ancestor->balance_factor == 'R' && compare(item, ancestor->item)))
    {
      
      ancestor->balance_factor = '=';
      adjustPath(ancestor, inserted);
     }

    //Case 3
    else if(ancestor->balance_factor == 'R' && !compare(item, ancestor->right->item))
    {
      ancestor->balance_factor = '=';
      rotate_left(ancestor);
      adjustPath(ancestor->parent, inserted);
    }

    //Case 4
    else if(ancestor->balance_factor == 'L' && compare(item, ancestor->left->item))
    {
      ancestor->balance_factor = '=';
      rotate_right(ancestor);
      adjustPath(ancestor->parent, inserted);
    }

    //Case 5
    else if(ancestor->balance_factor == 'L' && !compare(item, ancestor->left->item))
    {
      rotate_left(ancestor->left);
      rotate_right(ancestor);
      adjustLeftRight(ancestor, inserted);
    }

    //Case 6
    else
    {
      rotate_right(ancestor->right);
      rotate_left(ancestor);
      adjustRightLeft(ancestor, inserted);
    }
  }


/*  Name: adjustLeftRight(Link ancestor, Link inserted)                                                               */
/*  Purpose: check and correct balance factors                                                                        */
/*  Parameters: Link ancestor, Link inserted                                                                          */
/*  Preconditions: ancestor and inserted correctly initialized                                                        */
/*  Postconditions: balance factors corrected                                                                         */
  
  void adjustLeftRight(Link ancestor, Link inserted)
  {
    T item = inserted->item;

    if(ancestor->parent == inserted)
      ancestor->balance_factor = '=';
    else if(compare(item, ancestor->parent->item))
    {
      ancestor->balance_factor = 'R';
      adjustPath(ancestor->parent->left, inserted);
    }
    else
    {
      ancestor->balance_factor = '=';
      ancestor->parent->left->balance_factor = 'L';
      adjustPath(ancestor, inserted);
    }
  }


 /*  Name: adjustRightleft(Link ancestor, Link inserted)                                                               */
 /*  Purpose: check and correct balance factors                                                                        */
 /*  Parameters: Link ancestor, Link inserted                                                                          */
 /*  Preconditions: ancestor and inserted correctly initialized                                                        */
 /*  Postconditions: balance factors corrected                                                                         */
  
 void adjustRightLeft(Link ancestor, Link inserted)
 {
    T item = inserted->item;

    if(ancestor->parent == inserted)
      ancestor->balance_factor = '=';
    else if(!compare(item, ancestor->parent->item))
    {
       ancestor->balance_factor = 'L';
       adjustPath(ancestor->parent->right, inserted);
    }      
    else
    {
      ancestor->balance_factor = '=';
      ancestor->parent->right->balance_factor = 'R';
      adjustPath(ancestor, inserted);
    }
 }
  

/*  Name: rotate_right(Link x)                                                                                        */
/*  Purpose: perform right rotation around x                                                                          */
/*  Parameters:  Link x                                                                                               */
/*  Preconditions: x correctly initialized                                                                            */
/*  Postconditions: right rotation completed                                                                          */
 
  void rotate_right(Link x)
  {

     cout << "rotate right" << endl;
    Link y = x->left;
    
    x->left = y->right;
    if(y->right != NULL)
      y->right->parent = x;
    y->parent = x->parent;
    if(x == header->parent)
      header->parent = y;
    else if(x == x->parent->right)
      x->parent->right = y;
    else
     x->parent->left = y;
    y->right = x;
    x->parent = y;
  }

/*  Name: rotate_left(Link x)                                                                                         */
/*  Purpose: perform left rotation about x                                                                            */
/*  Parameters:  Link x                                                                                               */
/*  Preconditions: x correctly initialized                                                                            */
/*  Postconditions:  left rotation about x completed                                                                  */
  
 void rotate_left(Link x)
 {
   cout << "rotate left" << endl;
   Link y = x->right;
   x->right = y->left;
   if(y->left != NULL)
     y->left->parent = x;
   y->parent = x->parent;
   if( x == header->parent)
     header->parent = y;
   else if(x == x->parent->left)
     x->parent->left = y;
   else
     x->parent->right = y;
   y->left = x;
   x->parent = y; 
 } 
  
/*  Name:  adjustPath(Link to, Link inserted)                                                                         */
/*  Purpose: adjust balance factors affected by an insertion                                                          */
/*  Parameters:  Link to, Link inserted                                                                               */
/*  Preconditions: to and inserted correctly initialized                                                              */
/*  Postconditions: balance factors corrected                                                                         */
 
  void adjustPath(Link to, Link inserted)
  {
    T item = inserted->item;
    Link temp = inserted->parent;
    while(temp != to)
       { 
         if(compare (item, temp->item))
         {
           temp->balance_factor = 'L';
         }
         else
         {
           temp->balance_factor = 'R';
         }
         temp = temp->parent;
       }
  }
         class Iterator
         {
             friend class AVLTree<T, Compare>;

             protected:

                 Link link;
                 Iterator (Link new_link) : link (new_link) {}

             public:

                 Iterator () {}
                 Iterator& operator++ ()
                 {
                      Link tempLink;

                      if ((link -> right) != NULL)
                      {
                          link = link -> right;
                          while ((link -> left) != NULL)
                              link = link -> left;
                      } // node has right child
                      else
                      {
                          tempLink = link -> parent;
                          while (link == tempLink -> right)
                          {
                              link = tempLink;
                              tempLink = tempLink -> parent;
                          } // moving up and leftward as far as possible
                          if ((link -> right) != tempLink)
                              link = tempLink;
                      } // node has no right child
                      return *this;
                 } // prefix ++

                 Iterator operator++ (int)
                 {
                     Iterator temp = *this;
                     ++(*this);
                     return temp;
                 } // postfix ++
                 Iterator& operator-- ()
                 {
                     if (link -> isHeader)
                        link = link -> right;   // Return rightmost.
                     else if (link -> left != NULL)
                     {
                         Link y = link -> left;
                         while (y -> right != NULL)
                             y = y -> right;
                         link = y;
                     } // link -> left != NULL
                     else
                     {
                         Link y = link -> parent;
                         while (link == y -> left)
                         {
                             link = y;
                             y = y -> parent;
                         } // while moving up and rightward
                         link = y;
                     } // link -> left == NULL
                     return *this;
             } // pre-decrement operator

            T& operator* () const { return link -> item; }
            bool operator== (const Iterator &otherIterator)const
            {
                return link == otherIterator.link;
            } //operator ==
            bool operator!= (const Iterator &otherIterator)const
            {
                return link != otherIterator.link;
            } // operator !=

      }; // Iterator

/*  Name:   begin ()                                                                                                  */
/*  Purpose:  return beginning of tree                                                                                */
/*  Parameters:                                                                                                       */
/*  Preconditions: tree initialized                                                                                   */
/*  Postconditions:  first node returned                                                                              */
         
     Iterator begin () { return header -> left; }


/*  Name: end ()                                                                                                      */
/*  Purpose: return space after last node                                                                             */
/*  Parameters:                                                                                                       */
/*  Preconditions: tree correctly initialized                                                                         */
/*  Postconditions: end returned                                                                                      */
     
     Iterator end () { return header; }


/*  Name:  find (const T& item)                                                                                       */
/*  Purpose:  find a node in the tree                                                                                 */
/*  Parameters:  T& item                                                                                              */
/*  Preconditions:  item correctly initialized                                                                        */
/*  Postconditions:  iterator returned pointing to item location or end() if failed                                   */
     
     Iterator find (const T& item)
      {
          Link parent = header;
          Link child = header -> parent;
          while (child != NULL)
          {
              if (!(child -> item < item))
              {
                  parent = child;
                  child = child -> left;
              } // item <= child -> item
              else
                  child = child -> right;
          } // while

          if (parent == header || item < parent->item)
              return end();
          else
              return parent;   // automatic type casting
      } // find

/*  Name: erase (Iterator itr)                                                                                        */
/*  Purpose: erase an item from the tree                                                                              */
/*  Parameters: Iterator itr                                                                                          */
/*  Preconditions:  itr corectly initialized                                                                          */
/*  Postconditions: item deleted if found                                                                             */
     
      void erase (Iterator itr)
      {
          if (itr.link -> parent -> parent == itr.link)
              deleteLink (itr.link -> parent -> parent);
          else if (itr.link -> parent -> left == itr.link)
              deleteLink (itr.link -> parent -> left);
          else
              deleteLink (itr.link -> parent -> right);
       } // erase


    protected:

/*  Name: insertLeaf (const T& item, Link parent, Link& child)                                                        */
/*  Purpose: insert a node into the tree                                                                              */
/*  Parameters: T& item, Link parent, Link& child                                                                     */
/*  Preconditions: parameters correctly initialized                                                                   */
/*  Postconditions: node inserted                                                                                     */
      
      void insertLeaf (const T& item, Link parent, Link& child)
        {
            child = new tree_node;
            child -> item = item;
            child -> parent = parent;
            child -> left = NULL;
            child -> right = NULL;
            child -> isHeader = false;
            node_count++;
            child->balance_factor = '=';
        } // insertLeaf


/*  Name:  prune (Link& link)                                                                                         */
/*  Purpose: remove node                                                                                              */
/*  Parameters: Link& link                                                                                            */
/*  Preconditions:  link correctly initialized                                                                        */
/*  Postconditions: node pointed to by link is removed                                                                */
      
      void prune (Link& link)
        {
            Link linkCopy = link,
                 newLink;

            node_count--;
            if ((link -> left == NULL) && (link -> right == NULL))
            {
                if (link == header -> left)
                    header -> left = link -> parent; // new leftmost
                if (link == header -> right)
                    header -> right = link -> parent; // new rightmost
                link = NULL;
            } // link's node is a leaf
            else if (link -> left == NULL)
            {
                link = link -> right;
                link -> parent = linkCopy -> parent;
                if (linkCopy == header -> left)
                {
                    newLink = link;
                    while ((newLink -> left) != NULL)
                        newLink = newLink -> left;
                    header -> left = newLink;  // new leftmost
                } // re-calculate leftmost
            } // link -> left nonempty
            else
            {
                 link = link -> left;
                 link -> parent = linkCopy -> parent;
                 if (linkCopy == header -> right)
                 {
                      newLink = link;
                      while ((newLink -> right) != NULL)
                          newLink = newLink -> right;
                      header -> right = newLink; // new rightmost
                 } // re-calculate rightmost
            } // root -> right nonempty
            delete linkCopy;
       } // prune


/*  Name: deleteLink (Link& link)                                                                                     */
/*  Purpose: delete a link in the tree                                                                                */
/*  Parameters:  Link& link                                                                                           */
/*  Preconditions: link correctly initialized                                                                         */
/*  Postconditions:  link removed                                                                                     */
      
      void deleteLink (Link& link)
       {
            T item = link -> item;
            Link parent = link -> parent;

            if (link -> left == NULL || link -> right == NULL) //the item has no children
                prune (link);
            else if (link -> right -> left == NULL)
            {
                parent = link;
                link -> item = link -> right ->item;
                prune(link -> right);
            } // empty left subtree

            else
            {
              Link temp = link -> right -> left;
              while (temp -> left != NULL)
                temp = temp -> left;
              parent = temp -> parent;
              link -> item = temp -> item;
              prune (temp -> parent -> left);
              
            } //neither subtree empty
       } // deleteLink



}; // AVLTree


#endif