1 | //===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "llvm/ADT/IntervalMap.h" |
10 | #include "gtest/gtest.h" |
11 | #include <type_traits> |
12 | |
13 | using namespace llvm; |
14 | |
15 | namespace { |
16 | |
17 | typedef IntervalMap<unsigned, unsigned, 4> UUMap; |
18 | typedef IntervalMap<unsigned, unsigned, 4, |
19 | IntervalMapHalfOpenInfo<unsigned>> UUHalfOpenMap; |
20 | |
21 | // Empty map tests |
22 | TEST(IntervalMapTest, EmptyMap) { |
23 | UUMap::Allocator allocator; |
24 | UUMap map(allocator); |
25 | EXPECT_TRUE(map.empty()); |
26 | |
27 | // Lookup on empty map. |
28 | EXPECT_EQ(0u, map.lookup(0)); |
29 | EXPECT_EQ(7u, map.lookup(0, 7)); |
30 | EXPECT_EQ(0u, map.lookup(~0u-1)); |
31 | EXPECT_EQ(7u, map.lookup(~0u-1, 7)); |
32 | |
33 | // Iterators. |
34 | EXPECT_TRUE(map.begin() == map.begin()); |
35 | EXPECT_TRUE(map.begin() == map.end()); |
36 | EXPECT_TRUE(map.end() == map.end()); |
37 | EXPECT_FALSE(map.begin() != map.begin()); |
38 | EXPECT_FALSE(map.begin() != map.end()); |
39 | EXPECT_FALSE(map.end() != map.end()); |
40 | EXPECT_FALSE(map.begin().valid()); |
41 | EXPECT_FALSE(map.end().valid()); |
42 | UUMap::iterator I = map.begin(); |
43 | EXPECT_FALSE(I.valid()); |
44 | EXPECT_TRUE(I == map.end()); |
45 | |
46 | // Default constructor and cross-constness compares. |
47 | UUMap::const_iterator CI; |
48 | CI = map.begin(); |
49 | EXPECT_TRUE(CI == I); |
50 | UUMap::iterator I2; |
51 | I2 = map.end(); |
52 | EXPECT_TRUE(I2 == CI); |
53 | } |
54 | |
55 | // Test one-element closed ranges. |
56 | TEST(IntervalMapTest, OneElementRanges) { |
57 | UUMap::Allocator allocator; |
58 | UUMap map(allocator); |
59 | map.insert(a: 1, b: 1, y: 1); |
60 | map.insert(a: 2, b: 2, y: 2); |
61 | EXPECT_EQ(1u, map.lookup(1)); |
62 | EXPECT_EQ(2u, map.lookup(2)); |
63 | } |
64 | |
65 | // Single entry map tests |
66 | TEST(IntervalMapTest, SingleEntryMap) { |
67 | UUMap::Allocator allocator; |
68 | UUMap map(allocator); |
69 | map.insert(a: 100, b: 150, y: 1); |
70 | EXPECT_FALSE(map.empty()); |
71 | |
72 | // Lookup around interval. |
73 | EXPECT_EQ(0u, map.lookup(0)); |
74 | EXPECT_EQ(0u, map.lookup(99)); |
75 | EXPECT_EQ(1u, map.lookup(100)); |
76 | EXPECT_EQ(1u, map.lookup(101)); |
77 | EXPECT_EQ(1u, map.lookup(125)); |
78 | EXPECT_EQ(1u, map.lookup(149)); |
79 | EXPECT_EQ(1u, map.lookup(150)); |
80 | EXPECT_EQ(0u, map.lookup(151)); |
81 | EXPECT_EQ(0u, map.lookup(200)); |
82 | EXPECT_EQ(0u, map.lookup(~0u-1)); |
83 | |
84 | // Iterators. |
85 | EXPECT_TRUE(map.begin() == map.begin()); |
86 | EXPECT_FALSE(map.begin() == map.end()); |
87 | EXPECT_TRUE(map.end() == map.end()); |
88 | EXPECT_TRUE(map.begin().valid()); |
89 | EXPECT_FALSE(map.end().valid()); |
90 | |
91 | // Iter deref. |
92 | UUMap::iterator I = map.begin(); |
93 | ASSERT_TRUE(I.valid()); |
94 | EXPECT_EQ(100u, I.start()); |
95 | EXPECT_EQ(150u, I.stop()); |
96 | EXPECT_EQ(1u, I.value()); |
97 | |
98 | // Preincrement. |
99 | ++I; |
100 | EXPECT_FALSE(I.valid()); |
101 | EXPECT_FALSE(I == map.begin()); |
102 | EXPECT_TRUE(I == map.end()); |
103 | |
104 | // PreDecrement. |
105 | --I; |
106 | ASSERT_TRUE(I.valid()); |
107 | EXPECT_EQ(100u, I.start()); |
108 | EXPECT_EQ(150u, I.stop()); |
109 | EXPECT_EQ(1u, I.value()); |
110 | EXPECT_TRUE(I == map.begin()); |
111 | EXPECT_FALSE(I == map.end()); |
112 | |
113 | // Change the value. |
114 | I.setValue(2); |
115 | ASSERT_TRUE(I.valid()); |
116 | EXPECT_EQ(100u, I.start()); |
117 | EXPECT_EQ(150u, I.stop()); |
118 | EXPECT_EQ(2u, I.value()); |
119 | |
120 | // Grow the bounds. |
121 | I.setStart(0); |
122 | ASSERT_TRUE(I.valid()); |
123 | EXPECT_EQ(0u, I.start()); |
124 | EXPECT_EQ(150u, I.stop()); |
125 | EXPECT_EQ(2u, I.value()); |
126 | |
127 | I.setStop(200); |
128 | ASSERT_TRUE(I.valid()); |
129 | EXPECT_EQ(0u, I.start()); |
130 | EXPECT_EQ(200u, I.stop()); |
131 | EXPECT_EQ(2u, I.value()); |
132 | |
133 | // Shrink the bounds. |
134 | I.setStart(150); |
135 | ASSERT_TRUE(I.valid()); |
136 | EXPECT_EQ(150u, I.start()); |
137 | EXPECT_EQ(200u, I.stop()); |
138 | EXPECT_EQ(2u, I.value()); |
139 | |
140 | // Shrink the interval to have a length of 1 |
141 | I.setStop(150); |
142 | ASSERT_TRUE(I.valid()); |
143 | EXPECT_EQ(150u, I.start()); |
144 | EXPECT_EQ(150u, I.stop()); |
145 | EXPECT_EQ(2u, I.value()); |
146 | |
147 | I.setStop(160); |
148 | ASSERT_TRUE(I.valid()); |
149 | EXPECT_EQ(150u, I.start()); |
150 | EXPECT_EQ(160u, I.stop()); |
151 | EXPECT_EQ(2u, I.value()); |
152 | |
153 | // Shrink the interval to have a length of 1 |
154 | I.setStart(160); |
155 | ASSERT_TRUE(I.valid()); |
156 | EXPECT_EQ(160u, I.start()); |
157 | EXPECT_EQ(160u, I.stop()); |
158 | EXPECT_EQ(2u, I.value()); |
159 | |
160 | // Erase last elem. |
161 | I.erase(); |
162 | EXPECT_TRUE(map.empty()); |
163 | EXPECT_EQ(0, std::distance(map.begin(), map.end())); |
164 | } |
165 | |
166 | // Single entry half-open map tests |
167 | TEST(IntervalMapTest, SingleEntryHalfOpenMap) { |
168 | UUHalfOpenMap::Allocator allocator; |
169 | UUHalfOpenMap map(allocator); |
170 | map.insert(a: 100, b: 150, y: 1); |
171 | EXPECT_FALSE(map.empty()); |
172 | |
173 | UUHalfOpenMap::iterator I = map.begin(); |
174 | ASSERT_TRUE(I.valid()); |
175 | |
176 | // Shrink the interval to have a length of 1 |
177 | I.setStart(149); |
178 | ASSERT_TRUE(I.valid()); |
179 | EXPECT_EQ(149u, I.start()); |
180 | EXPECT_EQ(150u, I.stop()); |
181 | EXPECT_EQ(1u, I.value()); |
182 | |
183 | I.setStop(160); |
184 | ASSERT_TRUE(I.valid()); |
185 | EXPECT_EQ(149u, I.start()); |
186 | EXPECT_EQ(160u, I.stop()); |
187 | EXPECT_EQ(1u, I.value()); |
188 | |
189 | // Shrink the interval to have a length of 1 |
190 | I.setStop(150); |
191 | ASSERT_TRUE(I.valid()); |
192 | EXPECT_EQ(149u, I.start()); |
193 | EXPECT_EQ(150u, I.stop()); |
194 | EXPECT_EQ(1u, I.value()); |
195 | } |
196 | |
197 | // Flat coalescing tests. |
198 | TEST(IntervalMapTest, RootCoalescing) { |
199 | UUMap::Allocator allocator; |
200 | UUMap map(allocator); |
201 | map.insert(a: 100, b: 150, y: 1); |
202 | |
203 | // Coalesce from the left. |
204 | map.insert(a: 90, b: 99, y: 1); |
205 | EXPECT_EQ(1, std::distance(map.begin(), map.end())); |
206 | EXPECT_EQ(90u, map.start()); |
207 | EXPECT_EQ(150u, map.stop()); |
208 | |
209 | // Coalesce from the right. |
210 | map.insert(a: 151, b: 200, y: 1); |
211 | EXPECT_EQ(1, std::distance(map.begin(), map.end())); |
212 | EXPECT_EQ(90u, map.start()); |
213 | EXPECT_EQ(200u, map.stop()); |
214 | |
215 | // Non-coalesce from the left. |
216 | map.insert(a: 60, b: 89, y: 2); |
217 | EXPECT_EQ(2, std::distance(map.begin(), map.end())); |
218 | EXPECT_EQ(60u, map.start()); |
219 | EXPECT_EQ(200u, map.stop()); |
220 | EXPECT_EQ(2u, map.lookup(89)); |
221 | EXPECT_EQ(1u, map.lookup(90)); |
222 | |
223 | UUMap::iterator I = map.begin(); |
224 | EXPECT_EQ(60u, I.start()); |
225 | EXPECT_EQ(89u, I.stop()); |
226 | EXPECT_EQ(2u, I.value()); |
227 | ++I; |
228 | EXPECT_EQ(90u, I.start()); |
229 | EXPECT_EQ(200u, I.stop()); |
230 | EXPECT_EQ(1u, I.value()); |
231 | ++I; |
232 | EXPECT_FALSE(I.valid()); |
233 | |
234 | // Non-coalesce from the right. |
235 | map.insert(a: 201, b: 210, y: 2); |
236 | EXPECT_EQ(3, std::distance(map.begin(), map.end())); |
237 | EXPECT_EQ(60u, map.start()); |
238 | EXPECT_EQ(210u, map.stop()); |
239 | EXPECT_EQ(2u, map.lookup(201)); |
240 | EXPECT_EQ(1u, map.lookup(200)); |
241 | |
242 | // Erase from the left. |
243 | map.begin().erase(); |
244 | EXPECT_EQ(2, std::distance(map.begin(), map.end())); |
245 | EXPECT_EQ(90u, map.start()); |
246 | EXPECT_EQ(210u, map.stop()); |
247 | |
248 | // Erase from the right. |
249 | (--map.end()).erase(); |
250 | EXPECT_EQ(1, std::distance(map.begin(), map.end())); |
251 | EXPECT_EQ(90u, map.start()); |
252 | EXPECT_EQ(200u, map.stop()); |
253 | |
254 | // Add non-coalescing, then trigger coalescing with setValue. |
255 | map.insert(a: 80, b: 89, y: 2); |
256 | map.insert(a: 201, b: 210, y: 2); |
257 | EXPECT_EQ(3, std::distance(map.begin(), map.end())); |
258 | (++map.begin()).setValue(2); |
259 | EXPECT_EQ(1, std::distance(map.begin(), map.end())); |
260 | I = map.begin(); |
261 | ASSERT_TRUE(I.valid()); |
262 | EXPECT_EQ(80u, I.start()); |
263 | EXPECT_EQ(210u, I.stop()); |
264 | EXPECT_EQ(2u, I.value()); |
265 | } |
266 | |
267 | // Flat multi-coalescing tests. |
268 | TEST(IntervalMapTest, RootMultiCoalescing) { |
269 | UUMap::Allocator allocator; |
270 | UUMap map(allocator); |
271 | map.insert(a: 140, b: 150, y: 1); |
272 | map.insert(a: 160, b: 170, y: 1); |
273 | map.insert(a: 100, b: 110, y: 1); |
274 | map.insert(a: 120, b: 130, y: 1); |
275 | EXPECT_EQ(4, std::distance(map.begin(), map.end())); |
276 | EXPECT_EQ(100u, map.start()); |
277 | EXPECT_EQ(170u, map.stop()); |
278 | |
279 | // Verify inserts. |
280 | UUMap::iterator I = map.begin(); |
281 | EXPECT_EQ(100u, I.start()); |
282 | EXPECT_EQ(110u, I.stop()); |
283 | ++I; |
284 | EXPECT_EQ(120u, I.start()); |
285 | EXPECT_EQ(130u, I.stop()); |
286 | ++I; |
287 | EXPECT_EQ(140u, I.start()); |
288 | EXPECT_EQ(150u, I.stop()); |
289 | ++I; |
290 | EXPECT_EQ(160u, I.start()); |
291 | EXPECT_EQ(170u, I.stop()); |
292 | ++I; |
293 | EXPECT_FALSE(I.valid()); |
294 | |
295 | // Test advanceTo on flat tree. |
296 | I = map.begin(); |
297 | I.advanceTo(x: 135); |
298 | ASSERT_TRUE(I.valid()); |
299 | EXPECT_EQ(140u, I.start()); |
300 | EXPECT_EQ(150u, I.stop()); |
301 | |
302 | I.advanceTo(x: 145); |
303 | ASSERT_TRUE(I.valid()); |
304 | EXPECT_EQ(140u, I.start()); |
305 | EXPECT_EQ(150u, I.stop()); |
306 | |
307 | I.advanceTo(x: 200); |
308 | EXPECT_FALSE(I.valid()); |
309 | |
310 | I.advanceTo(x: 300); |
311 | EXPECT_FALSE(I.valid()); |
312 | |
313 | // Coalesce left with followers. |
314 | // [100;110] [120;130] [140;150] [160;170] |
315 | map.insert(a: 111, b: 115, y: 1); |
316 | I = map.begin(); |
317 | ASSERT_TRUE(I.valid()); |
318 | EXPECT_EQ(100u, I.start()); |
319 | EXPECT_EQ(115u, I.stop()); |
320 | ++I; |
321 | ASSERT_TRUE(I.valid()); |
322 | EXPECT_EQ(120u, I.start()); |
323 | EXPECT_EQ(130u, I.stop()); |
324 | ++I; |
325 | ASSERT_TRUE(I.valid()); |
326 | EXPECT_EQ(140u, I.start()); |
327 | EXPECT_EQ(150u, I.stop()); |
328 | ++I; |
329 | ASSERT_TRUE(I.valid()); |
330 | EXPECT_EQ(160u, I.start()); |
331 | EXPECT_EQ(170u, I.stop()); |
332 | ++I; |
333 | EXPECT_FALSE(I.valid()); |
334 | |
335 | // Coalesce right with followers. |
336 | // [100;115] [120;130] [140;150] [160;170] |
337 | map.insert(a: 135, b: 139, y: 1); |
338 | I = map.begin(); |
339 | ASSERT_TRUE(I.valid()); |
340 | EXPECT_EQ(100u, I.start()); |
341 | EXPECT_EQ(115u, I.stop()); |
342 | ++I; |
343 | ASSERT_TRUE(I.valid()); |
344 | EXPECT_EQ(120u, I.start()); |
345 | EXPECT_EQ(130u, I.stop()); |
346 | ++I; |
347 | ASSERT_TRUE(I.valid()); |
348 | EXPECT_EQ(135u, I.start()); |
349 | EXPECT_EQ(150u, I.stop()); |
350 | ++I; |
351 | ASSERT_TRUE(I.valid()); |
352 | EXPECT_EQ(160u, I.start()); |
353 | EXPECT_EQ(170u, I.stop()); |
354 | ++I; |
355 | EXPECT_FALSE(I.valid()); |
356 | |
357 | // Coalesce left and right with followers. |
358 | // [100;115] [120;130] [135;150] [160;170] |
359 | map.insert(a: 131, b: 134, y: 1); |
360 | I = map.begin(); |
361 | ASSERT_TRUE(I.valid()); |
362 | EXPECT_EQ(100u, I.start()); |
363 | EXPECT_EQ(115u, I.stop()); |
364 | ++I; |
365 | ASSERT_TRUE(I.valid()); |
366 | EXPECT_EQ(120u, I.start()); |
367 | EXPECT_EQ(150u, I.stop()); |
368 | ++I; |
369 | ASSERT_TRUE(I.valid()); |
370 | EXPECT_EQ(160u, I.start()); |
371 | EXPECT_EQ(170u, I.stop()); |
372 | ++I; |
373 | EXPECT_FALSE(I.valid()); |
374 | |
375 | // Test clear() on non-branched map. |
376 | map.clear(); |
377 | EXPECT_TRUE(map.empty()); |
378 | EXPECT_TRUE(map.begin() == map.end()); |
379 | } |
380 | |
381 | // Branched, non-coalescing tests. |
382 | TEST(IntervalMapTest, Branched) { |
383 | UUMap::Allocator allocator; |
384 | UUMap map(allocator); |
385 | |
386 | // Insert enough intervals to force a branched tree. |
387 | // This creates 9 leaf nodes with 11 elements each, tree height = 1. |
388 | for (unsigned i = 1; i < 100; ++i) { |
389 | map.insert(a: 10*i, b: 10*i+5, y: i); |
390 | EXPECT_EQ(10u, map.start()); |
391 | EXPECT_EQ(10*i+5, map.stop()); |
392 | } |
393 | |
394 | // Tree limits. |
395 | EXPECT_FALSE(map.empty()); |
396 | EXPECT_EQ(10u, map.start()); |
397 | EXPECT_EQ(995u, map.stop()); |
398 | |
399 | // Tree lookup. |
400 | for (unsigned i = 1; i < 100; ++i) { |
401 | EXPECT_EQ(0u, map.lookup(10*i-1)); |
402 | EXPECT_EQ(i, map.lookup(10*i)); |
403 | EXPECT_EQ(i, map.lookup(10*i+5)); |
404 | EXPECT_EQ(0u, map.lookup(10*i+6)); |
405 | } |
406 | |
407 | // Forward iteration. |
408 | UUMap::iterator I = map.begin(); |
409 | for (unsigned i = 1; i < 100; ++i) { |
410 | ASSERT_TRUE(I.valid()); |
411 | EXPECT_EQ(10*i, I.start()); |
412 | EXPECT_EQ(10*i+5, I.stop()); |
413 | EXPECT_EQ(i, *I); |
414 | ++I; |
415 | } |
416 | EXPECT_FALSE(I.valid()); |
417 | EXPECT_TRUE(I == map.end()); |
418 | |
419 | // Backwards iteration. |
420 | for (unsigned i = 99; i; --i) { |
421 | --I; |
422 | ASSERT_TRUE(I.valid()); |
423 | EXPECT_EQ(10*i, I.start()); |
424 | EXPECT_EQ(10*i+5, I.stop()); |
425 | EXPECT_EQ(i, *I); |
426 | } |
427 | EXPECT_TRUE(I == map.begin()); |
428 | |
429 | // Test advanceTo in same node. |
430 | I.advanceTo(x: 20); |
431 | ASSERT_TRUE(I.valid()); |
432 | EXPECT_EQ(20u, I.start()); |
433 | EXPECT_EQ(25u, I.stop()); |
434 | |
435 | // Change value, no coalescing. |
436 | I.setValue(0); |
437 | ASSERT_TRUE(I.valid()); |
438 | EXPECT_EQ(20u, I.start()); |
439 | EXPECT_EQ(25u, I.stop()); |
440 | EXPECT_EQ(0u, I.value()); |
441 | |
442 | // Close the gap right, no coalescing. |
443 | I.setStop(29); |
444 | ASSERT_TRUE(I.valid()); |
445 | EXPECT_EQ(20u, I.start()); |
446 | EXPECT_EQ(29u, I.stop()); |
447 | EXPECT_EQ(0u, I.value()); |
448 | |
449 | // Change value, no coalescing. |
450 | I.setValue(2); |
451 | ASSERT_TRUE(I.valid()); |
452 | EXPECT_EQ(20u, I.start()); |
453 | EXPECT_EQ(29u, I.stop()); |
454 | EXPECT_EQ(2u, I.value()); |
455 | |
456 | // Change value, now coalescing. |
457 | I.setValue(3); |
458 | ASSERT_TRUE(I.valid()); |
459 | EXPECT_EQ(20u, I.start()); |
460 | EXPECT_EQ(35u, I.stop()); |
461 | EXPECT_EQ(3u, I.value()); |
462 | |
463 | // Close the gap, now coalescing. |
464 | I.setValue(4); |
465 | ASSERT_TRUE(I.valid()); |
466 | I.setStop(39); |
467 | ASSERT_TRUE(I.valid()); |
468 | EXPECT_EQ(20u, I.start()); |
469 | EXPECT_EQ(45u, I.stop()); |
470 | EXPECT_EQ(4u, I.value()); |
471 | |
472 | // advanceTo another node. |
473 | I.advanceTo(x: 200); |
474 | ASSERT_TRUE(I.valid()); |
475 | EXPECT_EQ(200u, I.start()); |
476 | EXPECT_EQ(205u, I.stop()); |
477 | |
478 | // Close the gap left, no coalescing. |
479 | I.setStart(196); |
480 | ASSERT_TRUE(I.valid()); |
481 | EXPECT_EQ(196u, I.start()); |
482 | EXPECT_EQ(205u, I.stop()); |
483 | EXPECT_EQ(20u, I.value()); |
484 | |
485 | // Change value, no coalescing. |
486 | I.setValue(0); |
487 | ASSERT_TRUE(I.valid()); |
488 | EXPECT_EQ(196u, I.start()); |
489 | EXPECT_EQ(205u, I.stop()); |
490 | EXPECT_EQ(0u, I.value()); |
491 | |
492 | // Change value, now coalescing. |
493 | I.setValue(19); |
494 | ASSERT_TRUE(I.valid()); |
495 | EXPECT_EQ(190u, I.start()); |
496 | EXPECT_EQ(205u, I.stop()); |
497 | EXPECT_EQ(19u, I.value()); |
498 | |
499 | // Close the gap, now coalescing. |
500 | I.setValue(18); |
501 | ASSERT_TRUE(I.valid()); |
502 | I.setStart(186); |
503 | ASSERT_TRUE(I.valid()); |
504 | EXPECT_EQ(180u, I.start()); |
505 | EXPECT_EQ(205u, I.stop()); |
506 | EXPECT_EQ(18u, I.value()); |
507 | |
508 | // Erase from the front. |
509 | I = map.begin(); |
510 | for (unsigned i = 0; i != 20; ++i) { |
511 | I.erase(); |
512 | EXPECT_TRUE(I == map.begin()); |
513 | EXPECT_FALSE(map.empty()); |
514 | EXPECT_EQ(I.start(), map.start()); |
515 | EXPECT_EQ(995u, map.stop()); |
516 | } |
517 | |
518 | // Test clear() on branched map. |
519 | map.clear(); |
520 | EXPECT_TRUE(map.empty()); |
521 | EXPECT_TRUE(map.begin() == map.end()); |
522 | } |
523 | |
524 | // Branched, high, non-coalescing tests. |
525 | TEST(IntervalMapTest, Branched2) { |
526 | UUMap::Allocator allocator; |
527 | UUMap map(allocator); |
528 | |
529 | // Insert enough intervals to force a height >= 2 tree. |
530 | for (unsigned i = 1; i < 1000; ++i) |
531 | map.insert(a: 10*i, b: 10*i+5, y: i); |
532 | |
533 | // Tree limits. |
534 | EXPECT_FALSE(map.empty()); |
535 | EXPECT_EQ(10u, map.start()); |
536 | EXPECT_EQ(9995u, map.stop()); |
537 | |
538 | // Tree lookup. |
539 | for (unsigned i = 1; i < 1000; ++i) { |
540 | EXPECT_EQ(0u, map.lookup(10*i-1)); |
541 | EXPECT_EQ(i, map.lookup(10*i)); |
542 | EXPECT_EQ(i, map.lookup(10*i+5)); |
543 | EXPECT_EQ(0u, map.lookup(10*i+6)); |
544 | } |
545 | |
546 | // Forward iteration. |
547 | UUMap::iterator I = map.begin(); |
548 | for (unsigned i = 1; i < 1000; ++i) { |
549 | ASSERT_TRUE(I.valid()); |
550 | EXPECT_EQ(10*i, I.start()); |
551 | EXPECT_EQ(10*i+5, I.stop()); |
552 | EXPECT_EQ(i, *I); |
553 | ++I; |
554 | } |
555 | EXPECT_FALSE(I.valid()); |
556 | EXPECT_TRUE(I == map.end()); |
557 | |
558 | // Backwards iteration. |
559 | for (unsigned i = 999; i; --i) { |
560 | --I; |
561 | ASSERT_TRUE(I.valid()); |
562 | EXPECT_EQ(10*i, I.start()); |
563 | EXPECT_EQ(10*i+5, I.stop()); |
564 | EXPECT_EQ(i, *I); |
565 | } |
566 | EXPECT_TRUE(I == map.begin()); |
567 | |
568 | // Test advanceTo in same node. |
569 | I.advanceTo(x: 20); |
570 | ASSERT_TRUE(I.valid()); |
571 | EXPECT_EQ(20u, I.start()); |
572 | EXPECT_EQ(25u, I.stop()); |
573 | |
574 | // advanceTo sibling leaf node. |
575 | I.advanceTo(x: 200); |
576 | ASSERT_TRUE(I.valid()); |
577 | EXPECT_EQ(200u, I.start()); |
578 | EXPECT_EQ(205u, I.stop()); |
579 | |
580 | // advanceTo further. |
581 | I.advanceTo(x: 2000); |
582 | ASSERT_TRUE(I.valid()); |
583 | EXPECT_EQ(2000u, I.start()); |
584 | EXPECT_EQ(2005u, I.stop()); |
585 | |
586 | // advanceTo beyond end() |
587 | I.advanceTo(x: 20000); |
588 | EXPECT_FALSE(I.valid()); |
589 | |
590 | // end().advanceTo() is valid as long as x > map.stop() |
591 | I.advanceTo(x: 30000); |
592 | EXPECT_FALSE(I.valid()); |
593 | |
594 | // Test clear() on branched map. |
595 | map.clear(); |
596 | EXPECT_TRUE(map.empty()); |
597 | EXPECT_TRUE(map.begin() == map.end()); |
598 | } |
599 | |
600 | // Random insertions, coalescing to a single interval. |
601 | TEST(IntervalMapTest, RandomCoalescing) { |
602 | UUMap::Allocator allocator; |
603 | UUMap map(allocator); |
604 | |
605 | // This is a poor PRNG with maximal period: |
606 | // x_n = 5 x_{n-1} + 1 mod 2^N |
607 | |
608 | unsigned x = 100; |
609 | for (unsigned i = 0; i != 4096; ++i) { |
610 | map.insert(a: 10*x, b: 10*x+9, y: 1); |
611 | EXPECT_GE(10*x, map.start()); |
612 | EXPECT_LE(10*x+9, map.stop()); |
613 | x = (5*x+1)%4096; |
614 | } |
615 | |
616 | // Map should be fully coalesced after that exercise. |
617 | EXPECT_FALSE(map.empty()); |
618 | EXPECT_EQ(0u, map.start()); |
619 | EXPECT_EQ(40959u, map.stop()); |
620 | EXPECT_EQ(1, std::distance(map.begin(), map.end())); |
621 | |
622 | } |
623 | |
624 | static void setupOverlaps(UUMap &M) { |
625 | M.insert(a: 10, b: 20, y: 0); |
626 | M.insert(a: 30, b: 40, y: 0); |
627 | M.insert(a: 50, b: 60, y: 0); |
628 | // Add extra nodes to force allocations. |
629 | for (int i = 70; i < 100; i += 2) |
630 | M.insert(a: i, b: i + 1, y: i); |
631 | } |
632 | |
633 | static void checkOverlaps(UUMap &M) { |
634 | EXPECT_FALSE(M.overlaps(0, 9)); |
635 | EXPECT_TRUE(M.overlaps(0, 10)); |
636 | EXPECT_TRUE(M.overlaps(0, 15)); |
637 | EXPECT_TRUE(M.overlaps(0, 25)); |
638 | EXPECT_TRUE(M.overlaps(0, 45)); |
639 | EXPECT_TRUE(M.overlaps(10, 45)); |
640 | EXPECT_TRUE(M.overlaps(30, 45)); |
641 | EXPECT_TRUE(M.overlaps(35, 36)); |
642 | EXPECT_TRUE(M.overlaps(40, 45)); |
643 | EXPECT_FALSE(M.overlaps(45, 45)); |
644 | EXPECT_TRUE(M.overlaps(60, 60)); |
645 | EXPECT_TRUE(M.overlaps(60, 66)); |
646 | EXPECT_FALSE(M.overlaps(66, 66)); |
647 | } |
648 | |
649 | TEST(IntervalMapTest, Copy) { |
650 | // Test that copy assignment and initialization works. |
651 | UUHalfOpenMap::Allocator Allocator; |
652 | UUMap Src(Allocator); |
653 | setupOverlaps(Src); |
654 | |
655 | UUMap CopyAssignmentDst(Allocator); |
656 | CopyAssignmentDst = Src; |
657 | |
658 | UUMap CopyInitDst(Src); |
659 | |
660 | checkOverlaps(M&: Src); |
661 | Src.clear(); |
662 | |
663 | checkOverlaps(M&: CopyAssignmentDst); |
664 | checkOverlaps(M&: CopyInitDst); |
665 | } |
666 | |
667 | TEST(IntervalMapTest, Move) { |
668 | // Test that move assignment and initialization works. |
669 | UUHalfOpenMap::Allocator Allocator; |
670 | // Double check that MoveAssignmentDst owns all its data by moving from an |
671 | // object that is destroyed before we call checkOverlaps. |
672 | UUMap MoveAssignmentDst(Allocator); |
673 | { |
674 | UUMap Src(Allocator); |
675 | setupOverlaps(Src); |
676 | MoveAssignmentDst = std::move(Src); |
677 | } |
678 | checkOverlaps(M&: MoveAssignmentDst); |
679 | |
680 | UUMap MoveInitSrc(Allocator); |
681 | setupOverlaps(MoveInitSrc); |
682 | UUMap MoveInitDst(std::move(MoveInitSrc)); |
683 | checkOverlaps(M&: MoveInitDst); |
684 | } |
685 | |
686 | TEST(IntervalMapTest, Overlaps) { |
687 | UUMap::Allocator allocator; |
688 | UUMap map(allocator); |
689 | setupOverlaps(map); |
690 | checkOverlaps(M&: map); |
691 | } |
692 | |
693 | TEST(IntervalMapTest, OverlapsHalfOpen) { |
694 | UUHalfOpenMap::Allocator allocator; |
695 | UUHalfOpenMap map(allocator); |
696 | map.insert(a: 10, b: 20, y: 0); |
697 | map.insert(a: 30, b: 40, y: 0); |
698 | map.insert(a: 50, b: 60, y: 0); |
699 | |
700 | EXPECT_FALSE(map.overlaps(0, 9)); |
701 | EXPECT_FALSE(map.overlaps(0, 10)); |
702 | EXPECT_TRUE(map.overlaps(0, 15)); |
703 | EXPECT_TRUE(map.overlaps(0, 25)); |
704 | EXPECT_TRUE(map.overlaps(0, 45)); |
705 | EXPECT_TRUE(map.overlaps(10, 45)); |
706 | EXPECT_TRUE(map.overlaps(30, 45)); |
707 | EXPECT_TRUE(map.overlaps(35, 36)); |
708 | EXPECT_FALSE(map.overlaps(40, 45)); |
709 | EXPECT_FALSE(map.overlaps(45, 46)); |
710 | EXPECT_FALSE(map.overlaps(60, 61)); |
711 | EXPECT_FALSE(map.overlaps(60, 66)); |
712 | EXPECT_FALSE(map.overlaps(66, 67)); |
713 | } |
714 | |
715 | TEST(IntervalMapOverlapsTest, SmallMaps) { |
716 | typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps; |
717 | UUMap::Allocator allocator; |
718 | UUMap mapA(allocator); |
719 | UUMap mapB(allocator); |
720 | |
721 | // empty, empty. |
722 | EXPECT_FALSE(UUOverlaps(mapA, mapB).valid()); |
723 | |
724 | mapA.insert(a: 1, b: 2, y: 3); |
725 | |
726 | // full, empty |
727 | EXPECT_FALSE(UUOverlaps(mapA, mapB).valid()); |
728 | // empty, full |
729 | EXPECT_FALSE(UUOverlaps(mapB, mapA).valid()); |
730 | |
731 | mapB.insert(a: 3, b: 4, y: 5); |
732 | |
733 | // full, full, non-overlapping |
734 | EXPECT_FALSE(UUOverlaps(mapA, mapB).valid()); |
735 | EXPECT_FALSE(UUOverlaps(mapB, mapA).valid()); |
736 | |
737 | // Add an overlapping segment. |
738 | mapA.insert(a: 4, b: 5, y: 6); |
739 | |
740 | UUOverlaps AB(mapA, mapB); |
741 | ASSERT_TRUE(AB.valid()); |
742 | EXPECT_EQ(4u, AB.a().start()); |
743 | EXPECT_EQ(3u, AB.b().start()); |
744 | ++AB; |
745 | EXPECT_FALSE(AB.valid()); |
746 | |
747 | UUOverlaps BA(mapB, mapA); |
748 | ASSERT_TRUE(BA.valid()); |
749 | EXPECT_EQ(3u, BA.a().start()); |
750 | EXPECT_EQ(4u, BA.b().start()); |
751 | // advance past end. |
752 | BA.advanceTo(x: 6); |
753 | EXPECT_FALSE(BA.valid()); |
754 | // advance an invalid iterator. |
755 | BA.advanceTo(x: 7); |
756 | EXPECT_FALSE(BA.valid()); |
757 | } |
758 | |
759 | TEST(IntervalMapOverlapsTest, BigMaps) { |
760 | typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps; |
761 | UUMap::Allocator allocator; |
762 | UUMap mapA(allocator); |
763 | UUMap mapB(allocator); |
764 | |
765 | // [0;4] [10;14] [20;24] ... |
766 | for (unsigned n = 0; n != 100; ++n) |
767 | mapA.insert(a: 10*n, b: 10*n+4, y: n); |
768 | |
769 | // [5;6] [15;16] [25;26] ... |
770 | for (unsigned n = 10; n != 20; ++n) |
771 | mapB.insert(a: 10*n+5, b: 10*n+6, y: n); |
772 | |
773 | // [208;209] [218;219] ... |
774 | for (unsigned n = 20; n != 30; ++n) |
775 | mapB.insert(a: 10*n+8, b: 10*n+9, y: n); |
776 | |
777 | // insert some overlapping segments. |
778 | mapB.insert(a: 400, b: 400, y: 400); |
779 | mapB.insert(a: 401, b: 401, y: 401); |
780 | mapB.insert(a: 402, b: 500, y: 402); |
781 | mapB.insert(a: 600, b: 601, y: 402); |
782 | |
783 | UUOverlaps AB(mapA, mapB); |
784 | ASSERT_TRUE(AB.valid()); |
785 | EXPECT_EQ(400u, AB.a().start()); |
786 | EXPECT_EQ(400u, AB.b().start()); |
787 | ++AB; |
788 | ASSERT_TRUE(AB.valid()); |
789 | EXPECT_EQ(400u, AB.a().start()); |
790 | EXPECT_EQ(401u, AB.b().start()); |
791 | ++AB; |
792 | ASSERT_TRUE(AB.valid()); |
793 | EXPECT_EQ(400u, AB.a().start()); |
794 | EXPECT_EQ(402u, AB.b().start()); |
795 | ++AB; |
796 | ASSERT_TRUE(AB.valid()); |
797 | EXPECT_EQ(410u, AB.a().start()); |
798 | EXPECT_EQ(402u, AB.b().start()); |
799 | ++AB; |
800 | ASSERT_TRUE(AB.valid()); |
801 | EXPECT_EQ(420u, AB.a().start()); |
802 | EXPECT_EQ(402u, AB.b().start()); |
803 | AB.skipB(); |
804 | ASSERT_TRUE(AB.valid()); |
805 | EXPECT_EQ(600u, AB.a().start()); |
806 | EXPECT_EQ(600u, AB.b().start()); |
807 | ++AB; |
808 | EXPECT_FALSE(AB.valid()); |
809 | |
810 | // Test advanceTo. |
811 | UUOverlaps AB2(mapA, mapB); |
812 | AB2.advanceTo(x: 410); |
813 | ASSERT_TRUE(AB2.valid()); |
814 | EXPECT_EQ(410u, AB2.a().start()); |
815 | EXPECT_EQ(402u, AB2.b().start()); |
816 | |
817 | // It is valid to advanceTo with any monotonic sequence. |
818 | AB2.advanceTo(x: 411); |
819 | ASSERT_TRUE(AB2.valid()); |
820 | EXPECT_EQ(410u, AB2.a().start()); |
821 | EXPECT_EQ(402u, AB2.b().start()); |
822 | |
823 | // Check reversed maps. |
824 | UUOverlaps BA(mapB, mapA); |
825 | ASSERT_TRUE(BA.valid()); |
826 | EXPECT_EQ(400u, BA.b().start()); |
827 | EXPECT_EQ(400u, BA.a().start()); |
828 | ++BA; |
829 | ASSERT_TRUE(BA.valid()); |
830 | EXPECT_EQ(400u, BA.b().start()); |
831 | EXPECT_EQ(401u, BA.a().start()); |
832 | ++BA; |
833 | ASSERT_TRUE(BA.valid()); |
834 | EXPECT_EQ(400u, BA.b().start()); |
835 | EXPECT_EQ(402u, BA.a().start()); |
836 | ++BA; |
837 | ASSERT_TRUE(BA.valid()); |
838 | EXPECT_EQ(410u, BA.b().start()); |
839 | EXPECT_EQ(402u, BA.a().start()); |
840 | ++BA; |
841 | ASSERT_TRUE(BA.valid()); |
842 | EXPECT_EQ(420u, BA.b().start()); |
843 | EXPECT_EQ(402u, BA.a().start()); |
844 | BA.skipA(); |
845 | ASSERT_TRUE(BA.valid()); |
846 | EXPECT_EQ(600u, BA.b().start()); |
847 | EXPECT_EQ(600u, BA.a().start()); |
848 | ++BA; |
849 | EXPECT_FALSE(BA.valid()); |
850 | |
851 | // Test advanceTo. |
852 | UUOverlaps BA2(mapB, mapA); |
853 | BA2.advanceTo(x: 410); |
854 | ASSERT_TRUE(BA2.valid()); |
855 | EXPECT_EQ(410u, BA2.b().start()); |
856 | EXPECT_EQ(402u, BA2.a().start()); |
857 | |
858 | BA2.advanceTo(x: 411); |
859 | ASSERT_TRUE(BA2.valid()); |
860 | EXPECT_EQ(410u, BA2.b().start()); |
861 | EXPECT_EQ(402u, BA2.a().start()); |
862 | } |
863 | |
864 | } // namespace |
865 | |