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

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

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