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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
package match
import (
"testing"
)
func TestBTree(t *testing.T) {
for id, test := range []struct {
tree BTree
str string
exp bool
}{
{
NewBTree(NewText("abc"), NewSuper(), NewSuper()),
"abc",
true,
},
{
NewBTree(NewText("a"), NewSingle(nil), NewSingle(nil)),
"aaa",
true,
},
{
NewBTree(NewText("b"), NewSingle(nil), nil),
"bbb",
false,
},
{
NewBTree(
NewText("c"),
NewBTree(
NewSingle(nil),
NewSuper(),
nil,
),
nil,
),
"abc",
true,
},
} {
act := test.tree.Match(test.str)
if act != test.exp {
t.Errorf("#%d match %q error: act: %t; exp: %t", id, test.str, act, test.exp)
continue
}
}
}
type fakeMatcher struct {
len int
name string
}
func (f *fakeMatcher) Match(string) bool {
return true
}
var i = 3
func (f *fakeMatcher) Index(s string) (int, []int) {
seg := make([]int, 0, i)
for x := 0; x < i; x++ {
seg = append(seg, x)
}
return 0, seg
}
func (f *fakeMatcher) Len() int {
return f.len
}
func (f *fakeMatcher) String() string {
return f.name
}
func BenchmarkMatchBTree(b *testing.B) {
l := &fakeMatcher{4, "left_fake"}
r := &fakeMatcher{4, "right_fake"}
v := &fakeMatcher{2, "value_fake"}
// must be <= len(l + r + v)
fixture := "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij"
bt := NewBTree(v, l, r)
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
bt.Match(fixture)
}
})
}
|
