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>
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 > |
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 1817 of file Containers_T.h.
| typedef ACE_Ordered_MultiSet_Iterator<T> ACE_Ordered_MultiSet< T >::ITERATOR |
Definition at line 1823 of file Containers_T.h.
| ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet | ( | ACE_Allocator * | the_allocator = 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 1520 of file Containers_T.cpp.
: 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 (); }
| ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet | ( | const ACE_Ordered_MultiSet< T > & | us | ) |
Copy constructor.
Initialize the set to be a copy of the provided set.
Definition at line 1533 of file Containers_T.cpp.
: 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); }
| ACE_Ordered_MultiSet< T >::~ACE_Ordered_MultiSet | ( | void | ) |
Destructor.
Delete the nodes of the set.
Definition at line 1548 of file Containers_T.cpp.
{
// ACE_TRACE ("ACE_Ordered_MultiSet<T>::~ACE_Ordered_MultiSet");
this->delete_nodes ();
}
| void ACE_Ordered_MultiSet< T >::copy_nodes | ( | const ACE_Ordered_MultiSet< T > & | us | ) | [private] |
Copy nodes into this set.
Definition at line 1793 of file Containers_T.cpp.
{
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);
}
| void ACE_Ordered_MultiSet< T >::delete_nodes | ( | void | ) | [private] |
Delete all the nodes in the Set.
Definition at line 1804 of file Containers_T.cpp.
{
// 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;
}
| void ACE_Ordered_MultiSet< T >::dump | ( | void | ) | const |
Dump the state of an object.
Definition at line 1649 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 */
}
| 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 1621 of file Containers_T.cpp.
{
// 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;
}
| 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 1578 of file Containers_T.cpp.
{
// ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert using iterator");
return this->insert_from (new_item, iter.current_, &iter.current_);
}
| 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 1570 of file Containers_T.cpp.
{
// ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert");
return this->insert_from (item, this->head_, 0);
}
| 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 1672 of file Containers_T.cpp.
{
// 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;
}
| int ACE_Ordered_MultiSet< T >::is_empty | ( | void | ) | const [inline] |
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.
| 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 1751 of file Containers_T.cpp.
{
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;
}
| void ACE_Ordered_MultiSet< T >::operator= | ( | const ACE_Ordered_MultiSet< T > & | us | ) |
Assignment operator.
Delete the nodes in lhs, and copy the nodes from the rhs.
Definition at line 1557 of file Containers_T.cpp.
{
ACE_TRACE ("ACE_Ordered_MultiSet<T>::operator=");
if (this != &us)
{
this->delete_nodes ();
this->copy_nodes (us);
}
}
| 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 1587 of file Containers_T.cpp.
{
// 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;
}
| void ACE_Ordered_MultiSet< T >::reset | ( | void | ) |
Reset the ACE_Ordered_MultiSet to be empty.
Delete the nodes inside the set.
Definition at line 1641 of file Containers_T.cpp.
{
ACE_TRACE ("reset");
this->delete_nodes ();
}
| size_t ACE_Ordered_MultiSet< T >::size | ( | void | ) | const [inline] |
Size of the set.
Constant time check to determine the size of the set.
Definition at line 263 of file Containers_T.inl.
{
// ACE_TRACE ("ACE_Ordered_MultiSet<T>::size");
return this->cur_size_;
}
friend class ACE_Ordered_MultiSet_Iterator< T > [friend] |
Definition at line 1820 of file Containers_T.h.
| ACE_Ordered_MultiSet< T >::ACE_ALLOC_HOOK_DECLARE |
Declare the dynamic allocation hooks.
Definition at line 1910 of file Containers_T.h.
ACE_Allocator* ACE_Ordered_MultiSet< T >::allocator_ [private] |
Allocation strategy of the set.
Definition at line 1952 of file Containers_T.h.
size_t ACE_Ordered_MultiSet< T >::cur_size_ [private] |
Current size of the set.
Definition at line 1949 of file Containers_T.h.
ACE_DNode<T>* ACE_Ordered_MultiSet< T >::head_ [private] |
Head of the bilinked list of Nodes.
Definition at line 1943 of file Containers_T.h.
ACE_DNode<T>* ACE_Ordered_MultiSet< T >::tail_ [private] |
Head of the bilinked list of Nodes.
Definition at line 1946 of file Containers_T.h.
1.7.0