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}
node_test.gno
10.88 Kb ยท 577 lines
