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

ACE_Bounded_Set Class Template Reference

Implement a simple unordered set of <T> with maximum set at creation time. More...

#include <Containers_T.h>

List of all members.

Public Types

typedef ACE_Bounded_Set_Iterator<
T > 
ITERATOR
enum  { DEFAULT_SIZE = 10 }

Public Methods

 ACE_Bounded_Set (void)
 Construct a Bounded_Set using the default size. More...

 ACE_Bounded_Set (size_t size)
 Construct a Bounded_Set with the provided sizeB. More...

 ACE_Bounded_Set (const ACE_Bounded_Set< T > &)
 Construct a Bounded_Set that is a copy of the provides Bounded_Set. More...

void operator= (const ACE_Bounded_Set< T > &)
 Assignment operator. More...

 ~ACE_Bounded_Set (void)
 Destructor. More...

int is_empty (void) const
 Returns 1 if the container is empty, otherwise returns 0. More...

int is_full (void) const
 Returns 1 if the container is full, otherwise returns 0. More...

int insert (const T &new_item)
 Inserts a new element unique to the set. More...

int remove (const T &item)
 Finds the specified element and removes it from the set. More...

int find (const T &item) const
 Finds if item occurs in the set. Returns 0 if finds, else -1. More...

size_t size (void) const
 Size of the set. More...

void dump (void) const
 Dump the state of an object. More...


Public Attributes

 ACE_ALLOC_HOOK_DECLARE
 Declare the dynamic allocation hooks. More...


Private Attributes

Search_Structuresearch_structure_
 Holds the contents of the set. More...

size_t cur_size_
 Current size of the set. More...

size_t max_size_
 Maximum size of the set. More...


Friends

class ACE_Bounded_Set_Iterator< T >


Detailed Description

template<class T>
class ACE_Bounded_Set< T >

Implement a simple unordered set of <T> with maximum set at creation time.

This implementation of an unordered set uses a Bounded array. This implementation does not allow duplicates. It provides linear insert/remove/find operations. Insertion/removal does not invalidate iterators, but caution should be taken to ensure expected behavior. Once initialized, the object has a maximum size which can only be increased by the assignment of another larger Bounded_Set.

Requirements and Performance Characteristics

Definition at line 1519 of file Containers_T.h.


Member Typedef Documentation

template<class T>
typedef ACE_Bounded_Set_Iterator<T> ACE_Bounded_Set::ITERATOR
 

Definition at line 1525 of file Containers_T.h.


Member Enumeration Documentation

template<class T>
anonymous enum
 

Enumeration values:
DEFAULT_SIZE 

Definition at line 1527 of file Containers_T.h.

01528   {
01529     DEFAULT_SIZE = 10
01530   };


Constructor & Destructor Documentation

template<class T>
ACE_Bounded_Set< T >::ACE_Bounded_Set void   
 

Construct a Bounded_Set using the default size.

The default constructor initializes the Bounded_Set to a maximum size specified by the DEFAULT_SIZE.

Definition at line 1183 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, ACE_TYPENAME, ACE_Bounded_Set::Search_Structure::is_free_, max_size_, and search_structure_.

01184   : cur_size_ (0),
01185     max_size_ (ACE_static_cast(size_t, ACE_Bounded_Set<T>::DEFAULT_SIZE))
01186 {
01187   ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set");
01188 
01189   ACE_NEW (this->search_structure_,
01190            ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[this->max_size_]);
01191 
01192   for (size_t i = 0; i < this->max_size_; i++)
01193     this->search_structure_[i].is_free_ = 1;
01194 }

template<class T>
ACE_Bounded_Set< T >::ACE_Bounded_Set size_t    size
 

Construct a Bounded_Set with the provided sizeB.

Initialize the Bounded_Set to have a maximum size equal to the size parameter specified.

Definition at line 1233 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, ACE_TYPENAME, ACE_Bounded_Set::Search_Structure::is_free_, max_size_, search_structure_, and size.

01234   : cur_size_ (0),
01235     max_size_ (size)
01236 {
01237   ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set");
01238   ACE_NEW (this->search_structure_,
01239            ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[size]);
01240 
01241   for (size_t i = 0; i < this->max_size_; i++)
01242     this->search_structure_[i].is_free_ = 1;
01243 }

template<class T>
ACE_Bounded_Set< T >::ACE_Bounded_Set const ACE_Bounded_Set< T > &   
 

Construct a Bounded_Set that is a copy of the provides Bounded_Set.

Initialize the Bounded_Set to be a copy of the Bounded_Set parameter.

Definition at line 1197 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, ACE_TYPENAME, cur_size_, and search_structure_.

01198   : cur_size_ (bs.cur_size_),
01199     max_size_ (bs.max_size_)
01200 {
01201   ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set");
01202 
01203   ACE_NEW (this->search_structure_,
01204            ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[this->max_size_]);
01205 
01206   for (size_t i = 0; i < this->cur_size_; i++)
01207     this->search_structure_[i] = bs.search_structure_[i];
01208 }

template<class T>
ACE_Bounded_Set< T >::~ACE_Bounded_Set void   
 

Destructor.

Clean up the underlying dynamically allocated memory that is used by the Bounded_Set.

Definition at line 1176 of file Containers_T.cpp.

References ACE_TRACE, and search_structure_.

01177 {
01178   ACE_TRACE ("ACE_Bounded_Set<T>::~ACE_Bounded_Set");
01179   delete [] this->search_structure_;
01180 }


Member Function Documentation

template<class T>
void ACE_Bounded_Set< T >::dump void    const
 

Dump the state of an object.

Definition at line 1170 of file Containers_T.cpp.

References ACE_TRACE.

01171 {
01172   ACE_TRACE ("ACE_Bounded_Set<T>::dump");
01173 }

template<class T>
int ACE_Bounded_Set< T >::find const T &    item const
 

Finds if item occurs in the set. Returns 0 if finds, else -1.

find preforms a linear search for <item> and returns 0 on successful find and -1 otherwise.

Definition at line 1246 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, ACE_Bounded_Set::Search_Structure::is_free_, ACE_Bounded_Set::Search_Structure::item_, and search_structure_.

01247 {
01248   ACE_TRACE ("ACE_Bounded_Set<T>::find");
01249 
01250   for (size_t i = 0; i < this->cur_size_; i++)
01251     if (this->search_structure_[i].item_ == item
01252         && this->search_structure_[i].is_free_ == 0)
01253       return 0;
01254 
01255   return -1;
01256 }

template<class T>
int ACE_Bounded_Set< T >::insert const T &    new_item
 

Inserts a new element unique to the set.

Insert new_item into the set (doesn't allow duplicates) in linear time. Returns -1 if failures occur, 1 if item is already present, else 0.

Definition at line 1259 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, ACE_Bounded_Set::Search_Structure::is_free_, ACE_Bounded_Set::Search_Structure::item_, max_size_, and search_structure_.

01260 {
01261   ACE_TRACE ("ACE_Bounded_Set<T>::insert");
01262   int first_free = -1;   // Keep track of first free slot.
01263   size_t i;
01264 
01265   for (i = 0; i < this->cur_size_; i++)
01266     // First, make sure we don't allow duplicates.
01267 
01268     if (this->search_structure_[i].item_ == item
01269         && this->search_structure_[i].is_free_ == 0)
01270       return 1;
01271     else if (this->search_structure_[i].is_free_ && first_free == -1)
01272       first_free = ACE_static_cast(int, i);
01273 
01274   if (first_free > -1)   // If we found a free spot let's reuse it.
01275     {
01276       this->search_structure_[first_free].item_ = item;
01277       this->search_structure_[first_free].is_free_ = 0;
01278       return 0;
01279     }
01280   else if (i < this->max_size_) // Insert at the end of the active portion.
01281     {
01282       this->search_structure_[i].item_ = item;
01283       this->search_structure_[i].is_free_ = 0;
01284       this->cur_size_++;
01285       return 0;
01286     }
01287   else /* No more room! */
01288     {
01289       errno = ENOMEM;
01290       return -1;
01291     }
01292 }

template<class T>
ACE_INLINE int ACE_Bounded_Set< T >::is_empty void    const
 

Returns 1 if the container is empty, otherwise returns 0.

A constant time check is performed to determine if the Bounded_Set is empty.

Definition at line 181 of file Containers_T.i.

References ACE_TRACE, and cur_size_.

00182 {
00183   ACE_TRACE ("ACE_Bounded_Set<T>::is_empty");
00184   return this->cur_size_ == 0;
00185 }

template<class T>
ACE_INLINE int ACE_Bounded_Set< T >::is_full void    const
 

Returns 1 if the container is full, otherwise returns 0.

Performs a constant time check to determine if the Bounded_Set is at capacity.

Definition at line 190 of file Containers_T.i.

References ACE_TRACE, cur_size_, and max_size_.

00191 {
00192   ACE_TRACE ("ACE_Bounded_Set<T>::is_full");
00193   return this->cur_size_ == this->max_size_;
00194 }

template<class T>
void ACE_Bounded_Set< T >::operator= const ACE_Bounded_Set< T > &   
 

Assignment operator.

The assignment will make a deep copy of the Bounded_Set provided. If the rhs has more elements than the capacity of the lhs, then the lhs will be deleted and reallocated to accomadate the larger number of elements.

Definition at line 1211 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, ACE_TYPENAME, cur_size_, max_size_, and search_structure_.

01212 {
01213   ACE_TRACE ("ACE_Bounded_Set<T>::operator=");
01214 
01215   if (this != &bs)
01216     {
01217       if (this->max_size_ < bs.cur_size_)
01218         {
01219           delete [] this->search_structure_;
01220           ACE_NEW (this->search_structure_,
01221                    ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[bs.cur_size_]);
01222           this->max_size_ = bs.cur_size_;
01223         }
01224 
01225       this->cur_size_ = bs.cur_size_;
01226 
01227       for (size_t i = 0; i < this->cur_size_; i++)
01228         this->search_structure_[i] = bs.search_structure_[i];
01229     }
01230 }

template<class T>
int ACE_Bounded_Set< T >::remove const T &    item
 

Finds the specified element and removes it from the set.

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. The linear remove operation does not reclaim the memory associated with the removed item.

Definition at line 1295 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, ACE_Bounded_Set::Search_Structure::is_free_, ACE_Bounded_Set::Search_Structure::item_, and search_structure_.

01296 {
01297   ACE_TRACE ("ACE_Bounded_Set<T>::remove");
01298   for (size_t i = 0; i < this->cur_size_; i++)
01299     if (this->search_structure_[i].item_ == item)
01300       {
01301         // Mark this entry as being free.
01302         this->search_structure_[i].is_free_ = 1;
01303 
01304         // If we just unbound the highest entry, then we need to
01305         // figure out where the next highest active entry is.
01306         if (i + 1 == this->cur_size_)
01307           {
01308             while (i > 0 && this->search_structure_[--i].is_free_)
01309               continue;
01310 
01311             if (i == 0 && this->search_structure_[i].is_free_)
01312               this->cur_size_ = 0;
01313             else
01314               this->cur_size_ = i + 1;
01315           }
01316         return 0;
01317       }
01318 
01319   return -1;
01320 }

template<class T>
size_t ACE_Bounded_Set< T >::size void    const
 

Size of the set.

Returns a size_t representing the current size of the set.

Definition at line 907 of file Containers_T.cpp.

References ACE_TRACE, and cur_size_.

Referenced by ACE_Bounded_Set.

00908 {
00909   ACE_TRACE ("ACE_Bounded_Set<T>::size");
00910   return this->cur_size_;
00911 }


Friends And Related Function Documentation

template<class T>
friend class ACE_Bounded_Set_Iterator< T > [friend]
 

Definition at line 1522 of file Containers_T.h.


Member Data Documentation

template<class T>
ACE_Bounded_Set::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 1621 of file Containers_T.h.

template<class T>
size_t ACE_Bounded_Set::cur_size_ [private]
 

Current size of the set.

Definition at line 1637 of file Containers_T.h.

Referenced by ACE_Bounded_Set, find, insert, is_empty, is_full, operator=, remove, and size.

template<class T>
size_t ACE_Bounded_Set::max_size_ [private]
 

Maximum size of the set.

Definition at line 1640 of file Containers_T.h.

Referenced by ACE_Bounded_Set, insert, is_full, and operator=.

template<class T>
Search_Structure* ACE_Bounded_Set::search_structure_ [private]
 

Holds the contents of the set.

Definition at line 1634 of file Containers_T.h.

Referenced by ACE_Bounded_Set, find, insert, operator=, remove, and ~ACE_Bounded_Set.


The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:46:13 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002