]>
git.proxmox.com Git - ceph.git/blob - ceph/src/test/common/test_interval_set.cc
1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2015 Mirantis, Inc.
8 * Author: Igor Fedotov <ifedotov@mirantis.com>
10 * This is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Lesser General Public
12 * License version 2.1, as published by the Free Software
13 * Foundation. See file COPYING.
17 #include <gtest/gtest.h>
18 #include <boost/container/flat_map.hpp>
19 #include "include/interval_set.h"
20 #include "include/btree_map.h"
24 typedef uint64_t IntervalValueType
;
26 template<typename T
> // tuple<type to test on, test array size>
27 class IntervalSetTest
: public ::testing::Test
{
33 typedef ::testing::Types
<
34 interval_set
<IntervalValueType
>,
35 interval_set
<IntervalValueType
,
36 btree::btree_map
<IntervalValueType
,IntervalValueType
>>,
37 interval_set
<IntervalValueType
,
38 boost::container::flat_map
<IntervalValueType
,IntervalValueType
>>
41 TYPED_TEST_CASE(IntervalSetTest
, IntervalSetTypes
);
43 TYPED_TEST(IntervalSetTest
, compare
) {
44 typedef typename
TestFixture::ISet ISet
;
46 ASSERT_TRUE(iset1
== iset1
);
47 ASSERT_TRUE(iset1
== iset2
);
50 ASSERT_FALSE(iset1
== iset2
);
53 ASSERT_TRUE(iset1
== iset2
);
57 ASSERT_FALSE(iset1
== iset2
);
63 ASSERT_TRUE(iset1
== iset2
);
65 iset1
.insert(100, 10);
67 ASSERT_FALSE(iset1
== iset2
);
69 ASSERT_TRUE(iset1
== iset2
);
71 iset1
.insert(200, 10);
73 ASSERT_FALSE(iset1
== iset2
);
76 ASSERT_FALSE(iset1
== iset2
);
78 ASSERT_TRUE(iset1
== iset2
);
81 ASSERT_FALSE(iset1
== iset2
);
83 ASSERT_TRUE(iset1
== iset2
);
86 TYPED_TEST(IntervalSetTest
, contains
) {
87 typedef typename
TestFixture::ISet ISet
;
89 ASSERT_FALSE(iset1
.contains( 1 ));
90 ASSERT_FALSE(iset1
.contains( 0, 1 ));
93 ASSERT_TRUE(iset1
.contains( 1 ));
94 ASSERT_FALSE(iset1
.contains( 0 ));
95 ASSERT_FALSE(iset1
.contains( 2 ));
96 ASSERT_FALSE(iset1
.contains( 0, 1 ));
97 ASSERT_FALSE(iset1
.contains( 0, 2 ));
98 ASSERT_TRUE(iset1
.contains( 1, 1 ));
99 ASSERT_FALSE(iset1
.contains( 1, 2 ));
102 ASSERT_TRUE(iset1
.contains( 1 ));
103 ASSERT_FALSE(iset1
.contains( 0 ));
104 ASSERT_TRUE(iset1
.contains( 2 ));
105 ASSERT_FALSE(iset1
.contains( 0, 1 ));
106 ASSERT_FALSE(iset1
.contains( 0, 2 ));
107 ASSERT_TRUE(iset1
.contains( 1, 1 ));
108 ASSERT_TRUE(iset1
.contains( 1, 2 ));
109 ASSERT_TRUE(iset1
.contains( 1, 3 ));
110 ASSERT_TRUE(iset1
.contains( 1, 4 ));
111 ASSERT_FALSE(iset1
.contains( 1, 5 ));
112 ASSERT_TRUE(iset1
.contains( 2, 1 ));
113 ASSERT_TRUE(iset1
.contains( 2, 2 ));
114 ASSERT_TRUE(iset1
.contains( 2, 3 ));
115 ASSERT_FALSE(iset1
.contains( 2, 4 ));
116 ASSERT_TRUE(iset1
.contains( 3, 2 ));
117 ASSERT_TRUE(iset1
.contains( 4, 1 ));
118 ASSERT_FALSE(iset1
.contains( 4, 2 ));
120 iset1
.insert(10, 10);
121 ASSERT_TRUE(iset1
.contains( 1, 4 ));
122 ASSERT_FALSE(iset1
.contains( 1, 5 ));
123 ASSERT_TRUE(iset1
.contains( 2, 2 ));
124 ASSERT_FALSE(iset1
.contains( 2, 4 ));
126 ASSERT_FALSE(iset1
.contains( 1, 10 ));
127 ASSERT_FALSE(iset1
.contains( 9, 1 ));
128 ASSERT_FALSE(iset1
.contains( 9 ));
129 ASSERT_FALSE(iset1
.contains( 9, 11 ));
130 ASSERT_TRUE(iset1
.contains( 10, 1 ));
131 ASSERT_TRUE(iset1
.contains( 11, 9 ));
132 ASSERT_TRUE(iset1
.contains( 11, 2 ));
133 ASSERT_TRUE(iset1
.contains( 18, 2 ));
134 ASSERT_TRUE(iset1
.contains( 18, 2 ));
135 ASSERT_TRUE(iset1
.contains( 10 ));
136 ASSERT_TRUE(iset1
.contains( 19 ));
137 ASSERT_FALSE(iset1
.contains( 20 ));
138 ASSERT_FALSE(iset1
.contains( 21 ));
140 ASSERT_FALSE(iset1
.contains( 11, 11 ));
141 ASSERT_FALSE(iset1
.contains( 18, 9 ));
144 ASSERT_FALSE(iset1
.contains( 1 ));
145 ASSERT_FALSE(iset1
.contains( 0 ));
146 ASSERT_FALSE(iset1
.contains( 2 ));
147 ASSERT_FALSE(iset1
.contains( 0, 1 ));
148 ASSERT_FALSE(iset1
.contains( 0, 2 ));
149 ASSERT_FALSE(iset1
.contains( 1, 1 ));
150 ASSERT_FALSE(iset1
.contains( 10, 2 ));
153 TYPED_TEST(IntervalSetTest
, intersects
) {
154 typedef typename
TestFixture::ISet ISet
;
156 ASSERT_FALSE(iset1
.intersects( 1, 1 ));
157 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
158 ASSERT_FALSE(iset1
.intersects( 0, 10 ));
161 ASSERT_TRUE(iset1
.intersects( 1, 1 ));
162 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
163 ASSERT_FALSE(iset1
.intersects( 2, 1 ));
164 ASSERT_TRUE(iset1
.intersects( 0, 2 ));
165 ASSERT_TRUE(iset1
.intersects( 0, 20 ));
166 ASSERT_TRUE(iset1
.intersects( 1, 2 ));
167 ASSERT_TRUE(iset1
.intersects( 1, 20 ));
170 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
171 ASSERT_TRUE(iset1
.intersects( 0, 2 ));
172 ASSERT_TRUE(iset1
.intersects( 0, 200 ));
173 ASSERT_TRUE(iset1
.intersects( 1, 1 ));
174 ASSERT_TRUE(iset1
.intersects( 1, 4 ));
175 ASSERT_TRUE(iset1
.intersects( 1, 5 ));
176 ASSERT_TRUE(iset1
.intersects( 2, 1 ));
177 ASSERT_TRUE(iset1
.intersects( 2, 2 ));
178 ASSERT_TRUE(iset1
.intersects( 2, 3 ));
179 ASSERT_TRUE(iset1
.intersects( 2, 4 ));
180 ASSERT_TRUE(iset1
.intersects( 3, 2 ));
181 ASSERT_TRUE(iset1
.intersects( 4, 1 ));
182 ASSERT_TRUE(iset1
.intersects( 4, 2 ));
183 ASSERT_FALSE(iset1
.intersects( 5, 2 ));
185 iset1
.insert(10, 10);
186 ASSERT_TRUE(iset1
.intersects( 1, 4 ));
187 ASSERT_TRUE(iset1
.intersects( 1, 5 ));
188 ASSERT_TRUE(iset1
.intersects( 1, 10 ));
189 ASSERT_TRUE(iset1
.intersects( 2, 2 ));
190 ASSERT_TRUE(iset1
.intersects( 2, 4 ));
191 ASSERT_FALSE(iset1
.intersects( 5, 1 ));
192 ASSERT_FALSE(iset1
.intersects( 5, 2 ));
193 ASSERT_FALSE(iset1
.intersects( 5, 5 ));
194 ASSERT_TRUE(iset1
.intersects( 5, 12 ));
195 ASSERT_TRUE(iset1
.intersects( 5, 20 ));
197 ASSERT_FALSE(iset1
.intersects( 9, 1 ));
198 ASSERT_TRUE(iset1
.intersects( 9, 2 ));
200 ASSERT_TRUE(iset1
.intersects( 9, 11 ));
201 ASSERT_TRUE(iset1
.intersects( 10, 1 ));
202 ASSERT_TRUE(iset1
.intersects( 11, 9 ));
203 ASSERT_TRUE(iset1
.intersects( 11, 2 ));
204 ASSERT_TRUE(iset1
.intersects( 11, 11 ));
205 ASSERT_TRUE(iset1
.intersects( 18, 2 ));
206 ASSERT_TRUE(iset1
.intersects( 18, 9 ));
207 ASSERT_FALSE(iset1
.intersects( 20, 1 ));
208 ASSERT_FALSE(iset1
.intersects( 21, 12 ));
211 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
212 ASSERT_FALSE(iset1
.intersects( 0, 2 ));
213 ASSERT_FALSE(iset1
.intersects( 1, 1 ));
214 ASSERT_FALSE(iset1
.intersects( 5, 2 ));
215 ASSERT_FALSE(iset1
.intersects( 10, 2 ));
218 TYPED_TEST(IntervalSetTest
, insert_erase
) {
219 typedef typename
TestFixture::ISet ISet
;
221 IntervalValueType start
, len
;
223 iset1
.insert(3, 5, &start
, &len
);
224 ASSERT_TRUE( start
== 3 );
225 ASSERT_TRUE( len
== 5 );
226 ASSERT_TRUE( iset1
.num_intervals() == 1 );
227 ASSERT_TRUE( iset1
.size() == 5 );
229 //adding standalone interval
230 iset1
.insert(15, 10, &start
, &len
);
231 ASSERT_TRUE( start
== 15 );
232 ASSERT_TRUE( len
== 10 );
233 ASSERT_TRUE( iset1
.num_intervals() == 2 );
234 ASSERT_EQ( iset1
.size(), 15 );
236 //adding leftmost standalone interval
237 iset1
.insert(1, 1, &start
, &len
);
238 ASSERT_TRUE( start
== 1 );
239 ASSERT_TRUE( len
== 1 );
240 ASSERT_TRUE( iset1
.num_intervals() == 3 );
241 ASSERT_EQ( iset1
.size(), 16 );
243 //adding leftmost adjusent interval
244 iset1
.insert(0, 1, &start
, &len
);
245 ASSERT_TRUE( start
== 0 );
246 ASSERT_TRUE( len
== 2 );
247 ASSERT_TRUE( iset1
.num_intervals() == 3 );
248 ASSERT_EQ( iset1
.size(), 17 );
250 //adding interim interval that merges leftmost and subseqent intervals
251 iset1
.insert(2, 1, &start
, &len
);
252 ASSERT_TRUE( start
== 0 );
253 ASSERT_TRUE( len
== 8 );
254 ASSERT_TRUE( iset1
.num_intervals() == 2);
255 ASSERT_EQ( iset1
.size(), 18);
257 //adding rigtmost standalone interval
258 iset1
.insert(30, 5, &start
, &len
);
259 ASSERT_TRUE( start
== 30 );
260 ASSERT_TRUE( len
== 5 );
261 ASSERT_TRUE( iset1
.num_intervals() == 3);
262 ASSERT_EQ( iset1
.size(), 23 );
264 //adding rigtmost adjusent interval
265 iset1
.insert(35, 10, &start
, &len
);
266 ASSERT_TRUE( start
== 30 );
267 ASSERT_TRUE( len
== 15 );
268 ASSERT_TRUE( iset1
.num_intervals() == 3);
269 ASSERT_EQ( iset1
.size(), 33 );
271 //adding interim interval that merges with the interval preceeding the rightmost
272 iset1
.insert(25, 1, &start
, &len
);
273 ASSERT_TRUE( start
== 15 );
274 ASSERT_TRUE( len
== 11 );
275 ASSERT_TRUE( iset1
.num_intervals() == 3);
276 ASSERT_EQ( iset1
.size(), 34);
278 //adding interim interval that merges with the rightmost and preceeding intervals
279 iset1
.insert(26, 4, &start
, &len
);
280 ASSERT_TRUE( start
== 15 );
281 ASSERT_TRUE( len
== 30 );
282 ASSERT_TRUE( iset1
.num_intervals() == 2);
283 ASSERT_EQ( iset1
.size(), 38);
285 //and finally build single interval filling the gap at 8-15 using different interval set
286 iset2
.insert( 8, 1 );
287 iset2
.insert( 14, 1 );
288 iset2
.insert( 9, 4 );
289 iset1
.insert( iset2
);
290 iset1
.insert(13, 1, &start
, &len
);
291 ASSERT_TRUE( start
== 0 );
292 ASSERT_TRUE( len
== 45 );
293 ASSERT_TRUE( iset1
.num_intervals() == 1);
294 ASSERT_EQ( iset1
.size(), 45);
296 //now reverses the process using subtract & erase
297 iset1
.subtract( iset2
);
299 ASSERT_TRUE( iset1
.num_intervals() == 2);
300 ASSERT_EQ( iset1
.size(), 38);
301 ASSERT_TRUE( iset1
.contains( 7, 1 ));
302 ASSERT_FALSE( iset1
.contains( 8, 7 ));
303 ASSERT_TRUE( iset1
.contains( 15, 1 ));
304 ASSERT_TRUE( iset1
.contains( 26, 4 ));
307 ASSERT_TRUE( iset1
.num_intervals() == 3);
308 ASSERT_EQ( iset1
.size(), 34);
309 ASSERT_TRUE( iset1
.contains( 7, 1 ));
310 ASSERT_FALSE( iset1
.intersects( 8, 7 ));
311 ASSERT_TRUE( iset1
.contains( 15, 1 ));
312 ASSERT_TRUE( iset1
.contains( 25, 1 ));
313 ASSERT_FALSE( iset1
.contains( 26, 4 ));
314 ASSERT_TRUE( iset1
.contains( 30, 1 ));
317 ASSERT_TRUE( iset1
.num_intervals() == 3);
318 ASSERT_EQ( iset1
.size(), 33 );
319 ASSERT_TRUE( iset1
.contains( 24, 1 ));
320 ASSERT_FALSE( iset1
.contains( 25, 1 ));
321 ASSERT_FALSE( iset1
.intersects( 26, 4 ));
322 ASSERT_TRUE( iset1
.contains( 30, 1 ));
323 ASSERT_TRUE( iset1
.contains( 35, 10 ));
326 ASSERT_TRUE( iset1
.num_intervals() == 3);
327 ASSERT_EQ( iset1
.size(), 23 );
328 ASSERT_TRUE( iset1
.contains( 30, 5 ));
329 ASSERT_TRUE( iset1
.contains( 34, 1 ));
330 ASSERT_FALSE( iset1
.contains( 35, 10 ));
331 ASSERT_FALSE(iset1
.contains( 45, 1 ));
334 ASSERT_TRUE( iset1
.num_intervals() == 2);
335 ASSERT_EQ( iset1
.size(), 18);
336 ASSERT_TRUE( iset1
.contains( 2, 1 ));
337 ASSERT_TRUE( iset1
.contains( 24, 1 ));
338 ASSERT_FALSE( iset1
.contains( 25, 1 ));
339 ASSERT_FALSE( iset1
.contains( 29, 1 ));
340 ASSERT_FALSE( iset1
.contains( 30, 5 ));
341 ASSERT_FALSE( iset1
.contains( 35, 1 ));
344 ASSERT_TRUE( iset1
.num_intervals() == 3 );
345 ASSERT_EQ( iset1
.size(), 17 );
346 ASSERT_TRUE( iset1
.contains( 0, 1 ));
347 ASSERT_TRUE( iset1
.contains( 1, 1 ));
348 ASSERT_FALSE( iset1
.contains( 2, 1 ));
349 ASSERT_TRUE( iset1
.contains( 3, 1 ));
350 ASSERT_TRUE( iset1
.contains( 15, 1 ));
351 ASSERT_FALSE( iset1
.contains( 25, 1 ));
354 ASSERT_TRUE( iset1
.num_intervals() == 3 );
355 ASSERT_EQ( iset1
.size(), 16 );
356 ASSERT_FALSE( iset1
.contains( 0, 1 ));
357 ASSERT_TRUE( iset1
.contains( 1, 1 ));
358 ASSERT_FALSE( iset1
.contains( 2, 1 ));
359 ASSERT_TRUE( iset1
.contains( 3, 1 ));
360 ASSERT_TRUE( iset1
.contains( 15, 1 ));
363 ASSERT_TRUE( iset1
.num_intervals() == 2 );
364 ASSERT_EQ( iset1
.size(), 15 );
365 ASSERT_FALSE( iset1
.contains( 1, 1 ));
366 ASSERT_TRUE( iset1
.contains( 15, 10 ));
367 ASSERT_TRUE( iset1
.contains( 3, 5 ));
370 ASSERT_TRUE( iset1
.num_intervals() == 1 );
371 ASSERT_TRUE( iset1
.size() == 5 );
372 ASSERT_FALSE( iset1
.contains( 1, 1 ));
373 ASSERT_FALSE( iset1
.contains( 15, 10 ));
374 ASSERT_FALSE( iset1
.contains( 25, 1 ));
375 ASSERT_TRUE( iset1
.contains( 3, 5 ));
378 ASSERT_TRUE( iset1
.num_intervals() == 1 );
379 ASSERT_TRUE( iset1
.size() == 4 );
380 ASSERT_FALSE( iset1
.contains( 1, 1 ));
381 ASSERT_FALSE( iset1
.contains( 15, 10 ));
382 ASSERT_FALSE( iset1
.contains( 25, 1 ));
383 ASSERT_TRUE( iset1
.contains( 4, 4 ));
384 ASSERT_FALSE( iset1
.contains( 3, 5 ));
387 ASSERT_TRUE( iset1
.num_intervals() == 0);
388 ASSERT_TRUE( iset1
.size() == 0);
389 ASSERT_FALSE( iset1
.contains( 1, 1 ));
390 ASSERT_FALSE( iset1
.contains( 15, 10 ));
391 ASSERT_FALSE( iset1
.contains( 25, 1 ));
392 ASSERT_FALSE( iset1
.contains( 3, 4 ));
393 ASSERT_FALSE( iset1
.contains( 3, 5 ));
394 ASSERT_FALSE( iset1
.contains( 4, 4 ));
399 TYPED_TEST(IntervalSetTest
, intersect_of
) {
400 typedef typename
TestFixture::ISet ISet
;
401 ISet iset1
, iset2
, iset3
;
403 iset1
.intersection_of( iset2
, iset3
);
404 ASSERT_TRUE( iset1
.num_intervals() == 0);
405 ASSERT_TRUE( iset1
.size() == 0);
407 iset2
.insert( 0, 1 );
408 iset2
.insert( 5, 10 );
409 iset2
.insert( 30, 10 );
411 iset3
.insert( 0, 2 );
412 iset3
.insert( 15, 1 );
413 iset3
.insert( 20, 5 );
414 iset3
.insert( 29, 3 );
415 iset3
.insert( 35, 3 );
416 iset3
.insert( 39, 3 );
418 iset1
.intersection_of( iset2
, iset3
);
419 ASSERT_TRUE( iset1
.num_intervals() == 4);
420 ASSERT_TRUE( iset1
.size() == 7);
422 ASSERT_TRUE( iset1
.contains( 0, 1 ));
423 ASSERT_FALSE( iset1
.contains( 0, 2 ));
425 ASSERT_FALSE( iset1
.contains( 5, 11 ));
426 ASSERT_FALSE( iset1
.contains( 4, 1 ));
427 ASSERT_FALSE( iset1
.contains( 16, 1 ));
429 ASSERT_FALSE( iset1
.contains( 20, 5 ));
431 ASSERT_FALSE( iset1
.contains( 29, 1 ));
432 ASSERT_FALSE( iset1
.contains( 30, 10 ));
434 ASSERT_TRUE( iset1
.contains( 30, 2 ));
435 ASSERT_TRUE( iset1
.contains( 35, 3 ));
436 ASSERT_FALSE( iset1
.contains( 35, 4 ));
438 ASSERT_TRUE( iset1
.contains( 39, 1 ));
439 ASSERT_FALSE( iset1
.contains( 38, 2 ));
440 ASSERT_FALSE( iset1
.contains( 39, 2 ));
443 iset1
.intersection_of(iset2
);
444 ASSERT_TRUE( iset1
== iset3
);
448 iset1
.intersection_of(iset2
);
449 ASSERT_TRUE( iset1
.num_intervals() == 1);
450 ASSERT_TRUE( iset1
.size() == 1);
454 iset1
.intersection_of(iset2
);
455 ASSERT_TRUE( iset1
.num_intervals() == 0);
456 ASSERT_TRUE( iset1
.size() == 0);
460 TYPED_TEST(IntervalSetTest
, union_of
) {
461 typedef typename
TestFixture::ISet ISet
;
462 ISet iset1
, iset2
, iset3
;
464 iset1
.union_of( iset2
, iset3
);
465 ASSERT_TRUE( iset1
.num_intervals() == 0);
466 ASSERT_TRUE( iset1
.size() == 0);
468 iset2
.insert( 0, 1 );
469 iset2
.insert( 5, 10 );
470 iset2
.insert( 30, 10 );
472 iset3
.insert( 0, 2 );
473 iset3
.insert( 15, 1 );
474 iset3
.insert( 20, 5 );
475 iset3
.insert( 29, 3 );
476 iset3
.insert( 39, 3 );
478 iset1
.union_of( iset2
, iset3
);
479 ASSERT_TRUE( iset1
.num_intervals() == 4);
480 ASSERT_EQ( iset1
.size(), 31);
481 ASSERT_TRUE( iset1
.contains( 0, 2 ));
482 ASSERT_FALSE( iset1
.contains( 0, 3 ));
484 ASSERT_TRUE( iset1
.contains( 5, 11 ));
485 ASSERT_FALSE( iset1
.contains( 4, 1 ));
486 ASSERT_FALSE( iset1
.contains( 16, 1 ));
488 ASSERT_TRUE( iset1
.contains( 20, 5 ));
490 ASSERT_TRUE( iset1
.contains( 30, 10 ));
491 ASSERT_TRUE( iset1
.contains( 29, 13 ));
492 ASSERT_FALSE( iset1
.contains( 29, 14 ));
493 ASSERT_FALSE( iset1
.contains( 42, 1 ));
496 iset1
.union_of(iset2
);
497 ASSERT_TRUE( iset1
.num_intervals() == 4);
498 ASSERT_EQ( iset1
.size(), 31);
501 iset3
.insert( 29, 3 );
502 iset3
.insert( 39, 2 );
503 iset1
.union_of(iset3
);
505 ASSERT_TRUE( iset1
.num_intervals() == 4);
506 ASSERT_EQ( iset1
.size(), 31); //actually we added nothing
507 ASSERT_TRUE( iset1
.contains( 29, 13 ));
508 ASSERT_FALSE( iset1
.contains( 29, 14 ));
509 ASSERT_FALSE( iset1
.contains( 42, 1 ));
513 TYPED_TEST(IntervalSetTest
, subset_of
) {
514 typedef typename
TestFixture::ISet ISet
;
517 ASSERT_TRUE(iset1
.subset_of(iset2
));
520 ASSERT_FALSE(iset1
.subset_of(iset2
));
523 ASSERT_FALSE(iset1
.subset_of(iset2
));
526 ASSERT_FALSE(iset1
.subset_of(iset2
));
529 ASSERT_TRUE(iset1
.subset_of(iset2
));
531 iset1
.insert( 20, 4);
532 ASSERT_TRUE(iset1
.subset_of(iset2
));
534 iset1
.insert( 24, 1);
535 ASSERT_FALSE(iset1
.subset_of(iset2
));
537 iset2
.insert( 24, 1);
538 ASSERT_TRUE(iset1
.subset_of(iset2
));
540 iset1
.insert( 30, 5);
541 ASSERT_FALSE(iset1
.subset_of(iset2
));
543 iset2
.insert( 30, 5);
544 ASSERT_TRUE(iset1
.subset_of(iset2
));
547 ASSERT_FALSE(iset1
.subset_of(iset2
));
550 ASSERT_TRUE(iset1
.subset_of(iset2
));
553 ASSERT_FALSE(iset1
.subset_of(iset2
));
556 ASSERT_TRUE(iset1
.subset_of(iset2
));
558 iset1
.insert( 40, 5);
559 ASSERT_FALSE(iset1
.subset_of(iset2
));
561 iset2
.insert( 39, 7);
562 ASSERT_TRUE(iset1
.subset_of(iset2
));
564 iset1
.insert( 50, 5);
565 iset2
.insert( 55, 2);
566 ASSERT_FALSE(iset1
.subset_of(iset2
));
568 ISet iset3
, iset4
, expected
;
572 iset4
.subset_of(iset3
, 0, 100);
573 expected
.insert(5, 10);
574 expected
.insert(20, 5);
575 ASSERT_TRUE(iset4
== expected
);
578 iset4
.subset_of(iset3
, 5, 25);
579 ASSERT_TRUE(iset4
== expected
);
582 iset4
.subset_of(iset3
, 1, 10);
584 expected
.insert(5, 5);
585 ASSERT_TRUE(iset4
== expected
);
588 iset4
.subset_of(iset3
, 8, 24);
590 expected
.insert(8, 7);
591 expected
.insert(20, 4);
592 ASSERT_TRUE(iset4
== expected
);
595 iset4
.subset_of(iset3
, 0, 0);
597 ASSERT_TRUE(iset4
== expected
);
600 iset4
.subset_of(iset3
, 0, 1);
601 ASSERT_TRUE(iset4
== expected
);
604 iset4
.subset_of(iset3
, 0, 5);
605 ASSERT_TRUE(iset4
== expected
);
608 iset4
.subset_of(iset3
, 25, 30);
609 ASSERT_TRUE(iset4
== expected
);
612 iset4
.subset_of(iset3
, 26, 40);
613 ASSERT_TRUE(iset4
== expected
);
616 TYPED_TEST(IntervalSetTest
, span_of
) {
617 typedef typename
TestFixture::ISet ISet
;
623 iset1
.span_of( iset2
, 8, 5 );
624 ASSERT_EQ( iset1
.num_intervals(), 2);
625 ASSERT_EQ( iset1
.size(), 5);
626 ASSERT_TRUE( iset1
.contains( 8, 2 ));
627 ASSERT_TRUE( iset1
.contains( 20, 3 ));
629 iset1
.span_of( iset2
, 3, 5 );
630 ASSERT_EQ( iset1
.num_intervals(), 1);
631 ASSERT_EQ( iset1
.size(), 5);
632 ASSERT_TRUE( iset1
.contains( 5, 5 ));
634 iset1
.span_of( iset2
, 10, 7 );
635 ASSERT_EQ( iset1
.num_intervals(), 1);
636 ASSERT_EQ( iset1
.size(), 5);
637 ASSERT_TRUE( iset1
.contains( 20, 5 ));
638 ASSERT_FALSE( iset1
.contains( 20, 6 ));
640 iset1
.span_of( iset2
, 5, 10);
641 ASSERT_EQ( iset1
.num_intervals(), 2);
642 ASSERT_EQ( iset1
.size(), 10);
643 ASSERT_TRUE( iset1
.contains( 5, 5 ));
644 ASSERT_TRUE( iset1
.contains( 20, 5 ));
646 iset1
.span_of( iset2
, 100, 5 );
647 ASSERT_EQ( iset1
.num_intervals(), 0);
648 ASSERT_EQ( iset1
.size(), 0);