-
Notifications
You must be signed in to change notification settings - Fork 0
/
stack.go
93 lines (64 loc) · 1.44 KB
/
stack.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package jsont
import (
"fmt"
"reflect"
"strings"
)
// Stack is the interface for a LIFO data structure that can hold values of arbitrary type
type Stack interface {
Push(elem interface{})
Pop() interface{}
Peek() interface{}
Size() int
}
type typeSafeStack struct {
contents []interface{}
pos int
t reflect.Type
}
func newTypeSafeStack(size int) *typeSafeStack {
s := make([]interface{}, 0, size)
return &typeSafeStack{contents: s, pos: -1}
}
func (s *typeSafeStack) Push(elem interface{}) {
t := reflect.TypeOf(elem)
if s.t != nil && t.PkgPath()+"/"+t.Name() != s.t.PkgPath()+"/"+s.t.Name() {
panic("pushing element of inconsistent type to stack")
}
s.contents = append(s.contents, elem)
s.pos++
if s.pos == 0 {
s.t = reflect.TypeOf(s.contents[0])
}
}
func (s *typeSafeStack) Pop() interface{} {
if s.pos < 0 {
return nil
}
res := s.contents[s.pos]
s.contents = s.contents[:s.pos]
s.pos--
return res
}
func (s *typeSafeStack) Peek() interface{} {
if s.pos < 0 {
return nil
}
return s.contents[s.pos]
}
func (s typeSafeStack) Size() int {
return len(s.contents)
}
func (s typeSafeStack) String() string {
sb := strings.Builder{}
sb.WriteString(fmt.Sprintf("Stack (%d) [", s.Size()))
for i, elem := range s.contents {
if i == len(s.contents)-1 {
sb.WriteString(fmt.Sprintf("%v", elem))
} else {
sb.WriteString(fmt.Sprintf("%v ", elem))
}
}
sb.WriteString("]")
return sb.String()
}