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 desc bool
21 }{
22 {"ascending", false},
23 {"descending", true},
24 }
25
26 for _, tt := range tt {
27 t.Run(tt.name, func(t *testing.T) {
28 sl := strings.Split(testStrings, "\n")
29
30 // sort a first time in the order opposite to how we'll be traversing
31 // the tree, to ensure that we are not just iterating through with
32 // insertion order.
33 sort.Strings(sl)
34 if !tt.desc {
35 reverseSlice(sl)
36 }
37
38 r := NewNode(sl[0], nil)
39 for _, v := range sl[1:] {
40 r, _ = r.Set(v, nil)
41 }
42
43 // then sort sl in the order we'll be traversing it, so that we can
44 // compare the result with sl.
45 reverseSlice(sl)
46
47 var result []string
48 for i := 0; i < len(sl); i++ {
49 r.TraverseByOffset(i, 1, tt.desc, 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.desc, 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 }
427}
428
429func TestRotateWhenHeightDiffers(t *testing.T) {
430 tests := []struct {
431 name string
432 input []string
433 expected []string
434 }{
435 {
436 "right rotation when left subtree is higher",
437 []string{"E", "C", "A", "B", "D"},
438 []string{"A", "B", "C", "E", "D"},
439 },
440 {
441 "left rotation when right subtree is higher",
442 []string{"A", "C", "E", "D", "F"},
443 []string{"A", "C", "D", "E", "F"},
444 },
445 {
446 "left-right rotation",
447 []string{"E", "A", "C", "B", "D"},
448 []string{"A", "B", "C", "E", "D"},
449 },
450 {
451 "right-left rotation",
452 []string{"A", "E", "C", "B", "D"},
453 []string{"A", "B", "C", "E", "D"},
454 },
455 }
456
457 for _, tt := range tests {
458 t.Run(tt.name, func(t *testing.T) {
459 var tree *Node
460 for _, key := range tt.input {
461 tree, _ = tree.Set(key, nil)
462 }
463
464 // perform rotation or balance
465 tree = tree.balance()
466
467 // check tree structure
468 var result []string
469 tree.Iterate("", "", func(n *Node) bool {
470 result = append(result, n.Key())
471 return false
472 })
473
474 if !slicesEqual(tt.expected, result) {
475 t.Errorf("want %v got %v", tt.expected, result)
476 }
477 })
478 }
479}
480
481func TestRotateAndBalance(t *testing.T) {
482 tests := []struct {
483 name string
484 input []string
485 expected []string
486 }{
487 {
488 "right rotation",
489 []string{"A", "B", "C", "D", "E"},
490 []string{"A", "B", "C", "D", "E"},
491 },
492 {
493 "left rotation",
494 []string{"E", "D", "C", "B", "A"},
495 []string{"A", "B", "C", "D", "E"},
496 },
497 {
498 "left-right rotation",
499 []string{"C", "A", "E", "B", "D"},
500 []string{"A", "B", "C", "D", "E"},
501 },
502 {
503 "right-left rotation",
504 []string{"C", "E", "A", "D", "B"},
505 []string{"A", "B", "C", "D", "E"},
506 },
507 }
508
509 for _, tt := range tests {
510 t.Run(tt.name, func(t *testing.T) {
511 var tree *Node
512 for _, key := range tt.input {
513 tree, _ = tree.Set(key, nil)
514 }
515
516 tree = tree.balance()
517
518 var result []string
519 tree.Iterate("", "", func(n *Node) bool {
520 result = append(result, n.Key())
521 return false
522 })
523
524 if !slicesEqual(tt.expected, result) {
525 t.Errorf("want %v got %v", tt.expected, result)
526 }
527 })
528 }
529}
530
531func slicesEqual(w1, w2 []string) bool {
532 if len(w1) != len(w2) {
533 return false
534 }
535 for i := 0; i < len(w1); i++ {
536 if w1[0] != w2[0] {
537 return false
538 }
539 }
540 return true
541}
542
543func maxint8(a, b int8) int8 {
544 if a > b {
545 return a
546 }
547 return b
548}
549
550func reverseSlice(ss []string) {
551 for i := 0; i < len(ss)/2; i++ {
552 j := len(ss) - 1 - i
553 ss[i], ss[j] = ss[j], ss[i]
554 }
555}
node_test.gno
10.25 Kb ยท 555 lines
