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 
37     public template opOpAssign ( string op : ">>" )
38     {
39         alias opOpAssign = rotateRight;
40     }
41 
42     public template opOpAssign ( string op : "<<" )
43     {
44         alias opOpAssign = rotateLeft;
45     }
46 
47     public template opOpAssign ( string op : "~" )
48     {
49         alias opOpAssign = push;
50     }
51 
52     static if (Size == 0)
53     {
54         private uint depth;
55         private V[]  stack;
56     }
57     else
58     {
59         private uint     depth;
60         private V[Size]  stack;
61     }
62 
63     /***************************************************************************
64 
65         Clear the stack
66 
67         Returns: pointer to itself for chaining calls
68 
69     ***************************************************************************/
70 
71     Stack* clear ( )
72     {
73         depth = 0;
74         return &this;
75     }
76 
77     /***************************************************************************
78 
79         Returns: depth of the stack
80 
81     ***************************************************************************/
82 
83     size_t size ( )
84     {
85         return depth;
86     }
87 
88     /***************************************************************************
89 
90         Returns: remaining unused slots
91 
92     ***************************************************************************/
93 
94     size_t unused  ( )
95     {
96         enforce(.e_bounds, stack.length >= depth);
97         return stack.length - depth;
98     }
99 
100     /***************************************************************************
101 
102         Returns: a (shallow) clone of this stack, on the stack
103 
104     ***************************************************************************/
105 
106     Stack clone ( )
107     {
108         Stack s;
109         static if (Size == 0)
110             s.stack.length = stack.length;
111         s.stack[] = stack;
112         s.depth = depth;
113         return s;
114     }
115 
116     /***************************************************************************
117 
118         Pushes shallow copy of topmost element
119 
120         Returns: pushed copy
121 
122     ***************************************************************************/
123 
124     V dup ( )
125     {
126         auto v = top;
127         push (v);
128         return v;
129     }
130 
131     /***************************************************************************
132 
133         Params:
134             value = valush to push on top of the stack
135 
136         Returns: pointer to itself for call chaining
137 
138         Throws: StackBoundsException when the stack is full
139 
140     ***************************************************************************/
141 
142     Stack* push ( V value )
143     {
144         static if (Size == 0)
145         {
146             if (depth >= stack.length)
147                 stack.length = stack.length + 64;
148             stack[depth++] = value;
149         }
150         else
151         {
152             enforce(.e_bounds, depth < stack.length);
153             stack[depth++] = value;
154         }
155         return &this;
156     }
157 
158     /***************************************************************************
159 
160         Params:
161             value = array of values to push onto the stack
162 
163         Returns: pointer to itself for call chaining
164 
165         Throws: StackBoundsException when the stack is full
166 
167     ***************************************************************************/
168 
169     Stack* append ( V[] value... )
170     {
171         foreach (v; value)
172             push (v);
173         return &this;
174     }
175 
176     /***************************************************************************
177 
178         Removes most recent stack element
179 
180         Return: most recent stack element before popping
181 
182         Throws: StackBoundsException when the stack is full
183 
184     ***************************************************************************/
185 
186     V pop ( )
187     {
188         enforce(.e_bounds, depth > 0);
189         return stack[--depth];
190     }
191 
192     /***************************************************************************
193 
194         Returns: most recent stack element
195 
196         Throws: StackBoundsException when the stack is full
197 
198     ***************************************************************************/
199 
200     V top ( )
201     {
202         enforce(.e_bounds, depth > 0);
203         return stack[depth-1];
204     }
205 
206     /***************************************************************************
207 
208         Swaps the top two entries
209 
210         Returns: the top element after swapping
211 
212         Throws: StackBoundsException when the stack has insufficient entries
213 
214     ***************************************************************************/
215 
216     V swap ( )
217     {
218         auto p = stack.ptr + depth;
219         enforce(.e_bounds, p - 2 >= stack.ptr);
220 
221         p -= 2;
222         auto v = p[0];
223         p[0] = p[1];
224         return p[1] = v;
225     }
226 
227     /***************************************************************************
228 
229         Params:
230             i = entry index
231 
232         Returns:
233             stack entry with index `i`, where a zero index represents the
234             newest stack entry (the top).
235 
236         Throws: StackBoundsException when the given index is out of range
237 
238     ***************************************************************************/
239 
240     V nth ( uint i )
241     {
242         enforce(.e_bounds, i < depth);
243         return stack [depth-i-1];
244     }
245 
246     /***************************************************************************
247 
248         Rotate the given number of stack entries
249 
250         Params:
251             d = number of entries
252 
253         Returns: pointer to itself for call chaining
254 
255         Throws: StackBoundsException when the number is out of range
256 
257     ***************************************************************************/
258 
259     Stack* rotateLeft ( uint d )
260     {
261         enforce(.e_bounds, d <= depth);
262         auto p = &stack[depth-d];
263         auto t = *p;
264         while (--d)
265         {
266             *p = *(p+1);
267             p++;
268         }
269         *p = t;
270         return &this;
271     }
272 
273     /***************************************************************************
274 
275         Rotate the given number of stack entries
276 
277         Params:
278             d = number of entries
279 
280         Returns: pointer to itself for call chaining
281 
282         Throws: StackBoundsException when the number is out of range
283 
284     ***************************************************************************/
285 
286     Stack* rotateRight ( uint d )
287     {
288         enforce(.e_bounds, d <= depth);
289         auto p = &stack[depth-1];
290         auto t = *p;
291         while (--d)
292         {
293             *p = *(p-1);
294             p--;
295         }
296         *p = t;
297         return &this;
298     }
299 
300     /***************************************************************************
301 
302         Returns:
303             The stack as an array of values, where the first
304             array entry represents the oldest value.
305 
306             Doing a foreach() on the returned array will traverse in
307             the opposite direction of foreach() upon a stack.
308 
309 
310     ***************************************************************************/
311 
312     V[] slice ( )
313     {
314         return stack[0 .. depth];
315     }
316 
317     /***************************************************************************
318 
319         Iterate from the most recent to the oldest stack entries
320 
321     ***************************************************************************/
322 
323     int opApply ( scope int delegate(ref V value) dg )
324     {
325         int result;
326 
327         for (int i=depth; i-- && result is 0;)
328             result = dg (stack[i]);
329 
330         return result;
331     }
332 }
333 
334 ///
335 unittest
336 {
337     Stack!(int) stack;
338     stack.push(42);
339     test!("==")(stack.pop(), 42);
340     testThrown!(StackBoundsException)(stack.pop());
341 }
342 
343 version (unittest)
344 {
345     static void runTests ( T ) ( NamedTest t, T stack )
346     {
347         t.test!("==")(stack.size(), 0);
348         testThrown!(StackBoundsException)(stack.pop());
349         stack.push(42);
350         t.test!("==")(stack.size(), 1);
351         stack.clear();
352         t.test!("==")(stack.size(), 0);
353 
354         stack.push(100);
355         t.test!("==")(stack.dup(), 100);
356         t.test!("==")(stack[], [ 100, 100 ]);
357 
358         auto clone = stack.clone();
359         foreach (idx, ref field; clone.tupleof)
360             t.test!("==")(field, stack.tupleof[idx]);
361 
362         stack.clear();
363         stack.append(1, 2, 3, 4);
364         t.test!("==")(stack[], [ 1, 2, 3, 4 ]);
365 
366         t.test!("==")(stack.top(), 4);
367         t.test!("==")(stack.pop(), 4);
368         t.test!("==")(stack.top(), 3);
369         t.test!("==")(stack[0], 3);
370         t.test!("==")(stack[2], 1);
371         testThrown!(StackBoundsException)(stack[10]);
372 
373         stack.swap();
374         t.test!("==")(stack[], [ 1, 3, 2 ]);
375         stack.clear();
376         testThrown!(StackBoundsException)(stack.swap());
377 
378         stack.append(1, 2, 3);
379         stack.rotateLeft(2);
380         t.test!("==")(stack[], [ 1, 3, 2 ]);
381         stack.rotateRight(2);
382         t.test!("==")(stack[], [ 1, 2, 3 ]);
383         testThrown!(StackBoundsException)(stack.rotateLeft(40));
384         testThrown!(StackBoundsException)(stack.rotateRight(40));
385     }
386 }
387 
388 unittest
389 {
390     // common tests
391     runTests(new NamedTest("Dynamic size"), Stack!(int).init);
392     runTests(new NamedTest("Static size"),  Stack!(int, 10).init);
393 }
394 
395 unittest
396 {
397     // fixed size specific tests
398     Stack!(int, 3) stack;
399     test!("==")(stack.unused(), 3);
400 
401     stack.push(1);
402     stack.push(1);
403     stack.push(1);
404     testThrown!(StackBoundsException)(stack.push(1));
405 }
406 
407 unittest
408 {
409     // dynamic size specific tests
410     Stack!(int) stack;
411     test!("==")(stack.unused(), 0);
412 }
413 
414 unittest
415 {
416     // Check overloaded operators
417     Stack!(int) stack;
418     stack ~= 4;
419     stack ~= 5;
420     stack >>= 2;
421     test!("==")(stack.pop(), 4);
422     stack <<= 1;
423     test!("==")(stack.pop(), 5);
424 }
425 
426 /*******************************************************************************
427 
428     Exception that indicates any kind of out of bound access in stack, for
429     example, trying to pop from empty one.
430 
431 *******************************************************************************/
432 
433 public class StackBoundsException : Exception
434 {
435     this ( )
436     {
437         super("Out of bounds access attempt to stack struct");
438     }
439 }
440 
441 private StackBoundsException e_bounds;
442 
443 static this ( )
444 {
445     e_bounds = new StackBoundsException;
446 }