Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

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}