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

ACE_Ordered_MultiSet Class Template Reference

Implement a simple ordered multiset of <T> of unbounded size that allows duplicates. This class template requires that < operator semantics be defined for the parameterized type <T>, but does not impose any restriction on how that ordering operator is implemented. The set is implemented as a linked list. More...

#include <Containers_T.h>

Collaboration diagram for ACE_Ordered_MultiSet:

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Ordered_MultiSet_Iterator<
T > 		ITERATOR

Public Methods

 ACE_Ordered_MultiSet (ACE_Allocator *alloc=0)
 Constructor. Use user specified allocation strategy if specified. More...

 ACE_Ordered_MultiSet (const ACE_Ordered_MultiSet< T > &)
 Copy constructor. More...

 ~ACE_Ordered_MultiSet (void)
 Destructor. More...

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

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

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

int insert (const T &new_item)
 Insert new_item into the ordered multiset. Returns -1 if failures occur, else 0. More...

int insert (const T &new_item, ITERATOR &iter)
 Linear time insert beginning at the point specified by the provided iterator. More...

int remove (const T &item)
 Remove first occurrence of item from the set. Returns 0 if it removes the item, -1 if it can't find the item. More...

int find (const T &item, ITERATOR &iter) const
 Linear find operation. More...

void reset (void)
 Reset the ACE_Ordered_MultiSet to be empty. 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 Methods

int insert_from (const T &item, ACE_DNode< T > *start_position, ACE_DNode< T > **new_position)
int locate (const T &item, ACE_DNode< T > *start_position, ACE_DNode< T > *&new_position) const
void delete_nodes (void)
 Delete all the nodes in the Set. More...

void copy_nodes (const ACE_Ordered_MultiSet< T > &)
 Copy nodes into this set. More...


Private Attributes

ACE_DNode< T > * head_
 Head of the bilinked list of Nodes. More...

ACE_DNode< T > * tail_
 Head of the bilinked list of Nodes. More...

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

ACE_Allocator * allocator_
 Allocation strategy of the set. More...


Friends

class ACE_Ordered_MultiSet_Iterator< T >

Detailed Description

template<class T>
class ACE_Ordered_MultiSet< T >

Implement a simple ordered multiset of <T> of unbounded size that allows duplicates. This class template requires that < operator semantics be defined for the parameterized type <T>, but does not impose any restriction on how that ordering operator is implemented. The set is implemented as a linked list.

Requirements and Performance Characteristics

Definition at line 1741 of file Containers_T.h.

Member Typedef Documentation

template<class T>
typedef ACE_Ordered_MultiSet_Iterator<T> ACE_Ordered_MultiSet::ITERATOR
 

Definition at line 1747 of file Containers_T.h.

Constructor & Destructor Documentation

template<class T>
ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet (  ACE_Allocator *    alloc = 0 ) 
 

Constructor. Use user specified allocation strategy if specified.

Initialize the set using the allocation strategy specified. If none, use the default strategy.

Definition at line 1467 of file Containers_T.cpp.

References allocator_, and ACE_Allocator::instance. 

01468   : head_ (0)
01469   , tail_ (0)
01470   , cur_size_ (0)
01471   , allocator_ (alloc)
01472 {
01473   // ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet");
01474 
01475   if (this->allocator_ == 0)
01476     this->allocator_ = ACE_Allocator::instance ();
01477 }

template<class T>
ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet (  const ACE_Ordered_MultiSet< T > &    ) 
 

Copy constructor.

Initialize the set to be a copy of the provided set.

Definition at line 1480 of file Containers_T.cpp.

References ACE_TRACE, allocator_, copy_nodes, and ACE_Allocator::instance. 

01481   : head_ (0)
01482   , tail_ (0)
01483   , cur_size_ (0)
01484   , allocator_ (us.allocator_)
01485 {
01486   ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet");
01487 
01488   if (this->allocator_ == 0)
01489     this->allocator_ = ACE_Allocator::instance ();
01490 
01491   this->copy_nodes (us);
01492 }

template<class T>
ACE_Ordered_MultiSet< T >::~ACE_Ordered_MultiSet (  void    ) 
 

Destructor.

Delete the nodes of the set.

Definition at line 1495 of file Containers_T.cpp.

References delete_nodes. 

01496 {
01497   // ACE_TRACE ("ACE_Ordered_MultiSet<T>::~ACE_Ordered_MultiSet");
01498 
01499   this->delete_nodes ();
01500 }

Member Function Documentation

template<class T>
void ACE_Ordered_MultiSet< T >::copy_nodes (  const ACE_Ordered_MultiSet< T > &    )  [private]
 

Copy nodes into this set.

Definition at line 1739 of file Containers_T.cpp.

References head_, insert_from, ACE_DNode::item_, and ACE_DNode::next_.

Referenced by ACE_Ordered_MultiSet, and operator=. 

01740 {
01741   ACE_DNode<T> *insertion_point = this->head_;
01742 
01743   for (ACE_DNode<T> *curr = us.head_;
01744        curr != 0;
01745        curr = curr->next_)
01746     this->insert_from (curr->item_, insertion_point, &insertion_point);
01747 }

template<class T>
void ACE_Ordered_MultiSet< T >::delete_nodes (  void    )  [private]
 

Delete all the nodes in the Set.

Definition at line 1750 of file Containers_T.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, ACE_DNode::next_, and tail_.

Referenced by operator=, reset, and ~ACE_Ordered_MultiSet. 

01751 {
01752   // iterate through list, deleting nodes
01753   for (ACE_DNode<T> *curr = this->head_;
01754        curr != 0;
01755        )
01756     {
01757       ACE_DNode<T> *temp = curr;
01758       curr = curr->next_;
01759       ACE_DES_FREE_TEMPLATE (temp,
01760                              this->allocator_->free,
01761                              ACE_DNode,
01762                              <T>);
01763     }
01764 
01765   this->head_ = 0;
01766   this->tail_ = 0;
01767   this->cur_size_ = 0;
01768 }

template<class T>
void ACE_Ordered_MultiSet< T >::dump (  void    )  const
 

Dump the state of an object.

Definition at line 1596 of file Containers_T.cpp. 

01597 {
01598   //  ACE_TRACE ("ACE_Ordered_MultiSet<T>::dump");
01599   //
01600   //  ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
01601   //  ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nhead_ = %u"), this->head_));
01602   //  ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
01603   //  ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_));
01604   //
01605   //  T *item = 0;
01606   //  size_t count = 1;
01607   //
01608   //  for (ACE_Ordered_MultiSet_Iterator<T> iter (*(ACE_Ordered_MultiSet<T> *) this);
01609   //       iter.next (item) != 0;
01610   //       iter.advance ())
01611   //    ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("count = %d\n"), count++));
01612   //
01613   //  ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
01614 }

template<class T>
int ACE_Ordered_MultiSet< T >::find (  const T &    item,
ITERATOR &    iter
)  const
 

Linear find operation.

Finds first occurrence of item in the multiset, using the iterator's current position as a hint to improve performance. If find succeeds, it positions the iterator at that node and returns 0, or if it cannot locate the node, it leaves the iterator alone and just returns -1.

Definition at line 1568 of file Containers_T.cpp.

References ACE_Ordered_MultiSet_Iterator::current_, and locate. 

01570 {
01571   // search an occurance of item, using iterator's current position as a hint
01572   ACE_DNode<T> *node = iter.current_;
01573   int result = locate (item, node, node);
01574 
01575   // if we found the node, update the iterator and indicate success
01576   if (node && (result == 0))
01577     {
01578       iter.current_ = node;
01579       return 0;
01580     }
01581 
01582   return -1;
01583 }

template<class T>
int ACE_Ordered_MultiSet< T >::insert (  const T &    new_item,
ITERATOR &    iter
) 
 

Linear time insert beginning at the point specified by the provided iterator.

Insert new_item into the ordered multiset, starting its search at the node pointed to by the iterator, and if insertion was successful, updates the iterator to point to the newly inserted node. Returns -1 if failures occur, else 0.

Definition at line 1525 of file Containers_T.cpp.

References ACE_Ordered_MultiSet_Iterator::current_, and insert_from. 

01527 {
01528   // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert using iterator");
01529 
01530   return  this->insert_from (new_item, iter.current_, &iter.current_);
01531 }

template<class T>
int ACE_Ordered_MultiSet< T >::insert (  const T &    new_item ) 
 

Insert new_item into the ordered multiset. Returns -1 if failures occur, else 0.

Linear time, order preserving insert into the set beginning at the head.

Definition at line 1517 of file Containers_T.cpp.

References insert_from. 

01518 {
01519   // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert");
01520 
01521   return  this->insert_from (item, this->head_, 0);
01522 }

template<class T>
int ACE_Ordered_MultiSet< T >::insert_from (  const T &    item,
ACE_DNode< T > *    start_position,
ACE_DNode< T > **    new_position
)  [private]
 

Insert item, starting its search at the position given, and if successful updates the passed pointer to point to the newly inserted item's node.

Definition at line 1617 of file Containers_T.cpp.

References ACE_NEW_MALLOC_RETURN, cur_size_, head_, locate, ACE_DNode::next_, ACE_DNode::prev_, and tail_.

Referenced by copy_nodes, and insert. 

01619 {
01620   // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert_from");
01621 
01622   // create a new node
01623   ACE_DNode<T> *temp;
01624   ACE_NEW_MALLOC_RETURN (temp,
01625                          ACE_static_cast(ACE_DNode<T>*,
01626                                          this->allocator_->malloc (sizeof (ACE_DNode<T>))),
01627                          ACE_DNode<T> (item),
01628                          -1);
01629   // obtain approximate location of the node
01630   int result = locate (item, position, position);
01631 
01632   // if there are nodes in the multiset
01633   if (position)
01634     {
01635       switch (result)
01636         {
01637           // insert after the approximate position
01638         case -1:
01639 
01640           // if there is a following node
01641           if (position->next_)
01642             {
01643               // link up with the following node
01644               position->next_->prev_ = temp;
01645               temp->next_ = position->next_;
01646             }
01647           else
01648             // appending to the end of the set
01649             tail_ = temp;
01650 
01651           // link up with the preceeding node
01652           temp->prev_ = position;
01653           position->next_ = temp;
01654 
01655           break;
01656 
01657           // insert before the position
01658         case  0:
01659         case  1:
01660 
01661           // if there is a preceeding node
01662           if (position->prev_)
01663             {
01664               // link up with the preceeding node
01665               position->prev_->next_ = temp;
01666               temp->prev_ = position->prev_;
01667             }
01668           else
01669             // prepending to the start of the set
01670             head_ = temp;
01671 
01672           // link up with the preceeding node
01673           temp->next_ = position;
01674           position->prev_ = temp;
01675 
01676           break;
01677 
01678         default:
01679           return -1;
01680         }
01681     }
01682   else
01683     {
01684       // point the head and tail to the new node.
01685       this->head_ = temp;
01686       this->tail_ = temp;
01687     }
01688 
01689   this->cur_size_++;
01690   if (new_position)
01691     *new_position = temp;
01692 
01693   return 0;
01694 }

template<class T>
ACE_INLINE int ACE_Ordered_MultiSet< T >::is_empty (  void    )  const
 

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

Constant time check to determine if the set is empty.

Definition at line 256 of file Containers_T.i.

References ACE_TRACE, and cur_size_. 

00257 {
00258   ACE_TRACE ("ACE_Ordered_MultiSet<T>::is_empty");
00259   return this->cur_size_ > 0 ? 0 : 1;
00260 }

template<class T>
int ACE_Ordered_MultiSet< T >::locate (  const T &    item,
ACE_DNode< T > *    start_position,
ACE_DNode< T > *&    new_position
)  const [private]
 

Looks for first occurance of item in the ordered set, using the passed starting position as a hint: if there is such an instance, it updates the new_position pointer to point to this node and returns 0; if there is no such node, then if there is a node before where the item would have been, it updates the new_position pointer to point to this node and returns -1; if there is no such node, then if there is a node after where the item would have been, it updates the new_position pointer to point to this node (or 0 if there is no such node) and returns 1;

Definition at line 1697 of file Containers_T.cpp.

References head_, ACE_DNode::item_, ACE_DNode::next_, and ACE_DNode::prev_.

Referenced by find, insert_from, and remove. 

01699 {
01700   if (! start_position)
01701     start_position = this->head_;
01702 
01703   // If starting before the item, move forward until at or just before
01704   // item.
01705   while (start_position && start_position->item_ < item &&
01706          start_position->next_)
01707     start_position = start_position->next_;
01708 
01709   // If starting after the item, move back until at or just after item
01710   while (start_position && item < start_position->item_ &&
01711          start_position->prev_)
01712     start_position = start_position->prev_;
01713 
01714   // Save the (approximate) location in the passed pointer.
01715   new_position = start_position;
01716 
01717   // Show the location is after (1), before (-1) , or at (0) the item
01718   if (!new_position)
01719     return 1;
01720   else if (item < new_position->item_)
01721     return 1;
01722   else if (new_position->item_ < item)
01723     return -1;
01724   else
01725     return 0;
01726 }

template<class T>
void ACE_Ordered_MultiSet< T >::operator= (  const ACE_Ordered_MultiSet< T > &    ) 
 

Assignment operator.

Delete the nodes in lhs, and copy the nodes from the rhs.

Definition at line 1504 of file Containers_T.cpp.

References ACE_TRACE, copy_nodes, and delete_nodes. 

01505 {
01506   ACE_TRACE ("ACE_Ordered_MultiSet<T>::operator=");
01507 
01508   if (this != &us)
01509     {
01510       this->delete_nodes ();
01511       this->copy_nodes (us);
01512     }
01513 }

template<class T>
int ACE_Ordered_MultiSet< T >::remove (  const T &    item ) 
 

Remove first occurrence of item from the set. Returns 0 if it removes the item, -1 if it can't find the item.

Linear time search operation which removes the item from the set if found .

Definition at line 1534 of file Containers_T.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, locate, ACE_DNode::next_, ACE_DNode::prev_, and tail_. 

01535 {
01536   // ACE_TRACE ("ACE_Ordered_MultiSet<T>::remove");
01537 
01538   ACE_DNode<T> *node = 0;
01539 
01540   int result = locate (item, 0, node);
01541 
01542   // if we found the node, remove from list and free it
01543   if (node && (result == 0))
01544     {
01545       if (node->prev_)
01546         node->prev_->next_ = node->next_;
01547       else
01548         head_ = node->next_;
01549 
01550       if (node->next_)
01551         node->next_->prev_ = node->prev_;
01552       else
01553         tail_ = node->prev_;
01554 
01555       this->cur_size_--;
01556 
01557       ACE_DES_FREE_TEMPLATE (node,
01558                              this->allocator_->free,
01559                              ACE_DNode,
01560                              <T>);
01561       return 0;
01562     }
01563 
01564   return -1;
01565 }

template<class T>
void ACE_Ordered_MultiSet< T >::reset (  void    ) 
 

Reset the ACE_Ordered_MultiSet to be empty.

Delete the nodes inside the set.

Definition at line 1588 of file Containers_T.cpp.

References ACE_TRACE, and delete_nodes. 

01589 {
01590   ACE_TRACE ("reset");
01591 
01592   this->delete_nodes ();
01593 }

template<class T>
ACE_INLINE size_t ACE_Ordered_MultiSet< T >::size (  void    )  const
 

Size of the set.

Constant time check to determine the size of the set.

Definition at line 263 of file Containers_T.i.

References cur_size_. 

00264 {
00265 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::size");
00266   return this->cur_size_;
00267 }

Friends And Related Function Documentation

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

Definition at line 1744 of file Containers_T.h.

Member Data Documentation

template<class T>
ACE_Ordered_MultiSet::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 1834 of file Containers_T.h.

template<class T>
ACE_Allocator* ACE_Ordered_MultiSet::allocator_ [private]
 

Allocation strategy of the set.

Definition at line 1876 of file Containers_T.h.

Referenced by ACE_Ordered_MultiSet.

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

Current size of the set.

Definition at line 1873 of file Containers_T.h.

Referenced by delete_nodes, insert_from, is_empty, remove, and size.

template<class T>
ACE_DNode<T>* ACE_Ordered_MultiSet::head_ [private]
 

Head of the bilinked list of Nodes.

Definition at line 1867 of file Containers_T.h.

Referenced by copy_nodes, delete_nodes, insert_from, locate, and remove.

template<class T>
ACE_DNode<T>* ACE_Ordered_MultiSet::tail_ [private]
 

Head of the bilinked list of Nodes.

Definition at line 1870 of file Containers_T.h.

Referenced by delete_nodes, insert_from, and remove.

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