ocean.util.container.more.Stack source code

1 /*******************************************************************************
2 
3     Copyright:
4         Copyright (c) 2008 Kris Bell.
5         Some parts copyright (c) 2009-2017 dunnhumby Germany GmbH.
6         All rights reserved.
7 
8     License:
9         Tango Dual License: 3-Clause BSD License / Academic Free License v3.0.
10         See LICENSE_TANGO.txt for details.
11 
12 *******************************************************************************/
13 
14 module ocean.util.container.more.Stack;
15 
16 import ocean.core.Enforce;
17 
18 version (UnitTest)
19 {
20     import ocean.core.Test;
21 }
22 
23 /*******************************************************************************
24 
25     A stack of the given value-type V, with maximum depth Size. Note
26     that this does no memory allocation of its own when Size != 0, and
27     does heap allocation when Size == 0. Thus you can have a fixed-size
28     low-overhead instance, or a heap oriented instance.
29 
30 *******************************************************************************/
31 
32 public struct Stack ( V, int Size = 0 )
33 {
34     public alias nth         opIndex;
35     public alias slice       opSlice;
36     public alias rotateRight opShrAssign;
37     public alias rotateLeft  opShlAssign;
38     public alias push        opCatAssign;
39 
40     static if (Size == 0)
41     {
42         private uint depth;
43         private V[]  stack;
44     }
45     else
46     {
47         private uint     depth;
48         private V[Size]  stack;
49     }
50 
51     /***************************************************************************
52 
53         Clear the stack
54 
55         Returns: pointer to itself for chaining calls
56 
57     ***************************************************************************/
58 
59     Stack* clear ( )
60     {
61         depth = 0;
62         return (&this);
63     }
64 
65     /***************************************************************************
66 
67         Returns: depth of the stack
68 
69     ***************************************************************************/
70 
71     size_t size ( )
72     {
73         return depth;
74     }
75 
76     /***************************************************************************
77 
78         Returns: remaining unused slots
79 
80     ***************************************************************************/
81 
82     size_t unused  ( )
83     {
84         enforce(.e_bounds, stack.length >= depth);
85         return stack.length - depth;
86     }
87 
88     /***************************************************************************
89 
90         Returns: a (shallow) clone of this stack, on the stack
91 
92     ***************************************************************************/
93 
94     Stack clone ( )
95     {
96         Stack s;
97         static if (Size == 0)
98             s.stack.length = stack.length;
99         s.stack[] = stack;
100         s.depth = depth;
101         return s;
102     }
103 
104     /***************************************************************************
105 
106         Pushes shallow copy of topmost element
107 
108         Returns: pushed copy
109 
110     ***************************************************************************/
111 
112     V dup ( )
113     {
114         auto v = top;
115         push (v);
116         return v;
117     }
118 
119     /***************************************************************************
120 
121         Params:
122             value = valush to push on top of the stack
123 
124         Returns: pointer to itself for call chaining
125 
126         Throws: StackBoundsException 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             enforce(.e_bounds, depth < stack.length);
141             stack[depth++] = value;
142         }
143         return (&this);
144     }
145 
146     /***************************************************************************
147 
148         Params:
149             value = array of values to push onto the stack
150 
151         Returns: pointer to itself for call chaining
152 
153         Throws: StackBoundsException when the stack is full
154 
155     ***************************************************************************/
156 
157     Stack* append ( V[] value... )
158     {
159         foreach (v; value)
160             push (v);
161         return (&this);
162     }
163 
164     /***************************************************************************
165 
166         Removes most recent stack element
167 
168         Return: most recent stack element before popping
169 
170         Throws: StackBoundsException when the stack is full
171 
172     ***************************************************************************/
173 
174     V pop ( )
175     {
176         enforce(.e_bounds, depth > 0);
177         return stack[--depth];
178     }
179 
180     /***************************************************************************
181 
182         Returns: most recent stack element
183 
184         Throws: StackBoundsException when the stack is full
185 
186     ***************************************************************************/
187 
188     V top ( )
189     {
190         enforce(.e_bounds, depth > 0);
191         return stack[depth-1];
192     }
193 
194     /***************************************************************************
195 
196         Swaps the top two entries
197 
198         Returns: the top element after swapping
199 
200         Throws: StackBoundsException when the stack has insufficient entries
201 
202     ***************************************************************************/
203 
204     V swap ( )
205     {
206         auto p = stack.ptr + depth;
207         enforce(.e_bounds, p - 2 >= stack.ptr);
208 
209         p -= 2;
210         auto v = p[0];
211         p[0] = p[1];
212         return p[1] = v;
213     }
214 
215     /***************************************************************************
216 
217         Params:
218             i = entry index
219 
220         Returns:
221             stack entry with index `i`, where a zero index represents the
222             newest stack entry (the top).
223 
224         Throws: StackBoundsException when the given index is out of range
225 
226     ***************************************************************************/
227 
228     V nth ( uint i )
229     {
230         enforce(.e_bounds, i < depth);
231         return stack [depth-i-1];
232     }
233 
234     /***************************************************************************
235 
236         Rotate the given number of stack entries
237 
238         Params:
239             d = number of entries
240 
241         Returns: pointer to itself for call chaining
242 
243         Throws: StackBoundsException when the number is out of range
244 
245     ***************************************************************************/
246 
247     Stack* rotateLeft ( uint d )
248     {
249         enforce(.e_bounds, d <= depth);
250         auto p = &stack[depth-d];
251         auto t = *p;
252         while (--d)
253         {
254             *p = *(p+1);
255             p++;
256         }
257         *p = t;
258         return (&this);
259     }
260 
261     /***************************************************************************
262 
263         Rotate the given number of stack entries
264 
265         Params:
266             d = number of entries
267 
268         Returns: pointer to itself for call chaining
269 
270         Throws: StackBoundsException when the number is out of range
271 
272     ***************************************************************************/
273 
274     Stack* rotateRight ( uint d )
275     {
276         enforce(.e_bounds, d <= depth);
277         auto p = &stack[depth-1];
278         auto t = *p;
279         while (--d)
280         {
281             *p = *(p-1);
282             p--;
283         }
284         *p = t;
285         return (&this);
286     }
287 
288     /***************************************************************************
289 
290         Returns:
291             The stack as an array of values, where the first
292             array entry represents the oldest value.
293 
294             Doing a foreach() on the returned array will traverse in
295             the opposite direction of foreach() upon a stack.
296 
297 
298     ***************************************************************************/
299 
300     V[] slice ( )
301     {
302         return stack[0 .. depth];
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 
318         return result;
319     }
320 }
321 
322 ///
323 unittest
324 {
325     Stack!(int) stack;
326     stack.push(42);
327     test!("==")(stack.pop(), 42);
328     testThrown!(StackBoundsException)(stack.pop());
329 }
330 
331 version(UnitTest)
332 {
333     static void runTests ( T ) ( NamedTest t, T stack )
334     {
335         t.test!("==")(stack.size(), 0);
336         testThrown!(StackBoundsException)(stack.pop());
337         stack.push(42);
338         t.test!("==")(stack.size(), 1);
339         stack.clear();
340         t.test!("==")(stack.size(), 0);
341 
342         stack.push(100);
343         t.test!("==")(stack.dup(), 100);
344         t.test!("==")(stack[], [ 100, 100 ]);
345 
346         auto clone = stack.clone();
347         foreach (idx, ref field; clone.tupleof)
348             t.test!("==")(field, stack.tupleof[idx]);
349 
350         stack.clear();
351         stack.append(1, 2, 3, 4);
352         t.test!("==")(stack[], [ 1, 2, 3, 4 ]);
353 
354         t.test!("==")(stack.top(), 4);
355         t.test!("==")(stack.pop(), 4);
356         t.test!("==")(stack.top(), 3);
357         t.test!("==")(stack[0], 3);
358         t.test!("==")(stack[2], 1);
359         testThrown!(StackBoundsException)(stack[10]);
360 
361         stack.swap();
362         t.test!("==")(stack[], [ 1, 3, 2 ]);
363         stack.clear();
364         testThrown!(StackBoundsException)(stack.swap());
365 
366         stack.append(1, 2, 3);
367         stack.rotateLeft(2);
368         t.test!("==")(stack[], [ 1, 3, 2 ]);
369         stack.rotateRight(2);
370         t.test!("==")(stack[], [ 1, 2, 3 ]);
371         testThrown!(StackBoundsException)(stack.rotateLeft(40));
372         testThrown!(StackBoundsException)(stack.rotateRight(40));
373     }
374 }
375 
376 unittest
377 {
378     // common tests
379     runTests(new NamedTest("Dynamic size"), Stack!(int).init);
380     runTests(new NamedTest("Static size"),  Stack!(int, 10).init);
381 }
382 
383 unittest
384 {
385     // fixed size specific tests
386     Stack!(int, 3) stack;
387     test!("==")(stack.unused(), 3);
388 
389     stack.push(1);
390     stack.push(1);
391     stack.push(1);
392     testThrown!(StackBoundsException)(stack.push(1));
393 }
394 
395 unittest
396 {
397     // dynamic size specific tests
398     Stack!(int) stack;
399     test!("==")(stack.unused(), 0);
400 }
401 
402 /*******************************************************************************
403 
404     Exception that indicates any kind of out of bound access in stack, for
405     example, trying to pop from empty one.
406 
407 *******************************************************************************/
408 
409 public class StackBoundsException : Exception
410 {
411     this ( )
412     {
413         super("Out of bounds access attempt to stack struct");
414     }
415 }
416 
417 private StackBoundsException e_bounds;
418 
419 static this ( )
420 {
421     e_bounds = new StackBoundsException;
422 }