1 package frost.collections
2
3 ====================================================================================================
4 An implementation of the stack abstract data type. A stack is a collection of elements which
5 operates in "LIFO" (last in, first out) order; that is, the element most recently added to the stack
6 is the first one retrieved.
7 ====================================================================================================
8 class Stack<T> : Iterable<T> {
9 @private
10 class StackIterator<T> : Iterator<T> {
11 def stack:Stack<T>
12
13 var index := 0
14
15 init(stack:Stack<T>) {
16 self.stack := stack
17 }
18
19 @override
20 function get_done():Bit {
21 return index >= stack.count
22 }
23
24 @override
25 method next():T {
26 def result := stack[index]
27 index += 1
28 return result
29 }
30 }
31
32 @private
33 def contents := Array<T>()
34
35 ================================================================================================
36 The number of elements on the stack.
37 ================================================================================================
38 property count:Int
39
40 ================================================================================================
41 Pushes a new element onto the stack.
42 ================================================================================================
43 method push(v:T) {
44 contents.add(v)
45 }
46
47 ================================================================================================
48 Pops the top value from the stack and returns it.
49 ================================================================================================
50 @pre(count > 0)
51 method pop():T {
52 assert contents.count > 0
53 def result := contents[contents.count - 1]
54 contents.removeIndex(contents.count - 1)
55 return result
56 }
57
58 ================================================================================================
59 Inserts a new element at the specified depth. A depth of `0` is equivalent to [push].
60 ================================================================================================
61 method insert(depth:Int, value:T) {
62 contents.insert(contents.count - 1 - depth, value)
63 }
64
65 method removeIndex(depth:Int):T {
66 return contents.removeIndex(contents.count - 1 - depth)
67 }
68
69 ================================================================================================
70 Returns the value at the given depth in the stack. The top element (most recently pushed) is
71 element 0, and the bottom element (earliest pushed) is element `count - 1`.
72 ================================================================================================
73 @pre(depth >= 0 & depth < count)< count)
74 function [](depth:Int):T {
75 assert contents.count > depth
76 return contents[contents.count - 1 - depth]
77 }
78
79 ================================================================================================
80 Removes all elements from the stack.
81 ================================================================================================
82 method clear() {
83 contents.clear()
84 }
85
86 ================================================================================================
87 Returns an iterator which returns elements from the stack, starting from the top and working
88 down to the bottom. Iterating over the stack does not modify it.
89 ================================================================================================
90 @override
91 function get_iterator():Iterator<T> {
92 return StackIterator<T>(self)
93 }
94
95 function get_count():Int {
96 return contents.count
97 }
98
99 @override
100 function get_toString():String {
101 return contents.toString
102 }
103 }