diff options
| -rw-r--r-- | ace/RB_Tree.cpp | 673 | ||||
| -rw-r--r-- | ace/RB_Tree.h | 248 | ||||
| -rw-r--r-- | ace/RB_Tree.i | 155 |
3 files changed, 1076 insertions, 0 deletions
diff --git a/ace/RB_Tree.cpp b/ace/RB_Tree.cpp new file mode 100644 index 00000000000..28b2ff0706e --- /dev/null +++ b/ace/RB_Tree.cpp @@ -0,0 +1,673 @@ +// $Id$ + +// RB_Tree.cpp + +#if !defined (ACE_RB_TREE_C) +#define ACE_RB_TREE_C + +#include "ace/RB_Tree.h" + +#if !defined (__ACE_INLINE__) +#include "ace/RB_Tree.i" +#endif /* __ACE_INLINE__ */ + +///////////////////////////////////////// +// template class RB_Tree_Node<KEY, T> // +///////////////////////////////////////// + +template <class KEY, class T> +RB_Tree_Node<KEY, T>::RB_Tree_Node (const KEY &k, const T &t) + : k_ (k) + , t_ (t) + , color_ (RED) + , parent_ (0) + , left_ (0) + , right_ (0) +{ +} + // constructor + +template <class KEY, class T> +RB_Tree_Node<KEY, T>::~RB_Tree_Node () +{ + // delete left sub-tree + delete left_; + + // delete right sub_tree + delete right_; +} + // destructor + + + +//////////////////////////////////// +// template class RB_Tree<KEY, T> // +//////////////////////////////////// + +template <class KEY, class T> +RB_Tree<KEY, T>::RB_Tree () + : root_ (0) +{ +} + // constructor + +template <class KEY, class T> +RB_Tree<KEY, T>::RB_Tree (const RB_Tree<KEY, T> &rbt) + : root_ (0) +{ + // make a deep copy of the passed tree + RB_Tree_Iterator<KEY, T> iter(rbt); + for (iter.first (); iter.is_done () == 0; iter.next ()) + { + insert (*(iter.key ()), *(iter.item ())); + } +} + // copy constructor + +template <class KEY, class T> +RB_Tree<KEY, T>::~RB_Tree () +{ + // clear away all nodes in the tree + clear (); +} + // destructor + +template <class KEY, class T> void +RB_Tree<KEY, T>::operator = (const RB_Tree<KEY, T> &rbt) +{ + // clear out the existing tree + clear (); + + // make a deep copy of the passed tree + RB_Tree_Iterator<KEY, T> iter(rbt); + for (iter.first (); iter.is_done () == 0; iter.next ()) + { + insert (*(iter.key ()), *(iter.item ())); + } +} + // assignment operator + +template <class KEY, class T> T* +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); + + if (current) + { + // if a nearest matching node was returned + if ((current->key () < k) || (k < current->key ())) + { + // 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 + return &(current->item ()); + } + } + else + { + // else, 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. + +template <class KEY, class T> T* +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); + if (current) + { + if (current->key () < k) + { + // if a nearest matching node has a key less than the insertion key + if (current->right ()) + { + // 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); + } + else + { + // else, the right subtree is empty: insert new node there + current->right (new 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 + T *item = &(current->right ()->item ()); + current->right ()->parent (current); + RB_rebalance (current->right ()); + root_->color (BLACK); + return item; + } + else + { + // else, 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); + } + } + } + else if (k < current->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 + ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), + ASYS_TEXT ("\nleft subtree already present in " + "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)); + 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 ()); + current->left ()->parent (current); + RB_rebalance (current->left ()); + root_->color (BLACK); + return item; + } + else + { + // else, 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); + } + } + } + else + { + // else, 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); + if (root_) + { + root_->color (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); + } + } +} + // 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> int +RB_Tree<KEY, T>::remove (const KEY &k) +{ + // find a matching node, if there is one + RB_Tree_Node<KEY, T> *z = find_node (k); + + if ((z) && (! (z->key () < k)) && (! (k < z->key ()))) + { + // there is a matching node: remove and destroy it + RB_Tree_Node<KEY, T> *y + if ((z->left ()) && (z->right ())) + { + y = RB_tree_successor (z); + } + else + { + y = z; + } + if (y->left ()) + { + x = y->left (); + } + else + { + x = y->right (); + } + x->parent (y->parent ()); + if (y->parent ()) + { + if (y == y->parent ()->left ()) + { + y->parent ()->left (x); + } + else + { + y->parent ()->right (x); + } + } + else + { + root_ = x; + } + if (y != z) + { + // copy the elements of y into z + z->key () = y->key (); + z->item () = y->item (); + } + if (y->color () == RB_Tree_Node<KEY, T>::BLACK) + { + RB_delete_fixup (x); + } + y->parent (0); + y->right (0); + y->left (0); + delete y; + return 1; + } + else + { + // else, 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. + + +template <class KEY, class T> void +RB_Tree<KEY, T>::RB_rotate_right (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"))); + } + 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"))); + } + else + { + RB_Tree_Node<KEY, T> * y; + y = x->left (); + x->left (y->right ()); + if (y->right ()) + { + y->right ()->parent (x); + } + y->parent (x->parent ()); + if (x->parent ()) + { + if (x == x->parent ()->right ()) + { + x->parent ()->right (y); + } + else + { + x->parent ()->left (y); + } + } + else + { + root_ = y; + } + y->right (x); + x->parent (y); + } +} + // method for right 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) +{ + 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"))); + } + 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"))); + } + else + { + RB_Tree_Node<KEY, T> * y; + y = x->right (); + x->right (y->left ()); + if (y->left ()) + { + y->left ()->parent (x); + } + y->parent (x->parent ()); + if (x->parent ()) + { + if (x == x->parent ()->left ()) + { + x->parent ()->left (y); + } + else + { + x->parent ()->right (y); + } + } + else + { + root_ = y; + } + y->left (x); + x->parent (y); + } +} + // method for left rotation of the tree about a given node + +template <class KEY, class T> void +RB_Tree<KEY, T>::RB_delete_fixup (RB_Tree_Node<KEY, T> * x) +{ + while ((x) && (x->parent ()) && (x->color () == RB_Tree_Node<KEY, T>::BLACK)) + { + if (x == x->parent ()->left ()) + { + RB_Tree_Node<KEY, T> *w = x->parent ()->right (); + if (w->color () == RB_Tree_Node<KEY, T>::RED) + { + w->color (RB_Tree_Node<KEY, T>::BLACK); + x->parent ()->color (RB_Tree_Node<KEY, T>::RED); + RB_rotate_left (x->parent ()); + w = x->parent ()->right (); + } + if ((w->left ()->color () == RB_Tree_Node<KEY, T>::BLACK) && + (w->right ()->color () == RB_Tree_Node<KEY, T>::BLACK)) + { + w->color (RB_Tree_Node<KEY, T>::RED); + x = x->parent (); + } + else + { + if (w->right ()->color () == RB_Tree_Node<KEY, T>::BLACK) + { + w->left ()->color (RB_Tree_Node<KEY, T>::BLACK); + w->color (RB_Tree_Node<KEY, T>::RED); + RB_rotate_right (w); + w = x->parent->right (); + } + w->color (x->parent->color ()); + x->parent->color (RB_Tree_Node<KEY, T>::BLACK); + w->right->color (RB_Tree_Node<KEY, T>::BLACK); + RB_rotate_left (x->parent ()); + x = root_; + } + } + else + { + RB_Tree_Node<KEY, T> *w = x->parent ()->left (); + if (w->color () == RB_Tree_Node<KEY, T>::RED) + { + w->color (RB_Tree_Node<KEY, T>::BLACK); + x->parent ()->color (RB_Tree_Node<KEY, T>::RED); + RB_rotate_right (x->parent ()); + w = x->parent ()->left (); + } + if ((w->left ()->color () == RB_Tree_Node<KEY, T>::BLACK) && + (w->right ()->color () == RB_Tree_Node<KEY, T>::BLACK)) + { + w->color (RB_Tree_Node<KEY, T>::RED); + x = x->parent (); + } + else + { + if (w->left ()->color () == RB_Tree_Node<KEY, T>::BLACK) + { + w->right ()->color (RB_Tree_Node<KEY, T>::BLACK); + w->color (RB_Tree_Node<KEY, T>::RED); + RB_rotate_left (w); + w = x->parent->left (); + } + w->color (x->parent->color ()); + x->parent->color (RB_Tree_Node<KEY, T>::BLACK); + w->left->color (RB_Tree_Node<KEY, T>::BLACK); + RB_rotate_right (x->parent ()); + x = root_; + } + } + } + + if (x) + { + x->color (RB_Tree_Node<KEY, T>::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) +{ + RB_Tree_Node<KEY, T> *current = root_; + + while (current) + { + // while there are more nodes to examine + if (current->key () < k) + { + // 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 + current = current->right (); + } + else + { + // if the right subtree is empty, we're done + break; + } + } + else if (k < current->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 + current = current->left (); + } + else + { + // if the left subtree is empty, we're done + break; + } + } + else + { + // 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. + +template <class KEY, class T> void +RB_Tree<KEY, T>::RB_rebalance (RB_Tree_Node<KEY, T> * x) +{ + RB_Tree_Node<KEY, T> *y = 0; + + while ((x) && (x->parent ()) && (x->parent ()->color () == RED)) + { + if (! x->parent ()->parent ()) + { + // 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"))); + return; + } + + if (x->parent () == x->parent ()->parent ()->left ()) + { + y = x->parent ()->parent ()->right (); + if (y && (y->color () == RED)) + { + // handle case 1 (see CLR book, pp. 269) + x->parent ()->color (BLACK); + y->color (BLACK); + x->parent ()->parent ()->color (RED); + x = x->parent ()->parent (); + } + else + { + if (x == x->parent ()->right ()) + { + // 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 (BLACK); + x->parent ()->parent ()->color (RED); + RB_rotate_right (x->parent ()->parent ()); + } + } + else + { + y = x->parent ()->parent ()->left (); + if (y && (y->color () == RED)) + { + // handle case 1 (see CLR book, pp. 269) + x->parent ()->color (BLACK); + y->color (BLACK); + x->parent ()->parent ()->color (RED); + x = x->parent ()->parent (); + } + else + { + if (x == x->parent ()->left ()) + { + // 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 (BLACK); + x->parent ()->parent ()->color (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 +{ + if (x->right ()) + { + return RB_tree_minimum (x->right ()); + } + + RB_Tree_Node<KEY, T> *y = x->parent (); + while ((y) && (x == y->right ())) + { + x = y; + y = y->parent (); + } + + 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 +{ + if (x->left ()) + { + return RB_tree_maximum (x->left ()); + } + + RB_Tree_Node<KEY, T> *y = x->parent (); + while ((y) && (x == y->left ())) + { + x = y; + y = y->parent (); + } + + 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 +{ + while ((x) && (x->left ())) + { + x = x->left (); + } + + 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 +{ + while ((x) && (x->right ())) + { + x = x->right (); + } + + 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 KEY, class T> +RB_Tree_Iterator<KEY, T>::RB_Tree_Iterator (const RB_Tree<KEY, T> &tree) + : tree_ (tree), node_ (0) +{ + // position the iterator at the first node in the tree + first (); +} + // constructor + +template <class KEY, class T> +RB_Tree_Iterator<KEY, T>::~RB_Tree_Iterator () +{ +} + // destructor + + +#endif /* !defined (ACE_RB_TREE_C) */ + diff --git a/ace/RB_Tree.h b/ace/RB_Tree.h new file mode 100644 index 00000000000..4bf6dc8e263 --- /dev/null +++ b/ace/RB_Tree.h @@ -0,0 +1,248 @@ +/* -*- C++ -*- */ +// $Id$ + +// ============================================================================ +// +// = LIBRARY +// ace +// +// = FILENAME +// RB_Tree.h +// +// = AUTHOR +// Chris Gill +// +// ============================================================================ + +#if !defined (ACE_RB_TREE_H) +#define ACE_RB_TREE_H + +#include "ace/ACE.h" + +enum RB_Tree_Node_Color {RED, BLACK}; + +// Class Template: RB_Tree_Node +// +// Purpose: Implements a node in a Red-Black Tree ADT +// +template <class KEY, class T> +class RB_Tree_Node +{ +public: + + RB_Tree_Node (const KEY &k, const T &t); + // constructor + + ~RB_Tree_Node (); + // destructor + + KEY & key (); + // key accessor + + T & item (); + // item accessor + + void color (RB_Tree_Node_Color c); + // set color of the node + + RB_Tree_Node_Color color (); + // get color of the node + + RB_Tree_Node<KEY, T> * parent (); + // accessor for node's parent pointer + + void parent (RB_Tree_Node<KEY, T> * p); + // mutator for node's parent pointer + + RB_Tree_Node<KEY, T> * left (); + // accessor for node's left child pointer + + void left (RB_Tree_Node<KEY, T> * l); + // mutator for node's left child pointer + + RB_Tree_Node<KEY, T> * right (); + // accessor for node's rightt child pointer + + void right (RB_Tree_Node<KEY, T> * r); + // mutator for node's right child pointer + +private: + + KEY k_; + // the key + + T t_; + // the item + + RB_Tree_Node_Color color_; + // color of the node + + RB_Tree_Node<KEY, T> *parent_; + // pointer to node's parent + + RB_Tree_Node<KEY, T> *left_; + // pointer to node's left child + + RB_Tree_Node<KEY, T> *right_; + // pointer to node's righ child + +}; + +// Class Template: RB_Tree +// +// Purpose: 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 +// +template <class KEY, class T> +class RB_Tree +{ +public: + + RB_Tree (); + // constructor + + RB_Tree (const RB_Tree<KEY, T> &rbt); + // copy constructor + + ~RB_Tree (); + // destructor + + void operator = (const RB_Tree<KEY, T> &rbt); + // assignment operator + + T* find (const KEY &k); + // Returns a pointer to the item corresponding to the + // given key, or 0 if it cannot find the key in the tree. + + 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 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. + + int remove (const KEY &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. + + void clear (); + // 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 + +// private: + + void RB_rotate_right (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); + // method for left rotation of the tree about a given node + + void RB_delete_fixup (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; + // 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; + // 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; + // 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; + // method to find the maximum node of the subtree rooted at the given node + + 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); + // rebalance the tree after insertion of a node + + // private members + + RB_Tree_Node<KEY, T> *root_; + // the root of the tree + +}; + +// Class Template: RB_Tree_Iterator +// +// Purpose: Implements an iterator for a Red-Black Tree ADT +// +template <class KEY, class T> +class RB_Tree_Iterator +{ +public: + + RB_Tree_Iterator (const RB_Tree<KEY, T> &tree); + // constructor + + ~RB_Tree_Iterator (); + // destructor + + KEY * key (); + // accessor for key of node under iterator (if any) + + T * item (); + // accessor for item of node under iterator (if any) + + int first (); + // move to the first item in the tree + + int last (); + // move to the last item in the tree + + int next (); + // move to the next item in the tree + + int previous (); + // move to the previous item in the tree + + int is_done (); + // returns 0 if the iterator is positioned over + // a valid RB_Tree node, returns 1 if not + +private: + + // declare private and do not define: explicitly + // prevent assignment and copy construction of iterators + RB_Tree_Iterator (const RB_Tree_Iterator<KEY, T> &); + operator = (const RB_Tree_Iterator<KEY, T> &); + + // private members + + const RB_Tree<KEY, T> &tree_; + // reference to the RB_Tree over which we're iterating + + RB_Tree_Node <KEY, T> *node_; + // pointer to the node currently under the iterator + +}; + +#if defined (__ACE_INLINE__) +#include "ace/RB_Tree.i" +#endif /* __ACE_INLINE__ */ + +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +#include "ace/RB_Tree.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ + +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +#pragma implementation ("RB_Tree.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ + +#endif /* ! defined (ACE_RB_TREE_H) */ + diff --git a/ace/RB_Tree.i b/ace/RB_Tree.i new file mode 100644 index 00000000000..28bc6f9d614 --- /dev/null +++ b/ace/RB_Tree.i @@ -0,0 +1,155 @@ +/* -*- C++ -*- */ +// $Id$ + +// RB_Tree.i + +///////////////////////////////////////// +// template class RB_Tree_Node<KEY, T> // +///////////////////////////////////////// + +template <class KEY, class T> ACE_INLINE KEY & +RB_Tree_Node<KEY, T>::key () +{ + return k_; +} + // key accessor + +template <class KEY, class T> ACE_INLINE T & +RB_Tree_Node<KEY, T>::item () +{ + return t_; +} + // item accessor + +template <class KEY, class T> ACE_INLINE void +RB_Tree_Node<KEY, T>::color (RB_Tree_Node_Color c) +{ + color_ = c; +} + // set color of the node + +template <class KEY, class T> ACE_INLINE RB_Tree_Node_Color +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 () +{ + return parent_; +} + // accessor 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) +{ + parent_ = p; +} + // mutator for node's parent pointer + +template <class KEY, class T> ACE_INLINE RB_Tree_Node<KEY, T> * +RB_Tree_Node<KEY, T>::left () +{ + return left_; +} + // accessor 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) +{ + 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 () +{ + return right_; +} + // accessor 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) +{ + right_ = r; +} + // mutator for node's right child pointer + + +//////////////////////////////////// +// template class RB_Tree<KEY, T> // +//////////////////////////////////// + +template <class KEY, class T> ACE_INLINE void +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 KEY, class T> ACE_INLINE KEY * +RB_Tree_Iterator<KEY, T>::key () +{ + return node_ ? (&(node_->key ())) : 0; +} + // accessor for key of node under iterator (if any) + +template <class KEY, class T> ACE_INLINE T * +RB_Tree_Iterator<KEY, T>::item () +{ + return node_ ? (&(node_->item ())) : 0; +} + // accessor for item of node under iterator (if any) + +template <class KEY, class T> ACE_INLINE int +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 + +template <class KEY, class T> ACE_INLINE int +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 + +template <class KEY, class T> ACE_INLINE int +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 + +template <class KEY, class T> ACE_INLINE int +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 () +{ + return node_ ? 0 : 1; +} + + |