node_test.gno
15.98 Kb · 763 lines
1package avl
2
3import (
4 "sort"
5 "strings"
6 "testing"
7
8 "gno.land/p/nt/ufmt/v0"
9)
10
11func TestTraverseByOffset(t *testing.T) {
12 const testStrings = `Alfa
13Alfred
14Alpha
15Alphabet
16Beta
17Beth
18Book
19Browser`
20 tt := []struct {
21 name string
22 asc bool
23 }{
24 {"ascending", true},
25 {"descending", false},
26 }
27
28 for _, tt := range tt {
29 t.Run(tt.name, func(t *testing.T) {
30 // use sl to insert the values, and reversed to match the values
31 // we do this to ensure that the order of TraverseByOffset is independent
32 // from the insertion order
33 sl := strings.Split(testStrings, "\n")
34 sort.Strings(sl)
35 reversed := append([]string{}, sl...)
36 reverseSlice(reversed)
37
38 if !tt.asc {
39 sl, reversed = reversed, sl
40 }
41
42 r := NewNode(reversed[0], nil)
43 for _, v := range reversed[1:] {
44 r, _ = r.Set(v, nil)
45 }
46
47 var result []string
48 for i := 0; i < len(sl); i++ {
49 r.TraverseByOffset(i, 1, tt.asc, true, func(n *Node) bool {
50 result = append(result, n.Key())
51 return false
52 })
53 }
54
55 if !slicesEqual(sl, result) {
56 t.Errorf("want %v got %v", sl, result)
57 }
58
59 for l := 2; l <= len(sl); l++ {
60 // "slices"
61 for i := 0; i <= len(sl); i++ {
62 max := i + l
63 if max > len(sl) {
64 max = len(sl)
65 }
66 exp := sl[i:max]
67 actual := []string{}
68
69 r.TraverseByOffset(i, l, tt.asc, true, func(tr *Node) bool {
70 actual = append(actual, tr.Key())
71 return false
72 })
73 if !slicesEqual(exp, actual) {
74 t.Errorf("want %v got %v", exp, actual)
75 }
76 }
77 }
78 })
79 }
80}
81
82func TestTraverseByOffsetNegativeOffset(t *testing.T) {
83 // a negative offset must be treated as 0, not silently drop the right
84 // subtree. building {"a","b","c","d"} yields a tree whose root has two
85 // inner children, exercising the traverseByOffset delta computation.
86 keys := []string{"a", "b", "c", "d"}
87 r := NewNode(keys[0], nil)
88 for _, k := range keys[1:] {
89 r, _ = r.Set(k, nil)
90 }
91
92 for _, offset := range []int{-1, -2, -100} {
93 var got []string
94 r.TraverseByOffset(offset, len(keys), true, true, func(n *Node) bool {
95 got = append(got, n.Key())
96 return false
97 })
98 if !slicesEqual(keys, got) {
99 t.Errorf("offset %d: want %v got %v", offset, keys, got)
100 }
101 }
102}
103
104func TestHas(t *testing.T) {
105 tests := []struct {
106 name string
107 input []string
108 hasKey string
109 expected bool
110 }{
111 {
112 "has key in non-empty tree",
113 []string{"C", "A", "B", "E", "D"},
114 "B",
115 true,
116 },
117 {
118 "does not have key in non-empty tree",
119 []string{"C", "A", "B", "E", "D"},
120 "F",
121 false,
122 },
123 {
124 "has key in single-node tree",
125 []string{"A"},
126 "A",
127 true,
128 },
129 {
130 "does not have key in single-node tree",
131 []string{"A"},
132 "B",
133 false,
134 },
135 {
136 "does not have key in empty tree",
137 []string{},
138 "A",
139 false,
140 },
141 }
142
143 for _, tt := range tests {
144 t.Run(tt.name, func(t *testing.T) {
145 var tree *Node
146 for _, key := range tt.input {
147 tree, _ = tree.Set(key, nil)
148 }
149
150 result := tree.Has(tt.hasKey)
151
152 if result != tt.expected {
153 t.Errorf("Expected %v, got %v", tt.expected, result)
154 }
155 })
156 }
157}
158
159func TestGet(t *testing.T) {
160 tests := []struct {
161 name string
162 input []string
163 getKey string
164 expectIdx int
165 expectVal any
166 expectExists bool
167 }{
168 {
169 "get existing key",
170 []string{"C", "A", "B", "E", "D"},
171 "B",
172 1,
173 nil,
174 true,
175 },
176 {
177 "get non-existent key (smaller)",
178 []string{"C", "A", "B", "E", "D"},
179 "@",
180 0,
181 nil,
182 false,
183 },
184 {
185 "get non-existent key (larger)",
186 []string{"C", "A", "B", "E", "D"},
187 "F",
188 5,
189 nil,
190 false,
191 },
192 {
193 "get from empty tree",
194 []string{},
195 "A",
196 0,
197 nil,
198 false,
199 },
200 }
201
202 for _, tt := range tests {
203 t.Run(tt.name, func(t *testing.T) {
204 var tree *Node
205 for _, key := range tt.input {
206 tree, _ = tree.Set(key, nil)
207 }
208
209 idx, val, exists := tree.Get(tt.getKey)
210
211 if idx != tt.expectIdx {
212 t.Errorf("Expected index %d, got %d", tt.expectIdx, idx)
213 }
214
215 if val != tt.expectVal {
216 t.Errorf("Expected value %v, got %v", tt.expectVal, val)
217 }
218
219 if exists != tt.expectExists {
220 t.Errorf("Expected exists %t, got %t", tt.expectExists, exists)
221 }
222 })
223 }
224}
225
226func TestGetByIndex(t *testing.T) {
227 tests := []struct {
228 name string
229 input []string
230 idx int
231 expectKey string
232 expectVal any
233 expectPanic bool
234 }{
235 {
236 "get by valid index",
237 []string{"C", "A", "B", "E", "D"},
238 2,
239 "C",
240 nil,
241 false,
242 },
243 {
244 "get by valid index (smallest)",
245 []string{"C", "A", "B", "E", "D"},
246 0,
247 "A",
248 nil,
249 false,
250 },
251 {
252 "get by valid index (largest)",
253 []string{"C", "A", "B", "E", "D"},
254 4,
255 "E",
256 nil,
257 false,
258 },
259 {
260 "get by invalid index (negative)",
261 []string{"C", "A", "B", "E", "D"},
262 -1,
263 "",
264 nil,
265 true,
266 },
267 {
268 "get by invalid index (out of range)",
269 []string{"C", "A", "B", "E", "D"},
270 5,
271 "",
272 nil,
273 true,
274 },
275 }
276
277 for _, tt := range tests {
278 t.Run(tt.name, func(t *testing.T) {
279 var tree *Node
280 for _, key := range tt.input {
281 tree, _ = tree.Set(key, nil)
282 }
283
284 if tt.expectPanic {
285 defer func() {
286 if r := recover(); r == nil {
287 t.Errorf("Expected a panic but didn't get one")
288 }
289 }()
290 }
291
292 key, val := tree.GetByIndex(tt.idx)
293
294 if !tt.expectPanic {
295 if key != tt.expectKey {
296 t.Errorf("Expected key %s, got %s", tt.expectKey, key)
297 }
298
299 if val != tt.expectVal {
300 t.Errorf("Expected value %v, got %v", tt.expectVal, val)
301 }
302 }
303 })
304 }
305}
306
307func TestRemove(t *testing.T) {
308 tests := []struct {
309 name string
310 input []string
311 removeKey string
312 expected []string
313 }{
314 {
315 "remove leaf node",
316 []string{"C", "A", "B", "D"},
317 "B",
318 []string{"A", "C", "D"},
319 },
320 {
321 "remove node with one child",
322 []string{"C", "A", "B", "D"},
323 "A",
324 []string{"B", "C", "D"},
325 },
326 {
327 "remove node with two children",
328 []string{"C", "A", "B", "E", "D"},
329 "C",
330 []string{"A", "B", "D", "E"},
331 },
332 {
333 "remove root node",
334 []string{"C", "A", "B", "E", "D"},
335 "C",
336 []string{"A", "B", "D", "E"},
337 },
338 {
339 "remove non-existent key",
340 []string{"C", "A", "B", "E", "D"},
341 "F",
342 []string{"A", "B", "C", "D", "E"},
343 },
344 }
345
346 for _, tt := range tests {
347 t.Run(tt.name, func(t *testing.T) {
348 var tree *Node
349 for _, key := range tt.input {
350 tree, _ = tree.Set(key, nil)
351 }
352
353 tree, _, _, _ = tree.Remove(tt.removeKey)
354
355 result := make([]string, 0)
356 tree.Iterate("", "", func(n *Node) bool {
357 result = append(result, n.Key())
358 return false
359 })
360
361 if !slicesEqual(tt.expected, result) {
362 t.Errorf("want %v got %v", tt.expected, result)
363 }
364 })
365 }
366}
367
368func TestTraverse(t *testing.T) {
369 tests := []struct {
370 name string
371 input []string
372 expected []string
373 }{
374 {
375 "empty tree",
376 []string{},
377 []string{},
378 },
379 {
380 "single node tree",
381 []string{"A"},
382 []string{"A"},
383 },
384 {
385 "small tree",
386 []string{"C", "A", "B", "E", "D"},
387 []string{"A", "B", "C", "D", "E"},
388 },
389 {
390 "large tree",
391 []string{"H", "D", "L", "B", "F", "J", "N", "A", "C", "E", "G", "I", "K", "M", "O"},
392 []string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"},
393 },
394 }
395
396 for _, tt := range tests {
397 t.Run(tt.name, func(t *testing.T) {
398 var tree *Node
399 for _, key := range tt.input {
400 tree, _ = tree.Set(key, nil)
401 }
402
403 t.Run("iterate", func(t *testing.T) {
404 var result []string
405 tree.Iterate("", "", func(n *Node) bool {
406 result = append(result, n.Key())
407 return false
408 })
409 if !slicesEqual(tt.expected, result) {
410 t.Errorf("want %v got %v", tt.expected, result)
411 }
412 })
413
414 t.Run("ReverseIterate", func(t *testing.T) {
415 var result []string
416 tree.ReverseIterate("", "", func(n *Node) bool {
417 result = append(result, n.Key())
418 return false
419 })
420 expected := make([]string, len(tt.expected))
421 copy(expected, tt.expected)
422 for i, j := 0, len(expected)-1; i < j; i, j = i+1, j-1 {
423 expected[i], expected[j] = expected[j], expected[i]
424 }
425 if !slicesEqual(expected, result) {
426 t.Errorf("want %v got %v", expected, result)
427 }
428 })
429
430 t.Run("TraverseInRange", func(t *testing.T) {
431 var result []string
432 start, end := "C", "M"
433 tree.TraverseInRange(start, end, true, true, func(n *Node) bool {
434 result = append(result, n.Key())
435 return false
436 })
437 expected := make([]string, 0)
438 for _, key := range tt.expected {
439 if key >= start && key < end {
440 expected = append(expected, key)
441 }
442 }
443 if !slicesEqual(expected, result) {
444 t.Errorf("want %v got %v", expected, result)
445 }
446 })
447
448 t.Run("early termination", func(t *testing.T) {
449 if len(tt.input) == 0 {
450 return // Skip for empty tree
451 }
452
453 var result []string
454 var count int
455 tree.Iterate("", "", func(n *Node) bool {
456 count++
457 result = append(result, n.Key())
458 return true // Stop after first item
459 })
460
461 if count != 1 {
462 t.Errorf("Expected callback to be called exactly once, got %d calls", count)
463 }
464 if len(result) != 1 {
465 t.Errorf("Expected exactly one result, got %d items", len(result))
466 }
467 if len(result) > 0 && result[0] != tt.expected[0] {
468 t.Errorf("Expected first item to be %v, got %v", tt.expected[0], result[0])
469 }
470 })
471 })
472 }
473}
474
475func TestRotateWhenHeightDiffers(t *testing.T) {
476 tests := []struct {
477 name string
478 input []string
479 expected []string
480 }{
481 {
482 "right rotation when left subtree is higher",
483 []string{"E", "C", "A", "B", "D"},
484 []string{"A", "B", "C", "D", "E"},
485 },
486 {
487 "left rotation when right subtree is higher",
488 []string{"A", "C", "E", "D", "F"},
489 []string{"A", "C", "D", "E", "F"},
490 },
491 {
492 "left-right rotation",
493 []string{"E", "A", "C", "B", "D"},
494 []string{"A", "B", "C", "D", "E"},
495 },
496 {
497 "right-left rotation",
498 []string{"A", "E", "C", "B", "D"},
499 []string{"A", "B", "C", "D", "E"},
500 },
501 }
502
503 for _, tt := range tests {
504 t.Run(tt.name, func(t *testing.T) {
505 var tree *Node
506 for _, key := range tt.input {
507 tree, _ = tree.Set(key, nil)
508 }
509
510 // perform rotation or balance
511 tree = tree.balance()
512
513 // check tree structure
514 var result []string
515 tree.Iterate("", "", func(n *Node) bool {
516 result = append(result, n.Key())
517 return false
518 })
519
520 if !slicesEqual(tt.expected, result) {
521 t.Errorf("want %v got %v", tt.expected, result)
522 }
523 })
524 }
525}
526
527func TestRotateAndBalance(t *testing.T) {
528 tests := []struct {
529 name string
530 input []string
531 expected []string
532 }{
533 {
534 "right rotation",
535 []string{"A", "B", "C", "D", "E"},
536 []string{"A", "B", "C", "D", "E"},
537 },
538 {
539 "left rotation",
540 []string{"E", "D", "C", "B", "A"},
541 []string{"A", "B", "C", "D", "E"},
542 },
543 {
544 "left-right rotation",
545 []string{"C", "A", "E", "B", "D"},
546 []string{"A", "B", "C", "D", "E"},
547 },
548 {
549 "right-left rotation",
550 []string{"C", "E", "A", "D", "B"},
551 []string{"A", "B", "C", "D", "E"},
552 },
553 }
554
555 for _, tt := range tests {
556 t.Run(tt.name, func(t *testing.T) {
557 var tree *Node
558 for _, key := range tt.input {
559 tree, _ = tree.Set(key, nil)
560 }
561
562 tree = tree.balance()
563
564 var result []string
565 tree.Iterate("", "", func(n *Node) bool {
566 result = append(result, n.Key())
567 return false
568 })
569
570 if !slicesEqual(tt.expected, result) {
571 t.Errorf("want %v got %v", tt.expected, result)
572 }
573 })
574 }
575}
576
577func TestRemoveFromEmptyTree(t *testing.T) {
578 var tree *Node
579 newTree, _, val, removed := tree.Remove("NonExistent")
580 if newTree != nil {
581 t.Errorf("Removing from an empty tree should still be nil tree.")
582 }
583 if val != nil || removed {
584 t.Errorf("Expected no value and removed=false when removing from empty tree.")
585 }
586}
587
588func TestBalanceAfterRemoval(t *testing.T) {
589 tests := []struct {
590 name string
591 insertKeys []string
592 removeKey string
593 expectedBalance int
594 }{
595 {
596 name: "balance after removing right node",
597 insertKeys: []string{"B", "A", "D", "C", "E"},
598 removeKey: "E",
599 expectedBalance: 0,
600 },
601 {
602 name: "balance after removing left node",
603 insertKeys: []string{"D", "B", "E", "A", "C"},
604 removeKey: "A",
605 expectedBalance: 0,
606 },
607 {
608 name: "ensure no lean after removal",
609 insertKeys: []string{"C", "B", "E", "A", "D", "F"},
610 removeKey: "F",
611 expectedBalance: -1,
612 },
613 {
614 name: "descending order insert, remove middle node",
615 insertKeys: []string{"E", "D", "C", "B", "A"},
616 removeKey: "C",
617 expectedBalance: 0,
618 },
619 {
620 name: "ascending order insert, remove middle node",
621 insertKeys: []string{"A", "B", "C", "D", "E"},
622 removeKey: "C",
623 expectedBalance: 0,
624 },
625 {
626 name: "duplicate key insert, remove the duplicated key",
627 insertKeys: []string{"C", "B", "C", "A", "D"},
628 removeKey: "C",
629 expectedBalance: 1,
630 },
631 {
632 name: "complex rotation case",
633 insertKeys: []string{"H", "B", "A", "C", "E", "D", "F", "G"},
634 removeKey: "B",
635 expectedBalance: 0,
636 },
637 }
638
639 for _, tt := range tests {
640 t.Run(tt.name, func(t *testing.T) {
641 var tree *Node
642 for _, key := range tt.insertKeys {
643 tree, _ = tree.Set(key, nil)
644 }
645
646 tree, _, _, _ = tree.Remove(tt.removeKey)
647
648 balance := tree.calcBalance()
649 if balance != tt.expectedBalance {
650 t.Errorf("Expected balance factor %d, got %d", tt.expectedBalance, balance)
651 }
652
653 if balance < -1 || balance > 1 {
654 t.Errorf("Tree is unbalanced with factor %d", balance)
655 }
656
657 if errMsg := checkSubtreeBalance(t, tree); errMsg != "" {
658 t.Errorf("AVL property violation after removal: %s", errMsg)
659 }
660 })
661 }
662}
663
664func TestBSTProperty(t *testing.T) {
665 var tree *Node
666 keys := []string{"D", "B", "F", "A", "C", "E", "G"}
667 for _, key := range keys {
668 tree, _ = tree.Set(key, nil)
669 }
670
671 var result []string
672 inorderTraversal(t, tree, &result)
673
674 for i := 1; i < len(result); i++ {
675 if result[i] < result[i-1] {
676 t.Errorf("BST property violated: %s < %s (index %d)",
677 result[i], result[i-1], i)
678 }
679 }
680}
681
682// inorderTraversal performs an inorder traversal of the tree and returns the keys in a list.
683func inorderTraversal(t *testing.T, node *Node, result *[]string) {
684 t.Helper()
685
686 if node == nil {
687 return
688 }
689 // leaf
690 if node.height == 0 {
691 *result = append(*result, node.key)
692 return
693 }
694 inorderTraversal(t, node.leftNode, result)
695 inorderTraversal(t, node.rightNode, result)
696}
697
698// checkSubtreeBalance checks if all nodes under the given node satisfy the AVL tree conditions.
699// The balance factor of all nodes must be ∈ [-1, +1]
700func checkSubtreeBalance(t *testing.T, node *Node) string {
701 t.Helper()
702
703 if node == nil {
704 return ""
705 }
706
707 if node.IsLeaf() {
708 // leaf node must be height=0, size=1
709 if node.height != 0 {
710 return ufmt.Sprintf("Leaf node %s has height %d, expected 0", node.Key(), node.height)
711 }
712 if node.size != 1 {
713 return ufmt.Sprintf("Leaf node %s has size %d, expected 1", node.Key(), node.size)
714 }
715 return ""
716 }
717
718 // check balance factor for current node
719 balanceFactor := node.calcBalance()
720 if balanceFactor < -1 || balanceFactor > 1 {
721 return ufmt.Sprintf("Node %s is unbalanced: balanceFactor=%d", node.Key(), balanceFactor)
722 }
723
724 // check height / size relationship for children
725 left, right := node.getLeftNode(), node.getRightNode()
726 expectedHeight := maxInt8(left.height, right.height) + 1
727 if node.height != expectedHeight {
728 return ufmt.Sprintf("Node %s has incorrect height %d, expected %d", node.Key(), node.height, expectedHeight)
729 }
730 expectedSize := left.Size() + right.Size()
731 if node.size != expectedSize {
732 return ufmt.Sprintf("Node %s has incorrect size %d, expected %d", node.Key(), node.size, expectedSize)
733 }
734
735 // recursively check the left/right subtree
736 if errMsg := checkSubtreeBalance(t, left); errMsg != "" {
737 return errMsg
738 }
739 if errMsg := checkSubtreeBalance(t, right); errMsg != "" {
740 return errMsg
741 }
742
743 return ""
744}
745
746func slicesEqual(w1, w2 []string) bool {
747 if len(w1) != len(w2) {
748 return false
749 }
750 for i := 0; i < len(w1); i++ {
751 if w1[i] != w2[i] {
752 return false
753 }
754 }
755 return true
756}
757
758func reverseSlice(ss []string) {
759 for i := 0; i < len(ss)/2; i++ {
760 j := len(ss) - 1 - i
761 ss[i], ss[j] = ss[j], ss[i]
762 }
763}
