Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

RB_Tree.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 //=============================================================================
00004 /**
00005  *  @file    RB_Tree.h
00006  *
00007  *  $Id: RB_Tree.h,v 1.1.1.4 2003/02/21 18:36:32 chad Exp $
00008  *
00009  *  @author  Chris Gill
00010  */
00011 //=============================================================================
00012 
00013 
00014 #ifndef ACE_RB_TREE_H
00015 #define ACE_RB_TREE_H
00016 #include "ace/pre.h"
00017 
00018 #include "ace/Global_Macros.h"
00019 #include "ace/Functor.h"
00020 
00021 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00022 # pragma once
00023 #endif /* ACE_LACKS_PRAGMA_ONCE */
00024 
00025 // Forward decl.
00026 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00027 class ACE_RB_Tree_Iterator_Base;
00028 
00029 // Forward decl.
00030 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00031 class ACE_RB_Tree_Iterator;
00032 
00033 // Forward decl.
00034 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00035 class ACE_RB_Tree_Reverse_Iterator;
00036 
00037 // Forward decl.
00038 class ACE_Allocator;
00039 
00040 class ACE_RB_Tree_Node_Base
00041 {
00042 public:
00043   enum RB_Tree_Node_Color {RED, BLACK};
00044 };
00045 
00046 /**
00047  * @class ACE_RB_Tree_Node
00048  *
00049  * @brief Implements a node in a Red-Black Tree ADT.
00050  */
00051 template <class EXT_ID, class INT_ID>
00052 class ACE_RB_Tree_Node : public ACE_RB_Tree_Node_Base
00053 {
00054 public:
00055   // = Initialization and termination methods.
00056 
00057   /// Constructor.
00058   ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t);
00059 
00060   /// Destructor.
00061   ~ACE_RB_Tree_Node (void);
00062 
00063   /// Key accessor.
00064   EXT_ID &key (void);
00065 
00066   /// Item accessor.
00067   INT_ID &item (void);
00068 
00069   /// Set color of the node.
00070   void color (RB_Tree_Node_Color c);
00071 
00072   /// Get color of the node.
00073   RB_Tree_Node_Color color (void);
00074 
00075   /// Accessor for node's parent pointer.
00076   ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent (void);
00077 
00078   /// Mutator for node's parent pointer.
00079   void parent (ACE_RB_Tree_Node<EXT_ID, INT_ID> * p);
00080 
00081   /// Accessor for node's left child pointer.
00082   ACE_RB_Tree_Node<EXT_ID, INT_ID> *left (void);
00083 
00084   /// Mutator for node's left child pointer.
00085   void left (ACE_RB_Tree_Node<EXT_ID, INT_ID> *l);
00086 
00087   /// Accessor for node's right child pointer.
00088   ACE_RB_Tree_Node<EXT_ID, INT_ID> *right (void);
00089 
00090   /// Mutator for node's right child pointer
00091   void right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * r);
00092 
00093 private:
00094 
00095   /// The key.
00096   EXT_ID k_;
00097 
00098   /// The item.
00099   INT_ID t_;
00100 
00101   /// Color of the node.
00102   RB_Tree_Node_Color color_;
00103 
00104   /// Pointer to node's parent.
00105   ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent_;
00106 
00107   /// Pointer to node's left child.
00108   ACE_RB_Tree_Node<EXT_ID, INT_ID> *left_;
00109 
00110   /// Pointer to node's right child.
00111   ACE_RB_Tree_Node<EXT_ID, INT_ID> *right_;
00112 };
00113 
00114 class ACE_RB_Tree_Base
00115 {
00116 public:
00117   /// Search result enumeration.
00118   enum RB_SearchResult {LEFT, EXACT, RIGHT};
00119 };
00120 
00121 /**
00122  * @class ACE_RB_Tree
00123  *
00124  * @brief Implements a Red-Black Tree ADT, according to T. H. Corman,
00125  * C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms"
00126  * 1990, MIT, chapter 14.
00127  *
00128  * A number of Changes have been made to this class template
00129  * in order to conform to the ACE_Hash_Map_Manager_Ex
00130  * interface.  All previously supported public methods are
00131  * still part of this class. However, these are marked as
00132  * DEPRECATED and will be removed from this class in
00133  * a future version of ACE.  Please migrate your code
00134  * to the appropriate public methods indicated in the
00135  * method deprecation comments.
00136  * This class uses an <ACE_Allocator> to allocate memory.  The
00137  * user can make this a persistent class by providing an
00138  * <ACE_Allocator> with a persistable memory pool.
00139  *
00140  * <b> Requirements and Performance Characteristics</b>
00141  *   - Internal Structure:
00142  *       Binary tree
00143  *   - Duplicates allowed?
00144  *       No
00145  *   - Random access allowed?
00146  *       No
00147  *   - Search speed:
00148  *       Log(n)
00149  *   - Insert/replace speed:
00150  *       Log(n)
00151  *   - Iterator still valid after change to container?
00152  *       Yes, except if the iterated-over element is removed.
00153  *   - Frees memory for removed elements?
00154  *       Yes
00155  *   - Items inserted by:
00156  *       Value
00157  *   - Requirements for contained type
00158  *       -# Default constructor
00159  *       -# Copy constructor
00160  *       -# operator=
00161  *       -# operator==
00162  *       -# operator<
00163  */
00164 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00165 class ACE_RB_Tree : public ACE_RB_Tree_Base
00166 {
00167 
00168 public:
00169   friend class ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>;
00170   friend class ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>;
00171   friend class ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>;
00172 
00173   typedef EXT_ID KEY;
00174   typedef INT_ID VALUE;
00175   typedef ACE_RB_Tree_Node<EXT_ID, INT_ID> ENTRY;
00176 
00177   // = ACE-style iterator typedefs.
00178   typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ITERATOR;
00179   typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> REVERSE_ITERATOR;
00180 
00181   // = STL-style iterator typedefs.
00182   typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iterator;
00183   typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> reverse_iterator;
00184 
00185   // = Initialization and termination methods.
00186 
00187   /// Constructor.
00188   ACE_RB_Tree (ACE_Allocator *alloc = 0);
00189 
00190   /// Copy constructor.
00191   ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt);
00192 
00193   /// Initialize an RB Tree.
00194   int open (ACE_Allocator *alloc = 0);
00195 
00196   /// Close down an RB_Tree and release dynamically allocated
00197   /// resources.
00198   int close (void);
00199 
00200   /// Destructor.
00201   virtual ~ACE_RB_Tree (void);
00202 
00203   // = insertion, removal, and search methods.
00204 
00205   /**
00206    * Associate <ext_id> with <int_id>.  If <ext_id> is already in the
00207    * tree then the <ACE_RB_Tree_Node> is not changed.  Returns 0 if a
00208    * new entry is bound successfully, returns 1 if an attempt is made
00209    * to bind an existing entry, and returns -1 if failures occur.
00210    */
00211   int bind (const EXT_ID &item,
00212             const INT_ID &int_id);
00213 
00214   /**
00215    * Same as a normal bind, except the tree entry is also passed back
00216    * to the caller.  The entry in this case will either be the newly
00217    * created entry, or the existing one.
00218    */
00219   int bind (const EXT_ID &ext_id,
00220             const INT_ID &int_id,
00221             ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry);
00222 
00223 
00224   /**
00225    * Associate <ext_id> with <int_id> if and only if <ext_id> is not
00226    * in the tree.  If <ext_id> is already in the tree then the <int_id>
00227    * parameter is assigned the existing value in the tree.  Returns 0
00228    * if a new entry is bound successfully, returns 1 if an attempt is
00229    * made to bind an existing entry, and returns -1 if failures occur.
00230    */
00231   int trybind (const EXT_ID &ext_id,
00232                INT_ID &int_id);
00233 
00234   /**
00235    * Same as a normal trybind, except the tree entry is also passed
00236    * back to the caller.  The entry in this case will either be the
00237    * newly created entry, or the existing one.
00238    */
00239   int trybind (const EXT_ID &ext_id,
00240                INT_ID &int_id,
00241                ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry);
00242 
00243   /**
00244    * Reassociate <ext_id> with <int_id>.  If <ext_id> is not in the
00245    * tree then behaves just like <bind>.  Returns 0 if a new entry is
00246    * bound successfully, returns 1 if an existing entry was rebound,
00247    * and returns -1 if failures occur.
00248    */
00249   int rebind (const EXT_ID &ext_id,
00250               const INT_ID &int_id);
00251 
00252   /**
00253    * Same as a normal rebind, except the tree entry is also passed back
00254    * to the caller.  The entry in this case will either be the newly
00255    * created entry, or the existing one.
00256    */
00257   int rebind (const EXT_ID &ext_id,
00258               const INT_ID &int_id,
00259               ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry);
00260 
00261   /**
00262    * Associate <ext_id> with <int_id>.  If <ext_id> is not in the tree
00263    * then behaves just like <bind>.  Otherwise, store the old value of
00264    * <int_id> into the "out" parameter and rebind the new parameters.
00265    * Returns 0 if a new entry is bound successfully, returns 1 if an
00266    * existing entry was rebound, and returns -1 if failures occur.
00267    */
00268   int rebind (const EXT_ID &ext_id,
00269               const INT_ID &int_id,
00270               INT_ID &old_int_id);
00271 
00272   /**
00273    * Same as a normal rebind, except the tree entry is also passed back
00274    * to the caller.  The entry in this case will either be the newly
00275    * created entry, or the existing one.
00276    */
00277   int rebind (const EXT_ID &ext_id,
00278               const INT_ID &int_id,
00279               INT_ID &old_int_id,
00280               ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry);
00281 
00282   /**
00283    * Associate <ext_id> with <int_id>.  If <ext_id> is not in the tree
00284    * then behaves just like <bind>.  Otherwise, store the old values
00285    * of <ext_id> and <int_id> into the "out" parameters and rebind the
00286    * new parameters.  This is very useful if you need to have an
00287    * atomic way of updating <ACE_RB_Tree_Nodes> and you also need
00288    * full control over memory allocation.  Returns 0 if a new entry is
00289    * bound successfully, returns 1 if an existing entry was rebound,
00290    * and returns -1 if failures occur.
00291    */
00292   int rebind (const EXT_ID &ext_id,
00293               const INT_ID &int_id,
00294               EXT_ID &old_ext_id,
00295               INT_ID &old_int_id);
00296 
00297   /**
00298    * Same as a normal rebind, except the tree entry is also passed back
00299    * to the caller.  The entry in this case will either be the newly
00300    * created entry, or the existing one.
00301    */
00302   int rebind (const EXT_ID &ext_id,
00303               const INT_ID &int_id,
00304               EXT_ID &old_ext_id,
00305               INT_ID &old_int_id,
00306               ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry);
00307 
00308   /// Locate <ext_id> and pass out parameter via <int_id>.  If found,
00309   /// return 0, returns -1 if not found.
00310   int find (const EXT_ID &ext_id,
00311             INT_ID &int_id);
00312 
00313   /// Locate <ext_id> and pass out parameter via <entry>.  If found,
00314   /// return 0, returns -1 if not found.
00315   int find (const EXT_ID &ext_id,
00316             ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry);
00317 
00318   /**
00319    * Unbind (remove) the <ext_id> from the tree.  Don't return the
00320    * <int_id> to the caller (this is useful for collections where the
00321    * <int_id>s are *not* dynamically allocated...)
00322    */
00323   int unbind (const EXT_ID &ext_id);
00324 
00325   /// Break any association of <ext_id>.  Returns the value of <int_id>
00326   /// in case the caller needs to deallocate memory.
00327   int unbind (const EXT_ID &ext_id,
00328               INT_ID &int_id);
00329 
00330   /**
00331    * Remove entry from tree.  This method should be used with *extreme*
00332    * caution, and only for optimization purposes.  The node being passed
00333    * in had better have been allocated by the tree that is unbinding it.
00334    */
00335   int unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry);
00336 
00337   // = Public helper methods.
00338 
00339   /// Returns the current number of nodes in the tree.
00340   size_t current_size (void) const;
00341 
00342   /// Assignment operator.
00343   void operator= (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt);
00344 
00345   /// Less than comparison function for keys, using comparison functor.
00346   virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2);
00347 
00348   /**
00349    * Returns a reference to the underlying <ACE_LOCK>.  This makes it
00350    * possible to acquire the lock explicitly, which can be useful in
00351    * some cases if you instantiate the <ACE_Atomic_Op> with an
00352    * <ACE_Recursive_Mutex> or <ACE_Process_Mutex>, or if you need to
00353    * guard the state of an iterator.  NOTE: the right name would be
00354    * <lock>, but HP/C++ will choke on that!
00355    */
00356   ACE_LOCK &mutex (void);
00357 
00358   /// Dump the state of an object.
00359   void dump (void) const;
00360 
00361   // = STL styled iterator factory functions.
00362 
00363   /// Return forward iterator positioned at first node in tree.
00364   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> begin (void);
00365 
00366   /// Return forward iterator positioned at last node in tree.
00367   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> end (void);
00368 
00369   /// Return reverse iterator positioned at last node in tree.
00370   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rbegin (void);
00371 
00372   /// Return reverse iterator positioned at first node in tree.
00373   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rend (void);
00374 
00375   /// Recursively tests the invariant red-black properties at each
00376   /// node of the tree.  Returns 0 if invariant holds, else -1.
00377   /// This method is computationally expensive, and should only be
00378   /// called for testing purposes, and not in code that depends on the
00379   /// algorithmic complexity bounds provided by the other methods.
00380   int test_invariant (void);
00381 
00382   // = DEPRECATED methods.
00383   //   Please migrate your code to use the new methods instead
00384 
00385   /**
00386    * Returns a pointer to the item corresponding to the
00387    * given key, or 0 if it cannot find the key in the tree.
00388    *
00389    * @deprecated signature will change to become
00390    * int find (const EXT_ID &ext_id); which will return
00391    * 0 if the <ext_id> is in the tree, otherwise -1.
00392    */
00393   INT_ID* find (const EXT_ID &k);
00394 
00395   /**
00396    * Inserts a *copy* of the key and the item into the tree: both the
00397    * key type EXT_ID and the item type INT_ID must have well defined semantics
00398    * for copy construction.  The default implementation also requires that
00399    * the key type support well defined < semantics.  This method returns a
00400    * pointer to the inserted item copy, or 0 if an error occurred.
00401    * NOTE: if an identical key already exists in the tree, no new item
00402    * is created, and the returned pointer addresses the existing item
00403    * associated with the existing key.
00404    * @deprecated
00405    */
00406   INT_ID* insert (const EXT_ID &k, const INT_ID &t);
00407 
00408   /**
00409    * Removes the item associated with the given key from the tree and
00410    * destroys it.  Returns 1 if it found the item and successfully
00411    * destroyed it, 0 if it did not find the item, or -1 if an error
00412    * occurred.
00413    * @deprecated
00414    */
00415   int remove (const EXT_ID &k);
00416 
00417   /// @deprecated
00418   /// Destroys all nodes and sets the root pointer null.
00419   void clear (void);
00420 
00421 protected:
00422 
00423   // = Protected methods. These should only be called with locks held.
00424 
00425   /// Recursively tests the invariant red-black properties at each
00426   /// node of the tree.  Returns 0 if invariant holds, else -1.
00427   int test_invariant_recurse (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x,
00428                               int & expected_black_height,
00429                               int measured_black_height);
00430 
00431   /// Method for right rotation of the tree about a given node.
00432   void RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
00433 
00434   /// Method for left rotation of the tree about a given node.
00435   void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
00436 
00437   /// Method for restoring Red-Black properties after deletion.
00438   void RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x,
00439                         ACE_RB_Tree_Node<EXT_ID, INT_ID> * parent);
00440 
00441   /// Method to find the successor node of the given node in the tree.
00442   ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00443     RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
00444 
00445   /// Method to find the predecessor node of the given node in the
00446   /// tree.
00447   ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00448     RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
00449 
00450   /// Method to find the minimum node of the subtree rooted at the
00451   /// given node.
00452   ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00453     RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
00454 
00455   /// Method to find the maximum node of the subtree rooted at the
00456   /// given node.
00457   ACE_RB_Tree_Node<EXT_ID, INT_ID> *
00458     RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;
00459 
00460   /**
00461    * Returns a pointer to a matching node if there is one, a pointer
00462    * to the node under which to insert the item if the tree is not
00463    * empty and there is no such match, or 0 if the tree is empty.
00464    * It stores the result of the search in the result argument:
00465    * LEFT if the node is to the left of the node to be inserted,
00466    * RIGHT if the node is to the right of the node to be inserted,
00467    * or EXACT if an exactly matching node already exists.
00468    */
00469   ACE_RB_Tree_Node<EXT_ID, INT_ID> *find_node (const EXT_ID &k,
00470                                                ACE_RB_Tree_Base::RB_SearchResult &result);
00471 
00472   /// Rebalance the tree after insertion of a node.
00473   void RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
00474 
00475   /// Close down an RB_Tree.  this method should
00476   /// only be called with locks already held.
00477   int close_i (void);
00478 
00479   /**
00480    * Retrieves a pointer to the item corresponding to the
00481    * given key. If find_exact==1, find the exact match node. Otherwise just find a match node
00482    * returns 0 for success, or -1 if it cannot find the key in the tree.
00483    */
00484   int find_i (const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID>* &entry, int find_exact = 1);
00485 
00486   /**
00487    * Inserts a *copy* of the key and the item into the tree: both the
00488    * key type EXT_ID and the item type INT_ID must have well defined semantics
00489    * for copy construction.  The default implementation also requires that
00490    * the key type support well defined < semantics.  This method returns a
00491    * pointer to the inserted item copy, or 0 if an error occurred.
00492    * NOTE: if an identical key already exists in the tree, no new item
00493    * is created, and the returned pointer addresses the existing item
00494    * associated with the existing key.
00495    */
00496   INT_ID* insert_i (const EXT_ID &k, const INT_ID &t);
00497 
00498   /**
00499    * Inserts a *copy* of the key and the item into the tree: both the
00500    * key type EXT_ID and the item type INT_ID must have well defined semantics
00501    * for copy construction.  The default implementation also requires that
00502    * the key type support well defined < semantics.  This method passes back
00503    * a pointer to the inserted (or existing) node, and the search status.  If
00504    * the node already exists, the method returns 1.  If the node does not
00505    * exist, and a new one is successfully created, and the method returns 0.
00506    * If there was an error, the method returns -1.
00507    */
00508   int insert_i (const EXT_ID &k, const INT_ID &t,
00509                 ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry);
00510 
00511   /**
00512    * Removes the item associated with the given key from the tree and
00513    * destroys it.  Returns 1 if it found the item and successfully
00514    * destroyed it, 0 if it did not find the item, or -1 if an error
00515    * occurred.  Returns the stored internal id in the second argument.
00516    */
00517   int remove_i (const EXT_ID &k, INT_ID &i);
00518 
00519   /// Removes the item associated with the given key from the tree and
00520   /// destroys it.
00521   int remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z);
00522 
00523   /// Recursive function to dump the state of an object.
00524   void dump_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *node) const;
00525 
00526   /// Function to dump node contents.   Does nothing in its
00527   /// basic form, but template specialization can be used to
00528   /// provide definitions for various EXT_ID and INT_ID types.
00529   void dump_node_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> &node) const;
00530 
00531 private:
00532 
00533   // = Private members.
00534 
00535   /// Pointer to a memory allocator.
00536   ACE_Allocator *allocator_;
00537 
00538   /// Synchronization variable for the MT_SAFE <ACE_RB_Tree>.
00539   ACE_LOCK lock_;
00540 
00541   /// The root of the tree.
00542   ACE_RB_Tree_Node<EXT_ID, INT_ID> *root_;
00543 
00544   /// Comparison functor for comparing nodes in the tree.
00545   COMPARE_KEYS compare_keys_;
00546 
00547   /// The current number of nodes in the tree.
00548   size_t current_size_;
00549 };
00550 
00551 /**
00552  * @class ACE_RB_Tree_Iterator_Base
00553  *
00554  * @brief Implements a common base class for iterators for a Red-Black Tree ADT.
00555  */
00556 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00557 class ACE_RB_Tree_Iterator_Base
00558 {
00559 
00560 public:
00561 
00562   /// Assignment operator: copies both the tree reference and the position in the tree.
00563   void operator= (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &iter);
00564 
00565   // = Iteration methods.
00566 
00567   /// Returns 1 when the iteration has completed, otherwise 0.
00568   int done (void) const;
00569 
00570   /// STL-like iterator dereference operator: returns a reference
00571   /// to the node underneath the iterator.
00572   ACE_RB_Tree_Node<EXT_ID, INT_ID> & operator* (void) const;
00573 
00574   /// Returns a const reference to the tree over which we're iterating.
00575   const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree (void);
00576 
00577   /// Comparison operator: returns 1 if both iterators point to the same position, otherwise 0.
00578   int operator== (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &) const;
00579 
00580   /// Comparison operator: returns 1 if the iterators point to different positions, otherwise 0.
00581   int operator!= (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &) const;
00582 
00583   /// Declare the dynamic allocation hooks.
00584   ACE_ALLOC_HOOK_DECLARE;
00585 
00586 protected:
00587 
00588   // = Initialization and termination methods.
00589 
00590   /// Create the singular iterator.  No valid iterator can be equal to
00591   /// it, it is illegal to dereference a singular iterator, etc. etc.
00592   ACE_RB_Tree_Iterator_Base (void);
00593 
00594   /**
00595    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and
00596    * an integer indicating (if non-zero) to position the iterator
00597    * at the first element in the tree (if this integer is 0, the
00598    * iterator is positioned at the last element in the tree).
00599    */
00600   ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
00601                              int set_first);
00602 
00603   /**
00604    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and
00605    * a pointer to a node in the tree.
00606    */
00607   ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
00608                              ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry);
00609 
00610   /**
00611    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and a key.
00612    * The key must come first to distinguish the case of EXT_ID == int.
00613    */
00614   ACE_RB_Tree_Iterator_Base (const EXT_ID& key,
00615                              ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS,ACE_LOCK> &tree);
00616 
00617   /// Copy constructor.
00618   ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &iter);
00619 
00620   /// Destructor.
00621   ~ACE_RB_Tree_Iterator_Base (void);
00622 
00623   // = Internal methods
00624 
00625   /// Move forward by one element in the tree.  Returns 0 when
00626   /// there are no more elements in the tree, otherwise 1.
00627   int forward_i (void);
00628 
00629   /// Move back by one element in the tree.  Returns 0 when
00630   /// there are no more elements in the tree, otherwise 1.
00631   int reverse_i (void);
00632 
00633   /// Dump the state of an object.
00634   void dump_i (void) const;
00635 
00636   // = Protected members.
00637 
00638   /// Reference to the ACE_RB_Tree over which we're iterating.
00639   const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> *tree_;
00640 
00641   /// Pointer to the node currently under the iterator.
00642   ACE_RB_Tree_Node <EXT_ID, INT_ID> *node_;
00643 
00644 };
00645 
00646 /**
00647  * @class ACE_RB_Tree_Iterator
00648  *
00649  * @brief Implements an iterator for a Red-Black Tree ADT.
00650  */
00651 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00652 class ACE_RB_Tree_Iterator : public ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
00653 {
00654 
00655 public:
00656 
00657   // = Initialization and termination methods.
00658   /**
00659    * Create the singular iterator.
00660    * It is illegal to deference the iterator, no valid iterator is
00661    * equal to a singular iterator, etc. etc.
00662    */
00663   ACE_RB_Tree_Iterator (void);
00664 
00665   /**
00666    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and
00667    * an integer indicating (if non-zero) to position the iterator
00668    * at the first element in the tree (if this integer is 0, the
00669    * iterator is positioned at the last element in the tree).
00670    */
00671   ACE_RB_Tree_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
00672                         int set_first = 1);
00673   /**
00674    * Constructor.  Takes an ACE_RB_Tree over which to iterate
00675    * and a pointer to a node in the tree.
00676    */
00677   ACE_RB_Tree_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
00678                         ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry);
00679 
00680    /**
00681    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and a key;
00682    * the key comes first in order to distinguish the case of EXT_ID == int.
00683    */
00684   ACE_RB_Tree_Iterator (const EXT_ID &key,
00685                         ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree);
00686 
00687   /// Destructor.
00688   ~ACE_RB_Tree_Iterator (void);
00689 
00690   // = ACE-style iteration methods.
00691 
00692   /// Move forward by one element in the tree.  Returns
00693   /// 0 when all elements have been seen, else 1.
00694   int advance (void);
00695 
00696   /// Dump the state of an object.
00697   void dump (void) const;
00698 
00699   // = STL-style iteration methods.
00700 
00701   /// Prefix advance.
00702   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> & operator++ (void);
00703 
00704   /// Postfix advance.
00705   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator++ (int);
00706 
00707   /// Prefix reverse.
00708   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> & operator-- (void);
00709 
00710   /// Postfix reverse.
00711   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator-- (int);
00712 
00713   /// Declare the dynamic allocation hooks.
00714   ACE_ALLOC_HOOK_DECLARE;
00715 
00716   /**
00717    * Passes back the <entry> under the iterator.  Returns 0 if
00718    * the iteration has completed, otherwise 1.  This method must
00719    * be declared and defined in both the derived forward and
00720    * reverse iterator classes rather than in the base iterator
00721    * class because of a method signature resolution problem
00722    * caused by the existence of the deprecated next (void)
00723    * method in the derived forward iterator class.  When that
00724    * deprecated method is removed, this method should be removed
00725    * from the derived classes and placed in the base class.
00726    */
00727   int next (ACE_RB_Tree_Node<EXT_ID, INT_ID> *&next_entry) const;
00728 
00729   // = DEPRECATED methods.  Please migrate your code to use the new methods instead
00730 
00731   /// @deprecated
00732   /// Accessor for key of node under iterator (if any).
00733   EXT_ID *key (void);
00734 
00735   /// @deprecated
00736   /// Accessor for item of node under iterator (if any).
00737   INT_ID *item (void);
00738 
00739   /// @deprecated
00740   /// Move to the first item in the iteration (and in the tree).
00741   int first (void);
00742 
00743   /// @deprecated
00744   /// Move to the last item in the iteration (and in the tree).
00745   int last (void);
00746 
00747   /// @deprecated
00748   /// Move to the next item in the iteration (and in the tree).
00749   int next (void);
00750 
00751   /// @deprecated
00752   /// Move to the previous item in the iteration (and in the tree).
00753   int previous (void);
00754 
00755   /**
00756    * @deprecated: use the base class <done> method instead.
00757    * Returns 0 if the iterator is positioned over a valid ACE_RB_Tree
00758    * node, returns 1 if not.
00759    */
00760   int is_done (void);
00761 
00762 };
00763 
00764 /**
00765  * @class ACE_RB_Tree_Reverse_Iterator
00766  *
00767  * @brief Implements a reverse iterator for a Red-Black Tree ADT.
00768  */
00769 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
00770 class ACE_RB_Tree_Reverse_Iterator : public ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>
00771 {
00772 
00773 public:
00774 
00775   // = Initialization and termination methods.
00776   /**
00777    * Create the singular iterator.
00778    * It is illegal to deference the iterator, no valid iterator is
00779    * equal to a singular iterator, etc. etc.
00780    */
00781   ACE_RB_Tree_Reverse_Iterator (void);
00782 
00783   /**
00784    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and
00785    * an integer indicating (if non-zero) to position the iterator
00786    * at the last element in the tree (if this integer is 0, the
00787    * iterator is positioned at the first element in the tree).
00788    */
00789   ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
00790                                 int set_last = 1);
00791 
00792   /**
00793    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and 
00794    * a point to a node in the tree.
00795    */  
00796   ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree,
00797                                 ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry);
00798 
00799   /**
00800    * Constructor.  Takes an ACE_RB_Tree over which to iterate, and a key;
00801    * the key comes first in order to distinguish the case of EXT_ID == int.
00802    */
00803   ACE_RB_Tree_Reverse_Iterator (const EXT_ID &key,
00804                                 ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree);
00805 
00806   /// Destructor.
00807   ~ACE_RB_Tree_Reverse_Iterator (void);
00808 
00809   // = ACE-style iteration methods.
00810 
00811   /// Move forward by one element in the tree.  Returns
00812   /// 0 when all elements have been seen, else 1.
00813   int advance (void);
00814 
00815   /// Dump the state of an object.
00816   void dump (void) const;
00817 
00818   // = STL-style iteration methods.
00819 
00820   /// Prefix advance.
00821   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> & operator++ (void);
00822 
00823   /// Postfix advance.
00824   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator++ (int);
00825 
00826   /// Prefix reverse.
00827   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> & operator-- (void);
00828 
00829   /// Postfix reverse.
00830   ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> operator-- (int);
00831 
00832   /// Declare the dynamic allocation hooks.
00833   ACE_ALLOC_HOOK_DECLARE;
00834 
00835   /**
00836    * Passes back the <entry> under the iterator.  Returns 0 if
00837    * the iteration has completed, otherwise 1.  This method must
00838    * be declared and defined in both the derived forward and
00839    * reverse iterator classes rather than in the base iterator
00840    * class because of a method signature resolution problem
00841    * caused by the existence of the deprecated next (void)
00842    * method in the derived forward iterator class.  When that
00843    * deprecated method is removed, this method should be removed
00844    * from the derived classes and placed in the base class.
00845    */
00846   int next (ACE_RB_Tree_Node<EXT_ID, INT_ID> *&next_entry) const;
00847 
00848 };
00849 
00850 #if defined (__ACE_INLINE__)
00851 #include "ace/RB_Tree.i"
00852 #endif /* __ACE_INLINE__ */
00853 
00854 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
00855 #include "ace/RB_Tree.cpp"
00856 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
00857 
00858 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
00859 #pragma implementation ("RB_Tree.cpp")
00860 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
00861 
00862 #include "ace/post.h"
00863 #endif /* ! defined (ACE_RB_TREE_H) */

Generated on Mon Jun 16 11:20:59 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002