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
|
#include <cassert>
#include <iostream>
#include <support/space.h>
using namespace wasm;
using Span = DisjointSpans::Span;
int main() {
// No spans
{
DisjointSpans root;
// Nothing in root
assert(!root.checkOverlap(Span{0, 100}));
}
// One span
{
DisjointSpans root;
root.add(Span{0, 100});
// It is there
assert(root.checkOverlap(Span{0, 100}));
}
{
DisjointSpans root;
root.add(Span{40, 60});
// Exact match
assert(root.checkOverlap(Span{40, 60}));
// No overlap
assert(!root.checkOverlap(Span{20, 30}));
// Touching, but no overlap
assert(!root.checkOverlap(Span{20, 40}));
// Overlap
assert(root.checkOverlap(Span{20, 41}));
assert(root.checkOverlap(Span{40, 41}));
// Internal
assert(root.checkOverlap(Span{45, 50}));
// Touches other side
assert(root.checkOverlap(Span{45, 60}));
// Overlaps on other side
assert(root.checkOverlap(Span{45, 70}));
// Just inside.
assert(root.checkOverlap(Span{59, 60}));
// Just outside
assert(!root.checkOverlap(Span{60, 61}));
// Totally outside
assert(!root.checkOverlap(Span{70, 80}));
}
// Two spans, different subtrees
{
DisjointSpans root;
root.add(Span{30, 40});
root.add(Span{60, 70});
assert(!root.checkOverlap(Span{10, 20}));
assert(!root.checkOverlap(Span{10, 30}));
assert(root.checkOverlap(Span{10, 40}));
assert(root.checkOverlap(Span{35, 40}));
assert(!root.checkOverlap(Span{40, 60}));
assert(!root.checkOverlap(Span{45, 55}));
assert(root.checkOverlap(Span{50, 61}));
assert(root.checkOverlap(Span{50, 100}));
assert(root.checkOverlap(Span{60, 70}));
assert(root.checkOverlap(Span{60, 61}));
assert(!root.checkOverlap(Span{70, 80}));
assert(!root.checkOverlap(Span{70, 100}));
}
// Two spans, same subtree
{
DisjointSpans root;
root.add(Span{30, 40});
root.add(Span{40, 45});
assert(!root.checkOverlap(Span{10, 20}));
assert(!root.checkOverlap(Span{10, 30}));
assert(root.checkOverlap(Span{10, 40}));
assert(root.checkOverlap(Span{35, 40}));
assert(root.checkOverlap(Span{40, 41}));
assert(root.checkOverlap(Span{35, 45}));
assert(!root.checkOverlap(Span{45, 100}));
}
// "Pixels"
{
const int N = 40;
for (int i = 0; i < N; i++) {
DisjointSpans root;
for (int j = 0; j < N; j++) {
// add all pixels but the i-th
if (j != i) {
root.add(Span{j, j + 1});
}
}
for (int j = 0; j < N; j++) {
if (j != i) {
assert(root.checkOverlap(Span{j, j + 1}));
} else {
assert(!root.checkOverlap(Span{j, j + 1}));
}
}
assert(root.checkOverlap(Span{10, N + 10}));
assert(!root.checkOverlap(Span{N + 10, N + 20}));
}
}
// Large numbers.
{
DisjointSpans root;
assert(!root.checkOverlap(Span{2948, 2949}));
root.add(Span{2948, 2949});
assert(root.checkOverlap(Span{2948, 2949}));
assert(root.checkOverlap(Span{2940, 2949}));
assert(root.checkOverlap(Span{2948, 2959}));
assert(root.checkOverlap(Span{0, 18766}));
assert(!root.checkOverlap(Span{2000, 2001}));
assert(!root.checkOverlap(Span{3000, 3001}));
}
std::cout << "success.\n";
}
|
