// file: MapAVL.template// Template implementation file for the MapAVL class/*--------------------------------------------------------------------------*//*                                                                          *//*  This class implements a map using AVL trees                             *//*                                                                          *//*- Modification History ---------------------------------------------------*//*  When:       Who:                    Comments:                           *//*                                                                          *//*  18-Mar-92   Christopher G. Healey   Initial implementation              *//*  07-Jan-93   Christopher G. Healey   Converted to work as a dictionary   *//*  04-Jul-93   Christopher G. Healey   Converted to C++                    *//*  28-Jul-98   Felix Chang             Change the interface to             *//*                                        follow the other Map template     *//*                                        class examples.                   *//*  20-Jun-01   Paul Carter             Changed so that this class is       */
/*                                      derived from MapAbstract base class */
/*--------------------------------------------------------------------------*/template <class Key, class Value>MapAVL<Key,Value>::MapAVL( )// Default constructor
// POST: An empty MapAVL is created{   root = NULL;}template <class Key, class Value>MapAVL<Key,Value>::MapAVL( const MapAVL<Key,Value>& someMapAVL )// Copy constructor
// POST: A new MapAVL is created containing the same elements as originalMapAVL{   copy( someMapAVL );}template <class Key, class Value>MapAVL<Key,Value>::~MapAVL()// Destructor
// POST: The MapAVL object is destroyed{   eraseTree( root );}template <class Key, class Value>MapAVL<Key,Value>& MapAVL<Key,Value>::operator=( const MapAVL<Key,Value>& someMapAVL )// Member operator function
// POST:  The contents of 'otherMapAVL' are copied into the current MapAVL{   if ( &someMapAVL != this )   {      eraseTree( root );      copy( someMapAVL );   }   return *this;}template <class Key, class Value>bool MapAVL<Key,Value>::empty( const Key& key ) const// Pre: key has been initialized
// Post: if the key is not in the map true is returned; otherwise
// false is returned{   MapAVLNode<Key,Value>* ptr = root;   while(ptr != NULL)   {     if (ptr->key == key)     {        return false;     }     if (ptr->key < key)     {        ptr = ptr->right;     }     else     {        ptr = ptr->left;     }   }

   return true;}template <class Key, class Value>void MapAVL<Key,Value>::erase( const Key& key )// Pre: key has been initialized
// Post: if key is in the map it has been removed; otherwise
// map is not changed{   bool shorter;                      // Tree shorter flag   root = eraseNode( root, key, shorter );}template <class Key, class Value>MapAVLNode<Key,Value>* MapAVL<Key,Value>::eraseNode( MapAVLNode<Key,Value>* tree, const Key& key, bool& shorter )// Private helper function that erases a key from a subtree.
// PRE:   key has been initialized
// POST:  If key is already in the tree, then it is deleted (and the new root returned)
//        otherwise map is not changed
//        Also, shorter will be set according to whether the tree has become shorter or not.{   //  ******************* Case 1 *******************   //  First possibility, root is NULL, so this is the bottom of the tree.   //  Node with given key certainly doesn't exist; so return NULL.   if ( tree == NULL )   {      shorter = false;            // Height of tree unchanged      return NULL;   }   //  ******************* Case 2 *******************   //  Second possibility, key equal to root's key, so found node. Node to   //  delete has two children, find it's predecessor, copy predecessor's   //  info into the root node, then delete the predecessor   if ( tree->key == key && tree->left && tree->right )   {      MapAVLNode<Key,Value>* child;    // Child of root node      // Find the predecessor of root.      child = tree->left;      while( child->right != NULL ) {         child = child->right;      }      tree->key = child->key;      tree->value = child->value;      tree->left = eraseNode( tree->left, child->key, shorter );      //  If the subtree shrunk in size, we must check to see if we are now      //  unbalanced. There are three possible cases:      //      //  1. currently LH, left subtree shrunk, so we are now EQ, and we      //     report that this tree shrunk in height      //  2. currently EQ, left subtree shrunk, so we are now RH, and we      //     report that this tree did not shrink in height      //  3. currently RH, left subtree shrunk, so we are out of balance,      //     and must perform a rotation to bring ourselves back into balance      //      //  If the subtree didn't shrink in size, then we didn't shrink either      if ( shorter )        {          switch( tree->factor )          // Determine current balancing factor          {            case LH:                      // Now, left and right same height               shorter = true;               tree->factor = EQ;               return tree;            case EQ:                      // Now, right 1 higher than left               shorter = false;               tree->factor = RH;               return tree;            case RH:                      // Now, we must rebalance                shorter = (tree->factor != EQ);               return rightBalance( tree );           }           shorter = false;    // If subtree isn't shorter, then this tree isn't shorter either.           return tree;        }   }   //  ******************* Case 3 *******************   //  Third possibility, key equal to root's key, so found node. Node to   //  delete has at most one child, simply have the parent point around   //  it to it's child subtree, or NULL if no subtrees exist   if ( tree->key == key )   {      shorter = true;   // Subtree is shorter      if ( tree->left )   // Root has left subtree?      {        MapAVLNode<Key,Value>* result = tree->left;        delete tree;        // The following code is necessary as of Release 3.4.0 of g++        // The code        //        //     count--;        //        // does not work because members inherited from the base class        // are not recognized in standard C++.  They either have to be        // fully qualified (as below) or you can instead say        //        //     this->count--;        //        MapAbstract<Key,Value>::count--;        return result;      }      if ( tree->right )   // Root has right subtree?      {        MapAVLNode<Key,Value>* result = tree->right;        delete tree;        MapAbstract<Key,Value>::count--;        return result;      }      // No left nor right subtree      delete tree;      MapAbstract<Key,Value>::count--;      return NULL;   }   //  ******************* Case 4 *******************   //  Fourth possibility, key is less than root's key, so search the left   //  subtree recursively   if ( tree->key > key )   {      tree->left = eraseNode( tree->left, key, shorter );      //  If the subtree shrunk in size, we must check to see if we are now      //  unbalanced.  There are three possible cases:      //      //  1. currently LH, left subtree shrunk, so we are now EQ, and we      //     report that this tree shrunk in height      //  2. currently EQ, left subtree shrunk, so we are now RH, and we      //     report that this tree did not shrink in height      //  3. currently RH, left subtree shrunk, so we are out of balance,      //     and must perform a rotation to bring ourselves back into balance      //      //  If the subtree didn't shrink in size, then we didn't shrink, either      if ( shorter )      {         switch( tree->factor )         // Determine current balancing factor         {          case LH:                      // Now, left and right same height             shorter = true;             tree->factor = EQ;             return tree;          case EQ:                      // Now, right 1 higher than left             shorter = false;             tree->factor = RH;             return tree;          case RH:                      // Now, we must rebalance              shorter = (tree->factor != EQ);             return rightBalance( tree );         }      }      // If subtree isn't shorter, then this tree isn't shorter either.      // So just return the tree.      return tree;   }   //  ******************* Case 5 *******************   //  Fifth (final) possibility, key is greater than root's key, so search the   //  right subtree recursively   tree->right = eraseNode( tree->right, key, shorter );   //  If the subtree shrunk in size, we must check to see if we are now   //  unbalanced, As mentioned in class, there are three possible cases:   //   //  1. currently RH, right subtree shrunk, so we are now EQ, and we   //     report that this tree shrunk in height   //  2. currently EQ, right subtree shrunk, so we are now LH, and we   //     report that this tree did not shrink in height   //  3. currently LH, right subtree shrunk, so we are out of balance,   //     and must perform a rotation to bring ourselves back into balance   //   //  If the subtree didn't shrink in size, then we didn't shrink, either   if ( shorter )   {      switch( tree->factor )            // Determine current balancing factor      {          case RH:                      // Now, left and right same height             shorter = true;             tree->factor = EQ;             return tree;          case EQ:                      // Now, left 1 higher than right             shorter = false;             tree->factor = LH;             return tree;          case LH:                      // Now, we must rebalance ourselves             shorter = (tree->factor != EQ );             return leftBalance( tree );      }   }   // If subtree isn't shorter, then this tree isn't shorter either.   // So just return the tree.   return tree;}template <class Key, class Value>Value& MapAVL<Key,Value>::operator[]( const Key& key )// Pre: key has been initialized
// Post: if key is in the map, reference to value corresponding to key 
//       has been returned; otherwise key has been added to map with 
//       corresponding default value
// Exception: if not enough memory to add key, map_full has been thrown{   MapAVLNode<Key,Value>* ptr;   if (root == NULL)  // No such key. So add it.   {     return add(key);   }   ptr = root;   while( true )   {     if (ptr->key == key)     {        return ptr->value;     }     if (ptr->key < key)     {        if (ptr->right == NULL)  // No such key. So add it.        {           return add(key);        }        ptr = ptr->right;     }     else     {        if (ptr->left == NULL)  // No such key. So add it.        {           return add(key);        }        ptr = ptr->left;     }   }}
template <class Key, class Value>
Value& MapAVL<Key,Value>::add( const Key& key )
// Private helper function that adds a key to a tree.
// PRE:   key has been initialized
// POST:  If key is not already in the tree, then it is added.
//        otherwise map is not changed.
// Exception: if not enough memory to add key, map_full exception is thrown
{
   bool  taller;         // Tree taller flag
   
   try
   {
      root = addNode( root, key, taller );
   }
   catch( bad_alloc& )
   {
      throw map_full();
   }

   return (*this)[key];
}


template <class Key, class Value>
MapAVLNode<Key,Value>* MapAVL<Key,Value>::addNode( MapAVLNode<Key,Value>* tree, const Key& key, bool& taller )
// Private helper function that adds a key to a subtree.
// PRE:   key has been initialized 
// POST:  If key is not already in the tree, then it is added (and the new root returned)
//        otherwise map is not changed
//        Also, taller will be set according to whether the tree has grown taller or not.
{
   //  First possibility, root is NULL, so this is the bottom of the tree.
   //  Create a new leaf node, update it's information, and return

   if ( tree == NULL )
   {
      MapAbstract<Key,Value>::count++;
      tree = new MapAVLNode<Key,Value>;
      tree->key = key;
      tree->factor = EQ;
      tree->left = NULL;
      tree->right = NULL;
      taller = true;                    // Height of tree has increased
      return tree;                      // Return pointer to new node
   }

   //  Second possibility, the key stored at this node is the same as the
   //  key we want to add, so just return its address.

   if ( tree->key == key )
   {
      taller = false;                 // Height of tree unchanged
      return tree;
   }

   //  Third possibility, the key we want to insert is less than the
   //  key stored in the current node, so insert in the left subtree

   if ( tree->key > key )
   {
      tree->left = addNode( tree->left, key, taller );

      //  If the subtree grew in size, we must check to see if we are now
      //  unbalanced. As mentioned in class, there are three possible cases:
      //
      //  1. currently RH, so left subtree grew, so we are now EQ, and we
      //     report that this tree did not grow in height
      //  2. currently EQ, so left subtree grew, so we are now LH, and we
      //     report that this tree did grow in height
      //  3. currently LH, so left subtree grew, so we are out of balance,
      //     and must peform a rotation to bring ourselves back into balance
      //
      //  If the subtree didn't grow in size, than we didn't grow, either.