casacore
Stack.h
Go to the documentation of this file.
1 //# Stack.h: Implementation of a stack using the doubly linked list class
2 //# Copyright (C) 1993,1994,1995,1999,2000
3 //# Associated Universities, Inc. Washington DC, USA.
4 //#
5 //# This library is free software; you can redistribute it and/or modify it
6 //# under the terms of the GNU Library General Public License as published by
7 //# the Free Software Foundation; either version 2 of the License, or (at your
8 //# option) any later version.
9 //#
10 //# This library is distributed in the hope that it will be useful, but WITHOUT
11 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 //# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
13 //# License for more details.
14 //#
15 //# You should have received a copy of the GNU Library General Public License
16 //# along with this library; if not, write to the Free Software Foundation,
17 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
18 //#
19 //# Correspondence concerning AIPS++ should be addressed as follows:
20 //# Internet email: aips2-request@nrao.edu.
21 //# Postal address: AIPS++ Project Office
22 //# National Radio Astronomy Observatory
23 //# 520 Edgemont Road
24 //# Charlottesville, VA 22903-2475 USA
25 //#
26 //# $Id$
27 
28 #ifndef CASA_STACK_H
29 #define CASA_STACK_H
30 
31 #include <casacore/casa/aips.h>
32 #include <casacore/casa/Containers/Link.h>
33 
34 namespace casacore { //# NAMESPACE CASACORE - BEGIN
35 
36 extern void throw_empty_Stack_error(const char *msg = 0);
37 
38 // This class, Stack<t>, defines an implementation of a stack using
39 // the doubly linked list primitive, Link<t>. It has the standard
40 // push and pop operations.
41 //
42 // <summary>
43 // A Last-In-First-Out (LIFO) data structure.
44 // </summary>
45 //
46 // <reviewed reviewer="Gareth Hunt" date="94Jan06" tests="tQueue" demos="">
47 // </reviewed>
48 //
49 // <synopsis>
50 // A Stack as implemented here is a simple container which can grow with time,
51 // and which returns its elements (only) in the inverse order which they are
52 // inserted. That is, the fundamental operations are to push (add) an element
53 // onto the top of the stack and to pop (remove) an element from the top of
54 // the stack. As a result, the last element placed on the stack will be the
55 // first element removed.
56 //
57 // <example>
58 // <srcblock>
59 // Stack<int> one,two;
60 // int count = 0;
61 // one.push(1); // add
62 // one.push(2); // add
63 // one.push(3); // add
64 // one.push(4); // add
65 // while ( !one.empty() ) {
66 // cout << one.top() << " "; // top element
67 // two.push(one.top()); // push = add
68 // one.pop(); // remove top element
69 // }
70 // cout << endl;
71 // while ( !two.empty() ) {
72 // one.push(two.top());
73 // cout << two.popVal() << " "; // remove and return top
74 // }
75 // while ( !one.empty() )
76 // count += one.popVal();
77 // cout << endl << count << endl;;
78 // </srcblock>
79 // This results in the following output:
80 // <pre>
81 // 4 3 2 1
82 // 1 2 3 4
83 // 10
84 // </pre>
85 // <example>
86 //
87 // Presently, this implementation is rather simple. It is built directly
88 // upon the Link class.
89 // </synopsis>
90 //
91 // <motivation>
92 // A simple stack was needed for the (now deprecated) CanDelete class.
93 // </motivation>
94 //
95 // <todo asof="28OCT94">
96 // <li> It is conceivable that an iterator might be useful for this class.
97 // <li> If this class is ever heavily used, a more space efficient
98 // implementation may be necessary.
99 // </todo>
100 //
101 template<class elem> class Stack {
102 private:
103  // Pointer to the top of the stack.
105 public:
106 
107  //
108  // This creates an empty stack.
109  //
110  Stack() : topOfStack(0) {}
111 
112  //
113  // Create a stack by making a copy of other.
114  //
115  Stack(const Stack<elem> &other);
116 
117  //
118  // Create a stack which is a copy of other.
119  //
120  Stack<elem> &operator=(const Stack<elem> &other);
121 
122  ~Stack();
123 
124  //
125  // Add an element to the top of the stack.
126  //
127  void push(const elem &e) {topOfStack = new Link<elem>(e,0,topOfStack);}
128 
129  //
130  // Remove the top element from the top of the stack.
131  //
132  void pop() {
133  if (topOfStack == 0)
134  throw_empty_Stack_error("Invalid operation (pop) on an empty Stack.");
135  Link<elem> *tmp = topOfStack;
136  topOfStack = (*tmp).unlink();
137  delete tmp;
138  }
139 
140  //
141  // Remove the top element from the top of the stack, and return it
142  //
143  elem popVal() {
144  if (topOfStack == 0)
145  throw_empty_Stack_error("Invalid operation (popVal) on an empty Stack.");
146  Link<elem> *tmp = topOfStack;
147  elem ret = (*tmp).val();
148  topOfStack = (*tmp).unlink();
149  delete tmp;
150  return ret;
151  }
152 
153  //
154  // Retreive the top element on the stack.
155  //
156  // <group>
157  elem &top() {
158  if (topOfStack == 0)
159  throw_empty_Stack_error("Invalid operation (top) on an empty Stack.");
160  return((*topOfStack).val());}
161 
162  const elem &top() const {
163  if (topOfStack == 0)
164  throw_empty_Stack_error("Invalid operation (const top) on an empty Stack.");
165  return((*topOfStack).val());}
166  // </group>
167 
168  //
169  // Check to see if the stack is empty.
170  //
171  Bool empty() const { return(topOfStack ? False : True);}
172 };
173 
174 
175 } //# NAMESPACE CASACORE - END
176 
177 #ifndef CASACORE_NO_AUTO_TEMPLATES
178 #include <casacore/casa/Containers/Stack.tcc>
179 #endif //# CASACORE_NO_AUTO_TEMPLATES
180 #endif
Link< elem > * topOfStack
Pointer to the top of the stack.
Definition: Stack.h:104
void push(const elem &e)
Add an element to the top of the stack.
Definition: Stack.h:127
void throw_empty_Stack_error(const char *msg=0)
Bool empty() const
Check to see if the stack is empty.
Definition: Stack.h:171
Stack< elem > & operator=(const Stack< elem > &other)
Create a stack which is a copy of other.
void pop()
Remove the top element from the top of the stack.
Definition: Stack.h:132
This class, Stack<t>, defines an implementation of a stack using the doubly linked list primitive...
Definition: Stack.h:101
const elem & top() const
Definition: Stack.h:162
Stack()
This creates an empty stack.
Definition: Stack.h:110
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:42
const Bool False
Definition: aipstype.h:44
elem & top()
Retreive the top element on the stack.
Definition: Stack.h:157
const Double e
e and functions thereof:
const Bool True
Definition: aipstype.h:43
this file contains all the compiler specific defines
Definition: mainpage.dox:28
elem popVal()
Remove the top element from the top of the stack, and return it.
Definition: Stack.h:143