#include <Containers_T.h>
Collaboration diagram for ACE_Ordered_MultiSet< T >:
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 > |
Requirements and Performance Characteristics
Definition at line 1770 of file Containers_T.h.
|
Definition at line 1776 of file Containers_T.h. |
|
Initialize the set using the allocation strategy specified. If none, use the default strategy. Definition at line 1524 of file Containers_T.cpp. References ACE_Allocator::instance().
01525 : head_ (0) 01526 , tail_ (0) 01527 , cur_size_ (0) 01528 , allocator_ (alloc) 01529 { 01530 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet"); 01531 01532 if (this->allocator_ == 0) 01533 this->allocator_ = ACE_Allocator::instance (); 01534 } |
|
Copy constructor. Initialize the set to be a copy of the provided set. Definition at line 1537 of file Containers_T.cpp. References ACE_TRACE, ACE_Ordered_MultiSet< T >::copy_nodes(), and ACE_Allocator::instance().
01538 : head_ (0) 01539 , tail_ (0) 01540 , cur_size_ (0) 01541 , allocator_ (us.allocator_) 01542 { 01543 ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet"); 01544 01545 if (this->allocator_ == 0) 01546 this->allocator_ = ACE_Allocator::instance (); 01547 01548 this->copy_nodes (us); 01549 } |
|
Destructor. Delete the nodes of the set. Definition at line 1552 of file Containers_T.cpp. References ACE_Ordered_MultiSet< T >::delete_nodes().
01553 { 01554 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::~ACE_Ordered_MultiSet"); 01555 01556 this->delete_nodes (); 01557 } |
|
Copy nodes into this set.
Definition at line 1797 of file Containers_T.cpp. References ACE_Ordered_MultiSet< T >::head_, ACE_Ordered_MultiSet< T >::insert_from(), ACE_DNode< T >::item_, and ACE_DNode< T >::next_. Referenced by ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet(), and ACE_Ordered_MultiSet< T >::operator=().
01798 { 01799 ACE_DNode<T> *insertion_point = this->head_; 01800 01801 for (ACE_DNode<T> *curr = us.head_; 01802 curr != 0; 01803 curr = curr->next_) 01804 this->insert_from (curr->item_, insertion_point, &insertion_point); 01805 } |
|
Delete all the nodes in the Set.
Definition at line 1808 of file Containers_T.cpp. References ACE_DES_FREE_TEMPLATE, ACE_DNode< T >::next_, 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().
01809 { 01810 // iterate through list, deleting nodes 01811 for (ACE_DNode<T> *curr = this->head_; 01812 curr != 0; 01813 ) 01814 { 01815 ACE_DNode<T> *temp = curr; 01816 curr = curr->next_; 01817 ACE_DES_FREE_TEMPLATE (temp, 01818 this->allocator_->free, 01819 ACE_DNode, 01820 <T>); 01821 } 01822 01823 this->head_ = 0; 01824 this->tail_ = 0; 01825 this->cur_size_ = 0; 01826 } |
|
Dump the state of an object.
Definition at line 1653 of file Containers_T.cpp.
01654 { 01655 #if defined (ACE_HAS_DUMP) 01656 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::dump"); 01657 // 01658 // ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); 01659 // ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_ = %u"), this->head_)); 01660 // ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); 01661 // ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); 01662 // 01663 // T *item = 0; 01664 // size_t count = 1; 01665 // 01666 // for (ACE_Ordered_MultiSet_Iterator<T> iter (*(ACE_Ordered_MultiSet<T> *) this); 01667 // iter.next (item) != 0; 01668 // iter.advance ()) 01669 // ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("count = %d\n"), count++)); 01670 // 01671 // ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); 01672 #endif /* ACE_HAS_DUMP */ 01673 } |
|
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 1625 of file Containers_T.cpp. References ACE_Ordered_MultiSet< T >::locate().
01627 { 01628 // search an occurance of item, using iterator's current position as a hint 01629 ACE_DNode<T> *node = iter.current_; 01630 int result = locate (item, node, node); 01631 01632 // if we found the node, update the iterator and indicate success 01633 if (node && (result == 0)) 01634 { 01635 iter.current_ = node; 01636 return 0; 01637 } 01638 01639 return -1; 01640 } |
|
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 1582 of file Containers_T.cpp. References ACE_Ordered_MultiSet< T >::insert_from().
01584 { 01585 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert using iterator"); 01586 01587 return this->insert_from (new_item, iter.current_, &iter.current_); 01588 } |
|
Linear time, order preserving insert into the set beginning at the head. Definition at line 1574 of file Containers_T.cpp. References ACE_Ordered_MultiSet< T >::insert_from().
01575 { 01576 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert"); 01577 01578 return this->insert_from (item, this->head_, 0); 01579 } |
|
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 1676 of file Containers_T.cpp. References ACE_NEW_MALLOC_RETURN, 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().
01678 { 01679 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert_from"); 01680 01681 // create a new node 01682 ACE_DNode<T> *temp; 01683 ACE_NEW_MALLOC_RETURN (temp, 01684 static_cast<ACE_DNode<T>*> (this->allocator_->malloc (sizeof (ACE_DNode<T>))), 01685 ACE_DNode<T> (item), 01686 -1); 01687 // obtain approximate location of the node 01688 int result = locate (item, position, position); 01689 01690 // if there are nodes in the multiset 01691 if (position) 01692 { 01693 switch (result) 01694 { 01695 // insert after the approximate position 01696 case -1: 01697 01698 // if there is a following node 01699 if (position->next_) 01700 { 01701 // link up with the following node 01702 position->next_->prev_ = temp; 01703 temp->next_ = position->next_; 01704 } 01705 else 01706 // appending to the end of the set 01707 tail_ = temp; 01708 01709 // link up with the preceeding node 01710 temp->prev_ = position; 01711 position->next_ = temp; 01712 01713 break; 01714 01715 // insert before the position 01716 case 0: 01717 case 1: 01718 01719 // if there is a preceeding node 01720 if (position->prev_) 01721 { 01722 // link up with the preceeding node 01723 position->prev_->next_ = temp; 01724 temp->prev_ = position->prev_; 01725 } 01726 else 01727 // prepending to the start of the set 01728 head_ = temp; 01729 01730 // link up with the preceeding node 01731 temp->next_ = position; 01732 position->prev_ = temp; 01733 01734 break; 01735 01736 default: 01737 return -1; 01738 } 01739 } 01740 else 01741 { 01742 // point the head and tail to the new node. 01743 this->head_ = temp; 01744 this->tail_ = temp; 01745 } 01746 01747 this->cur_size_++; 01748 if (new_position) 01749 *new_position = temp; 01750 01751 return 0; 01752 } |
|
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.
|
|
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 1755 of file Containers_T.cpp. References 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().
01757 { 01758 if (! start_position) 01759 start_position = this->head_; 01760 01761 // If starting before the item, move forward until at or just before 01762 // item. 01763 while (start_position && start_position->item_ < item && 01764 start_position->next_) 01765 start_position = start_position->next_; 01766 01767 // If starting after the item, move back until at or just after item 01768 while (start_position && item < start_position->item_ && 01769 start_position->prev_) 01770 start_position = start_position->prev_; 01771 01772 // Save the (approximate) location in the passed pointer. 01773 new_position = start_position; 01774 01775 // Show the location is after (1), before (-1) , or at (0) the item 01776 if (!new_position) 01777 return 1; 01778 else if (item < new_position->item_) 01779 return 1; 01780 else if (new_position->item_ < item) 01781 return -1; 01782 else 01783 return 0; 01784 } |
|
Assignment operator. Delete the nodes in lhs, and copy the nodes from the rhs. Definition at line 1561 of file Containers_T.cpp. References ACE_TRACE, ACE_Ordered_MultiSet< T >::copy_nodes(), and ACE_Ordered_MultiSet< T >::delete_nodes().
01562 { 01563 ACE_TRACE ("ACE_Ordered_MultiSet<T>::operator="); 01564 01565 if (this != &us) 01566 { 01567 this->delete_nodes (); 01568 this->copy_nodes (us); 01569 } 01570 } |
|
Linear time search operation which removes the item from the set if found . Definition at line 1591 of file Containers_T.cpp. References ACE_DES_FREE_TEMPLATE, ACE_Ordered_MultiSet< T >::locate(), ACE_DNode< T >::next_, ACE_DNode< T >::prev_, and ACE_Ordered_MultiSet< T >::tail_.
01592 { 01593 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::remove"); 01594 01595 ACE_DNode<T> *node = 0; 01596 01597 int result = locate (item, 0, node); 01598 01599 // if we found the node, remove from list and free it 01600 if (node && (result == 0)) 01601 { 01602 if (node->prev_) 01603 node->prev_->next_ = node->next_; 01604 else 01605 head_ = node->next_; 01606 01607 if (node->next_) 01608 node->next_->prev_ = node->prev_; 01609 else 01610 tail_ = node->prev_; 01611 01612 this->cur_size_--; 01613 01614 ACE_DES_FREE_TEMPLATE (node, 01615 this->allocator_->free, 01616 ACE_DNode, 01617 <T>); 01618 return 0; 01619 } 01620 01621 return -1; 01622 } |
|
Reset the ACE_Ordered_MultiSet to be empty. Delete the nodes inside the set. Definition at line 1645 of file Containers_T.cpp. References ACE_TRACE, and ACE_Ordered_MultiSet< T >::delete_nodes().
01646 { 01647 ACE_TRACE ("reset"); 01648 01649 this->delete_nodes (); 01650 } |
|
Size of the set. Constant time check to determine the size of the set. Definition at line 263 of file Containers_T.inl.
00264 { 00265 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::size"); 00266 return this->cur_size_; 00267 } |
|
Definition at line 1773 of file Containers_T.h. |
|
Declare the dynamic allocation hooks.
Definition at line 1863 of file Containers_T.h. |
|
Allocation strategy of the set.
Definition at line 1905 of file Containers_T.h. |
|
Current size of the set.
Definition at line 1902 of file Containers_T.h. |
|
Head of the bilinked list of Nodes.
Definition at line 1896 of file Containers_T.h. Referenced by ACE_Ordered_MultiSet< T >::copy_nodes(). |
|
Head of the bilinked list of Nodes.
Definition at line 1899 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(). |