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