00001 // -*- C++ -*- 00002 00003 //============================================================================= 00004 /** 00005 * @file Unbounded_Set.h 00006 * 00007 * Unbounded_Set.h,v 4.17 2006/02/10 10:33:16 jwillemsen Exp 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, int end = 0); 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 <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, int end = 0); 00098 00099 // = Iteration methods. 00100 00101 /// Pass back the @a next_item that hasn't been seen in the Set. 00102 /// @return Returns 0 when all items have been seen, else 1. 00103 int next (T *&next_item); 00104 00105 /// Move forward by one element in the set. Returns 0 when all the 00106 /// items in the set have been seen, else 1. 00107 int advance (void); 00108 00109 /// Move to the first element in the set. Returns 0 if the 00110 /// set is empty, else 1. 00111 int first (void); 00112 00113 /// Returns 1 when all items have been seen, else 0. 00114 int done (void) const; 00115 00116 /// Dump the state of an object. 00117 void dump (void) const; 00118 00119 // = STL styled iteration, compare, and reference functions. 00120 00121 /// Postfix advance. 00122 ACE_Unbounded_Set_Const_Iterator<T> operator++ (int); 00123 00124 /// Prefix advance. 00125 ACE_Unbounded_Set_Const_Iterator<T>& operator++ (void); 00126 00127 /// Returns a reference to the internal element <this> is pointing to. 00128 T& operator* (void); 00129 00130 /// Check if two iterators point to the same position 00131 bool operator== (const ACE_Unbounded_Set_Const_Iterator<T> &) const; 00132 bool operator!= (const ACE_Unbounded_Set_Const_Iterator<T> &) const; 00133 00134 /// Declare the dynamic allocation hooks. 00135 ACE_ALLOC_HOOK_DECLARE; 00136 00137 private: 00138 00139 /// Pointer to the current node in the iteration. 00140 ACE_Node<T> *current_; 00141 00142 /// Pointer to the set we're iterating over. 00143 const ACE_Unbounded_Set<T> *set_; 00144 }; 00145 00146 /** 00147 * @class ACE_Unbounded_Set 00148 * 00149 * @brief Implement a simple unordered set of <T> of unbounded size. 00150 * 00151 * This implementation of an unordered set uses a circular 00152 * linked list with a dummy node. This implementation does not 00153 * allow duplicates, but it maintains FIFO ordering of insertions. 00154 * 00155 * <b> Requirements and Performance Characteristics</b> 00156 * - Internal Structure 00157 * Circular linked list 00158 * - Duplicates allowed? 00159 * No 00160 * - Random access allowed? 00161 * No 00162 * - Search speed 00163 * Linear 00164 * - Insert/replace speed 00165 * Linear 00166 * - Iterator still valid after change to container? 00167 * Yes 00168 * - Frees memory for removed elements? 00169 * Yes 00170 * - Items inserted by 00171 * Value 00172 * - Requirements for contained type 00173 * -# Default constructor 00174 * -# Copy constructor 00175 * -# operator= 00176 * -# operator== 00177 * 00178 */ 00179 template <class T> 00180 class ACE_Unbounded_Set 00181 { 00182 public: 00183 friend class ACE_Unbounded_Set_Iterator<T>; 00184 friend class ACE_Unbounded_Set_Const_Iterator<T>; 00185 00186 // Trait definition. 00187 typedef ACE_Unbounded_Set_Iterator<T> ITERATOR; 00188 typedef ACE_Unbounded_Set_Iterator<T> iterator; 00189 typedef ACE_Unbounded_Set_Const_Iterator<T> CONST_ITERATOR; 00190 typedef ACE_Unbounded_Set_Const_Iterator<T> const_iterator; 00191 00192 // = Initialization and termination methods. 00193 /// Constructor. Use user specified allocation strategy 00194 /// if specified. 00195 /** 00196 * Initialize an empty set using the allocation strategy of the user if 00197 * provided. 00198 */ 00199 ACE_Unbounded_Set (ACE_Allocator *alloc = 0); 00200 00201 /// Copy constructor. 00202 /** 00203 * Initialize this set to be an exact copy of the set provided. 00204 */ 00205 ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &); 00206 00207 /// Assignment operator. 00208 /** 00209 * Perform a deep copy of the rhs into the lhs. 00210 */ 00211 ACE_Unbounded_Set<T> & operator= (const ACE_Unbounded_Set<T> &); 00212 00213 /// Destructor. 00214 /** 00215 * Destroy the nodes of the set. 00216 */ 00217 ~ACE_Unbounded_Set (void); 00218 00219 // = Check boundary conditions. 00220 00221 /// Returns 1 if the container is empty, otherwise returns 0. 00222 /** 00223 * Constant time is_empty check. 00224 */ 00225 int is_empty (void) const; 00226 00227 /// Returns 0. 00228 /** 00229 * Always returns 0 since the set can never fill up. 00230 */ 00231 int is_full (void) const; 00232 00233 // = Classic unordered set operations. 00234 00235 /// Linear insertion of an item. 00236 /** 00237 * Insert @a new_item into the set (doesn't allow duplicates). 00238 * Returns -1 if failures occur, 1 if item is already present, else 00239 * 0. 00240 */ 00241 int insert (const T &new_item); 00242 00243 /// Insert @a item at the tail of the set (doesn't check for 00244 /// duplicates). 00245 /** 00246 * Constant time insert at the end of the set. 00247 */ 00248 int insert_tail (const T &item); 00249 00250 /// Linear remove operation. 00251 /** 00252 * Remove first occurrence of @a item from the set. Returns 0 if 00253 * it removes the item, -1 if it can't find the item, and -1 if a 00254 * failure occurs. 00255 */ 00256 int remove (const T &item); 00257 00258 /// Finds if @a item occurs in the set. Returns 0 if find succeeds, 00259 /// else -1. 00260 /** 00261 * Performs a linear find operation. 00262 */ 00263 int find (const T &item) const; 00264 00265 /// Size of the set. 00266 /** 00267 * Access the size of the set. 00268 */ 00269 size_t size (void) const; 00270 00271 /// Dump the state of an object. 00272 void dump (void) const; 00273 00274 /// Reset the <ACE_Unbounded_Set> to be empty. 00275 /** 00276 * Delete the nodes of the set. 00277 */ 00278 void reset (void); 00279 00280 // = STL-styled unidirectional iterator factory. 00281 ACE_Unbounded_Set_Iterator<T> begin (void); 00282 ACE_Unbounded_Set_Iterator<T> end (void); 00283 00284 /// Declare the dynamic allocation hooks. 00285 ACE_ALLOC_HOOK_DECLARE; 00286 00287 private: 00288 /// Delete all the nodes in the Set. 00289 void delete_nodes (void); 00290 00291 /// Copy nodes into this set. 00292 void copy_nodes (const ACE_Unbounded_Set<T> &); 00293 00294 /// Head of the linked list of Nodes. 00295 ACE_Node<T> *head_; 00296 00297 /// Current size of the set. 00298 size_t cur_size_; 00299 00300 /// Allocation strategy of the set. 00301 ACE_Allocator *allocator_; 00302 }; 00303 00304 ACE_END_VERSIONED_NAMESPACE_DECL 00305 00306 #if defined (__ACE_INLINE__) 00307 #include "ace/Unbounded_Set.inl" 00308 #endif /* __ACE_INLINE__ */ 00309 00310 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE) 00311 #include "ace/Unbounded_Set.cpp" 00312 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ 00313 00314 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) 00315 #pragma implementation ("Unbounded_Set.cpp") 00316 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ 00317 00318 #include /**/ "ace/post.h" 00319 #endif /* ACE_UNBOUNDED_SET_H */