1 // Copyright (c) 2015-2016 The btcsuite developers
2 // Use of this source code is governed by an ISC
3 // license that can be found in the LICENSE file.
9 // Iterator represents an iterator for forwards and backwards iteration over
10 // the contents of a treap (mutable or immutable).
11 type Iterator struct {
12 t *Mutable // Mutable treap iterator is associated with or nil
13 root *treapNode // Root node of treap iterator is associated with
14 node *treapNode // The node the iterator is positioned at
15 parents parentStack // The stack of parents needed to iterate
16 isNew bool // Whether the iterator has been positioned
17 seekKey []byte // Used to handle dynamic updates for mutable treap
18 startKey []byte // Used to limit the iterator to a range
19 limitKey []byte // Used to limit the iterator to a range
22 // limitIterator clears the current iterator node if it is outside of the range
23 // specified when the iterator was created. It returns whether the iterator is
25 func (iter *Iterator) limitIterator() bool {
31 if iter.startKey != nil && bytes.Compare(node.key, iter.startKey) < 0 {
36 if iter.limitKey != nil && bytes.Compare(node.key, iter.limitKey) >= 0 {
44 // seek moves the iterator based on the provided key and flags.
46 // When the exact match flag is set, the iterator will either be moved to first
47 // key in the treap that exactly matches the provided key, or the one
48 // before/after it depending on the greater flag.
50 // When the exact match flag is NOT set, the iterator will be moved to the first
51 // key in the treap before/after the provided key depending on the greater flag.
53 // In all cases, the limits specified when the iterator was created are
55 func (iter *Iterator) seek(key []byte, exactMatch bool, greater bool) bool {
57 iter.parents = parentStack{}
58 var selectedNodeDepth int
59 for node := iter.root; node != nil; {
60 iter.parents.Push(node)
62 // Traverse left or right depending on the result of the
63 // comparison. Also, set the iterator to the node depending on
64 // the flags so the iterator is positioned properly when an
65 // exact match isn't found.
66 compareResult := bytes.Compare(key, node.key)
67 if compareResult < 0 {
70 selectedNodeDepth = iter.parents.Len() - 1
75 if compareResult > 0 {
78 selectedNodeDepth = iter.parents.Len() - 1
84 // The key is an exact match. Set the iterator and return now
85 // when the exact match flag is set.
89 return iter.limitIterator()
92 // The key is an exact match, but the exact match is not set, so
93 // choose which direction to go based on whether the larger or
94 // smaller key was requested.
102 // There was either no exact match or there was an exact match but the
103 // exact match flag was not set. In any case, the parent stack might
104 // need to be adjusted to only include the parents up to the selected
105 // node. Also, ensure the selected node's key does not exceed the
106 // allowed range of the iterator.
107 for i := iter.parents.Len(); i > selectedNodeDepth; i-- {
110 return iter.limitIterator()
113 // First moves the iterator to the first key/value pair. When there is only a
114 // single key/value pair both First and Last will point to the same pair.
115 // Returns false if there are no key/value pairs.
116 func (iter *Iterator) First() bool {
117 // Seek the start key if the iterator was created with one. This will
118 // result in either an exact match, the first greater key, or an
119 // exhausted iterator if no such key exists.
121 if iter.startKey != nil {
122 return iter.seek(iter.startKey, true, true)
125 // The smallest key is in the left-most node.
126 iter.parents = parentStack{}
127 for node := iter.root; node != nil; node = node.left {
128 if node.left == nil {
132 iter.parents.Push(node)
137 // Last moves the iterator to the last key/value pair. When there is only a
138 // single key/value pair both First and Last will point to the same pair.
139 // Returns false if there are no key/value pairs.
140 func (iter *Iterator) Last() bool {
141 // Seek the limit key if the iterator was created with one. This will
142 // result in the first key smaller than the limit key, or an exhausted
143 // iterator if no such key exists.
145 if iter.limitKey != nil {
146 return iter.seek(iter.limitKey, false, false)
149 // The highest key is in the right-most node.
150 iter.parents = parentStack{}
151 for node := iter.root; node != nil; node = node.right {
152 if node.right == nil {
156 iter.parents.Push(node)
161 // Next moves the iterator to the next key/value pair and returns false when the
162 // iterator is exhausted. When invoked on a newly created iterator it will
163 // position the iterator at the first item.
164 func (iter *Iterator) Next() bool {
169 if iter.node == nil {
173 // Reseek the previous key without allowing for an exact match if a
174 // force seek was requested. This results in the key greater than the
175 // previous one or an exhausted iterator if there is no such key.
176 if seekKey := iter.seekKey; seekKey != nil {
178 return iter.seek(seekKey, false, true)
181 // When there is no right node walk the parents until the parent's right
182 // node is not equal to the previous child. This will be the next node.
183 if iter.node.right == nil {
184 parent := iter.parents.Pop()
185 for parent != nil && parent.right == iter.node {
187 parent = iter.parents.Pop()
190 return iter.limitIterator()
193 // There is a right node, so the next node is the left-most node down
194 // the right sub-tree.
195 iter.parents.Push(iter.node)
196 iter.node = iter.node.right
197 for node := iter.node.left; node != nil; node = node.left {
198 iter.parents.Push(iter.node)
201 return iter.limitIterator()
204 // Prev moves the iterator to the previous key/value pair and returns false when
205 // the iterator is exhausted. When invoked on a newly created iterator it will
206 // position the iterator at the last item.
207 func (iter *Iterator) Prev() bool {
212 if iter.node == nil {
216 // Reseek the previous key without allowing for an exact match if a
217 // force seek was requested. This results in the key smaller than the
218 // previous one or an exhausted iterator if there is no such key.
219 if seekKey := iter.seekKey; seekKey != nil {
221 return iter.seek(seekKey, false, false)
224 // When there is no left node walk the parents until the parent's left
225 // node is not equal to the previous child. This will be the previous
227 for iter.node.left == nil {
228 parent := iter.parents.Pop()
229 for parent != nil && parent.left == iter.node {
231 parent = iter.parents.Pop()
234 return iter.limitIterator()
237 // There is a left node, so the previous node is the right-most node
238 // down the left sub-tree.
239 iter.parents.Push(iter.node)
240 iter.node = iter.node.left
241 for node := iter.node.right; node != nil; node = node.right {
242 iter.parents.Push(iter.node)
245 return iter.limitIterator()
248 // Seek moves the iterator to the first key/value pair with a key that is
249 // greater than or equal to the given key and returns true if successful.
250 func (iter *Iterator) Seek(key []byte) bool {
252 return iter.seek(key, true, true)
255 // Key returns the key of the current key/value pair or nil when the iterator
256 // is exhausted. The caller should not modify the contents of the returned
258 func (iter *Iterator) Key() []byte {
259 if iter.node == nil {
265 // Value returns the value of the current key/value pair or nil when the
266 // iterator is exhausted. The caller should not modify the contents of the
268 func (iter *Iterator) Value() []byte {
269 if iter.node == nil {
272 return iter.node.value
275 // Valid indicates whether the iterator is positioned at a valid key/value pair.
276 // It will be considered invalid when the iterator is newly created or exhausted.
277 func (iter *Iterator) Valid() bool {
278 return iter.node != nil
281 // ForceReseek notifies the iterator that the underlying mutable treap has been
282 // updated, so the next call to Prev or Next needs to reseek in order to allow
283 // the iterator to continue working properly.
285 // NOTE: Calling this function when the iterator is associated with an immutable
286 // treap has no effect as you would expect.
287 func (iter *Iterator) ForceReseek() {
288 // Nothing to do when the iterator is associated with an immutable
294 // Update the iterator root to the mutable treap root in case it
296 iter.root = iter.t.root
298 // Set the seek key to the current node. This will force the Next/Prev
299 // functions to reseek, and thus properly reconstruct the iterator, on
301 if iter.node == nil {
305 iter.seekKey = iter.node.key
308 // Iterator returns a new iterator for the mutable treap. The newly returned
309 // iterator is not pointing to a valid item until a call to one of the methods
310 // to position it is made.
312 // The start key and limit key parameters cause the iterator to be limited to
313 // a range of keys. The start key is inclusive and the limit key is exclusive.
314 // Either or both can be nil if the functionality is not desired.
316 // WARNING: The ForceSeek method must be called on the returned iterator if
317 // the treap is mutated. Failure to do so will cause the iterator to return
318 // unexpected keys and/or values.
321 // iter := t.Iterator(nil, nil)
323 // if someCondition {
324 // t.Delete(iter.Key())
325 // iter.ForceReseek()
328 func (t *Mutable) Iterator(startKey, limitKey []byte) *Iterator {
339 // Iterator returns a new iterator for the immutable treap. The newly returned
340 // iterator is not pointing to a valid item until a call to one of the methods
341 // to position it is made.
343 // The start key and limit key parameters cause the iterator to be limited to
344 // a range of keys. The start key is inclusive and the limit key is exclusive.
345 // Either or both can be nil if the functionality is not desired.
346 func (t *Immutable) Iterator(startKey, limitKey []byte) *Iterator {