tree_test.gno
65.06 Kb · 2593 lines
1package bptree
2
3import (
4 "math/rand"
5 "sort"
6 "testing"
7
8 "gno.land/p/nt/avl/v0"
9)
10
11//----------------------------------------
12// Basic operations
13
14func TestNewTree(t *testing.T) {
15 tree := NewBPTree32()
16 if tree.Size() != 0 {
17 t.Error("Expected empty tree size to be 0")
18 }
19}
20
21func TestZeroValue(t *testing.T) {
22 var tree BPTree
23 if tree.Size() != 0 {
24 t.Error("Expected zero-value tree size to be 0")
25 }
26 if tree.Has("x") {
27 t.Error("Expected Has to return false on zero-value tree")
28 }
29 if _, ok := tree.Get("x"); ok {
30 t.Error("Expected Get to return false on zero-value tree")
31 }
32 if _, ok := tree.Remove("x"); ok {
33 t.Error("Expected Remove to return false on zero-value tree")
34 }
35
36 // Set should work on zero-value tree.
37 if updated := tree.Set("a", 1); updated {
38 t.Error("Expected Set to return false for new key")
39 }
40 if tree.Size() != 1 {
41 t.Errorf("Expected size 1, got %d", tree.Size())
42 }
43 if v, ok := tree.Get("a"); !ok || v != 1 {
44 t.Errorf("Expected Get(a) = (1, true), got (%v, %v)", v, ok)
45 }
46}
47
48func TestSetAndGet(t *testing.T) {
49 tree := NewBPTreeN(4)
50 tree.Set("key1", "value1")
51 tree.Set("key2", "value2")
52
53 if tree.Size() != 2 {
54 t.Errorf("Expected size 2, got %d", tree.Size())
55 }
56
57 v, ok := tree.Get("key1")
58 if !ok || v != "value1" {
59 t.Errorf("Expected (value1, true), got (%v, %v)", v, ok)
60 }
61
62 _, ok = tree.Get("missing")
63 if ok {
64 t.Error("Expected Get to return false for missing key")
65 }
66}
67
68func TestSetUpdate(t *testing.T) {
69 tree := NewBPTreeN(4)
70 if updated := tree.Set("k", "v1"); updated {
71 t.Error("Expected false for new key")
72 }
73 if updated := tree.Set("k", "v2"); !updated {
74 t.Error("Expected true for existing key")
75 }
76 if tree.Size() != 1 {
77 t.Errorf("Expected size 1 after update, got %d", tree.Size())
78 }
79 if v, _ := tree.Get("k"); v != "v2" {
80 t.Errorf("Expected v2, got %v", v)
81 }
82}
83
84func TestHas(t *testing.T) {
85 tree := NewBPTreeN(4)
86 tree.Set("a", 1)
87 if !tree.Has("a") {
88 t.Error("Expected Has(a) = true")
89 }
90 if tree.Has("b") {
91 t.Error("Expected Has(b) = false")
92 }
93}
94
95func TestRemove(t *testing.T) {
96 tree := NewBPTreeN(4)
97 tree.Set("a", 1)
98 tree.Set("b", 2)
99
100 v, ok := tree.Remove("a")
101 if !ok || v != 1 {
102 t.Errorf("Expected (1, true), got (%v, %v)", v, ok)
103 }
104 if tree.Size() != 1 {
105 t.Errorf("Expected size 1, got %d", tree.Size())
106 }
107 if tree.Has("a") {
108 t.Error("Expected Has(a) = false after remove")
109 }
110
111 v, ok = tree.Remove("missing")
112 if ok || v != nil {
113 t.Errorf("Expected (nil, false), got (%v, %v)", v, ok)
114 }
115}
116
117func TestRemoveLastKey(t *testing.T) {
118 tree := NewBPTreeN(4)
119 tree.Set("a", 1)
120 tree.Remove("a")
121 if tree.Size() != 0 {
122 t.Errorf("Expected size 0, got %d", tree.Size())
123 }
124
125 // Insert after removing everything.
126 tree.Set("b", 2)
127 if tree.Size() != 1 {
128 t.Errorf("Expected size 1, got %d", tree.Size())
129 }
130 if v, ok := tree.Get("b"); !ok || v != 2 {
131 t.Errorf("Expected (2, true), got (%v, %v)", v, ok)
132 }
133}
134
135func TestNilValue(t *testing.T) {
136 tree := NewBPTreeN(4)
137 tree.Set("k", nil)
138 if !tree.Has("k") {
139 t.Error("Expected Has(k) = true for nil-valued entry")
140 }
141 v, ok := tree.Get("k")
142 if !ok {
143 t.Error("Expected key to exist")
144 }
145 if v != nil {
146 t.Errorf("Expected nil value, got %v", v)
147 }
148 v, ok = tree.Remove("k")
149 if !ok {
150 t.Error("Expected remove to succeed")
151 }
152 if v != nil {
153 t.Errorf("Expected nil removed value, got %v", v)
154 }
155}
156
157func TestEmptyStringKey(t *testing.T) {
158 tree := NewBPTreeN(4)
159 tree.Set("", "empty")
160 tree.Set("a", "alpha")
161 tree.Set("b", "beta")
162
163 if !tree.Has("") {
164 t.Error("Expected Has('') = true for empty string key")
165 }
166 if v, ok := tree.Get(""); !ok || v != "empty" {
167 t.Errorf("Expected (empty, true), got (%v, %v)", v, ok)
168 }
169 if tree.Size() != 3 {
170 t.Errorf("Expected size 3, got %d", tree.Size())
171 }
172
173 // Remove "" key.
174 v, ok := tree.Remove("")
175 if !ok || v != "empty" {
176 t.Errorf("Remove('') = (%v, %v), want (empty, true)", v, ok)
177 }
178 if tree.Size() != 2 {
179 t.Errorf("Expected size 2, got %d", tree.Size())
180 }
181 if tree.Has("") {
182 t.Error("Expected Has('') = false after remove")
183 }
184}
185
186func TestGetMissingReturnsNilFalse(t *testing.T) {
187 tree := NewBPTreeN(4)
188 tree.Set("a", 1)
189 v, ok := tree.Get("missing")
190 if v != nil {
191 t.Errorf("Expected nil value for missing key, got %v", v)
192 }
193 if ok {
194 t.Error("Expected false for missing key")
195 }
196}
197
198func TestRemoveMissingReturnsNilFalse(t *testing.T) {
199 tree := NewBPTreeN(4)
200 tree.Set("a", 1)
201 v, ok := tree.Remove("missing")
202 if v != nil {
203 t.Errorf("Expected nil value for missing remove, got %v", v)
204 }
205 if ok {
206 t.Error("Expected false for missing remove")
207 }
208
209 // Also on empty tree.
210 var empty BPTree
211 v, ok = empty.Remove("x")
212 if v != nil || ok {
213 t.Errorf("Remove on empty tree: got (%v, %v), want (nil, false)", v, ok)
214 }
215}
216
217func TestFanoutNeverResets(t *testing.T) {
218 var tree BPTree
219 tree.Set("a", 1)
220 tree.Remove("a")
221 // Tree is empty again, but fanout should still be 32.
222 tree.Set("b", 2)
223 if tree.Size() != 1 {
224 t.Errorf("Expected size 1, got %d", tree.Size())
225 }
226 if tree.fanout != 32 {
227 t.Errorf("Expected fanout 32 after re-insert, got %d", tree.fanout)
228 }
229}
230
231func TestSingleEntry(t *testing.T) {
232 tree := NewBPTreeN(4)
233 tree.Set("x", 42)
234
235 // Root should be a leaf for single entry.
236 if tree.root == nil {
237 t.Fatal("root is nil")
238 }
239 if !tree.root.isLeaf() {
240 t.Error("root should be a leaf for single entry")
241 }
242 if tree.Size() != 1 {
243 t.Errorf("Expected size 1, got %d", tree.Size())
244 }
245 k, v := tree.GetByIndex(0)
246 if k != "x" || v != 42 {
247 t.Errorf("GetByIndex(0) = (%v, %v), want (x, 42)", k, v)
248 }
249}
250
251//----------------------------------------
252// GetByIndex
253
254func TestGetByIndex(t *testing.T) {
255 tree := NewBPTreeN(4)
256 tree.Set("c", 3)
257 tree.Set("a", 1)
258 tree.Set("b", 2)
259
260 k, v := tree.GetByIndex(0)
261 if k != "a" || v != 1 {
262 t.Errorf("GetByIndex(0) = (%v, %v), want (a, 1)", k, v)
263 }
264 k, v = tree.GetByIndex(1)
265 if k != "b" || v != 2 {
266 t.Errorf("GetByIndex(1) = (%v, %v), want (b, 2)", k, v)
267 }
268 k, v = tree.GetByIndex(2)
269 if k != "c" || v != 3 {
270 t.Errorf("GetByIndex(2) = (%v, %v), want (c, 3)", k, v)
271 }
272}
273
274func TestGetByIndexPanics(t *testing.T) {
275 tree := NewBPTreeN(4)
276 tree.Set("a", 1)
277
278 assertPanics(t, "empty tree", func() {
279 var empty BPTree
280 empty.GetByIndex(0)
281 })
282 assertPanics(t, "negative index", func() {
283 tree.GetByIndex(-1)
284 })
285 assertPanics(t, "index == size", func() {
286 tree.GetByIndex(1)
287 })
288}
289
290//----------------------------------------
291// Iterate
292
293func TestIterate(t *testing.T) {
294 tree := NewBPTreeN(4)
295 tree.Set("a", 1)
296 tree.Set("b", 2)
297 tree.Set("c", 3)
298 tree.Set("d", 4)
299 tree.Set("e", 5)
300
301 // Full iteration.
302 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
303 return tr.Iterate("", "", cb)
304 })
305 assertSliceEqual(t, got, []string{"a", "b", "c", "d", "e"})
306
307 // Bounded iteration [b, d) → b, c.
308 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
309 return tr.Iterate("b", "d", cb)
310 })
311 assertSliceEqual(t, got, []string{"b", "c"})
312
313 // start == end → empty.
314 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
315 return tr.Iterate("b", "b", cb)
316 })
317 assertSliceEqual(t, got, nil)
318
319 // start > end → empty.
320 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
321 return tr.Iterate("z", "a", cb)
322 })
323 assertSliceEqual(t, got, nil)
324
325 // No lower bound.
326 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
327 return tr.Iterate("", "c", cb)
328 })
329 assertSliceEqual(t, got, []string{"a", "b"})
330
331 // Empty tree.
332 var empty BPTree
333 stopped := empty.Iterate("", "", func(k string, v any) bool {
334 t.Error("should not be called")
335 return false
336 })
337 if stopped {
338 t.Error("Expected false from Iterate on empty tree")
339 }
340}
341
342func TestIterateEarlyStop(t *testing.T) {
343 tree := NewBPTreeN(4)
344 tree.Set("a", 1)
345 tree.Set("b", 2)
346 tree.Set("c", 3)
347
348 count := 0
349 stopped := tree.Iterate("", "", func(k string, v any) bool {
350 count++
351 return true
352 })
353 if !stopped {
354 t.Error("Expected true from early-stopped Iterate")
355 }
356 if count != 1 {
357 t.Errorf("Expected 1 callback, got %d", count)
358 }
359}
360
361func TestIterateAllEdgeCases(t *testing.T) {
362 tree := NewBPTreeN(4)
363 tree.Set("a", 1)
364 tree.Set("b", 2)
365 tree.Set("c", 3)
366 tree.Set("d", 4)
367 tree.Set("e", 5)
368
369 // Iterate("a", "a") → empty [a,a).
370 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
371 return tr.Iterate("a", "a", cb)
372 })
373 assertSliceEqual(t, got, nil)
374
375 // Iterate("z", "a") → empty (start > end).
376 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
377 return tr.Iterate("z", "a", cb)
378 })
379 assertSliceEqual(t, got, nil)
380
381 // Iterate("", "a") → nothing < "a".
382 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
383 return tr.Iterate("", "a", cb)
384 })
385 assertSliceEqual(t, got, nil)
386
387 // Iterate("", "b") → just "a".
388 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
389 return tr.Iterate("", "b", cb)
390 })
391 assertSliceEqual(t, got, []string{"a"})
392
393 // ReverseIterate("a", "a") → visits "a" (both inclusive).
394 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
395 return tr.ReverseIterate("a", "a", cb)
396 })
397 assertSliceEqual(t, got, []string{"a"})
398
399 // ReverseIterate("z", "a") → empty (bounds don't swap).
400 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
401 return tr.ReverseIterate("z", "a", cb)
402 })
403 assertSliceEqual(t, got, nil)
404
405 // ReverseIterate("c", "") → keys >= "c" descending.
406 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
407 return tr.ReverseIterate("c", "", cb)
408 })
409 assertSliceEqual(t, got, []string{"e", "d", "c"})
410
411 // Iterate("", "a") on tree with key "" stored.
412 tree2 := NewBPTreeN(4)
413 tree2.Set("", "empty")
414 tree2.Set("a", "alpha")
415 tree2.Set("b", "beta")
416 got = collectKeys(tree2, func(tr *BPTree, cb IterCbFn) bool {
417 return tr.Iterate("", "a", cb)
418 })
419 assertSliceEqual(t, got, []string{""})
420
421 // Iterate("", "") visits all including "" key.
422 got = collectKeys(tree2, func(tr *BPTree, cb IterCbFn) bool {
423 return tr.Iterate("", "", cb)
424 })
425 assertSliceEqual(t, got, []string{"", "a", "b"})
426}
427
428func TestAllIterationEmptyTree(t *testing.T) {
429 var tree BPTree
430 noop := func(k string, v any) bool {
431 t.Error("should not be called")
432 return false
433 }
434 if tree.Iterate("", "", noop) {
435 t.Error("Iterate on empty tree should return false")
436 }
437 if tree.ReverseIterate("", "", noop) {
438 t.Error("ReverseIterate on empty tree should return false")
439 }
440 if tree.IterateByOffset(0, 1, noop) {
441 t.Error("IterateByOffset on empty tree should return false")
442 }
443 if tree.ReverseIterateByOffset(0, 1, noop) {
444 t.Error("ReverseIterateByOffset on empty tree should return false")
445 }
446}
447
448func TestReverseIterate(t *testing.T) {
449 tree := NewBPTreeN(4)
450 tree.Set("a", 1)
451 tree.Set("b", 2)
452 tree.Set("c", 3)
453 tree.Set("d", 4)
454 tree.Set("e", 5)
455
456 // Full reverse.
457 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
458 return tr.ReverseIterate("", "", cb)
459 })
460 assertSliceEqual(t, got, []string{"e", "d", "c", "b", "a"})
461
462 // Bounded [b, d] inclusive → d, c, b.
463 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
464 return tr.ReverseIterate("b", "d", cb)
465 })
466 assertSliceEqual(t, got, []string{"d", "c", "b"})
467
468 // start == end → visits that one key.
469 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
470 return tr.ReverseIterate("c", "c", cb)
471 })
472 assertSliceEqual(t, got, []string{"c"})
473
474 // start > end → empty.
475 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
476 return tr.ReverseIterate("z", "a", cb)
477 })
478 assertSliceEqual(t, got, nil)
479
480 // No upper bound.
481 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
482 return tr.ReverseIterate("c", "", cb)
483 })
484 assertSliceEqual(t, got, []string{"e", "d", "c"})
485
486 // end > max key → e, d, c, b, a.
487 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
488 return tr.ReverseIterate("a", "z", cb)
489 })
490 assertSliceEqual(t, got, []string{"e", "d", "c", "b", "a"})
491}
492
493func TestIterateByOffset(t *testing.T) {
494 tree := NewBPTreeN(4)
495 tree.Set("a", 1)
496 tree.Set("b", 2)
497 tree.Set("c", 3)
498 tree.Set("d", 4)
499 tree.Set("e", 5)
500
501 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
502 return tr.IterateByOffset(1, 3, cb)
503 })
504 assertSliceEqual(t, got, []string{"b", "c", "d"})
505
506 // offset=0, count=0 → nothing.
507 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
508 return tr.IterateByOffset(0, 0, cb)
509 })
510 assertSliceEqual(t, got, nil)
511
512 // offset=size → nothing.
513 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
514 return tr.IterateByOffset(5, 1, cb)
515 })
516 assertSliceEqual(t, got, nil)
517
518 // count exceeds remaining.
519 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
520 return tr.IterateByOffset(3, 100, cb)
521 })
522 assertSliceEqual(t, got, []string{"d", "e"})
523}
524
525func TestReverseIterateByOffset(t *testing.T) {
526 tree := NewBPTreeN(4)
527 tree.Set("a", 1)
528 tree.Set("b", 2)
529 tree.Set("c", 3)
530 tree.Set("d", 4)
531 tree.Set("e", 5)
532
533 // Full reverse.
534 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
535 return tr.ReverseIterateByOffset(0, 5, cb)
536 })
537 assertSliceEqual(t, got, []string{"e", "d", "c", "b", "a"})
538
539 // offset=1, count=2 → [d, c].
540 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
541 return tr.ReverseIterateByOffset(1, 2, cb)
542 })
543 assertSliceEqual(t, got, []string{"d", "c"})
544
545 // offset=4, count=1 → [a].
546 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
547 return tr.ReverseIterateByOffset(4, 1, cb)
548 })
549 assertSliceEqual(t, got, []string{"a"})
550
551 // offset=4, count=10 → [a].
552 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
553 return tr.ReverseIterateByOffset(4, 10, cb)
554 })
555 assertSliceEqual(t, got, []string{"a"})
556
557 // offset >= size → nothing.
558 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
559 return tr.ReverseIterateByOffset(5, 1, cb)
560 })
561 assertSliceEqual(t, got, nil)
562
563 // count=0 → nothing.
564 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
565 return tr.ReverseIterateByOffset(0, 0, cb)
566 })
567 assertSliceEqual(t, got, nil)
568
569 // negative offset
570 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
571 return tr.ReverseIterateByOffset(-1, 3, cb)
572 })
573 assertSliceEqual(t, got, []string{"e", "d", "c"})
574}
575
576func TestReverseIterateEarlyStop(t *testing.T) {
577 tree := NewBPTreeN(4)
578 tree.Set("a", 1)
579 tree.Set("b", 2)
580 tree.Set("c", 3)
581 count := 0
582 stopped := tree.ReverseIterate("", "", func(k string, v any) bool {
583 count++
584 return true
585 })
586 if !stopped {
587 t.Error("Expected true from early-stopped ReverseIterate")
588 }
589 if count != 1 {
590 t.Errorf("Expected 1 callback, got %d", count)
591 }
592}
593
594//----------------------------------------
595// Splits and merges (use small fanout to trigger them)
596
597func TestSplitAndMerge(t *testing.T) {
598 tree := NewBPTreeN(4)
599
600 // Insert enough keys to cause multiple splits.
601 keys := []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"}
602 for _, k := range keys {
603 tree.Set(k, k)
604 }
605 if tree.Size() != len(keys) {
606 t.Errorf("Expected size %d, got %d", len(keys), tree.Size())
607 }
608
609 // Verify all keys present and in order.
610 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
611 return tr.Iterate("", "", cb)
612 })
613 assertSliceEqual(t, got, keys)
614
615 // Verify GetByIndex works for all positions.
616 for i, k := range keys {
617 gk, gv := tree.GetByIndex(i)
618 if gk != k || gv != k {
619 t.Errorf("GetByIndex(%d) = (%v, %v), want (%v, %v)", i, gk, gv, k, k)
620 }
621 }
622
623 // Remove keys one by one and verify.
624 for _, k := range keys {
625 v, ok := tree.Remove(k)
626 if !ok || v != k {
627 t.Errorf("Remove(%v) = (%v, %v), want (%v, true)", k, v, ok, k)
628 }
629 }
630 if tree.Size() != 0 {
631 t.Errorf("Expected size 0 after removing all, got %d", tree.Size())
632 }
633}
634
635func TestRemoveFromMiddle(t *testing.T) {
636 tree := NewBPTreeN(4)
637 for _, k := range []string{"a", "b", "c", "d", "e", "f", "g", "h"} {
638 tree.Set(k, k)
639 }
640
641 // Remove from the middle to trigger redistributions and merges.
642 tree.Remove("d")
643 tree.Remove("e")
644 tree.Remove("b")
645 tree.Remove("g")
646
647 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
648 return tr.Iterate("", "", cb)
649 })
650 assertSliceEqual(t, got, []string{"a", "c", "f", "h"})
651 if tree.Size() != 4 {
652 t.Errorf("Expected size 4, got %d", tree.Size())
653 }
654}
655
656func TestSequentialInsertRemove(t *testing.T) {
657 tree := NewBPTreeN(4)
658
659 // Sequential insert.
660 n := 100
661 for i := 0; i < n; i++ {
662 k := intToKey(i)
663 tree.Set(k, i)
664 }
665 if tree.Size() != n {
666 t.Errorf("Expected size %d, got %d", n, tree.Size())
667 }
668
669 // Verify sorted order.
670 prev := ""
671 tree.Iterate("", "", func(k string, v any) bool {
672 if k <= prev && prev != "" {
673 t.Errorf("Keys not in order: %q after %q", k, prev)
674 }
675 prev = k
676 return false
677 })
678
679 // Remove all in reverse order.
680 for i := n - 1; i >= 0; i-- {
681 k := intToKey(i)
682 _, ok := tree.Remove(k)
683 if !ok {
684 t.Errorf("Remove(%v) failed", k)
685 }
686 }
687 if tree.Size() != 0 {
688 t.Errorf("Expected size 0, got %d", tree.Size())
689 }
690}
691
692func TestRandomInsertRemove(t *testing.T) {
693 tree := NewBPTreeN(4)
694
695 // Insert in "random" order (shuffled via simple hash).
696 keys := make([]string, 50)
697 for i := range keys {
698 keys[i] = intToKey((i*37 + 13) % 50)
699 }
700 for _, k := range keys {
701 tree.Set(k, k)
702 }
703 if tree.Size() != 50 {
704 t.Errorf("Expected size 50, got %d", tree.Size())
705 }
706
707 // Remove half.
708 for i := 0; i < 25; i++ {
709 tree.Remove(keys[i])
710 }
711 if tree.Size() != 25 {
712 t.Errorf("Expected size 25, got %d", tree.Size())
713 }
714
715 // Verify remaining keys are in sorted order.
716 prev := ""
717 tree.Iterate("", "", func(k string, v any) bool {
718 if k <= prev && prev != "" {
719 t.Errorf("Keys not in order: %q after %q", k, prev)
720 }
721 prev = k
722 return false
723 })
724}
725
726func TestDifferentFanouts(t *testing.T) {
727 for _, fanout := range []int{4, 5, 8, 16, 32} {
728 tree := NewBPTreeN(fanout)
729 n := 100
730 for i := 0; i < n; i++ {
731 tree.Set(intToKey(i), i)
732 }
733 if tree.Size() != n {
734 t.Errorf("fanout=%d: expected size %d, got %d", fanout, n, tree.Size())
735 }
736
737 // Verify order.
738 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
739 return tr.Iterate("", "", cb)
740 })
741 for i := 1; i < len(got); i++ {
742 if got[i] <= got[i-1] {
743 t.Errorf("fanout=%d: keys not in order at %d", fanout, i)
744 break
745 }
746 }
747
748 // Remove all.
749 for i := 0; i < n; i++ {
750 tree.Remove(intToKey(i))
751 }
752 if tree.Size() != 0 {
753 t.Errorf("fanout=%d: expected size 0 after remove all, got %d", fanout, tree.Size())
754 }
755 }
756}
757
758func TestNegativeCount(t *testing.T) {
759 tree := NewBPTreeN(4)
760 tree.Set("a", 1)
761
762 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
763 return tr.IterateByOffset(0, -1, cb)
764 })
765 assertSliceEqual(t, got, nil)
766
767 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
768 return tr.ReverseIterateByOffset(0, -1, cb)
769 })
770 assertSliceEqual(t, got, nil)
771}
772
773func TestRootCollapse(t *testing.T) {
774 tree := NewBPTreeN(4)
775 // Insert enough to create inner nodes.
776 for _, k := range []string{"a", "b", "c", "d", "e"} {
777 tree.Set(k, k)
778 }
779 if tree.root.isLeaf() {
780 t.Error("Expected inner root after 5 inserts with fanout 4")
781 }
782
783 // Remove enough to trigger merges and root collapse.
784 tree.Remove("a")
785 tree.Remove("b")
786 tree.Remove("c")
787 // With only "d" and "e" left, root should collapse to a leaf.
788 if !tree.root.isLeaf() {
789 t.Error("Expected leaf root after removing down to 2 entries")
790 }
791 if tree.Size() != 2 {
792 t.Errorf("Expected size 2, got %d", tree.Size())
793 }
794 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
795 return tr.Iterate("", "", cb)
796 })
797 assertSliceEqual(t, got, []string{"d", "e"})
798}
799
800func TestSeparatorKeyAfterLeftmostDeletion(t *testing.T) {
801 tree := NewBPTreeN(4)
802 // Insert keys to create a split.
803 for _, k := range []string{"a", "b", "c", "d", "e", "f", "g", "h"} {
804 tree.Set(k, k)
805 }
806 // Remove leftmost key "a" — should trigger separator update.
807 tree.Remove("a")
808
809 // Verify all remaining keys are accessible.
810 for _, k := range []string{"b", "c", "d", "e", "f", "g", "h"} {
811 if !tree.Has(k) {
812 t.Errorf("Expected Has(%s) = true after removing 'a'", k)
813 }
814 }
815 if tree.Has("a") {
816 t.Error("Expected Has(a) = false")
817 }
818
819 // Verify sorted order.
820 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
821 return tr.Iterate("", "", cb)
822 })
823 assertSliceEqual(t, got, []string{"b", "c", "d", "e", "f", "g", "h"})
824
825 // Verify GetByIndex still works.
826 k, _ := tree.GetByIndex(0)
827 if k != "b" {
828 t.Errorf("GetByIndex(0) = %v, want b", k)
829 }
830}
831
832func TestNinetyTenSplit(t *testing.T) {
833 // Sequential inserts should trigger 90/10 splits, keeping left leaves ~97% full.
834 tree := NewBPTreeN(4)
835 for _, k := range []string{"a", "b", "c", "d", "e"} {
836 tree.Set(k, k)
837 }
838 // After inserting a,b,c,d (leaf full), then e (append → 90/10 split):
839 // Left should have fanout-1=3 entries [a,b,c], right should have 2 entries [d,e].
840 if !tree.root.isLeaf() == true {
841 // Root should be an inner node after split.
842 }
843 inner := tree.root.(*innerNode)
844 left := inner.children[0].(*leafNode)
845 right := inner.children[1].(*leafNode)
846 if len(left.keys) != 3 {
847 t.Errorf("90/10 split: left leaf has %d entries, want 3", len(left.keys))
848 }
849 if len(right.keys) != 2 {
850 t.Errorf("90/10 split: right leaf has %d entries, want 2", len(right.keys))
851 }
852
853 // Verify all keys accessible.
854 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
855 return tr.Iterate("", "", cb)
856 })
857 assertSliceEqual(t, got, []string{"a", "b", "c", "d", "e"})
858}
859
860func TestNinetyTenSplitLargeFanout(t *testing.T) {
861 // With fanout=32, sequential inserts should produce high fill factor.
862 tree := NewBPTree32()
863 n := 200
864 for i := 0; i < n; i++ {
865 tree.Set(intToKey(i), i)
866 }
867 if tree.Size() != n {
868 t.Errorf("Expected size %d, got %d", n, tree.Size())
869 }
870
871 // Verify all keys in order.
872 prev := ""
873 count := 0
874 tree.Iterate("", "", func(k string, v any) bool {
875 if k <= prev && prev != "" {
876 t.Errorf("Keys not in order: %q after %q", k, prev)
877 }
878 prev = k
879 count++
880 return false
881 })
882 if count != n {
883 t.Errorf("Iterate visited %d entries, want %d", count, n)
884 }
885
886 // Remove all and verify.
887 for i := 0; i < n; i++ {
888 _, ok := tree.Remove(intToKey(i))
889 if !ok {
890 t.Errorf("Remove(%s) failed", intToKey(i))
891 }
892 }
893 if tree.Size() != 0 {
894 t.Errorf("Expected size 0, got %d", tree.Size())
895 }
896}
897
898func TestMixedSplitTypes(t *testing.T) {
899 // Sequential inserts trigger 90/10, then a middle insert triggers 50/50.
900 tree := NewBPTreeN(4)
901 // Sequential: triggers 90/10 split.
902 for _, k := range []string{"b", "c", "d", "e"} {
903 tree.Set(k, k)
904 }
905 // Insert "a" at the beginning of the left leaf — not an append, so if
906 // that leaf overflows it will use 50/50.
907 tree.Set("a", "a")
908
909 // Verify all keys present and sorted.
910 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
911 return tr.Iterate("", "", cb)
912 })
913 assertSliceEqual(t, got, []string{"a", "b", "c", "d", "e"})
914}
915
916func TestSizeCacheConsistency(t *testing.T) {
917 tree := NewBPTreeN(4)
918 keys := []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"}
919
920 // Check after each insert.
921 for _, k := range keys {
922 tree.Set(k, k)
923 verifySizeCache(t, tree.root)
924 }
925
926 // Check after each remove.
927 for _, k := range keys {
928 tree.Remove(k)
929 verifySizeCache(t, tree.root)
930 }
931
932 // Also check with large fanout.
933 tree2 := NewBPTree32()
934 for i := 0; i < 100; i++ {
935 tree2.Set(intToKey(i), i)
936 }
937 verifySizeCache(t, tree2.root)
938 for i := 0; i < 100; i++ {
939 tree2.Remove(intToKey(i))
940 verifySizeCache(t, tree2.root)
941 }
942}
943
944func verifySizeCache(t *testing.T, n node) {
945 t.Helper()
946 if n == nil || n.isLeaf() {
947 return
948 }
949 inner := n.(*innerNode)
950 // Verify each sizes[i] matches the actual child subtree size.
951 for i, child := range inner.children {
952 actual := child.nodeSize()
953 if inner.sizes[i] != actual {
954 t.Errorf("innerNode.sizes[%d]=%d but child.nodeSize()=%d", i, inner.sizes[i], actual)
955 }
956 verifySizeCache(t, child)
957 }
958}
959
960func TestValueIndirection(t *testing.T) {
961 tree := NewBPTreeN(4)
962
963 // Nil value through *any.
964 tree.Set("nil", nil)
965 v, ok := tree.Get("nil")
966 if !ok {
967 t.Error("Expected key 'nil' to exist")
968 }
969 if v != nil {
970 t.Errorf("Expected nil value, got %v", v)
971 }
972
973 // Various types.
974 tree.Set("int", 42)
975 tree.Set("str", "hello")
976 tree.Set("slice", []byte{1, 2, 3})
977
978 if v, _ := tree.Get("int"); v != 42 {
979 t.Errorf("Expected 42, got %v", v)
980 }
981 if v, _ := tree.Get("str"); v != "hello" {
982 t.Errorf("Expected hello, got %v", v)
983 }
984 if v, _ := tree.Get("slice"); len(v.([]byte)) != 3 {
985 t.Errorf("Expected 3-byte slice, got %v", v)
986 }
987
988 // Update value in place (should reuse the *any pointer).
989 tree.Set("int", 99)
990 if v, _ := tree.Get("int"); v != 99 {
991 t.Errorf("Expected 99 after update, got %v", v)
992 }
993
994 // Remove nil value.
995 v, ok = tree.Remove("nil")
996 if !ok || v != nil {
997 t.Errorf("Remove nil: got (%v, %v), want (nil, true)", v, ok)
998 }
999
1000 // Remove typed value.
1001 v, ok = tree.Remove("int")
1002 if !ok || v != 99 {
1003 t.Errorf("Remove int: got (%v, %v), want (99, true)", v, ok)
1004 }
1005
1006 // Large string values — each stored as separate *any object.
1007 bigVal := make([]byte, 10000)
1008 for i := range bigVal {
1009 bigVal[i] = byte(i % 256)
1010 }
1011 for i := 0; i < 10; i++ {
1012 tree.Set(intToKey(i), string(bigVal))
1013 }
1014 if tree.Size() != 12 { // 10 new + "str" + "slice" remaining
1015 t.Errorf("Expected size 12, got %d", tree.Size())
1016 }
1017
1018 // Verify large values round-trip correctly.
1019 for i := 0; i < 10; i++ {
1020 v, ok := tree.Get(intToKey(i))
1021 if !ok {
1022 t.Errorf("Missing key %s", intToKey(i))
1023 continue
1024 }
1025 s := v.(string)
1026 if len(s) != 10000 {
1027 t.Errorf("Key %s: expected 10000-byte string, got %d", intToKey(i), len(s))
1028 }
1029 }
1030
1031 // Iteration with mixed values.
1032 count := 0
1033 tree.Iterate("", "", func(k string, v any) bool {
1034 count++
1035 return false
1036 })
1037 if count != 12 {
1038 t.Errorf("Iterate counted %d, want 12", count)
1039 }
1040
1041 // Remove all and verify clean.
1042 for i := 0; i < 10; i++ {
1043 tree.Remove(intToKey(i))
1044 }
1045 tree.Remove("str")
1046 tree.Remove("slice")
1047 if tree.Size() != 0 {
1048 t.Errorf("Expected empty tree, got size %d", tree.Size())
1049 }
1050}
1051
1052func TestFanoutPanics(t *testing.T) {
1053 assertPanics(t, "fanout 3", func() {
1054 NewBPTreeN(3)
1055 })
1056 assertPanics(t, "fanout 0", func() {
1057 NewBPTreeN(0)
1058 })
1059}
1060
1061//----------------------------------------
1062// Ported from avl/v0 node_test.gno
1063
1064func TestHasTableDriven(t *testing.T) {
1065 tests := []struct {
1066 name string
1067 input []string
1068 hasKey string
1069 expected bool
1070 }{
1071 {"has key in non-empty tree", []string{"C", "A", "B", "E", "D"}, "B", true},
1072 {"does not have key in non-empty tree", []string{"C", "A", "B", "E", "D"}, "F", false},
1073 {"has key in single-node tree", []string{"A"}, "A", true},
1074 {"does not have key in single-node tree", []string{"A"}, "B", false},
1075 {"does not have key in empty tree", []string{}, "A", false},
1076 }
1077 for _, tt := range tests {
1078 t.Run(tt.name, func(t *testing.T) {
1079 tree := NewBPTreeN(4)
1080 for _, key := range tt.input {
1081 tree.Set(key, nil)
1082 }
1083 result := tree.Has(tt.hasKey)
1084 if result != tt.expected {
1085 t.Errorf("Expected %v, got %v", tt.expected, result)
1086 }
1087 })
1088 }
1089}
1090
1091func TestGetByIndexTableDriven(t *testing.T) {
1092 tests := []struct {
1093 name string
1094 input []string
1095 idx int
1096 expectKey string
1097 expectPanic bool
1098 }{
1099 {"get by valid index", []string{"C", "A", "B", "E", "D"}, 2, "C", false},
1100 {"get by valid index (smallest)", []string{"C", "A", "B", "E", "D"}, 0, "A", false},
1101 {"get by valid index (largest)", []string{"C", "A", "B", "E", "D"}, 4, "E", false},
1102 {"get by invalid index (negative)", []string{"C", "A", "B", "E", "D"}, -1, "", true},
1103 {"get by invalid index (out of range)", []string{"C", "A", "B", "E", "D"}, 5, "", true},
1104 }
1105 for _, tt := range tests {
1106 t.Run(tt.name, func(t *testing.T) {
1107 tree := NewBPTreeN(4)
1108 for _, key := range tt.input {
1109 tree.Set(key, nil)
1110 }
1111 if tt.expectPanic {
1112 defer func() {
1113 if r := recover(); r == nil {
1114 t.Errorf("Expected a panic but didn't get one")
1115 }
1116 }()
1117 }
1118 key, _ := tree.GetByIndex(tt.idx)
1119 if !tt.expectPanic && key != tt.expectKey {
1120 t.Errorf("Expected key %s, got %s", tt.expectKey, key)
1121 }
1122 })
1123 }
1124}
1125
1126func TestRemoveTableDriven(t *testing.T) {
1127 tests := []struct {
1128 name string
1129 input []string
1130 removeKey string
1131 expected []string
1132 }{
1133 {"remove from middle", []string{"C", "A", "B", "D"}, "B", []string{"A", "C", "D"}},
1134 {"remove first key", []string{"C", "A", "B", "D"}, "A", []string{"B", "C", "D"}},
1135 {"remove last key", []string{"C", "A", "B", "E", "D"}, "E", []string{"A", "B", "C", "D"}},
1136 {"remove root-equivalent key", []string{"C", "A", "B", "E", "D"}, "C", []string{"A", "B", "D", "E"}},
1137 {"remove non-existent key", []string{"C", "A", "B", "E", "D"}, "F", []string{"A", "B", "C", "D", "E"}},
1138 }
1139 for _, tt := range tests {
1140 t.Run(tt.name, func(t *testing.T) {
1141 tree := NewBPTreeN(4)
1142 for _, key := range tt.input {
1143 tree.Set(key, nil)
1144 }
1145 tree.Remove(tt.removeKey)
1146 var result []string
1147 tree.Iterate("", "", func(key string, value any) bool {
1148 result = append(result, key)
1149 return false
1150 })
1151 if len(result) == 0 {
1152 result = []string{}
1153 }
1154 assertSliceEqual(t, result, tt.expected)
1155 })
1156 }
1157}
1158
1159func TestTraverse(t *testing.T) {
1160 tests := []struct {
1161 name string
1162 input []string
1163 expected []string
1164 }{
1165 {"empty tree", []string{}, []string{}},
1166 {"single node tree", []string{"A"}, []string{"A"}},
1167 {"small tree", []string{"C", "A", "B", "E", "D"}, []string{"A", "B", "C", "D", "E"}},
1168 {"large tree", []string{"H", "D", "L", "B", "F", "J", "N", "A", "C", "E", "G", "I", "K", "M", "O"},
1169 []string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"}},
1170 }
1171 for _, tt := range tests {
1172 t.Run(tt.name, func(t *testing.T) {
1173 tree := NewBPTreeN(4)
1174 for _, key := range tt.input {
1175 tree.Set(key, nil)
1176 }
1177
1178 t.Run("iterate", func(t *testing.T) {
1179 var result []string
1180 tree.Iterate("", "", func(key string, value any) bool {
1181 result = append(result, key)
1182 return false
1183 })
1184 if len(result) == 0 {
1185 result = []string{}
1186 }
1187 assertSliceEqual(t, result, tt.expected)
1188 })
1189
1190 t.Run("ReverseIterate", func(t *testing.T) {
1191 var result []string
1192 tree.ReverseIterate("", "", func(key string, value any) bool {
1193 result = append(result, key)
1194 return false
1195 })
1196 expected := make([]string, len(tt.expected))
1197 copy(expected, tt.expected)
1198 for i, j := 0, len(expected)-1; i < j; i, j = i+1, j-1 {
1199 expected[i], expected[j] = expected[j], expected[i]
1200 }
1201 if len(result) == 0 {
1202 result = []string{}
1203 }
1204 assertSliceEqual(t, result, expected)
1205 })
1206
1207 t.Run("TraverseInRange", func(t *testing.T) {
1208 var result []string
1209 start, end := "C", "M"
1210 tree.Iterate(start, end, func(key string, value any) bool {
1211 result = append(result, key)
1212 return false
1213 })
1214 expected := make([]string, 0)
1215 for _, key := range tt.expected {
1216 if key >= start && key < end {
1217 expected = append(expected, key)
1218 }
1219 }
1220 if len(result) == 0 {
1221 result = []string{}
1222 }
1223 assertSliceEqual(t, result, expected)
1224 })
1225
1226 t.Run("early termination", func(t *testing.T) {
1227 if len(tt.input) == 0 {
1228 return
1229 }
1230 var result []string
1231 var count int
1232 tree.Iterate("", "", func(key string, value any) bool {
1233 count++
1234 result = append(result, key)
1235 return true
1236 })
1237 if count != 1 {
1238 t.Errorf("Expected callback to be called exactly once, got %d calls", count)
1239 }
1240 if len(result) != 1 {
1241 t.Errorf("Expected exactly one result, got %d items", len(result))
1242 }
1243 if len(result) > 0 && result[0] != tt.expected[0] {
1244 t.Errorf("Expected first item to be %v, got %v", tt.expected[0], result[0])
1245 }
1246 })
1247 })
1248 }
1249}
1250
1251func TestTraverseByOffset(t *testing.T) {
1252 sl := []string{"Alfa", "Alfred", "Alpha", "Alphabet", "Beta", "Beth", "Book", "Browser"}
1253
1254 // Insert in reverse order to ensure ordering is independent of insertion order.
1255 reversed := make([]string, len(sl))
1256 copy(reversed, sl)
1257 for i, j := 0, len(reversed)-1; i < j; i, j = i+1, j-1 {
1258 reversed[i], reversed[j] = reversed[j], reversed[i]
1259 }
1260
1261 t.Run("ascending", func(t *testing.T) {
1262 tree := NewBPTreeN(4)
1263 for _, v := range reversed {
1264 tree.Set(v, nil)
1265 }
1266
1267 // Single-element offset traversal.
1268 var result []string
1269 for i := 0; i < len(sl); i++ {
1270 tree.IterateByOffset(i, 1, func(key string, value any) bool {
1271 result = append(result, key)
1272 return false
1273 })
1274 }
1275 assertSliceEqual(t, result, sl)
1276
1277 // Sliding window.
1278 for l := 2; l <= len(sl); l++ {
1279 for i := 0; i <= len(sl); i++ {
1280 max := i + l
1281 if max > len(sl) {
1282 max = len(sl)
1283 }
1284 exp := sl[i:max]
1285 var actual []string
1286 tree.IterateByOffset(i, l, func(key string, value any) bool {
1287 actual = append(actual, key)
1288 return false
1289 })
1290 if len(actual) == 0 {
1291 actual = []string{}
1292 }
1293 assertSliceEqual(t, actual, exp)
1294 }
1295 }
1296 })
1297
1298 t.Run("descending", func(t *testing.T) {
1299 tree := NewBPTreeN(4)
1300 for _, v := range reversed {
1301 tree.Set(v, nil)
1302 }
1303
1304 // The descending order.
1305 desc := make([]string, len(sl))
1306 copy(desc, sl)
1307 for i, j := 0, len(desc)-1; i < j; i, j = i+1, j-1 {
1308 desc[i], desc[j] = desc[j], desc[i]
1309 }
1310
1311 // Single-element offset traversal in reverse.
1312 var result []string
1313 for i := 0; i < len(desc); i++ {
1314 tree.ReverseIterateByOffset(i, 1, func(key string, value any) bool {
1315 result = append(result, key)
1316 return false
1317 })
1318 }
1319 assertSliceEqual(t, result, desc)
1320
1321 // Sliding window in descending.
1322 for l := 2; l <= len(desc); l++ {
1323 for i := 0; i <= len(desc); i++ {
1324 max := i + l
1325 if max > len(desc) {
1326 max = len(desc)
1327 }
1328 exp := desc[i:max]
1329 var actual []string
1330 tree.ReverseIterateByOffset(i, l, func(key string, value any) bool {
1331 actual = append(actual, key)
1332 return false
1333 })
1334 if len(actual) == 0 {
1335 actual = []string{}
1336 }
1337 assertSliceEqual(t, actual, exp)
1338 }
1339 }
1340 })
1341}
1342
1343func TestBSTProperty(t *testing.T) {
1344 tree := NewBPTreeN(4)
1345 keys := []string{"D", "B", "F", "A", "C", "E", "G"}
1346 for _, key := range keys {
1347 tree.Set(key, nil)
1348 }
1349
1350 var result []string
1351 tree.Iterate("", "", func(key string, value any) bool {
1352 result = append(result, key)
1353 return false
1354 })
1355
1356 for i := 1; i < len(result); i++ {
1357 if result[i] < result[i-1] {
1358 t.Errorf("Sorted property violated: %s < %s (index %d)",
1359 result[i], result[i-1], i)
1360 }
1361 }
1362}
1363
1364func TestRemoveFromEmptyTree(t *testing.T) {
1365 var tree BPTree
1366 val, removed := tree.Remove("NonExistent")
1367 if val != nil || removed {
1368 t.Errorf("Expected no value and removed=false when removing from empty tree")
1369 }
1370}
1371
1372// Ported from avl tree_test.gno
1373
1374func TestPortedTreeSize(t *testing.T) {
1375 tree := NewBPTree32()
1376 if tree.Size() != 0 {
1377 t.Error("Expected empty tree size to be 0")
1378 }
1379 tree.Set("key1", "value1")
1380 tree.Set("key2", "value2")
1381 if tree.Size() != 2 {
1382 t.Error("Expected tree size to be 2")
1383 }
1384}
1385
1386func TestPortedTreeHas(t *testing.T) {
1387 tree := NewBPTree32()
1388 tree.Set("key1", "value1")
1389 if !tree.Has("key1") {
1390 t.Error("Expected tree to have key1")
1391 }
1392 if tree.Has("key2") {
1393 t.Error("Expected tree to not have key2")
1394 }
1395}
1396
1397func TestPortedTreeGet(t *testing.T) {
1398 tree := NewBPTree32()
1399 tree.Set("key1", "value1")
1400 value, exists := tree.Get("key1")
1401 if !exists || value != "value1" {
1402 t.Error("Expected Get to return value1 and true")
1403 }
1404 _, exists = tree.Get("key2")
1405 if exists {
1406 t.Error("Expected Get to return false for non-existent key")
1407 }
1408}
1409
1410func TestPortedTreeGetByIndex(t *testing.T) {
1411 tree := NewBPTree32()
1412 tree.Set("key1", "value1")
1413 tree.Set("key2", "value2")
1414 key, value := tree.GetByIndex(0)
1415 if key != "key1" || value != "value1" {
1416 t.Error("Expected GetByIndex(0) to return key1 and value1")
1417 }
1418 key, value = tree.GetByIndex(1)
1419 if key != "key2" || value != "value2" {
1420 t.Error("Expected GetByIndex(1) to return key2 and value2")
1421 }
1422 defer func() {
1423 if r := recover(); r == nil {
1424 t.Error("Expected GetByIndex to panic for out-of-range index")
1425 }
1426 }()
1427 tree.GetByIndex(2)
1428}
1429
1430func TestPortedTreeRemove(t *testing.T) {
1431 tree := NewBPTree32()
1432 tree.Set("key1", "value1")
1433 value, removed := tree.Remove("key1")
1434 if !removed || value != "value1" || tree.Size() != 0 {
1435 t.Error("Expected Remove to remove key-value pair")
1436 }
1437 _, removed = tree.Remove("key2")
1438 if removed {
1439 t.Error("Expected Remove to return false for non-existent key")
1440 }
1441}
1442
1443func TestPortedTreeIterate(t *testing.T) {
1444 tree := NewBPTree32()
1445 tree.Set("key1", "value1")
1446 tree.Set("key2", "value2")
1447 tree.Set("key3", "value3")
1448 var keys []string
1449 tree.Iterate("", "", func(key string, value any) bool {
1450 keys = append(keys, key)
1451 return false
1452 })
1453 assertSliceEqual(t, keys, []string{"key1", "key2", "key3"})
1454}
1455
1456func TestPortedTreeReverseIterate(t *testing.T) {
1457 tree := NewBPTree32()
1458 tree.Set("key1", "value1")
1459 tree.Set("key2", "value2")
1460 tree.Set("key3", "value3")
1461 var keys []string
1462 tree.ReverseIterate("", "", func(key string, value any) bool {
1463 keys = append(keys, key)
1464 return false
1465 })
1466 assertSliceEqual(t, keys, []string{"key3", "key2", "key1"})
1467}
1468
1469func TestPortedTreeIterateByOffset(t *testing.T) {
1470 tree := NewBPTree32()
1471 tree.Set("key1", "value1")
1472 tree.Set("key2", "value2")
1473 tree.Set("key3", "value3")
1474 var keys []string
1475 tree.IterateByOffset(1, 2, func(key string, value any) bool {
1476 keys = append(keys, key)
1477 return false
1478 })
1479 assertSliceEqual(t, keys, []string{"key2", "key3"})
1480}
1481
1482func TestPortedTreeReverseIterateByOffset(t *testing.T) {
1483 tree := NewBPTree32()
1484 tree.Set("key1", "value1")
1485 tree.Set("key2", "value2")
1486 tree.Set("key3", "value3")
1487 var keys []string
1488 tree.ReverseIterateByOffset(1, 2, func(key string, value any) bool {
1489 keys = append(keys, key)
1490 return false
1491 })
1492 assertSliceEqual(t, keys, []string{"key2", "key1"})
1493}
1494
1495func TestPortedReverseIterateByOffsetVaried(t *testing.T) {
1496 tree := NewBPTree32()
1497 tree.Set("a", 1)
1498 tree.Set("b", 2)
1499 tree.Set("c", 3)
1500 tree.Set("d", 4)
1501 tree.Set("e", 5)
1502
1503 cases := []struct {
1504 offset int
1505 limit int
1506 want []string
1507 }{
1508 {0, 5, []string{"e", "d", "c", "b", "a"}},
1509 {0, 1, []string{"e"}},
1510 {0, 3, []string{"e", "d", "c"}},
1511 {1, 2, []string{"d", "c"}},
1512 {2, 2, []string{"c", "b"}},
1513 {3, 5, []string{"b", "a"}},
1514 {4, 1, []string{"a"}},
1515 {4, 10, []string{"a"}},
1516 {5, 1, nil},
1517 {0, 0, nil},
1518 {10, 1, nil},
1519 }
1520
1521 for _, tc := range cases {
1522 var got []string
1523 tree.ReverseIterateByOffset(tc.offset, tc.limit, func(key string, value any) bool {
1524 got = append(got, key)
1525 return false
1526 })
1527 if !slicesEqual(got, tc.want) {
1528 t.Errorf("ReverseIterateByOffset(%d, %d): got %v, want %v",
1529 tc.offset, tc.limit, got, tc.want)
1530 }
1531 }
1532
1533 // Early termination.
1534 var got []string
1535 tree.ReverseIterateByOffset(1, 5, func(key string, value any) bool {
1536 got = append(got, key)
1537 return len(got) >= 2
1538 })
1539 assertSliceEqual(t, got, []string{"d", "c"})
1540}
1541
1542func TestPortedBalanceAfterRemoval(t *testing.T) {
1543 // This tests the behavioral equivalence: after various insert/remove
1544 // patterns, the tree maintains correct sorted order and all keys are
1545 // accessible. (AVL tests checked balance factors; we check correctness.)
1546 tests := []struct {
1547 name string
1548 insertKeys []string
1549 removeKey string
1550 }{
1551 {"remove right node", []string{"B", "A", "D", "C", "E"}, "E"},
1552 {"remove left node", []string{"D", "B", "E", "A", "C"}, "A"},
1553 {"remove after complex insert", []string{"C", "B", "E", "A", "D", "F"}, "F"},
1554 {"descending insert, remove middle", []string{"E", "D", "C", "B", "A"}, "C"},
1555 {"ascending insert, remove middle", []string{"A", "B", "C", "D", "E"}, "C"},
1556 {"duplicate insert, remove key", []string{"C", "B", "C", "A", "D"}, "C"},
1557 {"complex case", []string{"H", "B", "A", "C", "E", "D", "F", "G"}, "B"},
1558 }
1559 for _, tt := range tests {
1560 t.Run(tt.name, func(t *testing.T) {
1561 tree := NewBPTreeN(4)
1562 for _, key := range tt.insertKeys {
1563 tree.Set(key, nil)
1564 }
1565 tree.Remove(tt.removeKey)
1566
1567 // Verify sorted order.
1568 var result []string
1569 tree.Iterate("", "", func(key string, value any) bool {
1570 result = append(result, key)
1571 return false
1572 })
1573 for i := 1; i < len(result); i++ {
1574 if result[i] <= result[i-1] {
1575 t.Errorf("Sorted property violated: %s <= %s", result[i], result[i-1])
1576 }
1577 }
1578
1579 // Verify all expected keys present.
1580 for _, key := range tt.insertKeys {
1581 if key == tt.removeKey {
1582 if tree.Has(key) {
1583 // Only check if the key was unique (not duplicated).
1584 // With duplicates, Set overwrites, so there's only one copy.
1585 continue
1586 }
1587 }
1588 }
1589 })
1590 }
1591}
1592
1593//----------------------------------------
1594// Structural invariant verification
1595
1596// verifyInvariants checks all B+ tree structural invariants.
1597func verifyInvariants(t *testing.T, tree *BPTree) {
1598 t.Helper()
1599 if tree.root == nil {
1600 if tree.size != 0 {
1601 t.Errorf("nil root but size=%d", tree.size)
1602 }
1603 return
1604 }
1605
1606 // Check leaf depth uniformity.
1607 depth := leafDepth(tree.root, 0)
1608 if depth == -1 {
1609 t.Error("leaves are at different depths")
1610 }
1611
1612 // Check separator keys, child count bounds, sizes, ref-count.
1613 seen := make(map[node]bool)
1614 verifyNode(t, tree.root, tree.fanout, true, seen)
1615
1616 // Check tree.size matches actual leaf count.
1617 actual := tree.root.nodeSize()
1618 if tree.size != actual {
1619 t.Errorf("tree.size=%d but root.nodeSize()=%d", tree.size, actual)
1620 }
1621}
1622
1623func leafDepth(n node, depth int) int {
1624 if n.isLeaf() {
1625 return depth
1626 }
1627 inner := n.(*innerNode)
1628 d := -1
1629 for _, child := range inner.children {
1630 cd := leafDepth(child, depth+1)
1631 if d == -1 {
1632 d = cd
1633 } else if cd != d {
1634 return -1
1635 }
1636 }
1637 return d
1638}
1639
1640func verifyNode(t *testing.T, n node, fanout int, isRoot bool, seen map[node]bool) {
1641 t.Helper()
1642 if seen[n] {
1643 t.Errorf("node reachable by multiple paths (ref-count >= 2)")
1644 return
1645 }
1646 seen[n] = true
1647
1648 if n.isLeaf() {
1649 leaf := n.(*leafNode)
1650 if len(leaf.keys) == 0 && !isRoot {
1651 t.Errorf("non-root leaf has 0 keys")
1652 }
1653 if len(leaf.keys) > fanout {
1654 t.Errorf("leaf has %d keys, max=%d", len(leaf.keys), fanout)
1655 }
1656 return
1657 }
1658
1659 inner := n.(*innerNode)
1660
1661 // Child count bounds.
1662 minC := fanout / 2
1663 if isRoot {
1664 minC = 2
1665 }
1666 if len(inner.children) < minC && !isRoot {
1667 t.Errorf("inner node has %d children, min=%d", len(inner.children), minC)
1668 }
1669 if len(inner.children) > fanout {
1670 t.Errorf("inner node has %d children, max=%d", len(inner.children), fanout)
1671 }
1672
1673 // keys/children/sizes length consistency.
1674 if len(inner.keys) != len(inner.children)-1 {
1675 t.Errorf("len(keys)=%d but len(children)=%d", len(inner.keys), len(inner.children))
1676 }
1677 if len(inner.sizes) != len(inner.children) {
1678 t.Errorf("len(sizes)=%d but len(children)=%d", len(inner.sizes), len(inner.children))
1679 }
1680
1681 // Separator key correctness: keys[i] == children[i+1].minKey().
1682 for i, k := range inner.keys {
1683 expected := inner.children[i+1].minKey()
1684 if k != expected {
1685 t.Errorf("separator keys[%d]=%q but children[%d].minKey()=%q", i, k, i+1, expected)
1686 }
1687 }
1688
1689 // sizes[i] matches child.
1690 for i, child := range inner.children {
1691 actual := child.nodeSize()
1692 if inner.sizes[i] != actual {
1693 t.Errorf("sizes[%d]=%d but child.nodeSize()=%d", i, inner.sizes[i], actual)
1694 }
1695 verifyNode(t, child, fanout, false, seen)
1696 }
1697}
1698
1699func TestInvariantsAfterEveryOperation(t *testing.T) {
1700 tree := NewBPTreeN(4)
1701 keys := []string{"m", "f", "t", "b", "i", "p", "w", "a", "d", "g", "k", "n", "r", "u", "y"}
1702
1703 for _, k := range keys {
1704 tree.Set(k, k)
1705 verifyInvariants(t, tree)
1706 }
1707 for _, k := range keys {
1708 tree.Remove(k)
1709 verifyInvariants(t, tree)
1710 }
1711}
1712
1713//----------------------------------------
1714// Behavioral parity: GetByIndex == IterateByOffset
1715
1716func TestGetByIndexMatchesIterateByOffset(t *testing.T) {
1717 tree := NewBPTreeN(4)
1718 for _, k := range []string{"h", "d", "l", "b", "f", "j", "n", "a", "c", "e", "g"} {
1719 tree.Set(k, k)
1720 }
1721
1722 for i := 0; i < tree.Size(); i++ {
1723 k1, v1 := tree.GetByIndex(i)
1724 var k2 string
1725 var v2 any
1726 tree.IterateByOffset(i, 1, func(k string, v any) bool {
1727 k2 = k
1728 v2 = v
1729 return true
1730 })
1731 if k1 != k2 || v1 != v2 {
1732 t.Errorf("index %d: GetByIndex=(%q,%v) but IterateByOffset=(%q,%v)", i, k1, v1, k2, v2)
1733 }
1734 }
1735}
1736
1737//----------------------------------------
1738// Stress: oscillating tree size
1739
1740func TestOscillatingSize(t *testing.T) {
1741 tree := NewBPTreeN(4)
1742
1743 // Insert 100.
1744 for i := 0; i < 100; i++ {
1745 tree.Set(intToKey(i), i)
1746 }
1747 verifyInvariants(t, tree)
1748
1749 // Remove 50.
1750 for i := 0; i < 50; i++ {
1751 tree.Remove(intToKey(i))
1752 }
1753 verifyInvariants(t, tree)
1754 if tree.Size() != 50 {
1755 t.Errorf("Expected size 50, got %d", tree.Size())
1756 }
1757
1758 // Insert 50 new.
1759 for i := 100; i < 150; i++ {
1760 tree.Set(intToKey(i), i)
1761 }
1762 verifyInvariants(t, tree)
1763 if tree.Size() != 100 {
1764 t.Errorf("Expected size 100, got %d", tree.Size())
1765 }
1766
1767 // Remove all.
1768 for i := 50; i < 150; i++ {
1769 tree.Remove(intToKey(i))
1770 }
1771 verifyInvariants(t, tree)
1772 if tree.Size() != 0 {
1773 t.Errorf("Expected size 0, got %d", tree.Size())
1774 }
1775
1776 // Insert again from empty.
1777 for i := 0; i < 20; i++ {
1778 tree.Set(intToKey(i), i)
1779 }
1780 verifyInvariants(t, tree)
1781 if tree.Size() != 20 {
1782 t.Errorf("Expected size 20, got %d", tree.Size())
1783 }
1784}
1785
1786//----------------------------------------
1787// All 6 rebalance paths
1788
1789func TestAllRebalancePaths(t *testing.T) {
1790 // We use fanout=4 so min=2 for leaves.
1791 // Each sub-test constructs a specific tree state and triggers one rebalance path.
1792
1793 t.Run("leaf redistribute from left", func(t *testing.T) {
1794 tree := NewBPTreeN(4)
1795 for _, k := range []string{"a", "b", "c", "d", "e"} {
1796 tree.Set(k, k)
1797 }
1798 // After 90/10 split: left=[a,b,c], right=[d,e].
1799 // Remove "d" → right=[e] (1 < min=2). Left has 3 > 2 → redistribute from left.
1800 tree.Remove("d")
1801 verifyInvariants(t, tree)
1802 if !tree.Has("e") {
1803 t.Error("Missing key 'e' after redistribute")
1804 }
1805 })
1806
1807 t.Run("leaf redistribute from right", func(t *testing.T) {
1808 tree := NewBPTreeN(4)
1809 for _, k := range []string{"a", "b", "c", "d", "e", "f", "g"} {
1810 tree.Set(k, k)
1811 }
1812 // Remove from leftmost leaf until it underflows and must redistribute from right.
1813 tree.Remove("a")
1814 tree.Remove("b")
1815 verifyInvariants(t, tree)
1816 })
1817
1818 t.Run("leaf redistribute from right, no stale root separator keys", func(t *testing.T) {
1819 tree := NewBPTreeN(4)
1820 for _, k := range []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n"} {
1821 tree.Set(k, k)
1822 }
1823 tree.Remove("g") // no underflow
1824 tree.Remove("h") // leaf [h,i] underflows and must redistribute from right
1825 verifyInvariants(t, tree)
1826 })
1827
1828 t.Run("leaf redistribute from right, no stale inner node separator keys", func(t *testing.T) {
1829 tree := NewBPTreeN(4)
1830 for _, k := range []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q"} {
1831 tree.Set(k, k)
1832 }
1833 tree.Remove("g") // no underflow
1834 tree.Remove("j") // no underflow
1835 tree.Remove("k") // leaf [k,l] underflows and must redistribute from right
1836 verifyInvariants(t, tree)
1837 })
1838
1839 t.Run("stale separator, middle leaf pos0 redistribute from right", func(t *testing.T) {
1840 // Exercises the core bug: remove pos=0 from a middle leaf (childIdx > 0),
1841 // where left sibling is at minimum (can't redistribute left) and right
1842 // sibling has surplus (redistribute right fires). Without the fix,
1843 // parent.keys[childIdx-1] remains stale.
1844 //
1845 // After inserting a-k with fanout=4, tree is:
1846 // root keys=["d","g","j"]
1847 // children=[["a","b","c"], ["d","e","f"], ["g","h","i"], ["j","k"]]
1848 //
1849 // Remove "a" thins children[0] to ["b","c"] (at minimum).
1850 // Remove "f" thins children[1] to ["d","e"] (at minimum).
1851 // Remove "d" is pos=0 from children[1], causing underflow to ["e"].
1852 // Left sibling ["b","c"] has 2 = minKeys, can't spare.
1853 // Right sibling ["g","h","i"] has 3 > minKeys, redistribute right fires.
1854 // Without fix: keys[0] stays "d" (stale). With fix: updated to "e".
1855 tree := NewBPTreeN(4)
1856 for _, k := range []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k"} {
1857 tree.Set(k, k)
1858 }
1859 tree.Remove("a") // thin left sibling to minimum
1860 tree.Remove("f") // thin target leaf to minimum
1861 tree.Remove("d") // pos=0, underflow, triggers redistribute from right
1862 verifyInvariants(t, tree)
1863 })
1864
1865 t.Run("leaf merge", func(t *testing.T) {
1866 tree := NewBPTreeN(4)
1867 for _, k := range []string{"a", "b", "c", "d", "e"} {
1868 tree.Set(k, k)
1869 }
1870 // Remove enough to make both siblings at minimum, then one more triggers merge.
1871 tree.Remove("a")
1872 tree.Remove("b") // left=[c], right=[d,e]. left underflows. right has 2=min. merge.
1873 verifyInvariants(t, tree)
1874 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
1875 return tr.Iterate("", "", cb)
1876 })
1877 assertSliceEqual(t, got, []string{"c", "d", "e"})
1878 })
1879
1880 t.Run("inner redistribute from left", func(t *testing.T) {
1881 // Build a tree with enough inner nodes, then remove to trigger inner rebalance.
1882 tree := NewBPTreeN(4)
1883 for i := 0; i < 30; i++ {
1884 tree.Set(intToKey(i), i)
1885 }
1886 // Remove from the right side to underflow a right inner node.
1887 for i := 25; i < 30; i++ {
1888 tree.Remove(intToKey(i))
1889 }
1890 verifyInvariants(t, tree)
1891 })
1892
1893 t.Run("inner redistribute from right", func(t *testing.T) {
1894 tree := NewBPTreeN(4)
1895 for i := 0; i < 30; i++ {
1896 tree.Set(intToKey(i), i)
1897 }
1898 // Remove from the left side to underflow a left inner node.
1899 for i := 0; i < 5; i++ {
1900 tree.Remove(intToKey(i))
1901 }
1902 verifyInvariants(t, tree)
1903 })
1904
1905 t.Run("inner merge", func(t *testing.T) {
1906 tree := NewBPTreeN(4)
1907 for i := 0; i < 20; i++ {
1908 tree.Set(intToKey(i), i)
1909 }
1910 // Remove enough to trigger inner merge.
1911 for i := 0; i < 15; i++ {
1912 tree.Remove(intToKey(i))
1913 }
1914 verifyInvariants(t, tree)
1915 if tree.Size() != 5 {
1916 t.Errorf("Expected size 5, got %d", tree.Size())
1917 }
1918 })
1919}
1920
1921//----------------------------------------
1922// Value mutation after Get should not affect tree
1923
1924func TestValueMutationIndependence(t *testing.T) {
1925 tree := NewBPTreeN(4)
1926
1927 // Store a slice value.
1928 orig := []int{1, 2, 3}
1929 tree.Set("k", orig)
1930
1931 // Get the value and mutate it.
1932 v, _ := tree.Get("k")
1933 got := v.([]int)
1934 got[0] = 999
1935
1936 // The tree's stored value should also be affected (since slices are reference types
1937 // and *any holds the same interface). This is the expected Go behavior — not a copy.
1938 v2, _ := tree.Get("k")
1939 got2 := v2.([]int)
1940 if got2[0] != 999 {
1941 t.Errorf("Expected slice mutation to be visible (reference semantics), got %v", got2)
1942 }
1943
1944 // But replacing the value via Set should not affect previous Get results.
1945 tree.Set("k", []int{10, 20, 30})
1946 v3, _ := tree.Get("k")
1947 got3 := v3.([]int)
1948 if got3[0] != 10 {
1949 t.Errorf("Expected new value after Set, got %v", got3)
1950 }
1951 // The old reference should still have 999.
1952 if got[0] != 999 {
1953 t.Errorf("Old reference should still be 999, got %v", got)
1954 }
1955}
1956
1957//----------------------------------------
1958// Comprehensive invariant check across fanouts and sizes
1959
1960func TestInvariantsAcrossFanouts(t *testing.T) {
1961 for _, fanout := range []int{4, 5, 7, 8, 16, 32} {
1962 tree := NewBPTreeN(fanout)
1963 n := 200
1964
1965 // Insert all.
1966 for i := 0; i < n; i++ {
1967 tree.Set(intToKey(i), i)
1968 }
1969 verifyInvariants(t, tree)
1970
1971 // Remove every 3rd.
1972 for i := 0; i < n; i += 3 {
1973 tree.Remove(intToKey(i))
1974 }
1975 verifyInvariants(t, tree)
1976
1977 // Remove remaining.
1978 for i := 0; i < n; i++ {
1979 tree.Remove(intToKey(i))
1980 }
1981 verifyInvariants(t, tree)
1982 if tree.Size() != 0 {
1983 t.Errorf("fanout=%d: expected size 0, got %d", fanout, tree.Size())
1984 }
1985 }
1986}
1987
1988//----------------------------------------
1989// Deep stack unwinding
1990
1991func TestDeepStackUnwinding(t *testing.T) {
1992 // With fanout=4 and 500 keys, the tree is 4-5 levels deep.
1993 // Iterating across subtree boundaries forces advanceLeaf/retreatLeaf
1994 // to pop multiple stack levels.
1995 tree := NewBPTreeN(4)
1996 n := 500
1997 for i := 0; i < n; i++ {
1998 tree.Set(intToKey(i), i)
1999 }
2000
2001 // Full ascending iteration — every leaf boundary is crossed.
2002 count := 0
2003 prev := ""
2004 tree.Iterate("", "", func(k string, v any) bool {
2005 if k <= prev && prev != "" {
2006 t.Errorf("ascending order broken: %q after %q", k, prev)
2007 }
2008 prev = k
2009 count++
2010 return false
2011 })
2012 if count != n {
2013 t.Errorf("ascending: visited %d, want %d", count, n)
2014 }
2015
2016 // Full descending iteration.
2017 count = 0
2018 prev = ""
2019 tree.ReverseIterate("", "", func(k string, v any) bool {
2020 if prev != "" && k >= prev {
2021 t.Errorf("descending order broken: %q after %q", k, prev)
2022 }
2023 prev = k
2024 count++
2025 return false
2026 })
2027 if count != n {
2028 t.Errorf("descending: visited %d, want %d", count, n)
2029 }
2030
2031 // Offset-based iteration crossing deep boundaries.
2032 // Start from the middle, iterate to the end.
2033 count = 0
2034 tree.IterateByOffset(250, 250, func(k string, v any) bool {
2035 count++
2036 return false
2037 })
2038 if count != 250 {
2039 t.Errorf("IterateByOffset(250,250): visited %d, want 250", count)
2040 }
2041
2042 // Reverse offset from middle.
2043 count = 0
2044 tree.ReverseIterateByOffset(250, 250, func(k string, v any) bool {
2045 count++
2046 return false
2047 })
2048 if count != 250 {
2049 t.Errorf("ReverseIterateByOffset(250,250): visited %d, want 250", count)
2050 }
2051
2052 verifyInvariants(t, tree)
2053}
2054
2055//----------------------------------------
2056// Height invariant
2057
2058func treeHeight(n node) int {
2059 if n == nil {
2060 return 0
2061 }
2062 if n.isLeaf() {
2063 return 1
2064 }
2065 return 1 + treeHeight(n.(*innerNode).children[0])
2066}
2067
2068func TestHeightInvariant(t *testing.T) {
2069 // B+ tree with fanout F should have height <= 1 + log_{ceil(F/2)}(n).
2070 for _, fanout := range []int{4, 8, 32} {
2071 tree := NewBPTreeN(fanout)
2072 n := 1000
2073 for i := 0; i < n; i++ {
2074 tree.Set(intToKey(i), i)
2075 }
2076
2077 h := treeHeight(tree.root)
2078 // Compute max height: log base ceil(fanout/2) of n, plus 1 for root.
2079 minFill := fanout / 2
2080 if minFill < 2 {
2081 minFill = 2
2082 }
2083 maxH := 1
2084 capacity := 1
2085 for capacity < n {
2086 capacity *= minFill
2087 maxH++
2088 }
2089
2090 if h > maxH {
2091 t.Errorf("fanout=%d, n=%d: height=%d exceeds max=%d", fanout, n, h, maxH)
2092 }
2093 }
2094}
2095
2096//----------------------------------------
2097// Empty string as separator key
2098
2099func TestEmptyStringSeparator(t *testing.T) {
2100 tree := NewBPTreeN(4)
2101
2102 // Insert "" first, then other keys. With sequential inserts,
2103 // "" will end up in the leftmost leaf and could become a separator.
2104 tree.Set("", "empty")
2105 tree.Set("a", "a")
2106 tree.Set("b", "b")
2107 tree.Set("c", "c")
2108 tree.Set("d", "d") // triggers split; "" should be in left leaf
2109
2110 verifyInvariants(t, tree)
2111
2112 // Verify all keys accessible.
2113 if v, ok := tree.Get(""); !ok || v != "empty" {
2114 t.Errorf("Get('')=(%v,%v), want (empty,true)", v, ok)
2115 }
2116 for _, k := range []string{"a", "b", "c", "d"} {
2117 if !tree.Has(k) {
2118 t.Errorf("missing key %q", k)
2119 }
2120 }
2121
2122 // Iterate should include "".
2123 got := collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
2124 return tr.Iterate("", "", cb)
2125 })
2126 assertSliceEqual(t, got, []string{"", "a", "b", "c", "d"})
2127
2128 // ReverseIterate should include "".
2129 got = collectKeys(tree, func(tr *BPTree, cb IterCbFn) bool {
2130 return tr.ReverseIterate("", "", cb)
2131 })
2132 assertSliceEqual(t, got, []string{"d", "c", "b", "a", ""})
2133
2134 // Remove "" and verify tree is still valid.
2135 v, ok := tree.Remove("")
2136 if !ok || v != "empty" {
2137 t.Errorf("Remove('')=(%v,%v), want (empty,true)", v, ok)
2138 }
2139 verifyInvariants(t, tree)
2140 if tree.Has("") {
2141 t.Error("'' should be gone after remove")
2142 }
2143
2144 // Now insert more keys with "" to force it into a separator position.
2145 // Build a tree where "" is between two inner node children.
2146 tree2 := NewBPTreeN(4)
2147 // Insert keys that will sort before and after "".
2148 // In ASCII, "" < everything. So "" is always the smallest key.
2149 // To make "" a separator, we need it to be the minKey of a right child.
2150 // That happens when the leaf containing "" splits and "" ends up
2151 // as right.keys[0] (the promoted separator).
2152 // With 50/50 split: left gets lower half, right gets upper half.
2153 // Since "" is the smallest, it will always be in the left leaf.
2154 // With 90/10 on append: "" would be in the left leaf too.
2155 // So "" can become a separator only if it's the minKey of a right child
2156 // after a split where "" is in the right half.
2157 // Insert in reverse order so "" ends up in the right half of a split:
2158 tree2.Set("d", "d")
2159 tree2.Set("c", "c")
2160 tree2.Set("b", "b")
2161 tree2.Set("a", "a")
2162 tree2.Set("", "empty") // inserted at position 0 (not append), 50/50 split
2163
2164 verifyInvariants(t, tree2)
2165 got = collectKeys(tree2, func(tr *BPTree, cb IterCbFn) bool {
2166 return tr.Iterate("", "", cb)
2167 })
2168 assertSliceEqual(t, got, []string{"", "a", "b", "c", "d"})
2169}
2170
2171//----------------------------------------
2172// Pointer independence after split
2173
2174func TestPointerIndependenceAfterSplit(t *testing.T) {
2175 tree := NewBPTreeN(4)
2176
2177 // Insert 5 keys to trigger a split.
2178 tree.Set("a", "val_a")
2179 tree.Set("b", "val_b")
2180 tree.Set("c", "val_c")
2181 tree.Set("d", "val_d")
2182 tree.Set("e", "val_e") // triggers split
2183
2184 // Get values from both halves of the split.
2185 vLeft, _ := tree.Get("a")
2186 vRight, _ := tree.Get("d")
2187
2188 if vLeft != "val_a" {
2189 t.Errorf("left value: got %v, want val_a", vLeft)
2190 }
2191 if vRight != "val_d" {
2192 t.Errorf("right value: got %v, want val_d", vRight)
2193 }
2194
2195 // Update a value in the left half — should not affect right half.
2196 tree.Set("a", "new_a")
2197 vLeft2, _ := tree.Get("a")
2198 vRight2, _ := tree.Get("d")
2199 if vLeft2 != "new_a" {
2200 t.Errorf("updated left: got %v, want new_a", vLeft2)
2201 }
2202 if vRight2 != "val_d" {
2203 t.Errorf("right should be unchanged: got %v, want val_d", vRight2)
2204 }
2205
2206 // Update a value in the right half — should not affect left half.
2207 tree.Set("d", "new_d")
2208 vLeft3, _ := tree.Get("a")
2209 vRight3, _ := tree.Get("d")
2210 if vLeft3 != "new_a" {
2211 t.Errorf("left should be unchanged: got %v, want new_a", vLeft3)
2212 }
2213 if vRight3 != "new_d" {
2214 t.Errorf("updated right: got %v, want new_d", vRight3)
2215 }
2216
2217 // Verify that the *any pointers in the two leaves are different objects.
2218 // Access internals to check.
2219 inner := tree.root.(*innerNode)
2220 leftLeaf := inner.children[0].(*leafNode)
2221 rightLeaf := inner.children[1].(*leafNode)
2222
2223 // Each value pointer should be unique.
2224 seen := make(map[*any]bool)
2225 for _, vp := range leftLeaf.values {
2226 if seen[vp] {
2227 t.Error("duplicate *any pointer in left leaf")
2228 }
2229 seen[vp] = true
2230 }
2231 for _, vp := range rightLeaf.values {
2232 if seen[vp] {
2233 t.Error("*any pointer shared between left and right leaves after split")
2234 }
2235 seen[vp] = true
2236 }
2237}
2238
2239//----------------------------------------
2240// Helpers
2241
2242func slicesEqual(a, b []string) bool {
2243 if len(a) != len(b) {
2244 return false
2245 }
2246 for i := range a {
2247 if a[i] != b[i] {
2248 return false
2249 }
2250 }
2251 return true
2252}
2253
2254func intToKey(i int) string {
2255 // Zero-padded 4-digit string for correct lexicographic ordering.
2256 s := "0000"
2257 n := i
2258 b := []byte(s)
2259 for j := 3; j >= 0; j-- {
2260 b[j] = byte('0' + n%10)
2261 n /= 10
2262 }
2263 return string(b)
2264}
2265
2266func collectKeys(tree *BPTree, fn func(*BPTree, IterCbFn) bool) []string {
2267 var keys []string
2268 fn(tree, func(k string, v any) bool {
2269 keys = append(keys, k)
2270 return false
2271 })
2272 return keys
2273}
2274
2275func assertSliceEqual(t *testing.T, got, want []string) {
2276 t.Helper()
2277 if len(got) != len(want) {
2278 t.Errorf("got %v, want %v", got, want)
2279 return
2280 }
2281 for i := range got {
2282 if got[i] != want[i] {
2283 t.Errorf("got %v, want %v", got, want)
2284 return
2285 }
2286 }
2287}
2288
2289func assertPanics(t *testing.T, name string, fn func()) {
2290 t.Helper()
2291 defer func() {
2292 if r := recover(); r == nil {
2293 t.Errorf("%s: expected panic, got none", name)
2294 }
2295 }()
2296 fn()
2297}
2298
2299//----------------------------------------
2300// Stress tests
2301
2302// TestAVLCrossValidation runs identical random operations on both avl.Tree
2303// and BPTree and compares every return value.
2304func TestAVLCrossValidation(t *testing.T) {
2305 rng := rand.New(rand.NewPCG(12345, 0))
2306 at := avl.NewTree()
2307 bt := NewBPTree32()
2308
2309 const nOps = 5000
2310 const keyRange = 200
2311
2312 for i := 0; i < nOps; i++ {
2313 key := intToKey(rng.IntN(keyRange))
2314 op := rng.IntN(3)
2315 switch op {
2316 case 0: // Set
2317 aUpd := at.Set(key, i)
2318 bUpd := bt.Set(key, i)
2319 if aUpd != bUpd {
2320 t.Fatalf("op %d: Set(%q) updated avl=%v bpt=%v", i, key, aUpd, bUpd)
2321 }
2322 case 1: // Remove
2323 aVal, aOk := at.Remove(key)
2324 bVal, bOk := bt.Remove(key)
2325 if aOk != bOk {
2326 t.Fatalf("op %d: Remove(%q) avl=%v bpt=%v", i, key, aOk, bOk)
2327 }
2328 if aOk && aVal != bVal {
2329 t.Fatalf("op %d: Remove(%q) value avl=%v bpt=%v", i, key, aVal, bVal)
2330 }
2331 case 2: // Get
2332 aVal, aOk := at.Get(key)
2333 bVal, bOk := bt.Get(key)
2334 if aOk != bOk {
2335 t.Fatalf("op %d: Get(%q) avl=%v bpt=%v", i, key, aOk, bOk)
2336 }
2337 if aOk && aVal != bVal {
2338 t.Fatalf("op %d: Get(%q) value avl=%v bpt=%v", i, key, aVal, bVal)
2339 }
2340 }
2341 if at.Size() != bt.Size() {
2342 t.Fatalf("op %d: size avl=%d bpt=%d", i, at.Size(), bt.Size())
2343 }
2344 }
2345
2346 // Compare full iteration.
2347 var aKeys, bKeys []string
2348 at.Iterate("", "", func(k string, v any) bool { aKeys = append(aKeys, k); return false })
2349 bt.Iterate("", "", func(k string, v any) bool { bKeys = append(bKeys, k); return false })
2350 assertSliceEqual(t, bKeys, aKeys)
2351}
2352
2353// TestExhaustiveRemovalPermutations inserts N keys then tries all N!
2354// permutations of removal order, verifying invariants after each remove.
2355func TestExhaustiveRemovalPermutations(t *testing.T) {
2356 keys := []string{"a", "b", "c", "d", "e", "f", "g", "h"}
2357 n := len(keys)
2358
2359 perm := make([]int, n)
2360 for i := range perm {
2361 perm[i] = i
2362 }
2363
2364 count := 0
2365 permute(perm, 0, func(order []int) {
2366 tree := NewBPTreeN(4)
2367 for _, k := range keys {
2368 tree.Set(k, k)
2369 }
2370 for _, idx := range order {
2371 tree.Remove(keys[idx])
2372 verifyInvariants(t, tree)
2373 }
2374 if tree.Size() != 0 {
2375 t.Fatalf("perm %d: tree not empty after removing all keys", count)
2376 }
2377 count++
2378 })
2379}
2380
2381// permute generates all permutations of arr[start:] and calls fn for each.
2382func permute(arr []int, start int, fn func([]int)) {
2383 if start == len(arr) {
2384 fn(arr)
2385 return
2386 }
2387 for i := start; i < len(arr); i++ {
2388 arr[start], arr[i] = arr[i], arr[start]
2389 permute(arr, start+1, fn)
2390 arr[start], arr[i] = arr[i], arr[start]
2391 }
2392}
2393
2394// TestMultiFanoutStress runs the same operation sequence across different
2395// fanouts and verifies all produce identical results.
2396func TestMultiFanoutStress(t *testing.T) {
2397 fanouts := []int{4, 5, 6, 7, 8, 16, 32}
2398 const nOps = 2000
2399 const keyRange = 100
2400
2401 // Record expected results from the first fanout.
2402 type result struct {
2403 setUpdated bool
2404 getVal any
2405 getOk bool
2406 rmVal any
2407 rmOk bool
2408 }
2409
2410 rng0 := rand.New(rand.NewPCG(99999, 0))
2411 type op struct {
2412 kind int // 0=set, 1=remove, 2=get
2413 key string
2414 val int
2415 }
2416 ops := make([]op, nOps)
2417 for i := range ops {
2418 ops[i] = op{
2419 kind: rng0.IntN(3),
2420 key: intToKey(rng0.IntN(keyRange)),
2421 val: i,
2422 }
2423 }
2424
2425 // Run on each fanout and collect final keys.
2426 var referenceKeys []string
2427 for fi, fanout := range fanouts {
2428 tree := NewBPTreeN(fanout)
2429 for _, o := range ops {
2430 switch o.kind {
2431 case 0:
2432 tree.Set(o.key, o.val)
2433 case 1:
2434 tree.Remove(o.key)
2435 case 2:
2436 tree.Get(o.key)
2437 }
2438 }
2439 verifyInvariants(t, tree)
2440
2441 var keys []string
2442 tree.Iterate("", "", func(k string, v any) bool {
2443 keys = append(keys, k)
2444 return false
2445 })
2446
2447 if fi == 0 {
2448 referenceKeys = keys
2449 } else {
2450 assertSliceEqual(t, keys, referenceKeys)
2451 }
2452 }
2453}
2454
2455// TestSequentialInsertReverseRemove inserts keys 0..N-1 sequentially
2456// (triggering 90/10 splits) then removes them in reverse order
2457// (triggering cascading merges from the right).
2458func TestSequentialInsertReverseRemove(t *testing.T) {
2459 for _, fanout := range []int{4, 6, 8, 32} {
2460 tree := NewBPTreeN(fanout)
2461 n := 500
2462 for i := 0; i < n; i++ {
2463 tree.Set(intToKey(i), i)
2464 }
2465 verifyInvariants(t, tree)
2466 if tree.Size() != n {
2467 t.Errorf("fanout=%d: expected size %d, got %d", fanout, n, tree.Size())
2468 }
2469
2470 for i := n - 1; i >= 0; i-- {
2471 val, ok := tree.Remove(intToKey(i))
2472 if !ok {
2473 t.Fatalf("fanout=%d: Remove(%s) returned false", fanout, intToKey(i))
2474 }
2475 if val != i {
2476 t.Fatalf("fanout=%d: Remove(%s) value=%v want %d", fanout, intToKey(i), val, i)
2477 }
2478 verifyInvariants(t, tree)
2479 }
2480 if tree.Size() != 0 {
2481 t.Errorf("fanout=%d: expected empty tree, got size %d", fanout, tree.Size())
2482 }
2483 }
2484}
2485
2486// TestRandomOpsWithPeriodicVerification does 10K random Set/Remove calls,
2487// verifying invariants and sorted iteration every 100 ops.
2488func TestRandomOpsWithPeriodicVerification(t *testing.T) {
2489 rng := rand.New(rand.NewPCG(54321, 0))
2490 tree := NewBPTreeN(4)
2491
2492 const nOps = 10000
2493 const keyRange = 300
2494 const checkEvery = 100
2495
2496 // Track expected keys in a sorted slice for comparison.
2497 present := make(map[string]bool)
2498
2499 for i := 0; i < nOps; i++ {
2500 key := intToKey(rng.IntN(keyRange))
2501 if rng.IntN(3) == 0 { // ~33% removes
2502 _, ok := tree.Remove(key)
2503 if ok {
2504 delete(present, key)
2505 }
2506 } else { // ~67% sets
2507 tree.Set(key, i)
2508 present[key] = true
2509 }
2510
2511 if (i+1)%checkEvery == 0 {
2512 verifyInvariants(t, tree)
2513
2514 // Check size.
2515 if tree.Size() != len(present) {
2516 t.Fatalf("op %d: size mismatch tree=%d map=%d", i, tree.Size(), len(present))
2517 }
2518
2519 // Check iteration matches sorted keys.
2520 var expected []string
2521 for k := range present {
2522 expected = append(expected, k)
2523 }
2524 sort.Strings(expected)
2525
2526 var got []string
2527 tree.Iterate("", "", func(k string, v any) bool {
2528 got = append(got, k)
2529 return false
2530 })
2531 assertSliceEqual(t, got, expected)
2532 }
2533 }
2534}
2535
2536// TestGetByIndexIterateByOffsetConsistency verifies that GetByIndex(i)
2537// matches IterateByOffset(i, 1) for every valid index.
2538func TestGetByIndexIterateByOffsetConsistency(t *testing.T) {
2539 rng := rand.New(rand.NewPCG(77777, 0))
2540 tree := NewBPTreeN(4)
2541
2542 // Build a tree with random insertions and removals.
2543 const nOps = 1000
2544 const keyRange = 200
2545 for i := 0; i < nOps; i++ {
2546 key := intToKey(rng.IntN(keyRange))
2547 if rng.IntN(4) == 0 {
2548 tree.Remove(key)
2549 } else {
2550 tree.Set(key, i)
2551 }
2552 }
2553
2554 n := tree.Size()
2555 for i := 0; i < n; i++ {
2556 gKey, gVal := tree.GetByIndex(i)
2557
2558 var iKey string
2559 var iVal any
2560 tree.IterateByOffset(i, 1, func(k string, v any) bool {
2561 iKey = k
2562 iVal = v
2563 return true
2564 })
2565
2566 if gKey != iKey {
2567 t.Fatalf("index %d: GetByIndex key=%q IterateByOffset key=%q", i, gKey, iKey)
2568 }
2569 if gVal != iVal {
2570 t.Fatalf("index %d: GetByIndex val=%v IterateByOffset val=%v", i, gVal, iVal)
2571 }
2572 }
2573
2574 // Also check ReverseIterateByOffset consistency.
2575 for i := 0; i < n; i++ {
2576 gKey, gVal := tree.GetByIndex(n - 1 - i)
2577
2578 var rKey string
2579 var rVal any
2580 tree.ReverseIterateByOffset(i, 1, func(k string, v any) bool {
2581 rKey = k
2582 rVal = v
2583 return true
2584 })
2585
2586 if gKey != rKey {
2587 t.Fatalf("rev index %d: GetByIndex key=%q ReverseIterateByOffset key=%q", i, gKey, rKey)
2588 }
2589 if gVal != rVal {
2590 t.Fatalf("rev index %d: GetByIndex val=%v ReverseIterateByOffset val=%v", i, gVal, rVal)
2591 }
2592 }
2593}