Added test, less than functor, better comments, etc. to RB_Tree class

1 files changed, 275 insertions, 188 deletions

diff --git a/ace/RB_Tree.cpp b/ace/RB_Tree.cpp
index 3e03de0d05f..642638e33b4 100644
--- a/ace/RB_Tree.cpp
+++ b/ace/RB_Tree.cpp
@@ -13,12 +13,15 @@
 
 ACE_RCSID(ace, RB_Tree, "$Id$")
 
-/////////////////////////////////////////
-// template class RB_Tree_Node<KEY, T> //
-/////////////////////////////////////////
+/////////////////////////////////////////////
+// template class ACE_RB_Tree_Node<KEY, T> //
+/////////////////////////////////////////////
+
+
+// Constructor.
 
 template <class KEY, class T>
-RB_Tree_Node<KEY, T>::RB_Tree_Node (const KEY &k, const T &t)
+ACE_RB_Tree_Node<KEY, T>::ACE_RB_Tree_Node (const KEY &k, const T &t)
   : k_ (k)
   , t_ (t)
   , color_ (RED)
@@ -27,222 +30,286 @@ RB_Tree_Node<KEY, T>::RB_Tree_Node (const KEY &k, const T &t)
   , right_ (0)
 {
 }
-  // constructor
+
+
+// Destructor.
 
 template <class KEY, class T>
-RB_Tree_Node<KEY, T>::~RB_Tree_Node ()
+ACE_RB_Tree_Node<KEY, T>::~ACE_RB_Tree_Node ()
 {
-  // delete left sub-tree
+  // Delete left sub-tree.
   delete left_;
 
-  // delete right sub_tree
+  // Delete right sub_tree.
   delete right_;
 }
-  // destructor
 
 
 
-////////////////////////////////////
-// template class RB_Tree<KEY, T> //
-////////////////////////////////////
+////////////////////////////////////////
+// template class ACE_RB_Tree<KEY, T> //
+////////////////////////////////////////
+
+// Constructor.
 
 template <class KEY, class T>
-RB_Tree<KEY, T>::RB_Tree ()
-  : root_ (0)
+ACE_RB_Tree<KEY, T>::ACE_RB_Tree (
+  ACE_Const_Binary_Functor_Base<KEY, KEY> *less_than_functor,
+  int free_functor)
+  : root_ (0),
+    less_than_functor_ (less_than_functor),
+    free_functor_ (free_functor)
 {
+  if (less_than_functor_ == 0) 
+    {
+      less_than_functor_ = new ACE_Less_Than_Functor<KEY, KEY>;
+      free_functor_ = 1;
+    }
 }
-  // constructor
+
+
+// Copy constructor.
 
 template <class KEY, class T>
-RB_Tree<KEY, T>::RB_Tree (const RB_Tree<KEY, T> &rbt)
+ACE_RB_Tree<KEY, T>::ACE_RB_Tree (const ACE_RB_Tree<KEY, T> &rbt)
   : root_ (0)
 {
-  // make a deep copy of the passed tree
-  RB_Tree_Iterator<KEY, T> iter(rbt);
+  // Make a copy of the comparison functor.
+  less_than_functor_ = (rbt.less_than_functor_ == 0)
+                       ? 0 : rbt.less_than_functor_->clone ();
+  free_functor_ = 1;
+
+  // Make a deep copy of the passed tree.
+  ACE_RB_Tree_Iterator<KEY, T> iter(rbt);
   for (iter.first (); iter.is_done () == 0; iter.next ())
   {
     insert (*(iter.key ()), *(iter.item ()));
   }
 }
-  // copy constructor
+
+
+// Destructor.
 
 template <class KEY, class T>
-RB_Tree<KEY, T>::~RB_Tree ()
+ACE_RB_Tree<KEY, T>::~ACE_RB_Tree ()
 {
-  // clear away all nodes in the tree
+  // Free the comparison functor if needed.
+  if (free_functor_)
+    {
+      delete less_than_functor_;
+    }
+
+  // Clear away all nodes in the tree.
   clear ();
 }
-  // destructor
+
+
+// Assignment operator.
 
 template <class KEY, class T> void
-RB_Tree<KEY, T>::operator = (const RB_Tree<KEY, T> &rbt)
+ACE_RB_Tree<KEY, T>::operator = (const ACE_RB_Tree<KEY, T> &rbt)
 {
-  // clear out the existing tree
+  // Free the comparison functor if needed.
+  if (free_functor_)
+    {
+      delete less_than_functor_;
+    }
+
+  // Make a copy of the passed tree's comparison functor.
+  less_than_functor_ = (rbt.less_than_functor_ == 0)
+                       ? 0 : rbt.less_than_functor_->clone ();
+  free_functor_ = 1;
+
+  // Clear out the existing tree.
   clear ();
 
-  // make a deep copy of the passed tree
-  RB_Tree_Iterator<KEY, T> iter(rbt);
+  // Make a deep copy of the passed tree.
+  ACE_RB_Tree_Iterator<KEY, T> iter(rbt);
   for (iter.first (); iter.is_done () == 0; iter.next ())
   {
     insert (*(iter.key ()), *(iter.item ()));
   }
 }
-  // assignment operator
+
+// Less than comparison function for keys, default
+// functor implementation returns 1 if k1 < k2, 0 otherwise.
 
 template <class KEY, class T> int
-RB_Tree<KEY, T>::lessthan (const KEY &k1, const KEY &k2)
+ACE_RB_Tree<KEY, T>::lessthan (const KEY &k1, const KEY &k2)
 {
-  return k1 < k2;
+  if (less_than_functor_ == 0)
+    {
+      ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
+                         ASYS_TEXT ("\nNull comparison functor pointer.\n")), 
+                        0);
+    }
+  else
+    {
+      return less_than_functor_->execute (k1, k2);
+    }
 }
-  // lessthan comparison function for keys.
-  // returns 1 if k1 < k2, 0 otherwise
+
+
+// Returns a pointer to the item corresponding to the
+// given key, or 0 if it cannot find the key in the tree.
 
 template <class KEY, class T> T*
-RB_Tree<KEY, T>::find (const KEY &k)
+ACE_RB_Tree<KEY, T>::find (const KEY &k)
 {
-  // find the closest matching node, if there is one
-  RB_Tree_Node<KEY, T> *current = find_node (k);
+  // Find the closest matching node, if there is one.
+  ACE_RB_Tree_Node<KEY, T> *current = find_node (k);
 
   if (current)
   {
-    // if a nearest matching node was returned
+    // If a nearest matching node was returned.
     if (this->lessthan (current->key (), k)
         || this->lessthan (k, current->key ()))
     {
-      // if the keys differ, there is no match: return 0
+      // If the keys differ, there is no match: return 0.
       return 0;
     }
     else
     {
-      // else, the keys match: return a pointer to the node's item
+      // The keys match: return a pointer to the node's item.
       return &(current->item ());
     }
   }
   else
   {
-    // else, the tree is empty: return 0
+    // The tree is empty: return 0.
     return 0;
   }
 }
-  // Returns a pointer to the item corresponding to the
-  // given key, or 0 if it cannot find the key in the tree.
+
+
+
+// Inserts a *copy* of the key and the item into the tree:
+// both the key type KEY and the item type T must have well
+// defined semantics for copy construction and < comparison.
+// This method returns a pointer to the inserted item copy,
+// or 0 if an error occurred.  NOTE: if an identical key
+// already exists in the tree, no new item is created, and
+// the returned pointer addresses the existing item
+// associated with the existing key.
 
 template <class KEY, class T>  T*
-RB_Tree<KEY, T>::insert (const KEY &k, const T &t)
+ACE_RB_Tree<KEY, T>::insert (const KEY &k, const T &t)
 {
-  // find the closest matching node, if there is one
-  RB_Tree_Node<KEY, T> *current = find_node (k);
+  // Find the closest matching node, if there is one.
+  ACE_RB_Tree_Node<KEY, T> *current = find_node (k);
   if (current)
   {
     if (this->lessthan (current->key (), k))
     {
-      // if a nearest matching node has a key less than the insertion key
+      // If a nearest matching node has a key less than the insertion key.
       if (current->right ())
       {
-        // if there is already a right subtree, complain
+        // If there is already a right subtree, complain.
         ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nright subtree already present in "
-                                      "RB_Tree<KEY, T>::insert\n")), 0);
+                                      "ACE_RB_Tree<KEY, T>::insert\n")), 0);
       }
       else
       {
-        // else, the right subtree is empty: insert new node there
-        current->right (new RB_Tree_Node<KEY, T> (k, t));
+        // The right subtree is empty: insert new node there.
+        current->right (new ACE_RB_Tree_Node<KEY, T> (k, t));
         if (current->right ())
         {
-          // if the node was successfully inserted, set its parent, rebalance the
-          // tree, color the root black, and return a pointer to the inserted item
+          // If the node was successfully inserted, set its parent, rebalance 
+          // the tree, color the root black, and return a pointer to the 
+          // inserted item.
           T *item = &(current->right ()->item ());
           current->right ()->parent (current);
           RB_rebalance (current->right ());
-          root_->color (RB_Tree_Node_Base::BLACK);
+          root_->color (ACE_RB_Tree_Node_Base::BLACK);
           return item;
         }
         else
         {
-          // else, memory allocation failed
+          // Memory allocation failed.
         ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nmemory allocation to current->right_ failed "
-                                      "in RB_Tree<KEY, T>::insert\n")), 0);
+                                      "in ACE_RB_Tree<KEY, T>::insert\n")), 0);
         }
       }
     }
     else if (this->lessthan (k, current->key ()))
     {
-      // if a nearest matching node has a key greater than the insertion key
+      // If a nearest matching node has a key greater than the insertion key.
       if (current->left ())
       {
-        // if there is already a left subtree, complain
+        // If there is already a left subtree, complain.
         ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nleft subtree already present in "
-                                      "RB_Tree<KEY, T>::insert\n")), 0);
+                                      "ACE_RB_Tree<KEY, T>::insert\n")), 0);
       }
       else
       {
-        // else, the right subtree is empty: insert new node there
-        current->left (new RB_Tree_Node<KEY, T> (k, t));
+        // The right subtree is empty: insert new node there.
+        current->left (new ACE_RB_Tree_Node<KEY, T> (k, t));
         if (current->left ())
         {
-          // if the node was successfully inserted, set its parent, rebalance the
-          // tree, color the root black, and return a pointer to the inserted item
+          // If the node was successfully inserted, set its parent, rebalance
+          // the tree, color the root black, and return a pointer to the 
+          // inserted item.
           T *item = &(current->left ()->item ());
           current->left ()->parent (current);
           RB_rebalance (current->left ());
-          root_->color (RB_Tree_Node_Base::BLACK);
+          root_->color (ACE_RB_Tree_Node_Base::BLACK);
           return item;
         }
         else
         {
-          // else, memory allocation failed
+          // Memory allocation failed.
           ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nmemory allocation to current->left_ failed in "
-                                      "RB_Tree<KEY, T>::insert\n")), 0);
+                                      "ACE_RB_Tree<KEY, T>::insert\n")), 0);
         }
       }
     }
     else
     {
-      // else, the keys match: return a pointer to the node's item
+      // The keys match: return a pointer to the node's item.
       return &(current->item ());
     }
   }
   else
   {
-    // else, the tree is empty: insert at the root and color the root black
-    root_ = new RB_Tree_Node<KEY, T> (k, t);
+    // The tree is empty: insert at the root and color the root black.
+    root_ = new ACE_RB_Tree_Node<KEY, T> (k, t);
     if (root_)
     {
-      root_->color (RB_Tree_Node_Base::BLACK);
+      root_->color (ACE_RB_Tree_Node_Base::BLACK);
       return &(root_->item ());
     }
     else
     {
       ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                          ASYS_TEXT ("\nmemory allocation to root_ failed in "
-                                    "RB_Tree<KEY, T>::insert\n")), 0);
+                                    "ACE_RB_Tree<KEY, T>::insert\n")), 0);
     }
   }
 }
-  // Inserts a *copy* of the key and the item into the tree:
-  // both the key type KEY and the item type T must have well
-  // defined semantics for copy construction and < comparison.
-  // This method returns a pointer to the inserted item copy,
-  // or 0 if an error occurred.  NOTE: if an identical key
-  // already exists in the tree, no new item is created, and
-  // the returned pointer addresses the existing item
-  // associated with the existing key.
+
+
+// Removes the item associated with the given key from the
+// tree and destroys it.  Returns 1 if it found the item
+// and successfully destroyed it, 0 if it did not find the
+// item, or -1 if an error occurred.
 
 template <class KEY, class T>  int
-RB_Tree<KEY, T>::remove (const KEY &k)
+ACE_RB_Tree<KEY, T>::remove (const KEY &k)
 {
-  // find a matching node, if there is one
-  RB_Tree_Node<KEY, T> *x, *z = find_node (k);
+  // Find a matching node, if there is one.
+  ACE_RB_Tree_Node<KEY, T> *x, *z;
+  
+  z = find_node (k);
 
   if ((z) && (! this->lessthan (z->key (), k))
       && (! this->lessthan (k, z->key ())))
   {
-    // there is a matching node: remove and destroy it
-    RB_Tree_Node<KEY, T> *y;
+    // There is a matching node: remove and destroy it.
+    ACE_RB_Tree_Node<KEY, T> *y;
     if ((z->left ()) && (z->right ()))
     {
       y = RB_tree_successor (z);
@@ -259,7 +326,10 @@ RB_Tree<KEY, T>::remove (const KEY &k)
     {
       x = y->right ();
     }
-    x->parent (y->parent ());
+    if (x)
+	{
+	  x->parent (y->parent ());
+	}
     if (y->parent ())
     {
       if (y == y->parent ()->left ())
@@ -277,11 +347,11 @@ RB_Tree<KEY, T>::remove (const KEY &k)
     }
     if (y != z)
     {
-      // copy the elements of y into z
+      // Copy the elements of y into z.
       z->key () = y->key ();
       z->item () = y->item ();
     }
-    if (y->color () == RB_Tree_Node_Base::BLACK)
+    if (y->color () == ACE_RB_Tree_Node_Base::BLACK)
     {
       RB_delete_fixup (x);
     }
@@ -293,34 +363,32 @@ RB_Tree<KEY, T>::remove (const KEY &k)
   }
   else
   {
-    // else, no matching node was found: return 0
+    // No matching node was found: return 0.
     return 0;
   }
 }
-  // removes the item associated with the given key from the
-  // tree and destroys it.  Returns 1 if it found the item
-  // and successfully destroyed it, 0 if it did not find the
-  // item, or -1 if an error occurred.
 
 
+// Method for right rotation of the tree about a given node.
+
 template <class KEY, class T>  void
-RB_Tree<KEY, T>::RB_rotate_right (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x)
 {
   if (! x)
   {
     ACE_ERROR ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                        ASYS_TEXT ("\nerror: x is a null pointer in "
-                                  "RB_Tree<KEY, T>::RB_rotate_right\n")));
+                                  "ACE_RB_Tree<KEY, T>::RB_rotate_right\n")));
   }
   else if (! (x->left()))
   {
     ACE_ERROR ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                 ASYS_TEXT ("\nerror: x->left () is a null pointer in "
-                           "RB_Tree<KEY, T>::RB_rotate_right\n")));
+                           "ACE_RB_Tree<KEY, T>::RB_rotate_right\n")));
   }
   else
   {
-    RB_Tree_Node<KEY, T> * y;
+    ACE_RB_Tree_Node<KEY, T> * y;
     y = x->left ();
     x->left (y->right ());
     if (y->right ())
@@ -347,27 +415,28 @@ RB_Tree<KEY, T>::RB_rotate_right (RB_Tree_Node<KEY, T> * x)
     x->parent (y);
   }
 }
-  // method for right rotation of the tree about a given node
 
 
+// Method for left rotation of the tree about a given node.
+
 template <class KEY, class T> void
-RB_Tree<KEY, T>::RB_rotate_left (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x)
 {
   if (! x)
   {
     ACE_ERROR ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                 ASYS_TEXT ("\nerror: x is a null pointer in "
-                           "RB_Tree<KEY, T>::RB_rotate_left\n")));
+                           "ACE_RB_Tree<KEY, T>::RB_rotate_left\n")));
   }
   else if (! (x->right()))
   {
     ACE_ERROR ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                 ASYS_TEXT ("\nerror: x->right () is a null pointer "
-                           "in RB_Tree<KEY, T>::RB_rotate_left\n")));
+                           "in ACE_RB_Tree<KEY, T>::RB_rotate_left\n")));
   }
   else
   {
-    RB_Tree_Node<KEY, T> * y;
+    ACE_RB_Tree_Node<KEY, T> * y;
     y = x->right ();
     x->right (y->left ());
     if (y->left ())
@@ -394,73 +463,75 @@ RB_Tree<KEY, T>::RB_rotate_left (RB_Tree_Node<KEY, T> * x)
     x->parent (y);
   }
 }
-  // method for left rotation of the tree about a given node
+
+
+// Method for restoring Red-Black properties after deletion.
 
 template <class KEY, class T>  void
-RB_Tree<KEY, T>::RB_delete_fixup (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x)
 {
-  while ((x) && (x->parent ()) && (x->color () == RB_Tree_Node_Base::BLACK))
+  while ((x) && (x->parent ()) && (x->color () == ACE_RB_Tree_Node_Base::BLACK))
   {
     if (x == x->parent ()->left ())
     {
-      RB_Tree_Node<KEY, T> *w = x->parent ()->right ();
-      if (w->color () == RB_Tree_Node_Base::RED)
+      ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->right ();
+      if (w->color () == ACE_RB_Tree_Node_Base::RED)
       {
-        w->color (RB_Tree_Node_Base::BLACK);
-        x->parent ()->color (RB_Tree_Node_Base::RED);
+        w->color (ACE_RB_Tree_Node_Base::BLACK);
+        x->parent ()->color (ACE_RB_Tree_Node_Base::RED);
         RB_rotate_left (x->parent ());
         w = x->parent ()->right ();
       }
-      if ((w->left ()->color () == RB_Tree_Node_Base::BLACK) &&
-          (w->right ()->color () == RB_Tree_Node_Base::BLACK))
+      if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
+          (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
       {
-        w->color (RB_Tree_Node_Base::RED);
+        w->color (ACE_RB_Tree_Node_Base::RED);
         x = x->parent ();
       }
       else
       {
-        if (w->right ()->color () == RB_Tree_Node_Base::BLACK)
+        if (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)
         {
-          w->left ()->color (RB_Tree_Node_Base::BLACK);
-          w->color (RB_Tree_Node_Base::RED);
+          w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
+          w->color (ACE_RB_Tree_Node_Base::RED);
           RB_rotate_right (w);
           w = x->parent ()->right ();
         }
         w->color (x->parent ()->color ());
-        x->parent ()->color (RB_Tree_Node_Base::BLACK);
-        w->right ()->color (RB_Tree_Node_Base::BLACK);
+        x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+        w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
         RB_rotate_left (x->parent ());
         x = root_;
       }
     }
     else
     {
-      RB_Tree_Node<KEY, T> *w = x->parent ()->left ();
-      if (w->color () == RB_Tree_Node_Base::RED)
+      ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->left ();
+      if (w->color () == ACE_RB_Tree_Node_Base::RED)
       {
-        w->color (RB_Tree_Node_Base::BLACK);
-        x->parent ()->color (RB_Tree_Node_Base::RED);
+        w->color (ACE_RB_Tree_Node_Base::BLACK);
+        x->parent ()->color (ACE_RB_Tree_Node_Base::RED);
         RB_rotate_right (x->parent ());
         w = x->parent ()->left ();
       }
-      if ((w->left ()->color () == RB_Tree_Node_Base::BLACK) &&
-          (w->right ()->color () == RB_Tree_Node_Base::BLACK))
+      if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
+          (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
       {
-        w->color (RB_Tree_Node_Base::RED);
+        w->color (ACE_RB_Tree_Node_Base::RED);
         x = x->parent ();
       }
       else
       {
-        if (w->left ()->color () == RB_Tree_Node_Base::BLACK)
+        if (w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
         {
-          w->right ()->color (RB_Tree_Node_Base::BLACK);
-          w->color (RB_Tree_Node_Base::RED);
+          w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
+          w->color (ACE_RB_Tree_Node_Base::RED);
           RB_rotate_left (w);
           w = x->parent ()->left ();
         }
         w->color (x->parent ()->color ());
-        x->parent ()->color (RB_Tree_Node_Base::BLACK);
-        w->left ()->color (RB_Tree_Node_Base::BLACK);
+        x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+        w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
         RB_rotate_right (x->parent ());
         x = root_;
       }
@@ -469,143 +540,150 @@ RB_Tree<KEY, T>::RB_delete_fixup (RB_Tree_Node<KEY, T> * x)
 
   if (x)
   {
-    x->color (RB_Tree_Node_Base::BLACK);
+    x->color (ACE_RB_Tree_Node_Base::BLACK);
   }
 }
-  // method for restoring Red-Black properties after deletion
 
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::find_node (const KEY &k)
+
+
+// Return a pointer to a matching node if there is one,
+// a pointer to the node under which to insert the item
+// if the tree is not empty and there is no such match,
+// or 0 if the tree is empty.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::find_node (const KEY &k)
 {
-  RB_Tree_Node<KEY, T> *current = root_;
+  ACE_RB_Tree_Node<KEY, T> *current = root_;
 
   while (current)
   {
-    // while there are more nodes to examine
+    // While there are more nodes to examine.
     if (this->lessthan (current->key (), k))
     {
-      // if the search key is greater than the current node's key
+      // If the search key is greater than the current node's key.
       if (current->right ())
       {
-        // if the right subtree is not empty, search to the right
+        // If the right subtree is not empty, search to the right.
         current = current->right ();
       }
       else
       {
-        // if the right subtree is empty, we're done
+        // If the right subtree is empty, we're done.
         break;
       }
     }
     else if (this->lessthan (k, current->key ()))
     {
-      // else if the search key is less than the current node's key
+      // Else if the search key is less than the current node's key.
       if (current->left ())
       {
-        // if the left subtree is not empty, search to the left
+        // If the left subtree is not empty, search to the left.
         current = current->left ();
       }
       else
       {
-        // if the left subtree is empty, we're done
+        // If the left subtree is empty, we're done.
         break;
       }
     }
     else
     {
-      // if the keys match, we're done
+      // If the keys match, we're done.
       break;
     }
   }
 
   return current;
 }
-  // returns a pointer to a matching node if there is one,
-  // a pointer to the node under which to insert the item
-  // if the tree is not empty and there is no such match,
-  // or 0 if the tree is empty.
+
+
+// Rebalance the tree after insertion of a node.
 
 template <class KEY, class T> void
-RB_Tree<KEY, T>::RB_rebalance (RB_Tree_Node<KEY, T> * x)
+ACE_RB_Tree<KEY, T>::RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x)
 {
-  RB_Tree_Node<KEY, T> *y = 0;
+  ACE_RB_Tree_Node<KEY, T> *y = 0;
 
   while ((x) && (x->parent ())
-         && (x->parent ()->color () == RB_Tree_Node_Base::RED))
+         && (x->parent ()->color () == ACE_RB_Tree_Node_Base::RED))
   {
     if (! x->parent ()->parent ())
     {
-      // if we got here, something is drastically wrong!
+      // If we got here, something is drastically wrong!
       ACE_ERROR ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                   ASYS_TEXT ("\nerror: parent's parent is null in "
-                             "RB_Tree<KEY, T>::RB_rebalance\n")));
+                             "ACE_RB_Tree<KEY, T>::RB_rebalance\n")));
       return;
     }
 
     if (x->parent () == x->parent ()->parent ()->left ())
     {
       y = x->parent ()->parent ()->right ();
-      if (y && (y->color () == RB_Tree_Node_Base::RED))
+      if (y && (y->color () == ACE_RB_Tree_Node_Base::RED))
       {
-        // handle case 1 (see CLR book, pp. 269)
-        x->parent ()->color (RB_Tree_Node_Base::BLACK);
-        y->color (RB_Tree_Node_Base::BLACK);
-        x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+        // Handle case 1 (see CLR book, pp. 269).
+        x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+        y->color (ACE_RB_Tree_Node_Base::BLACK);
+        x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
         x = x->parent ()->parent ();
       }
       else
       {
         if (x == x->parent ()->right ())
         {
-          // transform case 2 into case 3 (see CLR book, pp. 269)
+          // Transform case 2 into case 3 (see CLR book, pp. 269).
           x = x->parent ();
           RB_rotate_left (x);
         }
 
-        // handle case 3 (see CLR book, pp. 269)
-        x->parent ()->color (RB_Tree_Node_Base::BLACK);
-        x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+        // Handle case 3 (see CLR book, pp. 269).
+        x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+        x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
         RB_rotate_right (x->parent ()->parent ());
       }
     }
     else
     {
       y = x->parent ()->parent ()->left ();
-      if (y && (y->color () == RB_Tree_Node_Base::RED))
+      if (y && (y->color () == ACE_RB_Tree_Node_Base::RED))
       {
-        // handle case 1 (see CLR book, pp. 269)
-        x->parent ()->color (RB_Tree_Node_Base::BLACK);
-        y->color (RB_Tree_Node_Base::BLACK);
-        x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+        // Handle case 1 (see CLR book, pp. 269).
+        x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+        y->color (ACE_RB_Tree_Node_Base::BLACK);
+        x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
         x = x->parent ()->parent ();
       }
       else
       {
         if (x == x->parent ()->left ())
         {
-          // transform case 2 into case 3 (see CLR book, pp. 269)
+          // Transform case 2 into case 3 (see CLR book, pp. 269).
           x = x->parent ();
           RB_rotate_right (x);
         }
 
-        // handle case 3 (see CLR book, pp. 269)
-        x->parent ()->color (RB_Tree_Node_Base::BLACK);
-        x->parent ()->parent ()->color (RB_Tree_Node_Base::RED);
+        // Handle case 3 (see CLR book, pp. 269).
+        x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
+        x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
         RB_rotate_left (x->parent ()->parent ());
       }
     }
   }
 }
-  // rebalance the tree after insertion of a node
 
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_successor (RB_Tree_Node<KEY, T> *x) const
+
+// Method to find the successor node of the given node in the tree.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const
 {
   if (x->right ())
   {
     return RB_tree_minimum (x->right ());
   }
 
-  RB_Tree_Node<KEY, T> *y = x->parent ();
+  ACE_RB_Tree_Node<KEY, T> *y = x->parent ();
   while ((y) && (x == y->right ()))
   {
     x = y;
@@ -614,17 +692,19 @@ RB_Tree<KEY, T>::RB_tree_successor (RB_Tree_Node<KEY, T> *x) const
 
   return y;
 }
-  // method to find the successor node of the given node in the tree
 
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_predecessor (RB_Tree_Node<KEY, T> *x) const
+ 
+// Method to find the predecessor node of the given node in the tree.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const
 {
   if (x->left ())
   {
     return RB_tree_maximum (x->left ());
   }
 
-  RB_Tree_Node<KEY, T> *y = x->parent ();
+  ACE_RB_Tree_Node<KEY, T> *y = x->parent ();
   while ((y) && (x == y->left ()))
   {
     x = y;
@@ -633,10 +713,12 @@ RB_Tree<KEY, T>::RB_tree_predecessor (RB_Tree_Node<KEY, T> *x) const
 
   return y;
 }
-  // method to find the predecessor node of the given node in the tree
 
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_minimum (RB_Tree_Node<KEY, T> *x) const
+
+// Method to find the minimum node of the subtree rooted at the given node.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const
 {
   while ((x) && (x->left ()))
   {
@@ -645,11 +727,12 @@ RB_Tree<KEY, T>::RB_tree_minimum (RB_Tree_Node<KEY, T> *x) const
 
   return x;
 }
-  // method to find the minimum node of the subtree rooted at the given node
 
 
-template <class KEY, class T> RB_Tree_Node<KEY, T> *
-RB_Tree<KEY, T>::RB_tree_maximum (RB_Tree_Node<KEY, T> *x) const
+// Method to find the maximum node of the subtree rooted at the given node.
+
+template <class KEY, class T> ACE_RB_Tree_Node<KEY, T> *
+ACE_RB_Tree<KEY, T>::RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const
 {
   while ((x) && (x->right ()))
   {
@@ -658,28 +741,32 @@ RB_Tree<KEY, T>::RB_tree_maximum (RB_Tree_Node<KEY, T> *x) const
 
   return x;
 }
-  // method to find the maximum node of the subtree rooted at the given node
 
 
 
-/////////////////////////////////////////////
-// template class RB_Tree_Iterator<KEY, T> //
-/////////////////////////////////////////////
+
+/////////////////////////////////////////////////
+// template class ACE_RB_Tree_Iterator<KEY, T> //
+/////////////////////////////////////////////////
+
+
+// Constructor.
 
 template <class KEY, class T>
-RB_Tree_Iterator<KEY, T>::RB_Tree_Iterator (const RB_Tree<KEY, T> &tree)
+ACE_RB_Tree_Iterator<KEY, T>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T> &tree)
   : tree_ (tree), node_ (0)
 {
-  // position the iterator at the first node in the tree
+  // Position the iterator at the first node in the tree.
   first ();
 }
-  // constructor
+
+
+// Destructor.
 
 template <class KEY, class T>
-RB_Tree_Iterator<KEY, T>::~RB_Tree_Iterator ()
+ACE_RB_Tree_Iterator<KEY, T>::~ACE_RB_Tree_Iterator ()
 {
 }
-  // destructor
 
 
 #endif /* !defined (ACE_RB_TREE_C) */