sbin.util.stack source code

1 module sbin.util.stack;
2 
3 package(sbin):
4 
5 struct Stack(T, size_t N=0)
6 {
7     //private
8     public
9     {
10         ptrdiff_t topI = 0;
11         static if (N) T[N] sdata;
12         T[] data;
13     }
14 
15     private void pushDynamic(T val)
16     {
17         if (cast(ptrdiff_t)data.length < topI-N) data ~= val;
18         else top = val;
19     }
20 
21     void push(T val)
22     {
23         topI++;
24         static if (N)
25         {
26             if (topI <= cast(ptrdiff_t)N) top = val;
27             else pushDynamic(val);
28         }
29         else pushDynamic(val);
30     }
31 
32     const(T[]) getData() const
33     {
34         static if (N)
35         {
36             if (topI <= cast(ptrdiff_t)N) return sdata[0..topI];
37             else return (sdata[] ~ data)[0..topI];
38         }
39         else return data[0..topI];
40     }
41 
42     void reserve(ptrdiff_t k)
43     {
44         k -= N;
45         if ((cast(ptrdiff_t)data.length) < k) data.length = k;
46     }
47 
48     ref inout(T) top() inout @property
49     {
50         static if (N)
51             return (topI <= (cast(ptrdiff_t)N)) ? sdata[topI-1] : data[topI-N-1];
52         else
53             return data[topI-1];
54     }
55     T pop()
56     {
57         if (empty) assert(0, "stack empty");
58         T ret = top;
59         topI--;
60         return ret;
61     }
62     bool empty() const @property { return topI == 0; }
63     void clear() { data.length = 0; topI = 0; }
64 }
65 
66 version (unittest) void testStack(size_t N)()
67 {
68     Stack!(int, N) s;
69     assert (s.empty);
70     s.reserve(5);
71     assert (s.empty);
72     s.push(1);
73     assert (!s.empty);
74     s.push(2);
75     assert (!s.empty);
76     assert (s.top == 2);
77     s.pop();
78     assert (s.top == 1);
79     s.pop();
80     assert (s.empty);
81 
82     import std.exception : assertThrown;
83     import core.exception : RangeError, AssertError;
84     import std.algorithm : equal, map;
85     import std.range : iota, chain;
86 
87     assertThrown!RangeError(s.top);
88     assertThrown!AssertError(s.pop());
89 
90     foreach (i; 1..10) s.push(i*10);
91     assert (equal(s.getData(), iota(1,10).map!"a*10"));
92     foreach_reverse (i; 1..10) assert (s.pop() == i*10);
93 
94     foreach (i; 1..100) s.push(i*3);
95     assert (equal(s.getData(), iota(1,100).map!"a*3"));
96     assert(s.pop() == 99*3);
97     foreach (i; 1..10) s.push(i*2);
98     assert (equal(s.getData(), chain(iota(1,99).map!"a*3", iota(1,10).map!"a*2")));
99     foreach_reverse (i; 1..10) assert (s.pop() == i*2);
100     foreach_reverse (i; 1..99) assert (s.pop() == i*3);
101 
102     assert (s.empty);
103     s.push(100);
104     assert (!s.empty);
105     s.clear();
106     assert (s.empty);
107 }
108 
109 unittest
110 {
111     static foreach (N; [0,1,5,8,9,10,11,12,99,100,101,196])
112         testStack!N;
113 }