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