Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

ACE_Unbounded_Stack Class Template Reference

Implement a generic LIFO abstract data type. More...

#include <Containers_T.h>

Collaboration diagram for ACE_Unbounded_Stack:

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Unbounded_Stack_Iterator<
T > 
ITERATOR

Public Methods

 ACE_Unbounded_Stack (ACE_Allocator *alloc=0)
 Initialize a new stack so that it is empty. Use user defined allocation strategy if specified. More...

 ACE_Unbounded_Stack (const ACE_Unbounded_Stack< T > &s)
 The copy constructor (performs initialization). More...

void operator= (const ACE_Unbounded_Stack< T > &s)
 Assignment operator (performs assignment). More...

 ~ACE_Unbounded_Stack (void)
 Perform actions needed when stack goes out of scope. More...

int push (const T &new_item)
 Push an element onto the top of stack. More...

int pop (T &item)
 Pop the top element of the stack. More...

int top (T &item) const
 Examine the top of the stack. More...

int is_empty (void) const
 Returns 1 if the container is empty, otherwise returns 0. More...

int is_full (void) const
 Returns 1 if the container is full, otherwise returns 0. More...

int insert (const T &new_item)
 Linear Insert of an item. More...

int 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. More...

int find (const T &item) const
 Finds if item occurs the set. Returns 0 if finds, else -1. More...

size_t size (void) const
 The number of items in the stack. More...

void dump (void) const
 Dump the state of an object. More...


Public Attributes

 ACE_ALLOC_HOOK_DECLARE
 Declare the dynamic allocation hooks. More...


Private Methods

void delete_all_nodes (void)
 Delete all the nodes in the stack. More...

void copy_all_nodes (const ACE_Unbounded_Stack< T > &s)
 Copy all nodes from <s> to <this>. More...


Private Attributes

ACE_Node< T > * head_
 Head of the linked list of Nodes. More...

size_t cur_size_
 Current size of the stack. More...

ACE_Allocatorallocator_
 Allocation strategy of the stack. More...


Friends

class ACE_Unbounded_Stack_Iterator< T >

Detailed Description

template<class T>
class ACE_Unbounded_Stack< 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.


Member Typedef Documentation

template<class T>
typedef ACE_Unbounded_Stack_Iterator<T> ACE_Unbounded_Stack::ITERATOR
 

Definition at line 380 of file Containers_T.h.


Constructor & Destructor Documentation

template<class T>
ACE_Unbounded_Stack< T >::ACE_Unbounded_Stack ACE_Allocator   alloc = 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 140 of file Containers_T.cpp.

References ACE_NEW_MALLOC, allocator_, head_, and ACE_Allocator::instance.

00141   : head_ (0),
00142     cur_size_ (0),
00143     allocator_ (alloc)
00144 {
00145   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::ACE_Unbounded_Stack");
00146   if (this->allocator_ == 0)
00147     this->allocator_ = ACE_Allocator::instance ();
00148 
00149   ACE_NEW_MALLOC (this->head_,
00150                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
00151                   ACE_Node<T>);
00152   this->head_->next_ = this->head_;
00153 }

template<class T>
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 197 of file Containers_T.cpp.

References ACE_NEW_MALLOC, allocator_, copy_all_nodes, head_, and ACE_Allocator::instance.

00198   : head_ (0),
00199     cur_size_ (0),
00200     allocator_ (s.allocator_)
00201 {
00202   if (this->allocator_ == 0)
00203     this->allocator_ = ACE_Allocator::instance ();
00204 
00205   ACE_NEW_MALLOC (this->head_,
00206                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
00207                   ACE_Node<T>);
00208   this->head_->next_ = this->head_;
00209 
00210   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::ACE_Unbounded_Stack");
00211   this->copy_all_nodes (s);
00212 }

template<class T>
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 227 of file Containers_T.cpp.

References ACE_DES_FREE_TEMPLATE, delete_all_nodes, and head_.

00228 {
00229   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::~ACE_Unbounded_Stack");
00230 
00231   this->delete_all_nodes ();
00232   ACE_DES_FREE_TEMPLATE (head_,
00233                          this->allocator_->free,
00234                          ACE_Node,
00235                          <T>);
00236 }


Member Function Documentation

template<class 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 175 of file Containers_T.cpp.

References ACE_ASSERT, ACE_NEW_MALLOC, cur_size_, head_, ACE_Node::item_, and ACE_Node::next_.

Referenced by ACE_Unbounded_Stack, and operator=.

00176 {
00177   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::copy_all_nodes");
00178 
00179   ACE_ASSERT (this->head_ == this->head_->next_);
00180 
00181   ACE_Node<T> *temp = this->head_;
00182 
00183   for (ACE_Node<T> *s_temp = s.head_->next_;
00184        s_temp != s.head_;
00185        s_temp = s_temp->next_)
00186     {
00187       ACE_Node<T> *nptr = temp->next_;
00188       ACE_NEW_MALLOC (temp->next_,
00189                       (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
00190                       ACE_Node<T> (s_temp->item_, nptr));
00191       temp = temp->next_;
00192     }
00193   this->cur_size_ = s.cur_size_;
00194 }

template<class T>
void ACE_Unbounded_Stack< T >::delete_all_nodes void    [private]
 

Delete all the nodes in the stack.

Definition at line 156 of file Containers_T.cpp.

References ACE_ASSERT, ACE_DES_FREE_TEMPLATE, cur_size_, head_, is_empty, and ACE_Node::next_.

Referenced by operator=, and ~ACE_Unbounded_Stack.

00157 {
00158   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::delete_all_nodes");
00159 
00160   while (this->is_empty () == 0)
00161     {
00162       ACE_Node<T> *temp = this->head_->next_;
00163       this->head_->next_ = temp->next_;
00164       ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free,
00165                              ACE_Node, <T>);
00166     }
00167 
00168   this->cur_size_ = 0;
00169 
00170   ACE_ASSERT (this->head_ == this->head_->next_
00171               && this->is_empty ());
00172 }

template<class T>
void ACE_Unbounded_Stack< T >::dump void    const
 

Dump the state of an object.

Definition at line 134 of file Containers_T.cpp.

00135 {
00136   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::dump");
00137 }

template<class T>
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 278 of file Containers_T.cpp.

References head_, ACE_Node::item_, and ACE_Node::next_.

Referenced by insert.

00279 {
00280   // ACE_TRACE ("ACE_Unbounded_Stack<T>::find");
00281   // Set <item> into the dummy node.
00282   this->head_->item_ = item;
00283 
00284   ACE_Node<T> *temp = this->head_->next_;
00285 
00286   // Keep looping until we find the item.
00287   while (!(temp->item_ == item))
00288     temp = temp->next_;
00289 
00290   // If we found the dummy node then it's not really there, otherwise,
00291   // it is there.
00292   return temp == this->head_ ? -1 : 0;
00293 }

template<class T>
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 296 of file Containers_T.cpp.

References find, and push.

00297 {
00298   // ACE_TRACE ("ACE_Unbounded_Stack<T>::insert");
00299 
00300   if (this->find (item) == 0)
00301     return 1;
00302   else
00303     return this->push (item);
00304 }

template<class T>
ACE_INLINE int ACE_Unbounded_Stack< T >::is_empty void    const
 

Returns 1 if the container is empty, otherwise returns 0.

Constant time check to see if the stack is empty.

Definition at line 127 of file Containers_T.i.

References head_.

Referenced by delete_all_nodes, pop, and top.

00128 {
00129   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::is_empty");
00130   return this->head_ == this->head_->next_;
00131 }

template<class T>
ACE_INLINE int ACE_Unbounded_Stack< T >::is_full void    const
 

Returns 1 if the container is full, otherwise returns 0.

Always resturns 0 since the stack is unbounded.

Definition at line 147 of file Containers_T.i.

References ACE_TRACE.

00148 {
00149   ACE_TRACE ("ACE_Unbounded_Stack<T>::is_full");
00150   return 0; // ???
00151 }

template<class T>
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 215 of file Containers_T.cpp.

References copy_all_nodes, and delete_all_nodes.

00216 {
00217   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::operator=");
00218 
00219   if (this != &s)
00220     {
00221       this->delete_all_nodes ();
00222       this->copy_all_nodes (s);
00223     }
00224 }

template<class T>
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 256 of file Containers_T.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, is_empty, ACE_Node::item_, and ACE_Node::next_.

00257 {
00258   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::pop");
00259 
00260   if (this->is_empty ())
00261     return -1;
00262   else
00263     {
00264       ACE_Node<T> *temp = this->head_->next_;
00265       item = temp->item_;
00266       this->head_->next_ = temp->next_;
00267 
00268       ACE_DES_FREE_TEMPLATE (temp,
00269                              this->allocator_->free,
00270                              ACE_Node,
00271                              <T>);
00272       this->cur_size_--;
00273       return 0;
00274     }
00275 }

template<class T>
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 239 of file Containers_T.cpp.

References ACE_NEW_MALLOC_RETURN, cur_size_, and head_.

Referenced by insert.

00240 {
00241   //  ACE_TRACE ("ACE_Unbounded_Stack<T>::push");
00242 
00243   ACE_Node<T> *temp;
00244 
00245   ACE_NEW_MALLOC_RETURN (temp,
00246                          ACE_static_cast(ACE_Node<T> *,
00247                                          this->allocator_->malloc (sizeof (ACE_Node<T>))),
00248                          ACE_Node<T> (new_item, this->head_->next_),
00249                          -1);
00250   this->head_->next_ = temp;
00251   this->cur_size_++;
00252   return 0;
00253 }

template<class T>
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 307 of file Containers_T.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, and ACE_Node::next_.

00308 {
00309   // ACE_TRACE ("ACE_Unbounded_Stack<T>::remove");
00310 
00311   // Insert the item to be founded into the dummy node.
00312   this->head_->item_ = item;
00313 
00314   ACE_Node<T> *curr = this->head_;
00315 
00316   while (!(curr->next_->item_ == item))
00317     curr = curr->next_;
00318 
00319   if (curr->next_ == this->head_)
00320     return -1; // Item was not found.
00321   else
00322     {
00323       ACE_Node<T> *temp = curr->next_;
00324       // Skip over the node that we're deleting.
00325       curr->next_ = temp->next_;
00326       this->cur_size_--;
00327       ACE_DES_FREE_TEMPLATE (temp,
00328                              this->allocator_->free,
00329                              ACE_Node,
00330                              <T>);
00331       return 0;
00332     }
00333 }

template<class T>
ACE_INLINE size_t ACE_Unbounded_Stack< T >::size void    const
 

The number of items in the stack.

Constant time access to the current stack size.

Definition at line 154 of file Containers_T.i.

References cur_size_.

00155 {
00156   return this->cur_size_;
00157 }

template<class T>
ACE_INLINE int ACE_Unbounded_Stack< T >::top T &    item const
 

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 134 of file Containers_T.i.

References ACE_TRACE, head_, and is_empty.

00135 {
00136   ACE_TRACE ("ACE_Unbounded_Stack<T>::top");
00137   if (this->is_empty () == 0)
00138     {
00139       item = this->head_->next_->item_;
00140       return 0;
00141     }
00142   else
00143     return -1;
00144 }


Friends And Related Function Documentation

template<class T>
friend class ACE_Unbounded_Stack_Iterator< T > [friend]
 

Definition at line 377 of file Containers_T.h.


Member Data Documentation

template<class T>
ACE_Unbounded_Stack::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 483 of file Containers_T.h.

template<class T>
ACE_Allocator* ACE_Unbounded_Stack::allocator_ [private]
 

Allocation strategy of the stack.

Definition at line 499 of file Containers_T.h.

Referenced by ACE_Unbounded_Stack.

template<class T>
size_t ACE_Unbounded_Stack::cur_size_ [private]
 

Current size of the stack.

Definition at line 496 of file Containers_T.h.

Referenced by copy_all_nodes, delete_all_nodes, pop, push, remove, and size.

template<class T>
ACE_Node<T>* ACE_Unbounded_Stack::head_ [private]
 

Head of the linked list of Nodes.

Definition at line 493 of file Containers_T.h.

Referenced by ACE_Unbounded_Stack, copy_all_nodes, delete_all_nodes, find, is_empty, pop, push, remove, top, and ~ACE_Unbounded_Stack.


The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:58:55 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002