-
Notifications
You must be signed in to change notification settings - Fork 0
/
tests.cpp
416 lines (374 loc) · 12.1 KB
/
tests.cpp
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
//
// Created by jens on 09/09/23.
//
// TODO migrate to gtest?
// #include <gtest/gtest.h>
#include <iostream>
#include <array>
#include <map>
#include <functional>
#include <ranges>
#include <algorithm>
#include "lineseg.h"
#include "world.h"
#include "pntalloc.h"
bool expect(pntalloc &, int i, lineseg const &, lineseg const &, std::optional<point>);
// Tests are sorted by increasing integratedness
/** Test basic pathpoint allocator */
[[nodiscard]] bool test_pntalloc();
/** Test line segments and their intersections */
[[nodiscard]] bool test_lineseg();
/** Test splitting line segment into two */
[[nodiscard]] bool test_split_seg();
/** Test inserter into path */
[[nodiscard]] bool test_poly1();
/** Test splitting paths at intersections */
[[nodiscard]] bool test_poly2();
/** Test path iterator - which iterates over segments */
[[nodiscard]] static bool test_path_iter();
/** Test finding branch points (nodes of degree > 2) */
[[nodiscard]] static bool test_branch_points();
/** Test reorganising the path into "proper" paths starting and ending in branch points */
[[nodiscard]] static bool test_path_split();
[[nodiscard]] static bool test_make_poly1();
[[nodiscard]] static bool test_make_poly2();
static world make_world(int);
/** Utility function for test code to access the World's paths */
decltype(world::map_) &test_paths(world &w)
{
return w.map_;
}
/** Utility function for test code to access the World's allocator */
pntalloc &test_allocator(world &w)
{
return w.alloc_;
}
int tests()
{
bool ret = true;
unsigned num{0};
// Tests are to be run in this order
std::array<std::function<bool()>,8> all{test_pntalloc, test_lineseg, test_split_seg, test_poly1,
test_poly2, test_path_iter, test_branch_points, test_path_split};
for( auto testfunc : all ) {
++num;
try {
bool result = testfunc();
if(!result) {
std::cerr << "Test " << num << " failed with no exception raised\n";
return 1;
}
}
catch (BadLineSegment &bad) {
std::cerr << "Test " << num << ": Bad Line Segment exception " << bad.what() << std::endl;
return 1;
}
catch (BadPath &bad) {
std::cerr << "Test " << num << ": BadPath exception " << bad.what() << std::endl;
return 1;
}
}
return ret ? 0 : 1;
}
bool test_pntalloc()
{
pntalloc z;
pathpoint u1 = z.make_point(1,2);
pathpoint u2 = z.make_point(3,4);
pathpoint u3 = z.make_point(1,2);
return u1 == u3 && u1->use_count() == 2 \
&& u2->use_count() == 1 && u2 != u1;
}
bool
test_lineseg()
{
pntalloc u;
// a b define a line y = x/3
// c-f are collinear, on the line y = -2x+14
point a = point(0, 0),
b = point(9,3),
c = point(4,6),
d = point(5,4),
e = point(6,2),
f = point(7,0);
lineseg ab(u, a, b);
bool ret = true;
ret &= expect(u, 1, ab, lineseg(u, c, f), e);
ret &= expect(u, 2, ab, lineseg(u, c, d), std::nullopt);
ret &= expect(u, 3, ab, lineseg(u, c, e), e);
ret &= expect(u, 4, lineseg(u, a, e), lineseg(u, c, e), e);
lineseg gh(u, point(1, 3), point(5, -1));
ret &= expect(u, 5, ab, gh, point(3,1));
ret &= expect(u, 6, gh, ab, point(3,1));
return ret;
}
bool
expect(pntalloc &u, int i, lineseg const &v, lineseg const &w, std::optional<point> expt)
{
bool ret = true;
std::optional<point> z = intersects(v, w);
if(z.has_value() && expt.has_value()) {
if(z.value() != expt.value()) {
std::cerr << "Test " << i << " expected " << expt.value() << " got " << z.value() << std::endl;
ret = false;
}
} else if(z.has_value() && !expt.has_value()) {
std::cerr << "Test " << i << " expected no intersection, got " << z.value() << std::endl;
ret = false;
} else if(!z.has_value() && expt.has_value()) {
std::cerr << "Test " << i << " expected " << expt.value() << " got no intersection" << std::endl;
ret = false;
}
return ret;
}
bool test_split_seg()
{
pntalloc u;
point a(-1,-1), b(2,1), c(3, 0);
lineseg ac(u,a,c);
// Splitting at b should turn a->c into a->b while returning b->c
auto bc{ac.split_at(u,b)};
auto a1{ac.first()}, b1{ac.last()}, b2{bc.first()}, c2{bc.last()};
bool ret = true;
if(*a1 != a || a1->use_count() != 1) {
std::cerr << "split a expected " << a << "[1], got " << a1 << std::endl;
ret = false;
}
if(*b1 != b || b1->use_count() != 2) {
std::cerr << "split b expected " << b << "[2], got " << b1 << std::endl;
ret = false;
}
if(b1 != b2) {
std::cerr << "split end segment 1 doesn't match start of 2: " << b1 << ' ' << b2 << std::endl;
ret = false;
}
if(*c2 != c || c2->use_count() != 1) {
std::cerr << "split c expected " << c << "[1], got " << c2 << std::endl;
ret = false;
}
return ret;
}
bool test_poly1()
{
world w;
pntalloc &u = test_allocator(w);
// World is empty, so should not iterate here
for( auto const &y : w ) {
std::cerr << "Error: World is not empty!\n";
return false;
}
point a = {1, 2},
b = {2,3},
c = {3,1},
d = {4,5},
e = {-1,-2},
f = {-2,-3},
o = {0,0};
// Two line segments: a->b and b->c
w.add_path(path(u, {a, b, c}));
auto q = w.begin(); // point to first segment
++q; // point to second and last segment
// Add c->d
q.insert_after(lineseg(u,c,d));
auto &map = test_paths(w);
if( map[0] != path(u, {a, b, c, d})) {
std::cerr << "Insertion failed: " << map[0] << '\n';
return false;
}
// Add e->f as a separate path
w.add_path(path(u, {e, f}));
// Adding a path may have invalidated the iterator, so we refresh it
q = w.begin(); ++q; ++q; ++q;
// q should now reference the single line segment on the second path
q.insert_after(lineseg(u,f,o));
if(map.size() != 2) {
std::cerr << "Expected two paths; found " << map.size() << '\n';
return false;
}
if(map[0] != path(u, {a, b, c, d}) || map[1] != path(u, {e, f, o})) {
std::cerr << "Error with paths " << map[0] << " or " << map[1] << '\n';
return false;
}
// Finally, an insert at not-the-end - q still points to the *first* entry on path 2
// This is a dummy line segment, not usually useful (or permitted)
q.insert_after(lineseg(u,f,f));
return true;
}
bool test_poly2()
{
world w;
pntalloc &u = test_allocator(w);
w.add_path(path{u, {{-2, 2},{-1,2},{-1,-2},{2,-2},{2,1},{3,2}}});
w.add_path(path{u, {{-3, 1},{3,1}}});
w.split_segments();
// These path comparisons reuse the same points, so only check path structure...
auto &map = test_paths(w);
if( map[0] != path(u, {{-2, 2},
{-1, 2},
{-1, 1},
{-1, -2},
{2, -2},
{2, 1},
{3, 2}}) ) {
std::cerr << "poly2 first path mismatch\n";
std::cerr << map[0] << std::endl;
return false;
}
if( map[1] != path{u, {{-3, 1},{-1,1},{2,1},{3,1}}} ) {
std::cerr << "poly2 second path mismatch\n";
std::cerr << map[1] << std::endl;
return false;
}
// ... so the final test checks the multiplicites;
// however, the previous tests, having visited all the points, have precisely
// doubled all the expected multiplicities because they have the same line segments
std::list<std::pair<point,unsigned int>> expect{{{-2,2},1},{{-1,2},2},{{-1,-2},2},{{2,-2},2},{{2,1},4},{{3,2},1},{{-3,1},1},{{-1,1},4},{{3,1},1}};
bool ret = true;
for( auto const y : u.points() ) {
point p{ static_cast<point>(*y) };
auto z = std::ranges::find_if( expect, [&p](std::pair<point,unsigned int> const &q) { return q.first == p; } );
if(z == expect.end()) {
std::cerr << "poly2: unexpected point " << y << '\n';
ret = false;
} else {
if( 2 * z->second != y->use_count() ) {
std::cerr << "poly2: " << y << " expected " << z->second << " count\n";
ret = false;
}
expect.erase(z);
}
}
if( !expect.empty() ) {
for( const auto &[pt,val] : expect )
std::cerr << "poly2: expected " << point(pt) << '[' << val << "]\n";
ret = false;
}
return ret;
}
bool test_path_iter()
{
world w;
point a = {1, 1},
b = {2,2},
c = {3,4},
d = {5,6};
w.add_path({a, b});
w.add_path({c, d});
std::vector<point> items;
for( auto const &seg : w.segments() ) {
items.push_back(*seg.first());
items.push_back(*seg.last());
}
std::vector<point> expected{a, b, c, d};
return items == expected;
}
bool test_branch_points()
{
world w{make_world(4)};
// Expecting {-1,0},{0,0},{1,1},{-2,1}
std::set<point> const expect{{-1,0},{0,0},{1,1},{-2,1}};
std::set<point> found;
// though not necessarily in that order
for( auto p : w.branch_points() )
found.insert(*p);
return found == expect;
}
bool test_path_split1(std::vector<point> const &at, std::initializer_list<std::initializer_list<point>> y)
{
world w{make_world(1)};
pntalloc &u = test_allocator(w);
// This is the actual code we're testing
w.proper_paths(at);
std::vector<path> expected;
for( auto &x : y )
expected.emplace_back(u, x);
auto &map{test_paths(w)};
if(map.empty()) {
std::cerr << "pathsplit1 no paths returned - not possible!\n";
return false;
}
bool ret = true;
// Check whether expected paths match reality
for( path const &p : map ) {
auto found = std::ranges::find( expected, p );
if( found == expected.end() ) {
std::cerr << "pathsplit1 got unexpected path " << p << std::endl;
ret = false;
} else {
expected.erase(found);
}
}
for( auto const &p : expected ) {
std::cerr << "pathsplit1 expected path " << p << " not found\n";
ret = false;
}
if(!ret)
std::cerr << "pathsplit1 (used " << at << " to split)\n";
return ret;
}
bool test_path_split()
{
std::vector<point> at;
at.push_back(point(-2,1)); // d
// Result should be a single path d->a->b->c->d
if(!test_path_split1(at, {{{-2,1},{-3,2},{-3,0},{-1,0},{-2,1}}}))
return false;
at.clear();
at.emplace_back(1,0);
at.emplace_back(-3,2); // a
at.emplace_back(-1,0); // c
at.emplace_back(1,1);
// Result should be two paths a->b->c and c->d->a
if(!test_path_split1(at, {{{-3,2},{-3,0},{-1,0}},{{-1,0},{-2,1},{-3,2}}}))
return false;
at.clear();
at.emplace_back(-1,0); // c
at.emplace_back(-3,0); // b
// Result should be two paths b->c and c->d->a->b
if(!test_path_split1(at,{{{-3,2},{-3,0}},{{-3,0},{-1,0}},{{-1,0},{-2,1},{-3,2}}}))
return false;
return true;
}
bool test_make_poly1()
{
return true;
}
bool test_make_poly2()
{
return true;
}
/* make_world returns a test setup with k paths (1..4)
* Path 1 is a triangle abcda
* Path 2 is a line defg
* Path 3 is another triangle ihgi
* Path 4 is another path between them, making three polygons
*
* The branching points for k==1 are {d,g}; for k==2, {c,d,g,h}
* The "proper paths" (possibly reversed) derived from the four paths
* for k==2 are:
* 1a. cbad
* 1b. cd
* 2. defg
* 3a. hg
* 3b. gih
* 4. ch
*/
world make_world(int k)
{
world w;
// Triangle one
point c = point(-1, 0), b = point(-3, 0), a = point(-3, 2);
// Triangle two
point h = point(0, 0), i = point(1, 0), g = point(1, 1);
// Connecting line
point d = point(-2, 1), e = point(-1, 2), f = point(0, 2);
w.add_path({a, b, c, d, a});
if(k>=2)
w.add_path({d, e, f, g});
if(k>=3)
w.add_path({i, g, h, i});
if(k == 4) {
w.add_path({c, h});
}
return w;
}