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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
package merkletrie
// Iter is a radix tree iterator that will traverse the trie in
// depth-first pre-order. Entries are traversed in (case-sensitive)
// alphabetical order for each level.
//
// This is the kind of traversal you will expect when listing
// ordinary files and directories recursively, for example:
//
// Trie Traversal order
// ---- ---------------
// .
// / | \ a
// / | \ b
// b a z ===> b/a
// / \ b/c
// c a z
//
//
// The Step method will return the next item, the Next method will do
// the same but without descending deeper into the tree (i.e. skipping
// the contents of "directories").
//
// The name of the type and its methods are based on the well known "next"
// and "step" operations, quite common in debuggers, like gdb.
type Iter struct {
// tells if the iteration has started.
hasStarted bool
// Each level of the tree is represented as a frame, this stack
// keeps track of the frames wrapping the current iterator position.
// The iterator will "step" into a node by adding its frame to the
// stack, or go to the next element at the same level by poping the
// current frame.
frameStack []*frame
}
// NewIter returns a new iterator for the trie with its root at n.
func NewIter(n Noder) *Iter {
ret := &Iter{}
ret.push(newFrame("", n))
return ret
}
func (iter *Iter) top() (*frame, bool) {
if len(iter.frameStack) == 0 {
return nil, false
}
top := len(iter.frameStack) - 1
return iter.frameStack[top], true
}
func (iter *Iter) pop() (*frame, bool) {
if len(iter.frameStack) == 0 {
return nil, false
}
top := len(iter.frameStack) - 1
ret := iter.frameStack[top]
iter.frameStack[top] = nil
iter.frameStack = iter.frameStack[:top]
return ret, true
}
func (iter *Iter) push(f *frame) {
iter.frameStack = append(iter.frameStack, f)
}
const (
descend = true
dontDescend = false
)
// Next returns the next node without descending deeper into the tree
// and true. If there are no more entries it returns nil and false.
func (iter *Iter) Next() (Noder, bool) {
return iter.advance(dontDescend)
}
// Step returns the next node in the tree, descending deeper into it if
// needed. If there are no more nodes in the tree, it returns nil and
// false.
func (iter *Iter) Step() (Noder, bool) {
return iter.advance(descend)
}
// advances the iterator in whatever direction you want: descend or
// dontDescend.
func (iter *Iter) advance(mustDescend bool) (Noder, bool) {
node, ok := iter.current()
if !ok {
return nil, false
}
// The first time we just return the current node.
if !iter.hasStarted {
iter.hasStarted = true
return node, ok
}
// following advances will involve dropping already seen nodes
// or getting into their children
ignoreChildren := node.NumChildren() == 0 || !mustDescend
if ignoreChildren {
// if we must ignore the current node children, just drop
// it and find the next one in the existing frames.
_ = iter.drop()
node, ok = iter.current()
return node, ok
}
// if we must descend into the current's node children, drop the
// parent and add a new frame with its children.
_ = iter.drop()
iter.push(newFrame(node.Key(), node))
node, _ = iter.current()
return node, true
}
// returns the current frame and the current node (i.e. the ones at the
// top of their respective stacks.
func (iter *Iter) current() (Noder, bool) {
f, ok := iter.top()
if !ok {
return nil, false
}
n, ok := f.top()
if !ok {
return nil, false
}
return n, true
}
// removes the current node and all the frames that become empty as a
// consequence of this action. It returns true if something was dropped,
// and false if there were no more nodes in the iterator.
func (iter *Iter) drop() bool {
frame, ok := iter.top()
if !ok {
return false
}
_, ok = frame.pop()
if !ok {
return false
}
for { // remove empty frames
if len(frame.stack) != 0 {
break
}
_, _ = iter.pop()
frame, ok = iter.top()
if !ok {
break
}
}
return true
}
|
