Mercurial > ~dholland > hg > ag > index.cgi

comparison oldclasslib/include/stack.h @ 0:13d2b8934445

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import AnaGram (near-)release tree into Mercurial.
author David A. Holland
date Sat, 22 Dec 2007 17:52:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:13d2b8934445
1 /*
2 * AnaGram, a System for Syntax Directed Programming
3 *
4 * Stack Class Definition
5 *
6 * Please note that the entire class is defined in this module. There
7 * is no supplementary code module.
8 *
9 * Copyright 1993 Parsifal Software. All Rights Reserved.
10 *
11 * This software is provided 'as-is', without any express or implied
12 * warranty. In no event will the authors be held liable for any damages
13 * arising from the use of this software.
14 *
15 * Permission is granted to anyone to use this software for any purpose,
16 * including commercial applications, and to alter it and redistribute it
17 * freely, subject to the following restrictions:
18 *
19 * 1. The origin of this software must not be misrepresented; you must not
20 * claim that you wrote the original software. If you use this software
21 * in a product, an acknowledgment in the product documentation would be
22 * appreciated but is not required.
23 * 2. Altered source versions must be plainly marked as such, and must not be
24 * misrepresented as being the original software.
25 * 3. This notice may not be removed or altered from any source distribution.
26 */
27
28 #ifndef STACK_H
29 #define STACK_H
30
31 #include <assert.h>
32
33 // Some forward decls required in current C++
34 template <class T> class stack;
35 template <class T> stack <T> &reset(stack <T> &s);
36 template <class T> unsigned size(const stack <T> &s);
37
38
39 template <class T>
40 class stack {
41 protected:
42 T *cs; // data storage
43 unsigned *ls; // index (level) storage
44 unsigned sx; // stack index
45 unsigned lx; // level index
46 unsigned sxmax; // max stack index
47 unsigned lxmax; // max level index
48 int copy_flag; // is it live or memorex?
49 public:
50
51
52 // Constructor
53
54 stack(unsigned n, unsigned m) { // (storage request, levels)
55 cs = new T[n]; // allocate data storage
56 ls = new unsigned[m]; // allocate index storage
57 lx = lxmax = m; // set up for pre-decrement push
58 sx = sxmax = n; // post-increment pop
59 ls[--lx] = sx; // init first level
60 copy_flag = 0; // live
61 }
62
63 stack(unsigned n) { // (storage request)
64 unsigned m = 1; // single level
65 cs = new T[n]; // allocate data storage
66 ls = new unsigned[m]; // allocate index storage
67 lx = lxmax = m; // set up for pre-decrement push
68 sx = sxmax = n; // post-increment pop
69 ls[--lx] = sx; // init first level
70 copy_flag = 0; // live
71 }
72
73 stack(stack<T> &s) {
74 *this = s;
75 copy_flag++; // memorex
76 }
77
78
79 // Destructor
80
81 ~stack() {
82 if (copy_flag) return;
83 delete [] cs;
84 delete [] ls;
85 }
86
87
88 // Reset function
89 #ifdef __IBMCPP__
90 friend stack<T> &reset(stack<T> &s);
91 #else
92 friend stack<T> &reset<>(stack<T> &s);
93 #endif
94
95
96 // Change levels
97
98 stack<T> &operator ++() { // next level -- preincrement
99 assert(copy_flag == 0);
100 assert(lx); // not going to overflow
101 ls[--lx] = sx; // push storage index
102 return *this;
103 }
104
105 stack<T> operator ++(int); // next level -- postincrement
106
107 stack<T> &operator --() { // previous level -- predecrement
108 assert(copy_flag == 0);
109 sx = ls[lx++]; // restore storage index
110 assert(lx < lxmax); // no underflow
111 return *this;
112 }
113
114 stack<T> operator --(int); // previous level -- postdecrement
115
116
117 // Push data
118
119 stack<T> &operator << (T t) { // push data
120 assert(copy_flag == 0);
121 assert(sx && lx < lxmax); // everything's ok
122 cs[--sx] = t; // save it
123 return *this;
124 }
125
126
127 // Pop data
128
129 stack<T> &operator >> (T &t) { // pop data
130 assert(copy_flag == 0);
131 assert(lx < lxmax && sx < ls[lx]); // all's well
132 t = cs[sx++]; // get it
133 return *this;
134 }
135
136
137 // Access stack element
138
139 T &operator[] (unsigned k) { // access stack element
140 assert(lx < lxmax && sx + k < ls[lx]); // legitimate index
141 return cs[sx+k]; // reference data
142 }
143
144
145 // Pointer to top element
146
147 // See README.txt
148 #if 0
149 operator T * () {
150 return &cs[sx];
151 }
152 #endif
153 T *top() {
154 return &cs[sx];
155 }
156
157
158 // Get size of stack
159
160 #ifdef __IBMCPP__
161 friend unsigned size(const stack <T> &s); // size at current level
162 #else
163 friend unsigned size<>(const stack <T> &s); // size at current level
164 #endif
165
166 };
167
168 template <class T>
169 inline stack <T> &reset(stack <T> &s) {
170 assert(s.copy_flag == 0);
171 s.lx = s.lxmax; // set up for pre-decrement push
172 s.sx = s.sxmax; // post-increment pop
173 s.ls[--s.lx] = s.sx; // init first level
174 return s;
175 }
176
177 template <class T>
178 inline unsigned size(const stack <T> &s) { // size at current level
179 return s.ls[s.lx] - s.sx;
180 }
181
182
183 template <class T>
184 stack<T> stack<T>::operator ++(int) { // next level -- postintcrement
185 stack<T> cpy(*this); // make copy for return value
186 assert(copy_flag == 0);
187 assert(lx);
188 ls[--lx] = sx;
189 return cpy;
190 }
191
192 template <class T>
193 stack<T> stack<T>::operator --(int) { // previous level -- postdecrement
194 stack <T> cpy(*this); // make copy for return value
195 assert(copy_flag == 0);
196 sx = ls[lx++]; // restore storage index
197 assert(lx < lxmax); // no underflow
198 return cpy;
199 }
200 #endif