]>
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
, btree::btree_map
>,
36 interval_set
<IntervalValueType
, boost::container::flat_map
>
39 TYPED_TEST_SUITE(IntervalSetTest
, IntervalSetTypes
);
41 TYPED_TEST(IntervalSetTest
, compare
) {
42 typedef typename
TestFixture::ISet ISet
;
44 ASSERT_TRUE(iset1
== iset1
);
45 ASSERT_TRUE(iset1
== iset2
);
48 ASSERT_FALSE(iset1
== iset2
);
51 ASSERT_TRUE(iset1
== iset2
);
55 ASSERT_FALSE(iset1
== iset2
);
61 ASSERT_TRUE(iset1
== iset2
);
63 iset1
.insert(100, 10);
65 ASSERT_FALSE(iset1
== iset2
);
67 ASSERT_TRUE(iset1
== iset2
);
69 iset1
.insert(200, 10);
71 ASSERT_FALSE(iset1
== iset2
);
74 ASSERT_FALSE(iset1
== iset2
);
76 ASSERT_TRUE(iset1
== iset2
);
79 ASSERT_FALSE(iset1
== iset2
);
81 ASSERT_TRUE(iset1
== iset2
);
84 TYPED_TEST(IntervalSetTest
, contains
) {
85 typedef typename
TestFixture::ISet ISet
;
87 ASSERT_FALSE(iset1
.contains( 1 ));
88 ASSERT_FALSE(iset1
.contains( 0, 1 ));
91 ASSERT_TRUE(iset1
.contains( 1 ));
92 ASSERT_FALSE(iset1
.contains( 0 ));
93 ASSERT_FALSE(iset1
.contains( 2 ));
94 ASSERT_FALSE(iset1
.contains( 0, 1 ));
95 ASSERT_FALSE(iset1
.contains( 0, 2 ));
96 ASSERT_TRUE(iset1
.contains( 1, 1 ));
97 ASSERT_FALSE(iset1
.contains( 1, 2 ));
100 ASSERT_TRUE(iset1
.contains( 1 ));
101 ASSERT_FALSE(iset1
.contains( 0 ));
102 ASSERT_TRUE(iset1
.contains( 2 ));
103 ASSERT_FALSE(iset1
.contains( 0, 1 ));
104 ASSERT_FALSE(iset1
.contains( 0, 2 ));
105 ASSERT_TRUE(iset1
.contains( 1, 1 ));
106 ASSERT_TRUE(iset1
.contains( 1, 2 ));
107 ASSERT_TRUE(iset1
.contains( 1, 3 ));
108 ASSERT_TRUE(iset1
.contains( 1, 4 ));
109 ASSERT_FALSE(iset1
.contains( 1, 5 ));
110 ASSERT_TRUE(iset1
.contains( 2, 1 ));
111 ASSERT_TRUE(iset1
.contains( 2, 2 ));
112 ASSERT_TRUE(iset1
.contains( 2, 3 ));
113 ASSERT_FALSE(iset1
.contains( 2, 4 ));
114 ASSERT_TRUE(iset1
.contains( 3, 2 ));
115 ASSERT_TRUE(iset1
.contains( 4, 1 ));
116 ASSERT_FALSE(iset1
.contains( 4, 2 ));
118 iset1
.insert(10, 10);
119 ASSERT_TRUE(iset1
.contains( 1, 4 ));
120 ASSERT_FALSE(iset1
.contains( 1, 5 ));
121 ASSERT_TRUE(iset1
.contains( 2, 2 ));
122 ASSERT_FALSE(iset1
.contains( 2, 4 ));
124 ASSERT_FALSE(iset1
.contains( 1, 10 ));
125 ASSERT_FALSE(iset1
.contains( 9, 1 ));
126 ASSERT_FALSE(iset1
.contains( 9 ));
127 ASSERT_FALSE(iset1
.contains( 9, 11 ));
128 ASSERT_TRUE(iset1
.contains( 10, 1 ));
129 ASSERT_TRUE(iset1
.contains( 11, 9 ));
130 ASSERT_TRUE(iset1
.contains( 11, 2 ));
131 ASSERT_TRUE(iset1
.contains( 18, 2 ));
132 ASSERT_TRUE(iset1
.contains( 18, 2 ));
133 ASSERT_TRUE(iset1
.contains( 10 ));
134 ASSERT_TRUE(iset1
.contains( 19 ));
135 ASSERT_FALSE(iset1
.contains( 20 ));
136 ASSERT_FALSE(iset1
.contains( 21 ));
138 ASSERT_FALSE(iset1
.contains( 11, 11 ));
139 ASSERT_FALSE(iset1
.contains( 18, 9 ));
142 ASSERT_FALSE(iset1
.contains( 1 ));
143 ASSERT_FALSE(iset1
.contains( 0 ));
144 ASSERT_FALSE(iset1
.contains( 2 ));
145 ASSERT_FALSE(iset1
.contains( 0, 1 ));
146 ASSERT_FALSE(iset1
.contains( 0, 2 ));
147 ASSERT_FALSE(iset1
.contains( 1, 1 ));
148 ASSERT_FALSE(iset1
.contains( 10, 2 ));
151 TYPED_TEST(IntervalSetTest
, intersects
) {
152 typedef typename
TestFixture::ISet ISet
;
154 ASSERT_FALSE(iset1
.intersects( 1, 1 ));
155 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
156 ASSERT_FALSE(iset1
.intersects( 0, 10 ));
159 ASSERT_TRUE(iset1
.intersects( 1, 1 ));
160 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
161 ASSERT_FALSE(iset1
.intersects( 2, 1 ));
162 ASSERT_TRUE(iset1
.intersects( 0, 2 ));
163 ASSERT_TRUE(iset1
.intersects( 0, 20 ));
164 ASSERT_TRUE(iset1
.intersects( 1, 2 ));
165 ASSERT_TRUE(iset1
.intersects( 1, 20 ));
168 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
169 ASSERT_TRUE(iset1
.intersects( 0, 2 ));
170 ASSERT_TRUE(iset1
.intersects( 0, 200 ));
171 ASSERT_TRUE(iset1
.intersects( 1, 1 ));
172 ASSERT_TRUE(iset1
.intersects( 1, 4 ));
173 ASSERT_TRUE(iset1
.intersects( 1, 5 ));
174 ASSERT_TRUE(iset1
.intersects( 2, 1 ));
175 ASSERT_TRUE(iset1
.intersects( 2, 2 ));
176 ASSERT_TRUE(iset1
.intersects( 2, 3 ));
177 ASSERT_TRUE(iset1
.intersects( 2, 4 ));
178 ASSERT_TRUE(iset1
.intersects( 3, 2 ));
179 ASSERT_TRUE(iset1
.intersects( 4, 1 ));
180 ASSERT_TRUE(iset1
.intersects( 4, 2 ));
181 ASSERT_FALSE(iset1
.intersects( 5, 2 ));
183 iset1
.insert(10, 10);
184 ASSERT_TRUE(iset1
.intersects( 1, 4 ));
185 ASSERT_TRUE(iset1
.intersects( 1, 5 ));
186 ASSERT_TRUE(iset1
.intersects( 1, 10 ));
187 ASSERT_TRUE(iset1
.intersects( 2, 2 ));
188 ASSERT_TRUE(iset1
.intersects( 2, 4 ));
189 ASSERT_FALSE(iset1
.intersects( 5, 1 ));
190 ASSERT_FALSE(iset1
.intersects( 5, 2 ));
191 ASSERT_FALSE(iset1
.intersects( 5, 5 ));
192 ASSERT_TRUE(iset1
.intersects( 5, 12 ));
193 ASSERT_TRUE(iset1
.intersects( 5, 20 ));
195 ASSERT_FALSE(iset1
.intersects( 9, 1 ));
196 ASSERT_TRUE(iset1
.intersects( 9, 2 ));
198 ASSERT_TRUE(iset1
.intersects( 9, 11 ));
199 ASSERT_TRUE(iset1
.intersects( 10, 1 ));
200 ASSERT_TRUE(iset1
.intersects( 11, 9 ));
201 ASSERT_TRUE(iset1
.intersects( 11, 2 ));
202 ASSERT_TRUE(iset1
.intersects( 11, 11 ));
203 ASSERT_TRUE(iset1
.intersects( 18, 2 ));
204 ASSERT_TRUE(iset1
.intersects( 18, 9 ));
205 ASSERT_FALSE(iset1
.intersects( 20, 1 ));
206 ASSERT_FALSE(iset1
.intersects( 21, 12 ));
209 ASSERT_FALSE(iset1
.intersects( 0, 1 ));
210 ASSERT_FALSE(iset1
.intersects( 0, 2 ));
211 ASSERT_FALSE(iset1
.intersects( 1, 1 ));
212 ASSERT_FALSE(iset1
.intersects( 5, 2 ));
213 ASSERT_FALSE(iset1
.intersects( 10, 2 ));
216 TYPED_TEST(IntervalSetTest
, insert_erase
) {
217 typedef typename
TestFixture::ISet ISet
;
219 IntervalValueType start
, len
;
221 iset1
.insert(3, 5, &start
, &len
);
224 ASSERT_EQ(1, iset1
.num_intervals());
225 ASSERT_EQ(5, iset1
.size());
227 //adding standalone interval
228 iset1
.insert(15, 10, &start
, &len
);
229 ASSERT_EQ(15, start
);
231 ASSERT_EQ(2, iset1
.num_intervals());
232 ASSERT_EQ(15, iset1
.size());
234 //adding leftmost standalone interval
235 iset1
.insert(1, 1, &start
, &len
);
238 ASSERT_EQ(3, iset1
.num_intervals());
239 ASSERT_EQ(16, iset1
.size());
241 //adding leftmost adjucent interval
242 iset1
.insert(0, 1, &start
, &len
);
245 ASSERT_EQ(3, iset1
.num_intervals());
246 ASSERT_EQ(17, iset1
.size());
248 //adding interim interval that merges leftmost and subseqent intervals
249 iset1
.insert(2, 1, &start
, &len
);
252 ASSERT_EQ(2, iset1
.num_intervals());
253 ASSERT_EQ(18, iset1
.size());
255 //adding rigtmost standalone interval
256 iset1
.insert(30, 5, &start
, &len
);
257 ASSERT_EQ(30, start
);
259 ASSERT_EQ(3, iset1
.num_intervals());
260 ASSERT_EQ(23, iset1
.size());
262 //adding rigtmost adjusent interval
263 iset1
.insert(35, 10, &start
, &len
);
264 ASSERT_EQ(30, start
);
266 ASSERT_EQ(3, iset1
.num_intervals());
267 ASSERT_EQ(33, iset1
.size());
269 //adding interim interval that merges with the interval preceeding the rightmost
270 iset1
.insert(25, 1, &start
, &len
);
271 ASSERT_EQ(15, start
);
273 ASSERT_EQ(3, iset1
.num_intervals());
274 ASSERT_EQ(34, iset1
.size());
276 //adding interim interval that merges with the rightmost and preceeding intervals
277 iset1
.insert(26, 4, &start
, &len
);
278 ASSERT_EQ(15, start
);
280 ASSERT_EQ(2, iset1
.num_intervals());
281 ASSERT_EQ(38, iset1
.size());
283 //and finally build single interval filling the gap at 8-15 using different interval set
284 iset2
.insert( 8, 1 );
285 iset2
.insert( 14, 1 );
286 iset2
.insert( 9, 4 );
287 iset1
.insert( iset2
);
288 iset1
.insert(13, 1, &start
, &len
);
291 ASSERT_EQ(1, iset1
.num_intervals());
292 ASSERT_EQ(45, iset1
.size());
294 //now reverses the process using subtract & erase
295 iset1
.subtract( iset2
);
297 ASSERT_EQ( 2, iset1
.num_intervals() );
298 ASSERT_EQ(38, iset1
.size());
299 ASSERT_TRUE( iset1
.contains( 7, 1 ));
300 ASSERT_FALSE( iset1
.contains( 8, 7 ));
301 ASSERT_TRUE( iset1
.contains( 15, 1 ));
302 ASSERT_TRUE( iset1
.contains( 26, 4 ));
305 ASSERT_EQ(3, iset1
.num_intervals());
306 ASSERT_EQ(34, iset1
.size());
307 ASSERT_TRUE( iset1
.contains( 7, 1 ));
308 ASSERT_FALSE( iset1
.intersects( 8, 7 ));
309 ASSERT_TRUE( iset1
.contains( 15, 1 ));
310 ASSERT_TRUE( iset1
.contains( 25, 1 ));
311 ASSERT_FALSE( iset1
.contains( 26, 4 ));
312 ASSERT_TRUE( iset1
.contains( 30, 1 ));
315 ASSERT_EQ(3, iset1
.num_intervals());
316 ASSERT_EQ(33, iset1
.size());
317 ASSERT_TRUE( iset1
.contains( 24, 1 ));
318 ASSERT_FALSE( iset1
.contains( 25, 1 ));
319 ASSERT_FALSE( iset1
.intersects( 26, 4 ));
320 ASSERT_TRUE( iset1
.contains( 30, 1 ));
321 ASSERT_TRUE( iset1
.contains( 35, 10 ));
324 ASSERT_EQ(3, iset1
.num_intervals());
325 ASSERT_EQ(23, iset1
.size());
326 ASSERT_TRUE( iset1
.contains( 30, 5 ));
327 ASSERT_TRUE( iset1
.contains( 34, 1 ));
328 ASSERT_FALSE( iset1
.contains( 35, 10 ));
329 ASSERT_FALSE(iset1
.contains( 45, 1 ));
332 ASSERT_EQ(2, iset1
.num_intervals());
333 ASSERT_EQ(18, iset1
.size());
334 ASSERT_TRUE( iset1
.contains( 2, 1 ));
335 ASSERT_TRUE( iset1
.contains( 24, 1 ));
336 ASSERT_FALSE( iset1
.contains( 25, 1 ));
337 ASSERT_FALSE( iset1
.contains( 29, 1 ));
338 ASSERT_FALSE( iset1
.contains( 30, 5 ));
339 ASSERT_FALSE( iset1
.contains( 35, 1 ));
342 ASSERT_EQ(3, iset1
.num_intervals());
343 ASSERT_EQ( iset1
.size(), 17 );
344 ASSERT_TRUE( iset1
.contains( 0, 1 ));
345 ASSERT_TRUE( iset1
.contains( 1, 1 ));
346 ASSERT_FALSE( iset1
.contains( 2, 1 ));
347 ASSERT_TRUE( iset1
.contains( 3, 1 ));
348 ASSERT_TRUE( iset1
.contains( 15, 1 ));
349 ASSERT_FALSE( iset1
.contains( 25, 1 ));
352 ASSERT_EQ(3, iset1
.num_intervals());
353 ASSERT_EQ(16, iset1
.size());
354 ASSERT_FALSE( iset1
.contains( 0, 1 ));
355 ASSERT_TRUE( iset1
.contains( 1, 1 ));
356 ASSERT_FALSE( iset1
.contains( 2, 1 ));
357 ASSERT_TRUE( iset1
.contains( 3, 1 ));
358 ASSERT_TRUE( iset1
.contains( 15, 1 ));
361 ASSERT_EQ(2, iset1
.num_intervals());
362 ASSERT_EQ(15, iset1
.size());
363 ASSERT_FALSE( iset1
.contains( 1, 1 ));
364 ASSERT_TRUE( iset1
.contains( 15, 10 ));
365 ASSERT_TRUE( iset1
.contains( 3, 5 ));
368 ASSERT_EQ(1, iset1
.num_intervals());
369 ASSERT_EQ(5, iset1
.size());
370 ASSERT_FALSE( iset1
.contains( 1, 1 ));
371 ASSERT_FALSE( iset1
.contains( 15, 10 ));
372 ASSERT_FALSE( iset1
.contains( 25, 1 ));
373 ASSERT_TRUE( iset1
.contains( 3, 5 ));
376 ASSERT_EQ(1, iset1
.num_intervals());
377 ASSERT_EQ(4, iset1
.size());
378 ASSERT_FALSE( iset1
.contains( 1, 1 ));
379 ASSERT_FALSE( iset1
.contains( 15, 10 ));
380 ASSERT_FALSE( iset1
.contains( 25, 1 ));
381 ASSERT_TRUE( iset1
.contains( 4, 4 ));
382 ASSERT_FALSE( iset1
.contains( 3, 5 ));
385 ASSERT_EQ(0, iset1
.num_intervals());
386 ASSERT_EQ(0, iset1
.size());
387 ASSERT_FALSE( iset1
.contains( 1, 1 ));
388 ASSERT_FALSE( iset1
.contains( 15, 10 ));
389 ASSERT_FALSE( iset1
.contains( 25, 1 ));
390 ASSERT_FALSE( iset1
.contains( 3, 4 ));
391 ASSERT_FALSE( iset1
.contains( 3, 5 ));
392 ASSERT_FALSE( iset1
.contains( 4, 4 ));
397 TYPED_TEST(IntervalSetTest
, intersect_of
) {
398 typedef typename
TestFixture::ISet ISet
;
399 ISet iset1
, iset2
, iset3
;
401 iset1
.intersection_of( iset2
, iset3
);
402 ASSERT_TRUE( iset1
.num_intervals() == 0);
403 ASSERT_TRUE( iset1
.size() == 0);
405 iset2
.insert( 0, 1 );
406 iset2
.insert( 5, 10 );
407 iset2
.insert( 30, 10 );
409 iset3
.insert( 0, 2 );
410 iset3
.insert( 15, 1 );
411 iset3
.insert( 20, 5 );
412 iset3
.insert( 29, 3 );
413 iset3
.insert( 35, 3 );
414 iset3
.insert( 39, 3 );
416 iset1
.intersection_of( iset2
, iset3
);
417 ASSERT_TRUE( iset1
.num_intervals() == 4);
418 ASSERT_TRUE( iset1
.size() == 7);
420 ASSERT_TRUE( iset1
.contains( 0, 1 ));
421 ASSERT_FALSE( iset1
.contains( 0, 2 ));
423 ASSERT_FALSE( iset1
.contains( 5, 11 ));
424 ASSERT_FALSE( iset1
.contains( 4, 1 ));
425 ASSERT_FALSE( iset1
.contains( 16, 1 ));
427 ASSERT_FALSE( iset1
.contains( 20, 5 ));
429 ASSERT_FALSE( iset1
.contains( 29, 1 ));
430 ASSERT_FALSE( iset1
.contains( 30, 10 ));
432 ASSERT_TRUE( iset1
.contains( 30, 2 ));
433 ASSERT_TRUE( iset1
.contains( 35, 3 ));
434 ASSERT_FALSE( iset1
.contains( 35, 4 ));
436 ASSERT_TRUE( iset1
.contains( 39, 1 ));
437 ASSERT_FALSE( iset1
.contains( 38, 2 ));
438 ASSERT_FALSE( iset1
.contains( 39, 2 ));
441 iset1
.intersection_of(iset2
);
442 ASSERT_TRUE( iset1
== iset3
);
446 iset1
.intersection_of(iset2
);
447 ASSERT_TRUE( iset1
.num_intervals() == 1);
448 ASSERT_TRUE( iset1
.size() == 1);
452 iset1
.intersection_of(iset2
);
453 ASSERT_TRUE( iset1
.num_intervals() == 0);
454 ASSERT_TRUE( iset1
.size() == 0);
458 TYPED_TEST(IntervalSetTest
, union_of
) {
459 typedef typename
TestFixture::ISet ISet
;
460 ISet iset1
, iset2
, iset3
;
462 iset1
.union_of( iset2
, iset3
);
463 ASSERT_TRUE( iset1
.num_intervals() == 0);
464 ASSERT_TRUE( iset1
.size() == 0);
466 iset2
.insert( 0, 1 );
467 iset2
.insert( 5, 10 );
468 iset2
.insert( 30, 10 );
470 iset3
.insert( 0, 2 );
471 iset3
.insert( 15, 1 );
472 iset3
.insert( 20, 5 );
473 iset3
.insert( 29, 3 );
474 iset3
.insert( 39, 3 );
476 iset1
.union_of( iset2
, iset3
);
477 ASSERT_TRUE( iset1
.num_intervals() == 4);
478 ASSERT_EQ( iset1
.size(), 31);
479 ASSERT_TRUE( iset1
.contains( 0, 2 ));
480 ASSERT_FALSE( iset1
.contains( 0, 3 ));
482 ASSERT_TRUE( iset1
.contains( 5, 11 ));
483 ASSERT_FALSE( iset1
.contains( 4, 1 ));
484 ASSERT_FALSE( iset1
.contains( 16, 1 ));
486 ASSERT_TRUE( iset1
.contains( 20, 5 ));
488 ASSERT_TRUE( iset1
.contains( 30, 10 ));
489 ASSERT_TRUE( iset1
.contains( 29, 13 ));
490 ASSERT_FALSE( iset1
.contains( 29, 14 ));
491 ASSERT_FALSE( iset1
.contains( 42, 1 ));
494 iset1
.union_of(iset2
);
495 ASSERT_TRUE( iset1
.num_intervals() == 4);
496 ASSERT_EQ( iset1
.size(), 31);
499 iset3
.insert( 29, 3 );
500 iset3
.insert( 39, 2 );
501 iset1
.union_of(iset3
);
503 ASSERT_TRUE( iset1
.num_intervals() == 4);
504 ASSERT_EQ( iset1
.size(), 31); //actually we added nothing
505 ASSERT_TRUE( iset1
.contains( 29, 13 ));
506 ASSERT_FALSE( iset1
.contains( 29, 14 ));
507 ASSERT_FALSE( iset1
.contains( 42, 1 ));
511 TYPED_TEST(IntervalSetTest
, subset_of
) {
512 typedef typename
TestFixture::ISet ISet
;
515 ASSERT_TRUE(iset1
.subset_of(iset2
));
518 ASSERT_FALSE(iset1
.subset_of(iset2
));
521 ASSERT_FALSE(iset1
.subset_of(iset2
));
524 ASSERT_FALSE(iset1
.subset_of(iset2
));
527 ASSERT_TRUE(iset1
.subset_of(iset2
));
529 iset1
.insert( 20, 4);
530 ASSERT_TRUE(iset1
.subset_of(iset2
));
532 iset1
.insert( 24, 1);
533 ASSERT_FALSE(iset1
.subset_of(iset2
));
535 iset2
.insert( 24, 1);
536 ASSERT_TRUE(iset1
.subset_of(iset2
));
538 iset1
.insert( 30, 5);
539 ASSERT_FALSE(iset1
.subset_of(iset2
));
541 iset2
.insert( 30, 5);
542 ASSERT_TRUE(iset1
.subset_of(iset2
));
545 ASSERT_FALSE(iset1
.subset_of(iset2
));
548 ASSERT_TRUE(iset1
.subset_of(iset2
));
551 ASSERT_FALSE(iset1
.subset_of(iset2
));
554 ASSERT_TRUE(iset1
.subset_of(iset2
));
556 iset1
.insert( 40, 5);
557 ASSERT_FALSE(iset1
.subset_of(iset2
));
559 iset2
.insert( 39, 7);
560 ASSERT_TRUE(iset1
.subset_of(iset2
));
562 iset1
.insert( 50, 5);
563 iset2
.insert( 55, 2);
564 ASSERT_FALSE(iset1
.subset_of(iset2
));
567 TYPED_TEST(IntervalSetTest
, span_of
) {
568 typedef typename
TestFixture::ISet ISet
;
574 iset1
.span_of( iset2
, 8, 5 );
575 ASSERT_EQ( iset1
.num_intervals(), 2);
576 ASSERT_EQ( iset1
.size(), 5);
577 ASSERT_TRUE( iset1
.contains( 8, 2 ));
578 ASSERT_TRUE( iset1
.contains( 20, 3 ));
580 iset1
.span_of( iset2
, 3, 5 );
581 ASSERT_EQ( iset1
.num_intervals(), 1);
582 ASSERT_EQ( iset1
.size(), 5);
583 ASSERT_TRUE( iset1
.contains( 5, 5 ));
585 iset1
.span_of( iset2
, 10, 7 );
586 ASSERT_EQ( iset1
.num_intervals(), 1);
587 ASSERT_EQ( iset1
.size(), 5);
588 ASSERT_TRUE( iset1
.contains( 20, 5 ));
589 ASSERT_FALSE( iset1
.contains( 20, 6 ));
591 iset1
.span_of( iset2
, 5, 10);
592 ASSERT_EQ( iset1
.num_intervals(), 2);
593 ASSERT_EQ( iset1
.size(), 10);
594 ASSERT_TRUE( iset1
.contains( 5, 5 ));
595 ASSERT_TRUE( iset1
.contains( 20, 5 ));
597 iset1
.span_of( iset2
, 100, 5 );
598 ASSERT_EQ( iset1
.num_intervals(), 0);
599 ASSERT_EQ( iset1
.size(), 0);