Implement a generic LIFO abstract data type. More...
#include <Containers_T.h>
Public Types | |
typedef ACE_Unbounded_Stack_Iterator < T > | ITERATOR |
Public Member Functions | |
ACE_Unbounded_Stack (ACE_Allocator *the_allocator=0) | |
ACE_Unbounded_Stack (const ACE_Unbounded_Stack< T > &s) | |
The copy constructor (performs initialization). | |
void | operator= (const ACE_Unbounded_Stack< T > &s) |
Assignment operator (performs assignment). | |
~ACE_Unbounded_Stack (void) | |
Perform actions needed when stack goes out of scope. | |
int | push (const T &new_item) |
Push an element onto the top of stack. | |
int | pop (T &item) |
Pop the top element of the stack. | |
int | top (T &item) const |
Examine the top of the stack. | |
int | is_empty (void) const |
Returns 1 if the container is empty, otherwise returns 0. | |
int | is_full (void) const |
Returns 1 if the container is full, otherwise returns 0. | |
int | insert (const T &new_item) |
Linear Insert of an item. | |
int | remove (const T &item) |
int | find (const T &item) const |
Finds if item occurs the set. Returns 0 if finds, else -1. | |
size_t | size (void) const |
The number of items in the stack. | |
void | dump (void) const |
Dump the state of an object. | |
Public Attributes | |
ACE_ALLOC_HOOK_DECLARE | |
Declare the dynamic allocation hooks. | |
Private Member Functions | |
void | delete_all_nodes (void) |
Delete all the nodes in the stack. | |
void | copy_all_nodes (const ACE_Unbounded_Stack< T > &s) |
Copy all nodes from {s} to {this}. | |
Private Attributes | |
ACE_Node< T > * | head_ |
Head of the linked list of Nodes. | |
size_t | cur_size_ |
Current size of the stack. | |
ACE_Allocator * | allocator_ |
Allocation strategy of the stack. | |
Friends | |
class | ACE_Unbounded_Stack_Iterator< T > |
Implement a generic LIFO abstract data type.
This implementation of an unbounded Stack uses a linked list. If you use the {insert} or {remove} methods you should keep in mind that duplicate entries aren't allowed. In general, therefore, you should avoid the use of these methods since they aren't really part of the ADT stack. The stack is implemented as a doubly linked list.
Requirements and Performance Characteristics
Definition at line 374 of file Containers_T.h.
typedef ACE_Unbounded_Stack_Iterator<T> ACE_Unbounded_Stack< T >::ITERATOR |
Definition at line 380 of file Containers_T.h.
ACE_Unbounded_Stack< T >::ACE_Unbounded_Stack | ( | ACE_Allocator * | the_allocator = 0 |
) |
Initialize a new stack so that it is empty. Use user defined allocation strategy if specified. Initialize an empty stack using the user specified allocation strategy if provided.
Definition at line 147 of file Containers_T.cpp.
: head_ (0), cur_size_ (0), allocator_ (alloc) { // ACE_TRACE ("ACE_Unbounded_Stack<T>::ACE_Unbounded_Stack"); if (this->allocator_ == 0) this->allocator_ = ACE_Allocator::instance (); ACE_NEW_MALLOC (this->head_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T>); this->head_->next_ = this->head_; }
ACE_Unbounded_Stack< T >::ACE_Unbounded_Stack | ( | const ACE_Unbounded_Stack< T > & | s | ) |
The copy constructor (performs initialization).
Initialize this stack to be an exact copy of {s}.
Definition at line 204 of file Containers_T.cpp.
: head_ (0), cur_size_ (0), allocator_ (s.allocator_) { if (this->allocator_ == 0) this->allocator_ = ACE_Allocator::instance (); ACE_NEW_MALLOC (this->head_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T>); this->head_->next_ = this->head_; // ACE_TRACE ("ACE_Unbounded_Stack<T>::ACE_Unbounded_Stack"); this->copy_all_nodes (s); }
ACE_Unbounded_Stack< T >::~ACE_Unbounded_Stack | ( | void | ) |
Perform actions needed when stack goes out of scope.
Destroy the underlying list for the stack.
Definition at line 234 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::~ACE_Unbounded_Stack"); this->delete_all_nodes (); ACE_DES_FREE_TEMPLATE (head_, this->allocator_->free, ACE_Node, <T>); }
void ACE_Unbounded_Stack< T >::copy_all_nodes | ( | const ACE_Unbounded_Stack< T > & | s | ) | [private] |
Copy all nodes from {s} to {this}.
Definition at line 182 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::copy_all_nodes"); ACE_ASSERT (this->head_ == this->head_->next_); ACE_Node<T> *temp = this->head_; for (ACE_Node<T> *s_temp = s.head_->next_; s_temp != s.head_; s_temp = s_temp->next_) { ACE_Node<T> *nptr = temp->next_; ACE_NEW_MALLOC (temp->next_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T> (s_temp->item_, nptr)); temp = temp->next_; } this->cur_size_ = s.cur_size_; }
void ACE_Unbounded_Stack< T >::delete_all_nodes | ( | void | ) | [private] |
Delete all the nodes in the stack.
Definition at line 163 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::delete_all_nodes"); while (this->is_empty () == 0) { ACE_Node<T> *temp = this->head_->next_; this->head_->next_ = temp->next_; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); } this->cur_size_ = 0; ACE_ASSERT (this->head_ == this->head_->next_ && this->is_empty ()); }
void ACE_Unbounded_Stack< T >::dump | ( | void | ) | const |
Dump the state of an object.
Definition at line 139 of file Containers_T.cpp.
{ #if defined (ACE_HAS_DUMP) // ACE_TRACE ("ACE_Unbounded_Stack<T>::dump"); #endif /* ACE_HAS_DUMP */ }
int ACE_Unbounded_Stack< T >::find | ( | const T & | item | ) | const |
Finds if item occurs the set. Returns 0 if finds, else -1.
Linear find operation.
Definition at line 284 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::find"); // Set <item> into the dummy node. this->head_->item_ = item; ACE_Node<T> *temp = this->head_->next_; // Keep looping until we find the item. while (!(temp->item_ == item)) temp = temp->next_; // If we found the dummy node then it's not really there, otherwise, // it is there. return temp == this->head_ ? -1 : 0; }
int ACE_Unbounded_Stack< T >::insert | ( | const T & | new_item | ) |
Linear Insert of an item.
Insert {new_item} into the Stack at the head (but doesn't allow duplicates). Returns -1 if failures occur, 1 if item is already present (i.e., no duplicates are allowed), else 0.
Definition at line 302 of file Containers_T.cpp.
int ACE_Unbounded_Stack< T >::is_empty | ( | void | ) | const [inline] |
Returns 1 if the container is empty, otherwise returns 0.
Constant time check to see if the stack is empty.
Definition at line 128 of file Containers_T.inl.
int ACE_Unbounded_Stack< T >::is_full | ( | void | ) | const [inline] |
Returns 1 if the container is full, otherwise returns 0.
Always resturns 0 since the stack is unbounded.
Definition at line 148 of file Containers_T.inl.
{ ACE_TRACE ("ACE_Unbounded_Stack<T>::is_full"); return 0; // ??? }
void ACE_Unbounded_Stack< T >::operator= | ( | const ACE_Unbounded_Stack< T > & | s | ) |
Assignment operator (performs assignment).
Perform a deep copy of the rhs into the lhs.
Definition at line 222 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::operator="); if (this != &s) { this->delete_all_nodes (); this->copy_all_nodes (s); } }
int ACE_Unbounded_Stack< T >::pop | ( | T & | item | ) |
Pop the top element of the stack.
Remove and return the top stack item. Returns -1 if the stack is already empty, 0 if the stack is not already empty, and -1 if failure occurs.
Definition at line 262 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::pop"); if (this->is_empty ()) return -1; else { ACE_Node<T> *temp = this->head_->next_; item = temp->item_; this->head_->next_ = temp->next_; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); --this->cur_size_; return 0; } }
int ACE_Unbounded_Stack< T >::push | ( | const T & | new_item | ) |
Push an element onto the top of stack.
Place a new item on top of the stack. Returns -1 if the stack is already full, 0 if the stack is not already full, and -1 if failure occurs.
Definition at line 246 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::push"); ACE_Node<T> *temp = 0; ACE_NEW_MALLOC_RETURN (temp, static_cast<ACE_Node<T> *> (this->allocator_->malloc (sizeof (ACE_Node<T>))), ACE_Node<T> (new_item, this->head_->next_), -1); this->head_->next_ = temp; ++this->cur_size_; return 0; }
int ACE_Unbounded_Stack< T >::remove | ( | const T & | item | ) |
Remove item from the Stack. Returns 0 if it removes the item, -1 if it can't find the item, and -1 if a failure occurs. Linear remove operation.
Definition at line 313 of file Containers_T.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Stack<T>::remove"); // Insert the item to be founded into the dummy node. this->head_->item_ = item; ACE_Node<T> *curr = this->head_; while (!(curr->next_->item_ == item)) curr = curr->next_; if (curr->next_ == this->head_) return -1; // Item was not found. else { ACE_Node<T> *temp = curr->next_; // Skip over the node that we're deleting. curr->next_ = temp->next_; --this->cur_size_; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); return 0; } }
size_t ACE_Unbounded_Stack< T >::size | ( | void | ) | const [inline] |
The number of items in the stack.
Constant time access to the current stack size.
Definition at line 155 of file Containers_T.inl.
{ return this->cur_size_; }
int ACE_Unbounded_Stack< T >::top | ( | T & | item | ) | const [inline] |
Examine the top of the stack.
Return top stack item without removing it. Returns -1 if the stack is already empty, 0 if the stack is not already empty, and -1 if failure occurs.
Definition at line 135 of file Containers_T.inl.
friend class ACE_Unbounded_Stack_Iterator< T > [friend] |
Definition at line 377 of file Containers_T.h.
ACE_Unbounded_Stack< T >::ACE_ALLOC_HOOK_DECLARE |
Declare the dynamic allocation hooks.
Definition at line 483 of file Containers_T.h.
ACE_Allocator* ACE_Unbounded_Stack< T >::allocator_ [private] |
Allocation strategy of the stack.
Definition at line 499 of file Containers_T.h.
size_t ACE_Unbounded_Stack< T >::cur_size_ [private] |
Current size of the stack.
Definition at line 496 of file Containers_T.h.
ACE_Node<T>* ACE_Unbounded_Stack< T >::head_ [private] |
Head of the linked list of Nodes.
Definition at line 493 of file Containers_T.h.