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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
// Copyright (c) 2013 Mathieu Turcotte
// Licensed under the MIT license.
package gtrie_test
import (
"bufio"
"github.com/ctdk/go-trie/gtrie"
"io"
"log"
"os"
"strings"
"testing"
)
func TestCreateUnsortedWords(t *testing.T) {
_, err := gtrie.Create([]string{"ab", "ef", "cd"})
if err == nil {
t.Errorf("expected error when creating trie from unsorted words")
}
}
func TestTrie(t *testing.T) {
words := []string{"abfg", "acfg", "adfg"}
missings := []string{"", "foo", "été", "adfgg", "adf"}
trie, err := gtrie.Create(words)
if err != nil {
log.Fatal(err)
} else if trie == nil {
log.Fatal("returned trie was nil")
}
// Ensure that stored words are accepted.
for _, word := range words {
if !trie.Accepts(word) {
t.Errorf("expected %s to be accepted", word)
}
}
// Ensure that missings words aren't accepted.
for _, word := range missings {
if trie.Accepts(word) {
t.Errorf("expected %s to be rejected", word)
}
}
// Ensure that the graph is minimal by counting the number of nodes.
size := gtrie.Size(trie)
if size != 5 {
t.Errorf("expected size of 5 but got %s", size)
}
}
func TestPrefix(t *testing.T) {
words := []string{"abfg", "acfg", "adfg"}
missings := []string{"ar", "fo", "ade"}
prefixes := []string{ "ab", "ac", "ad" }
trie, err := gtrie.Create(words)
if err != nil {
log.Fatal(err)
} else if trie == nil {
log.Fatal("returned trie was nil")
}
// Check that prefixes are found
for _, word := range prefixes {
if _, err := trie.HasPrefix(word); err != nil {
t.Errorf("expected %s to be accepted as a prefix", word)
}
}
// Ensure that missing prefixes are not found
for _, word := range missings {
if _, err := trie.HasPrefix(word); err == nil {
t.Errorf("expected %s to be rejected as a prefix", word)
}
}
// Ensure that the graph is minimal by counting the number of nodes.
size := gtrie.Size(trie)
if size != 5 {
t.Errorf("expected size of 5 but got %s", size)
}
}
func BenchmarkAccepts(b *testing.B) {
b.StopTimer()
words := []string{"abaissassions", "abaisserions", "abandonnassions"}
trie, err := gtrie.Create(readWords("words.txt"))
if err != nil {
log.Fatal(err)
}
b.StartTimer()
for i := 0; i < b.N; i++ {
for _, word := range words {
if !trie.Accepts(word) {
log.Fatal(word)
}
}
}
}
func readWords(filename string) (words []string) {
file, err := os.Open(filename)
if err != nil {
log.Fatal(err)
}
defer file.Close()
reader := bufio.NewReader(file)
for {
word, rerr := reader.ReadString('\n')
if rerr != nil {
if rerr == io.EOF {
break
} else {
log.Fatal(err)
}
}
words = append(words, strings.TrimSpace(word))
}
return
}
|
