-
Notifications
You must be signed in to change notification settings - Fork 0
/
traversal_test.go
73 lines (65 loc) · 1.36 KB
/
traversal_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package rbtree
import (
"sort"
"strconv"
"testing"
)
func TestFuzzInOrder(t *testing.T) {
tree := New(compare)
keys := generateKeys(512)
for _, key := range keys {
tree.Insert(key)
}
sort.Ints(keys)
inOrder := tree.InOrder()
for i := 0; inOrder.HasNext(); i++ {
if i >= len(keys) {
t.Fatal("fuzz in order HasNext failed")
}
if inOrder.Next() != keys[i] {
t.Fatal("fuzz in order bad val")
}
}
}
func TestFuzzOutOrder(t *testing.T) {
tree := New(compare)
keys := generateKeys(512)
for _, key := range keys {
tree.Insert(key)
}
sort.Sort(sort.Reverse(sort.IntSlice(keys)))
outOrder := tree.OutOrder()
for i := 0; outOrder.HasNext(); i++ {
if i >= len(keys) {
t.Fatal("fuzz out order HasNext failed")
}
if outOrder.Next() != keys[i] {
t.Fatal("fuzz out order bad val")
}
}
}
// Benchmark time taken to traverse the entire red-black tree.
func BenchmarkInOrderGrowth(b *testing.B) {
top := 6
if testing.Short() {
top /= 2
}
sizes := []int{256}
for i := 1; i < top; i++ {
sizes = append(sizes, sizes[i-1]*2)
}
for _, size := range sizes {
b.Run(strconv.Itoa(size), func(sub *testing.B) {
tree := New(compare)
keys := generateKeys(size)
for _, key := range keys {
tree.Insert(key)
}
sub.ResetTimer()
for i := 0; i < sub.N; i++ {
for in := tree.InOrder(); in.HasNext(); in.Next() {
}
}
})
}
}