btree_test.gno
18.93 Kb ยท 680 lines
1package btree
2
3import (
4 "fmt"
5 "sort"
6 "testing"
7)
8
9// Content represents a key-value pair where the Key can be either an int or string
10// and the Value can be any type.
11type Content struct {
12 Key any
13 Value any
14}
15
16// Less compares two Content records by their Keys.
17// The Key must be either an int or a string.
18func (c Content) Less(than Record) bool {
19 other, ok := than.(Content)
20 if !ok {
21 panic("cannot compare: incompatible types")
22 }
23
24 switch key := c.Key.(type) {
25 case int:
26 switch otherKey := other.Key.(type) {
27 case int:
28 return key < otherKey
29 case string:
30 return true // ints are always less than strings
31 default:
32 panic("unsupported key type: must be int or string")
33 }
34 case string:
35 switch otherKey := other.Key.(type) {
36 case int:
37 return false // strings are always greater than ints
38 case string:
39 return key < otherKey
40 default:
41 panic("unsupported key type: must be int or string")
42 }
43 default:
44 panic("unsupported key type: must be int or string")
45 }
46}
47
48type ContentSlice []Content
49
50func (s ContentSlice) Len() int {
51 return len(s)
52}
53
54func (s ContentSlice) Less(i, j int) bool {
55 return s[i].Less(s[j])
56}
57
58func (s ContentSlice) Swap(i, j int) {
59 s[i], s[j] = s[j], s[i]
60}
61
62func (s ContentSlice) Copy() ContentSlice {
63 newSlice := make(ContentSlice, len(s))
64 copy(newSlice, s)
65 return newSlice
66}
67
68// Ensure Content implements the Record interface.
69var _ Record = Content{}
70
71// ****************************************************************************
72// Test helpers
73// ****************************************************************************
74
75func genericSeeding(tree *BTree, size int) *BTree {
76 for i := 0; i < size; i++ {
77 tree.Insert(Content{Key: i, Value: fmt.Sprintf("Value_%d", i)})
78 }
79 return tree
80}
81
82func intSlicesCompare(left, right []int) int {
83 if len(left) != len(right) {
84 if len(left) > len(right) {
85 return 1
86 } else {
87 return -1
88 }
89 }
90
91 for position, leftInt := range left {
92 if leftInt != right[position] {
93 if leftInt > right[position] {
94 return 1
95 } else {
96 return -1
97 }
98 }
99 }
100
101 return 0
102}
103
104// ****************************************************************************
105// Tests
106// ****************************************************************************
107
108func TestLen(t *testing.T) {
109 length := genericSeeding(New(WithDegree(10)), 7).Len()
110 if length != 7 {
111 t.Errorf("Length is incorrect. Expected 7, but got %d.", length)
112 }
113
114 length = genericSeeding(New(WithDegree(5)), 111).Len()
115 if length != 111 {
116 t.Errorf("Length is incorrect. Expected 111, but got %d.", length)
117 }
118
119 length = genericSeeding(New(WithDegree(30)), 123).Len()
120 if length != 123 {
121 t.Errorf("Length is incorrect. Expected 123, but got %d.", length)
122 }
123}
124
125func TestHas(t *testing.T) {
126 tree := genericSeeding(New(WithDegree(10)), 40)
127
128 if tree.Has(Content{Key: 7}) != true {
129 t.Errorf("Has(7) reported false, but it should be true.")
130 }
131 if tree.Has(Content{Key: 39}) != true {
132 t.Errorf("Has(40) reported false, but it should be true.")
133 }
134 if tree.Has(Content{Key: 1111}) == true {
135 t.Errorf("Has(1111) reported true, but it should be false.")
136 }
137}
138
139func TestMin(t *testing.T) {
140 min := genericSeeding(New(WithDegree(10)), 53).Min().(Content)
141
142 if min.Key != 0 {
143 t.Errorf("Minimum should have been 0, but it was reported as %d.", min)
144 }
145}
146
147func TestMax(t *testing.T) {
148 max := genericSeeding(New(WithDegree(10)), 53).Max().(Content)
149
150 if max.Key != 52 {
151 t.Errorf("Maximum should have been 52, but it was reported as %d.", max)
152 }
153}
154
155func TestGet(t *testing.T) {
156 tree := genericSeeding(New(WithDegree(10)), 40)
157
158 if val := tree.Get(Content{Key: 7}); val != nil && val.(Content).Value != "Value_7" {
159 t.Errorf("Get(7) should have returned 'Value_7', but it returned %v.", val)
160 }
161 if val := tree.Get(Content{Key: 39}); val != nil && val.(Content).Value != "Value_39" {
162 t.Errorf("Get(39) should have returned 'Value_39', but it returned %v.", val)
163 }
164 if val := tree.Get(Content{Key: 1111}); val != nil {
165 t.Errorf("Get(1111) returned %v, but it should be nil.", val)
166 }
167}
168
169func TestDescend(t *testing.T) {
170 tree := genericSeeding(New(WithDegree(10)), 5)
171
172 expected := []int{4, 3, 2, 1, 0}
173 found := []int{}
174
175 tree.Descend(func(_record Record) bool {
176 record := _record.(Content)
177 found = append(found, record.Key.(int))
178 return true
179 })
180
181 if intSlicesCompare(expected, found) != 0 {
182 t.Errorf("Descend returned the wrong sequence. Expected %v, but got %v.", expected, found)
183 }
184}
185
186func TestDescendGreaterThan(t *testing.T) {
187 tree := genericSeeding(New(WithDegree(10)), 10)
188
189 expected := []int{9, 8, 7, 6, 5}
190 found := []int{}
191
192 tree.DescendGreaterThan(Content{Key: 4}, func(_record Record) bool {
193 record := _record.(Content)
194 found = append(found, record.Key.(int))
195 return true
196 })
197
198 if intSlicesCompare(expected, found) != 0 {
199 t.Errorf("DescendGreaterThan returned the wrong sequence. Expected %v, but got %v.", expected, found)
200 }
201}
202
203func TestDescendLessOrEqual(t *testing.T) {
204 tree := genericSeeding(New(WithDegree(10)), 10)
205
206 expected := []int{4, 3, 2, 1, 0}
207 found := []int{}
208
209 tree.DescendLessOrEqual(Content{Key: 4}, func(_record Record) bool {
210 record := _record.(Content)
211 found = append(found, record.Key.(int))
212 return true
213 })
214
215 if intSlicesCompare(expected, found) != 0 {
216 t.Errorf("DescendLessOrEqual returned the wrong sequence. Expected %v, but got %v.", expected, found)
217 }
218}
219
220func TestDescendRange(t *testing.T) {
221 tree := genericSeeding(New(WithDegree(10)), 10)
222
223 expected := []int{6, 5, 4, 3, 2}
224 found := []int{}
225
226 tree.DescendRange(Content{Key: 6}, Content{Key: 1}, func(_record Record) bool {
227 record := _record.(Content)
228 found = append(found, record.Key.(int))
229 return true
230 })
231
232 if intSlicesCompare(expected, found) != 0 {
233 t.Errorf("DescendRange returned the wrong sequence. Expected %v, but got %v.", expected, found)
234 }
235}
236
237func TestAscend(t *testing.T) {
238 tree := genericSeeding(New(WithDegree(10)), 5)
239
240 expected := []int{0, 1, 2, 3, 4}
241 found := []int{}
242
243 tree.Ascend(func(_record Record) bool {
244 record := _record.(Content)
245 found = append(found, record.Key.(int))
246 return true
247 })
248
249 if intSlicesCompare(expected, found) != 0 {
250 t.Errorf("Ascend returned the wrong sequence. Expected %v, but got %v.", expected, found)
251 }
252}
253
254func TestAscendGreaterOrEqual(t *testing.T) {
255 tree := genericSeeding(New(WithDegree(10)), 10)
256
257 expected := []int{5, 6, 7, 8, 9}
258 found := []int{}
259
260 tree.AscendGreaterOrEqual(Content{Key: 5}, func(_record Record) bool {
261 record := _record.(Content)
262 found = append(found, record.Key.(int))
263 return true
264 })
265
266 if intSlicesCompare(expected, found) != 0 {
267 t.Errorf("AscendGreaterOrEqual returned the wrong sequence. Expected %v, but got %v.", expected, found)
268 }
269}
270
271func TestAscendLessThan(t *testing.T) {
272 tree := genericSeeding(New(WithDegree(10)), 10)
273
274 expected := []int{0, 1, 2, 3, 4}
275 found := []int{}
276
277 tree.AscendLessThan(Content{Key: 5}, func(_record Record) bool {
278 record := _record.(Content)
279 found = append(found, record.Key.(int))
280 return true
281 })
282
283 if intSlicesCompare(expected, found) != 0 {
284 t.Errorf("AscendLessThan returned the wrong sequence. Expected %v, but got %v.", expected, found)
285 }
286}
287
288func TestAscendRange(t *testing.T) {
289 tree := genericSeeding(New(WithDegree(10)), 10)
290
291 expected := []int{2, 3, 4, 5, 6}
292 found := []int{}
293
294 tree.AscendRange(Content{Key: 2}, Content{Key: 7}, func(_record Record) bool {
295 record := _record.(Content)
296 found = append(found, record.Key.(int))
297 return true
298 })
299
300 if intSlicesCompare(expected, found) != 0 {
301 t.Errorf("AscendRange returned the wrong sequence. Expected %v, but got %v.", expected, found)
302 }
303}
304
305func TestDeleteMin(t *testing.T) {
306 tree := genericSeeding(New(WithDegree(3)), 100)
307
308 expected := []int{0, 1, 2, 3, 4}
309 found := []int{}
310
311 found = append(found, tree.DeleteMin().(Content).Key.(int))
312 found = append(found, tree.DeleteMin().(Content).Key.(int))
313 found = append(found, tree.DeleteMin().(Content).Key.(int))
314 found = append(found, tree.DeleteMin().(Content).Key.(int))
315 found = append(found, tree.DeleteMin().(Content).Key.(int))
316
317 if intSlicesCompare(expected, found) != 0 {
318 t.Errorf("5 rounds of DeleteMin returned the wrong elements. Expected %v, but got %v.", expected, found)
319 }
320}
321
322func TestShift(t *testing.T) {
323 tree := genericSeeding(New(WithDegree(3)), 100)
324
325 expected := []int{0, 1, 2, 3, 4}
326 found := []int{}
327
328 found = append(found, tree.Shift().(Content).Key.(int))
329 found = append(found, tree.Shift().(Content).Key.(int))
330 found = append(found, tree.Shift().(Content).Key.(int))
331 found = append(found, tree.Shift().(Content).Key.(int))
332 found = append(found, tree.Shift().(Content).Key.(int))
333
334 if intSlicesCompare(expected, found) != 0 {
335 t.Errorf("5 rounds of Shift returned the wrong elements. Expected %v, but got %v.", expected, found)
336 }
337}
338
339func TestDeleteMax(t *testing.T) {
340 tree := genericSeeding(New(WithDegree(3)), 100)
341
342 expected := []int{99, 98, 97, 96, 95}
343 found := []int{}
344
345 found = append(found, tree.DeleteMax().(Content).Key.(int))
346 found = append(found, tree.DeleteMax().(Content).Key.(int))
347 found = append(found, tree.DeleteMax().(Content).Key.(int))
348 found = append(found, tree.DeleteMax().(Content).Key.(int))
349 found = append(found, tree.DeleteMax().(Content).Key.(int))
350
351 if intSlicesCompare(expected, found) != 0 {
352 t.Errorf("5 rounds of DeleteMax returned the wrong elements. Expected %v, but got %v.", expected, found)
353 }
354}
355
356func TestPop(t *testing.T) {
357 tree := genericSeeding(New(WithDegree(3)), 100)
358
359 expected := []int{99, 98, 97, 96, 95}
360 found := []int{}
361
362 found = append(found, tree.Pop().(Content).Key.(int))
363 found = append(found, tree.Pop().(Content).Key.(int))
364 found = append(found, tree.Pop().(Content).Key.(int))
365 found = append(found, tree.Pop().(Content).Key.(int))
366 found = append(found, tree.Pop().(Content).Key.(int))
367
368 if intSlicesCompare(expected, found) != 0 {
369 t.Errorf("5 rounds of Pop returned the wrong elements. Expected %v, but got %v.", expected, found)
370 }
371}
372
373func TestInsertGet(t *testing.T) {
374 tree := New(WithDegree(4))
375
376 expected := []Content{}
377
378 for count := 0; count < 20; count++ {
379 value := fmt.Sprintf("Value_%d", count)
380 tree.Insert(Content{Key: count, Value: value})
381 expected = append(expected, Content{Key: count, Value: value})
382 }
383
384 for count := 0; count < 20; count++ {
385 val := tree.Get(Content{Key: count})
386 if val == nil || val.(Content) != expected[count] {
387 t.Errorf("Insert/Get doesn't appear to be working. Expected to retrieve %v with key %d, but got %v.", expected[count], count, val)
388 }
389 }
390}
391
392func TestClone(t *testing.T) {
393 // Implement the clone test
394}
395
396// ***** The following tests are functional or stress testing type tests.
397
398func TestBTree(t *testing.T) {
399 // Create a B-Tree of degree 3
400 tree := New(WithDegree(3))
401
402 // insertData := []Content{}
403 var insertData ContentSlice
404
405 // Insert integer keys
406 intKeys := []int{10, 20, 5, 6, 12, 30, 7, 17}
407 for _, key := range intKeys {
408 content := Content{Key: key, Value: fmt.Sprintf("Value_%d", key)}
409 insertData = append(insertData, content)
410 result := tree.Insert(content)
411 if result != nil {
412 t.Errorf("**** Already in the tree? %v", result)
413 }
414 }
415
416 // Insert string keys
417 stringKeys := []string{"apple", "banana", "cherry", "date", "fig", "grape"}
418 for _, key := range stringKeys {
419 content := Content{Key: key, Value: fmt.Sprintf("Fruit_%s", key)}
420 insertData = append(insertData, content)
421 tree.Insert(content)
422 }
423
424 if tree.Len() != 14 {
425 t.Errorf("Tree length wrong. Expected 14 but got %d", tree.Len())
426 }
427
428 // Search for existing and non-existing keys
429 searchTests := []struct {
430 test Content
431 expected bool
432 }{
433 {Content{Key: 10, Value: "Value_10"}, true},
434 {Content{Key: 15, Value: ""}, false},
435 {Content{Key: "banana", Value: "Fruit_banana"}, true},
436 {Content{Key: "kiwi", Value: ""}, false},
437 }
438
439 t.Logf("Search Tests:\n")
440 for _, test := range searchTests {
441 val := tree.Get(test.test)
442
443 if test.expected {
444 if val != nil && val.(Content).Value == test.test.Value {
445 t.Logf("Found expected key:value %v:%v", test.test.Key, test.test.Value)
446 } else {
447 if val == nil {
448 t.Logf("Didn't find %v, but expected", test.test.Key)
449 } else {
450 t.Errorf("Expected key %v:%v, but found %v:%v.", test.test.Key, test.test.Value, val.(Content).Key, val.(Content).Value)
451 }
452 }
453 } else {
454 if val != nil {
455 t.Errorf("Did not expect key %v, but found key:value %v:%v", test.test.Key, val.(Content).Key, val.(Content).Value)
456 } else {
457 t.Logf("Didn't find %v, but wasn't expected", test.test.Key)
458 }
459 }
460 }
461
462 // Iterate in order
463 t.Logf("\nIn-order Iteration:\n")
464 pos := 0
465
466 if tree.Len() != 14 {
467 t.Errorf("Tree length wrong. Expected 14 but got %d", tree.Len())
468 }
469
470 sortedInsertData := insertData.Copy()
471 sort.Sort(sortedInsertData)
472
473 t.Logf("Insert Data Length: %d", len(insertData))
474 t.Logf("Sorted Data Length: %d", len(sortedInsertData))
475 t.Logf("Tree Length: %d", tree.Len())
476
477 tree.Ascend(func(_record Record) bool {
478 record := _record.(Content)
479 t.Logf("Key:Value == %v:%v", record.Key, record.Value)
480 if record.Key != sortedInsertData[pos].Key {
481 t.Errorf("Out of order! Expected %v, but got %v", sortedInsertData[pos].Key, record.Key)
482 }
483 pos++
484 return true
485 })
486 // // Reverse Iterate
487 t.Logf("\nReverse-order Iteration:\n")
488 pos = len(sortedInsertData) - 1
489
490 tree.Descend(func(_record Record) bool {
491 record := _record.(Content)
492 t.Logf("Key:Value == %v:%v", record.Key, record.Value)
493 if record.Key != sortedInsertData[pos].Key {
494 t.Errorf("Out of order! Expected %v, but got %v", sortedInsertData[pos].Key, record.Key)
495 }
496 pos--
497 return true
498 })
499
500 deleteTests := []Content{
501 {Key: 10, Value: "Value_10"},
502 {Key: 15, Value: ""},
503 {Key: "banana", Value: "Fruit_banana"},
504 {Key: "kiwi", Value: ""},
505 }
506 for _, test := range deleteTests {
507 fmt.Printf("\nDeleting %+v\n", test)
508 tree.Delete(test)
509 }
510
511 if tree.Len() != 12 {
512 t.Errorf("Tree length wrong. Expected 12 but got %d", tree.Len())
513 }
514
515 for _, test := range deleteTests {
516 val := tree.Get(test)
517 if val != nil {
518 t.Errorf("Did not expect key %v, but found key:value %v:%v", test.Key, val.(Content).Key, val.(Content).Value)
519 } else {
520 t.Logf("Didn't find %v, but wasn't expected", test.Key)
521 }
522 }
523}
524
525// Write a test that populates a large B-Tree with 1000 records.
526// It should then `Clone` the tree, make some changes to both the original and the clone,
527// And then clone the clone, and make some changes to all three trees, and then check that the changes are isolated
528// to the tree they were made in.
529func TestBTreeCloneIsolation(t *testing.T) {
530 t.Logf("Creating B-Tree of degree 10 with 1000 records\n")
531 size := 1000
532 tree := genericSeeding(New(WithDegree(10)), size)
533
534 // Clone the tree
535 t.Logf("Cloning the tree\n")
536 clone := tree.Clone()
537
538 // Make some changes to the original and the clone
539 t.Logf("Making changes to the original and the clone\n")
540 for i := 0; i < size; i += 2 {
541 content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
542 tree.Delete(content)
543 content = Content{Key: i + 1, Value: fmt.Sprintf("Value_%d", i+1)}
544 clone.Delete(content)
545 }
546
547 // Clone the clone
548 t.Logf("Cloning the clone\n")
549 clone2 := clone.Clone()
550
551 // Make some changes to all three trees
552 t.Logf("Making changes to all three trees\n")
553 for i := 0; i < size; i += 3 {
554 content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
555 tree.Delete(content)
556 content = Content{Key: i, Value: fmt.Sprintf("Value_%d", i+1)}
557 clone.Delete(content)
558 content = Content{Key: i + 2, Value: fmt.Sprintf("Value_%d", i+2)}
559 clone2.Delete(content)
560 }
561
562 // Check that the changes are isolated to the tree they were made in
563 t.Logf("Checking that the changes are isolated to the tree they were made in\n")
564 for i := 0; i < size; i++ {
565 content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
566 val := tree.Get(content)
567
568 if i%3 == 0 || i%2 == 0 {
569 if val != nil {
570 t.Errorf("Didn't expect key %v, but found key:value %v:%v", content.Key, val.(Content).Key, val.(Content).Value)
571 }
572 } else {
573 if val == nil {
574 t.Errorf("Expected key %v, but didn't find it", content.Key)
575 }
576 }
577
578 val = clone.Get(content)
579 if i%2 != 0 || i%3 == 0 {
580 if val != nil {
581 t.Errorf("Didn't expect key %v, but found key:value %v:%v", content.Key, val.(Content).Key, val.(Content).Value)
582 }
583 } else {
584 if val == nil {
585 t.Errorf("Expected key %v, but didn't find it", content.Key)
586 }
587 }
588
589 val = clone2.Get(content)
590 if i%2 != 0 || (i-2)%3 == 0 {
591 if val != nil {
592 t.Errorf("Didn't expect key %v, but found key:value %v:%v", content.Key, val.(Content).Key, val.(Content).Value)
593 }
594 } else {
595 if val == nil {
596 t.Errorf("Expected key %v, but didn't find it", content.Key)
597 }
598 }
599 }
600}
601
602// --------------------
603// Stress tests. Disabled for testing performance
604
605//func TestStress(t *testing.T) {
606// // Loop through creating B-Trees with a range of degrees from 3 to 12, stepping by 3.
607// // Insert 1000 records into each tree, then search for each record.
608// // Delete half of the records, skipping every other one, then search for each record.
609//
610// for degree := 3; degree <= 12; degree += 3 {
611// t.Logf("Testing B-Tree of degree %d\n", degree)
612// tree := New(WithDegree(degree))
613//
614// // Insert 1000 records
615// t.Logf("Inserting 1000 records\n")
616// for i := 0; i < 1000; i++ {
617// content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
618// tree.Insert(content)
619// }
620//
621// // Search for all records
622// for i := 0; i < 1000; i++ {
623// content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
624// val := tree.Get(content)
625// if val == nil {
626// t.Errorf("Expected key %v, but didn't find it", content.Key)
627// }
628// }
629//
630// // Delete half of the records
631// for i := 0; i < 1000; i += 2 {
632// content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
633// tree.Delete(content)
634// }
635//
636// // Search for all records
637// for i := 0; i < 1000; i++ {
638// content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
639// val := tree.Get(content)
640// if i%2 == 0 {
641// if val != nil {
642// t.Errorf("Didn't expect key %v, but found key:value %v:%v", content.Key, val.(Content).Key, val.(Content).Value)
643// }
644// } else {
645// if val == nil {
646// t.Errorf("Expected key %v, but didn't find it", content.Key)
647// }
648// }
649// }
650// }
651//
652// // Now create a very large tree, with 100000 records
653// // Then delete roughly one third of them, using a very basic random number generation scheme
654// // (implement it right here) to determine which records to delete.
655// // Print a few lines using Logf to let the user know what's happening.
656//
657// t.Logf("Testing B-Tree of degree 10 with 100000 records\n")
658// tree := New(WithDegree(10))
659//
660// // Insert 100000 records
661// t.Logf("Inserting 100000 records\n")
662// for i := 0; i < 100000; i++ {
663// content := Content{Key: i, Value: fmt.Sprintf("Value_%d", i)}
664// tree.Insert(content)
665// }
666//
667// // Implement a very basic random number generator
668// seed := 0
669// random := func() int {
670// seed = (seed*1103515245 + 12345) & 0x7fffffff
671// return seed
672// }
673//
674// // Delete one third of the records
675// t.Logf("Deleting one third of the records\n")
676// for i := 0; i < 35000; i++ {
677// content := Content{Key: random() % 100000, Value: fmt.Sprintf("Value_%d", i)}
678// tree.Delete(content)
679// }
680//}
