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