1 /*-----------------------------------------------------------------------------+
2 Copyright (c) 2008-2010: Joachim Faulhaber
3 +------------------------------------------------------------------------------+
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENCE.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7 +-----------------------------------------------------------------------------*/
8 #ifndef LIBS_ICL_TEST_TEST_INTERVAL_SET_SHARED_HPP_JOFA_080920
9 #define LIBS_ICL_TEST_TEST_INTERVAL_SET_SHARED_HPP_JOFA_080920
10
11 #include "portability.hpp"
12
13 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_fundamentals_4_ordered_types()14 void interval_set_fundamentals_4_ordered_types()
15 {
16 typedef IntervalSet<T> IntervalSetT;
17 typedef typename IntervalSetT::interval_type IntervalT;
18 typedef typename IntervalSet<T>::size_type size_T;
19 typedef typename IntervalSet<T>::difference_type diff_T;
20
21 // ordered types is the largest set of instance types.
22 // Because we can not generate values via incrementation for e.g. string,
23 // we are able to test operations only for the most basic values
24 // identity_element (0, empty, T() ...) and unit_element.
25
26 T v0 = boost::icl::identity_element<T>::value();
27 T v1 = unit_element<T>::value();
28 IntervalT I0_0I(v0);
29 IntervalT I1_1I(v1);
30 IntervalT I0_1I(v0, v1, interval_bounds::closed());
31
32 //-------------------------------------------------------------------------
33 //empty set
34 //-------------------------------------------------------------------------
35 BOOST_CHECK_EQUAL(IntervalSet<T>().empty(), true);
36 BOOST_CHECK_EQUAL(icl::is_empty(IntervalSet<T>()), true);
37 BOOST_CHECK_EQUAL(cardinality(IntervalSet<T>()), boost::icl::identity_element<size_T>::value());
38 BOOST_CHECK_EQUAL(IntervalSet<T>().size(), boost::icl::identity_element<size_T>::value());
39 BOOST_CHECK_EQUAL(interval_count(IntervalSet<T>()), 0);
40 BOOST_CHECK_EQUAL(IntervalSet<T>().iterative_size(), 0);
41 BOOST_CHECK_EQUAL(iterative_size(IntervalSet<T>()), 0);
42 BOOST_CHECK_EQUAL(IntervalSet<T>(), IntervalSet<T>());
43
44 IntervalT mt_interval = boost::icl::identity_element<IntervalT>::value();
45 BOOST_CHECK_EQUAL(mt_interval, IntervalT());
46 IntervalSet<T> mt_set = boost::icl::identity_element<IntervalSet<T> >::value();
47 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
48
49 //adding emptieness to emptieness yields emptieness ;)
50 mt_set.add(mt_interval).add(mt_interval);
51 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
52 mt_set.insert(mt_interval).insert(mt_interval);
53 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
54 (mt_set += mt_interval) += mt_interval;
55 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
56 BOOST_CHECK_EQUAL(hull(mt_set), boost::icl::identity_element<IntervalT >::value());
57
58 //subtracting emptieness
59 mt_set.subtract(mt_interval).subtract(mt_interval);
60 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
61 mt_set.erase(mt_interval).erase(mt_interval);
62 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
63 (mt_set -= mt_interval) -= mt_interval;
64 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
65
66 //subtracting elements form emptieness
67 mt_set.subtract(v0).subtract(v1);
68 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
69 mt_set.erase(v0).erase(v1);
70 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
71 (mt_set -= v1) -= v0;
72 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
73
74 //subtracting intervals form emptieness
75 mt_set.subtract(I0_1I).subtract(I1_1I);
76 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
77 mt_set.erase(I0_1I).erase(I1_1I);
78 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
79 (mt_set -= I1_1I) -= I0_1I;
80 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
81
82 //insecting emptieness
83 //mt_set.insect(mt_interval).insect(mt_interval);
84 //BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
85 (mt_set &= mt_interval) &= mt_interval;
86 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
87 //insecting emptieness with elements
88 (mt_set &= v1) &= v0;
89 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
90 //insecting emptieness with intervals
91 (mt_set &= I1_1I) &= I0_1I;
92 BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
93
94 //-------------------------------------------------------------------------
95 //unary set
96 //-------------------------------------------------------------------------
97 IntervalSet<T> single_I0_0I_from_element(v0);
98 IntervalSet<T> single_I0_0I_from_interval(I0_0I);
99 IntervalSet<T> single_I0_0I(single_I0_0I_from_interval);
100
101 BOOST_CHECK_EQUAL(single_I0_0I_from_element, single_I0_0I_from_interval);
102 BOOST_CHECK_EQUAL(single_I0_0I_from_element, single_I0_0I);
103 BOOST_CHECK_EQUAL(icl::hull(single_I0_0I).lower(), I0_0I.lower());
104 BOOST_CHECK_EQUAL(icl::hull(single_I0_0I).upper(), I0_0I.upper());
105
106 IntervalSet<T> single_I1_1I_from_element(v1);
107 IntervalSet<T> single_I1_1I_from_interval(I1_1I);
108 IntervalSet<T> single_I1_1I(single_I1_1I_from_interval);
109
110 BOOST_CHECK_EQUAL(single_I1_1I_from_element, single_I1_1I_from_interval);
111 BOOST_CHECK_EQUAL(single_I1_1I_from_element, single_I1_1I);
112
113 IntervalSet<T> single_I0_1I_from_interval(I0_1I);
114 IntervalSet<T> single_I0_1I(single_I0_1I_from_interval);
115
116 BOOST_CHECK_EQUAL(single_I0_1I_from_interval, single_I0_1I);
117 BOOST_CHECK_EQUAL(hull(single_I0_1I), I0_1I);
118 BOOST_CHECK_EQUAL(hull(single_I0_1I).lower(), I0_1I.lower());
119 BOOST_CHECK_EQUAL(hull(single_I0_1I).upper(), I0_1I.upper());
120
121 //contains predicate
122 BOOST_CHECK_EQUAL(icl::contains(single_I0_0I, v0), true);
123 BOOST_CHECK_EQUAL(icl::contains(single_I0_0I, I0_0I), true);
124 BOOST_CHECK_EQUAL(icl::contains(single_I1_1I, v1), true);
125 BOOST_CHECK_EQUAL(icl::contains(single_I1_1I, I1_1I), true);
126
127 BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, v0), true);
128 BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, I0_1I), true);
129 BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, v1), true);
130 BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, I1_1I), true);
131
132 BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, single_I0_0I), true);
133 BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, single_I1_1I), true);
134 BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, single_I0_1I), true);
135
136 BOOST_CHECK_EQUAL(cardinality(single_I0_0I), unit_element<size_T>::value());
137 BOOST_CHECK_EQUAL(single_I0_0I.size(), unit_element<size_T>::value());
138 BOOST_CHECK_EQUAL(interval_count(single_I0_0I), 1);
139 BOOST_CHECK_EQUAL(single_I0_0I.iterative_size(), 1);
140 BOOST_CHECK_EQUAL(iterative_size(single_I0_0I), 1);
141 }
142
143
144
145 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_ctor_4_bicremental_types()146 void interval_set_ctor_4_bicremental_types()
147 {
148 typedef IntervalSet<T> IntervalSetT;
149 typedef typename IntervalSetT::interval_type IntervalT;
150
151 T v4 = make<T>(4);
152 IntervalT I4_4I(v4);
153
154 IntervalSet<T> _I4_4I;
155 BOOST_CHECK_EQUAL( _I4_4I.empty(), true );
156 IntervalSet<T> _I4_4I_1;
157 IntervalSet<T> _I4_4I_2;
158 IntervalSet<T> _I4_4I_3;
159 _I4_4I += v4;
160 _I4_4I_1 += I4_4I;
161 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_1 );
162 _I4_4I_2.add(v4);
163 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_2 );
164 _I4_4I_3.add(I4_4I);
165 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_3 );
166 _I4_4I_1.add(v4).add(I4_4I);
167 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_1 );
168 _I4_4I_1.insert(v4).insert(I4_4I);
169 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_1 );
170 (_I4_4I_1 += v4) += I4_4I;
171 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_1 );
172
173 BOOST_CHECK_EQUAL( cardinality(_I4_4I), unit_element<typename IntervalSet<T>::size_type>::value() );
174 BOOST_CHECK_EQUAL( _I4_4I.size(), unit_element<typename IntervalSet<T>::size_type>::value() );
175 BOOST_CHECK_EQUAL( interval_count(_I4_4I), 1 );
176 BOOST_CHECK_EQUAL( _I4_4I.iterative_size(), 1 );
177 BOOST_CHECK_EQUAL( iterative_size(_I4_4I), 1 );
178 BOOST_CHECK_EQUAL( hull(_I4_4I).lower(), v4 );
179 BOOST_CHECK_EQUAL( hull(_I4_4I).upper(), v4 );
180
181 IntervalSet<T> _I4_4I_copy(_I4_4I);
182 IntervalSet<T> _I4_4I_assigned;
183 _I4_4I_assigned = _I4_4I;
184 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_copy );
185 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_assigned );
186 _I4_4I_assigned.clear();
187 BOOST_CHECK_EQUAL( true, _I4_4I_assigned.empty() );
188
189 _I4_4I_assigned.swap(_I4_4I_copy);
190 BOOST_CHECK_EQUAL( true, _I4_4I_copy.empty() );
191 BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_assigned );
192
193 }
194
195 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_add_sub_4_bicremental_types()196 void interval_set_add_sub_4_bicremental_types()
197 {
198 typedef IntervalSet<T> IntervalSetT;
199 typedef typename IntervalSetT::interval_type IntervalT;
200
201 T v0 = make<T>(0);
202 T v5 = make<T>(5);
203 T v6 = make<T>(6);
204 T v9 = make<T>(9);
205 IntervalT I5_6I(v5,v6,interval_bounds::closed());
206 IntervalT I5_9I(v5,v9,interval_bounds::closed());
207 IntervalT I0_9I = IntervalT::closed(v0, v9);
208
209 BOOST_CHECK_EQUAL( IntervalSet<T>(I5_6I).add(v0).add(v9),
210 IntervalSet<T>().insert(v9).insert(I5_6I).insert(v0) );
211
212 IntervalSet<T> set_A = IntervalSet<T>(I5_6I).add(v0).add(v9);
213 IntervalSet<T> set_B = IntervalSet<T>().insert(v9).insert(I5_6I).insert(v0);
214 BOOST_CHECK_EQUAL( set_A, set_B );
215 BOOST_CHECK_EQUAL( hull(set_A), I0_9I );
216 BOOST_CHECK_EQUAL( hull(set_A).lower(), I0_9I.lower() );
217 BOOST_CHECK_EQUAL( hull(set_A).upper(), I0_9I.upper() );
218
219 IntervalSet<T> set_A1 = set_A, set_B1 = set_B,
220 set_A2 = set_A, set_B2 = set_B;
221
222 set_A1.subtract(I5_6I).subtract(v9);
223 set_B1.erase(v9).erase(I5_6I);
224 BOOST_CHECK_EQUAL( set_A1, set_B1 );
225
226 set_A2.subtract(I5_9I);
227 set_B2.erase(I5_9I);
228 BOOST_CHECK_EQUAL( set_A1, set_B1 );
229 BOOST_CHECK_EQUAL( set_A1, set_A2 );
230 BOOST_CHECK_EQUAL( set_B1, set_B2 );
231 }
232
233
234 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_distinct_4_bicremental_types()235 void interval_set_distinct_4_bicremental_types()
236 {
237 typedef IntervalSet<T> IntervalSetT;
238 typedef typename IntervalSetT::interval_type IntervalT;
239 typedef typename IntervalSet<T>::size_type size_T;
240 typedef typename IntervalSet<T>::difference_type diff_T;
241 T v1 = make<T>(1);
242 T v3 = make<T>(3);
243 T v5 = make<T>(5);
244
245 size_T s3 = make<size_T>(3);
246
247
248 IntervalSet<T> is_1_3_5;
249 is_1_3_5.add(v1).add(v3).add(v5);
250
251 BOOST_CHECK_EQUAL( cardinality(is_1_3_5), s3 );
252 BOOST_CHECK_EQUAL( is_1_3_5.size(), s3 );
253 BOOST_CHECK_EQUAL( interval_count(is_1_3_5), 3 );
254 BOOST_CHECK_EQUAL( iterative_size(is_1_3_5), 3 );
255 BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(), 3 );
256 }
257
258
259 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_distinct_4_bicremental_continuous_types()260 void interval_set_distinct_4_bicremental_continuous_types()
261 {
262 typedef IntervalSet<T> IntervalSetT;
263 typedef typename IntervalSetT::interval_type IntervalT;
264 typedef typename IntervalSet<T>::size_type size_T;
265 typedef typename IntervalSet<T>::difference_type diff_T;
266 T v1 = make<T>(1);
267 T v3 = make<T>(3);
268 T v5 = make<T>(5);
269
270 size_T s3 = make<size_T>(3);
271 diff_T d0 = make<diff_T>(0);
272 diff_T d2 = make<diff_T>(2);
273
274 IntervalSet<T> is_1_3_5;
275 is_1_3_5.add(v1).add(v3).add(v5);
276
277 BOOST_CHECK_EQUAL( cardinality(is_1_3_5), s3 );
278 BOOST_CHECK_EQUAL( is_1_3_5.size(), s3 );
279 BOOST_CHECK_EQUAL( icl::length(is_1_3_5), d0 );
280 BOOST_CHECK_EQUAL( interval_count(is_1_3_5), 3 );
281 BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(), 3 );
282 BOOST_CHECK_EQUAL( iterative_size(is_1_3_5), 3 );
283
284
285
286 IntervalSet<T> is_123_5;
287 is_123_5 = is_1_3_5;
288 is_123_5 += IntervalT::open(v1,v3);
289
290 BOOST_CHECK_EQUAL( cardinality(is_123_5), icl::infinity<size_T>::value() );
291 BOOST_CHECK_EQUAL( is_123_5.size(), icl::infinity<size_T>::value() );
292 BOOST_CHECK_EQUAL( icl::length(is_123_5), d2 );
293 }
294
295
296 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_isolate_4_bicremental_continuous_types()297 void interval_set_isolate_4_bicremental_continuous_types()
298 {
299 typedef IntervalSet<T> IntervalSetT;
300 typedef typename IntervalSetT::interval_type IntervalT;
301 typedef typename IntervalSet<T>::size_type size_T;
302 typedef typename IntervalSet<T>::difference_type diff_T;
303
304 T v0 = make<T>(0);
305 T v2 = make<T>(2);
306 T v4 = make<T>(4);
307 IntervalT I0_4I = IntervalT::closed(v0,v4);
308 IntervalT C0_2D = IntervalT::open(v0,v2);
309 IntervalT C2_4D = IntervalT::open(v2,v4);
310 // {[0 4]}
311 // - { (0,2) (2,4) }
312 // = {[0] [2] [4]}
313 IntervalSet<T> iso_set = IntervalSet<T>(I0_4I);
314 IntervalSet<T> gap_set;
315 gap_set.add(C0_2D).add(C2_4D);
316 BOOST_CHECK_EQUAL( true, true );
317 iso_set -= gap_set;
318
319 BOOST_CHECK_EQUAL( cardinality(iso_set), static_cast<size_T>(3) );
320 BOOST_CHECK_EQUAL( iso_set.iterative_size(), static_cast<std::size_t>(3) );
321 BOOST_CHECK_EQUAL( iterative_size(iso_set), static_cast<std::size_t>(3) );
322
323 IntervalSet<T> iso_set2;
324 iso_set2.add(I0_4I);
325 iso_set2.subtract(C0_2D).subtract(C2_4D);
326
327 IntervalSet<T> iso_set3(I0_4I);
328 (iso_set3 -= C0_2D) -= C2_4D;
329
330 IntervalSet<T> iso_set4;
331 iso_set4.insert(I0_4I);
332 iso_set4.erase(C0_2D).erase(C2_4D);
333
334 BOOST_CHECK_EQUAL( iso_set, iso_set2 );
335 BOOST_CHECK_EQUAL( iso_set, iso_set3 );
336 BOOST_CHECK_EQUAL( iso_set, iso_set4 );
337 }
338
339
340 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_element_compare_4_bicremental_types()341 void interval_set_element_compare_4_bicremental_types()
342 {
343 typedef IntervalSet<T> IntervalSetT;
344 typedef typename IntervalSetT::interval_type IntervalT;
345 typedef IntervalSet<T> ISet;
346
347 BOOST_CHECK_EQUAL( is_element_equal( ISet(), ISet()), true );
348 BOOST_CHECK_EQUAL( is_element_equal( ISet(), ISet(I_D(0,1))), false );
349 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet()), false );
350 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet(I_D(0,1))), true );
351
352 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,5)), ISet(I_D(3,8))), false );
353 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(3,8)), ISet(I_D(0,5))), false );
354
355 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet(I_D(0,1)) ), true );
356 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet(I_D(0,1))+I_D(1,2) ), false );
357 BOOST_CHECK_EQUAL( is_element_equal( I_D(1,2)+ISet(I_D(0,1)), ISet(I_D(0,1)) ), false );
358 BOOST_CHECK_EQUAL( is_element_equal( I_D(1,2)+ISet(I_D(0,1)), ISet(I_D(0,1))+I_D(1,2) ), true );
359
360 //[0 1)[1 2)
361 //[0 2)
362 BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(1,2)), ISet(I_D(0,2)) ), true );
363 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,2)), ISet(I_D(0,1))+I_D(1,2) ), true );
364
365 //[0 1) [2 3)
366 //[0 3)
367 BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(2,3)), ISet(I_D(0,3)) ), false );
368 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,3)), ISet(I_D(0,1))+I_D(2,3) ), false );
369
370 //[0 2)[2 4)
371 // [1 4)
372 BOOST_CHECK_EQUAL( is_element_equal( I_D(0,2)+ISet(I_D(2,4)), ISet(I_D(1,4)) ), false );
373 BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(1,4)), ISet(I_D(0,2))+I_D(2,4) ), false );
374
375 //[0 2)[2 4)
376 //[0 1)[1 3)[3 4)
377 BOOST_CHECK_EQUAL( is_element_equal( I_D(0,2)+ISet(I_D(2,4)), I_D(0,1)+ISet(I_D(1,4))+I_D(3,4) ), true );
378 BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(1,4))+I_D(3,4), I_D(0,2)+ISet(I_D(2,4)) ), true );
379 }
380
381 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_contains_4_bicremental_types()382 void interval_set_contains_4_bicremental_types()
383 {
384 typedef IntervalSet<T> IntervalSetT;
385 typedef typename IntervalSetT::interval_type IntervalT;
386 //LAW: x.add(e).contains(e);
387 //LAW: z = x + y => contains(z, x) && contains(z, y);
388 T v1 = make<T>(1);
389 T v3 = make<T>(3);
390 T v5 = make<T>(5);
391 T v7 = make<T>(7);
392 T v8 = make<T>(8);
393 T v9 = make<T>(9);
394 T v11 = make<T>(11);
395 IntervalSet<T> is(v1);
396 BOOST_CHECK_EQUAL( icl::contains(is, v1), true );
397
398 BOOST_CHECK_EQUAL( icl::contains(IntervalSet<T>().add(make<T>(2)), make<T>(2)), true );
399 BOOST_CHECK_EQUAL( icl::contains(IntervalSet<T>().insert(make<T>(2)), make<T>(2)), true );
400 BOOST_CHECK_EQUAL( icl::contains((is += IntervalT(v3,v7)), IntervalT(v3,v7)), true );
401
402 IntervalSet<T> is0 = is;
403
404 IntervalSet<T> is2(IntervalT::closed(v5,v8));
405 is2.add(v9).add(v11);
406 is += is2;
407 BOOST_CHECK_EQUAL( contains(is, is2), true );
408
409 is = is0;
410 IntervalSet<T> is3(IntervalT::closed(v5,v8));
411 is3.insert(v9).insert(v11);
412 is += is3;
413 BOOST_CHECK_EQUAL( contains(is, is3), true );
414 }
415
416
417 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_operators_4_bicremental_types()418 void interval_set_operators_4_bicremental_types()
419 {
420 typedef IntervalSet<T> IntervalSetT;
421 typedef typename IntervalSetT::interval_type IntervalT;
422 T v0 = make<T>(0);
423 T v1 = make<T>(1);
424 T v3 = make<T>(3);
425 T v5 = make<T>(5);
426 T v7 = make<T>(7);
427 T v8 = make<T>(8);
428 IntervalSet<T> left, left2, right, all, all2, section, complement, naught;
429 left.add(IntervalT::closed(v0,v1)).add(IntervalT::closed(v3,v5));
430 (right += IntervalT::closed(v3,v5)) += IntervalT::closed(v7,v8);
431
432 BOOST_CHECK_EQUAL( disjoint(left, right), false );
433
434 (all += left) += right;
435 (section += left) &= right;
436 (complement += all) -= section;
437 (all2 += section) += complement;
438
439 BOOST_CHECK_EQUAL( disjoint(section, complement), true );
440 BOOST_CHECK_EQUAL( all, all2 );
441
442 BOOST_CHECK_EQUAL( icl::contains(all, left), true );
443 BOOST_CHECK_EQUAL( icl::contains(all, right), true );
444 BOOST_CHECK_EQUAL( icl::contains(all, complement), true );
445
446 BOOST_CHECK_EQUAL( icl::contains(left, section), true );
447 BOOST_CHECK_EQUAL( icl::contains(right, section), true );
448
449 BOOST_CHECK_EQUAL( within(left, all), true );
450 BOOST_CHECK_EQUAL( within(right, all), true );
451 BOOST_CHECK_EQUAL( within(complement, all), true );
452 BOOST_CHECK_EQUAL( within(section, left), true );
453 BOOST_CHECK_EQUAL( within(section, right), true );
454 }
455
456
457 // Test for nontrivial intersection of interval sets with intervals and values
458 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_base_intersect_4_bicremental_types()459 void interval_set_base_intersect_4_bicremental_types()
460 {
461 typedef IntervalSet<T> IntervalSetT;
462 typedef typename IntervalSetT::interval_type IntervalT;
463 T v0 = make<T>(0);
464 T v1 = make<T>(1);
465 T v2 = make<T>(2);
466 T v3 = make<T>(3);
467 T v6 = make<T>(6);
468 T v7 = make<T>(7);
469 T v8 = make<T>(8);
470 T v9 = make<T>(9);
471
472 IntervalT I0_3D = IntervalT::right_open(v0,v3);
473 IntervalT I1_3D = IntervalT::right_open(v1,v3);
474 IntervalT I1_8D = IntervalT::right_open(v1,v8);
475 IntervalT I2_7D = IntervalT::right_open(v2,v7);
476 IntervalT I2_3D = IntervalT::right_open(v2,v3);
477 IntervalT I6_7D = IntervalT::right_open(v6,v7);
478 IntervalT I6_8D = IntervalT::right_open(v6,v8);
479 IntervalT I6_9D = IntervalT::right_open(v6,v9);
480
481 //--------------------------------------------------------------------------
482 // IntervalSet
483 //--------------------------------------------------------------------------
484 //split_A [0 3) [6 9)
485 // &= [1 8)
486 //split_AB -> [1 3) [6 8)
487 // &= [2 7)
488 // -> [2 3) [6 7)
489 IntervalSet<T> split_A, split_B, split_AB, split_ab, split_ab2;
490
491 split_A.add(I0_3D).add(I6_9D);
492 split_AB = split_A;
493 split_AB &= I1_8D;
494 split_ab.add(I1_3D).add(I6_8D);
495
496 BOOST_CHECK_EQUAL( split_AB, split_ab );
497
498 split_AB = split_A;
499 (split_AB &= I1_8D) &= I2_7D;
500 split_ab2.add(I2_3D).add(I6_7D);
501
502 BOOST_CHECK_EQUAL( split_AB, split_ab2 );
503
504
505 //--------------------------------------------------------------------------
506 //split_A [0 3) [6 9)
507 // &= 1
508 //split_AB -> [1]
509 // += (1 7)
510 // -> [1](1 7)
511 split_A.add(I0_3D).add(I6_9D);
512 split_AB = split_A;
513 split_AB &= v1;
514 split_ab.clear();
515 split_ab.add(v1);
516
517 BOOST_CHECK_EQUAL( split_AB, split_ab );
518
519 split_AB = split_A;
520 (split_AB &= v1) += IntervalT::open(v1,v7);
521 split_ab2.clear();
522 split_ab2 += IntervalT::right_open(v1,v7);
523
524 BOOST_CHECK_EQUAL( is_element_equal(split_AB, split_ab2), true );
525 }
526
527
528 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_flip_4_bicremental_types()529 void interval_set_flip_4_bicremental_types()
530 {
531 typedef IntervalSet<T> IntervalSetT;
532 typedef typename IntervalSetT::interval_type IntervalT;
533 typedef IntervalSetT ISet;
534
535 IntervalSetT set_a, set_b, lhs, rhs;
536 //[0 2)
537 // [1 3)
538 //[0 1) [2 3) : {[0 2)} ^= [2 3)
539 //gcc seed ambiguities with std::_Ios_Iostate& std::operator^= here:
540 // BOOST_CHECK_EQUAL(ISet(I_D(0,2)) ^= I_D(1,3), ISet(I_D(0,1)) + I_D(2,3));
541 set_a = ISet(I_D(0,2));
542 BOOST_CHECK_EQUAL(set_a ^= I_D(1,3), ISet(I_D(0,1)) + I_D(2,3));
543
544 // [1 3)
545 //[0 2)
546 //[0 1) [2 3) : {[1 3)} ^= [0 2)
547 set_a = ISet(I_D(1,3));
548 BOOST_CHECK_EQUAL(set_a ^= I_D(0,2), ISet(I_D(0,1)) + I_D(2,3));
549
550 //[0 2) (3 5]
551 // [1 3)
552 //[0 1) [2 3) (3 5] : a ^= b
553 set_a.clear();
554 set_a.add(I_D(0,2)).add(C_I(3,5));
555 set_b.add(I_D(1,3));
556 lhs = set_a;
557 lhs ^= set_b;
558 rhs.add(I_D(0,1)).add(I_D(2,3)).add(C_I(3,5));
559 BOOST_CHECK_EQUAL(lhs, rhs);
560 }
561
562
563 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_infix_plus_overload_4_bicremental_types()564 void interval_set_infix_plus_overload_4_bicremental_types()
565 {
566 typedef IntervalSet<T> IntervalSetT;
567 typedef typename IntervalSetT::interval_type IntervalT;
568 IntervalT itv = I_D(3,5);
569
570 IntervalSetT set_a, set_b;
571 set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
572 set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
573
574 BOOST_CHECK_EQUAL(set_a + set_b, set_b + set_a);
575 // This checks all cases of is_interval_set_derivative<T>
576 BOOST_CHECK_EQUAL(set_a + itv, itv + set_a);
577 BOOST_CHECK_EQUAL(set_b + MK_v(4), MK_v(4) + set_b);
578 }
579
580
581 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_infix_pipe_overload_4_bicremental_types()582 void interval_set_infix_pipe_overload_4_bicremental_types()
583 {
584 typedef IntervalSet<T> IntervalSetT;
585 typedef typename IntervalSetT::interval_type IntervalT;
586
587 IntervalT itv = I_D(3,5);
588
589 IntervalSetT set_a, set_b;
590 set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
591 set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
592
593 BOOST_CHECK_EQUAL(set_a | set_b, set_b | set_a);
594 //This checks all cases of is_interval_set_derivative<T>
595 BOOST_CHECK_EQUAL(set_a | itv, itv | set_a);
596 BOOST_CHECK_EQUAL(set_b | MK_v(4), MK_v(4) | set_b);
597 }
598
599
600
601 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_infix_minus_overload_4_bicremental_types()602 void interval_set_infix_minus_overload_4_bicremental_types()
603 {
604 typedef IntervalSet<T> IntervalSetT;
605 typedef typename IntervalSetT::interval_type IntervalT;
606
607 IntervalT itv = I_D(3,5);
608
609 IntervalSetT set_a, set_b;
610 set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
611 set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
612
613 BOOST_CHECK_EQUAL(set_a - set_b, (set_b + set_a) - set_b);
614 //This checks all cases of is_interval_set_derivative<T>
615 BOOST_CHECK_EQUAL(set_a - itv, (itv + set_a) - itv);
616 BOOST_CHECK_EQUAL(set_b - MK_v(4), (MK_v(4) + set_b) - MK_v(4));
617 }
618
619
620 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_infix_et_overload_4_bicremental_types()621 void interval_set_infix_et_overload_4_bicremental_types()
622 {
623 typedef IntervalSet<T> IntervalSetT;
624 typedef typename IntervalSetT::interval_type IntervalT;
625
626 IntervalT itv = I_D(3,5);
627
628 IntervalSetT set_a, set_b;
629 set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
630 set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
631
632 BOOST_CHECK_EQUAL(set_a & set_b, set_b & set_a);
633 //This checks all cases of is_interval_set_derivative<T>
634 BOOST_CHECK_EQUAL(set_a & itv, itv & set_a);
635 BOOST_CHECK_EQUAL(set_b & MK_v(4), MK_v(4) & set_b);
636 }
637
638
639
640 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_infix_caret_overload_4_bicremental_types()641 void interval_set_infix_caret_overload_4_bicremental_types()
642 {
643 typedef IntervalSet<T> IntervalSetT;
644 typedef typename IntervalSetT::interval_type IntervalT;
645
646 IntervalT itv = I_D(3,5);
647
648 IntervalSetT set_a, set_b;
649 set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
650 set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
651
652 BOOST_CHECK_EQUAL(set_a ^ set_b, set_b ^ set_a);
653 //This checks all cases of is_interval_set_derivative<T>
654 BOOST_CHECK_EQUAL(set_a ^ itv, itv ^ set_a);
655 BOOST_CHECK_EQUAL(set_b ^ MK_v(4), MK_v(4) ^ set_b);
656 }
657
658
659
660 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_find_4_bicremental_types()661 void interval_set_find_4_bicremental_types()
662 {
663 typedef IntervalSet<T> IntervalSetT;
664 typedef typename IntervalSetT::interval_type IntervalT;
665 typedef typename IntervalSetT::const_iterator c_iterator;
666
667 IntervalT itv = I_D(3,5);
668
669 IntervalSetT set_a;
670 set_a.add(C_D(1,3)).add(I_I(6,11));
671
672 typename IntervalSetT::const_iterator found = set_a.find(MK_v(6));
673
674 BOOST_CHECK_EQUAL( *found, I_I(6,11) );
675
676 found = set_a.find(MK_v(5));
677
678 BOOST_CHECK_EQUAL( found == set_a.end(), true );
679
680 c_iterator found1 = set_a.find(MK_v(6));
681 c_iterator found2 = icl::find(set_a, MK_v(6));
682
683 BOOST_CHECK ( found1 == found2 );
684 BOOST_CHECK_EQUAL( *found1, *found2 );
685 BOOST_CHECK_EQUAL( *found1, I_I(6,11) );
686
687 found1 = set_a.find(MK_v(5));
688
689 BOOST_CHECK_EQUAL( found1 == set_a.end(), true );
690
691 //LAW map c; key k: k in dom(c) => contains(c, *find(c, k))
692 BOOST_CHECK( icl::contains(set_a, *icl::find(set_a, MK_v(2))) );
693 BOOST_CHECK( icl::contains(set_a, *set_a.find(MK_v(11))) );
694
695 BOOST_CHECK( icl::contains(set_a, MK_v(2)) );
696 BOOST_CHECK( icl::contains(set_a, MK_v(10)) );
697 BOOST_CHECK( !icl::contains(set_a, MK_v(1)) );
698 BOOST_CHECK( !icl::contains(set_a, MK_v(3)) );
699
700 BOOST_CHECK( icl::intersects(set_a, MK_v(2)) );
701 BOOST_CHECK( icl::intersects(set_a, MK_v(10)) );
702 BOOST_CHECK( !icl::intersects(set_a, MK_v(1)) );
703 BOOST_CHECK( !icl::intersects(set_a, MK_v(3)) );
704 }
705
706
707 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_intersects_4_bicremental_types()708 void interval_set_intersects_4_bicremental_types()
709 {
710 typedef IntervalSet<T> IntervalSetT;
711 typedef typename IntervalSetT::interval_type IntervalT;
712 typedef typename IntervalSetT::key_type KeyT;
713
714 IntervalT between = I_D(3,5);
715
716 IntervalSetT set_a;
717 set_a.add(C_D(1,3)).add(I_I(6,11));
718 // (1 3) [6 11]
719 BOOST_CHECK( icl::intersects(set_a, MK_v(2)) );
720 BOOST_CHECK( icl::intersects(set_a, MK_v(11)) );
721 BOOST_CHECK( icl::disjoint(set_a, MK_v(3)) );
722 BOOST_CHECK( icl::disjoint(set_a, MK_v(5)) );
723
724 BOOST_CHECK( icl::intersects(set_a, C_D(1,3)) );
725 BOOST_CHECK( icl::intersects(set_a, I_D(8,10)) );
726 BOOST_CHECK( icl::disjoint(set_a, between) );
727 BOOST_CHECK( icl::disjoint(set_a, I_I(0,1)) );
728
729 IntervalSetT to_12 = IntervalSetT(I_D(0, 13));
730 IntervalSetT complement_a = to_12 - set_a;
731 BOOST_CHECK( icl::disjoint(set_a, complement_a) );
732 BOOST_CHECK( icl::intersects(to_12, set_a) );
733
734 BOOST_CHECK_EQUAL( icl::lower(set_a), icl::lower(*(set_a.begin())) );
735 BOOST_CHECK_EQUAL( icl::lower(set_a), MK_v(1) );
736 BOOST_CHECK_EQUAL( icl::upper(set_a), icl::upper(*(set_a.rbegin())) );
737 BOOST_CHECK_EQUAL( icl::upper(set_a), MK_v(11) );
738 }
739
740
741 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_range_4_discrete_types()742 void interval_set_range_4_discrete_types()
743 {
744 typedef IntervalSet<T> IntervalSetT;
745 typedef typename IntervalSetT::interval_type IntervalT;
746 typedef typename IntervalSetT::key_type KeyT;
747
748 IntervalT between = I_D(3,5);
749
750 IntervalSetT set_a;
751 set_a.add(C_D(1,3)).add(I_I(6,11));
752 // (1 3) [6 11]
753 BOOST_CHECK_EQUAL( icl::first(set_a), icl::first(*(set_a.begin())) );
754 BOOST_CHECK_EQUAL( icl::first(set_a), MK_v(2) );
755 BOOST_CHECK_EQUAL( icl::last(set_a), icl::last(*(set_a.rbegin())) );
756 BOOST_CHECK_EQUAL( icl::last(set_a), MK_v(11) );
757 }
758
759
760 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_bitset_find_4_integral_types()761 void interval_bitset_find_4_integral_types()
762 {
763 typedef IntervalSet<T> IntervalSetT;
764 typedef typename IntervalSetT::interval_type IntervalT;
765 typedef typename IntervalSetT::bitset_type BitsT;
766
767 IntervalT itv = I_D(3,5);
768
769 IntervalSetT set_a;
770 set_a.add(C_D(1,3)).add(I_I(6,11));
771
772 typename IntervalSetT::const_iterator found = set_a.find(MK_v(6));
773
774 BOOST_CHECK( (found->second).contains(6) );
775
776 found = set_a.find(MK_v(5));
777 BOOST_CHECK( found == set_a.end() );
778
779 set_a.add(MK_v(64));
780 found = set_a.find(MK_v(64));
781 BOOST_CHECK( (found->second).contains(0) );
782
783 set_a.add(MK_v(65));
784 found = set_a.find(MK_v(65));
785 BOOST_CHECK( (found->second).contains(1) );
786
787 found = set_a.find(MK_v(66));
788 BOOST_CHECK( found == set_a.end() );
789 }
790
791 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_element_iter_4_discrete_types()792 void interval_set_element_iter_4_discrete_types()
793 {
794 typedef IntervalSet<T> IntervalSetT;
795 typedef typename IntervalSetT::interval_type IntervalT;
796 typedef std::vector<T> VectorT;
797
798 IntervalSetT set_a;
799 set_a.add(I_I(1,3)).add(I_I(6,7));
800
801 VectorT vec(5), cev(5);
802 vec[0]=MK_v(1);vec[1]=MK_v(2);vec[2]=MK_v(3);vec[3]=MK_v(6);vec[4]=MK_v(7);
803 cev[0]=MK_v(7);cev[1]=MK_v(6);cev[2]=MK_v(3);cev[3]=MK_v(2);cev[4]=MK_v(1);
804
805 VectorT dest;
806 std::copy(elements_begin(set_a), elements_end(set_a), std::back_inserter(dest));
807 BOOST_CHECK_EQUAL( vec == dest, true );
808
809 dest.clear();
810 std::copy(elements_rbegin(set_a), elements_rend(set_a), std::back_inserter(dest));
811 BOOST_CHECK_EQUAL( cev == dest, true );
812
813 dest.clear();
814 std::reverse_copy(elements_begin(set_a), elements_end(set_a), std::back_inserter(dest));
815 BOOST_CHECK_EQUAL( cev == dest, true );
816
817 dest.clear();
818 std::reverse_copy(elements_rbegin(set_a), elements_rend(set_a), std::back_inserter(dest));
819 BOOST_CHECK_EQUAL( vec == dest, true );
820 }
821
822
823 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
interval_set_move_4_discrete_types()824 void interval_set_move_4_discrete_types()
825 {
826 typedef IntervalSet<T> IntervalSetT;
827 typedef typename IntervalSetT::interval_type IntervalT;
828 typedef std::vector<T> VectorT;
829
830 //JODO static_cast fails for gcc compilers
831 //IntervalSetT set_A(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,4)))));
832 IntervalSetT set_A(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,4)).add(I_D(0,0)) )));
833 IntervalSetT set_B(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,2)).add(I_D(2,4)).add(I_D(0,4)))));
834
835 BOOST_CHECK( icl::is_element_equal(set_A, set_B) );
836 BOOST_CHECK_EQUAL( set_A, join(set_B) );
837
838 //JODO static_cast fails for gcc compilers
839 //set_A = boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_I(1,4))));
840 set_A = boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_I(1,4)).add(I_D(0,0))));
841 set_B = boost::move(static_cast<IntervalSetT&>(IntervalSetT(C_I(0,2)).insert(I_D(3,5)).add(C_D(0,5))));
842
843 BOOST_CHECK( icl::is_element_equal(set_A, set_B) );
844 BOOST_CHECK_EQUAL( set_A, join(set_B) );
845 }
846
847
848
849 #endif // LIBS_ICL_TEST_TEST_INTERVAL_SET_SHARED_HPP_JOFA_080920
850
851