| 79 | } |
| 80 | |
| 81 | func TestBTreeRandom(t *testing.T) { |
| 82 | maxKeysCases := []int{4, 16} |
| 83 | sizes := []int{100, 0xBA5, 0xF00} |
| 84 | for _, maxKeys := range maxKeysCases { |
| 85 | for _, size := range sizes { |
| 86 | rnd := rand.New(rand.NewSource(0)) |
| 87 | tree := bt.NewBTree[int](maxKeys) |
| 88 | nums := rnd.Perm(size) |
| 89 | if tree.Search(0) { |
| 90 | t.Errorf("Tree expected to contain 0") |
| 91 | } |
| 92 | for i := 0; i < size; i++ { |
| 93 | tree.Insert(nums[i]) |
| 94 | } |
| 95 | for i := 0; i < size; i++ { |
| 96 | if !tree.Search(nums[i]) { |
| 97 | t.Errorf("Tree expected to contain %d", nums[i]) |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | for i := 0; i < size; i += 5 { |
| 102 | tree.Delete(nums[i]) |
| 103 | } |
| 104 | for i := 0; i < size; i++ { |
| 105 | hasKey := tree.Search(nums[i]) |
| 106 | if i%5 == 0 && hasKey { |
| 107 | t.Errorf("Tree not expected to contain %d", i) |
| 108 | } else if i%5 != 0 && !hasKey { |
| 109 | t.Errorf("Tree expected to contain %d", i) |
| 110 | } |
| 111 | } |
| 112 | } |
| 113 | } |
| 114 | } |
| 115 | |
| 116 | func TestBTreeDeleteEverything(t *testing.T) { |
| 117 | tree := bt.NewBTree[int](4) |