ACE_Ordered_MultiSet< T > 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< T >:

[legend]List of all members.

Public Types
typedef ACE_Ordered_MultiSet_Iterator< T >	ITERATOR
Public Member Functions
	ACE_Ordered_MultiSet (ACE_Allocator *the_allocator=0)
	ACE_Ordered_MultiSet (const ACE_Ordered_MultiSet< T > &)
	Copy constructor.
	~ACE_Ordered_MultiSet (void)
	Destructor.
void	operator= (const ACE_Ordered_MultiSet< T > &)
	Assignment operator.
int	is_empty (void) const
	Returns 1 if the container is empty, otherwise returns 0.
size_t	size (void) const
	Size of the set.
int	insert (const T &new_item)
int	insert (const T &new_item, ITERATOR &iter)
	Linear time insert beginning at the point specified by the provided iterator.
int	remove (const T &item)
int	find (const T &item, ITERATOR &iter) const
	Linear find operation.
void	reset (void)
	Reset the ACE_Ordered_MultiSet to be empty.
void	dump (void) const
	Dump the state of an object.
Public Attributes
	ACE_ALLOC_HOOK_DECLARE
	Declare the dynamic allocation hooks.
Private Member Functions
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.
void	copy_nodes (const ACE_Ordered_MultiSet< T > &)
	Copy nodes into this set.
Private Attributes
ACE_DNode< T > *	head_
	Head of the bilinked list of Nodes.
ACE_DNode< T > *	tail_
	Head of the bilinked list of Nodes.
size_t	cur_size_
	Current size of the set.
ACE_Allocator *	allocator_
	Allocation strategy of the set.
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

• Internal Structure Double linked list
• Duplicates allowed? Yes
• Random access allowed? No
• Search speed Linear
• Insert/replace speed Linear
• Iterator still valid after change to container? Yes
• Frees memory for removed elements? Yes
• Items inserted by Value
• Requirements for contained type
  1. Default constructor
  2. Copy constructor
  3. operator=
  4. operator==
  5. operator<

Definition at line 1768 of file Containers_T.h.

---

Member Typedef Documentation

template<class T>

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

Definition at line 1774 of file Containers_T.h.

---

Constructor & Destructor Documentation

template<class T>

ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet

(

ACE_Allocator *

the_allocator = 0

)

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

Definition at line 1518 of file Containers_T.cpp.

References ACE_Allocator::instance().

  : head_ (0)
  , tail_ (0)
  , cur_size_ (0)
  , allocator_ (alloc)
{
  // ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet");

  if (this->allocator_ == 0)
    this->allocator_ = ACE_Allocator::instance ();
}

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 1531 of file Containers_T.cpp.

References ACE_TRACE, ACE_Ordered_MultiSet< T >::allocator_, ACE_Ordered_MultiSet< T >::copy_nodes(), and ACE_Allocator::instance().

  : head_ (0)
  , tail_ (0)
  , cur_size_ (0)
  , allocator_ (us.allocator_)
{
  ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet");

  if (this->allocator_ == 0)
    this->allocator_ = ACE_Allocator::instance ();

  this->copy_nodes (us);
}

template<class T>

ACE_Ordered_MultiSet< T >::~ACE_Ordered_MultiSet

(

void

)

Destructor.

Delete the nodes of the set.

Definition at line 1546 of file Containers_T.cpp.

References ACE_Ordered_MultiSet< T >::delete_nodes().

{
  // ACE_TRACE ("ACE_Ordered_MultiSet<T>::~ACE_Ordered_MultiSet");

  this->delete_nodes ();
}

---

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 1791 of file Containers_T.cpp.

References ACE_Ordered_MultiSet< T >::head_, and ACE_Ordered_MultiSet< T >::insert_from().

Referenced by ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet(), and ACE_Ordered_MultiSet< T >::operator=().

{
  ACE_DNode<T> *insertion_point = this->head_;

  for (ACE_DNode<T> *curr = us.head_;
       curr != 0;
       curr = curr->next_)
    this->insert_from (curr->item_, insertion_point, &insertion_point);
}

template<class T>

void ACE_Ordered_MultiSet< T >::delete_nodes

(

void

)

[private]

Delete all the nodes in the Set.

Definition at line 1802 of file Containers_T.cpp.

References ACE_DES_FREE_TEMPLATE, ACE_Ordered_MultiSet< T >::cur_size_, ACE_Ordered_MultiSet< T >::head_, and ACE_Ordered_MultiSet< T >::tail_.

Referenced by ACE_Ordered_MultiSet< T >::operator=(), ACE_Ordered_MultiSet< T >::reset(), and ACE_Ordered_MultiSet< T >::~ACE_Ordered_MultiSet().

{
  // iterate through list, deleting nodes
  for (ACE_DNode<T> *curr = this->head_;
       curr != 0;
       )
    {
      ACE_DNode<T> *temp = curr;
      curr = curr->next_;
      ACE_DES_FREE_TEMPLATE (temp,
                             this->allocator_->free,
                             ACE_DNode,
                             <T>);
    }

  this->head_ = 0;
  this->tail_ = 0;
  this->cur_size_ = 0;
}

template<class T>

void ACE_Ordered_MultiSet< T >::dump

(

void

)

const

Dump the state of an object.

Definition at line 1647 of file Containers_T.cpp.

{
#if defined (ACE_HAS_DUMP)
  //  ACE_TRACE ("ACE_Ordered_MultiSet<T>::dump");
  //
  //  ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
  //  ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_ = %u"), this->head_));
  //  ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
  //  ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ncur_size_ = %d\n"), this->cur_size_));
  //
  //  T *item = 0;
  //  size_t count = 1;
  //
  //  for (ACE_Ordered_MultiSet_Iterator<T> iter (*(ACE_Ordered_MultiSet<T> *) this);
  //       iter.next (item) != 0;
  //       iter.advance ())
  //    ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("count = %d\n"), count++));
  //
  //  ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
#endif /* ACE_HAS_DUMP */
}

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 1619 of file Containers_T.cpp.

References ACE_Ordered_MultiSet_Iterator< T >::current_, and ACE_Ordered_MultiSet< T >::locate().

{
  // search an occurance of item, using iterator's current position as a hint
  ACE_DNode<T> *node = iter.current_;
  int const result = locate (item, node, node);

  // if we found the node, update the iterator and indicate success
  if (node && (result == 0))
    {
      iter.current_ = node;
      return 0;
    }

  return -1;
}

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 1576 of file Containers_T.cpp.

References ACE_Ordered_MultiSet_Iterator< T >::current_, and ACE_Ordered_MultiSet< T >::insert_from().

{
  // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert using iterator");

  return  this->insert_from (new_item, iter.current_, &iter.current_);
}

template<class T>

int ACE_Ordered_MultiSet< T >::insert

(

const T &

new_item

)

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

Definition at line 1568 of file Containers_T.cpp.

References ACE_Ordered_MultiSet< T >::insert_from().

{
  // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert");

  return this->insert_from (item, this->head_, 0);
}

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 1670 of file Containers_T.cpp.

References ACE_NEW_MALLOC_RETURN, ACE_Ordered_MultiSet< T >::cur_size_, ACE_Ordered_MultiSet< T >::head_, ACE_Ordered_MultiSet< T >::locate(), ACE_DNode< T >::next_, ACE_DNode< T >::prev_, and ACE_Ordered_MultiSet< T >::tail_.

Referenced by ACE_Ordered_MultiSet< T >::copy_nodes(), and ACE_Ordered_MultiSet< T >::insert().

{
  // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert_from");

  // create a new node
  ACE_DNode<T> *temp = 0;
  ACE_NEW_MALLOC_RETURN (temp,
                         static_cast<ACE_DNode<T>*> (this->allocator_->malloc (sizeof (ACE_DNode<T>))),
                         ACE_DNode<T> (item),
                         -1);
  // obtain approximate location of the node
  int result = locate (item, position, position);

  // if there are nodes in the multiset
  if (position)
    {
      switch (result)
        {
          // insert after the approximate position
        case -1:

          // if there is a following node
          if (position->next_)
            {
              // link up with the following node
              position->next_->prev_ = temp;
              temp->next_ = position->next_;
            }
          else
            // appending to the end of the set
            tail_ = temp;

          // link up with the preceeding node
          temp->prev_ = position;
          position->next_ = temp;

          break;

          // insert before the position
        case  0:
        case  1:

          // if there is a preceeding node
          if (position->prev_)
            {
              // link up with the preceeding node
              position->prev_->next_ = temp;
              temp->prev_ = position->prev_;
            }
          else
            // prepending to the start of the set
            head_ = temp;

          // link up with the preceeding node
          temp->next_ = position;
          position->prev_ = temp;

          break;

        default:
          return -1;
        }
    }
  else
    {
      // point the head and tail to the new node.
      this->head_ = temp;
      this->tail_ = temp;
    }

  ++this->cur_size_;
  if (new_position)
    *new_position = temp;

  return 0;
}

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.inl.

References ACE_TRACE, and ACE_Ordered_MultiSet< T >::cur_size_.

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

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 1749 of file Containers_T.cpp.

References ACE_Ordered_MultiSet< T >::head_, ACE_DNode< T >::item_, ACE_DNode< T >::next_, and ACE_DNode< T >::prev_.

Referenced by ACE_Ordered_MultiSet< T >::find(), ACE_Ordered_MultiSet< T >::insert_from(), and ACE_Ordered_MultiSet< T >::remove().

{
  if (! start_position)
    start_position = this->head_;

  // If starting before the item, move forward until at or just before
  // item.
  while (start_position && start_position->item_ < item &&
         start_position->next_)
    start_position = start_position->next_;

  // If starting after the item, move back until at or just after item
  while (start_position && item < start_position->item_ &&
         start_position->prev_)
    start_position = start_position->prev_;

  // Save the (approximate) location in the passed pointer.
  new_position = start_position;

  // Show the location is after (1), before (-1) , or at (0) the item
  if (!new_position)
    return 1;
  else if (item < new_position->item_)
    return 1;
  else if (new_position->item_ < item)
    return -1;
  else
    return 0;
}

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 1555 of file Containers_T.cpp.

References ACE_TRACE, ACE_Ordered_MultiSet< T >::copy_nodes(), and ACE_Ordered_MultiSet< T >::delete_nodes().

{
  ACE_TRACE ("ACE_Ordered_MultiSet<T>::operator=");

  if (this != &us)
    {
      this->delete_nodes ();
      this->copy_nodes (us);
    }
}

template<class T>

int ACE_Ordered_MultiSet< T >::remove

(

const T &

item

)

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

Definition at line 1585 of file Containers_T.cpp.

References ACE_DES_FREE_TEMPLATE, ACE_Ordered_MultiSet< T >::cur_size_, ACE_Ordered_MultiSet< T >::head_, ACE_Ordered_MultiSet< T >::locate(), ACE_DNode< T >::next_, ACE_DNode< T >::prev_, and ACE_Ordered_MultiSet< T >::tail_.

{
  // ACE_TRACE ("ACE_Ordered_MultiSet<T>::remove");

  ACE_DNode<T> *node = 0;

  int result = locate (item, 0, node);

  // if we found the node, remove from list and free it
  if (node && (result == 0))
    {
      if (node->prev_)
        node->prev_->next_ = node->next_;
      else
        head_ = node->next_;

      if (node->next_)
        node->next_->prev_ = node->prev_;
      else
        tail_ = node->prev_;

      --this->cur_size_;

      ACE_DES_FREE_TEMPLATE (node,
                             this->allocator_->free,
                             ACE_DNode,
                             <T>);
      return 0;
    }

  return -1;
}

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 1639 of file Containers_T.cpp.

References ACE_TRACE, and ACE_Ordered_MultiSet< T >::delete_nodes().

{
  ACE_TRACE ("reset");

  this->delete_nodes ();
}

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.inl.

References ACE_Ordered_MultiSet< T >::cur_size_.

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

---

Friends And Related Function Documentation

template<class T>

friend class ACE_Ordered_MultiSet_Iterator< T > [friend]

Definition at line 1771 of file Containers_T.h.

---

Member Data Documentation

template<class T>

ACE_Ordered_MultiSet< T >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

Definition at line 1861 of file Containers_T.h.

template<class T>

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

Allocation strategy of the set.

Definition at line 1903 of file Containers_T.h.

Referenced by ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet().

template<class T>

size_t ACE_Ordered_MultiSet< T >::cur_size_ [private]

Current size of the set.

Definition at line 1900 of file Containers_T.h.

Referenced by ACE_Ordered_MultiSet< T >::delete_nodes(), ACE_Ordered_MultiSet< T >::insert_from(), ACE_Ordered_MultiSet< T >::is_empty(), ACE_Ordered_MultiSet< T >::remove(), and ACE_Ordered_MultiSet< T >::size().

template<class T>

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

Head of the bilinked list of Nodes.

Definition at line 1894 of file Containers_T.h.

Referenced by ACE_Ordered_MultiSet< T >::copy_nodes(), ACE_Ordered_MultiSet< T >::delete_nodes(), ACE_Ordered_MultiSet< T >::insert_from(), ACE_Ordered_MultiSet< T >::locate(), and ACE_Ordered_MultiSet< T >::remove().

template<class T>

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

Head of the bilinked list of Nodes.

Definition at line 1897 of file Containers_T.h.

Referenced by ACE_Ordered_MultiSet< T >::delete_nodes(), ACE_Ordered_MultiSet< T >::insert_from(), and ACE_Ordered_MultiSet< T >::remove().

---

The documentation for this class was generated from the following files:

• Containers_T.h
• Containers_T.cpp
• Containers_T.inl

---