ACE/ace/Unbounded_Set_Ex.h

   1 // -*- C++ -*-
   2
   3 //=============================================================================
   4 /**
   5  *  @file Unbounded_Set_Ex.h
   6  *
   7  *  @author Douglas C. Schmidt <d.schmidt@vanderbilt.edu>
   8  */
   9 //=============================================================================
  10
  11 #ifndef ACE_UNBOUNDED_SET_EX_H
  12 #define ACE_UNBOUNDED_SET_EX_H
  13 #include /**/ "ace/pre.h"
  14
  15 #include "ace/Node.h"
  16 #include "ace/os_include/os_stddef.h"
  17 #include <iterator>
  18
  19 #if !defined (ACE_LACKS_PRAGMA_ONCE)
  20 # pragma once
  21 #endif /* ACE_LACKS_PRAGMA_ONCE */
  22
  23 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  24
  25 class ACE_Allocator;
  26
  27 template <class T, class C>
  28 class ACE_Unbounded_Set_Ex_Iterator;
  29
  30 template <class T, class C>
  31 class ACE_Unbounded_Set_Ex_Const_Iterator;
  32
  33 template <class T, class C>
  34 class ACE_Unbounded_Set_Ex;
  35
  36 /**
  37  * @class ACE_Unbounded_Set_Ex_Iterator
  38  *
  39  * @brief Implement an iterator over an unbounded set.
  40  */
  41 template <class T, class C>
  42 class ACE_Unbounded_Set_Ex_Iterator
  43 {
  44 public:
  45   /// Type definition of the container type.
  46   typedef ACE_Unbounded_Set_Ex<T, C> container_type;
  47
  48   // = std::iterator_traits typedefs/traits.
  49   typedef std::forward_iterator_tag                iterator_category;
  50   typedef typename container_type::value_type      value_type;
  51   typedef typename container_type::reference       reference;
  52   typedef typename container_type::pointer         pointer;
  53   typedef typename container_type::difference_type difference_type;
  54
  55   ACE_Unbounded_Set_Ex_Iterator (ACE_Unbounded_Set_Ex<T, C> &s, bool end = false);
  56
  57   // = Iteration methods.
  58
  59   /// Pass back the @a next_item that hasn't been seen in the Set.
  60   /// Returns 0 when all items have been seen, else 1.
  61   int next (T *&next_item);
  62
  63   /// Move forward by one element in the set.  Returns 0 when all the
  64   /// items in the set have been seen, else 1.
  65   int advance (void);
  66
  67   /// Move to the first element in the set.  Returns 0 if the
  68   /// set is empty, else 1.
  69   int first (void);
  70
  71   /// Returns 1 when all items have been seen, else 0.
  72   int done (void) const;
  73
  74   /// Dump the state of an object.
  75   void dump (void) const;
  76
  77   // = STL styled iteration, compare, and reference functions.
  78
  79   /// Postfix advance.
  80   ACE_Unbounded_Set_Ex_Iterator<T, C> operator++ (int);
  81
  82   /// Prefix advance.
  83   ACE_Unbounded_Set_Ex_Iterator<T, C>& operator++ (void);
  84
  85   /// Returns a reference to the internal element @c this is pointing to.
  86   T& operator* (void);
  87
  88   /// Check if two iterators point to the same position
  89   bool operator== (const ACE_Unbounded_Set_Ex_Iterator<T, C> &) const;
  90   bool operator!= (const ACE_Unbounded_Set_Ex_Iterator<T, C> &) const;
  91
  92   /// Declare the dynamic allocation hooks.
  93   ACE_ALLOC_HOOK_DECLARE;
  94
  95 private:
  96   /// Pointer to the current node in the iteration.
  97   ACE_Node<T, C> *current_;
  98
  99   /// Pointer to the set we're iterating over.
 100   ACE_Unbounded_Set_Ex<T, C> *set_;
 101 };
 102
 103 /**
 104  * @class ACE_Unbounded_Set_Ex_Const_Iterator
 105  *
 106  * @brief Implement an const iterator over an unbounded set.
 107  */
 108 template <class T, class C>
 109 class ACE_Unbounded_Set_Ex_Const_Iterator
 110 {
 111 public:
 112   typedef ACE_Unbounded_Set_Ex<T, C> container_type;
 113
 114   // = std::iterator_traits typedefs/traits.
 115   typedef std::forward_iterator_tag                 iterator_category;
 116   typedef typename container_type::const_value_type value_type;
 117   typedef typename container_type::const_reference  reference;
 118   typedef typename container_type::const_pointer    pointer;
 119   typedef typename container_type::difference_type  difference_type;
 120
 121   ACE_Unbounded_Set_Ex_Const_Iterator (const ACE_Unbounded_Set_Ex<T, C> &s,
 122                                        bool end = false);
 123
 124   // = Iteration methods.
 125
 126   /// Pass back the @a next_item that hasn't been seen in the Set.
 127   /// @return Returns 0 when all items have been seen, else 1.
 128   int next (T *&next_item);
 129
 130   /// Move forward by one element in the set.  Returns 0 when all the
 131   /// items in the set have been seen, else 1.
 132   int advance (void);
 133
 134   /// Move to the first element in the set.  Returns 0 if the
 135   /// set is empty, else 1.
 136   int first (void);
 137
 138   /// Returns 1 when all items have been seen, else 0.
 139   int done (void) const;
 140
 141   /// Dump the state of an object.
 142   void dump (void) const;
 143
 144   // = STL styled iteration, compare, and reference functions.
 145
 146   /// Postfix advance.
 147   ACE_Unbounded_Set_Ex_Const_Iterator<T, C> operator++ (int);
 148
 149   /// Prefix advance.
 150   ACE_Unbounded_Set_Ex_Const_Iterator<T, C>& operator++ (void);
 151
 152   /// Returns a reference to the internal element @c this is pointing to.
 153   T& operator* (void);
 154
 155   /// Check if two iterators point to the same position
 156   bool operator== (const ACE_Unbounded_Set_Ex_Const_Iterator<T, C> &) const;
 157   bool operator!= (const ACE_Unbounded_Set_Ex_Const_Iterator<T, C> &) const;
 158
 159   /// Declare the dynamic allocation hooks.
 160   ACE_ALLOC_HOOK_DECLARE;
 161
 162 private:
 163   /// Pointer to the current node in the iteration.
 164   ACE_Node<T, C> *current_;
 165
 166   /// Pointer to the set we're iterating over.
 167   const ACE_Unbounded_Set_Ex<T, C> *set_;
 168 };
 169
 170 /**
 171  * @class ACE_Unbounded_Set_Ex
 172  *
 173  * @brief Implement a simple unordered set of <T> of unbounded size.
 174  *
 175  * This implementation of an unordered set uses a circular
 176  * linked list with a dummy node.  This implementation does not
 177  * allow duplicates, but it maintains FIFO ordering of insertions.
 178  *
 179  * This implementation may also be parameterized with a comparator
 180  * functor, which must implement bool operator () (const T&, const T&) const,
 181  * returning true if the given items are equivalent.  The default comparator
 182  * is sufficient for objects reliably compared with operator==.
 183  *
 184  * <b> Requirements and Performance Characteristics</b>
 185  *   - Internal Structure
 186  *       Circular linked list
 187  *   - Duplicates allowed?
 188  *       No
 189  *   - Random access allowed?
 190  *       No
 191  *   - Search speed
 192  *       Linear
 193  *   - Insert/replace speed
 194  *       Linear
 195  *   - Iterator still valid after change to container?
 196  *       Yes
 197  *   - Frees memory for removed elements?
 198  *       Yes
 199  *   - Items inserted by
 200  *       Value
 201  *   - Requirements for contained type
 202  *       -# Default constructor
 203  *       -# Copy constructor
 204  *       -# operator=
 205  *       -# operator== const
 206  */
 207 template <class T, class C>
 208 class ACE_Unbounded_Set_Ex
 209 {
 210 public:
 211   friend class ACE_Unbounded_Set_Ex_Iterator<T, C>;
 212   friend class ACE_Unbounded_Set_Ex_Const_Iterator<T, C>;
 213
 214   // Trait definition.
 215   typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ITERATOR;
 216   typedef ACE_Unbounded_Set_Ex_Iterator<T, C> iterator;
 217   typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> CONST_ITERATOR;
 218   typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> const_iterator;
 219   typedef C COMP;
 220   typedef ACE_Node<T, C> NODE;
 221
 222   // = STL typedefs/traits.
 223   typedef T                   value_type;
 224   typedef T const             const_value_type;
 225   typedef value_type &        reference;
 226   typedef const_value_type &  const_reference;
 227   typedef value_type *        pointer;
 228   typedef const_value_type *  const_pointer;
 229   typedef ptrdiff_t           difference_type;
 230
 231   /// Constructor.  Use user specified allocation strategy
 232   /// if specified.
 233   /**
 234    * Initialize an empty set using the allocation strategy of the user if
 235    * provided.
 236    */
 237   ACE_Unbounded_Set_Ex (ACE_Allocator *alloc = 0);
 238
 239   /**
 240    * Initialize an empty set using the allocation strategy of the user if
 241    * provided, and a given comparator functor.
 242    */
 243   ACE_Unbounded_Set_Ex (const C &comparator, ACE_Allocator *alloc = 0);
 244
 245   /// Copy constructor.
 246   /**
 247    * Initialize this set to be an exact copy of the set provided.
 248    */
 249   ACE_Unbounded_Set_Ex (const ACE_Unbounded_Set_Ex<T, C> &);
 250
 251   /// Assignment operator.
 252   /**
 253    * Perform a deep copy of the rhs into the lhs.
 254    */
 255   ACE_Unbounded_Set_Ex<T, C> & operator= (const ACE_Unbounded_Set_Ex<T, C> &);
 256
 257   /// Destructor.
 258   /**
 259    * Destroy the nodes of the set.
 260    */
 261   ~ACE_Unbounded_Set_Ex (void);
 262
 263   // = Check boundary conditions.
 264
 265   /// Returns @c true if the container is empty, otherwise returns @c false.
 266   /**
 267    * Constant time is_empty check.
 268    */
 269   bool is_empty (void) const;
 270
 271   /// Returns @c false.
 272   /**
 273    * Always returns @c false since the set can never fill up.
 274    */
 275   bool is_full (void) const;
 276
 277   // = Classic unordered set operations.
 278
 279   /// Linear insertion of an item.
 280   /**
 281    * Insert @a new_item into the set (doesn't allow duplicates).
 282    * Returns -1 if failures occur, 1 if item is already present, else
 283    * 0.
 284    */
 285   int insert (const T &new_item);
 286
 287   /// Insert @a item at the tail of the set (doesn't check for
 288   /// duplicates).
 289   /**
 290    * Constant time insert at the end of the set.
 291    */
 292   int insert_tail (const T &item);
 293
 294   /// Linear remove operation.
 295   /**
 296    * Remove first occurrence of @a item from the set.  Returns 0 if
 297    * it removes the item, -1 if it can't find the item, and -1 if a
 298    * failure occurs.
 299    */
 300   int remove (const T &item);
 301
 302   /// Finds if @a item occurs in the set.  Returns 0 if find succeeds,
 303   /// else -1.
 304   /**
 305    * Performs a linear find operation.
 306    */
 307   int find (const T &item) const;
 308
 309   /// Size of the set.
 310   /**
 311    * Access the size of the set.
 312    */
 313   size_t size (void) const;
 314
 315   /// Dump the state of an object.
 316   void dump (void) const;
 317
 318   /// Reset the ACE_Unbounded_Set_Ex to be empty.
 319   /**
 320    * Delete the nodes of the set.
 321    */
 322   void reset (void);
 323
 324   // = STL-styled unidirectional iterator factory.
 325   iterator begin (void);
 326   iterator end (void);
 327   const_iterator begin (void) const;
 328   const_iterator end (void) const;
 329
 330   /// Declare the dynamic allocation hooks.
 331   ACE_ALLOC_HOOK_DECLARE;
 332
 333 private:
 334   /// Delete all the nodes in the Set.
 335   void delete_nodes (void);
 336
 337   /// Copy nodes into this set.
 338   void copy_nodes (const ACE_Unbounded_Set_Ex<T, C> &);
 339
 340   /// Head of the linked list of Nodes.
 341   NODE *head_;
 342
 343   /// Current size of the set.
 344   size_t cur_size_;
 345
 346   /// Allocation strategy of the set.
 347   ACE_Allocator *allocator_;
 348
 349   /// Comparator to be used
 350   COMP comp_;
 351 };
 352
 353 ACE_END_VERSIONED_NAMESPACE_DECL
 354
 355 #if defined (__ACE_INLINE__)
 356 #include "ace/Unbounded_Set_Ex.inl"
 357 #endif /* __ACE_INLINE__ */
 358
 359 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
 360 #include "ace/Unbounded_Set_Ex.cpp"
 361 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
 362
 363 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
 364 #pragma implementation ("Unbounded_Set_Ex.cpp")
 365 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
 366
 367 #include /**/ "ace/post.h"
 368 #endif /* ACE_UNBOUNDED_SET_H */