Search Apps Documentation Source Content File Folder Download Copy

node_test.gno

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