interim checkin of RB_Tree interface adaptations

4 files changed, 484 insertions, 185 deletions

diff --git a/ChangeLog-99b b/ChangeLog-99b
index 77cc16b5ae2..ae6621fb339 100644
--- a/ChangeLog-99b
+++ b/ChangeLog-99b
@@ -1,3 +1,10 @@
+Tue May 04 16:24:00 1999  Chris Gill  <cdgill@cs.wustl.edu>
+
+        * ace/RB_Tree.{cpp, h, i}: Added deprecation comments to methods that
+          are going to be replaced by the new Hash_Map_Manager compliant
+	  interface.  Factored out iterator base class, added reverse iterator.
+	  Interim checkin since it all compiles and RB_Tree_Test runs clean.
+	
 Tue May 04 15:56:41 1999  Steve Huston  <shuston@riverace.com>
 
         * ace/ACE.cpp: Re-enabled DllMain (see Mon May 3 entry from Chris
diff --git a/ace/RB_Tree.cpp b/ace/RB_Tree.cpp
index 2c2196366e3..4a3417e5e4d 100644
--- a/ace/RB_Tree.cpp
+++ b/ace/RB_Tree.cpp
@@ -18,14 +18,14 @@
 ACE_RCSID(ace, RB_Tree, "$Id$")
 
 /////////////////////////////////////////////
-// template class ACE_RB_Tree_Node<KEY, T> //
+// template class ACE_RB_Tree_Node<EXT_ID, INT_ID> //
 /////////////////////////////////////////////
 
 
 // Constructor.
 
-template <class KEY, class T>
-ACE_RB_Tree_Node<KEY, T>::ACE_RB_Tree_Node (const KEY &k, const T &t)
+template <class EXT_ID, class INT_ID>
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t)
   : k_ (k)
   , t_ (t)
   , color_ (RED)
@@ -38,8 +38,8 @@ ACE_RB_Tree_Node<KEY, T>::ACE_RB_Tree_Node (const KEY &k, const T &t)
 
 // Destructor.
 
-template <class KEY, class T>
-ACE_RB_Tree_Node<KEY, T>::~ACE_RB_Tree_Node ()
+template <class EXT_ID, class INT_ID>
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node ()
 {
   // Delete left sub-tree.
   delete left_;
@@ -51,26 +51,27 @@ ACE_RB_Tree_Node<KEY, T>::~ACE_RB_Tree_Node ()
 
 
 ////////////////////////////////////////
-// template class ACE_RB_Tree<KEY, T> //
+// template class ACE_RB_Tree<EXT_ID, INT_ID> //
 ////////////////////////////////////////
 
 // Constructor.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree ()
-  : root_ (0)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree ()
+  : root_ (0), 
+    current_size_ (0)
 {
 }
 
 
 // Copy constructor.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt)
-  : root_ (0)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)
+  : root_ (0), current_size_ (0)
 {
   // Make a deep copy of the passed tree.
-  ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> iter(rbt);
+  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
   for (iter.first (); iter.is_done () == 0; iter.next ())
   {
     insert (*(iter.key ()), *(iter.item ()));
@@ -80,8 +81,8 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (const ACE_RB_Tree<KEY,
 
 // Destructor.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree ()
 {
   // Clear away all nodes in the tree.
   clear ();
@@ -90,14 +91,14 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree ()
 
 // Assignment operator.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::operator = (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator = (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)
 {
   // Clear out the existing tree.
   clear ();
 
   // Make a deep copy of the passed tree.
-  ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> iter(rbt);
+  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
   for (iter.first (); iter.is_done () == 0; iter.next ())
   {
     insert (*(iter.key ()), *(iter.item ()));
@@ -107,8 +108,8 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::operator = (const ACE_RB_Tree<KEY,
 // Less than comparison function for keys, default
 // functor implementation returns 1 if k1 < k2, 0 otherwise.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> int
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::lessthan (const KEY &k1, const KEY &k2)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> int
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan (const EXT_ID &k1, const EXT_ID &k2)
 {
       return this->compare_keys_ (k1, k2);
 }
@@ -117,11 +118,11 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::lessthan (const KEY &k1, const KEY
 // 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, class COMPARE_KEYS, class ACE_LOCK> T*
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::find (const KEY &k)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> INT_ID*
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &k)
 {
   // Find the closest matching node, if there is one.
-  ACE_RB_Tree_Node<KEY, T> *current = find_node (k);
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k);
 
   if (current)
   {
@@ -148,7 +149,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::find (const KEY &k)
 
 
 // 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
+// both the key type EXT_ID and the item type INT_ID 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
@@ -156,11 +157,11 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::find (const KEY &k)
 // the returned pointer addresses the existing item
 // associated with the existing key.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>  T*
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  INT_ID*
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert (const EXT_ID &k, const INT_ID &t)
 {
   // Find the closest matching node, if there is one.
-  ACE_RB_Tree_Node<KEY, T> *current = find_node (k);
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k);
   if (current)
   {
     if (this->lessthan (current->key (), k))
@@ -171,21 +172,22 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t)
         // If there is already a right subtree, complain.
         ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nright subtree already present in "
-                                      "ACE_RB_Tree<KEY, T>::insert\n")), 0);
+                                      "ACE_RB_Tree<EXT_ID, INT_ID>::insert\n")), 0);
       }
       else
       {
         // The right subtree is empty: insert new node there.
-        current->right (new ACE_RB_Tree_Node<KEY, T> (k, t));
+        current->right (new ACE_RB_Tree_Node<EXT_ID, INT_ID> (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.
-          T *item = &(current->right ()->item ());
+          INT_ID *item = &(current->right ()->item ());
           current->right ()->parent (current);
           RB_rebalance (current->right ());
           root_->color (ACE_RB_Tree_Node_Base::BLACK);
+          ++current_size_;
           return item;
         }
         else
@@ -193,7 +195,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t)
           // Memory allocation failed.
         ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nmemory allocation to current->right_ failed "
-                                      "in ACE_RB_Tree<KEY, T>::insert\n")), 0);
+                                      "in ACE_RB_Tree<EXT_ID, INT_ID>::insert\n")), 0);
         }
       }
     }
@@ -205,21 +207,22 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t)
         // If there is already a left subtree, complain.
         ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nleft subtree already present in "
-                                      "ACE_RB_Tree<KEY, T>::insert\n")), 0);
+                                      "ACE_RB_Tree<EXT_ID, INT_ID>::insert\n")), 0);
       }
       else
       {
         // The right subtree is empty: insert new node there.
-        current->left (new ACE_RB_Tree_Node<KEY, T> (k, t));
+        current->left (new ACE_RB_Tree_Node<EXT_ID, INT_ID> (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.
-          T *item = &(current->left ()->item ());
+          INT_ID *item = &(current->left ()->item ());
           current->left ()->parent (current);
           RB_rebalance (current->left ());
           root_->color (ACE_RB_Tree_Node_Base::BLACK);
+          ++current_size_;
           return item;
         }
         else
@@ -227,7 +230,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t)
           // Memory allocation failed.
           ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                            ASYS_TEXT ("\nmemory allocation to current->left_ failed in "
-                                      "ACE_RB_Tree<KEY, T>::insert\n")), 0);
+                                      "ACE_RB_Tree<EXT_ID, INT_ID>::insert\n")), 0);
         }
       }
     }
@@ -240,17 +243,18 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t)
   else
   {
     // The tree is empty: insert at the root and color the root black.
-    root_ = new ACE_RB_Tree_Node<KEY, T> (k, t);
+    root_ = new ACE_RB_Tree_Node<EXT_ID, INT_ID> (k, t);
     if (root_)
     {
       root_->color (ACE_RB_Tree_Node_Base::BLACK);
+      ++current_size_;
       return &(root_->item ());
     }
     else
     {
       ACE_ERROR_RETURN ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                          ASYS_TEXT ("\nmemory allocation to root_ failed in "
-                                    "ACE_RB_Tree<KEY, T>::insert\n")), 0);
+                                    "ACE_RB_Tree<EXT_ID, INT_ID>::insert\n")), 0);
     }
   }
 }
@@ -261,11 +265,11 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t)
 // and successfully destroyed it, 0 if it did not find the
 // item, or -1 if an error occurred.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>  int
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::remove (const KEY &k)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  int
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove (const EXT_ID &k)
 {
   // Find a matching node, if there is one.
-  ACE_RB_Tree_Node<KEY, T> *x, *z;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *x, *z;
 
   z = find_node (k);
 
@@ -273,7 +277,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::remove (const KEY &k)
       && (! this->lessthan (k, z->key ())))
   {
     // There is a matching node: remove and destroy it.
-    ACE_RB_Tree_Node<KEY, T> *y;
+    ACE_RB_Tree_Node<EXT_ID, INT_ID> *y;
     if ((z->left ()) && (z->right ()))
     {
       y = RB_tree_successor (z);
@@ -324,6 +328,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::remove (const KEY &k)
     y->right (0);
     y->left (0);
     delete y;
+    --current_size_;
     return 1;
   }
   else
@@ -336,24 +341,24 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::remove (const KEY &k)
 
 // Method for right rotation of the tree about a given node.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>  void
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  void
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
 {
   if (! x)
   {
     ACE_ERROR ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                        ASYS_TEXT ("\nerror: x is a null pointer in "
-                                  "ACE_RB_Tree<KEY, T>::RB_rotate_right\n")));
+                                  "ACE_RB_Tree<EXT_ID, INT_ID>::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 "
-                           "ACE_RB_Tree<KEY, T>::RB_rotate_right\n")));
+                           "ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
   }
   else
   {
-    ACE_RB_Tree_Node<KEY, T> * y;
+    ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
     y = x->left ();
     x->left (y->right ());
     if (y->right ())
@@ -384,24 +389,24 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tree_Node<K
 
 // Method for left rotation of the tree about a given node.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
 {
   if (! x)
   {
     ACE_ERROR ((LM_ERROR,  ASYS_TEXT ("%p\n"),
                 ASYS_TEXT ("\nerror: x is a null pointer in "
-                           "ACE_RB_Tree<KEY, T>::RB_rotate_left\n")));
+                           "ACE_RB_Tree<EXT_ID, INT_ID>::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 ACE_RB_Tree<KEY, T>::RB_rotate_left\n")));
+                           "in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
   }
   else
   {
-    ACE_RB_Tree_Node<KEY, T> * y;
+    ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
     y = x->right ();
     x->right (y->left ());
     if (y->left ())
@@ -432,8 +437,8 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<KE
 
 // Method for restoring Red-Black properties after deletion.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>  void
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>  void
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
 {
   while (x && 
          x->parent () && 
@@ -441,7 +446,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<K
   {
     if (x == x->parent ()->left ())
     {
-      ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->right ();
+      ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = x->parent ()->right ();
       if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
       {
         w->color (ACE_RB_Tree_Node_Base::BLACK);
@@ -480,7 +485,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<K
     }
     else
     {
-      ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->left ();
+      ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = x->parent ()->left ();
       if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
       {
         w->color (ACE_RB_Tree_Node_Base::BLACK);
@@ -530,10 +535,10 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<K
 // if the tree is not empty and there is no such match,
 // or 0 if the tree is empty.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::find_node (const KEY &k)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node (const EXT_ID &k)
 {
-  ACE_RB_Tree_Node<KEY, T> *current = root_;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = root_;
 
   while (current)
   {
@@ -579,10 +584,10 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::find_node (const KEY &k)
 
 // Rebalance the tree after insertion of a node.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x)
 {
-  ACE_RB_Tree_Node<KEY, T> *y = 0;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = 0;
 
   while (x && 
          x->parent () &&
@@ -593,7 +598,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<KEY,
       // 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 "
-                             "ACE_RB_Tree<KEY, T>::RB_rebalance\n")));
+                             "ACE_RB_Tree<EXT_ID, INT_ID>::RB_rebalance\n")));
       return;
     }
 
@@ -655,15 +660,15 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<KEY,
 
 // Method to find the successor node of the given node in the tree.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 {
   if (x->right ())
   {
     return RB_tree_minimum (x->right ());
   }
 
-  ACE_RB_Tree_Node<KEY, T> *y = x->parent ();
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
   while ((y) && (x == y->right ()))
   {
     x = y;
@@ -676,15 +681,15 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor (ACE_RB_Tree_Node
 
 // Method to find the predecessor node of the given node in the tree.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 {
   if (x->left ())
   {
     return RB_tree_maximum (x->left ());
   }
 
-  ACE_RB_Tree_Node<KEY, T> *y = x->parent ();
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
   while ((y) && (x == y->left ()))
   {
     x = y;
@@ -697,8 +702,8 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor (ACE_RB_Tree_No
 
 // Method to find the minimum node of the subtree rooted at the given node.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 {
   while ((x) && (x->left ()))
   {
@@ -711,8 +716,8 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum (ACE_RB_Tree_Node<K
 
 // Method to find the maximum node of the subtree rooted at the given node.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const
 {
   while ((x) && (x->right ()))
   {
@@ -723,28 +728,80 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum (ACE_RB_Tree_Node<K
 }
 
 
+///////////////////////////////////////////////////////////////////////
+// template class                                                    //
+// ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
+///////////////////////////////////////////////////////////////////////
 
 
-//////////////////////////////////////////////////////////
-// template class ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> //
-//////////////////////////////////////////////////////////
+// Constructor.
+
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,               int set_first)
+  : tree_ (tree), node_ (0)
+{
+  // Position the iterator at the first (or last) node in the tree.
+  if (set_first)
+    {
+      node_ = tree_.RB_tree_minimum (tree_.root_);
+    }
+  else
+    {
+      node_ = tree_.RB_tree_maximum (tree_.root_);
+    }
+}
+
+
+// Destructor.
+
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base ()
+{
+}
+
+
+//////////////////////////////////////////////////////////////////
+// template class                                               //
+// ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
+//////////////////////////////////////////////////////////////////
 
 
 // Constructor.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &tree)
-  : tree_ (tree), node_ (0)
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
+     int set_first)
+  : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_first)
+{
+}
+
+
+// Destructor.
+
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator ()
+{
+}
+
+//////////////////////////////////////////////////////////////////////////
+// template class                                                       //
+// ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
+//////////////////////////////////////////////////////////////////////////
+
+
+// Constructor.
+
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, int set_last)
+  : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_last ? 0 : 1)
 {
-  // Position the iterator at the first node in the tree.
-  first ();
 }
 
 
 // Destructor.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator ()
 {
 }
 
diff --git a/ace/RB_Tree.h b/ace/RB_Tree.h
index a58a07d540f..e09a21fc4c3 100644
--- a/ace/RB_Tree.h
+++ b/ace/RB_Tree.h
@@ -24,31 +24,47 @@
 # pragma once
 #endif /* ACE_LACKS_PRAGMA_ONCE */
 
+// Forward decl.
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+class ACE_RB_Tree_Iterator_Base;
+
+// Forward decl.
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+class ACE_RB_Tree_Iterator;
+
+// Forward decl.
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+class ACE_RB_Tree_Reverse_Iterator;
+
+// Forward decl.
+class ACE_Allocator;
+
 class ACE_RB_Tree_Node_Base
 {
 public:
   enum RB_Tree_Node_Color {RED, BLACK};
 };
 
-template <class KEY, class T>
+template <class EXT_ID, class INT_ID>
 class ACE_RB_Tree_Node : public ACE_RB_Tree_Node_Base
 {
   // = TITLE
-  //   Implements a node in a Red-Black Tree ADT.
+  //   Implements a node in a Red-Black Tree ADT.  
+  //
 public:
 
   // Initialization and termination methods.
 
-  ACE_RB_Tree_Node (const KEY &k, const T &t);
+  ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t);
   // Constructor.
 
   ~ACE_RB_Tree_Node (void);
   // Destructor.
 
-  KEY &key (void);
+  EXT_ID &key (void);
   // Key accessor.
 
-  T &item (void);
+  INT_ID &item (void);
   // Item accessor.
 
   void color (RB_Tree_Node_Color c);
@@ -57,46 +73,46 @@ public:
   RB_Tree_Node_Color color (void);
   // Get color of the node.
 
-  ACE_RB_Tree_Node<KEY, T> *parent (void);
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent (void);
   // Accessor for node's parent pointer.
 
-  void parent (ACE_RB_Tree_Node<KEY, T> * p);
+  void parent (ACE_RB_Tree_Node<EXT_ID, INT_ID> * p);
   // Mutator for node's parent pointer.
 
-  ACE_RB_Tree_Node<KEY, T> *left (void);
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *left (void);
   // Accessor for node's left child pointer.
 
-  void left (ACE_RB_Tree_Node<KEY, T> *l);
+  void left (ACE_RB_Tree_Node<EXT_ID, INT_ID> *l);
   // Mutator for node's left child pointer.
 
-  ACE_RB_Tree_Node<KEY, T> *right (void);
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *right (void);
   // Accessor for node's right child pointer.
 
-  void right (ACE_RB_Tree_Node<KEY, T> * r);
+  void right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * r);
   // Mutator for node's right child pointer
 
 private:
 
-  KEY k_;
+  EXT_ID k_;
   // The key.
 
-  T t_;
+  INT_ID t_;
   // The item.
 
   RB_Tree_Node_Color color_;
   // Color of the node.
 
-  ACE_RB_Tree_Node<KEY, T> *parent_;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent_;
   // Pointer to node's parent.
 
-  ACE_RB_Tree_Node<KEY, T> *left_;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *left_;
   // Pointer to node's left child.
 
-  ACE_RB_Tree_Node<KEY, T> *right_;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *right_;
   // Pointer to node's right child.
 };
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 class ACE_RB_Tree
 {
   // = TITLE
@@ -105,47 +121,76 @@ class ACE_RB_Tree
   //   1990, MIT, chapter 14.
   //
   // = Description
-  //   If an ACE allocator is passed to the RB_Tree constructor, it is used 
-  //   for all dynamic allocations done by the tree.
+  //   A number of Changes have been made to this class template 
+  //   in order to conform to the ACE_Hash_Map_Manager_Ex 
+  //   interface.  All previously supported public methods are 
+  //   still part of this class. However, these are marked as
+  //   DEPRECATED and will be removed from this class in
+  //   a future version of ACE.  Please migrate your code
+  //   to the appropriate public methods indicated in the
+  //   method deprecation comments.
+
 public:
+
+  typedef EXT_ID KEY;
+  typedef INT_ID VALUE;
+  typedef ACE_RB_Tree_Node<EXT_ID, INT_ID> ENTRY;
+
+  // = ACE-style iterator typedefs.
+  typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ITERATOR;
+  typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> REVERSE_ITERATOR;
+
+  // = STL-style iterator typedefs.
+  typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iterator;
+  typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> reverse_iterator;
+
   // = Initialization and termination methods.
   ACE_RB_Tree ();
   // Constructor.
 
-  ACE_RB_Tree (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt);
+  ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt);
   // Copy constructor.
 
   virtual ~ACE_RB_Tree (void);
   // Destructor.
 
-  void operator= (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt);
+  size_t current_size (void);
+  // Returns the current number of nodes in the tree.
+
+  void operator= (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt);
   // Assignment operator.
 
-  virtual int lessthan (const KEY &k1, const KEY &k2);
+  virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2);
   // Less than comparison function for keys, using comparison functor.
 
-  T* find (const KEY &k);
+  // = DEPRECATED methods.  Please migrate your code to use the new methods instead
+
+  INT_ID* find (const EXT_ID &k);
   // Returns a pointer to the item corresponding to the
   // given key, or 0 if it cannot find the key in the tree.
+  // DEPRECATED
 
-  T* insert (const KEY &k, const T &t);
+  INT_ID* insert (const EXT_ID &k, const INT_ID &t);
   // 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
+  // key type EXT_ID and the item type INT_ID must have well defined semantics
   // for copy construction.  The default implementation also requires that
-  // the key type support welll defined < semantics.  This method returns a
+  // the key type support well defined < semantics.  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.
+  // DEPRECATED
 
-  int remove (const KEY &k);
+  int remove (const EXT_ID &k);
   // 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.
+  // DEPRECATED
 
   void clear (void);
   // Destroys all nodes and sets the root pointer null.
+  // DEPRECATED
 
   // These could all be made private methods by making the corresponding
   // class template instantiations friends, but there are some problems
@@ -153,104 +198,273 @@ public:
 
 // private:
 
-  void RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x);
+  void RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
   // Method for right rotation of the tree about a given node.
 
-  void RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x);
+  void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
   // Method for left rotation of the tree about a given node.
 
-  void RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x);
+  void RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
   // Method for restoring Red-Black properties after deletion.
 
-  ACE_RB_Tree_Node<KEY, T> * 
-    RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> * 
+    RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
   // Method to find the successor node of the given node in the tree.
 
-  ACE_RB_Tree_Node<KEY, T> * 
-    RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> * 
+    RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
   // Method to find the predecessor node of the given node in the
   // tree.
 
-  ACE_RB_Tree_Node<KEY, T> * 
-    RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> * 
+    RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
   // Method to find the minimum node of the subtree rooted at the
   // given node.
 
-  ACE_RB_Tree_Node<KEY, T> * 
-    RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> * 
+    RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
   // Method to find the maximum node of the subtree rooted at the
   // given node.
 
-  ACE_RB_Tree_Node<KEY, T> * find_node (const KEY &k);
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> * find_node (const EXT_ID &k);
   // 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.
 
-  void RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x);
+  void RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
   // Rebalance the tree after insertion of a node.
 
   // Private members.
 
-  ACE_RB_Tree_Node<KEY, T> *root_;
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> *root_;
   // The root of the tree.
 
   COMPARE_KEYS compare_keys_;
   // Comparison functor for comparing nodes in the tree.
 
+  size_t current_size_;
+  // The current number of nodes in the tree.
 };
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
-class ACE_RB_Tree_Iterator
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+class ACE_RB_Tree_Iterator_Base
+{
+  // = TITLE
+  //   Implements a common base class for iterators for a Red-Black Tree ADT.
+public:
+
+  // = Initialization and termination methods.
+
+  ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
+                             int set_first);
+  // Constructor.  Takes an ACE_RB_Tree over which to iterate, and
+  // an integer indicating (if non-zero) to position the iterator
+  // at the first element in the tree (if this integer is 0, the
+  // iterator is positioned at the last element in the tree).
+
+  ~ACE_RB_Tree_Iterator_Base (void);
+  // Destructor.
+
+  // = Iteration methods.
+
+  int next (ACE_RB_Tree_Node<EXT_ID, INT_ID> *&next_entry) const;
+  // Passes back the <entry> under the iterator.  Returns 0 if
+  // the iteration has completed, otherwise 1.
+
+  int done (void) const;
+  // Returns 1 when the iteration has completed, otherwise 0.
+
+  ACE_RB_Tree_Node<EXT_ID, INT_ID> & operator* (void) const;
+  // STL-like iterator dereference operator: returns a reference
+  // to the node underneath the iterator.
+
+  ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree (void);
+  // Returns a reference to the tree over which we're iterating.
+
+  int operator== (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &) const;
+  // Comparison operator: returns 1 if both iterators point to the same position, otherwise 0.
+
+  int operator!= (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &) const;
+  // Comparison operator: returns 1 if the iterators point to different positions, otherwise 0.
+
+  ACE_ALLOC_HOOK_DECLARE;
+  // Declare the dynamic allocation hooks.
+
+protected:
+
+  // = protected methods
+
+  int forward_i (void);
+  // Move forward by one element in the tree.  Returns 0 when
+  // there are no more elements in the tree, otherwise 1.
+
+  int reverse_i (void);
+  // Move forward by one element in the tree.  Returns 0 when
+  // there are no more elements in the tree, otherwise 1.
+
+  void dump_i (void) const;
+  // Dump the state of an object.
+
+  // = Protected members.
+
+  const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree_;
+  // Reference to the ACE_RB_Tree over which we're iterating.
+
+  ACE_RB_Tree_Node <EXT_ID, INT_ID> *node_;
+  // Pointer to the node currently under the iterator.
+
+private:
+
+  // = Declare private and do not define.
+
+  // Explicitly prevent assignment and copy construction of iterators.
+  ACE_UNIMPLEMENTED_FUNC (
+    ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &))
+  ACE_UNIMPLEMENTED_FUNC (
+    void operator = (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &))
+
+};
+
+
+
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+class ACE_RB_Tree_Iterator :
+  public ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
 {
   // = TITLE
   //   Implements an iterator for a Red-Black Tree ADT.
 public:
   // = Initialization and termination methods.
-  ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &tree);
-  // Constructor.
+  ACE_RB_Tree_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
+                        int set_first = 1);
+  // Constructor.  Takes an ACE_RB_Tree over which to iterate, and
+  // an integer indicating (if non-zero) to position the iterator
+  // at the first element in the tree (if this integer is 0, the
+  // iterator is positioned at the last element in the tree).
 
   ~ACE_RB_Tree_Iterator (void);
   // Destructor.
 
-  KEY *key (void);
+  // = ACE-style iteration methods.
+
+  int advance (void);
+  // Move forward by one element in the tree.  Returns
+  // 0 when all elements have been seen, else 1.
+
+  void dump (void) const;
+  // Dump the state of an object.
+
+  // = STL-style iteration methods.
+
+  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator++ (void);
+  // Prefix advance.
+
+  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator++ (int);
+  // Postfix advance.
+
+  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator-- (void);
+  // Prefix reverse.
+
+  ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator-- (int);
+  // Postfix reverse.
+
+  ACE_ALLOC_HOOK_DECLARE;
+  // Declare the dynamic allocation hooks.
+
+  // = DEPRECATED methods.  Please migrate your code to use the new methods instead
+
+  EXT_ID *key (void);
   // Accessor for key of node under iterator (if any).
+  // DEPRECATED
 
-  T *item (void);
+  INT_ID *item (void);
   // Accessor for item of node under iterator (if any).
+  // DEPRECATED
 
   int first (void);
-  // Move to the first item in the tree.
+  // Move to the first item in the iteration (and in the tree).
+  // DEPRECATED
 
   int last (void);
-  // Move to the last item in the tree.
+  // Move to the last item in the iteration (and in the tree).
+  // DEPRECATED
 
   int next (void);
-  // Move to the next item in the tree.
+  // Move to the next item in the iteration (and in the tree).
+  // DEPRECATED
 
   int previous (void);
-  // Move to the previous item in the tree.
+  // Move to the previous item in the iteration (and in the tree).
+  // DEPRECATED
 
   int is_done (void);
   // Returns 0 if the iterator is positioned over a valid ACE_RB_Tree
   // node, returns 1 if not.
+  // DEPRECATED: use the base class done () method instead.
 
 private:
   // = Declare private and do not define.
 
   // Explicitly prevent assignment and copy construction of iterators.
   ACE_UNIMPLEMENTED_FUNC (
-    ACE_RB_Tree_Iterator (const ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> &))
+    ACE_RB_Tree_Iterator (const ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &))
   ACE_UNIMPLEMENTED_FUNC (
-    void operator = (const ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> &))
+    void operator = (const ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &))
 
-  // Private members.
+};
 
-  const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &tree_;
-  // Reference to the ACE_RB_Tree over which we're iterating.
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+class ACE_RB_Tree_Reverse_Iterator : 
+  public ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
+{
+  // = TITLE
+  //   Implements a reverse iterator for a Red-Black Tree ADT.
+public:
+  // = Initialization and termination methods.
+  ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
+                                int set_last = 1);
+  // Constructor.  Takes an ACE_RB_Tree over which to iterate, and
+  // an integer indicating (if non-zero) to position the iterator
+  // at the last element in the tree (if this integer is 0, the
+  // iterator is positioned at the first element in the tree).
+
+  ~ACE_RB_Tree_Reverse_Iterator (void);
+  // Destructor.
 
-  ACE_RB_Tree_Node <KEY, T> *node_;
-  // Pointer to the node currently under the iterator.
+  // = ACE-style iteration methods.
+
+  int advance (void);
+  // Move forward by one element in the tree.  Returns
+  // 0 when all elements have been seen, else 1.
+
+  void dump (void) const;
+  // Dump the state of an object.
+
+  // = STL-style iteration methods.
+
+  ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator++ (void);
+  // Prefix advance.
 
+  ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator++ (int);
+  // Postfix advance.
+
+  ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator-- (void);
+  // Prefix reverse.
+
+  ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &operator-- (int);
+  // Postfix reverse.
+
+  ACE_ALLOC_HOOK_DECLARE;
+  // Declare the dynamic allocation hooks.
+
+private:
+  // = Declare private and do not define.
+
+  // Explicitly prevent assignment and copy construction of iterators.
+  ACE_UNIMPLEMENTED_FUNC (
+    ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &))
+  ACE_UNIMPLEMENTED_FUNC (
+    void operator = (const ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &))
 };
 
 #if defined (__ACE_INLINE__)
diff --git a/ace/RB_Tree.i b/ace/RB_Tree.i
index 3ddfee0f079..d085ec78e9e 100644
--- a/ace/RB_Tree.i
+++ b/ace/RB_Tree.i
@@ -1,14 +1,14 @@
 /* -*- C++ -*- */
 // $Id$
 
-/////////////////////////////////////////////
-// template class ACE_RB_Tree_Node<KEY, T> //
-/////////////////////////////////////////////
+/////////////////////////////////////////////////////
+// template class ACE_RB_Tree_Node<EXT_ID, INT_ID> //
+/////////////////////////////////////////////////////
 
 // Key accessor.
 
-template <class KEY, class T> ACE_INLINE KEY &
-ACE_RB_Tree_Node<KEY, T>::key ()
+template <class EXT_ID, class INT_ID> ACE_INLINE EXT_ID &
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::key ()
 {
   return k_;
 }
@@ -16,8 +16,8 @@ ACE_RB_Tree_Node<KEY, T>::key ()
 
 // Item accessor.
 
-template <class KEY, class T> ACE_INLINE T &
-ACE_RB_Tree_Node<KEY, T>::item ()
+template <class EXT_ID, class INT_ID> ACE_INLINE INT_ID &
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::item ()
 {
   return t_;
 }
@@ -25,8 +25,8 @@ ACE_RB_Tree_Node<KEY, T>::item ()
 
 // Set color of the node.
 
-template <class KEY, class T> ACE_INLINE void
-ACE_RB_Tree_Node<KEY, T>::color (ACE_RB_Tree_Node_Base::RB_Tree_Node_Color c)
+template <class EXT_ID, class INT_ID> ACE_INLINE void
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::color (ACE_RB_Tree_Node_Base::RB_Tree_Node_Color c)
 {
   color_ = c;
 }
@@ -34,9 +34,9 @@ ACE_RB_Tree_Node<KEY, T>::color (ACE_RB_Tree_Node_Base::RB_Tree_Node_Color c)
 
 // Get color of the node.
 
-template <class KEY, class T>
+template <class EXT_ID, class INT_ID>
 ACE_INLINE ACE_RB_Tree_Node_Base::RB_Tree_Node_Color
-ACE_RB_Tree_Node<KEY, T>::color ()
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::color ()
 {
   return color_;
 }
@@ -44,8 +44,9 @@ ACE_RB_Tree_Node<KEY, T>::color ()
 
 // Accessor for node's parent pointer.
 
-template <class KEY, class T> ACE_INLINE ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree_Node<KEY, T>::parent ()
+template <class EXT_ID, class INT_ID> 
+ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent ()
 {
   return parent_;
 }
@@ -53,8 +54,8 @@ ACE_RB_Tree_Node<KEY, T>::parent ()
 
 // Mutator for node's parent pointer.
 
-template <class KEY, class T> ACE_INLINE void
-ACE_RB_Tree_Node<KEY, T>::parent (ACE_RB_Tree_Node<KEY, T> * p)
+template <class EXT_ID, class INT_ID> ACE_INLINE void
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::parent (ACE_RB_Tree_Node<EXT_ID, INT_ID> * p)
 {
   parent_ = p;
 }
@@ -63,8 +64,9 @@ ACE_RB_Tree_Node<KEY, T>::parent (ACE_RB_Tree_Node<KEY, T> * p)
 
 // Accessor for node's left child pointer.
 
-template <class KEY, class T> ACE_INLINE ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree_Node<KEY, T>::left ()
+template <class EXT_ID, class INT_ID> 
+ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::left ()
 {
   return left_;
 }
@@ -72,8 +74,8 @@ ACE_RB_Tree_Node<KEY, T>::left ()
 
 // Mutator for node's left child pointer.
 
-template <class KEY, class T> ACE_INLINE void
-ACE_RB_Tree_Node<KEY, T>::left (ACE_RB_Tree_Node<KEY, T> * l)
+template <class EXT_ID, class INT_ID> ACE_INLINE void
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * l)
 {
   left_ = l;
 }
@@ -81,8 +83,9 @@ ACE_RB_Tree_Node<KEY, T>::left (ACE_RB_Tree_Node<KEY, T> * l)
 
 // Accessor for node's right child pointer.
 
-template <class KEY, class T> ACE_INLINE ACE_RB_Tree_Node<KEY, T> *
-ACE_RB_Tree_Node<KEY, T>::right ()
+template <class EXT_ID, class INT_ID> 
+ACE_INLINE ACE_RB_Tree_Node<EXT_ID, INT_ID> *
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::right ()
 {
   return right_;
 }
@@ -90,39 +93,51 @@ ACE_RB_Tree_Node<KEY, T>::right ()
 
 // Mutator for node's right child pointer.
 
-template <class KEY, class T> ACE_INLINE void
-ACE_RB_Tree_Node<KEY, T>::right (ACE_RB_Tree_Node<KEY, T> * r)
+template <class EXT_ID, class INT_ID> ACE_INLINE void
+ACE_RB_Tree_Node<EXT_ID, INT_ID>::right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * r)
 {
   right_ = r;
 }
 
 
 
-////////////////////////////////////////////////////////////////
-// template class ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> //
-////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+// template class ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
+////////////////////////////////////////////////////////////////////////
 
 
 // Destroys all nodes and sets the root pointer null.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE void
-ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::clear ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 
+ACE_INLINE void
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear ()
 {
   delete root_;
   root_ = 0;
+  current_size_ = 0;
 }
 
+// Returns the current number of nodes in the tree.
+
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_INLINE size_t 
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size ()
+{
+  return current_size_;
+}
 
 
-//////////////////////////////////////////////////////////
-// template class ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> //
-//////////////////////////////////////////////////////////
 
+//////////////////////////////////////////////////////////////////
+// template class                                               //
+// ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> //
+//////////////////////////////////////////////////////////////////
 
 // Accessor for key of node under iterator (if any).
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE KEY *
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::key ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_INLINE EXT_ID *
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::key ()
 {
   return node_ ? (&(node_->key ())) : 0;
 }
@@ -130,8 +145,9 @@ ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::key ()
 
 // Accessor for item of node under iterator (if any).
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE T *
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::item ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 
+ACE_INLINE INT_ID *
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::item ()
 {
   return node_ ? (&(node_->item ())) : 0;
 }
@@ -139,8 +155,9 @@ ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::item ()
 
 // Move to the first item in the tree.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE int
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::first ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_INLINE int
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::first ()
 {
   node_ = tree_.RB_tree_minimum (tree_.root_);
   return node_ ? 1 : 0;
@@ -149,8 +166,9 @@ ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::first ()
 
 // Move to the last item in the tree.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE int
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::last ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_INLINE int
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::last ()
 {
   node_ = tree_.RB_tree_maximum (tree_.root_);
   return node_ ? 1 : 0;
@@ -160,8 +178,9 @@ ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::last ()
 // Moves to the next item in the tree,
 // returns 1 if there is a next item, 0 otherwise.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE int
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::next ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 
+ACE_INLINE int
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::next ()
 {
   node_ = tree_.RB_tree_successor (node_);
   return node_ ? 1 : 0;
@@ -171,15 +190,17 @@ ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::next ()
 // Moves to the previous item in the tree,
 // returns 1 if there is a previous item, 0 otherwise.
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE int
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::previous ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 
+ACE_INLINE int
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::previous ()
 {
   node_ = tree_.RB_tree_predecessor (node_);
   return node_ ? 1 : 0;
 }
 
-template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_INLINE int
-ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::is_done ()
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 
+ACE_INLINE int
+ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::is_done ()
 {
   return node_ ? 0 : 1;
 }