mapavl.template.cpp

The existed tree implementation

// 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.