Search Apps Documentation Source Content File Folder Download Copy

node_test.gno

10.88 Kb ยท 577 lines
  1package avl
  2
  3import (
  4	"sort"
  5	"strings"
  6	"testing"
  7)
  8
  9func TestTraverseByOffset(t *testing.T) {
 10	const testStrings = `Alfa
 11Alfred
 12Alpha
 13Alphabet
 14Beta
 15Beth
 16Book
 17Browser`
 18	tt := []struct {
 19		name string
 20		asc  bool
 21	}{
 22		{"ascending", true},
 23		{"descending", false},
 24	}
 25
 26	for _, tt := range tt {
 27		t.Run(tt.name, func(t *testing.T) {
 28			// use sl to insert the values, and reversed to match the values
 29			// we do this to ensure that the order of TraverseByOffset is independent
 30			// from the insertion order
 31			sl := strings.Split(testStrings, "\n")
 32			sort.Strings(sl)
 33			reversed := append([]string{}, sl...)
 34			reverseSlice(reversed)
 35
 36			if !tt.asc {
 37				sl, reversed = reversed, sl
 38			}
 39
 40			r := NewNode(reversed[0], nil)
 41			for _, v := range reversed[1:] {
 42				r, _ = r.Set(v, nil)
 43			}
 44
 45			var result []string
 46			for i := 0; i < len(sl); i++ {
 47				r.TraverseByOffset(i, 1, tt.asc, true, func(n *Node) bool {
 48					result = append(result, n.Key())
 49					return false
 50				})
 51			}
 52
 53			if !slicesEqual(sl, result) {
 54				t.Errorf("want %v got %v", sl, result)
 55			}
 56
 57			for l := 2; l <= len(sl); l++ {
 58				// "slices"
 59				for i := 0; i <= len(sl); i++ {
 60					max := i + l
 61					if max > len(sl) {
 62						max = len(sl)
 63					}
 64					exp := sl[i:max]
 65					actual := []string{}
 66
 67					r.TraverseByOffset(i, l, tt.asc, true, func(tr *Node) bool {
 68						actual = append(actual, tr.Key())
 69						return false
 70					})
 71					if !slicesEqual(exp, actual) {
 72						t.Errorf("want %v got %v", exp, actual)
 73					}
 74				}
 75			}
 76		})
 77	}
 78}
 79
 80func TestHas(t *testing.T) {
 81	tests := []struct {
 82		name     string
 83		input    []string
 84		hasKey   string
 85		expected bool
 86	}{
 87		{
 88			"has key in non-empty tree",
 89			[]string{"C", "A", "B", "E", "D"},
 90			"B",
 91			true,
 92		},
 93		{
 94			"does not have key in non-empty tree",
 95			[]string{"C", "A", "B", "E", "D"},
 96			"F",
 97			false,
 98		},
 99		{
100			"has key in single-node tree",
101			[]string{"A"},
102			"A",
103			true,
104		},
105		{
106			"does not have key in single-node tree",
107			[]string{"A"},
108			"B",
109			false,
110		},
111		{
112			"does not have key in empty tree",
113			[]string{},
114			"A",
115			false,
116		},
117	}
118
119	for _, tt := range tests {
120		t.Run(tt.name, func(t *testing.T) {
121			var tree *Node
122			for _, key := range tt.input {
123				tree, _ = tree.Set(key, nil)
124			}
125
126			result := tree.Has(tt.hasKey)
127
128			if result != tt.expected {
129				t.Errorf("Expected %v, got %v", tt.expected, result)
130			}
131		})
132	}
133}
134
135func TestGet(t *testing.T) {
136	tests := []struct {
137		name         string
138		input        []string
139		getKey       string
140		expectIdx    int
141		expectVal    interface{}
142		expectExists bool
143	}{
144		{
145			"get existing key",
146			[]string{"C", "A", "B", "E", "D"},
147			"B",
148			1,
149			nil,
150			true,
151		},
152		{
153			"get non-existent key (smaller)",
154			[]string{"C", "A", "B", "E", "D"},
155			"@",
156			0,
157			nil,
158			false,
159		},
160		{
161			"get non-existent key (larger)",
162			[]string{"C", "A", "B", "E", "D"},
163			"F",
164			5,
165			nil,
166			false,
167		},
168		{
169			"get from empty tree",
170			[]string{},
171			"A",
172			0,
173			nil,
174			false,
175		},
176	}
177
178	for _, tt := range tests {
179		t.Run(tt.name, func(t *testing.T) {
180			var tree *Node
181			for _, key := range tt.input {
182				tree, _ = tree.Set(key, nil)
183			}
184
185			idx, val, exists := tree.Get(tt.getKey)
186
187			if idx != tt.expectIdx {
188				t.Errorf("Expected index %d, got %d", tt.expectIdx, idx)
189			}
190
191			if val != tt.expectVal {
192				t.Errorf("Expected value %v, got %v", tt.expectVal, val)
193			}
194
195			if exists != tt.expectExists {
196				t.Errorf("Expected exists %t, got %t", tt.expectExists, exists)
197			}
198		})
199	}
200}
201
202func TestGetByIndex(t *testing.T) {
203	tests := []struct {
204		name        string
205		input       []string
206		idx         int
207		expectKey   string
208		expectVal   interface{}
209		expectPanic bool
210	}{
211		{
212			"get by valid index",
213			[]string{"C", "A", "B", "E", "D"},
214			2,
215			"C",
216			nil,
217			false,
218		},
219		{
220			"get by valid index (smallest)",
221			[]string{"C", "A", "B", "E", "D"},
222			0,
223			"A",
224			nil,
225			false,
226		},
227		{
228			"get by valid index (largest)",
229			[]string{"C", "A", "B", "E", "D"},
230			4,
231			"E",
232			nil,
233			false,
234		},
235		{
236			"get by invalid index (negative)",
237			[]string{"C", "A", "B", "E", "D"},
238			-1,
239			"",
240			nil,
241			true,
242		},
243		{
244			"get by invalid index (out of range)",
245			[]string{"C", "A", "B", "E", "D"},
246			5,
247			"",
248			nil,
249			true,
250		},
251	}
252
253	for _, tt := range tests {
254		t.Run(tt.name, func(t *testing.T) {
255			var tree *Node
256			for _, key := range tt.input {
257				tree, _ = tree.Set(key, nil)
258			}
259
260			if tt.expectPanic {
261				defer func() {
262					if r := recover(); r == nil {
263						t.Errorf("Expected a panic but didn't get one")
264					}
265				}()
266			}
267
268			key, val := tree.GetByIndex(tt.idx)
269
270			if !tt.expectPanic {
271				if key != tt.expectKey {
272					t.Errorf("Expected key %s, got %s", tt.expectKey, key)
273				}
274
275				if val != tt.expectVal {
276					t.Errorf("Expected value %v, got %v", tt.expectVal, val)
277				}
278			}
279		})
280	}
281}
282
283func TestRemove(t *testing.T) {
284	tests := []struct {
285		name      string
286		input     []string
287		removeKey string
288		expected  []string
289	}{
290		{
291			"remove leaf node",
292			[]string{"C", "A", "B", "D"},
293			"B",
294			[]string{"A", "C", "D"},
295		},
296		{
297			"remove node with one child",
298			[]string{"C", "A", "B", "D"},
299			"A",
300			[]string{"B", "C", "D"},
301		},
302		{
303			"remove node with two children",
304			[]string{"C", "A", "B", "E", "D"},
305			"C",
306			[]string{"A", "B", "D", "E"},
307		},
308		{
309			"remove root node",
310			[]string{"C", "A", "B", "E", "D"},
311			"C",
312			[]string{"A", "B", "D", "E"},
313		},
314		{
315			"remove non-existent key",
316			[]string{"C", "A", "B", "E", "D"},
317			"F",
318			[]string{"A", "B", "C", "D", "E"},
319		},
320	}
321
322	for _, tt := range tests {
323		t.Run(tt.name, func(t *testing.T) {
324			var tree *Node
325			for _, key := range tt.input {
326				tree, _ = tree.Set(key, nil)
327			}
328
329			tree, _, _, _ = tree.Remove(tt.removeKey)
330
331			result := make([]string, 0)
332			tree.Iterate("", "", func(n *Node) bool {
333				result = append(result, n.Key())
334				return false
335			})
336
337			if !slicesEqual(tt.expected, result) {
338				t.Errorf("want %v got %v", tt.expected, result)
339			}
340		})
341	}
342}
343
344func TestTraverse(t *testing.T) {
345	tests := []struct {
346		name     string
347		input    []string
348		expected []string
349	}{
350		{
351			"empty tree",
352			[]string{},
353			[]string{},
354		},
355		{
356			"single node tree",
357			[]string{"A"},
358			[]string{"A"},
359		},
360		{
361			"small tree",
362			[]string{"C", "A", "B", "E", "D"},
363			[]string{"A", "B", "C", "D", "E"},
364		},
365		{
366			"large tree",
367			[]string{"H", "D", "L", "B", "F", "J", "N", "A", "C", "E", "G", "I", "K", "M", "O"},
368			[]string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"},
369		},
370	}
371
372	for _, tt := range tests {
373		t.Run(tt.name, func(t *testing.T) {
374			var tree *Node
375			for _, key := range tt.input {
376				tree, _ = tree.Set(key, nil)
377			}
378
379			t.Run("iterate", func(t *testing.T) {
380				var result []string
381				tree.Iterate("", "", func(n *Node) bool {
382					result = append(result, n.Key())
383					return false
384				})
385				if !slicesEqual(tt.expected, result) {
386					t.Errorf("want %v got %v", tt.expected, result)
387				}
388			})
389
390			t.Run("ReverseIterate", func(t *testing.T) {
391				var result []string
392				tree.ReverseIterate("", "", func(n *Node) bool {
393					result = append(result, n.Key())
394					return false
395				})
396				expected := make([]string, len(tt.expected))
397				copy(expected, tt.expected)
398				for i, j := 0, len(expected)-1; i < j; i, j = i+1, j-1 {
399					expected[i], expected[j] = expected[j], expected[i]
400				}
401				if !slicesEqual(expected, result) {
402					t.Errorf("want %v got %v", expected, result)
403				}
404			})
405
406			t.Run("TraverseInRange", func(t *testing.T) {
407				var result []string
408				start, end := "C", "M"
409				tree.TraverseInRange(start, end, true, true, func(n *Node) bool {
410					result = append(result, n.Key())
411					return false
412				})
413				expected := make([]string, 0)
414				for _, key := range tt.expected {
415					if key >= start && key < end {
416						expected = append(expected, key)
417					}
418				}
419				if !slicesEqual(expected, result) {
420					t.Errorf("want %v got %v", expected, result)
421				}
422			})
423
424			t.Run("early termination", func(t *testing.T) {
425				if len(tt.input) == 0 {
426					return // Skip for empty tree
427				}
428
429				var result []string
430				var count int
431				tree.Iterate("", "", func(n *Node) bool {
432					count++
433					result = append(result, n.Key())
434					return true // Stop after first item
435				})
436
437				if count != 1 {
438					t.Errorf("Expected callback to be called exactly once, got %d calls", count)
439				}
440				if len(result) != 1 {
441					t.Errorf("Expected exactly one result, got %d items", len(result))
442				}
443				if len(result) > 0 && result[0] != tt.expected[0] {
444					t.Errorf("Expected first item to be %v, got %v", tt.expected[0], result[0])
445				}
446			})
447		})
448	}
449}
450
451func TestRotateWhenHeightDiffers(t *testing.T) {
452	tests := []struct {
453		name     string
454		input    []string
455		expected []string
456	}{
457		{
458			"right rotation when left subtree is higher",
459			[]string{"E", "C", "A", "B", "D"},
460			[]string{"A", "B", "C", "D", "E"},
461		},
462		{
463			"left rotation when right subtree is higher",
464			[]string{"A", "C", "E", "D", "F"},
465			[]string{"A", "C", "D", "E", "F"},
466		},
467		{
468			"left-right rotation",
469			[]string{"E", "A", "C", "B", "D"},
470			[]string{"A", "B", "C", "D", "E"},
471		},
472		{
473			"right-left rotation",
474			[]string{"A", "E", "C", "B", "D"},
475			[]string{"A", "B", "C", "D", "E"},
476		},
477	}
478
479	for _, tt := range tests {
480		t.Run(tt.name, func(t *testing.T) {
481			var tree *Node
482			for _, key := range tt.input {
483				tree, _ = tree.Set(key, nil)
484			}
485
486			// perform rotation or balance
487			tree = tree.balance()
488
489			// check tree structure
490			var result []string
491			tree.Iterate("", "", func(n *Node) bool {
492				result = append(result, n.Key())
493				return false
494			})
495
496			if !slicesEqual(tt.expected, result) {
497				t.Errorf("want %v got %v", tt.expected, result)
498			}
499		})
500	}
501}
502
503func TestRotateAndBalance(t *testing.T) {
504	tests := []struct {
505		name     string
506		input    []string
507		expected []string
508	}{
509		{
510			"right rotation",
511			[]string{"A", "B", "C", "D", "E"},
512			[]string{"A", "B", "C", "D", "E"},
513		},
514		{
515			"left rotation",
516			[]string{"E", "D", "C", "B", "A"},
517			[]string{"A", "B", "C", "D", "E"},
518		},
519		{
520			"left-right rotation",
521			[]string{"C", "A", "E", "B", "D"},
522			[]string{"A", "B", "C", "D", "E"},
523		},
524		{
525			"right-left rotation",
526			[]string{"C", "E", "A", "D", "B"},
527			[]string{"A", "B", "C", "D", "E"},
528		},
529	}
530
531	for _, tt := range tests {
532		t.Run(tt.name, func(t *testing.T) {
533			var tree *Node
534			for _, key := range tt.input {
535				tree, _ = tree.Set(key, nil)
536			}
537
538			tree = tree.balance()
539
540			var result []string
541			tree.Iterate("", "", func(n *Node) bool {
542				result = append(result, n.Key())
543				return false
544			})
545
546			if !slicesEqual(tt.expected, result) {
547				t.Errorf("want %v got %v", tt.expected, result)
548			}
549		})
550	}
551}
552
553func slicesEqual(w1, w2 []string) bool {
554	if len(w1) != len(w2) {
555		return false
556	}
557	for i := 0; i < len(w1); i++ {
558		if w1[i] != w2[i] {
559			return false
560		}
561	}
562	return true
563}
564
565func maxint8(a, b int8) int8 {
566	if a > b {
567		return a
568	}
569	return b
570}
571
572func reverseSlice(ss []string) {
573	for i := 0; i < len(ss)/2; i++ {
574		j := len(ss) - 1 - i
575		ss[i], ss[j] = ss[j], ss[i]
576	}
577}