/***************************************************
 * avltree.h                                       *
 *                                                 *
 *  Interface 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 AVLTree: ClearStats, ReturnTotal,*
// *         ReturnRecent, operator<<, operator>>, two *
// *         counters: TotalCompares & RecentCompares. *
// *       - modified the Find, Insert and Remove fns. *
// *                                                   *
// *****************************************************


#ifndef AVLTREE_H
#define AVLTREE_H



// **************************************************************
// *                                                            *
// *  Class : AVLTreeNode                                       *
// *                                                            *
// *  A node class for the AVL implementation                   *
// *                                                            *
// **************************************************************

template <class Etype>
class AVLTreeNode
{
protected:

   // AVLTreeNode
   //    - default constructor
   //    - initializes node to default values
   AVLTreeNode() : element(), left(NULL), right(NULL), height(0) {}


   // AVLTreeNode
   //    - constructor
   //    - parameters : elmt - initialization element
   //                 : leftPtr - initialization left pointer
   //                 : rightPtr - initialization right pointer
   //                 : hgt - initialization of height
   //    - initializes node to parameter values 
   AVLTreeNode(Etype elmt, AVLTreeNode* leftPtr = NULL, 
                 AVLTreeNode* rightPtr = NULL, int hgt = 0) :
            element(elmt), left(leftPtr), right(rightPtr), height(hgt) {}

   Etype element;            // element of node
   AVLTreeNode* left;        // pointer to left subtree
   AVLTreeNode* right;       // pointer to right subtree
   int height;               // height of node


   // AVLTree is a friend class so that the AVLTree has access to 
   // the protected node data
   friend class AVLTree<Etype>;
};




// **************************************************************
// *                                                            *
// *  Class : AVLTree                                           *
// *                                                            *
// *  The interface class for the AVL implementation            * 
// *                                                            *
// **************************************************************

template <class Etype>
class AVLTree 
{
public:

   // AVLTree
   //    - default constructor 
   //    - initializes tree to be empty
   AVLTree(); 



   // AVLTree
   //    - copy constructor
   //    - parameters : origVal - previously allocated AVLTree object
   //    - initializes object to be a copy of origVal
   AVLTree(const AVLTree& origVal); 



   // ~AVLTree
   //    - destructor
   //    - deletes dynamically allocated memory
   virtual ~AVLTree(); 



   // operator= 
   //    - parameters : origVal - previously allocated AVLTree object
   //    - return value - const reference to this object
   //    - sets object to be a copy of origVal
   const AVLTree& operator=(const AVLTree& origVal);



   // Make_Empty
   //    - clears the tree 
   void Make_Empty()
        { Make_Empty(root); root = lastFound = NULL; size=0; }



   // PreOrder
   //    - prints tree in preorder format; assumes Etype has operator<<
   //       defined
   void PreOrder() const
        { PreOrder(root); }



   // InOrder
   //    - prints tree in inorder format; assumes Etype has operator<<
   //       defined
   void InOrder() const
        { InOrder(root); }



   // PostOrder
   //    - prints tree in postorder format; assumes Etype has operator<<
   //       defined
   void PostOrder() const
        { PostOrder(root); }



   // Find
   //    - parameters : searchElem - element to be found
   //    - return value : boolean integer
   //    - returns 1 if searchElem is found in tree, 0 else
   //        also, if found, points internal pointer to that node 
   virtual int Find(const Etype& searchElem)
        { 
	  RecentCompares = 0;

	  return int(lastFound = Find(searchElem, root)); 
	}



   // Find_Min
   //    - return value : boolean integer
   //    - returns 1 if there is a minimum element, 0 else;
   //        also, if there is one, internal pointer points
   //        to it
   virtual int Find_Min()
        { return int(lastFound = Find_Min(root)); }



   // Find_Max
   //    - return value : boolean integer
   //    - returns 1 if there is a maximum element, 0 else;
   //        also, if there is one, internal pointer points
   //        to it
   virtual int Find_Max()
        { return int(lastFound = Find_Max(root)); }



   // Insert
   //    - parameters : insElem - element to be inserted
   //    - inserts insElem into tree (does nothing if it is
   //         already there
   virtual void Insert(const Etype& insElem)
        { 
	  RecentCompares = 0;

	  Insert(insElem, root); 

	  TotalCompares += RecentCompares;
	}



   // Remove
   //    - parameters : remElem - element to be removed
   //    - removes remElem from tree if it is in tree
   virtual void Remove(const Etype& remElem)
        { 
	  RecentCompares = 0;

	  Remove(remElem, root); 

	  TotalCompares += RecentCompares;
	}



   // IsEmpty
   //    - return value : boolean integer
   //    - returns 1 if tree is empty, 0 otherwise
   virtual int IsEmpty() const
        { return (root == NULL); }



   // Size
   //    - return value : size of tree
   //    - returns number of elements in tree
   int Size() const
        { return size;}



   // Last
   //    - return value : object of the generic type
   //    - returns copy of element in the last node looked up;
   //         if no node to return, return default object
   virtual Etype Last() const;

   // ClearStats
   //    - return value : none
   //    - clears the _total_ and _recent_ statistics
   void ClearStats()
   { TotalCompares = RecentCompares = 0; }


   // ReturnTotal
   //    - return value : integer
   // - returns a number corresponding to the _total_ number
   //      of compares done traversing the BS tree
   int ReturnTotal() const
   { return TotalCompares; }


   // ReturnRecent
   //    - return value : integer
   // - returns a number corresponding to the total number of
   //      compares performed on the last traversal of the tree
   //      ... this traversal could be an Insert, Remove or Find   
   int ReturnRecent()
   { return RecentCompares; }


   // 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
   friend ostream& operator<<(ostream& Out, const AVLTree<Etype>& outputAVLTree);


   // 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
   friend istream& operator>>(istream& In, AVLTree<Etype>& inputAVLTree);

protected:


   // Copy
   //    - parameters : TN - a treenode pointer
   //    - return value : a treenode pointer
   //    - makes a new treenode which is a copy of the
   //        parameter node, and returns it
   AVLTreeNode<Etype>* Copy(const AVLTreeNode<Etype>* TN);



   // Make_Empty
   //    - parameters : TN - reference to a treenode pointer
   //    - recursively clears the tree
   void Make_Empty( AVLTreeNode<Etype>*& TN);



   // PreOrder
   //    - parameters : TN - reference to a tree node pointer
   //    - recursively prints tree in preorder format; assumes Etype has
   //       has operator<< defined
   void PreOrder(const AVLTreeNode<Etype>* TN) const;



   // InOrder
   //    - parameters : TN - reference to a tree node pointer
   //    - recursively prints tree in inorder format; assumes Etype has
   //       has operator<< defined
   void InOrder(const AVLTreeNode<Etype>* TN) const;


   // PostOrder
   //    - parameters : TN - reference to a tree node pointer
   //    - recursively prints tree in postorder format; assumes Etype has
   //       has operator<< defined
   void PostOrder(const AVLTreeNode<Etype>* TN) const;



   // Find
   //    - parameters : searchElem - element to be found
   //                 : TN - a treenode pointer
   //    - return value : treenode pointer
   //    - returns 1 if searchElem is found in tree, 0 else
   //        also, if found, returns pointer to that node
   AVLTreeNode<Etype>* Find(const Etype& searchElem, 
                           AVLTreeNode<Etype>* TN);


   // Find_Min
   //    - parameters : TN - a treenode pointer
   //    - return value : treenode pointer
   //    - returns pointer to the minimum value in tree
   AVLTreeNode<Etype>* Find_Min(AVLTreeNode<Etype>* TN) const;



   // Find_Max
   //    - parameters : TN - a treenode pointer
   //    - return value : treenode pointer
   //    - returns pointer to the maximum value in tree
   AVLTreeNode<Etype>* Find_Max(AVLTreeNode<Etype>* TN) const;



   // 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
   void Insert(const Etype& insElem, AVLTreeNode<Etype>*& TN);


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


   AVLTreeNode<Etype>* root;         // pointer to root node of tree
   AVLTreeNode<Etype>* lastFound;    // pointer to node that was 
                                     //   located during last search
   int size;                         // number of nodes in tree

   int TotalCompares;                // number of Total compares on AVL tree 
   int RecentCompares;               // number of Recent compares on AVL tree


   // ***** Additional Helper Functions (not in original BST class)

   // NodeHt
   //    - parameters : TN - a treenode pointer    
   //    - return value : integer height of node
   //    - returns node's height; returns -1 if pointer is NULL
   int NodeHt(AVLTreeNode<Etype>* TN)
       { return (TN ? TN->height : -1); }


   // CalculateHeight
   //    - parameters : TN - a treenode pointer 
   //    - correctly sets TN's height; assumes correct
   //        subtree heights
   void CalculateHeight(AVLTreeNode<Etype>* TN);


   // SingleRightRotation
   //    - parameters : k2 - root of subtree
   //    - 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.
   void SingleRightRotation(AVLTreeNode<Etype>*& k2);


   // DoubleRightRotation
   //   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.
   void DoubleRightRotation(AVLTreeNode<Etype>*& k3);


   // SingleLeftRotation
   //   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.
   void SingleLeftRotation(AVLTreeNode<Etype>*& k2);


   // DoubleLeftRotation
   //   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.
   void DoubleLeftRotation(AVLTreeNode<Etype>*& k3);

};


// These lines necessary to allow CC to understand the template
//   friend function operator<<
template <class Etype>
ostream& operator<<(ostream& Out, const AVLTree<Etype>&);


// These lines necessary to allow CC to understand the template
// friend function operator>>
template <class Etype>
istream& operator>>(istream& In, AVLTree<Etype>&);

#endif
