treapiter_test.go raw
1 package treap
2
3 import (
4 "bytes"
5 "encoding/binary"
6 "testing"
7 )
8
9 // TestMutableIterator ensures that the general behavior of mutable treap iterators is as expected including tests for
10 // first, last, ordered and reverse ordered iteration, limiting the range, seeking, and initially unpositioned.
11 func TestMutableIterator(t *testing.T) {
12 t.Parallel()
13 tests := []struct {
14 numKeys int
15 step int
16 startKey []byte
17 limitKey []byte
18 expectedFirst []byte
19 expectedLast []byte
20 seekKey []byte
21 expectedSeek []byte
22 }{
23 // No range limits. Values are the set (0, 1, 2, ..., 49).
24 // Seek existing value.
25 {
26 numKeys: 50,
27 step: 1,
28 expectedFirst: serializeUint32(0),
29 expectedLast: serializeUint32(49),
30 seekKey: serializeUint32(12),
31 expectedSeek: serializeUint32(12),
32 },
33 // Limited to range [24, end]. Values are the set
34 // (0, 2, 4, ..., 48). Seek value that doesn't exist and is
35 // greater than largest existing key.
36 {
37 numKeys: 50,
38 step: 2,
39 startKey: serializeUint32(24),
40 expectedFirst: serializeUint32(24),
41 expectedLast: serializeUint32(48),
42 seekKey: serializeUint32(49),
43 expectedSeek: nil,
44 },
45 // Limited to range [start, 25). Values are the set
46 // (0, 3, 6, ..., 48). Seek value that doesn't exist but is
47 // before an existing value within the range.
48 {
49 numKeys: 50,
50 step: 3,
51 limitKey: serializeUint32(25),
52 expectedFirst: serializeUint32(0),
53 expectedLast: serializeUint32(24),
54 seekKey: serializeUint32(17),
55 expectedSeek: serializeUint32(18),
56 },
57 // Limited to range [10, 21). Values are the set
58 // (0, 4, ..., 48). Seek value that exists, but is before the
59 // minimum allowed range.
60 {
61 numKeys: 50,
62 step: 4,
63 startKey: serializeUint32(10),
64 limitKey: serializeUint32(21),
65 expectedFirst: serializeUint32(12),
66 expectedLast: serializeUint32(20),
67 seekKey: serializeUint32(4),
68 expectedSeek: nil,
69 },
70 // Limited by prefix {0,0,0}, range [{0,0,0}, {0,0,1}).
71 // Since it's a bytewise compare, {0,0,0,...} < {0,0,1}.
72 // Seek existing value within the allowed range.
73 {
74 numKeys: 300,
75 step: 1,
76 startKey: []byte{0x00, 0x00, 0x00},
77 limitKey: []byte{0x00, 0x00, 0x01},
78 expectedFirst: serializeUint32(0),
79 expectedLast: serializeUint32(255),
80 seekKey: serializeUint32(100),
81 expectedSeek: serializeUint32(100),
82 },
83 }
84 testLoop:
85 for i, test := range tests {
86 // Insert a bunch of keys.
87 testTreap := NewMutable()
88 for j := 0; j < test.numKeys; j += test.step {
89 key := serializeUint32(uint32(j))
90 testTreap.Put(key, key)
91 }
92 // Create new iterator limited by the test chaincfg.
93 iter := testTreap.Iterator(test.startKey, test.limitKey)
94 // Ensure the first item is accurate.
95 hasFirst := iter.First()
96 if !hasFirst && test.expectedFirst != nil {
97 t.Errorf("First #%d: unexpected exhausted iterator", i)
98 continue
99 }
100 gotKey := iter.Key()
101 if !bytes.Equal(gotKey, test.expectedFirst) {
102 t.Errorf("First.Key #%d: unexpected key - got %x, "+
103 "want %x", i, gotKey, test.expectedFirst,
104 )
105 continue
106 }
107 gotVal := iter.Value()
108 if !bytes.Equal(gotVal, test.expectedFirst) {
109 t.Errorf("First.value #%d: unexpected value - got %x, "+
110 "want %x", i, gotVal, test.expectedFirst,
111 )
112 continue
113 }
114 // Ensure the iterator gives the expected items in order.
115 curNum := binary.BigEndian.Uint32(test.expectedFirst)
116 for iter.Next() {
117 curNum += uint32(test.step)
118 // Ensure key is as expected.
119 gotKey = iter.Key()
120 expectedKey := serializeUint32(curNum)
121 if !bytes.Equal(gotKey, expectedKey) {
122 t.Errorf("iter.Key #%d (%d): unexpected key - "+
123 "got %x, want %x", i, curNum, gotKey,
124 expectedKey,
125 )
126 continue testLoop
127 }
128 // Ensure value is as expected.
129 gotVal = iter.Value()
130 if !bytes.Equal(gotVal, expectedKey) {
131 t.Errorf("iter.value #%d (%d): unexpected "+
132 "value - got %x, want %x", i, curNum,
133 gotVal, expectedKey,
134 )
135 continue testLoop
136 }
137 }
138 // Ensure iterator is exhausted.
139 if iter.Valid() {
140 t.Errorf("Valid #%d: iterator should be exhausted", i)
141 continue
142 }
143 // Ensure the last item is accurate.
144 hasLast := iter.Last()
145 if !hasLast && test.expectedLast != nil {
146 t.Errorf("Last #%d: unexpected exhausted iterator", i)
147 continue
148 }
149 gotKey = iter.Key()
150 if !bytes.Equal(gotKey, test.expectedLast) {
151 t.Errorf("Last.Key #%d: unexpected key - got %x, "+
152 "want %x", i, gotKey, test.expectedLast,
153 )
154 continue
155 }
156 gotVal = iter.Value()
157 if !bytes.Equal(gotVal, test.expectedLast) {
158 t.Errorf("Last.value #%d: unexpected value - got %x, "+
159 "want %x", i, gotVal, test.expectedLast,
160 )
161 continue
162 }
163 // Ensure the iterator gives the expected items in reverse
164 // order.
165 curNum = binary.BigEndian.Uint32(test.expectedLast)
166 for iter.Prev() {
167 curNum -= uint32(test.step)
168 // Ensure key is as expected.
169 gotKey = iter.Key()
170 expectedKey := serializeUint32(curNum)
171 if !bytes.Equal(gotKey, expectedKey) {
172 t.Errorf("iter.Key #%d (%d): unexpected key - "+
173 "got %x, want %x", i, curNum, gotKey,
174 expectedKey,
175 )
176 continue testLoop
177 }
178 // Ensure value is as expected.
179 gotVal = iter.Value()
180 if !bytes.Equal(gotVal, expectedKey) {
181 t.Errorf("iter.value #%d (%d): unexpected "+
182 "value - got %x, want %x", i, curNum,
183 gotVal, expectedKey,
184 )
185 continue testLoop
186 }
187 }
188 // Ensure iterator is exhausted.
189 if iter.Valid() {
190 t.Errorf("Valid #%d: iterator should be exhausted", i)
191 continue
192 }
193 // Seek to the provided key.
194 seekValid := iter.Seek(test.seekKey)
195 if !seekValid && test.expectedSeek != nil {
196 t.Errorf("Seek #%d: unexpected exhausted iterator", i)
197 continue
198 }
199 gotKey = iter.Key()
200 if !bytes.Equal(gotKey, test.expectedSeek) {
201 t.Errorf("Seek.Key #%d: unexpected key - got %x, "+
202 "want %x", i, gotKey, test.expectedSeek,
203 )
204 continue
205 }
206 gotVal = iter.Value()
207 if !bytes.Equal(gotVal, test.expectedSeek) {
208 t.Errorf("Seek.value #%d: unexpected value - got %x, "+
209 "want %x", i, gotVal, test.expectedSeek,
210 )
211 continue
212 }
213 // Recreate the iterator and ensure calling Next on it before it
214 // has been positioned gives the first element.
215 iter = testTreap.Iterator(test.startKey, test.limitKey)
216 hasNext := iter.Next()
217 if !hasNext && test.expectedFirst != nil {
218 t.Errorf("Next #%d: unexpected exhausted iterator", i)
219 continue
220 }
221 gotKey = iter.Key()
222 if !bytes.Equal(gotKey, test.expectedFirst) {
223 t.Errorf("Next.Key #%d: unexpected key - got %x, "+
224 "want %x", i, gotKey, test.expectedFirst,
225 )
226 continue
227 }
228 gotVal = iter.Value()
229 if !bytes.Equal(gotVal, test.expectedFirst) {
230 t.Errorf("Next.value #%d: unexpected value - got %x, "+
231 "want %x", i, gotVal, test.expectedFirst,
232 )
233 continue
234 }
235 // Recreate the iterator and ensure calling Prev on it before it
236 // has been positioned gives the first element.
237 iter = testTreap.Iterator(test.startKey, test.limitKey)
238 hasPrev := iter.Prev()
239 if !hasPrev && test.expectedLast != nil {
240 t.Errorf("Prev #%d: unexpected exhausted iterator", i)
241 continue
242 }
243 gotKey = iter.Key()
244 if !bytes.Equal(gotKey, test.expectedLast) {
245 t.Errorf("Prev.Key #%d: unexpected key - got %x, "+
246 "want %x", i, gotKey, test.expectedLast,
247 )
248 continue
249 }
250 gotVal = iter.Value()
251 if !bytes.Equal(gotVal, test.expectedLast) {
252 t.Errorf("Next.value #%d: unexpected value - got %x, "+
253 "want %x", i, gotVal, test.expectedLast,
254 )
255 continue
256 }
257 }
258 }
259
260 // TestMutableEmptyIterator ensures that the various functions behave as expected when a mutable treap is empty.
261 func TestMutableEmptyIterator(t *testing.T) {
262 t.Parallel()
263 // Create iterator against empty treap.
264 testTreap := NewMutable()
265 iter := testTreap.Iterator(nil, nil)
266 // Ensure Valid on empty iterator reports it as exhausted.
267 if iter.Valid() {
268 t.Fatal("Valid: iterator should be exhausted")
269 }
270 // Ensure First and Last on empty iterator report it as exhausted.
271 if iter.First() {
272 t.Fatal("First: iterator should be exhausted")
273 }
274 if iter.Last() {
275 t.Fatal("Last: iterator should be exhausted")
276 }
277 // Ensure Next and Prev on empty iterator report it as exhausted.
278 if iter.Next() {
279 t.Fatal("Next: iterator should be exhausted")
280 }
281 if iter.Prev() {
282 t.Fatal("Prev: iterator should be exhausted")
283 }
284 // Ensure Key and value on empty iterator are nil.
285 if gotKey := iter.Key(); gotKey != nil {
286 t.Fatalf("Key: should be nil - got %q", gotKey)
287 }
288 if gotVal := iter.Value(); gotVal != nil {
289 t.Fatalf("value: should be nil - got %q", gotVal)
290 }
291 // Ensure Next and Prev report exhausted after forcing a reseek on an empty iterator.
292 iter.ForceReseek()
293 if iter.Next() {
294 t.Fatal("Next: iterator should be exhausted")
295 }
296 iter.ForceReseek()
297 if iter.Prev() {
298 t.Fatal("Prev: iterator should be exhausted")
299 }
300 }
301
302 // TestIteratorUpdates ensures that issuing a call to ForceReseek on an iterator that had the underlying mutable treap
303 // updated works as expected.
304 func TestIteratorUpdates(t *testing.T) {
305 t.Parallel()
306 // Create a new treap with various values inserted in no particular order. The resulting keys are the set (2, 4, 7,
307 // 11, 18, 25).
308 testTreap := NewMutable()
309 testTreap.Put(serializeUint32(7), nil)
310 testTreap.Put(serializeUint32(2), nil)
311 testTreap.Put(serializeUint32(18), nil)
312 testTreap.Put(serializeUint32(11), nil)
313 testTreap.Put(serializeUint32(25), nil)
314 testTreap.Put(serializeUint32(4), nil)
315 // Create an iterator against the treap with a range that excludes the lowest and highest entries. The limited set
316 // is then (4, 7, 11, 18)
317 iter := testTreap.Iterator(serializeUint32(3), serializeUint32(25))
318 // Delete a key from the middle of the range and notify the iterator to force a reseek.
319 testTreap.Delete(serializeUint32(11))
320 iter.ForceReseek()
321 // Ensure that calling Next on the iterator after the forced reseek gives the expected key. The limited set of keys
322 // at this point is (4, 7, 18) and the iterator has not yet been positioned.
323 if !iter.Next() {
324 t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
325 }
326 wantKey := serializeUint32(4)
327 gotKey := iter.Key()
328 if !bytes.Equal(gotKey, wantKey) {
329 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
330 gotKey, wantKey,
331 )
332 }
333 // Delete the key the iterator is currently position at and notify the iterator to force a reseek.
334 testTreap.Delete(serializeUint32(4))
335 iter.ForceReseek()
336 // Ensure that calling Next on the iterator after the forced reseek gives the expected key. The limited set of keys
337 // at this point is (7, 18) and the iterator is positioned at a deleted entry before 7.
338 if !iter.Next() {
339 t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
340 }
341 wantKey = serializeUint32(7)
342 gotKey = iter.Key()
343 if !bytes.Equal(gotKey, wantKey) {
344 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
345 gotKey, wantKey,
346 )
347 }
348 // Add a key before the current key the iterator is position at and notify the iterator to force a reseek.
349 testTreap.Put(serializeUint32(4), nil)
350 iter.ForceReseek()
351 // Ensure that calling Prev on the iterator after the forced reseek gives the expected key. The limited set of keys
352 // at this point is (4, 7, 18) and the iterator is positioned at 7.
353 if !iter.Prev() {
354 t.Fatal("ForceReseek.Prev: unexpected exhausted iterator")
355 }
356 wantKey = serializeUint32(4)
357 gotKey = iter.Key()
358 if !bytes.Equal(gotKey, wantKey) {
359 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
360 gotKey, wantKey,
361 )
362 }
363 // Delete the next key the iterator would ordinarily move to then notify the iterator to force a reseek.
364 testTreap.Delete(serializeUint32(7))
365 iter.ForceReseek()
366 // Ensure that calling Next on the iterator after the forced reseek gives the expected key. The limited set of keys
367 // at this point is (4, 18) and the iterator is positioned at 4.
368 if !iter.Next() {
369 t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
370 }
371 wantKey = serializeUint32(18)
372 gotKey = iter.Key()
373 if !bytes.Equal(gotKey, wantKey) {
374 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
375 gotKey, wantKey,
376 )
377 }
378 }
379
380 // TestImmutableIterator ensures that the general behavior of immutable treap iterators is as expected including tests
381 // for first, last, ordered and reverse ordered iteration, limiting the range, seeking, and initially unpositioned.
382 func TestImmutableIterator(t *testing.T) {
383 t.Parallel()
384 tests := []struct {
385 numKeys int
386 step int
387 startKey []byte
388 limitKey []byte
389 expectedFirst []byte
390 expectedLast []byte
391 seekKey []byte
392 expectedSeek []byte
393 }{
394 // No range limits. Values are the set (0, 1, 2, ..., 49).
395 // Seek existing value.
396 {
397 numKeys: 50,
398 step: 1,
399 expectedFirst: serializeUint32(0),
400 expectedLast: serializeUint32(49),
401 seekKey: serializeUint32(12),
402 expectedSeek: serializeUint32(12),
403 },
404 // Limited to range [24, end]. Values are the set
405 // (0, 2, 4, ..., 48). Seek value that doesn't exist and is
406 // greater than largest existing key.
407 {
408 numKeys: 50,
409 step: 2,
410 startKey: serializeUint32(24),
411 expectedFirst: serializeUint32(24),
412 expectedLast: serializeUint32(48),
413 seekKey: serializeUint32(49),
414 expectedSeek: nil,
415 },
416 // Limited to range [start, 25). Values are the set
417 // (0, 3, 6, ..., 48). Seek value that doesn't exist but is
418 // before an existing value within the range.
419 {
420 numKeys: 50,
421 step: 3,
422 limitKey: serializeUint32(25),
423 expectedFirst: serializeUint32(0),
424 expectedLast: serializeUint32(24),
425 seekKey: serializeUint32(17),
426 expectedSeek: serializeUint32(18),
427 },
428 // Limited to range [10, 21). Values are the set
429 // (0, 4, ..., 48). Seek value that exists, but is before the
430 // minimum allowed range.
431 {
432 numKeys: 50,
433 step: 4,
434 startKey: serializeUint32(10),
435 limitKey: serializeUint32(21),
436 expectedFirst: serializeUint32(12),
437 expectedLast: serializeUint32(20),
438 seekKey: serializeUint32(4),
439 expectedSeek: nil,
440 },
441 // Limited by prefix {0,0,0}, range [{0,0,0}, {0,0,1}).
442 // Since it's a bytewise compare, {0,0,0,...} < {0,0,1}.
443 // Seek existing value within the allowed range.
444 {
445 numKeys: 300,
446 step: 1,
447 startKey: []byte{0x00, 0x00, 0x00},
448 limitKey: []byte{0x00, 0x00, 0x01},
449 expectedFirst: serializeUint32(0),
450 expectedLast: serializeUint32(255),
451 seekKey: serializeUint32(100),
452 expectedSeek: serializeUint32(100),
453 },
454 }
455 testLoop:
456 for i, test := range tests {
457 // Insert a bunch of keys.
458 testTreap := NewImmutable()
459 for j := 0; j < test.numKeys; j += test.step {
460 key := serializeUint32(uint32(j))
461 testTreap = testTreap.Put(key, key)
462 }
463 // Create new iterator limited by the test chaincfg.
464 iter := testTreap.Iterator(test.startKey, test.limitKey)
465 // Ensure the first item is accurate.
466 hasFirst := iter.First()
467 if !hasFirst && test.expectedFirst != nil {
468 t.Errorf("First #%d: unexpected exhausted iterator", i)
469 continue
470 }
471 gotKey := iter.Key()
472 if !bytes.Equal(gotKey, test.expectedFirst) {
473 t.Errorf("First.Key #%d: unexpected key - got %x, "+
474 "want %x", i, gotKey, test.expectedFirst,
475 )
476 continue
477 }
478 gotVal := iter.Value()
479 if !bytes.Equal(gotVal, test.expectedFirst) {
480 t.Errorf("First.value #%d: unexpected value - got %x, "+
481 "want %x", i, gotVal, test.expectedFirst,
482 )
483 continue
484 }
485 // Ensure the iterator gives the expected items in order.
486 curNum := binary.BigEndian.Uint32(test.expectedFirst)
487 for iter.Next() {
488 curNum += uint32(test.step)
489 // Ensure key is as expected.
490 gotKey = iter.Key()
491 expectedKey := serializeUint32(curNum)
492 if !bytes.Equal(gotKey, expectedKey) {
493 t.Errorf("iter.Key #%d (%d): unexpected key - "+
494 "got %x, want %x", i, curNum, gotKey,
495 expectedKey,
496 )
497 continue testLoop
498 }
499 // Ensure value is as expected.
500 gotVal = iter.Value()
501 if !bytes.Equal(gotVal, expectedKey) {
502 t.Errorf("iter.value #%d (%d): unexpected "+
503 "value - got %x, want %x", i, curNum,
504 gotVal, expectedKey,
505 )
506 continue testLoop
507 }
508 }
509 // Ensure iterator is exhausted.
510 if iter.Valid() {
511 t.Errorf("Valid #%d: iterator should be exhausted", i)
512 continue
513 }
514 // Ensure the last item is accurate.
515 hasLast := iter.Last()
516 if !hasLast && test.expectedLast != nil {
517 t.Errorf("Last #%d: unexpected exhausted iterator", i)
518 continue
519 }
520 gotKey = iter.Key()
521 if !bytes.Equal(gotKey, test.expectedLast) {
522 t.Errorf("Last.Key #%d: unexpected key - got %x, "+
523 "want %x", i, gotKey, test.expectedLast,
524 )
525 continue
526 }
527 gotVal = iter.Value()
528 if !bytes.Equal(gotVal, test.expectedLast) {
529 t.Errorf("Last.value #%d: unexpected value - got %x, "+
530 "want %x", i, gotVal, test.expectedLast,
531 )
532 continue
533 }
534 // Ensure the iterator gives the expected items in reverse
535 // order.
536 curNum = binary.BigEndian.Uint32(test.expectedLast)
537 for iter.Prev() {
538 curNum -= uint32(test.step)
539 // Ensure key is as expected.
540 gotKey = iter.Key()
541 expectedKey := serializeUint32(curNum)
542 if !bytes.Equal(gotKey, expectedKey) {
543 t.Errorf("iter.Key #%d (%d): unexpected key - "+
544 "got %x, want %x", i, curNum, gotKey,
545 expectedKey,
546 )
547 continue testLoop
548 }
549 // Ensure value is as expected.
550 gotVal = iter.Value()
551 if !bytes.Equal(gotVal, expectedKey) {
552 t.Errorf("iter.value #%d (%d): unexpected "+
553 "value - got %x, want %x", i, curNum,
554 gotVal, expectedKey,
555 )
556 continue testLoop
557 }
558 }
559 // Ensure iterator is exhausted.
560 if iter.Valid() {
561 t.Errorf("Valid #%d: iterator should be exhausted", i)
562 continue
563 }
564 // Seek to the provided key.
565 seekValid := iter.Seek(test.seekKey)
566 if !seekValid && test.expectedSeek != nil {
567 t.Errorf("Seek #%d: unexpected exhausted iterator", i)
568 continue
569 }
570 gotKey = iter.Key()
571 if !bytes.Equal(gotKey, test.expectedSeek) {
572 t.Errorf("Seek.Key #%d: unexpected key - got %x, "+
573 "want %x", i, gotKey, test.expectedSeek,
574 )
575 continue
576 }
577 gotVal = iter.Value()
578 if !bytes.Equal(gotVal, test.expectedSeek) {
579 t.Errorf("Seek.value #%d: unexpected value - got %x, "+
580 "want %x", i, gotVal, test.expectedSeek,
581 )
582 continue
583 }
584 // Recreate the iterator and ensure calling Next on it before it
585 // has been positioned gives the first element.
586 iter = testTreap.Iterator(test.startKey, test.limitKey)
587 hasNext := iter.Next()
588 if !hasNext && test.expectedFirst != nil {
589 t.Errorf("Next #%d: unexpected exhausted iterator", i)
590 continue
591 }
592 gotKey = iter.Key()
593 if !bytes.Equal(gotKey, test.expectedFirst) {
594 t.Errorf("Next.Key #%d: unexpected key - got %x, "+
595 "want %x", i, gotKey, test.expectedFirst,
596 )
597 continue
598 }
599 gotVal = iter.Value()
600 if !bytes.Equal(gotVal, test.expectedFirst) {
601 t.Errorf("Next.value #%d: unexpected value - got %x, "+
602 "want %x", i, gotVal, test.expectedFirst,
603 )
604 continue
605 }
606 // Recreate the iterator and ensure calling Prev on it before it
607 // has been positioned gives the first element.
608 iter = testTreap.Iterator(test.startKey, test.limitKey)
609 hasPrev := iter.Prev()
610 if !hasPrev && test.expectedLast != nil {
611 t.Errorf("Prev #%d: unexpected exhausted iterator", i)
612 continue
613 }
614 gotKey = iter.Key()
615 if !bytes.Equal(gotKey, test.expectedLast) {
616 t.Errorf("Prev.Key #%d: unexpected key - got %x, "+
617 "want %x", i, gotKey, test.expectedLast,
618 )
619 continue
620 }
621 gotVal = iter.Value()
622 if !bytes.Equal(gotVal, test.expectedLast) {
623 t.Errorf("Next.value #%d: unexpected value - got %x, "+
624 "want %x", i, gotVal, test.expectedLast,
625 )
626 continue
627 }
628 }
629 }
630
631 // TestImmutableEmptyIterator ensures that the various functions behave as expected when an immutable treap is empty.
632 func TestImmutableEmptyIterator(t *testing.T) {
633 t.Parallel()
634 // Create iterator against empty treap.
635 testTreap := NewImmutable()
636 iter := testTreap.Iterator(nil, nil)
637 // Ensure Valid on empty iterator reports it as exhausted.
638 if iter.Valid() {
639 t.Fatal("Valid: iterator should be exhausted")
640 }
641 // Ensure First and Last on empty iterator report it as exhausted.
642 if iter.First() {
643 t.Fatal("First: iterator should be exhausted")
644 }
645 if iter.Last() {
646 t.Fatal("Last: iterator should be exhausted")
647 }
648 // Ensure Next and Prev on empty iterator report it as exhausted.
649 if iter.Next() {
650 t.Fatal("Next: iterator should be exhausted")
651 }
652 if iter.Prev() {
653 t.Fatal("Prev: iterator should be exhausted")
654 }
655 // Ensure Key and value on empty iterator are nil.
656 if gotKey := iter.Key(); gotKey != nil {
657 t.Fatalf("Key: should be nil - got %q", gotKey)
658 }
659 if gotVal := iter.Value(); gotVal != nil {
660 t.Fatalf("value: should be nil - got %q", gotVal)
661 }
662 // Ensure calling ForceReseek on an immutable treap iterator does not cause any issues since it only applies to
663 // mutable treap iterators.
664 iter.ForceReseek()
665 if iter.Next() {
666 t.Fatal("Next: iterator should be exhausted")
667 }
668 iter.ForceReseek()
669 if iter.Prev() {
670 t.Fatal("Prev: iterator should be exhausted")
671 }
672 }
673