1 /*******************************************************************************
2
3 copyright: Copyright (c) 2008 Kris Bell. All rights reserved
4
5 license: BSD style: $(LICENSE)
6
7 version: Initial release: April 2008
8
9 author: Kris
10
11 Since: 0.99.7
12
13 *******************************************************************************/
14
15 module tango.util.container.more.Stack;
16
17 private import tango.core.Exception : RangeError;
18
19 /******************************************************************************
20
21 A stack of the given value-type V, with maximum depth Size. Note
22 that this does no memory allocation of its own when Size != 0, and
23 does heap allocation when Size == 0. Thus you can have a fixed-size
24 low-overhead instance, or a heap oriented instance.
25
26 ******************************************************************************/
27
28 struct Stack (V, int Size = 0)
29 {
30 alias nth opIndex;
31 alias slice opSlice;
32
33 Stack* opOpAssign(immutable(char)[] s : ">>")(uint d)
34 {
35 return rotateRight(d);
36 }
37
38 Stack* opOpAssign(immutable(char)[] s : "<<")(uint d)
39 {
40 return rotateLeft(d);
41 }
42
43 Stack* opOpAssign(immutable(char)[] s : "~")(V value)
44 {
45 return push(value);
46 }
47
48 static if (Size == 0)
49 {
50 private uint depth;
51 private V[] stack;
52 }
53 else
54 {
55 private uint depth;
56 private V[Size] stack;
57 }
58
59 /***********************************************************************
60
61 Clear the stack
62
63 ***********************************************************************/
64
65 Stack* clear ()
66 {
67 depth = 0;
68 return &this;
69 }
70
71 /***********************************************************************
72
73 Return depth of the stack
74
75 ***********************************************************************/
76
77 @property size_t size ()
78 {
79 return depth;
80 }
81
82 /***********************************************************************
83
84 Return remaining unused slots
85
86 ***********************************************************************/
87
88 size_t unused ()
89 {
90 return stack.length - depth;
91 }
92
93 /***********************************************************************
94
95 Returns a (shallow) clone of this stack, on the stack
96
97 ***********************************************************************/
98
99 Stack clone ()
100 {
101 Stack s = void;
102 static if (Size == 0)
103 s.stack.length = stack.length;
104 s.stack[] = stack[];
105 s.depth = depth;
106 return s;
107 }
108
109 /***********************************************************************
110
111 Push and return a (shallow) copy of the topmost element
112
113 ***********************************************************************/
114
115 @property V dup ()
116 {
117 auto v = top;
118 push (v);
119 return v;
120 }
121
122 /**********************************************************************
123
124 Push a value onto the stack.
125
126 Throws an exception when the stack is full
127
128 **********************************************************************/
129
130 Stack* push (V value)
131 {
132 static if (Size == 0)
133 {
134 if (depth >= stack.length)
135 stack.length = stack.length + 64;
136 stack[depth++] = value;
137 }
138 else
139 {
140 if (depth < stack.length)
141 stack[depth++] = value;
142 else
143 error (__LINE__);
144 }
145 return &this;
146 }
147
148 /**********************************************************************
149
150 Push a series of values onto the stack.
151
152 Throws an exception when the stack is full
153
154 **********************************************************************/
155
156 Stack* append (V[] value...)
157 {
158 foreach (v; value)
159 push (v);
160 return &this;
161 }
162
163 /**********************************************************************
164
165 Remove and return the most recent addition to the stack.
166
167 Throws an exception when the stack is empty
168
169 **********************************************************************/
170
171 V pop ()
172 {
173 if (depth)
174 return stack[--depth];
175
176 return error (__LINE__);
177 }
178
179 /**********************************************************************
180
181 Return the most recent addition to the stack.
182
183 Throws an exception when the stack is empty
184
185 **********************************************************************/
186
187 @property V top ()
188 {
189 if (depth)
190 return stack[depth-1];
191
192 return error (__LINE__);
193 }
194
195 /**********************************************************************
196
197 Swaps the top two entries, and return the top
198
199 Throws an exception when the stack has insufficient entries
200
201 **********************************************************************/
202
203 V swap ()
204 {
205 auto p = stack.ptr + depth;
206 if ((p -= 2) >= stack.ptr)
207 {
208 auto v = p[0];
209 p[0] = p[1];
210 return p[1] = v;
211 }
212
213 return error (__LINE__);
214 }
215
216 /**********************************************************************
217
218 Index stack entries, where a zero index represents the
219 newest stack entry (the top).
220
221 Throws an exception when the given index is out of range
222
223 **********************************************************************/
224
225 V nth (size_t i)
226 {
227 if (i < depth)
228 return stack [depth-i-1];
229
230 return error (__LINE__);
231 }
232
233 /**********************************************************************
234
235 Rotate the given number of stack entries
236
237 Throws an exception when the number is out of range
238
239 **********************************************************************/
240
241 Stack* rotateLeft (size_t d)
242 {
243 if (d <= depth)
244 {
245 auto p = &stack[depth-d];
246 auto t = *p;
247 while (--d)
248 *p++ = *(p+1);
249 *p = t;
250 }
251 else
252 error (__LINE__);
253 return &this;
254 }
255
256 /**********************************************************************
257
258 Rotate the given number of stack entries
259
260 Throws an exception when the number is out of range
261
262 **********************************************************************/
263
264 Stack* rotateRight (size_t d)
265 {
266 if (d <= depth)
267 {
268 auto p = &stack[depth-1];
269 auto t = *p;
270 while (--d)
271 *p-- = *(p-1);
272 *p = t;
273 }
274 else
275 error (__LINE__);
276 return &this;
277 }
278
279 /**********************************************************************
280
281 Return the stack as an array of values, where the first
282 array entry represents the oldest value.
283
284 Doing a foreach() on the returned array will traverse in
285 the opposite direction of foreach() upon a stack
286
287 **********************************************************************/
288
289 V[] slice ()
290 {
291 return stack [0 .. depth];
292 }
293
294 /**********************************************************************
295
296 Throw an exception
297
298 **********************************************************************/
299
300 private V error (size_t line)
301 {
302 throw new RangeError (__FILE__, line);
303 }
304
305 /***********************************************************************
306
307 Iterate from the most recent to the oldest stack entries
308
309 ***********************************************************************/
310
311 int opApply (scope int delegate(ref V value) dg)
312 {
313 int result;
314
315 for (int i=depth; i-- && result is 0;)
316 result = dg (stack[i]);
317 return result;
318 }
319 }
320
321
322 /*******************************************************************************
323
324 *******************************************************************************/
325
326 debug (Stack)
327 {
328 import tango.io.Stdout;
329
330 void main()
331 {
332 Stack!(int) v;
333 v.push(1);
334
335 Stack!(int, 10) s;
336
337 Stdout.formatln ("push four");
338 s.push (1);
339 s.push (2);
340 s.push (3);
341 s.push (4);
342 foreach (v; s)
343 Stdout.formatln ("{}", v);
344 s <<= 4;
345 s >>= 4;
346 foreach (v; s)
347 Stdout.formatln ("{}", v);
348
349 s = s.clone;
350 Stdout.formatln ("pop one: {}", s.pop);
351 foreach (v; s)
352 Stdout.formatln ("{}", v);
353 Stdout.formatln ("top: {}", s.top);
354
355 Stdout.formatln ("pop three");
356 s.pop;
357 s.pop;
358 s.pop;
359 foreach (v; s)
360 Stdout.formatln ("> {}", v);
361 }
362 }
363