Unbounded_Set.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 //=============================================================================
00004 /**
00005  *  @file Unbounded_Set.h
00006  *
00007  *  $Id: Unbounded_Set.h 78476 2007-05-24 07:55:50Z johnnyw $
00008  *
00009  *  @author Douglas C. Schmidt <schmidt@cs.wustl.edu>
00010  */
00011 //=============================================================================
00012 
00013 #ifndef ACE_UNBOUNDED_SET_H
00014 #define ACE_UNBOUNDED_SET_H
00015 #include /**/ "ace/pre.h"
00016 
00017 #include "ace/Node.h"
00018 #include "ace/os_include/os_stddef.h"
00019 
00020 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00021 # pragma once
00022 #endif /* ACE_LACKS_PRAGMA_ONCE */
00023 
00024 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
00025 
00026 class ACE_Allocator;
00027 
00028 /**
00029  * @class ACE_Unbounded_Set_Iterator
00030  *
00031  * @brief Implement an iterator over an unbounded set.
00032  */
00033 template <class T>
00034 class ACE_Unbounded_Set_Iterator
00035 {
00036 public:
00037   // = Initialization method.
00038   ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> &s, bool end = false);
00039 
00040   // = Iteration methods.
00041 
00042   /// Pass back the <next_item> that hasn't been seen in the Set.
00043   /// Returns 0 when all items have been seen, else 1.
00044   int next (T *&next_item);
00045 
00046   /// Move forward by one element in the set.  Returns 0 when all the
00047   /// items in the set have been seen, else 1.
00048   int advance (void);
00049 
00050   /// Move to the first element in the set.  Returns 0 if the
00051   /// set is empty, else 1.
00052   int first (void);
00053 
00054   /// Returns 1 when all items have been seen, else 0.
00055   int done (void) const;
00056 
00057   /// Dump the state of an object.
00058   void dump (void) const;
00059 
00060   // = STL styled iteration, compare, and reference functions.
00061 
00062   /// Postfix advance.
00063   ACE_Unbounded_Set_Iterator<T> operator++ (int);
00064 
00065   /// Prefix advance.
00066   ACE_Unbounded_Set_Iterator<T>& operator++ (void);
00067 
00068   /// Returns a reference to the internal element @c this is pointing to.
00069   T& operator* (void);
00070 
00071   /// Check if two iterators point to the same position
00072   bool operator== (const ACE_Unbounded_Set_Iterator<T> &) const;
00073   bool operator!= (const ACE_Unbounded_Set_Iterator<T> &) const;
00074 
00075   /// Declare the dynamic allocation hooks.
00076   ACE_ALLOC_HOOK_DECLARE;
00077 
00078 private:
00079 
00080   /// Pointer to the current node in the iteration.
00081   ACE_Node<T> *current_;
00082 
00083   /// Pointer to the set we're iterating over.
00084   ACE_Unbounded_Set<T> *set_;
00085 };
00086 
00087 /**
00088  * @class ACE_Unbounded_Set_Const_Iterator
00089  *
00090  * @brief Implement an const iterator over an unbounded set.
00091  */
00092 template <class T>
00093 class ACE_Unbounded_Set_Const_Iterator
00094 {
00095 public:
00096   // = Initialization method.
00097   ACE_Unbounded_Set_Const_Iterator (const ACE_Unbounded_Set<T> &s,
00098                                     bool end = false);
00099 
00100   // = Iteration methods.
00101 
00102   /// Pass back the @a next_item that hasn't been seen in the Set.
00103   /// @return Returns 0 when all items have been seen, else 1.
00104   int next (T *&next_item);
00105 
00106   /// Move forward by one element in the set.  Returns 0 when all the
00107   /// items in the set have been seen, else 1.
00108   int advance (void);
00109 
00110   /// Move to the first element in the set.  Returns 0 if the
00111   /// set is empty, else 1.
00112   int first (void);
00113 
00114   /// Returns 1 when all items have been seen, else 0.
00115   int done (void) const;
00116 
00117   /// Dump the state of an object.
00118   void dump (void) const;
00119 
00120   // = STL styled iteration, compare, and reference functions.
00121 
00122   /// Postfix advance.
00123   ACE_Unbounded_Set_Const_Iterator<T> operator++ (int);
00124 
00125   /// Prefix advance.
00126   ACE_Unbounded_Set_Const_Iterator<T>& operator++ (void);
00127 
00128   /// Returns a reference to the internal element @c this is pointing to.
00129   T& operator* (void);
00130 
00131   /// Check if two iterators point to the same position
00132   bool operator== (const ACE_Unbounded_Set_Const_Iterator<T> &) const;
00133   bool operator!= (const ACE_Unbounded_Set_Const_Iterator<T> &) const;
00134 
00135   /// Declare the dynamic allocation hooks.
00136   ACE_ALLOC_HOOK_DECLARE;
00137 
00138 private:
00139 
00140   /// Pointer to the current node in the iteration.
00141   ACE_Node<T> *current_;
00142 
00143   /// Pointer to the set we're iterating over.
00144   const ACE_Unbounded_Set<T> *set_;
00145 };
00146 
00147 /**
00148  * @class ACE_Unbounded_Set
00149  *
00150  * @brief Implement a simple unordered set of <T> of unbounded size.
00151  *
00152  * This implementation of an unordered set uses a circular
00153  * linked list with a dummy node.  This implementation does not
00154  * allow duplicates, but it maintains FIFO ordering of insertions.
00155  *
00156  * <b> Requirements and Performance Characteristics</b>
00157  *   - Internal Structure
00158  *       Circular linked list
00159  *   - Duplicates allowed?
00160  *       No
00161  *   - Random access allowed?
00162  *       No
00163  *   - Search speed
00164  *       Linear
00165  *   - Insert/replace speed
00166  *       Linear
00167  *   - Iterator still valid after change to container?
00168  *       Yes
00169  *   - Frees memory for removed elements?
00170  *       Yes
00171  *   - Items inserted by
00172  *       Value
00173  *   - Requirements for contained type
00174  *       -# Default constructor
00175  *       -# Copy constructor
00176  *       -# operator=
00177  *       -# operator==
00178  *
00179  */
00180 template <class T>
00181 class ACE_Unbounded_Set
00182 {
00183 public:
00184   friend class ACE_Unbounded_Set_Iterator<T>;
00185   friend class ACE_Unbounded_Set_Const_Iterator<T>;
00186 
00187   // Trait definition.
00188   typedef ACE_Unbounded_Set_Iterator<T> ITERATOR;
00189   typedef ACE_Unbounded_Set_Iterator<T> iterator;
00190   typedef ACE_Unbounded_Set_Const_Iterator<T> CONST_ITERATOR;
00191   typedef ACE_Unbounded_Set_Const_Iterator<T> const_iterator;
00192 
00193   // = Initialization and termination methods.
00194   /// Constructor.  Use user specified allocation strategy
00195   /// if specified.
00196   /**
00197    * Initialize an empty set using the allocation strategy of the user if
00198    * provided.
00199    */
00200   ACE_Unbounded_Set (ACE_Allocator *alloc = 0);
00201 
00202   /// Copy constructor.
00203   /**
00204    * Initialize this set to be an exact copy of the set provided.
00205    */
00206   ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &);
00207 
00208   /// Assignment operator.
00209   /**
00210    * Perform a deep copy of the rhs into the lhs.
00211    */
00212   ACE_Unbounded_Set<T> & operator= (const ACE_Unbounded_Set<T> &);
00213 
00214   /// Destructor.
00215   /**
00216    * Destroy the nodes of the set.
00217    */
00218   ~ACE_Unbounded_Set (void);
00219 
00220   // = Check boundary conditions.
00221 
00222   /// Returns @c true if the container is empty, otherwise returns @c false.
00223   /**
00224    * Constant time is_empty check.
00225    */
00226   bool is_empty (void) const;
00227 
00228   /// Returns @c false.
00229   /**
00230    * Always returns @c false since the set can never fill up.
00231    */
00232   bool is_full (void) const;
00233 
00234   // = Classic unordered set operations.
00235 
00236   /// Linear insertion of an item.
00237   /**
00238    * Insert @a new_item into the set (doesn't allow duplicates).
00239    * Returns -1 if failures occur, 1 if item is already present, else
00240    * 0.
00241    */
00242   int insert (const T &new_item);
00243 
00244   /// Insert @a item at the tail of the set (doesn't check for
00245   /// duplicates).
00246   /**
00247    * Constant time insert at the end of the set.
00248    */
00249   int insert_tail (const T &item);
00250 
00251   /// Linear remove operation.
00252   /**
00253    * Remove first occurrence of @a item from the set.  Returns 0 if
00254    * it removes the item, -1 if it can't find the item, and -1 if a
00255    * failure occurs.
00256    */
00257   int remove (const T &item);
00258 
00259   /// Finds if @a item occurs in the set.  Returns 0 if find succeeds,
00260   /// else -1.
00261   /**
00262    * Performs a linear find operation.
00263    */
00264   int find (const T &item) const;
00265 
00266   /// Size of the set.
00267   /**
00268    * Access the size of the set.
00269    */
00270   size_t size (void) const;
00271 
00272   /// Dump the state of an object.
00273   void dump (void) const;
00274 
00275   /// Reset the ACE_Unbounded_Set to be empty.
00276   /**
00277    * Delete the nodes of the set.
00278    */
00279   void reset (void);
00280 
00281   // = STL-styled unidirectional iterator factory.
00282   iterator begin (void);
00283   iterator end (void);
00284   const_iterator begin (void) const;
00285   const_iterator end (void) const;
00286 
00287   /// Declare the dynamic allocation hooks.
00288   ACE_ALLOC_HOOK_DECLARE;
00289 
00290 private:
00291   /// Delete all the nodes in the Set.
00292   void delete_nodes (void);
00293 
00294   /// Copy nodes into this set.
00295   void copy_nodes (const ACE_Unbounded_Set<T> &);
00296 
00297   /// Head of the linked list of Nodes.
00298   ACE_Node<T> *head_;
00299 
00300   /// Current size of the set.
00301   size_t cur_size_;
00302 
00303   /// Allocation strategy of the set.
00304   ACE_Allocator *allocator_;
00305 };
00306 
00307 ACE_END_VERSIONED_NAMESPACE_DECL
00308 
00309 #if defined (__ACE_INLINE__)
00310 #include "ace/Unbounded_Set.inl"
00311 #endif /* __ACE_INLINE__ */
00312 
00313 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
00314 #include "ace/Unbounded_Set.cpp"
00315 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
00316 
00317 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
00318 #pragma implementation ("Unbounded_Set.cpp")
00319 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
00320 
00321 #include /**/ "ace/post.h"
00322 #endif /* ACE_UNBOUNDED_SET_H */

Generated on Sun Jan 27 12:05:43 2008 for ACE by doxygen 1.3.6