#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 1768 of file Containers_T.h.
|
Definition at line 1774 of file Containers_T.h. |
|
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().
01519 : head_ (0) 01520 , tail_ (0) 01521 , cur_size_ (0) 01522 , allocator_ (alloc) 01523 { 01524 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet"); 01525 01526 if (this->allocator_ == 0) 01527 this->allocator_ = ACE_Allocator::instance (); 01528 } |
|
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 >::copy_nodes(), and ACE_Allocator::instance().
01532 : head_ (0) 01533 , tail_ (0) 01534 , cur_size_ (0) 01535 , allocator_ (us.allocator_) 01536 { 01537 ACE_TRACE ("ACE_Ordered_MultiSet<T>::ACE_Ordered_MultiSet"); 01538 01539 if (this->allocator_ == 0) 01540 this->allocator_ = ACE_Allocator::instance (); 01541 01542 this->copy_nodes (us); 01543 } |
|
Destructor. Delete the nodes of the set. Definition at line 1546 of file Containers_T.cpp. References ACE_Ordered_MultiSet< T >::delete_nodes().
01547 { 01548 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::~ACE_Ordered_MultiSet"); 01549 01550 this->delete_nodes (); 01551 } |
|
Copy nodes into this set.
Definition at line 1791 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=().
01792 { 01793 ACE_DNode<T> *insertion_point = this->head_; 01794 01795 for (ACE_DNode<T> *curr = us.head_; 01796 curr != 0; 01797 curr = curr->next_) 01798 this->insert_from (curr->item_, insertion_point, &insertion_point); 01799 } |
|
Delete all the nodes in the Set.
Definition at line 1802 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().
01803 { 01804 // iterate through list, deleting nodes 01805 for (ACE_DNode<T> *curr = this->head_; 01806 curr != 0; 01807 ) 01808 { 01809 ACE_DNode<T> *temp = curr; 01810 curr = curr->next_; 01811 ACE_DES_FREE_TEMPLATE (temp, 01812 this->allocator_->free, 01813 ACE_DNode, 01814 <T>); 01815 } 01816 01817 this->head_ = 0; 01818 this->tail_ = 0; 01819 this->cur_size_ = 0; 01820 } |
|
Dump the state of an object.
Definition at line 1647 of file Containers_T.cpp.
01648 { 01649 #if defined (ACE_HAS_DUMP) 01650 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::dump"); 01651 // 01652 // ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); 01653 // ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nhead_ = %u"), this->head_)); 01654 // ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); 01655 // ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); 01656 // 01657 // T *item = 0; 01658 // size_t count = 1; 01659 // 01660 // for (ACE_Ordered_MultiSet_Iterator<T> iter (*(ACE_Ordered_MultiSet<T> *) this); 01661 // iter.next (item) != 0; 01662 // iter.advance ()) 01663 // ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("count = %d\n"), count++)); 01664 // 01665 // ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); 01666 #endif /* ACE_HAS_DUMP */ 01667 } |
|
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< T >::locate().
01621 { 01622 // search an occurance of item, using iterator's current position as a hint 01623 ACE_DNode<T> *node = iter.current_; 01624 int const result = locate (item, node, node); 01625 01626 // if we found the node, update the iterator and indicate success 01627 if (node && (result == 0)) 01628 { 01629 iter.current_ = node; 01630 return 0; 01631 } 01632 01633 return -1; 01634 } |
|
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< T >::insert_from().
01578 { 01579 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert using iterator"); 01580 01581 return this->insert_from (new_item, iter.current_, &iter.current_); 01582 } |
|
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().
01569 { 01570 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert"); 01571 01572 return this->insert_from (item, this->head_, 0); 01573 } |
|
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 >::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().
01672 { 01673 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::insert_from"); 01674 01675 // create a new node 01676 ACE_DNode<T> *temp = 0; 01677 ACE_NEW_MALLOC_RETURN (temp, 01678 static_cast<ACE_DNode<T>*> (this->allocator_->malloc (sizeof (ACE_DNode<T>))), 01679 ACE_DNode<T> (item), 01680 -1); 01681 // obtain approximate location of the node 01682 int result = locate (item, position, position); 01683 01684 // if there are nodes in the multiset 01685 if (position) 01686 { 01687 switch (result) 01688 { 01689 // insert after the approximate position 01690 case -1: 01691 01692 // if there is a following node 01693 if (position->next_) 01694 { 01695 // link up with the following node 01696 position->next_->prev_ = temp; 01697 temp->next_ = position->next_; 01698 } 01699 else 01700 // appending to the end of the set 01701 tail_ = temp; 01702 01703 // link up with the preceeding node 01704 temp->prev_ = position; 01705 position->next_ = temp; 01706 01707 break; 01708 01709 // insert before the position 01710 case 0: 01711 case 1: 01712 01713 // if there is a preceeding node 01714 if (position->prev_) 01715 { 01716 // link up with the preceeding node 01717 position->prev_->next_ = temp; 01718 temp->prev_ = position->prev_; 01719 } 01720 else 01721 // prepending to the start of the set 01722 head_ = temp; 01723 01724 // link up with the preceeding node 01725 temp->next_ = position; 01726 position->prev_ = temp; 01727 01728 break; 01729 01730 default: 01731 return -1; 01732 } 01733 } 01734 else 01735 { 01736 // point the head and tail to the new node. 01737 this->head_ = temp; 01738 this->tail_ = temp; 01739 } 01740 01741 ++this->cur_size_; 01742 if (new_position) 01743 *new_position = temp; 01744 01745 return 0; 01746 } |
|
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 1749 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().
01751 { 01752 if (! start_position) 01753 start_position = this->head_; 01754 01755 // If starting before the item, move forward until at or just before 01756 // item. 01757 while (start_position && start_position->item_ < item && 01758 start_position->next_) 01759 start_position = start_position->next_; 01760 01761 // If starting after the item, move back until at or just after item 01762 while (start_position && item < start_position->item_ && 01763 start_position->prev_) 01764 start_position = start_position->prev_; 01765 01766 // Save the (approximate) location in the passed pointer. 01767 new_position = start_position; 01768 01769 // Show the location is after (1), before (-1) , or at (0) the item 01770 if (!new_position) 01771 return 1; 01772 else if (item < new_position->item_) 01773 return 1; 01774 else if (new_position->item_ < item) 01775 return -1; 01776 else 01777 return 0; 01778 } |
|
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().
01556 { 01557 ACE_TRACE ("ACE_Ordered_MultiSet<T>::operator="); 01558 01559 if (this != &us) 01560 { 01561 this->delete_nodes (); 01562 this->copy_nodes (us); 01563 } 01564 } |
|
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 >::locate(), ACE_DNode< T >::next_, ACE_DNode< T >::prev_, and ACE_Ordered_MultiSet< T >::tail_.
01586 { 01587 // ACE_TRACE ("ACE_Ordered_MultiSet<T>::remove"); 01588 01589 ACE_DNode<T> *node = 0; 01590 01591 int result = locate (item, 0, node); 01592 01593 // if we found the node, remove from list and free it 01594 if (node && (result == 0)) 01595 { 01596 if (node->prev_) 01597 node->prev_->next_ = node->next_; 01598 else 01599 head_ = node->next_; 01600 01601 if (node->next_) 01602 node->next_->prev_ = node->prev_; 01603 else 01604 tail_ = node->prev_; 01605 01606 --this->cur_size_; 01607 01608 ACE_DES_FREE_TEMPLATE (node, 01609 this->allocator_->free, 01610 ACE_DNode, 01611 <T>); 01612 return 0; 01613 } 01614 01615 return -1; 01616 } |
|
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().
01640 { 01641 ACE_TRACE ("reset"); 01642 01643 this->delete_nodes (); 01644 } |
|
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 1771 of file Containers_T.h. |
|
Declare the dynamic allocation hooks.
Definition at line 1861 of file Containers_T.h. |
|
Allocation strategy of the set.
Definition at line 1903 of file Containers_T.h. |
|
Current size of the set.
Definition at line 1900 of file Containers_T.h. |
|
Head of the bilinked list of Nodes.
Definition at line 1894 of file Containers_T.h. Referenced by ACE_Ordered_MultiSet< T >::copy_nodes(). |
|
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(). |