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 */