diff options
Diffstat (limited to 'ace/RB_Tree.h')
| -rw-r--r-- | ace/RB_Tree.h | 210 |
1 files changed, 103 insertions, 107 deletions
diff --git a/ace/RB_Tree.h b/ace/RB_Tree.h index 231a355b376..969396e82b0 100644 --- a/ace/RB_Tree.h +++ b/ace/RB_Tree.h @@ -19,224 +19,220 @@ #include "ace/ACE.h" +#if !defined (ACE_LACKS_PRAGMA_ONCE) +#pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + class RB_Tree_Node_Base { public: - 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_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); - // constructor + // Constructor. - ~RB_Tree_Node (); - // destructor + ~RB_Tree_Node (void); + // Destructor. - KEY & key (); - // key accessor + KEY &key (void); + // Key accessor. - T & item (); - // item accessor + T &item (void); + // Item accessor. void color (RB_Tree_Node_Color c); - // set color of the node + // Set color of the node. - RB_Tree_Node_Color color (); - // get color of the node + RB_Tree_Node_Color color (void); + // Get color of the node. - RB_Tree_Node<KEY, T> * parent (); - // accessor for node's parent pointer + RB_Tree_Node<KEY, T> *parent (void); + // Accessor for node's parent pointer. void parent (RB_Tree_Node<KEY, T> * p); - // mutator for node's parent pointer + // Mutator for node's parent pointer. - RB_Tree_Node<KEY, T> * left (); - // accessor for node's left child pointer + RB_Tree_Node<KEY, T> *left (void); + // Accessor for node's left child pointer. - void left (RB_Tree_Node<KEY, T> * l); - // mutator 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 + RB_Tree_Node<KEY, T> *right (void); + // Accessor for node's right child pointer. void right (RB_Tree_Node<KEY, T> * r); - // mutator for node's right child pointer + // Mutator for node's right child pointer private: KEY k_; - // the key + // The key. T t_; - // the item + // The item. RB_Tree_Node_Color color_; - // color of the node + // Color of the node. RB_Tree_Node<KEY, T> *parent_; - // pointer to node's parent + // Pointer to node's parent. RB_Tree_Node<KEY, T> *left_; - // pointer to node's left child + // Pointer to node's left child. RB_Tree_Node<KEY, T> *right_; - // pointer to node's righ child - + // 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 { + // = 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 public: - - RB_Tree (); - // constructor + // = Initialization and termination methods. + RB_Tree (void); + // Constructor RB_Tree (const RB_Tree<KEY, T> &rbt); - // copy constructor + // copy constructor. - virtual ~RB_Tree (); - // destructor + virtual ~RB_Tree (void); + // Destructor - void operator = (const RB_Tree<KEY, T> &rbt); - // assignment operator + void operator= (const 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 + // Lessthan comparison function for keys. returns 1 if k1 < k2, 0 + // otherwise. 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 + // 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. + // 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 (); + void clear (void); // 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 + // 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 + // 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 + // 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 + // 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 + // 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 + // 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 + // 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 + // 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. + // 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 + // Rebalance the tree after insertion of a node. // private members RB_Tree_Node<KEY, T> *root_; - // the root of the tree - + // 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 { + // = TITLE + // Implements an iterator for a Red-Black Tree ADT. public: - + // = Initialization and termination methods. RB_Tree_Iterator (const RB_Tree<KEY, T> &tree); - // constructor + // Constructor. - ~RB_Tree_Iterator (); - // destructor + ~RB_Tree_Iterator (void); + // Destructor. - KEY * key (); - // accessor for key of node under iterator (if any) + KEY *key (void); + // Accessor for key of node under iterator (if any). - T * item (); - // accessor for item of node under iterator (if any) + T *item (void); + // Accessor for item of node under iterator (if any). - int first (); - // move to the first item in the tree + int first (void); + // Move to the first item in the tree. - int last (); - // move to the last item in the tree + int last (void); + // Move to the last item in the tree. - int next (); - // move to the next item in the tree + int next (void); + // Move to the next item in the tree. - int previous (); - // move to the previous item in the tree + int previous (void); + // 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 + int is_done (void); + // 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 + // = 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> &)) - // private members + // Private members. const RB_Tree<KEY, T> &tree_; - // reference to the RB_Tree over which we're iterating + // Reference to the RB_Tree over which we're iterating. RB_Tree_Node <KEY, T> *node_; - // pointer to the node currently under the iterator + // Pointer to the node currently under the iterator. }; |