1
2
3
4
5
6
7
8 package trie
9
10 import (
11 "math/rand"
12 "testing"
13 )
14
15 func TestMask(t *testing.T) {
16 for _, c := range []struct {
17 p prefix
18 b bitpos
19 want prefix
20 }{
21 {
22 p: 0b00001000,
23 b: 0b00000100,
24 want: 0b00001011,
25 }, {
26 p: 0b01011011,
27 b: 0b00000000,
28 want: ^prefix(0),
29 }, {
30 p: 0b01011011,
31 b: 0b00000001,
32 want: 0b01011010,
33 }, {
34 p: 0b01011011,
35 b: 0b00000010,
36 want: 0b01011001,
37 }, {
38 p: 0b01011011,
39 b: 0b00000100,
40 want: 0b01011011,
41 }, {
42 p: 0b01011011,
43 b: 0b00001000,
44 want: 0b01010111,
45 }, {
46 p: 0b01011011,
47 b: 0b00010000,
48 want: 0b01001111,
49 }, {
50 p: 0b01011011,
51 b: 0b00100000,
52 want: 0b01011111,
53 }, {
54 p: 0b01011011,
55 b: 0b01000000,
56 want: 0b00111111,
57 }, {
58 p: 0b01011011,
59 b: 0b01000000,
60 want: 0b00111111,
61 }, {
62 p: 0b01011011,
63 b: 0b10000000,
64 want: 0b01111111,
65 },
66 } {
67 if got := mask(c.p, c.b); got != c.want {
68 t.Errorf("mask(%#b,%#b) got %#b. want %#b", c.p, c.b, got, c.want)
69 }
70 }
71 }
72
73 func TestMaskImpotent(t *testing.T) {
74
75 for _, p := range []prefix{
76 0b0, 0b1, 0b100, ^prefix(0b0), ^prefix(0b10),
77 } {
78 for _, b := range []bitpos{
79 0, 0b1, 1 << 2, 1 << 63,
80 } {
81 once := mask(p, b)
82 twice := mask(once, b)
83 if once != twice {
84 t.Errorf("mask(mask(%#b,%#b), %#b) != mask(%#b,%#b) got %#b. want %#b",
85 p, b, b, p, b, twice, once)
86 }
87 }
88 }
89 }
90
91 func TestMatchPrefix(t *testing.T) {
92 for _, c := range []struct {
93 k prefix
94 p prefix
95 b bitpos
96 }{
97 {
98 k: 0b1000,
99 p: 0b1011,
100 b: 0b0100,
101 }, {
102 k: 0b1001,
103 p: 0b1011,
104 b: 0b0100,
105 }, {
106 k: 0b1010,
107 p: 0b1011,
108 b: 0b0100,
109 }, {
110 k: 0b1011,
111 p: 0b1011,
112 b: 0b0100,
113 }, {
114 k: 0b1100,
115 p: 0b1011,
116 b: 0b0100,
117 }, {
118 k: 0b1101,
119 p: 0b1011,
120 b: 0b0100,
121 }, {
122 k: 0b1110,
123 p: 0b1011,
124 b: 0b0100,
125 }, {
126 k: 0b1111,
127 p: 0b1011,
128 b: 0b0100,
129 },
130 } {
131 if !matchPrefix(c.k, c.p, c.b) {
132 t.Errorf("matchPrefix(%#b, %#b,%#b) should be true", c.k, c.p, c.b)
133 }
134 }
135 }
136
137 func TestNotMatchPrefix(t *testing.T) {
138 for _, c := range []struct {
139 k prefix
140 p prefix
141 b bitpos
142 }{
143 {
144 k: 0b0000,
145 p: 0b1011,
146 b: 0b0100,
147 }, {
148 k: 0b0010,
149 p: 0b1011,
150 b: 0b0100,
151 },
152 } {
153 if matchPrefix(c.k, c.p, c.b) {
154 t.Errorf("matchPrefix(%#b, %#b,%#b) should be false", c.k, c.p, c.b)
155 }
156 }
157 }
158
159 func TestBranchingBit(t *testing.T) {
160 for _, c := range []struct {
161 x prefix
162 y prefix
163 want bitpos
164 }{
165 {
166 x: 0b0000,
167 y: 0b1011,
168 want: 0b1000,
169 }, {
170 x: 0b1010,
171 y: 0b1011,
172 want: 0b0001,
173 }, {
174 x: 0b1011,
175 y: 0b1111,
176 want: 0b0100,
177 }, {
178 x: 0b1011,
179 y: 0b1001,
180 want: 0b0010,
181 },
182 } {
183 if got := branchingBit(c.x, c.y); got != c.want {
184 t.Errorf("branchingBit(%#b, %#b,) is not expected value. got %#b want %#b",
185 c.x, c.y, got, c.want)
186 }
187 }
188 }
189
190 func TestZeroBit(t *testing.T) {
191 for _, c := range []struct {
192 k prefix
193 b bitpos
194 }{
195 {
196 k: 0b1000,
197 b: 0b0100,
198 }, {
199 k: 0b1001,
200 b: 0b0100,
201 }, {
202 k: 0b1010,
203 b: 0b0100,
204 },
205 } {
206 if !zeroBit(c.k, c.b) {
207 t.Errorf("zeroBit(%#b, %#b) should be true", c.k, c.b)
208 }
209 }
210 }
211 func TestZeroBitFails(t *testing.T) {
212 for _, c := range []struct {
213 k prefix
214 b bitpos
215 }{
216 {
217 k: 0b1000,
218 b: 0b1000,
219 }, {
220 k: 0b1001,
221 b: 0b0001,
222 }, {
223 k: 0b1010,
224 b: 0b0010,
225 }, {
226 k: 0b1011,
227 b: 0b0001,
228 },
229 } {
230 if zeroBit(c.k, c.b) {
231 t.Errorf("zeroBit(%#b, %#b) should be false", c.k, c.b)
232 }
233 }
234 }
235
236 func TestOrd(t *testing.T) {
237 a := bitpos(0b0010)
238 b := bitpos(0b1000)
239 if ord(a, b) {
240 t.Errorf("ord(%#b, %#b) should be false", a, b)
241 }
242 if !ord(b, a) {
243 t.Errorf("ord(%#b, %#b) should be true", b, a)
244 }
245 if ord(a, a) {
246 t.Errorf("ord(%#b, %#b) should be false", a, a)
247 }
248 if !ord(a, 0) {
249 t.Errorf("ord(%#b, %#b) should be true", a, 0)
250 }
251 }
252
253 func TestPrefixesOverlapLemma(t *testing.T) {
254
255
256
257
258
259
260
261
262 m, n := bitpos(1<<2), bitpos(1<<1)
263 p, q := mask(0b100, m), mask(0b010, n)
264 if !(prefixesOverlap(p, m, q, n) && m > n && matchPrefix(q, p, m)) {
265 t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
266 p, m, q, n)
267 }
268
269 m, n = bitpos(1<<2), bitpos(1<<3)
270 p, q = mask(0b100, m), mask(0b1000, n)
271 if !(prefixesOverlap(p, m, q, n) && m < n && matchPrefix(p, q, n)) {
272 t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
273 p, m, q, n)
274 }
275
276 m, n = bitpos(1<<2), bitpos(1<<2)
277 p, q = mask(0b100, m), mask(0b001, n)
278 if !(prefixesOverlap(p, m, q, n) && m == n && p == q) {
279 t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
280 p, m, q, n)
281 }
282
283 m, n = bitpos(1<<1), bitpos(1<<1)
284 p, q = mask(0b100, m), mask(0b001, n)
285 if prefixesOverlap(p, m, q, n) ||
286 (m > n && matchPrefix(q, p, m)) ||
287 (m < n && matchPrefix(p, q, n)) ||
288 (m == n && p == q) {
289 t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
290 p, m, q, n)
291 }
292
293
294 r := rand.New(rand.NewSource(123))
295 N := 2000
296 for i := 0; i < N; i++ {
297 m := bitpos(1 << (r.Uint64() % (64 + 1)))
298 n := bitpos(1 << (r.Uint64() % (64 + 1)))
299
300 p := mask(prefix(r.Uint64()), m)
301 q := mask(prefix(r.Uint64()), n)
302
303 lhs := prefixesOverlap(p, m, q, n)
304 rhs := (m > n && matchPrefix(q, p, m)) ||
305 (m < n && matchPrefix(p, q, n)) ||
306 (m == n && p == q)
307
308 if lhs != rhs {
309 t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) != <lemma> got %v. want %v",
310 p, m, q, n, lhs, rhs)
311 }
312 }
313 }
314
View as plain text