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

Containers_T.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 //=============================================================================
00004 /**
00005  *  @file    Containers_T.h
00006  *
00007  *  $Id: Containers_T.h,v 1.1.1.4 2003/02/21 18:36:32 chad Exp $
00008  *
00009  *  @author Douglas C. Schmidt <schmidt@cs.wustl.edu>
00010  */
00011 //=============================================================================
00012 
00013 #ifndef ACE_CONTAINERS_T_H
00014 #define ACE_CONTAINERS_T_H
00015 
00016 #include "ace/pre.h"
00017 
00018 #include "ace/config-all.h"
00019 
00020 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00021 # pragma once
00022 #endif /* ACE_LACKS_PRAGMA_ONCE */
00023 
00024 // Need by ACE_DLList_Node.
00025 #include "ace/Containers.h"
00026 
00027 // Shared with "ace/Unbounded_Set.h"
00028 #include "ace/Node.h"
00029 
00030 // Backwards compatibility, please include "ace/Array_Base.h" directly.
00031 #include "ace/Array_Base.h"
00032 
00033 // Backwards compatibility, please include "ace/Unbounded_Set.h" directly.
00034 #include "ace/Unbounded_Set.h"
00035 
00036 // Backwards compatibility, please include "ace/Unbounded_Queue.h" directly.
00037 #include "ace/Unbounded_Queue.h"
00038 
00039 class ACE_Allocator;
00040 
00041 
00042 /**
00043  * @class ACE_Bounded_Stack
00044  *
00045  * @brief Implement a generic LIFO abstract data type.
00046  *
00047  * This implementation of a Stack uses a bounded array
00048  * that is allocated dynamically.  The Stack interface
00049  * provides the standard constant time push, pop, and top
00050  * operations.
00051  *
00052  * <b> Requirements and Performance Characteristics</b>
00053  *   - Internal Structure
00054  *       Dynamic array
00055  *   - Duplicates allowed?
00056  *       Yes
00057  *   - Random access allowed?
00058  *       No
00059  *   - Search speed
00060  *       N/A
00061  *   - Insert/replace speed
00062  *       N/A
00063  *   - Iterator still valid after change to container?
00064  *       N/A
00065  *   - Frees memory for removed elements?
00066  *       No
00067  *   - Items inserted by
00068  *       Value
00069  *   - Requirements for contained type
00070  *       -# Default constructor
00071  *       -# Copy constructor
00072  *       -# operator=
00073  *
00074  */
00075 template <class T>
00076 class ACE_Bounded_Stack
00077 {
00078 public:
00079   // = Initialization, assignment, and termination methods.
00080 
00081   /// Initialize a new empty stack with the provided size..
00082   /**
00083    * Initialize and allocate space for a new Bounded_Stack with the provided
00084    * size.
00085    */
00086   ACE_Bounded_Stack (size_t size);
00087 
00088   /// Initialize the stack to be a copy of the stack provided.
00089   /**
00090    * Initialize the stack to be an exact copy of the Bounded_Stack provided
00091    * as a parameter.
00092    */
00093   ACE_Bounded_Stack (const ACE_Bounded_Stack<T> &s);
00094 
00095   /// Assignment operator
00096   /**
00097    * Perform a deep copy operation using the Bounded_Stack parameter.  If the
00098    * capacity of the lhs isn't sufficient for the rhs, then the underlying data
00099    * structure will be reallocated to accomadate the larger number of elements.
00100    */
00101   void operator= (const ACE_Bounded_Stack<T> &s);
00102 
00103   /// Perform actions needed when stack goes out of scope.
00104   /**
00105    * Deallocate the memory used by the Bounded_Stack.
00106    */
00107   ~ACE_Bounded_Stack (void);
00108 
00109   // = Classic Stack operations.
00110 
00111   ///Add an element to the top of the stack.
00112   /**
00113    * Place a new item on top of the stack.  Returns -1 if the stack
00114    * is already full, 0 if the stack is not already full, and -1 if
00115    * failure occurs.
00116    */
00117   int push (const T &new_item);
00118 
00119   ///Remove an item from the top of stack.
00120   /**
00121    * Remove and return the top stack item.  Returns -1 if the stack is
00122    * already empty, 0 if the stack is not already empty, and -1 if
00123    * failure occurs.
00124    */
00125   int pop (T &item);
00126 
00127   ///Examine the contents of the top of stack.
00128   /**
00129    * Return top stack item without removing it.  Returns -1 if the
00130    * stack is already empty, 0 if the stack is not already empty, and
00131    * -1 if failure occurs.
00132    */
00133   int top (T &item) const;
00134 
00135   // = Check boundary conditions.
00136 
00137   /// Returns 1 if the container is empty, otherwise returns 0.
00138   /**
00139    * Performs constant time check to determine if the stack is empty.
00140    */
00141   int is_empty (void) const;
00142 
00143   /// Returns 1 if the container is full, otherwise returns 0.
00144   /**
00145    * Performs constant time check to determine if the stack is at capacity.
00146    */
00147   int is_full (void) const;
00148 
00149   /// The number of items in the stack.
00150   /**
00151    * Return the number of items currently in the stack.
00152    */
00153   size_t size (void) const;
00154 
00155   /// Dump the state of an object.
00156   void dump (void) const;
00157 
00158   /// Declare the dynamic allocation hooks.
00159   ACE_ALLOC_HOOK_DECLARE;
00160 
00161 private:
00162   /// Size of the dynamically allocated data.
00163   size_t size_;
00164 
00165   /// Keeps track of the current top of stack.
00166   size_t top_;
00167 
00168   /// Holds the stack's contents.
00169   T *stack_;
00170 };
00171 
00172 //----------------------------------------
00173 
00174 
00175 /**
00176  * @class ACE_Fixed_Stack
00177  *
00178  * @brief Implement a generic LIFO abstract data type.
00179  *
00180  * This implementation of a Stack uses a fixed array
00181  * with the size fixed at instantiation time.
00182  *
00183  * <b> Requirements and Performance Characteristics</b>
00184  *   - Internal Structure
00185  *       Fixed array
00186  *   - Duplicates allowed?
00187  *       Yes
00188  *   - Random access allowed?
00189  *       No
00190  *   - Search speed
00191  *       N/A
00192  *   - Insert/replace speed
00193  *       N/A
00194  *   - Iterator still valid after change to container?
00195  *       N/A
00196  *   - Frees memory for removed elements?
00197  *       No
00198  *   - Items inserted by
00199  *       Value
00200  *   - Requirements for contained type
00201  *       -# Default constructor
00202  *       -# Copy constructor
00203  *       -# operator=
00204  *
00205  */
00206 template <class T, size_t ACE_SIZE>
00207 class ACE_Fixed_Stack
00208 {
00209 public:
00210   // = Initialization, assignment, and termination methods.
00211   /// Initialize a new stack so that it is empty.
00212   /**
00213    * Initialize an empty stack.
00214    */
00215   ACE_Fixed_Stack (void);
00216 
00217   /// The copy constructor (performs initialization).
00218   /**
00219    * Initialize the stack and copy the provided stack into the current stack.
00220    */
00221   ACE_Fixed_Stack (const ACE_Fixed_Stack<T, ACE_SIZE> &s);
00222 
00223   /// Assignment operator (performs assignment).
00224   /**
00225    * Perform a deep copy of the provided stack.
00226    */
00227   void operator= (const ACE_Fixed_Stack<T, ACE_SIZE> &s);
00228 
00229   /// Perform actions needed when stack goes out of scope.
00230   /**
00231    * Destroy the stack.
00232    */
00233   ~ACE_Fixed_Stack (void);
00234 
00235   // = Classic Stack operations.
00236 
00237   ///Constant time placement of element on top of stack.
00238   /**
00239    * Place a new item on top of the stack.  Returns -1 if the stack
00240    * is already full, 0 if the stack is not already full, and -1 if
00241    * failure occurs.
00242    */
00243   int push (const T &new_item);
00244 
00245   ///Constant time removal of top of stack.
00246   /**
00247    * Remove and return the top stack item.  Returns -1 if the stack is
00248    * already empty, 0 if the stack is not already empty, and -1 if
00249    * failure occurs.
00250    */
00251   int pop (T &item);
00252 
00253   ///Constant time examination of top of stack.
00254   /**
00255    * Return top stack item without removing it.  Returns -1 if the
00256    * stack is already empty, 0 if the stack is not already empty, and
00257    * -1 if failure occurs.
00258    */
00259   int top (T &item) const;
00260 
00261   // = Check boundary conditions.
00262 
00263   /// Returns 1 if the container is empty, otherwise returns 0.
00264   /**
00265    * Performs constant time check to see if stack is empty.
00266    */
00267   int is_empty (void) const;
00268 
00269   /// Returns 1 if the container is full, otherwise returns 0.
00270   /**
00271    * Performs constant time check to see if stack is full.
00272    */
00273   int is_full (void) const;
00274 
00275   /// The number of items in the stack.
00276   /**
00277    * Constant time access to the current size of the stack.
00278    */
00279   size_t size (void) const;
00280 
00281   /// Dump the state of an object.
00282   void dump (void) const;
00283 
00284   /// Declare the dynamic allocation hooks.
00285   ACE_ALLOC_HOOK_DECLARE;
00286 
00287 private:
00288   /// Size of the allocated data.
00289   size_t size_;
00290 
00291   /// Keeps track of the current top of stack.
00292   size_t top_;
00293 
00294   /// Holds the stack's contents.
00295   T stack_[ACE_SIZE];
00296 };
00297 
00298 //----------------------------------------
00299 
00300 template<class T> class ACE_Ordered_MultiSet;
00301 template<class T> class ACE_Ordered_MultiSet_Iterator;
00302 
00303 /**
00304  * @class ACE_DNode
00305  *
00306  * @brief Implementation element in a bilinked list.
00307  */
00308 template<class T>
00309 class ACE_DNode
00310 {
00311   friend class ACE_Ordered_MultiSet<T>;
00312   friend class ACE_Ordered_MultiSet_Iterator<T>;
00313 
00314 public:
00315 
00316 # if ! defined (ACE_HAS_BROKEN_NOOP_DTORS)
00317   /// This isn't necessary, but it keeps some compilers happy.
00318   ~ACE_DNode (void);
00319 # endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */
00320 
00321 private:
00322 
00323   // = Initialization methods
00324   ACE_DNode (const T &i, ACE_DNode<T> *n = 0, ACE_DNode<T> *p = 0);
00325 
00326   /// Pointer to next element in the list of <ACE_DNode>s.
00327   ACE_DNode<T> *next_;
00328 
00329   /// Pointer to previous element in the list of <ACE_DNode>s.
00330   ACE_DNode<T> *prev_;
00331 
00332   /// Current value of the item in this node.
00333   T item_;
00334 };
00335 
00336 
00337 
00338 /**
00339  * @class ACE_Unbounded_Stack
00340  *
00341  * @brief Implement a generic LIFO abstract data type.
00342  *
00343  * This implementation of an unbounded Stack uses a linked list.
00344  * If you use the <insert> or <remove> methods you should keep
00345  * in mind that duplicate entries aren't allowed.  In general,
00346  * therefore, you should avoid the use of these methods since
00347  * they aren't really part of the ADT stack.  The stack is implemented
00348  * as a doubly linked list.
00349  *
00350  * <b> Requirements and Performance Characteristics</b>
00351  *   - Internal Structure
00352  *       Double linked list
00353  *   - Duplicates allowed?
00354  *       No
00355  *   - Random access allowed?
00356  *       No
00357  *   - Search speed
00358  *       Linear
00359  *   - Insert/replace speed
00360  *       Linear
00361  *   - Iterator still valid after change to container?
00362  *       Yes
00363  *   - Frees memory for removed elements?
00364  *       Yes
00365  *   - Items inserted by
00366  *       Value
00367  *   - Requirements for contained type
00368  *       -# Default constructor
00369  *       -# Copy constructor
00370  *       -# operator=
00371  *
00372  */
00373 template <class T>
00374 class ACE_Unbounded_Stack
00375 {
00376 public:
00377   friend class ACE_Unbounded_Stack_Iterator<T>;
00378 
00379   // Trait definition.
00380   typedef ACE_Unbounded_Stack_Iterator<T> ITERATOR;
00381 
00382   // = Initialization, assignment, and termination methods.
00383   /// Initialize a new stack so that it is empty.  Use user defined
00384   /// allocation strategy if specified.
00385   /**
00386    * Initialize an empty stack using the user specified allocation strategy
00387    * if provided.
00388    */
00389   ACE_Unbounded_Stack (ACE_Allocator *alloc = 0);
00390 
00391   /// The copy constructor (performs initialization).
00392   /**
00393    * Initialize this stack to be an exact copy of <s>.
00394    */
00395   ACE_Unbounded_Stack (const ACE_Unbounded_Stack<T> &s);
00396 
00397   /// Assignment operator (performs assignment).
00398   /**
00399    * Perform a deep copy of the rhs into the lhs.
00400    */
00401   void operator= (const ACE_Unbounded_Stack<T> &s);
00402 
00403   /// Perform actions needed when stack goes out of scope.
00404   /**
00405    * Destroy the underlying list for the stack.
00406    */
00407   ~ACE_Unbounded_Stack (void);
00408 
00409   // = Classic Stack operations.
00410 
00411 
00412   ///Push an element onto the top of stack.
00413   /**
00414    * Place a new item on top of the stack.  Returns -1 if the stack
00415    * is already full, 0 if the stack is not already full, and -1 if
00416    * failure occurs.
00417    */
00418   int push (const T &new_item);
00419 
00420   ///Pop the top element of the stack.
00421   /**
00422    * Remove and return the top stack item.  Returns -1 if the stack is
00423    * already empty, 0 if the stack is not already empty, and -1 if
00424    * failure occurs.
00425    */
00426   int pop (T &item);
00427 
00428   ///Examine the top of the stack.
00429   /**
00430    * Return top stack item without removing it.  Returns -1 if the
00431    * stack is already empty, 0 if the stack is not already empty, and
00432    * -1 if failure occurs.
00433    */
00434   int top (T &item) const;
00435 
00436   // = Check boundary conditions.
00437 
00438   /// Returns 1 if the container is empty, otherwise returns 0.
00439   /**
00440    * Constant time check to see if the stack is empty.
00441    */
00442   int is_empty (void) const;
00443 
00444   /// Returns 1 if the container is full, otherwise returns 0.
00445   /**
00446    * Always resturns 0 since the stack is unbounded.
00447    */
00448   int is_full (void) const;
00449 
00450   // = Auxiliary methods (not strictly part of the Stack ADT).
00451 
00452   ///Linear Insert of an item.
00453   /**
00454    * Insert <new_item> into the Stack at the head (but doesn't allow
00455    * duplicates).  Returns -1 if failures occur, 1 if item is already
00456    * present (i.e., no duplicates are allowed), else 0.
00457    */
00458   int insert (const T &new_item);
00459 
00460   /// Remove @a item from the Stack.  Returns 0 if it removes the item,
00461   /// -1 if it can't find the item, and -1 if a failure occurs.
00462   /**
00463    * Linear remove operation.
00464    */
00465   int remove (const T &item);
00466 
00467   /// Finds if @a item occurs the set.  Returns 0 if finds, else -1.
00468   /**
00469    * Linear find operation.
00470    */
00471   int find (const T &item) const;
00472 
00473   /// The number of items in the stack.
00474   /**
00475    * Constant time access to the current stack size.
00476    */
00477   size_t size (void) const;
00478 
00479   /// Dump the state of an object.
00480   void dump (void) const;
00481 
00482   /// Declare the dynamic allocation hooks.
00483   ACE_ALLOC_HOOK_DECLARE;
00484 
00485 private:
00486   /// Delete all the nodes in the stack.
00487   void delete_all_nodes (void);
00488 
00489   /// Copy all nodes from <s> to <this>.
00490   void copy_all_nodes (const ACE_Unbounded_Stack<T> &s);
00491 
00492   /// Head of the linked list of Nodes.
00493   ACE_Node<T> *head_;
00494 
00495   /// Current size of the stack.
00496   size_t cur_size_;
00497 
00498   /// Allocation strategy of the stack.
00499   ACE_Allocator *allocator_;
00500 };
00501 
00502 /**
00503  * @class ACE_Unbounded_Stack_Iterator
00504  *
00505  * @brief Implement an iterator over an unbounded Stack.
00506  */
00507 template <class T>
00508 class ACE_Unbounded_Stack_Iterator
00509 {
00510 public:
00511   // = Initialization method.
00512   /// Move to the first element in the <stack>.
00513   ACE_Unbounded_Stack_Iterator (ACE_Unbounded_Stack<T> &stack);
00514 
00515   // = Iteration methods.
00516 
00517   /// Pass back the @a next_item that hasn't been seen in the Stack.
00518   /// Returns 0 when all items have been seen, else 1.
00519   int next (T *&next_item);
00520 
00521   /// Move forward by one element in the Stack.  Returns 0 when all the
00522   /// items in the Stack have been seen, else 1.
00523   int advance (void);
00524 
00525   /// Move to the first element in the Stack.  Returns 0 if the
00526   /// Stack is empty, else 1.
00527   int first (void);
00528 
00529   /// Returns 1 when all items have been seen, else 0.
00530   int done (void) const;
00531 
00532   /// Dump the state of an object.
00533   void dump (void) const;
00534 
00535   /// Declare the dynamic allocation hooks.
00536   ACE_ALLOC_HOOK_DECLARE;
00537 
00538 private:
00539   /// Pointer to the current node in the iteration.
00540   ACE_Node<T> *current_;
00541 
00542   /// Pointer to the Stack we're iterating over.
00543   ACE_Unbounded_Stack<T> &stack_;
00544 };
00545 
00546 template <class T>
00547 class ACE_Double_Linked_List;
00548 
00549 /**
00550  * @class ACE_Double_Linked_List_Iterator_Base
00551  *
00552  * @brief Implements a common base class for iterators for a double
00553  * linked list ADT
00554  */
00555 template <class T>
00556 class ACE_Double_Linked_List_Iterator_Base
00557 {
00558 public:
00559   // = Iteration methods.
00560 
00561   /// Passes back the <entry> under the iterator. Returns 0 if the
00562   /// iteration has completed, otherwise 1
00563   int next (T *&) const;
00564 
00565   /**
00566    * @deprecated Return the address of next (current) unvisited item in
00567    * the list. 0 if there is no more element available.
00568    */
00569   T *next (void) const;
00570 
00571   /// Returns 1 when all items have been seen, else 0.
00572   int done (void) const;
00573 
00574   /// STL-like iterator dereference operator: returns a reference
00575   /// to the node underneath the iterator.
00576   T & operator* (void) const ;
00577 
00578   /**
00579    * Retasks the iterator to iterate over a new
00580    * Double_Linked_List. This allows clients to reuse an iterator
00581    * without incurring the constructor overhead. If you do use this,
00582    * be aware that if there are more than one reference to this
00583    * iterator, the other "clients" may be very bothered when their
00584    * iterator changes.  @@ Here be dragons. Comments?
00585    */
00586   void reset (ACE_Double_Linked_List<T> &);
00587 
00588   /// Declare the dynamic allocation hooks.
00589   ACE_ALLOC_HOOK_DECLARE;
00590 
00591 protected:
00592   // = Initialization methods.
00593 
00594   /// Constructor
00595   ACE_Double_Linked_List_Iterator_Base (const ACE_Double_Linked_List<T> &);
00596 
00597   /// Copy constructor.
00598   ACE_Double_Linked_List_Iterator_Base (const
00599                                         ACE_Double_Linked_List_Iterator_Base<T>
00600                                         &iter);
00601 
00602   // = Iteration methods.
00603   /**
00604    * Move to the first element of the list. Returns 0 if the list is
00605    * empty, else 1. Note: the head of the ACE_DLList is actually a
00606    * null entry, so the first element is actually the 2n'd entry
00607    */
00608   int go_head (void);
00609 
00610   /// Move to the last element of the list. Returns 0 if the list is
00611   /// empty, else 1.
00612   int go_tail (void);
00613 
00614   /**
00615    * Check if we reach the end of the list.  Can also be used to get
00616    * the *current* element in the list.  Return the address of the
00617    * current item if there are still elements left , 0 if we run out
00618    * of element.
00619    */
00620   T *not_done (void) const ;
00621 
00622   /// Advance to the next element in the list.  Return the address of the
00623   /// next element if there are more, 0 otherwise.
00624   T *do_advance (void);
00625 
00626   /// Retreat to the previous element in the list.  Return the address
00627   /// of the previous element if there are more, 0 otherwise.
00628   T *do_retreat (void);
00629 
00630   /// Dump the state of an object.
00631   void dump_i (void) const;
00632 
00633   /// Remember where we are.
00634   T *current_;
00635 
00636   const ACE_Double_Linked_List<T> *dllist_;
00637 };
00638 
00639 /**
00640  * @class ACE_Double_Linked_List_Iterator
00641  *
00642  * @brief Implements an iterator for a double linked list ADT
00643  *
00644  * Iterate thru the double-linked list.  This class provides
00645  * an interface that let users access the internal element
00646  * addresses directly. Notice <class T> must declare
00647  * ACE_Double_Linked_List<T>,
00648  * ACE_Double_Linked_List_Iterator_Base <T> and
00649  * ACE_Double_Linked_List_Iterator as friend classes and class T
00650  * should also have data members T* next_ and T* prev_.
00651  */
00652 template <class T>
00653 class ACE_Double_Linked_List_Iterator : public ACE_Double_Linked_List_Iterator_Base <T>
00654 {
00655 public:
00656   // = Initialization method.
00657   ACE_Double_Linked_List_Iterator (const ACE_Double_Linked_List<T> &);
00658 
00659   /**
00660    * Retasks the iterator to iterate over a new
00661    * Double_Linked_List. This allows clients to reuse an iterator
00662    * without incurring the constructor overhead. If you do use this,
00663    * be aware that if there are more than one reference to this
00664    * iterator, the other "clients" may be very bothered when their
00665    * iterator changes.
00666    * @@ Here be dragons. Comments?
00667    */
00668   void reset (ACE_Double_Linked_List<T> &);
00669 
00670   /// Move to the first element in the list.  Returns 0 if the
00671   /// list is empty, else 1.
00672   int first (void);
00673 
00674   /// Move forward by one element in the list.  Returns 0 when all the
00675   /// items in the list have been seen, else 1.
00676   int advance (void);
00677 
00678   /**
00679    * Advance the iterator while removing the original item from the
00680    * list.  Return a pointer points to the original (removed) item.
00681    * If <dont_remove> equals 0, this function behaves like <advance>
00682    * but return 0 (NULL) instead.
00683    */
00684   T* advance_and_remove (int dont_remove);
00685 
00686   // = STL-style iteration methods
00687 
00688   /// Prefix advance.
00689   ACE_Double_Linked_List_Iterator<T> & operator++ (void);
00690 
00691   /// Postfix advance.
00692   ACE_Double_Linked_List_Iterator<T> operator++ (int);
00693 
00694   /// Prefix reverse.
00695   ACE_Double_Linked_List_Iterator<T> & operator-- (void);
00696 
00697   /// Postfix reverse.
00698   ACE_Double_Linked_List_Iterator<T> operator-- (int);
00699 
00700   /// Dump the state of an object.
00701   void dump (void) const;
00702 
00703   /// Declare the dynamic allocation hooks.
00704   ACE_ALLOC_HOOK_DECLARE;
00705 };
00706 
00707 /**
00708  * @class ACE_Double_Linked_List_Reverse_Iterator
00709  *
00710  * @brief Implements a reverse iterator for a double linked list ADT
00711  *
00712  * Iterate backwards over the double-linked list.  This class
00713  * provide an interface that let users access the internal
00714  * element addresses directly, which seems to break the
00715  * encapsulation.  Notice <class T> must declare
00716  * ACE_Double_Linked_List<T>,
00717  * ACE_Double_Linked_List_Iterator_Base <T> and
00718  * ACE_Double_Linked_List_Iterator as friend classes and class T
00719  * should also have data members T* next_ and T* prev_.
00720  */
00721 template <class T>
00722 class ACE_Double_Linked_List_Reverse_Iterator : public ACE_Double_Linked_List_Iterator_Base <T>
00723 {
00724 public:
00725   // = Initialization method.
00726   ACE_Double_Linked_List_Reverse_Iterator (ACE_Double_Linked_List<T> &);
00727 
00728   /**
00729    * Retasks the iterator to iterate over a new
00730    * Double_Linked_List. This allows clients to reuse an iterator
00731    * without incurring the constructor overhead. If you do use this,
00732    * be aware that if there are more than one reference to this
00733    * iterator, the other "clients" may be very bothered when their
00734    * iterator changes.
00735    * @@ Here be dragons. Comments?
00736    */
00737   void reset (ACE_Double_Linked_List<T> &);
00738 
00739   /// Move to the first element in the list.  Returns 0 if the
00740   /// list is empty, else 1.
00741   int first (void);
00742 
00743   /// Move forward by one element in the list.  Returns 0 when all the
00744   /// items in the list have been seen, else 1.
00745   int advance (void);
00746 
00747   /**
00748    * Advance the iterator while removing the original item from the
00749    * list.  Return a pointer points to the original (removed) item.
00750    * If <dont_remove> equals 0, this function behaves like <advance>
00751    * but return 0 (NULL) instead.
00752    */
00753   T* advance_and_remove (int dont_remove);
00754 
00755   // = STL-style iteration methods
00756 
00757   /// Prefix advance.
00758   ACE_Double_Linked_List_Reverse_Iterator<T> & operator++ (void);
00759 
00760   /// Postfix advance.
00761   ACE_Double_Linked_List_Reverse_Iterator<T> operator++ (int);
00762 
00763   /// Prefix reverse.
00764   ACE_Double_Linked_List_Reverse_Iterator<T> & operator-- (void);
00765 
00766   /// Postfix reverse.
00767   ACE_Double_Linked_List_Reverse_Iterator<T> operator-- (int);
00768 
00769   /// Dump the state of an object.
00770   void dump (void) const;
00771 
00772   /// Declare the dynamic allocation hooks.
00773   ACE_ALLOC_HOOK_DECLARE;
00774 };
00775 
00776 
00777 /**
00778  * @class ACE_Double_Linked_List
00779  *
00780  * @brief A double-linked list implementation.
00781  *
00782  * This implementation of an unbounded double-linked list uses a
00783  * circular linked list with a dummy node.  It is pretty much
00784  * like the <ACE_Unbounded_Queue> except that it allows removing
00785  * of a specific element from a specific location.
00786  * Notice that this class is an implementation of a very simple
00787  * data structure. This is *NOT* a container class.  You can use the
00788  * class to implement other contains classes but it is *NOT* a
00789  * general purpose container class.
00790  * The parameter class *MUST* have members T* prev and T* next
00791  * and users of this class are responsible to follow the general
00792  * rules of using double-linked lists to maintaining the list
00793  * integrity.
00794  * If you need a double linked container class, use the DLList
00795  * class which is a container but delegates to the Double_Linked_List
00796  * class.
00797  *
00798  * <b> Requirements and Performance Characteristics</b>
00799  *   - Internal Structure
00800  *       Double Linked List
00801  *   - Duplicates allowed?
00802  *       Yes
00803  *   - Random access allowed?
00804  *       No
00805  *   - Search speed
00806  *       N/A
00807  *   - Insert/replace speed
00808  *       Linear
00809  *   - Iterator still valid after change to container?
00810  *       Yes
00811  *   - Frees memory for removed elements?
00812  *       No
00813  *   - Items inserted by
00814  *       Value
00815  *   - Requirements for contained type
00816  *       -# Default constructor
00817  *       -# Copy constructor
00818  *       -# operator=
00819  *
00820  */
00821 template <class T>
00822 class ACE_Double_Linked_List
00823 {
00824 public:
00825   friend class ACE_Double_Linked_List_Iterator_Base<T>;
00826   friend class ACE_Double_Linked_List_Iterator<T>;
00827   friend class ACE_Double_Linked_List_Reverse_Iterator<T>;
00828 
00829   // Trait definition.
00830   typedef ACE_Double_Linked_List_Iterator<T> ITERATOR;
00831   typedef ACE_Double_Linked_List_Reverse_Iterator<T> REVERSE_ITERATOR;
00832 
00833   // = Initialization and termination methods.
00834   /// construction.  Use user specified allocation strategy
00835   /// if specified.
00836   /**
00837    * Initialize an empy list using the allocation strategy specified by the user.
00838    * If none is specified, then use default allocation strategy.
00839    */
00840   ACE_Double_Linked_List (ACE_Allocator *alloc = 0);
00841 
00842   /// Copy constructor.
00843   /**
00844    * Create a double linked list that is a copy of the provided
00845    * parameter.
00846    */
00847   ACE_Double_Linked_List (const ACE_Double_Linked_List<T> &);
00848 
00849   /// Assignment operator.
00850   /**
00851    * Perform a deep copy of the provided list by first deleting the nodes of the
00852    * lhs and then copying the nodes of the rhs.
00853    */
00854   void operator= (const ACE_Double_Linked_List<T> &);
00855 
00856   /// Destructor.
00857   /**
00858    * Clean up the memory allocated for the nodes of the list.
00859    */
00860   ~ACE_Double_Linked_List (void);
00861 
00862   // = Check boundary conditions.
00863 
00864   /// Returns 1 if the container is empty, 0 otherwise.
00865   /**
00866    * Performs constant time check to determine if the list is empty.
00867    */
00868   int is_empty (void) const;
00869 
00870   /// The list is unbounded, so this always returns 0.
00871   /**
00872    * Since the list is unbounded, the method simply returns 0.
00873    */
00874   int is_full (void) const;
00875 
00876   // = Classic queue operations.
00877 
00878   /// Adds <new_item> to the tail of the list. Returns the new item
00879   /// that was inserted.
00880   /**
00881    * Provides constant time insertion at the end of the list structure.
00882    */
00883   T *insert_tail (T *new_item);
00884 
00885   /// Adds <new_item> to the head of the list.Returns the new item that
00886   /// was inserted.
00887   /**
00888    * Provides constant time insertion at the head of the list.
00889    */
00890   T *insert_head (T *new_item);
00891 
00892   ///Removes the head of the list and returns a pointer to that item.
00893   /**
00894    * Removes and returns the first <item> in the list.  Returns
00895    * internal node's address on success, 0 if the queue was empty.
00896    * This method will *not* free the internal node.
00897    */
00898   T* delete_head (void);
00899 
00900   ///Removes the tail of the list and returns a pointer to that item.
00901   /**
00902    * Removes and returns the last <item> in the list.  Returns
00903    * internal nodes's address on success, 0 if the queue was
00904    * empty. This method will *not* free the internal node.
00905    */
00906   T *delete_tail (void);
00907 
00908   // = Additional utility methods.
00909 
00910   ///Empty the list.
00911   /**
00912    * Reset the <ACE_Double_Linked_List> to be empty.
00913    * Notice that since no one is interested in the items within,
00914    * This operation will delete all items.
00915    */
00916   void reset (void);
00917 
00918   /// Get the <slot>th element in the set.  Returns -1 if the element
00919   /// isn't in the range {0..<size> - 1}, else 0.
00920   /**
00921    * Iterates through the list to the desired index and assigns the provides pointer
00922    * with the address of the node occupying that index.
00923    */
00924   int get (T *&item, size_t slot = 0);
00925 
00926   /// The number of items in the queue.
00927   /**
00928    * Constant time call to return the current size of the list.
00929    */
00930   size_t size (void) const;
00931 
00932   /// Dump the state of an object.
00933   void dump (void) const;
00934 
00935   /// Use DNode address directly.
00936   /**
00937    * Constant time removal of an item from the list using it's address.
00938    */
00939   int remove (T *n);
00940 
00941   /// Declare the dynamic allocation hooks.
00942   ACE_ALLOC_HOOK_DECLARE;
00943 
00944 protected:
00945   /// Delete all the nodes in the list.
00946   /**
00947    * Removes and deallocates memory for all of the list nodes.
00948    */
00949   void delete_nodes (void);
00950 
00951   /// Copy nodes from <rhs> into this list.
00952   /**
00953    * Copy the elements of the provided list by allocated new nodes and assigning
00954    * them with the proper data.
00955    */
00956   void copy_nodes (const ACE_Double_Linked_List<T> &rhs);
00957 
00958   /// Setup header pointer.  Called after we create the head node in ctor.
00959   /**
00960    * Initialize the head pointer so that the list has a dummy node.
00961    */
00962   void init_head (void);
00963 
00964   ///Constant time insert a new item into the list structure.
00965   /**
00966    * Insert a @a new_item into the list.  It will be added before
00967    * or after @a old_item.  Default is to insert the new item *after*
00968    * <head_>.  Return 0 if succeed, -1 if error occured.
00969    */
00970   int insert_element (T *new_item,
00971                       int before = 0,
00972                       T *old_item = 0);
00973 
00974   ///Constant time delete an item from the list structure.
00975   /**
00976    * Remove @a item from the list.  Return 0 if succeed, -1 otherwise.
00977    * Notice that this function checks if item is <head_> and either its
00978    * <next_> or <prev_> is NULL.  The function resets item's <next_> and
00979    * <prev_> to 0 to prevent clobbering the double-linked list if a user
00980    * tries to remove the same node again.
00981    */
00982   int remove_element (T *item);
00983 
00984   /// Head of the circular double-linked list.
00985   T *head_;
00986 
00987   /// Size of this list.
00988   size_t size_;
00989 
00990   /// Allocation Strategy of the queue.
00991   ACE_Allocator *allocator_;
00992 };
00993 
00994 
00995 template <class T> class ACE_DLList;
00996 template <class T> class ACE_DLList_Iterator;
00997 template <class T> class ACE_DLList_Reverse_Iterator;
00998 
00999 typedef ACE_Double_Linked_List<ACE_DLList_Node> ACE_DLList_Base;
01000 
01001 //typedef ACE_Double_Linked_List_Iterator <ACE_DLList_Node>
01002 //        ACE_DLList_Iterator_Base;
01003 //typedef ACE_Double_Linked_List_Reverse_Iterator <ACE_DLList_Node>
01004 //        ACE_DLList_Reverse_Iterator_Base;
01005 //@@ These two typedefs (inherited from James Hu's original design)
01006 // have been removed because Sun CC 4.2 had problems with it. I guess
01007 // having the DLList_Iterators inheriting from a class which is
01008 // actually a typedef leads to problems. #define'ing rather than
01009 // typedef'ing worked, but as per Carlos's reccomendation, I'm just
01010 // replacing all references to the base classes with their actual
01011 // type.  Matt Braun (6/15/99)
01012 
01013 /**
01014  * @class ACE_DLList
01015  *
01016  * @brief A double-linked list container class.
01017  *
01018  * This implementation uses ACE_Double_Linked_List to perform
01019  * the logic behind this container class.  It delegates all of its
01020  * calls to ACE_Double_Linked_List.
01021  */
01022 template <class T>
01023 class ACE_DLList : public ACE_DLList_Base
01024 {
01025   friend class ACE_DLList_Node;
01026   friend class ACE_Double_Linked_List_Iterator<T>;
01027   friend class ACE_DLList_Iterator<T>;
01028   friend class ACE_DLList_Reverse_Iterator<T>;
01029 
01030 public:
01031 
01032   /// Delegates to ACE_Double_Linked_List.
01033   void operator= (const ACE_DLList<T> &l);
01034 
01035   // = Classic queue operations.
01036 
01037   /// Delegates to ACE_Double_Linked_List.
01038   T *insert_tail (T *new_item);
01039 
01040   /// Delegates to ACE_Double_Linked_List.
01041   T *insert_head (T *new_item);
01042 
01043   /// Delegates to ACE_Double_Linked_List.
01044   T *delete_head (void);
01045 
01046   /// Delegates to ACE_Double_Linked_List.
01047   T *delete_tail (void);
01048 
01049   // = Additional utility methods.
01050 
01051   /**
01052    * Delegates to <ACE_Double_Linked_List>, but where
01053    * <ACE_Double_Linked_List> returns the node as the item, this get
01054    * returns the contents of the node in item.
01055    */
01056   int get (T *&item, size_t slot = 0);
01057 
01058   /// Delegates to ACE_Double_Linked_List.
01059   void dump (void) const;
01060 
01061   /// Delegates to ACE_Double_Linked_List.
01062   int remove (ACE_DLList_Node *n);
01063 
01064 
01065   // = Initialization and termination methods.
01066 
01067   /// Delegates to ACE_Double_Linked_List.
01068   ACE_DLList (ACE_Allocator *alloc = 0);
01069 
01070   /// Delegates to ACE_Double_Linked_List.
01071   ACE_DLList (const ACE_DLList<T> &l);
01072 
01073   /// Deletes the list starting from the head.
01074   ~ACE_DLList (void);
01075 };
01076 
01077 /**
01078  * @class ACE_DLList_Iterator
01079  *
01080  * @brief A double-linked list container class iterator.
01081  *
01082  * This implementation uses ACE_Double_Linked_List_Iterator to
01083  * perform the logic behind this container class.  It delegates
01084  * all of its calls to ACE_Double_Linked_List_Iterator.
01085  */
01086 template <class T>
01087 class ACE_DLList_Iterator : public ACE_Double_Linked_List_Iterator <ACE_DLList_Node>
01088 {
01089 
01090   friend class ACE_DLList<T>;
01091   friend class ACE_DLList_Node;
01092 
01093 public:
01094 
01095   // = Initialization method.
01096   ACE_DLList_Iterator (ACE_DLList<T> &l);
01097 
01098   /**
01099    * Retasks the iterator to iterate over a new
01100    * Double_Linked_List. This allows clients to reuse an iterator
01101    * without incurring the constructor overhead. If you do use this,
01102    * be aware that if there are more than one reference to this
01103    * iterator, the other "clients" may be very bothered when their
01104    * iterator changes.
01105    * @@ Here be dragons. Comments?
01106    */
01107   void reset (ACE_DLList<T> &l);
01108 
01109   // = Iteration methods.
01110   /// Move forward by one element in the list.  Returns 0 when all the
01111   /// items in the list have been seen, else 1.
01112   int advance (void);
01113 
01114   /// Pass back the <next_item> that hasn't been seen in the list.
01115   /// Returns 0 when all items have been seen, else 1.
01116   int next (T *&);
01117 
01118   /**
01119    * @deprecated Delegates to ACE_Double_Linked_List_Iterator, except that
01120    * whereas the Double_Linked_List version of next returns the node, this next
01121    * returns the contents of the node
01122    */
01123   T *next (void) const;
01124 
01125   /**
01126    * Removes the current item (i.e., <next>) from the list.
01127    * Note that DLList iterators do not support <advance_and_remove>
01128    * directly (defined in its base class) and you will need to
01129    * release the element returned by it.
01130    */
01131   int remove (void);
01132 
01133   /// Delegates to ACE_Double_Linked_List_Iterator.
01134   void dump (void) const;
01135 
01136 private:
01137   ACE_DLList<T> *list_;
01138 };
01139 
01140 /**
01141  * @class ACE_DLList_Reverse_Iterator
01142  *
01143  * @brief A double-linked list container class iterator.
01144  *
01145  * This implementation uses ACE_Double_Linked_List_Iterator to
01146  * perform the logic behind this container class.  It delegates
01147  * all of its calls to ACE_Double_Linked_List_Iterator.
01148  */
01149 template <class T>
01150 class ACE_DLList_Reverse_Iterator : public ACE_Double_Linked_List_Reverse_Iterator <ACE_DLList_Node>
01151 {
01152 
01153   friend class ACE_DLList<T>;
01154   friend class ACE_DLList_Node;
01155 
01156 public:
01157 
01158   // = Initialization method.
01159   ACE_DLList_Reverse_Iterator (ACE_DLList<T> &l);
01160 
01161   /**
01162    * Retasks the iterator to iterate over a new
01163    * Double_Linked_List. This allows clients to reuse an iterator
01164    * without incurring the constructor overhead. If you do use this,
01165    * be aware that if there are more than one reference to this
01166    * iterator, the other "clients" may be very bothered when their
01167    * iterator changes.
01168    * @@ Here be dragons. Comments?
01169    */
01170   void reset (ACE_DLList<T> &l);
01171 
01172   // = Iteration methods.
01173   /// Move forward by one element in the list.  Returns 0 when all the
01174   /// items in the list have been seen, else 1.
01175   int advance (void);
01176 
01177   /// Pass back the <next_item> that hasn't been seen in the list.
01178   /// Returns 0 when all items have been seen, else 1.
01179   int next (T *&);
01180 
01181   /// @deprecated Delegates to ACE_Double_Linked_List_Iterator.
01182   T *next (void) const;
01183 
01184   /// Removes the current item (i.e., <next>) from the list.
01185   /// Note that DLList iterators do not support <advance_and_remove>
01186   /// directly (defined in its base class) and you will need to
01187   /// release the element returned by it.
01188   int remove (void);
01189 
01190   /// Delegates to ACE_Double_Linked_List_Iterator.
01191   void dump (void) const;
01192 
01193 private:
01194   ACE_DLList<T> *list_;
01195 };
01196 
01197 // Forward declaration.
01198 template <class T, size_t ACE_SIZE>
01199 class ACE_Fixed_Set;
01200 
01201 /**
01202  * @class ACE_Fixed_Set_Iterator
01203  *
01204  * @brief Iterates through an unordered set.
01205  *
01206  * This implementation of an unordered set uses a fixed array.
01207  * Allows deletions while iteration is occurring.
01208  */
01209 template <class T, size_t ACE_SIZE>
01210 class ACE_Fixed_Set_Iterator
01211 {
01212 public:
01213   // = Initialization method.
01214   ACE_Fixed_Set_Iterator (ACE_Fixed_Set<T, ACE_SIZE> &s);
01215 
01216   // = Iteration methods.
01217 
01218   /// Pass back the <next_item> that hasn't been seen in the Set.
01219   /// Returns 0 when all items have been seen, else 1.
01220   int next (T *&next_item);
01221 
01222   /// Move forward by one element in the set.  Returns 0 when all the
01223   /// items in the set have been seen, else 1.
01224   int advance (void);
01225 
01226   /// Move to the first element in the set.  Returns 0 if the
01227   /// set is empty, else 1.
01228   int first (void);
01229 
01230   /// Returns 1 when all items have been seen, else 0.
01231   int done (void) const;
01232 
01233   /// Dump the state of an object.
01234   void dump (void) const;
01235 
01236   /// Declare the dynamic allocation hooks.
01237   ACE_ALLOC_HOOK_DECLARE;
01238 
01239 private:
01240   /// Set we are iterating over.
01241   ACE_Fixed_Set<T, ACE_SIZE> &s_;
01242 
01243   /// How far we've advanced over the set.
01244   ssize_t next_;
01245 };
01246 
01247 /**
01248  * @class ACE_Fixed_Set_Const_Iterator
01249  *
01250  * @brief Iterates through a const unordered set.
01251  *
01252  * This implementation of an unordered set uses a fixed array.
01253  */
01254 template <class T, size_t ACE_SIZE>
01255 class ACE_Fixed_Set_Const_Iterator
01256 {
01257 public:
01258   // = Initialization method.
01259   ACE_Fixed_Set_Const_Iterator (const ACE_Fixed_Set<T, ACE_SIZE> &s);
01260 
01261   // = Iteration methods.
01262 
01263   /// Pass back the <next_item> that hasn't been seen in the Set.
01264   /// Returns 0 when all items have been seen, else 1.
01265   int next (T *&next_item);
01266 
01267   /// Move forward by one element in the set.  Returns 0 when all the
01268   /// items in the set have been seen, else 1.
01269   int advance (void);
01270 
01271   /// Move to the first element in the set.  Returns 0 if the
01272   /// set is empty, else 1.
01273   int first (void);
01274 
01275   /// Returns 1 when all items have been seen, else 0.
01276   int done (void) const;
01277 
01278   /// Dump the state of an object.
01279   void dump (void) const;
01280 
01281   /// Declare the dynamic allocation hooks.
01282   ACE_ALLOC_HOOK_DECLARE;
01283 
01284 private:
01285   /// Set we are iterating over.
01286   const ACE_Fixed_Set<T, ACE_SIZE> &s_;
01287 
01288   /// How far we've advanced over the set.
01289   ssize_t next_;
01290 };
01291 
01292 
01293 /**
01294  * @class ACE_Fixed_Set
01295  *
01296  * @brief Implement a simple unordered set of <T> with maximum <ACE_SIZE>.
01297  *
01298  * This implementation of an unordered set uses a fixed array.
01299  * It does not allow duplicate members.  The set provides linear insertion/deletion
01300  * operations.
01301  *
01302  * <b> Requirements and Performance Characteristics</b>
01303  *   - Internal Structure
01304  *       Fixed array
01305  *   - Duplicates allowed?
01306  *       No
01307  *   - Random access allowed?
01308  *       No
01309  *   - Search speed
01310  *       Linear
01311  *   - Insert/replace speed
01312  *       Linear
01313  *   - Iterator still valid after change to container?
01314  *       Yes
01315  *   - Frees memory for removed elements?
01316  *       No
01317  *   - Items inserted by
01318  *       Value
01319  *   - Requirements for contained type
01320  *       -# Default constructor
01321  *       -# Copy constructor
01322  *       -# operator=
01323  *       -# operator==
01324  *
01325  */
01326 template <class T, size_t ACE_SIZE>
01327 class ACE_Fixed_Set
01328 {
01329 public:
01330   friend class ACE_Fixed_Set_Iterator<T, ACE_SIZE>;
01331   friend class ACE_Fixed_Set_Const_Iterator<T, ACE_SIZE>;
01332 
01333   // Trait definition.
01334   typedef ACE_Fixed_Set_Iterator<T, ACE_SIZE> ITERATOR;
01335   typedef ACE_Fixed_Set_Iterator<T, ACE_SIZE> CONST_ITERATOR;
01336 
01337   // = Initialization and termination methods.
01338   /// Default Constructor.
01339   /**
01340    * Creates an empy set
01341    */
01342   ACE_Fixed_Set (void);
01343 
01344   /// Copy constructor.
01345   /**
01346    * Initializes a set to be a copy of the set parameter.
01347    */
01348   ACE_Fixed_Set (const ACE_Fixed_Set<T, ACE_SIZE> &);
01349 
01350   /// Assignment operator.
01351   /**
01352    * Deep copy of one set to another.
01353    */
01354   void operator= (const ACE_Fixed_Set<T, ACE_SIZE> &);
01355 
01356   /// Destructor.
01357   /**
01358    * Destroys a set.
01359    */
01360   ~ACE_Fixed_Set (void);
01361 
01362   // = Check boundary conditions.
01363 
01364   /// Returns 1 if the container is empty, otherwise returns 0.
01365   /**
01366    * Performs constant time check to determine if a set is empty.
01367    */
01368   int is_empty (void) const;
01369 
01370   /// Returns 1 if the container is full, otherwise returns 0.
01371   /**
01372    * Performs a constant time check to see if the set is full.
01373    */
01374   int is_full (void) const;
01375 
01376   // = Classic unordered set operations.
01377 
01378   ///Linear time insertion of an item unique to the set.
01379   /**
01380    * Insert @a new_item into the set (doesn't allow duplicates).
01381    * Returns -1 if failures occur, 1 if item is already present, else
01382    * 0.
01383    */
01384   int insert (const T &new_item);
01385 
01386   ///Linear time removal operation of an item.
01387   /**
01388    * Remove first occurrence of <item> from the set.  Returns 0 if
01389    * it removes the item, -1 if it can't find the item, and -1 if a
01390    * failure occurs.  Removal doesn't reclaim memory for the @a item.
01391    */
01392   int remove (const T &item);
01393 
01394   /// Finds if @a item occurs in the set.  Returns 0 if finds, else -1.
01395   /**
01396    * Performs a linear find operation for the specified @a item.
01397    */
01398   int find (const T &item) const;
01399 
01400   /// Size of the set.
01401   /**
01402    * Returns the current size of the set.
01403    */
01404   size_t size (void) const;
01405 
01406   /// Dump the state of an object.
01407   void dump (void) const;
01408 
01409   /// Declare the dynamic allocation hooks.
01410   ACE_ALLOC_HOOK_DECLARE;
01411 
01412 private:
01413   /// Holds the contents of the set.
01414   struct
01415   {
01416     /// Item in the set.
01417     T item_;
01418 
01419     /// Keeps track of whether this item is in use or not.
01420     int is_free_;
01421   } search_structure_[ACE_SIZE];
01422 
01423   /// Current size of the set.
01424   size_t cur_size_;
01425 
01426   /// Maximum size of the set.
01427   size_t max_size_;
01428 };
01429 
01430 // Forward declaration.
01431 template <class T>
01432 class ACE_Bounded_Set;
01433 
01434 /**
01435  * @class ACE_Bounded_Set_Iterator
01436  *
01437  * @brief Iterates through an unordered set.
01438  *
01439  * This implementation of an unordered set uses a Bounded array.
01440  * Allows deletions while iteration is occurring.
01441  */
01442 template <class T>
01443 class ACE_Bounded_Set_Iterator
01444 {
01445 public:
01446   // = Initialization method.
01447   ACE_Bounded_Set_Iterator (ACE_Bounded_Set<T> &s);
01448 
01449   // = Iteration methods.
01450 
01451   /// Pass back the <next_item> that hasn't been seen in the Set.
01452   /// Returns 0 when all items have been seen, else 1.
01453   int next (T *&next_item);
01454 
01455   /// Move forward by one element in the set.  Returns 0 when all the
01456   /// items in the set have been seen, else 1.
01457   int advance (void);
01458 
01459   /// Move to the first element in the set.  Returns 0 if the
01460   /// set is empty, else 1.
01461   int first (void);
01462 
01463   /// Returns 1 when all items have been seen, else 0.
01464   int done (void) const;
01465 
01466   /// Dump the state of an object.
01467   void dump (void) const;
01468 
01469   /// Declare the dynamic allocation hooks.
01470   ACE_ALLOC_HOOK_DECLARE;
01471 
01472 private:
01473   /// Set we are iterating over.
01474   ACE_Bounded_Set<T> &s_;
01475 
01476   /// How far we've advanced over the set.
01477   ssize_t next_;
01478 };
01479 
01480 
01481 /**
01482  * @class ACE_Bounded_Set
01483  *
01484  * @brief Implement a simple unordered set of <T> with maximum
01485  * set at creation time.
01486  *
01487  * This implementation of an unordered set uses a Bounded array.
01488  * This implementation does not allow duplicates.  It provides
01489  * linear insert/remove/find operations.  Insertion/removal does not
01490  * invalidate iterators, but caution should be taken to ensure
01491  * expected behavior.  Once initialized, the object has a maximum size
01492  * which can only be increased by the assignment of another larger Bounded_Set.
01493  *
01494  * <b> Requirements and Performance Characteristics</b>
01495  *   - Internal Structure
01496  *       Bounded array which can grow via assignment
01497  *   - Duplicates allowed?
01498  *       No
01499  *   - Random access allowed?
01500  *       No
01501  *   - Search speed
01502  *       Linear
01503  *   - Insert/replace speed
01504  *       Linear
01505  *   - Iterator still valid after change to container?
01506  *       Yes
01507  *   - Frees memory for removed elements?
01508  *       No
01509  *   - Items inserted by
01510  *       Value
01511  *   - Requirements for contained type
01512  *       -# Default constructor
01513  *       -# Copy constructor
01514  *       -# operator=
01515  *       -# operator==
01516  *
01517  */
01518 template <class T>
01519 class ACE_Bounded_Set
01520 {
01521 public:
01522   friend class ACE_Bounded_Set_Iterator<T>;
01523 
01524   // Trait definition.
01525   typedef ACE_Bounded_Set_Iterator<T> ITERATOR;
01526 
01527   enum
01528   {
01529     DEFAULT_SIZE = 10
01530   };
01531 
01532   // = Initialization and termination methods.
01533   /// Construct a Bounded_Set using the default size.
01534   /**
01535    * The default constructor initializes the Bounded_Set to a maximum size
01536    * specified by the DEFAULT_SIZE.
01537    */
01538   ACE_Bounded_Set (void);
01539 
01540   /// Construct a Bounded_Set with the provided sizeB.
01541   /**
01542    * Initialize the Bounded_Set to have a maximum size equal to the size
01543    * parameter specified.
01544    */
01545   ACE_Bounded_Set (size_t size);
01546 
01547   /// Construct a Bounded_Set that is a copy of the provides Bounded_Set.
01548   /**
01549    * Initialize the Bounded_Set to be a copy of the Bounded_Set parameter.
01550    */
01551   ACE_Bounded_Set (const ACE_Bounded_Set<T> &);
01552 
01553   /// Assignment operator.
01554   /**
01555    * The assignment will make a deep copy of the Bounded_Set provided.  If the
01556    * rhs has more elements than the capacity of the lhs, then the lhs will be
01557    * deleted and reallocated to accomadate the larger number of elements.
01558    */
01559   void operator= (const ACE_Bounded_Set<T> &);
01560 
01561   /// Destructor
01562   /**
01563    * Clean up the underlying dynamically allocated memory that is used by
01564    * the Bounded_Set.
01565    */
01566   ~ACE_Bounded_Set (void);
01567 
01568   // = Check boundary conditions.
01569 
01570   /// Returns 1 if the container is empty, otherwise returns 0.
01571   /**
01572    * A constant time check is performed to determine if the Bounded_Set is
01573    * empty.
01574    */
01575   int is_empty (void) const;
01576 
01577   /// Returns 1 if the container is full, otherwise returns 0.
01578   /**
01579    * Performs a constant time check to determine if the Bounded_Set is at
01580    * capacity.
01581    */
01582   int is_full (void) const;
01583 
01584   // = Classic unordered set operations.
01585 
01586   ///Inserts a new element unique to the set.
01587   /**
01588    * Insert @a new_item into the set (doesn't allow duplicates) in linear
01589    * time.
01590    * Returns -1 if failures occur, 1 if item is already present, else
01591    * 0.
01592    */
01593   int insert (const T &new_item);
01594 
01595   ///Finds the specified element and removes it from the set.
01596   /**
01597    * Remove first occurrence of @a item from the set.  Returns 0 if it
01598    * removes the item, -1 if it can't find the item, and -1 if a
01599    * failure occurs.  The linear remove operation does not reclaim the
01600    * memory associated with the removed item.
01601    */
01602   int remove (const T &item);
01603 
01604   /// Finds if @a item occurs in the set.  Returns 0 if finds, else -1.
01605   /**
01606    * find preforms a linear search for <item> and returns 0 on successful
01607    * find and -1 otherwise.
01608    */
01609   int find (const T &item) const;
01610 
01611   /// Size of the set.
01612   /**
01613    * Returns a size_t representing the current size of the set.
01614    */
01615   size_t size (void) const;
01616 
01617   /// Dump the state of an object.
01618   void dump (void) const;
01619 
01620   /// Declare the dynamic allocation hooks.
01621   ACE_ALLOC_HOOK_DECLARE;
01622 
01623 private:
01624   struct Search_Structure
01625   {
01626     /// Item in the set.
01627     T item_;
01628 
01629     /// Keeps track of whether this item is in use or not.
01630     int is_free_;
01631   };
01632 
01633   /// Holds the contents of the set.
01634   Search_Structure *search_structure_;
01635 
01636   /// Current size of the set.
01637   size_t cur_size_;
01638 
01639   /// Maximum size of the set.
01640   size_t max_size_;
01641 };
01642 
01643 /**
01644  * @class ACE_Ordered_MultiSet_Iterator
01645  *
01646  * @brief Implement a bidirectional iterator over an ordered multiset.
01647  * This class template requires that < operator semantics be
01648  * defined for the parameterized type <T>, but does not impose
01649  * any restriction on how that ordering operator is implemented.
01650  */
01651 template <class T>
01652 class ACE_Ordered_MultiSet_Iterator
01653 {
01654 public:
01655   friend class ACE_Ordered_MultiSet<T>;
01656 
01657   // = Initialization method.
01658   ACE_Ordered_MultiSet_Iterator (ACE_Ordered_MultiSet<T> &s);
01659 
01660   // = Iteration methods.
01661 
01662   /// Pass back the <next_item> that hasn't been seen in the ordered multiset.
01663   /// Returns 0 when all items have been seen, else 1.
01664   int next (T *&next_item) const;
01665 
01666   /// Repositions the iterator at the first item in the ordered multiset
01667   /// Returns 0 if the list is empty else 1.
01668   int first (void);
01669 
01670   /// Repositions the iterator at the last item in the ordered multiset
01671   /// Returns 0 if the list is empty else 1.
01672   int last (void);
01673 
01674   /// Move forward by one element in the set.  Returns 0 when all the
01675   /// items in the set have been seen, else 1.
01676   int advance (void);
01677 
01678   /// Move backward by one element in the set.  Returns 0 when all the
01679   /// items in the set have been seen, else 1.
01680   int retreat (void);
01681 
01682   /// Returns 1 when all items have been seen, else 0.
01683   int done (void) const;
01684 
01685   /// Dump the state of an object.
01686   void dump (void) const;
01687 
01688   /// Returns a reference to the internal element <this> is pointing to.
01689   T& operator* (void);
01690 
01691   /// Declare the dynamic allocation hooks.
01692   ACE_ALLOC_HOOK_DECLARE;
01693 
01694 private:
01695 
01696   /// Pointer to the current node in the iteration.
01697   ACE_DNode<T> *current_;
01698 
01699   /// Pointer to the set we're iterating over.
01700   ACE_Ordered_MultiSet<T> &set_;
01701 };
01702 
01703 
01704 /**
01705  * @class ACE_Ordered_MultiSet
01706  *
01707  * @brief Implement a simple ordered multiset of <T> of unbounded size
01708  * that allows duplicates.  This class template requires that <
01709  * operator semantics be defined for the parameterized type <T>, but
01710  * does not impose any restriction on how that ordering operator is
01711  * implemented.  The set is implemented as a linked list.
01712  *
01713  *
01714  * <b> Requirements and Performance Characteristics</b>
01715  *   - Internal Structure
01716  *       Double linked list
01717  *   - Duplicates allowed?
01718  *       Yes
01719  *   - Random access allowed?
01720  *       No
01721  *   - Search speed
01722  *       Linear
01723  *   - Insert/replace speed
01724  *       Linear
01725  *   - Iterator still valid after change to container?
01726  *       Yes
01727  *   - Frees memory for removed elements?
01728  *       Yes
01729  *   - Items inserted by
01730  *       Value
01731  *   - Requirements for contained type
01732  *       -# Default constructor
01733  *       -# Copy constructor
01734  *       -# operator=
01735  *       -# operator==
01736  *       -# operator<
01737  *
01738  *
01739  */
01740 template <class T>
01741 class ACE_Ordered_MultiSet
01742 {
01743 public:
01744   friend class ACE_Ordered_MultiSet_Iterator<T>;
01745 
01746   // Trait definition.
01747   typedef ACE_Ordered_MultiSet_Iterator<T> ITERATOR;
01748 
01749   // = Initialization and termination methods.
01750   /// Constructor.  Use user specified allocation strategy
01751   /// if specified.
01752   /**
01753    * Initialize the set using the allocation strategy specified.  If none, use the
01754    * default strategy.
01755    */
01756   ACE_Ordered_MultiSet (ACE_Allocator *alloc = 0);
01757 
01758   /// Copy constructor.
01759   /**
01760    * Initialize the set to be a copy of the provided set.
01761    */
01762   ACE_Ordered_MultiSet (const ACE_Ordered_MultiSet<T> &);
01763 
01764   /// Destructor.
01765   /**
01766    * Delete the nodes of the set.
01767    */
01768   ~ACE_Ordered_MultiSet (void);
01769 
01770   /// Assignment operator.
01771   /**
01772    * Delete the nodes in lhs, and copy the nodes from the rhs.
01773    */
01774   void operator= (const ACE_Ordered_MultiSet<T> &);
01775 
01776   // = Check boundary conditions.
01777 
01778   /// Returns 1 if the container is empty, otherwise returns 0.
01779   /**
01780    * Constant time check to determine if the set is empty.
01781    */
01782   int is_empty (void) const;
01783 
01784   /// Size of the set.
01785   /**
01786    * Constant time check to determine the size of the set.
01787    */
01788   size_t size (void) const;
01789 
01790   // = Classic unordered set operations.
01791 
01792   /// Insert @a new_item into the ordered multiset.
01793   /// Returns -1 if failures occur, else 0.
01794   /**
01795    * Linear time, order preserving insert into the set beginning at the head.
01796    */
01797   int insert (const T &new_item);
01798 
01799   ///Linear time insert beginning at the point specified by the provided iterator.
01800   /**
01801    * Insert @a new_item into the ordered multiset, starting its search at
01802    * the node pointed to by the iterator, and if insertion was successful,
01803    * updates the iterator to point to the newly inserted node.
01804    * Returns -1 if failures occur, else 0.
01805    */
01806   int insert (const T &new_item, ITERATOR &iter);
01807 
01808   /// Remove first occurrence of @a item from the set.  Returns 0 if
01809   /// it removes the item, -1 if it can't find the item.
01810   /**
01811    * Linear time search operation which removes the item from the set if found .
01812    */
01813   int remove (const T &item);
01814 
01815   ///Linear find operation.
01816   /**
01817    * Finds first occurrence of @a item in the multiset, using the iterator's
01818    * current position as a hint to improve performance. If find succeeds,
01819    * it positions the iterator at that node and returns 0, or if it cannot
01820    * locate the node, it leaves the iterator alone and just returns -1.
01821    */
01822   int find (const T &item, ITERATOR &iter) const;
01823 
01824   /// Reset the ACE_Ordered_MultiSet to be empty.
01825   /**
01826    * Delete the nodes inside the set.
01827    */
01828   void reset (void);
01829 
01830   /// Dump the state of an object.
01831   void dump (void) const;
01832 
01833   /// Declare the dynamic allocation hooks.
01834   ACE_ALLOC_HOOK_DECLARE;
01835 
01836 private:
01837 
01838   /**
01839    * Insert @a item, starting its search at the position given,
01840    * and if successful updates the passed pointer to point to
01841    * the newly inserted item's node.
01842    */
01843   int insert_from (const T &item, ACE_DNode<T> *start_position,
01844                    ACE_DNode<T> **new_position);
01845 
01846   /**
01847    * Looks for first occurance of @a item in the ordered set, using the
01848    * passed starting position as a hint: if there is such an instance, it
01849    * updates the new_position pointer to point to this node and returns 0;
01850    * if there is no such node, then if there is a node before where the
01851    * item would have been, it updates the new_position pointer to point
01852    * to this node and returns -1; if there is no such node, then if there
01853    * is a node after where the item would have been, it updates the
01854    * new_position pointer to point to this node (or 0 if there is no such
01855    * node) and returns 1;
01856    */
01857   int locate (const T &item, ACE_DNode<T> *start_position,
01858               ACE_DNode<T> *&new_position) const;
01859 
01860   /// Delete all the nodes in the Set.
01861   void delete_nodes (void);
01862 
01863   /// Copy nodes into this set.
01864   void copy_nodes (const ACE_Ordered_MultiSet<T> &);
01865 
01866   /// Head of the bilinked list of Nodes.
01867   ACE_DNode<T> *head_;
01868 
01869   /// Head of the bilinked list of Nodes.
01870   ACE_DNode<T> *tail_;
01871 
01872   /// Current size of the set.
01873   size_t cur_size_;
01874 
01875   /// Allocation strategy of the set.
01876   ACE_Allocator *allocator_;
01877 };
01878 
01879 // ****************************************************************
01880 
01881 /**
01882  * @class ACE_Array
01883  *
01884  * @brief A dynamic array class.
01885  *
01886  * This class extends ACE_Array_Base, adding comparison operators.
01887  *
01888  * <b> Requirements and Performance Characteristics</b>
01889  *   - Internal Structure
01890  *       Dynamic array
01891  *   - Duplicates allowed?
01892  *       Yes
01893  *   - Random access allowed?
01894  *       Yes
01895  *   - Search speed
01896  *       N/A
01897  *   - Insert/replace speed
01898  *       O(1)
01899  *   - Iterator still valid after change to container?
01900  *       - In general, yes.
01901  *       - If array size is changed during iteration, no.
01902  *   - Frees memory for removed elements?
01903  *       No
01904  *   - Items inserted by
01905  *       Value
01906  *   - Requirements for contained type
01907  *       -# Default constructor
01908  *       -# Copy constructor
01909  *       -# operator=
01910  *       -# operator!=
01911  *
01912  * @sa ACE_Array_Base. This class inherits its operations and requirements.
01913  */
01914 template <class T>
01915 class ACE_Array : public ACE_Array_Base<T>
01916 {
01917 public:
01918   // Define a "trait"
01919   typedef T TYPE;
01920 
01921   typedef ACE_Array_Iterator<T> ITERATOR;
01922 
01923   // = Exceptions.
01924 
01925   // = Initialization and termination methods.
01926 
01927   /// Dynamically create an uninitialized array.
01928   /**
01929    * Initialize an empty array of the specified size using the provided
01930    * allocation strategy.
01931    */
01932   ACE_Array (size_t size = 0,
01933              ACE_Allocator* alloc = 0);
01934 
01935   /// Dynamically initialize the entire array to the <default_value>.
01936   /**
01937    * Initialize an array the given size placing the default_value in each index.
01938    */
01939   ACE_Array (size_t size,
01940              const T &default_value,
01941              ACE_Allocator* alloc = 0);
01942 
01943   ///Copy constructor.
01944   /**
01945    * The copy constructor performs initialization by making an exact
01946    * copy of the contents of parameter <s>, i.e., *this == s will
01947    * return true.
01948    */
01949   ACE_Array (const ACE_Array<T> &s);
01950 
01951   ///Assignment operator
01952   /**
01953    * Assignment operator performs an assignment by making an exact
01954    * copy of the contents of parameter <s>, i.e., *this == s will
01955    * return true.  Note that if the <max_size_> of <array_> is >= than
01956    * <s.max_size_> we can copy it without reallocating.  However, if
01957    * <max_size_> is < <s.max_size_> we must delete the <array_>,
01958    * reallocate a new <array_>, and then copy the contents of <s>.
01959    */
01960   void operator= (const ACE_Array<T> &s);
01961 
01962   // = Compare operators
01963 
01964   ///Equality comparison operator.
01965   /**
01966    * Compare this array with <s> for equality.  Two arrays are equal
01967    * if their <size>'s are equal and all the elements from 0 .. <size>
01968    * are equal.
01969    */
01970   int operator== (const ACE_Array<T> &s) const;
01971 
01972   ///Inequality comparison operator.
01973   /**
01974    * Compare this array with <s> for inequality such that <*this> !=
01975    * <s> is always the complement of the boolean return value of
01976    * <*this> == <s>.
01977    */
01978   int operator!= (const ACE_Array<T> &s) const;
01979 };
01980 
01981 #if defined (__ACE_INLINE__)
01982 #include "ace/Containers_T.i"
01983 #endif /* __ACE_INLINE__ */
01984 
01985 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
01986 #include "ace/Containers_T.cpp"
01987 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
01988 
01989 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
01990 #pragma implementation ("Containers_T.cpp")
01991 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
01992 
01993 #include "ace/post.h"
01994 
01995 #endif /* ACE_CONTAINERS_T_H */

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