1
2
3
4
5 package abt
6
7 import (
8 "fmt"
9 "strconv"
10 "testing"
11 )
12
13 func makeTree(te *testing.T, x []int32, check bool) (t *T, k int, min, max int32) {
14 t = &T{}
15 k = 0
16 min = int32(0x7fffffff)
17 max = int32(-0x80000000)
18 history := []*T{}
19
20 for _, d := range x {
21 d = d + d
22
23 if check {
24 history = append(history, t.Copy())
25 }
26
27 t.Insert(d, stringer(fmt.Sprintf("%v", d)))
28
29 k++
30 if d < min {
31 min = d
32 }
33 if d > max {
34 max = d
35 }
36
37 if !check {
38 continue
39 }
40
41 for j, old := range history {
42 s, i := old.wellFormed()
43 if s != "" {
44 te.Errorf("Old tree consistency problem %v at k=%d, j=%d, old=\n%v, t=\n%v", s, k, j, old.DebugString(), t.DebugString())
45 return
46 }
47 if i != j {
48 te.Errorf("Wrong tree size %v, expected %v for old %v", i, j, old.DebugString())
49 }
50 }
51 s, i := t.wellFormed()
52 if s != "" {
53 te.Errorf("Tree consistency problem at %v", s)
54 return
55 }
56 if i != k {
57 te.Errorf("Wrong tree size %v, expected %v for %v", i, k, t.DebugString())
58 return
59 }
60 if t.Size() != k {
61 te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), k, t.DebugString())
62 return
63 }
64 }
65 return
66 }
67
68 func applicInsert(te *testing.T, x []int32) {
69 makeTree(te, x, true)
70 }
71
72 func applicFind(te *testing.T, x []int32) {
73 t, _, _, _ := makeTree(te, x, false)
74
75 for _, d := range x {
76 d = d + d
77 s := fmt.Sprintf("%v", d)
78 f := t.Find(d)
79
80
81 if s != fmt.Sprint(f) {
82 te.Errorf("s(%v) != f(%v)", s, f)
83 }
84 }
85 }
86
87 func applicBounds(te *testing.T, x []int32) {
88 t, _, min, max := makeTree(te, x, false)
89 for _, d := range x {
90 d = d + d
91 s := fmt.Sprintf("%v", d)
92
93 kg, g := t.Glb(d + 1)
94 kge, ge := t.GlbEq(d)
95 kl, l := t.Lub(d - 1)
96 kle, le := t.LubEq(d)
97
98
99 if d != kg {
100 te.Errorf("d(%v) != kg(%v)", d, kg)
101 }
102 if d != kl {
103 te.Errorf("d(%v) != kl(%v)", d, kl)
104 }
105 if d != kge {
106 te.Errorf("d(%v) != kge(%v)", d, kge)
107 }
108 if d != kle {
109 te.Errorf("d(%v) != kle(%v)", d, kle)
110 }
111
112 if s != fmt.Sprint(g) {
113 te.Errorf("s(%v) != g(%v)", s, g)
114 }
115 if s != fmt.Sprint(l) {
116 te.Errorf("s(%v) != l(%v)", s, l)
117 }
118 if s != fmt.Sprint(ge) {
119 te.Errorf("s(%v) != ge(%v)", s, ge)
120 }
121 if s != fmt.Sprint(le) {
122 te.Errorf("s(%v) != le(%v)", s, le)
123 }
124 }
125
126 for _, d := range x {
127 d = d + d
128 s := fmt.Sprintf("%v", d)
129 kge, ge := t.GlbEq(d + 1)
130 kle, le := t.LubEq(d - 1)
131 if d != kge {
132 te.Errorf("d(%v) != kge(%v)", d, kge)
133 }
134 if d != kle {
135 te.Errorf("d(%v) != kle(%v)", d, kle)
136 }
137 if s != fmt.Sprint(ge) {
138 te.Errorf("s(%v) != ge(%v)", s, ge)
139 }
140 if s != fmt.Sprint(le) {
141 te.Errorf("s(%v) != le(%v)", s, le)
142 }
143 }
144
145 kg, g := t.Glb(min)
146 kge, ge := t.GlbEq(min - 1)
147 kl, l := t.Lub(max)
148 kle, le := t.LubEq(max + 1)
149 fmin := t.Find(min - 1)
150 fmax := t.Find(max + 1)
151
152 if kg != NOT_KEY32 || kge != NOT_KEY32 || kl != NOT_KEY32 || kle != NOT_KEY32 {
153 te.Errorf("Got non-error-key for missing query")
154 }
155
156 if g != nil || ge != nil || l != nil || le != nil || fmin != nil || fmax != nil {
157 te.Errorf("Got non-error-data for missing query")
158 }
159 }
160
161 func applicDeleteMin(te *testing.T, x []int32) {
162 t, _, _, _ := makeTree(te, x, false)
163 _, size := t.wellFormed()
164 history := []*T{}
165 for !t.IsEmpty() {
166 k, _ := t.Min()
167 history = append(history, t.Copy())
168 kd, _ := t.DeleteMin()
169 if kd != k {
170 te.Errorf("Deleted minimum key %v not equal to minimum %v", kd, k)
171 }
172 for j, old := range history {
173 s, i := old.wellFormed()
174 if s != "" {
175 te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
176 return
177 }
178 if i != len(x)-j {
179 te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
180 return
181 }
182 }
183 size--
184 s, i := t.wellFormed()
185 if s != "" {
186 te.Errorf("Tree consistency problem at %v after DeleteMin, tree=\n%v", s, t.DebugString())
187 return
188 }
189 if i != size {
190 te.Errorf("Wrong tree size %v, expected %v after DeleteMin", i, size)
191 return
192 }
193 if t.Size() != size {
194 te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
195 return
196 }
197 }
198 }
199
200 func applicDeleteMax(te *testing.T, x []int32) {
201 t, _, _, _ := makeTree(te, x, false)
202 _, size := t.wellFormed()
203 history := []*T{}
204
205 for !t.IsEmpty() {
206 k, _ := t.Max()
207 history = append(history, t.Copy())
208 kd, _ := t.DeleteMax()
209 if kd != k {
210 te.Errorf("Deleted maximum key %v not equal to maximum %v", kd, k)
211 }
212
213 for j, old := range history {
214 s, i := old.wellFormed()
215 if s != "" {
216 te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
217 return
218 }
219 if i != len(x)-j {
220 te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
221 return
222 }
223 }
224
225 size--
226 s, i := t.wellFormed()
227 if s != "" {
228 te.Errorf("Tree consistency problem at %v after DeleteMax, tree=\n%v", s, t.DebugString())
229 return
230 }
231 if i != size {
232 te.Errorf("Wrong tree size %v, expected %v after DeleteMax", i, size)
233 return
234 }
235 if t.Size() != size {
236 te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
237 return
238 }
239 }
240 }
241
242 func applicDelete(te *testing.T, x []int32) {
243 t, _, _, _ := makeTree(te, x, false)
244 _, size := t.wellFormed()
245 history := []*T{}
246
247 missing := t.Delete(11)
248 if missing != nil {
249 te.Errorf("Returned a value when there should have been none, %v", missing)
250 return
251 }
252
253 s, i := t.wellFormed()
254 if s != "" {
255 te.Errorf("Tree consistency problem at %v after delete of missing value, tree=\n%v", s, t.DebugString())
256 return
257 }
258 if size != i {
259 te.Errorf("Delete of missing data should not change tree size, expected %d, got %d", size, i)
260 return
261 }
262
263 for _, d := range x {
264 d += d
265 vWant := fmt.Sprintf("%v", d)
266 history = append(history, t.Copy())
267 v := t.Delete(d)
268
269 for j, old := range history {
270 s, i := old.wellFormed()
271 if s != "" {
272 te.Errorf("Tree consistency problem %s at old after DeleteMin, old=\n%stree=\n%v", s, old.DebugString(), t.DebugString())
273 return
274 }
275 if i != len(x)-j {
276 te.Errorf("Wrong old tree size %v, expected %v after DeleteMin, old=\n%vtree\n%v", i, len(x)-j, old.DebugString(), t.DebugString())
277 return
278 }
279 }
280
281 if v.(*sstring).s != vWant {
282 te.Errorf("Deleted %v expected %v but got %v", d, vWant, v)
283 return
284 }
285 size--
286 s, i := t.wellFormed()
287 if s != "" {
288 te.Errorf("Tree consistency problem at %v after Delete %d, tree=\n%v", s, d, t.DebugString())
289 return
290 }
291 if i != size {
292 te.Errorf("Wrong tree size %v, expected %v after Delete", i, size)
293 return
294 }
295 if t.Size() != size {
296 te.Errorf("Wrong t.Size() %v, expected %v for %v", t.Size(), i, t.DebugString())
297 return
298 }
299 }
300
301 }
302
303 func applicIterator(te *testing.T, x []int32) {
304 t, _, _, _ := makeTree(te, x, false)
305 it := t.Iterator()
306 for !it.Done() {
307 k0, d0 := it.Next()
308 k1, d1 := t.DeleteMin()
309 if k0 != k1 || d0 != d1 {
310 te.Errorf("Iterator and deleteMin mismatch, k0, k1, d0, d1 = %v, %v, %v, %v", k0, k1, d0, d1)
311 return
312 }
313 }
314 if t.Size() != 0 {
315 te.Errorf("Iterator ended early, remaining tree = \n%s", t.DebugString())
316 return
317 }
318 }
319
320 func equiv(a, b interface{}) bool {
321 sa, sb := a.(*sstring), b.(*sstring)
322 return *sa == *sb
323 }
324
325 func applicEquals(te *testing.T, x, y []int32) {
326 t, _, _, _ := makeTree(te, x, false)
327 u, _, _, _ := makeTree(te, y, false)
328 if !t.Equiv(t, equiv) {
329 te.Errorf("Equiv failure, t == t, =\n%v", t.DebugString())
330 return
331 }
332 if !t.Equiv(t.Copy(), equiv) {
333 te.Errorf("Equiv failure, t == t.Copy(), =\n%v", t.DebugString())
334 return
335 }
336 if !t.Equiv(u, equiv) {
337 te.Errorf("Equiv failure, t == u, =\n%v", t.DebugString())
338 return
339 }
340 v := t.Copy()
341
342 v.DeleteMax()
343 if t.Equiv(v, equiv) {
344 te.Errorf("!Equiv failure, t != v, =\n%v\nand%v\n", t.DebugString(), v.DebugString())
345 return
346 }
347
348 if v.Equiv(u, equiv) {
349 te.Errorf("!Equiv failure, v != u, =\n%v\nand%v\n", v.DebugString(), u.DebugString())
350 return
351 }
352
353 }
354
355 func tree(x []int32) *T {
356 t := &T{}
357 for _, d := range x {
358 t.Insert(d, stringer(fmt.Sprintf("%v", d)))
359 }
360 return t
361 }
362
363 func treePlus1(x []int32) *T {
364 t := &T{}
365 for _, d := range x {
366 t.Insert(d, stringer(fmt.Sprintf("%v", d+1)))
367 }
368 return t
369 }
370 func TestApplicInsert(t *testing.T) {
371 applicInsert(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
372 applicInsert(t, []int32{1, 2, 3, 4})
373 applicInsert(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
374 applicInsert(t, []int32{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})
375 applicInsert(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
376 applicInsert(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
377 applicInsert(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
378 applicInsert(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
379 }
380
381 func TestApplicFind(t *testing.T) {
382 applicFind(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
383 applicFind(t, []int32{1, 2, 3, 4})
384 applicFind(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
385 applicFind(t, []int32{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})
386 applicFind(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
387 applicFind(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
388 applicFind(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
389 applicFind(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
390 }
391
392 func TestBounds(t *testing.T) {
393 applicBounds(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
394 applicBounds(t, []int32{1, 2, 3, 4})
395 applicBounds(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
396 applicBounds(t, []int32{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})
397 applicBounds(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
398 applicBounds(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
399 applicBounds(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
400 applicBounds(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
401 }
402 func TestDeleteMin(t *testing.T) {
403 applicDeleteMin(t, []int32{1, 2, 3, 4})
404 applicDeleteMin(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
405 applicDeleteMin(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
406 applicDeleteMin(t, []int32{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})
407 applicDeleteMin(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
408 applicDeleteMin(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
409 applicDeleteMin(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
410 applicDeleteMin(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
411 }
412 func TestDeleteMax(t *testing.T) {
413 applicDeleteMax(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
414 applicDeleteMax(t, []int32{1, 2, 3, 4})
415 applicDeleteMax(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
416 applicDeleteMax(t, []int32{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})
417 applicDeleteMax(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
418 applicDeleteMax(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
419 applicDeleteMax(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
420 applicDeleteMax(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
421 }
422 func TestDelete(t *testing.T) {
423 applicDelete(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
424 applicDelete(t, []int32{1, 2, 3, 4})
425 applicDelete(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
426 applicDelete(t, []int32{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})
427 applicDelete(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
428 applicDelete(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
429 applicDelete(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
430 applicDelete(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
431 }
432 func TestIterator(t *testing.T) {
433 applicIterator(t, []int32{1, 2, 3, 4})
434 applicIterator(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9})
435 applicIterator(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
436 applicIterator(t, []int32{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})
437 applicIterator(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
438 applicIterator(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
439 applicIterator(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
440 applicIterator(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
441 }
442 func TestEquals(t *testing.T) {
443 applicEquals(t, []int32{1, 2, 3, 4}, []int32{4, 3, 2, 1})
444
445 applicEquals(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25},
446 []int32{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})
447 applicEquals(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
448 []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
449 applicEquals(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24},
450 []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
451 }
452
453 func first(x, y interface{}) interface{} {
454 return x
455 }
456 func second(x, y interface{}) interface{} {
457 return y
458 }
459 func alwaysNil(x, y interface{}) interface{} {
460 return nil
461 }
462 func smaller(x, y interface{}) interface{} {
463 xi, _ := strconv.Atoi(fmt.Sprint(x))
464 yi, _ := strconv.Atoi(fmt.Sprint(y))
465 if xi < yi {
466 return x
467 }
468 return y
469 }
470 func assert(t *testing.T, expected, got *T, what string) {
471 s, _ := got.wellFormed()
472 if s != "" {
473 t.Errorf("Tree consistency problem %v for 'got' in assert for %s, tree=\n%v", s, what, got.DebugString())
474 return
475 }
476
477 if !expected.Equiv(got, equiv) {
478 t.Errorf("%s fail, expected\n%vgot\n%v\n", what, expected.DebugString(), got.DebugString())
479 }
480 }
481
482 func TestSetOps(t *testing.T) {
483 A := tree([]int32{1, 2, 3, 4})
484 B := tree([]int32{3, 4, 5, 6, 7})
485
486 AIB := tree([]int32{3, 4})
487 ADB := tree([]int32{1, 2})
488 BDA := tree([]int32{5, 6, 7})
489 AUB := tree([]int32{1, 2, 3, 4, 5, 6, 7})
490 AXB := tree([]int32{1, 2, 5, 6, 7})
491
492 aib1 := A.Intersection(B, first)
493 assert(t, AIB, aib1, "aib1")
494 if A.Find(3) != aib1.Find(3) {
495 t.Errorf("Failed aliasing/reuse check, A/aib1")
496 }
497 aib2 := A.Intersection(B, second)
498 assert(t, AIB, aib2, "aib2")
499 if B.Find(3) != aib2.Find(3) {
500 t.Errorf("Failed aliasing/reuse check, B/aib2")
501 }
502 aib3 := B.Intersection(A, first)
503 assert(t, AIB, aib3, "aib3")
504 if A.Find(3) != aib3.Find(3) {
505
506 t.Errorf("Failed aliasing/reuse check, A/aib3")
507 }
508 aib4 := B.Intersection(A, second)
509 assert(t, AIB, aib4, "aib4")
510 if A.Find(3) != aib4.Find(3) {
511 t.Errorf("Failed aliasing/reuse check, A/aib4")
512 }
513
514 aub1 := A.Union(B, first)
515 assert(t, AUB, aub1, "aub1")
516 if B.Find(3) != aub1.Find(3) {
517
518 t.Errorf("Failed aliasing/reuse check, A/aub1")
519 }
520 aub2 := A.Union(B, second)
521 assert(t, AUB, aub2, "aub2")
522 if B.Find(3) != aub2.Find(3) {
523 t.Errorf("Failed aliasing/reuse check, B/aub2")
524 }
525 aub3 := B.Union(A, first)
526 assert(t, AUB, aub3, "aub3")
527 if B.Find(3) != aub3.Find(3) {
528 t.Errorf("Failed aliasing/reuse check, B/aub3")
529 }
530 aub4 := B.Union(A, second)
531 assert(t, AUB, aub4, "aub4")
532 if A.Find(3) != aub4.Find(3) {
533 t.Errorf("Failed aliasing/reuse check, A/aub4")
534 }
535
536 axb1 := A.Union(B, alwaysNil)
537 assert(t, AXB, axb1, "axb1")
538 axb2 := B.Union(A, alwaysNil)
539 assert(t, AXB, axb2, "axb2")
540
541 adb := A.Difference(B, alwaysNil)
542 assert(t, ADB, adb, "adb")
543 bda := B.Difference(A, nil)
544 assert(t, BDA, bda, "bda")
545
546 Ap1 := treePlus1([]int32{1, 2, 3, 4})
547
548 ada1_1 := A.Difference(Ap1, smaller)
549 assert(t, A, ada1_1, "ada1_1")
550 ada1_2 := Ap1.Difference(A, smaller)
551 assert(t, A, ada1_2, "ada1_2")
552
553 }
554
555 type sstring struct {
556 s string
557 }
558
559 func (s *sstring) String() string {
560 return s.s
561 }
562
563 func stringer(s string) interface{} {
564 return &sstring{s}
565 }
566
567
568
569
570
571
572
573 func (t *T) wellFormed() (s string, i int) {
574 if t.root == nil {
575 s = ""
576 i = 0
577 return
578 }
579 return t.root.wellFormedSubtree(nil, -0x80000000, 0x7fffffff)
580 }
581
582
583
584
585
586
587
588 func (t *node32) wellFormedSubtree(parent *node32, keyMin, keyMax int32) (s string, i int) {
589 i = -1
590 s = ""
591
592 if keyMin >= t.key {
593 s = " min >= t.key"
594 return
595 }
596
597 if keyMax <= t.key {
598 s = " max <= t.key"
599 return
600 }
601
602 l := t.left
603 r := t.right
604
605 lh := l.height()
606 rh := r.height()
607 mh := max(lh, rh)
608 th := t.height()
609 dh := lh - rh
610 if dh < 0 {
611 dh = -dh
612 }
613 if dh > 1 {
614 s = fmt.Sprintf(" dh > 1, t=%d", t.key)
615 return
616 }
617
618 if l == nil && r == nil {
619 if th != LEAF_HEIGHT {
620 s = " leaf height wrong"
621 return
622 }
623 }
624
625 if th != mh+1 {
626 s = " th != mh + 1"
627 return
628 }
629
630 if l != nil {
631 if th <= lh {
632 s = " t.height <= l.height"
633 } else if th > 2+lh {
634 s = " t.height > 2+l.height"
635 } else if t.key <= l.key {
636 s = " t.key <= l.key"
637 }
638 if s != "" {
639 return
640 }
641
642 }
643
644 if r != nil {
645 if th <= rh {
646 s = " t.height <= r.height"
647 } else if th > 2+rh {
648 s = " t.height > 2+r.height"
649 } else if t.key >= r.key {
650 s = " t.key >= r.key"
651 }
652 if s != "" {
653 return
654 }
655 }
656
657 ii := 1
658 if l != nil {
659 res, il := l.wellFormedSubtree(t, keyMin, t.key)
660 if res != "" {
661 s = ".L" + res
662 return
663 }
664 ii += il
665 }
666 if r != nil {
667 res, ir := r.wellFormedSubtree(t, t.key, keyMax)
668 if res != "" {
669 s = ".R" + res
670 return
671 }
672 ii += ir
673 }
674 i = ii
675 return
676 }
677
678 func (t *T) DebugString() string {
679 if t.root == nil {
680 return ""
681 }
682 return t.root.DebugString(0)
683 }
684
685
686
687 func (t *node32) DebugString(indent int) string {
688 s := ""
689 if t.left != nil {
690 s = s + t.left.DebugString(indent+1)
691 }
692 for i := 0; i < indent; i++ {
693 s = s + " "
694 }
695 s = s + fmt.Sprintf("%v=%v:%d\n", t.key, t.data, t.height_)
696 if t.right != nil {
697 s = s + t.right.DebugString(indent+1)
698 }
699 return s
700 }
701
View as plain text