|
40
|
1 module doodle.containers.stack;
|
|
|
2
|
|
|
3 class Stack(T) {
|
|
|
4 this() {
|
|
|
5 _data.length = 1;
|
|
|
6 }
|
|
|
7
|
|
|
8 bool isEmpty() {
|
|
|
9 return _depth == 0;
|
|
|
10 }
|
|
|
11
|
|
|
12 void push(T t) {
|
|
|
13 if (_depth == _data.length) {
|
|
|
14 // Need it to grow
|
|
|
15 _data.length = 2 * _data.length;
|
|
|
16 }
|
|
|
17
|
|
|
18 _data[_depth] = t;
|
|
|
19 ++_depth;
|
|
|
20 }
|
|
|
21
|
|
|
22 T pop() {
|
|
|
23 assert(!isEmpty());
|
|
|
24 --_depth;
|
|
|
25 auto t = _data[_depth];
|
|
|
26 _data[_depth] = T.init;
|
|
|
27 return t;
|
|
|
28 }
|
|
|
29
|
|
|
30 T top() {
|
|
|
31 assert(!isEmpty());
|
|
|
32 return _data[_depth - 1];
|
|
|
33 }
|
|
|
34
|
|
|
35 void top(T t) {
|
|
|
36 assert(!isEmpty());
|
|
|
37 _data[_depth - 1] = t;
|
|
|
38 }
|
|
|
39
|
|
|
40 void clear() {
|
|
|
41 while (_depth > 0) {
|
|
|
42 --_depth;
|
|
|
43 _data[_depth] = T.init;
|
|
|
44 }
|
|
|
45 }
|
|
|
46
|
|
|
47 void shrink() {
|
|
|
48 size_t new_l = _data.length;
|
|
|
49 do new_l /= 2; while (new_l > _depth * 2);
|
|
|
50 _data.length = new_l;
|
|
|
51 }
|
|
|
52
|
|
|
53 void capacity(size_t l) {
|
|
|
54 if (l > _data.length) {
|
|
|
55 size_t new_l = _data.length;
|
|
|
56 do new_l *= 2; while (new_l < l);
|
|
|
57 _data.length = new_l;
|
|
|
58 }
|
|
|
59 }
|
|
|
60
|
|
|
61 private {
|
|
|
62 size_t capacity() {
|
|
|
63 return _data.length;
|
|
|
64 }
|
|
|
65
|
|
|
66 size_t depth() {
|
|
|
67 return _depth;
|
|
|
68 }
|
|
|
69
|
|
|
70 T[] _data; // capacity
|
|
|
71 size_t _depth;
|
|
|
72 }
|
|
|
73 }
|
|
|
74 unittest {
|
|
|
75 auto s = new Stack!(int);
|
|
|
76
|
|
|
77 assert(s.capacity() == 1);
|
|
|
78
|
|
|
79 assert(s.depth() == 0);
|
|
|
80 s.push(15);
|
|
|
81 assert(s.depth() == 1);
|
|
|
82 assert(s.top() == 15);
|
|
|
83 assert(s.pop() == 15);
|
|
|
84 assert(s.depth() == 0);
|
|
|
85 assert(s.isEmpty());
|
|
|
86
|
|
|
87 assert(s.capacity() == 1);
|
|
|
88 s.push(12);
|
|
|
89 assert(s.capacity() == 1);
|
|
|
90 s.push(13);
|
|
|
91 assert(s.capacity() == 2);
|
|
|
92 s.push(14);
|
|
|
93 assert(s.depth() == 3);
|
|
|
94 assert(s.capacity() == 4);
|
|
|
95 s.push(s.pop());
|
|
|
96 assert(s.capacity() == 4);
|
|
|
97 }
|
