diff options
Diffstat (limited to 'ace')
| -rw-r--r-- | ace/Functor_T.h | 135 | ||||
| -rw-r--r-- | ace/Functor_T.i | 18 | ||||
| -rw-r--r-- | ace/RB_Tree.cpp | 463 | ||||
| -rw-r--r-- | ace/RB_Tree.h | 120 | ||||
| -rw-r--r-- | ace/RB_Tree.i | 133 |
5 files changed, 582 insertions, 287 deletions
diff --git a/ace/Functor_T.h b/ace/Functor_T.h index 471170262e4..10883b311e0 100644 --- a/ace/Functor_T.h +++ b/ace/Functor_T.h @@ -66,6 +66,141 @@ private: // Method that is going to be invoked. }; +///////////////////////////// +// Unary functor templates // +///////////////////////////// + +template <class OPERAND> +class ACE_Unary_Functor_Base +{ + // = TITLE + // Defines a class template that allows us to invoke a function object + // over a single non-const parameterized type without knowing anything + // about the function and operand objects except their types. + // + // = DESCRIPTION + // This class declares an interface to execute a unary operation over a + // single object of the non-const paramterized type. A class can invoke + // such operation without knowing anything about it, or how it was + // implemented. + // +public: + + virtual ~ACE_Unary_Functor_Base () {}; + // Virtual destructor. + + virtual int execute (OPERAND &operand) = 0; + // Invokes the function object. + + virtual ACE_Unary_Functor_Base * clone () = 0; + // Creates another object of the same type. +}; + +template <class OPERAND> +class ACE_Const_Unary_Functor_Base +{ + // = TITLE + // Defines a class template that allows us to invoke a function object + // over a single parameterized type without knowing anything about + // the function and operand objects except their types. + // + // = DESCRIPTION + // This class declares an interface to execute a unary operation over a + // single object of the paramterized type. A class can invoke such + // an operation without knowing anything about it, or its implementation. + // +public: + + virtual ~ACE_Const_Unary_Functor_Base () {}; + // Virtual destructor. + + virtual int execute (const OPERAND &operand) = 0; + // Invokes the function object. + + virtual ACE_Const_Unary_Functor_Base * clone () = 0; + // Creates another object of the same type. +}; + +///////////////////////////// +// Binary functor templates // +///////////////////////////// + +template <class OPERAND1, class OPERAND2> +class ACE_Binary_Functor_Base +{ + // = TITLE + // Defines a class template that allows us to invoke a binary function + // object over two non-const parameterized types without knowing anything + // about the function and operand objects except their types. + // + // = DESCRIPTION + // This class declares an interface to execute a binary operation over two + // objects of the paramterized non-const types. A class can invoke such + // an operation without knowing anything about it, or its implementation. + // +public: + + virtual ~ACE_Binary_Functor_Base () {}; + // Virtual destructor. + + virtual int execute (OPERAND1 &operand1, OPERAND2 &operand2) = 0; + // Invokes the function object. + + virtual ACE_Binary_Functor_Base * clone () = 0; + // Creates another object of the same type. +}; + +template <class OPERAND1, class OPERAND2> +class ACE_Const_Binary_Functor_Base +{ + // = TITLE + // Defines a class template that allows us to invoke a binary function + // object over two parameterized types without knowing anything about + // the function and operand objects except their types. + // + // = DESCRIPTION + // This class declares an interface to execute a binary operation over two + // objects of the paramterized types. A class can invoke such + // an operation without knowing anything about it, or its implementation. + // +public: + + virtual ~ACE_Const_Binary_Functor_Base () {}; + // Virtual destructor. + + virtual int execute (const OPERAND1 &operand1, const OPERAND2 &operand2) = 0; + // Invokes the function object. + + virtual ACE_Const_Binary_Functor_Base * clone () = 0; + // Creates another object of the same type. +}; + + +template <class OPERAND1, class OPERAND2> +class ACE_Less_Than_Functor : + public ACE_Const_Binary_Functor_Base<OPERAND1, OPERAND2> +{ + // = TITLE + // Defines a class template that allows us to invoke a binary less than + // function over two parameterized types without knowing anything about + // the function and operand objects except their types. + // + // = DESCRIPTION + // This class depends on the definition + // objects of the paramterized types. A class can invoke such + // an operation without knowing anything about it, or its implementation. + // +public: + + virtual int execute (const OPERAND1 &operand1, const OPERAND2 &operand2); + // Invokes the function object. + + virtual + ACE_Const_Binary_Functor_Base<OPERAND1, OPERAND2> + * clone (); + // Creates another object of the same type. +}; + #if defined (__ACE_INLINE__) #include "ace/Functor_T.i" diff --git a/ace/Functor_T.i b/ace/Functor_T.i index 6bb3fdeccce..01b93b3dfca 100644 --- a/ace/Functor_T.i +++ b/ace/Functor_T.i @@ -26,5 +26,23 @@ // ============================================================================ +// Invokes the less than function object. + +template <class OPERAND1, class OPERAND2> ACE_INLINE int +ACE_Less_Than_Functor<OPERAND1, OPERAND2>::execute (const OPERAND1 &operand1, + const OPERAND2 &operand2) +{ + return (operand1 < operand2) ? 1 : 0; +} + +// Creates another object of the same type. + +template <class OPERAND1, class OPERAND2> ACE_INLINE +ACE_Const_Binary_Functor_Base<OPERAND1, OPERAND2> * +ACE_Less_Than_Functor<OPERAND1, OPERAND2>::clone () +{ + return new ACE_Less_Than_Functor<OPERAND1, OPERAND2>; +} + // EOF 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) */ diff --git a/ace/RB_Tree.h b/ace/RB_Tree.h index e7a0c2ce470..7728c59d366 100644 --- a/ace/RB_Tree.h +++ b/ace/RB_Tree.h @@ -18,28 +18,31 @@ #define ACE_RB_TREE_H #include "ace/ACE.h" +#include "ace/Functor.h" #if !defined (ACE_LACKS_PRAGMA_ONCE) # pragma once #endif /* ACE_LACKS_PRAGMA_ONCE */ -class RB_Tree_Node_Base +class ACE_RB_Tree_Node_Base { public: enum RB_Tree_Node_Color {RED, BLACK}; }; template <class KEY, class T> -class RB_Tree_Node : public RB_Tree_Node_Base +class ACE_RB_Tree_Node : public ACE_RB_Tree_Node_Base { // = TITLE // Implements a node in a Red-Black Tree ADT. public: + // Initialization and termination methods. - RB_Tree_Node (const KEY &k, const T &t); + + ACE_RB_Tree_Node (const KEY &k, const T &t); // Constructor. - ~RB_Tree_Node (void); + ~ACE_RB_Tree_Node (void); // Destructor. KEY &key (void); @@ -54,22 +57,22 @@ public: RB_Tree_Node_Color color (void); // Get color of the node. - RB_Tree_Node<KEY, T> *parent (void); + ACE_RB_Tree_Node<KEY, T> *parent (void); // Accessor for node's parent pointer. - void parent (RB_Tree_Node<KEY, T> * p); + void parent (ACE_RB_Tree_Node<KEY, T> * p); // Mutator for node's parent pointer. - RB_Tree_Node<KEY, T> *left (void); + ACE_RB_Tree_Node<KEY, T> *left (void); // Accessor for node's left child pointer. - void left (RB_Tree_Node<KEY, T> *l); + void left (ACE_RB_Tree_Node<KEY, T> *l); // Mutator for node's left child pointer. - RB_Tree_Node<KEY, T> *right (void); + ACE_RB_Tree_Node<KEY, T> *right (void); // Accessor for node's right child pointer. - void right (RB_Tree_Node<KEY, T> * r); + void right (ACE_RB_Tree_Node<KEY, T> * r); // Mutator for node's right child pointer private: @@ -83,40 +86,45 @@ private: RB_Tree_Node_Color color_; // Color of the node. - RB_Tree_Node<KEY, T> *parent_; + ACE_RB_Tree_Node<KEY, T> *parent_; // Pointer to node's parent. - RB_Tree_Node<KEY, T> *left_; + ACE_RB_Tree_Node<KEY, T> *left_; // Pointer to node's left child. - RB_Tree_Node<KEY, T> *right_; - // Pointer to node's righ child. + ACE_RB_Tree_Node<KEY, T> *right_; + // Pointer to node's right child. }; template <class KEY, class T> -class RB_Tree +class ACE_RB_Tree { // = TITLE // Implements a Red-Black Tree ADT, according to T. H. Corman, // C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms" - // 1990, MIT, chapter 14 + // 1990, MIT, chapter 14. + // + // = Description + // Optional flag passed to constructor indicates whether or not the + // passed functor should be deleted by the ACE_RB_Tree's destructor. public: // = Initialization and termination methods. - RB_Tree (void); - // Constructor + ACE_RB_Tree (ACE_Const_Binary_Functor_Base<KEY, KEY> *less_than_functor = 0, + int free_functor = 0); + // Constructor. - RB_Tree (const RB_Tree<KEY, T> &rbt); - // copy constructor. + ACE_RB_Tree (const ACE_RB_Tree<KEY, T> &rbt); + // Copy constructor. - virtual ~RB_Tree (void); - // Destructor + virtual ~ACE_RB_Tree (void); + // Destructor. - void operator= (const RB_Tree<KEY, T> &rbt); + void operator= (const ACE_RB_Tree<KEY, T> &rbt); // Assignment operator. virtual int lessthan (const KEY &k1, const KEY &k2); - // Lessthan comparison function for keys. returns 1 if k1 < k2, 0 - // otherwise. + // Less than comparison function for keys. Default implementation returns 1 + // if k1 < k2, and 0 otherwise. T* find (const KEY &k); // Returns a pointer to the item corresponding to the @@ -125,7 +133,8 @@ public: T* insert (const KEY &k, const T &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 - // for copy construction and < comparison. This method returns a + // for copy construction. The default implementation also requires that + // the key type support welll 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 @@ -138,63 +147,74 @@ public: // occurred. void clear (void); - // destroys all nodes and sets the root pointer null. + // Destroys all nodes and sets the root pointer null. // These could all be made private methods by making the corresponding // class template instantiations friends, but there are some problems - // with this on certain compilers: leave them all public for now + // with this on certain compilers: leave them all public for now. // private: - void RB_rotate_right (RB_Tree_Node<KEY, T> * x); + void RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x); // Method for right rotation of the tree about a given node. - void RB_rotate_left (RB_Tree_Node<KEY, T> * x); + void RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x); // Method for left rotation of the tree about a given node. - void RB_delete_fixup (RB_Tree_Node<KEY, T> * x); + void RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x); // Method for restoring Red-Black properties after deletion. - RB_Tree_Node<KEY, T> * RB_tree_successor (RB_Tree_Node<KEY, T> *x) const; + ACE_RB_Tree_Node<KEY, T> * + RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const; // Method to find the successor node of the given node in the tree. - RB_Tree_Node<KEY, T> * RB_tree_predecessor (RB_Tree_Node<KEY, T> *x) const; + ACE_RB_Tree_Node<KEY, T> * + RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const; // Method to find the predecessor node of the given node in the // tree. - RB_Tree_Node<KEY, T> * RB_tree_minimum (RB_Tree_Node<KEY, T> *x) const; + ACE_RB_Tree_Node<KEY, T> * + RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const; // Method to find the minimum node of the subtree rooted at the // given node. - RB_Tree_Node<KEY, T> * RB_tree_maximum (RB_Tree_Node<KEY, T> *x) const; + ACE_RB_Tree_Node<KEY, T> * + RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const; // Method to find the maximum node of the subtree rooted at the // given node. - RB_Tree_Node<KEY, T> * find_node (const KEY &k); + ACE_RB_Tree_Node<KEY, T> * find_node (const KEY &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 (RB_Tree_Node<KEY, T> * x); + void RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x); // Rebalance the tree after insertion of a node. - // private members + // Private members. - RB_Tree_Node<KEY, T> *root_; + ACE_RB_Tree_Node<KEY, T> *root_; // The root of the tree. + + ACE_Const_Binary_Functor_Base<KEY, KEY> *less_than_functor_; + // "Less than" functor for comparing nodes in the tree. + + int free_functor_; + // Flag indicating whether or not to delete functor in destructor + // and assignment operator. }; template <class KEY, class T> -class RB_Tree_Iterator +class ACE_RB_Tree_Iterator { // = TITLE // Implements an iterator for a Red-Black Tree ADT. public: // = Initialization and termination methods. - RB_Tree_Iterator (const RB_Tree<KEY, T> &tree); + ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T> &tree); // Constructor. - ~RB_Tree_Iterator (void); + ~ACE_RB_Tree_Iterator (void); // Destructor. KEY *key (void); @@ -216,22 +236,24 @@ public: // Move to the previous item in the tree. int is_done (void); - // Returns 0 if the iterator is positioned over a valid RB_Tree + // Returns 0 if the iterator is positioned over a valid ACE_RB_Tree // node, returns 1 if not. private: // = Declare private and do not define. - // Explicitly prevent assignment and copy construction of iterators - ACE_UNIMPLEMENTED_FUNC (RB_Tree_Iterator (const RB_Tree_Iterator<KEY, T> &)) - ACE_UNIMPLEMENTED_FUNC (void operator = (const RB_Tree_Iterator<KEY, T> &)) + // Explicitly prevent assignment and copy construction of iterators. + ACE_UNIMPLEMENTED_FUNC ( + ACE_RB_Tree_Iterator (const ACE_RB_Tree_Iterator<KEY, T> &)) + ACE_UNIMPLEMENTED_FUNC ( + void operator = (const ACE_RB_Tree_Iterator<KEY, T> &)) // Private members. - const RB_Tree<KEY, T> &tree_; - // Reference to the RB_Tree over which we're iterating. + const ACE_RB_Tree<KEY, T> &tree_; + // Reference to the ACE_RB_Tree over which we're iterating. - RB_Tree_Node <KEY, T> *node_; + ACE_RB_Tree_Node <KEY, T> *node_; // Pointer to the node currently under the iterator. }; diff --git a/ace/RB_Tree.i b/ace/RB_Tree.i index ce6c15dfa0a..b423d77d5dd 100644 --- a/ace/RB_Tree.i +++ b/ace/RB_Tree.i @@ -1,152 +1,185 @@ /* -*- C++ -*- */ // $Id$ -///////////////////////////////////////// -// template class RB_Tree_Node<KEY, T> // -///////////////////////////////////////// +///////////////////////////////////////////// +// template class ACE_RB_Tree_Node<KEY, T> // +///////////////////////////////////////////// + +// Key accessor. template <class KEY, class T> ACE_INLINE KEY & -RB_Tree_Node<KEY, T>::key () +ACE_RB_Tree_Node<KEY, T>::key () { return k_; } - // key accessor + + +// Item accessor. template <class KEY, class T> ACE_INLINE T & -RB_Tree_Node<KEY, T>::item () +ACE_RB_Tree_Node<KEY, T>::item () { return t_; } - // item accessor + + +// Set color of the node. template <class KEY, class T> ACE_INLINE void -RB_Tree_Node<KEY, T>::color (RB_Tree_Node_Base::RB_Tree_Node_Color c) +ACE_RB_Tree_Node<KEY, T>::color (ACE_RB_Tree_Node_Base::RB_Tree_Node_Color c) { color_ = c; } - // set color of the node + + +// Get color of the node. template <class KEY, class T> -ACE_INLINE RB_Tree_Node_Base::RB_Tree_Node_Color -RB_Tree_Node<KEY, T>::color () +ACE_INLINE ACE_RB_Tree_Node_Base::RB_Tree_Node_Color +ACE_RB_Tree_Node<KEY, T>::color () { return color_; } - // get color of the node -template <class KEY, class T> ACE_INLINE RB_Tree_Node<KEY, T> * -RB_Tree_Node<KEY, T>::parent () +// 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 () { return parent_; } - // accessor for node's parent pointer + + +// Mutator for node's parent pointer. template <class KEY, class T> ACE_INLINE void -RB_Tree_Node<KEY, T>::parent (RB_Tree_Node<KEY, T> * p) +ACE_RB_Tree_Node<KEY, T>::parent (ACE_RB_Tree_Node<KEY, T> * p) { parent_ = p; } - // mutator for node's parent pointer + + + +// Accessor for node's left child pointer. -template <class KEY, class T> ACE_INLINE RB_Tree_Node<KEY, T> * -RB_Tree_Node<KEY, T>::left () +template <class KEY, class T> ACE_INLINE ACE_RB_Tree_Node<KEY, T> * +ACE_RB_Tree_Node<KEY, T>::left () { return left_; } - // accessor for node's left child pointer + + +// Mutator for node's left child pointer. template <class KEY, class T> ACE_INLINE void -RB_Tree_Node<KEY, T>::left (RB_Tree_Node<KEY, T> * l) +ACE_RB_Tree_Node<KEY, T>::left (ACE_RB_Tree_Node<KEY, T> * l) { left_ = l; } - // mutator for node's left child pointer -template <class KEY, class T> ACE_INLINE RB_Tree_Node<KEY, T> * -RB_Tree_Node<KEY, T>::right () + +// 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 () { return right_; } - // accessor for node's right child pointer + + +// Mutator for node's right child pointer. template <class KEY, class T> ACE_INLINE void -RB_Tree_Node<KEY, T>::right (RB_Tree_Node<KEY, T> * r) +ACE_RB_Tree_Node<KEY, T>::right (ACE_RB_Tree_Node<KEY, T> * r) { right_ = r; } - // mutator for node's right child pointer -//////////////////////////////////// -// template class RB_Tree<KEY, T> // -//////////////////////////////////// + +//////////////////////////////////////// +// template class ACE_RB_Tree<KEY, T> // +//////////////////////////////////////// + + +// Destroys all nodes and sets the root pointer null. template <class KEY, class T> ACE_INLINE void -RB_Tree<KEY, T>::clear () +ACE_RB_Tree<KEY, T>::clear () { delete root_; root_ = 0; } - // destroys all nodes and sets the root pointer null. -///////////////////////////////////////////// -// template class RB_Tree_Iterator<KEY, T> // -///////////////////////////////////////////// +///////////////////////////////////////////////// +// template class ACE_RB_Tree_Iterator<KEY, T> // +///////////////////////////////////////////////// +// Accessor for key of node under iterator (if any). + template <class KEY, class T> ACE_INLINE KEY * -RB_Tree_Iterator<KEY, T>::key () +ACE_RB_Tree_Iterator<KEY, T>::key () { return node_ ? (&(node_->key ())) : 0; } - // accessor for key of node under iterator (if any) + + +// Accessor for item of node under iterator (if any). template <class KEY, class T> ACE_INLINE T * -RB_Tree_Iterator<KEY, T>::item () +ACE_RB_Tree_Iterator<KEY, T>::item () { return node_ ? (&(node_->item ())) : 0; } - // accessor for item of node under iterator (if any) + + +// Move to the first item in the tree. template <class KEY, class T> ACE_INLINE int -RB_Tree_Iterator<KEY, T>::first () +ACE_RB_Tree_Iterator<KEY, T>::first () { node_ = tree_.RB_tree_minimum (tree_.root_); return node_ ? 1 : 0; } - // move to the first item in the tree + + +// Move to the last item in the tree. template <class KEY, class T> ACE_INLINE int -RB_Tree_Iterator<KEY, T>::last () +ACE_RB_Tree_Iterator<KEY, T>::last () { node_ = tree_.RB_tree_maximum (tree_.root_); return node_ ? 1 : 0; } - // move to the last item in the tree + + +// Moves to the next item in the tree, +// returns 1 if there is a next item, 0 otherwise. template <class KEY, class T> ACE_INLINE int -RB_Tree_Iterator<KEY, T>::next () +ACE_RB_Tree_Iterator<KEY, T>::next () { node_ = tree_.RB_tree_successor (node_); return node_ ? 1 : 0; } - // move to the next item in the tree - // returns 1 if there is a next item, 0 otherwise + + +// Moves to the previous item in the tree, +// returns 1 if there is a previous item, 0 otherwise. template <class KEY, class T> ACE_INLINE int -RB_Tree_Iterator<KEY, T>::previous () +ACE_RB_Tree_Iterator<KEY, T>::previous () { node_ = tree_.RB_tree_predecessor (node_); return node_ ? 1 : 0; } - // move to the previous item in the tree - // returns 1 if there is a previous item, 0 otherwise template <class KEY, class T> ACE_INLINE int -RB_Tree_Iterator<KEY, T>::is_done () +ACE_RB_Tree_Iterator<KEY, T>::is_done () { return node_ ? 0 : 1; } |