//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MBN 06/28/89 -- Initial design and implementation
// Updated: MBN 08/20/89 -- Updated template usage to reflect new syntax
// Updated: MBN 09/19/89 -- Added conditional exception handling
// Updated: DKM 11/05/89 -- Replaced re-balance after exceeding goal height
//                          with true AVL rotation alorythm.
// Updated: LGO 12/04/89 -- operator<< not inline
// Updated: LGO 12/04/89 -- balance not inline
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The AVL_Tree<Type> class implements height-balanced, dynamic,  binary trees.
// The  AVL_Tree<Type> class is  publicly derived   from  the Binary_Tree<Type>
// class and  both  are parameterized  over some type   Type. An AVL  tree is a
// compromise  between the  expense  of a  fully balanced binary  tree and  the
// desire for efficient search times for both average and worst case scenarios.
// As a result, an AVL tree  maintains a  binary tree that  is height-balanced,
// insuring that the minimum and maximum depth  of any path  through the binary
// tree is within some specified range.
//
// The  AVL_Tree<Type>  class has  no private  data slots   and only two public
// constructors.  The first constructor  takes an optional argument that allows
// the user  to  specify  the height-balance limit  (the   default is  two).  A
// height-balance  value   of  zero indicates    that  the  tree should  remain
// completely balanced.   The second  constructor  takes a reference to another
// AVL_Tree<Type> and duplicates its size and values.
//
// The  AVL_Tree<Type>  class   inherits  all its   methods  publicly from  the
// Binary_Tree<Type> class. The only methods that are overloaded are those that
// affect  the structure of  the tree, thus  potentially requiring  one or more
// subtrees to be shaken and restructured.
//

#ifndef AVL_TREEH				// If no definition for class
#define AVL_TREEH

#ifndef BINARY_TREEH				// If no definition for class
#include <cool/Binary_Tree.h>			// include definition file
#endif

// DECLARE Binary_Tree<Type>, but ensure it's only done once.
template <class Type> AVL_Tree {
#ifndef declare_Binary_Tree_##Type
#define DECLARE_Binary_Tree_##Type
  DECLARE Binary_Tree<Type>;
#endif
}

#define AVL_Tree_state BT_State

template <class Type>
class AVL_Tree<Type> : public Binary_Tree<Type> {
  
public:
  inline AVL_Tree<Type> () {};			// Simple constructor
  AVL_Tree<Type> (const AVL_Tree<Type>&);	// Constructor for reference
  AVL_Tree<Type> (const Binary_Tree<Type>&);	// Convert BT into AVL
  ~AVL_Tree<Type> ();				// Destructor

  inline Boolean put (const Type&);		// Add an item to tree
  inline Boolean remove (const Type&);		// Remove item from tree
  inline Boolean remove ();			// Remove item current position
  void balance ();				// Special balance for AVL
  inline AVL_Tree<Type>& operator= (AVL_Tree<Type>&);  // Assignment overloaded
  inline AVL_Tree<Type>& operator= (Binary_Tree<Type>&);//Assignment overloaded
  friend ostream& operator<< (ostream&, const AVL_Tree<Type>&);
  friend ostream& operator<< (ostream&, const AVL_Tree<Type>*);
};

// IMPLEMENT Binary_Tree<Type>, but ensure it's only done once.
template <class Type> AVL_Tree {
ONCE_ONLY(IMPLEMENT_Binary_Tree_##Type) {
  IMPLEMENT Binary_Tree<Type>;
}}


// ~AVL_TREE -- Destructor (not inline because it's virtual)
template <class Type>
AVL_Tree<Type>::~AVL_Tree<Type> () {}


// AVL_TREE -- Reference to AVL_Tree

template <class Type>
AVL_Tree<Type>::AVL_Tree<Type> (const AVL_Tree<Type>& b)
#ifdef __cplusplus
 : Binary_Tree<Type>(b)
#else
 : (b)
#endif
{
  IGNORE (b);
}			      

// AVL_TREE -- Reference to Binary_Tree (Copies BT, and make AVL out of it)

template <class Type>
AVL_Tree<Type>::AVL_Tree<Type> (const Binary_Tree<Type>& b)
#ifdef __cplusplus
 : Binary_Tree<Type>(b)
#else
 : (b)
#endif 
{
  IGNORE (b);
  this->balance();		     	// Do an AVL balance on new tree
}			      


// put -- Add a value to the AVL tree if it is not already there and balance
//        tree if necessary
// Input: Reference to value to add to tree
// Output: TRUE if item added, FALSE otherwise

template <class Type> 
inline Boolean AVL_Tree<Type>::put (const Type& value) {
  return (Binary_Tree<Type>::put_internal (value, TRUE)); 
}


// remove -- Remove a value from the AVL tree. Deletion of a node and balance
//           tree if necessary
// Input:    Reference to value to remove
// Output:   TRUE if item removed, FALSE otherwise

template <class Type> 
inline Boolean AVL_Tree<Type>::remove (const Type& value) {
  return (Binary_Tree<Type>::remove_internal (value, TRUE)) ;
}


// remove -- Remove node at current position in the tree and balance tree
// Input:    None
// Output:   Value of node removed from tree

template <class Type> 
inline Boolean AVL_Tree<Type>::remove () {
  return (Binary_Tree<Type>::remove_internal(this->value(),TRUE));
}

// balance  -- Rebalance an AVL tree, and then recalculate each node's
//             balance (right subtree depth minus left subtree depth)
// input:      None
// Output:     None

template <class Type>
void AVL_Tree<Type>::balance () {
  Binary_Tree<Type>::balance();
  Binary_Tree::calc_depth (this->get_root(), 0, TRUE);
}

template <class Type> 
inline AVL_Tree<Type>& AVL_Tree<Type>::operator= (AVL_Tree<Type>& av) {
  Binary_Tree<Type>::operator= (av);		// Create the new Tree
  return *this;					// Return tree reference
}

template <class Type>
inline AVL_Tree<Type>& AVL_Tree<Type>::operator= (Binary_Tree<Type>& bt) {
  Binary_Tree<Type>::operator= (bt);		// Create the new Tree
  balance();					// Do an AVL balance
  return *this;					// Return tree reference
}


template<class Type> AVL_Tree {
ostream& operator<< (ostream& os, const AVL_Tree<Type>& av) {
  Type ## _print_tree((Binary_Node<Type>*)av.get_root(),os);
  return os;
}
}


template<class Type> AVL_Tree {
ostream& operator<< (ostream& os, const AVL_Tree<Type>* av) {
  return operator<< (os, *av);
}
}

#endif						// End AVL_TREEH #if
