casacore
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 #ifndef AIPS_USE_DEPRECATED
32 #error "Stack.h is deprecated; use -DBUILD_DEPRECATED=ON to use it"
33 #endif
34 
35 #include <casacore/casa/aips.h>
37 
38 namespace casacore { //# NAMESPACE CASACORE - BEGIN
39 
40 extern void throw_empty_Stack_error(const char *msg = 0);
41 
42 // This class, Stack<t>, defines an implementation of a stack using
43 // the doubly linked list primitive, Link<t>. It has the standard
44 // push and pop operations.
45 //
46 // <summary>
47 // A Last-In-First-Out (LIFO) data structure.
48 // </summary>
49 //
50 // <reviewed reviewer="Gareth Hunt" date="94Jan06" tests="tQueue" demos="">
51 // </reviewed>
52 //
53 // <synopsis>
54 // A Stack as implemented here is a simple container which can grow with time,
55 // and which returns its elements (only) in the inverse order which they are
56 // inserted. That is, the fundamental operations are to push (add) an element
57 // onto the top of the stack and to pop (remove) an element from the top of
58 // the stack. As a result, the last element placed on the stack will be the
59 // first element removed.
60 //
61 // <example>
62 // <srcblock>
63 // Stack<int> one,two;
64 // int count = 0;
65 // one.push(1); // add
66 // one.push(2); // add
67 // one.push(3); // add
68 // one.push(4); // add
69 // while ( !one.empty() ) {
70 // cout << one.top() << " "; // top element
71 // two.push(one.top()); // push = add
72 // one.pop(); // remove top element
73 // }
74 // cout << endl;
75 // while ( !two.empty() ) {
76 // one.push(two.top());
77 // cout << two.popVal() << " "; // remove and return top
78 // }
79 // while ( !one.empty() )
80 // count += one.popVal();
81 // cout << endl << count << endl;;
82 // </srcblock>
83 // This results in the following output:
84 // <pre>
85 // 4 3 2 1
86 // 1 2 3 4
87 // 10
88 // </pre>
89 // <example>
90 //
91 // Presently, this implementation is rather simple. It is built directly
92 // upon the Link class.
93 // </synopsis>
94 //
95 // <motivation>
96 // A simple stack was needed for the (now deprecated) CanDelete class.
97 // </motivation>
98 //
99 // <todo asof="28OCT94">
100 // <li> It is conceivable that an iterator might be useful for this class.
101 // <li> If this class is ever heavily used, a more space efficient
102 // implementation may be necessary.
103 // </todo>
104 //
105 template<class elem> class Stack {
106 private:
107  // Pointer to the top of the stack.
109 public:
110 
111  //
112  // This creates an empty stack.
113  //
114  Stack() : topOfStack(0) {}
115 
116  //
117  // Create a stack by making a copy of other.
118  //
119  Stack(const Stack<elem> &other);
120 
121  //
122  // Create a stack which is a copy of other.
123  //
124  Stack<elem> &operator=(const Stack<elem> &other);
125 
126  ~Stack();
127 
128  //
129  // Add an element to the top of the stack.
130  //
131  void push(const elem &e) {topOfStack = new Link<elem>(e,0,topOfStack);}
132 
133  //
134  // Remove the top element from the top of the stack.
135  //
136  void pop() {
137  if (topOfStack == 0)
138  throw_empty_Stack_error("Invalid operation (pop) on an empty Stack.");
139  Link<elem> *tmp = topOfStack;
140  topOfStack = (*tmp).unlink();
141  delete tmp;
142  }
143 
144  //
145  // Remove the top element from the top of the stack, and return it
146  //
147  elem popVal() {
148  if (topOfStack == 0)
149  throw_empty_Stack_error("Invalid operation (popVal) on an empty Stack.");
150  Link<elem> *tmp = topOfStack;
151  elem ret = (*tmp).val();
152  topOfStack = (*tmp).unlink();
153  delete tmp;
154  return ret;
155  }
156 
157  //
158  // Retreive the top element on the stack.
159  //
160  // <group>
161  elem &top() {
162  if (topOfStack == 0)
163  throw_empty_Stack_error("Invalid operation (top) on an empty Stack.");
164  return((*topOfStack).val());}
165 
166  const elem &top() const {
167  if (topOfStack == 0)
168  throw_empty_Stack_error("Invalid operation (const top) on an empty Stack.");
169  return((*topOfStack).val());}
170  // </group>
171 
172  //
173  // Check to see if the stack is empty.
174  //
175  Bool empty() const { return(topOfStack ? False : True);}
176 };
177 
178 
179 } //# NAMESPACE CASACORE - END
180 
181 #ifndef CASACORE_NO_AUTO_TEMPLATES
182 #include <casacore/casa/Containers/Stack.tcc>
183 #endif //# CASACORE_NO_AUTO_TEMPLATES
184 #endif
Link< elem > * topOfStack
Pointer to the top of the stack.
Definition: Stack.h:108
void push(const elem &e)
Add an element to the top of the stack.
Definition: Stack.h:131
void throw_empty_Stack_error(const char *msg=0)
const elem & top() const
Definition: Stack.h:166
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:136
This class, Stack&lt;t&gt;, defines an implementation of a stack using the doubly linked list primitive...
Definition: Stack.h:105
Bool empty() const
Check to see if the stack is empty.
Definition: Stack.h:175
Stack()
This creates an empty stack.
Definition: Stack.h:114
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:161
const Double e
e and functions thereof:
const Bool True
Definition: aipstype.h:43
elem popVal()
Remove the top element from the top of the stack, and return it.
Definition: Stack.h:147