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

Unbounded_Queue.h

Go to the documentation of this file.
00001 /* -*- C++ -*- */
00002 
00003 //=============================================================================
00004 /**
00005  *  @file Unbounded_Queue.h
00006  *
00007  *  $Id: Unbounded_Queue.h,v 1.1.1.2 2003/02/21 18:36:32 chad Exp $
00008  *
00009  *  @author Douglas C. Schmidt <schmidt@cs.wustl.edu>
00010  */
00011 //=============================================================================
00012 
00013 #ifndef ACE_UNBOUNDED_QUEUE_H
00014 #define ACE_UNBOUNDED_QUEUE_H
00015 #include "ace/pre.h"
00016 
00017 #include "ace/Node.h"
00018 
00019 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00020 # pragma once
00021 #endif /* ACE_LACKS_PRAGMA_ONCE */
00022 
00023 // For size_t under Chorus
00024 #include "ace/OS_Memory.h"
00025 
00026 class ACE_Allocator;
00027 
00028 template <class T>
00029 class ACE_Unbounded_Queue;
00030 
00031 /**
00032  * @class ACE_Unbounded_Queue_Iterator
00033  *
00034  * @brief Implement an iterator over an unbounded queue.
00035  */
00036 template <class T>
00037 class ACE_Unbounded_Queue_Iterator
00038 {
00039 public:
00040   // = Initialization method.
00041   ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end = 0);
00042 
00043   // = Iteration methods.
00044 
00045   /// Pass back the @a next_item that hasn't been seen in the queue.
00046   /// Returns 0 when all items have been seen, else 1.
00047   int next (T *&next_item);
00048 
00049   /// Move forward by one element in the set.  Returns 0 when all the
00050   /// items in the queue have been seen, else 1.
00051   int advance (void);
00052 
00053   /// Move to the first element in the queue.  Returns 0 if the
00054   /// queue is empty, else 1.
00055   int first (void);
00056 
00057   /// Returns 1 when all items have been seen, else 0.
00058   int done (void) const;
00059 
00060   /// Dump the state of an object.
00061   void dump (void) const;
00062 
00063   /// Declare the dynamic allocation hooks.
00064   ACE_ALLOC_HOOK_DECLARE;
00065 
00066 private:
00067   /// Pointer to the current node in the iteration.
00068   ACE_Node<T> *current_;
00069 
00070   /// Pointer to the queue we're iterating over.
00071   ACE_Unbounded_Queue<T> &queue_;
00072 };
00073 
00074 /**
00075  * @class ACE_Unbounded_Queue_Const_Iterator
00076  *
00077  * @brief Implement an iterator over an const unbounded queue.
00078  */
00079 template <class T>
00080 class ACE_Unbounded_Queue_Const_Iterator
00081 {
00082 public:
00083   // = Initialization method.
00084   ACE_Unbounded_Queue_Const_Iterator (const ACE_Unbounded_Queue<T> &q, int end = 0);
00085 
00086   // = Iteration methods.
00087 
00088   /// Pass back the @a next_item that hasn't been seen in the queue.
00089   /// Returns 0 when all items have been seen, else 1.
00090   int next (T *&next_item);
00091 
00092   /// Move forward by one element in the set.  Returns 0 when all the
00093   /// items in the queue have been seen, else 1.
00094   int advance (void);
00095 
00096   /// Move to the first element in the queue.  Returns 0 if the
00097   /// queue is empty, else 1.
00098   int first (void);
00099 
00100   /// Returns 1 when all items have been seen, else 0.
00101   int done (void) const;
00102 
00103   /// Dump the state of an object.
00104   void dump (void) const;
00105 
00106   /// Declare the dynamic allocation hooks.
00107   ACE_ALLOC_HOOK_DECLARE;
00108 
00109 private:
00110   /// Pointer to the current node in the iteration.
00111   ACE_Node<T> *current_;
00112 
00113   /// Pointer to the queue we're iterating over.
00114   const ACE_Unbounded_Queue<T> &queue_;
00115 };
00116 
00117 /**
00118  * @class ACE_Unbounded_Queue
00119  *
00120  * @brief A Queue of "infinite" length.
00121  *
00122  * This implementation of an unbounded queue uses a circular
00123  * linked list with a dummy node.
00124  *
00125  * <b> Requirements and Performance Characteristics</b>
00126  *   - Internal Structure
00127  *       Circular linked list
00128  *   - Duplicates allowed?
00129  *       Yes
00130  *   - Random access allowed?
00131  *       No
00132  *   - Search speed
00133  *       N/A
00134  *   - Insert/replace speed
00135  *       N/A
00136  *   - Iterator still valid after change to container?
00137  *       Yes
00138  *   - Frees memory for removed elements?
00139  *       Yes
00140  *   - Items inserted by
00141  *       Value
00142  *   - Requirements for contained type
00143  *       -# Default constructor
00144  *       -# Copy constructor
00145  *       -# operator=
00146  *
00147  */
00148 template <class T>
00149 class ACE_Unbounded_Queue
00150 {
00151 public:
00152   friend class ACE_Unbounded_Queue_Iterator<T>;
00153   friend class ACE_Unbounded_Queue_Const_Iterator<T>;
00154 
00155   // Trait definition.
00156   typedef ACE_Unbounded_Queue_Iterator<T> ITERATOR;
00157   typedef ACE_Unbounded_Queue_Const_Iterator<T> CONST_ITERATOR;
00158 
00159   // = Initialization and termination methods.
00160   /// Construction.  Use user specified allocation strategy
00161   /// if specified.
00162   /**
00163    * Initialize an empty queue using the strategy provided.
00164    */
00165   ACE_Unbounded_Queue (ACE_Allocator *alloc = 0);
00166 
00167   /// Copy constructor.
00168   /**
00169    * Initialize the queue to be a copy of the provided queue.
00170    */
00171   ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &);
00172 
00173   /// Assignment operator.
00174   /**
00175    * Perform a deep copy of rhs.
00176    */
00177   void operator= (const ACE_Unbounded_Queue<T> &);
00178 
00179   /// Destructor.
00180   /**
00181    * Clean up the memory for the queue.
00182    */
00183   ~ACE_Unbounded_Queue (void);
00184 
00185   // = Check boundary conditions.
00186 
00187   /// Returns 1 if the container is empty, otherwise returns 0.
00188   /**
00189    * Constant time check to see if the queue is empty.
00190    */
00191   int is_empty (void) const;
00192 
00193   /// Returns 0.
00194   /**
00195    * The queue cannot be full, so it always returns 0.
00196    */
00197   int is_full (void) const;
00198 
00199   // = Classic queue operations.
00200 
00201   /// Adds @a new_item to the tail of the queue.  Returns 0 on success,
00202   /// -1 on failure.
00203   /**
00204    * Insert an item at the end of the queue.
00205    */
00206   int enqueue_tail (const T &new_item);
00207 
00208   /// Adds @a new_item to the head of the queue.  Returns 0 on success,
00209   /// -1 on failure.
00210   /**
00211    * Insert an item at the head of the queue.
00212    */
00213   int enqueue_head (const T &new_item);
00214 
00215   /// Removes and returns the first @a item on the queue.  Returns 0 on
00216   /// success, -1 if the queue was empty.
00217   /**
00218    * Remove an item from the head of the queue.
00219    */
00220   int dequeue_head (T &item);
00221 
00222   // = Additional utility methods.
00223 
00224   /// Reset the ACE_Unbounded_Queue to be empty and release all its
00225   /// dynamically allocated resources.
00226   /**
00227    * Delete the queue nodes.
00228    */
00229   void reset (void);
00230 
00231   /// Get the @a slot th element in the set.  Returns -1 if the element
00232   /// isn't in the range {0..#cur_size_ - 1}, else 0.
00233   /**
00234    * Find the item in the queue between 0 and the provided index of the
00235    * queue.
00236    */
00237   int get (T *&item, size_t slot = 0) const;
00238 
00239   /// Set the @a slot th element of the queue to @a item.
00240   /**
00241    * Set the @a slot th element in the set.  Will pad out the set with
00242    * empty nodes if @a slot is beyond the range {0..#cur_size_ - 1}.
00243    * Returns -1 on failure, 0 if @a slot isn't initially in range, and
00244    * 0 otherwise.
00245    */
00246   int set (const T &item, size_t slot);
00247 
00248   /// The number of items in the queue.
00249   /**
00250    * Return the size of the queue.
00251    */
00252   size_t size (void) const;
00253 
00254   /// Dump the state of an object.
00255   void dump (void) const;
00256 
00257   // = STL-styled unidirectional iterator factory.
00258   ACE_Unbounded_Queue_Iterator<T> begin (void);
00259   ACE_Unbounded_Queue_Iterator<T> end (void);
00260 
00261   /// Declare the dynamic allocation hooks.
00262   ACE_ALLOC_HOOK_DECLARE;
00263 
00264 protected:
00265   /// Delete all the nodes in the queue.
00266   void delete_nodes (void);
00267 
00268   /// Copy nodes into this queue.
00269   void copy_nodes (const ACE_Unbounded_Queue<T> &);
00270 
00271   /// Pointer to the dummy node in the circular linked Queue.
00272   ACE_Node<T> *head_;
00273 
00274   /// Current size of the queue.
00275   size_t cur_size_;
00276 
00277   /// Allocation Strategy of the queue.
00278   ACE_Allocator *allocator_;
00279 };
00280 
00281 #if defined (__ACE_INLINE__)
00282 #include "ace/Unbounded_Queue.inl"
00283 #endif /* __ACE_INLINE__ */
00284 
00285 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
00286 #include "ace/Unbounded_Queue.cpp"
00287 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
00288 
00289 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
00290 #pragma implementation ("Unbounded_Queue.cpp")
00291 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
00292 
00293 #include "ace/post.h"
00294 #endif /* ACE_UNBOUNDED_QUEUE_H */

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