diff options
author | coryan <coryan@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 2001-03-26 21:18:51 +0000 |
---|---|---|
committer | coryan <coryan@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 2001-03-26 21:18:51 +0000 |
commit | dc7b47e328ac184eed767b8287f918a46eb5d68e (patch) | |
tree | d2a03a59e7a8e39f4aeef13f0b7eb07b589b076c /ace/Unbounded_Set.h | |
parent | 91a94f0f3fa63a897d5556805a23dee7a8bba7fb (diff) | |
download | ATCD-dc7b47e328ac184eed767b8287f918a46eb5d68e.tar.gz |
ChangeLogTag:Mon Mar 26 13:00:37 2001 Carlos O'Ryan <coryan@uci.edu>
Diffstat (limited to 'ace/Unbounded_Set.h')
-rw-r--r-- | ace/Unbounded_Set.h | 196 |
1 files changed, 196 insertions, 0 deletions
diff --git a/ace/Unbounded_Set.h b/ace/Unbounded_Set.h new file mode 100644 index 00000000000..3a6f94daf03 --- /dev/null +++ b/ace/Unbounded_Set.h @@ -0,0 +1,196 @@ +/* -*- C++ -*- */ + +//============================================================================= +/** + * @file Unbounded_Set.h + * + * $Id$ + * + * @author Doug Schmidt + */ +//============================================================================= + + +#ifndef ACE_UNBOUNDED_SET_H +#define ACE_UNBOUNDED_SET_H +#include "ace/pre.h" + +#include "ace/Node.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +class ACE_Allocator; + +/** + * @class ACE_Unbounded_Set_Iterator + * + * @brief Implement an iterator over an unbounded set. + */ +template <class T> +class ACE_Unbounded_Set_Iterator +{ +public: + // = Initialization method. + ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> &s, int end = 0); + + // = Iteration methods. + + /// Pass back the <next_item> that hasn't been seen in the Set. + /// Returns 0 when all items have been seen, else 1. + int next (T *&next_item); + + /// Move forward by one element in the set. Returns 0 when all the + /// items in the set have been seen, else 1. + int advance (void); + + /// Move to the first element in the set. Returns 0 if the + /// set is empty, else 1. + int first (void); + + /// Returns 1 when all items have been seen, else 0. + int done (void) const; + + /// Dump the state of an object. + void dump (void) const; + + // = STL styled iteration, compare, and reference functions. + + /// Postfix advance. + ACE_Unbounded_Set_Iterator<T> operator++ (int); + + /// Prefix advance. + ACE_Unbounded_Set_Iterator<T>& operator++ (void); + + /// Returns a reference to the internal element <this> is pointing to. + T& operator* (void); + + /// Check if two iterators point to the same position + int operator== (const ACE_Unbounded_Set_Iterator<T> &) const; + int operator!= (const ACE_Unbounded_Set_Iterator<T> &) const; + + /// Declare the dynamic allocation hooks. + ACE_ALLOC_HOOK_DECLARE; + +private: + + /// Pointer to the current node in the iteration. + ACE_Node<T> *current_; + + /// Pointer to the set we're iterating over. + ACE_Unbounded_Set<T> *set_; +}; + +/** + * @class ACE_Unbounded_Set + * + * @brief Implement a simple unordered set of <T> of unbounded size. + * + * This implementation of an unordered set uses a circular + * linked list with a dummy node. This implementation does not + * allow duplicates, but it maintains FIFO ordering of insertions. + */ +template <class T> +class ACE_Unbounded_Set +{ +public: + friend class ACE_Unbounded_Set_Iterator<T>; + + // Trait definition. + typedef ACE_Unbounded_Set_Iterator<T> ITERATOR; + typedef ACE_Unbounded_Set_Iterator<T> iterator; + + // = Initialization and termination methods. + /// Constructor. Use user specified allocation strategy + /// if specified. + ACE_Unbounded_Set (ACE_Allocator *alloc = 0); + + /// Copy constructor. + ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &); + + /// Assignment operator. + void operator= (const ACE_Unbounded_Set<T> &); + + /// Destructor. + ~ACE_Unbounded_Set (void); + + // = Check boundary conditions. + + /// Returns 1 if the container is empty, otherwise returns 0. + int is_empty (void) const; + + /// Returns 1 if the container is full, otherwise returns 0. + int is_full (void) const; + + // = Classic unordered set operations. + + /** + * Insert <new_item> into the set (doesn't allow duplicates). + * Returns -1 if failures occur, 1 if item is already present, else + * 0. + */ + int insert (const T &new_item); + + /** + * Remove first occurrence of <item> from the set. Returns 0 if + * it removes the item, -1 if it can't find the item, and -1 if a + * failure occurs. + */ + int remove (const T &item); + + /// Finds if <item> occurs in the set. Returns 0 if find succeeds, + /// else -1. + int find (const T &item) const; + + /// Size of the set. + size_t size (void) const; + + /// Dump the state of an object. + void dump (void) const; + + /// Reset the <ACE_Unbounded_Set> to be empty. + void reset (void); + + // = STL-styled unidirectional iterator factory. + ACE_Unbounded_Set_Iterator<T> begin (void); + ACE_Unbounded_Set_Iterator<T> end (void); + + /// Declare the dynamic allocation hooks. + ACE_ALLOC_HOOK_DECLARE; + +private: + /// Insert <item> at the tail of the set (doesn't check for + /// duplicates). + int insert_tail (const T &item); + + /// Delete all the nodes in the Set. + void delete_nodes (void); + + /// Copy nodes into this set. + void copy_nodes (const ACE_Unbounded_Set<T> &); + + /// Head of the linked list of Nodes. + ACE_Node<T> *head_; + + /// Current size of the set. + size_t cur_size_; + + /// Allocation strategy of the set. + ACE_Allocator *allocator_; +}; + +#if defined (__ACE_INLINE__) +#include "ace/Unbounded_Set.inl" +#endif /* __ACE_INLINE__ */ + +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +#include "ace/Unbounded_Set.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ + +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +#pragma implementation ("Unbounded_Set.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ + +#include "ace/post.h" +#endif /* ACE_UNBOUNDED_SET_H */ |