vendor/github.com/btcsuite/btcd/database/internal/treap/treapiter_test.go

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