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 <boost/range/algorithm.hpp> |
12 | #include "portability.hpp" |
13 | |
14 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
15 | void interval_set_fundamentals_4_ordered_types() |
16 | { |
17 | typedef IntervalSet<T> IntervalSetT; |
18 | typedef typename IntervalSetT::interval_type IntervalT; |
19 | typedef typename IntervalSet<T>::size_type size_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> |
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> |
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> |
235 | void interval_set_distinct_4_bicremental_types() |
236 | { |
237 | typedef typename IntervalSet<T>::size_type size_T; |
238 | |
239 | T v1 = make<T>(1); |
240 | T v3 = make<T>(3); |
241 | T v5 = make<T>(5); |
242 | |
243 | size_T s3 = make<size_T>(3); |
244 | |
245 | IntervalSet<T> is_1_3_5; |
246 | is_1_3_5.add(v1).add(v3).add(v5); |
247 | |
248 | BOOST_CHECK_EQUAL( cardinality(is_1_3_5), s3 ); |
249 | BOOST_CHECK_EQUAL( is_1_3_5.size(), s3 ); |
250 | BOOST_CHECK_EQUAL( interval_count(is_1_3_5), 3 ); |
251 | BOOST_CHECK_EQUAL( iterative_size(is_1_3_5), 3 ); |
252 | BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(), 3 ); |
253 | } |
254 | |
255 | |
256 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
257 | void interval_set_distinct_4_bicremental_continuous_types() |
258 | { |
259 | typedef IntervalSet<T> IntervalSetT; |
260 | typedef typename IntervalSetT::interval_type IntervalT; |
261 | typedef typename IntervalSet<T>::size_type size_T; |
262 | typedef typename IntervalSet<T>::difference_type diff_T; |
263 | T v1 = make<T>(1); |
264 | T v3 = make<T>(3); |
265 | T v5 = make<T>(5); |
266 | |
267 | size_T s3 = make<size_T>(3); |
268 | diff_T d0 = make<diff_T>(0); |
269 | diff_T d2 = make<diff_T>(2); |
270 | |
271 | IntervalSet<T> is_1_3_5; |
272 | is_1_3_5.add(v1).add(v3).add(v5); |
273 | |
274 | BOOST_CHECK_EQUAL( cardinality(is_1_3_5), s3 ); |
275 | BOOST_CHECK_EQUAL( is_1_3_5.size(), s3 ); |
276 | BOOST_CHECK_EQUAL( icl::length(is_1_3_5), d0 ); |
277 | BOOST_CHECK_EQUAL( interval_count(is_1_3_5), 3 ); |
278 | BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(), 3 ); |
279 | BOOST_CHECK_EQUAL( iterative_size(is_1_3_5), 3 ); |
280 | |
281 | |
282 | |
283 | IntervalSet<T> is_123_5; |
284 | is_123_5 = is_1_3_5; |
285 | is_123_5 += IntervalT::open(v1,v3); |
286 | |
287 | BOOST_CHECK_EQUAL( cardinality(is_123_5), icl::infinity<size_T>::value() ); |
288 | BOOST_CHECK_EQUAL( is_123_5.size(), icl::infinity<size_T>::value() ); |
289 | BOOST_CHECK_EQUAL( icl::length(is_123_5), d2 ); |
290 | } |
291 | |
292 | |
293 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
294 | void interval_set_isolate_4_bicremental_continuous_types() |
295 | { |
296 | typedef IntervalSet<T> IntervalSetT; |
297 | typedef typename IntervalSetT::interval_type IntervalT; |
298 | typedef typename IntervalSet<T>::size_type size_T; |
299 | |
300 | T v0 = make<T>(0); |
301 | T v2 = make<T>(2); |
302 | T v4 = make<T>(4); |
303 | IntervalT I0_4I = IntervalT::closed(v0,v4); |
304 | IntervalT C0_2D = IntervalT::open(v0,v2); |
305 | IntervalT C2_4D = IntervalT::open(v2,v4); |
306 | // {[0 4]} |
307 | // - { (0,2) (2,4) } |
308 | // = {[0] [2] [4]} |
309 | IntervalSet<T> iso_set = IntervalSet<T>(I0_4I); |
310 | IntervalSet<T> gap_set; |
311 | gap_set.add(C0_2D).add(C2_4D); |
312 | BOOST_CHECK_EQUAL( true, true ); |
313 | iso_set -= gap_set; |
314 | |
315 | BOOST_CHECK_EQUAL( cardinality(iso_set), static_cast<size_T>(3) ); |
316 | BOOST_CHECK_EQUAL( iso_set.iterative_size(), static_cast<std::size_t>(3) ); |
317 | BOOST_CHECK_EQUAL( iterative_size(iso_set), static_cast<std::size_t>(3) ); |
318 | |
319 | IntervalSet<T> iso_set2; |
320 | iso_set2.add(I0_4I); |
321 | iso_set2.subtract(C0_2D).subtract(C2_4D); |
322 | |
323 | IntervalSet<T> iso_set3(I0_4I); |
324 | (iso_set3 -= C0_2D) -= C2_4D; |
325 | |
326 | IntervalSet<T> iso_set4; |
327 | iso_set4.insert(I0_4I); |
328 | iso_set4.erase(C0_2D).erase(C2_4D); |
329 | |
330 | BOOST_CHECK_EQUAL( iso_set, iso_set2 ); |
331 | BOOST_CHECK_EQUAL( iso_set, iso_set3 ); |
332 | BOOST_CHECK_EQUAL( iso_set, iso_set4 ); |
333 | } |
334 | |
335 | |
336 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
337 | void interval_set_element_compare_4_bicremental_types() |
338 | { |
339 | typedef IntervalSet<T> ISet; |
340 | |
341 | BOOST_CHECK_EQUAL( is_element_equal( ISet(), ISet()), true ); |
342 | BOOST_CHECK_EQUAL( is_element_equal( ISet(), ISet(I_D(0,1))), false ); |
343 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet()), false ); |
344 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet(I_D(0,1))), true ); |
345 | |
346 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,5)), ISet(I_D(3,8))), false ); |
347 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(3,8)), ISet(I_D(0,5))), false ); |
348 | |
349 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet(I_D(0,1)) ), true ); |
350 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet(I_D(0,1))+I_D(1,2) ), false ); |
351 | BOOST_CHECK_EQUAL( is_element_equal( I_D(1,2)+ISet(I_D(0,1)), ISet(I_D(0,1)) ), false ); |
352 | 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 ); |
353 | |
354 | //[0 1)[1 2) |
355 | //[0 2) |
356 | BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(1,2)), ISet(I_D(0,2)) ), true ); |
357 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,2)), ISet(I_D(0,1))+I_D(1,2) ), true ); |
358 | |
359 | //[0 1) [2 3) |
360 | //[0 3) |
361 | BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(2,3)), ISet(I_D(0,3)) ), false ); |
362 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,3)), ISet(I_D(0,1))+I_D(2,3) ), false ); |
363 | |
364 | //[0 2)[2 4) |
365 | // [1 4) |
366 | BOOST_CHECK_EQUAL( is_element_equal( I_D(0,2)+ISet(I_D(2,4)), ISet(I_D(1,4)) ), false ); |
367 | BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(1,4)), ISet(I_D(0,2))+I_D(2,4) ), false ); |
368 | |
369 | //[0 2)[2 4) |
370 | //[0 1)[1 3)[3 4) |
371 | 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 ); |
372 | 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 ); |
373 | } |
374 | |
375 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
376 | void interval_set_contains_4_bicremental_types() |
377 | { |
378 | typedef IntervalSet<T> IntervalSetT; |
379 | typedef typename IntervalSetT::interval_type IntervalT; |
380 | //LAW: x.add(e).contains(e); |
381 | //LAW: z = x + y => contains(z, x) && contains(z, y); |
382 | T v1 = make<T>(1); |
383 | T v3 = make<T>(3); |
384 | T v5 = make<T>(5); |
385 | T v7 = make<T>(7); |
386 | T v8 = make<T>(8); |
387 | T v9 = make<T>(9); |
388 | T v11 = make<T>(11); |
389 | IntervalSet<T> is(v1); |
390 | BOOST_CHECK_EQUAL( icl::contains(is, v1), true ); |
391 | |
392 | BOOST_CHECK_EQUAL( icl::contains(IntervalSet<T>().add(make<T>(2)), make<T>(2)), true ); |
393 | BOOST_CHECK_EQUAL( icl::contains(IntervalSet<T>().insert(make<T>(2)), make<T>(2)), true ); |
394 | BOOST_CHECK_EQUAL( icl::contains((is += IntervalT(v3,v7)), IntervalT(v3,v7)), true ); |
395 | |
396 | IntervalSet<T> is0 = is; |
397 | |
398 | IntervalSet<T> is2(IntervalT::closed(v5,v8)); |
399 | is2.add(v9).add(v11); |
400 | is += is2; |
401 | BOOST_CHECK_EQUAL( contains(is, is2), true ); |
402 | |
403 | is = is0; |
404 | IntervalSet<T> is3(IntervalT::closed(v5,v8)); |
405 | is3.insert(v9).insert(v11); |
406 | is += is3; |
407 | BOOST_CHECK_EQUAL( contains(is, is3), true ); |
408 | } |
409 | |
410 | |
411 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
412 | void interval_set_operators_4_bicremental_types() |
413 | { |
414 | typedef IntervalSet<T> IntervalSetT; |
415 | typedef typename IntervalSetT::interval_type IntervalT; |
416 | T v0 = make<T>(0); |
417 | T v1 = make<T>(1); |
418 | T v3 = make<T>(3); |
419 | T v5 = make<T>(5); |
420 | T v7 = make<T>(7); |
421 | T v8 = make<T>(8); |
422 | IntervalSet<T> left, left2, right, all, all2, section, complement, naught; |
423 | left.add(IntervalT::closed(v0,v1)).add(IntervalT::closed(v3,v5)); |
424 | (right += IntervalT::closed(v3,v5)) += IntervalT::closed(v7,v8); |
425 | |
426 | BOOST_CHECK_EQUAL( disjoint(left, right), false ); |
427 | |
428 | (all += left) += right; |
429 | (section += left) &= right; |
430 | (complement += all) -= section; |
431 | (all2 += section) += complement; |
432 | |
433 | BOOST_CHECK_EQUAL( disjoint(section, complement), true ); |
434 | BOOST_CHECK_EQUAL( all, all2 ); |
435 | |
436 | BOOST_CHECK_EQUAL( icl::contains(all, left), true ); |
437 | BOOST_CHECK_EQUAL( icl::contains(all, right), true ); |
438 | BOOST_CHECK_EQUAL( icl::contains(all, complement), true ); |
439 | |
440 | BOOST_CHECK_EQUAL( icl::contains(left, section), true ); |
441 | BOOST_CHECK_EQUAL( icl::contains(right, section), true ); |
442 | |
443 | BOOST_CHECK_EQUAL( within(left, all), true ); |
444 | BOOST_CHECK_EQUAL( within(right, all), true ); |
445 | BOOST_CHECK_EQUAL( within(complement, all), true ); |
446 | BOOST_CHECK_EQUAL( within(section, left), true ); |
447 | BOOST_CHECK_EQUAL( within(section, right), true ); |
448 | } |
449 | |
450 | |
451 | // Test for nontrivial intersection of interval sets with intervals and values |
452 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
453 | void interval_set_base_intersect_4_bicremental_types() |
454 | { |
455 | typedef IntervalSet<T> IntervalSetT; |
456 | typedef typename IntervalSetT::interval_type IntervalT; |
457 | T v0 = make<T>(0); |
458 | T v1 = make<T>(1); |
459 | T v2 = make<T>(2); |
460 | T v3 = make<T>(3); |
461 | T v6 = make<T>(6); |
462 | T v7 = make<T>(7); |
463 | T v8 = make<T>(8); |
464 | T v9 = make<T>(9); |
465 | |
466 | IntervalT I0_3D = IntervalT::right_open(v0,v3); |
467 | IntervalT I1_3D = IntervalT::right_open(v1,v3); |
468 | IntervalT I1_8D = IntervalT::right_open(v1,v8); |
469 | IntervalT I2_7D = IntervalT::right_open(v2,v7); |
470 | IntervalT I2_3D = IntervalT::right_open(v2,v3); |
471 | IntervalT I6_7D = IntervalT::right_open(v6,v7); |
472 | IntervalT I6_8D = IntervalT::right_open(v6,v8); |
473 | IntervalT I6_9D = IntervalT::right_open(v6,v9); |
474 | |
475 | //-------------------------------------------------------------------------- |
476 | // IntervalSet |
477 | //-------------------------------------------------------------------------- |
478 | //split_A [0 3) [6 9) |
479 | // &= [1 8) |
480 | //split_AB -> [1 3) [6 8) |
481 | // &= [2 7) |
482 | // -> [2 3) [6 7) |
483 | IntervalSet<T> split_A, split_B, split_AB, split_ab, split_ab2; |
484 | |
485 | split_A.add(I0_3D).add(I6_9D); |
486 | split_AB = split_A; |
487 | split_AB &= I1_8D; |
488 | split_ab.add(I1_3D).add(I6_8D); |
489 | |
490 | BOOST_CHECK_EQUAL( split_AB, split_ab ); |
491 | |
492 | split_AB = split_A; |
493 | (split_AB &= I1_8D) &= I2_7D; |
494 | split_ab2.add(I2_3D).add(I6_7D); |
495 | |
496 | BOOST_CHECK_EQUAL( split_AB, split_ab2 ); |
497 | |
498 | |
499 | //-------------------------------------------------------------------------- |
500 | //split_A [0 3) [6 9) |
501 | // &= 1 |
502 | //split_AB -> [1] |
503 | // += (1 7) |
504 | // -> [1](1 7) |
505 | split_A.add(I0_3D).add(I6_9D); |
506 | split_AB = split_A; |
507 | split_AB &= v1; |
508 | split_ab.clear(); |
509 | split_ab.add(v1); |
510 | |
511 | BOOST_CHECK_EQUAL( split_AB, split_ab ); |
512 | |
513 | split_AB = split_A; |
514 | (split_AB &= v1) += IntervalT::open(v1,v7); |
515 | split_ab2.clear(); |
516 | split_ab2 += IntervalT::right_open(v1,v7); |
517 | |
518 | BOOST_CHECK_EQUAL( is_element_equal(split_AB, split_ab2), true ); |
519 | } |
520 | |
521 | |
522 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
523 | void interval_set_flip_4_bicremental_types() |
524 | { |
525 | typedef IntervalSet<T> IntervalSetT; |
526 | typedef IntervalSetT ISet; |
527 | |
528 | IntervalSetT set_a, set_b, lhs, rhs; |
529 | //[0 2) |
530 | // [1 3) |
531 | //[0 1) [2 3) : {[0 2)} ^= [2 3) |
532 | //gcc seed ambiguities with std::_Ios_Iostate& std::operator^= here: |
533 | // BOOST_CHECK_EQUAL(ISet(I_D(0,2)) ^= I_D(1,3), ISet(I_D(0,1)) + I_D(2,3)); |
534 | set_a = ISet(I_D(0,2)); |
535 | BOOST_CHECK_EQUAL(set_a ^= I_D(1,3), ISet(I_D(0,1)) + I_D(2,3)); |
536 | |
537 | // [1 3) |
538 | //[0 2) |
539 | //[0 1) [2 3) : {[1 3)} ^= [0 2) |
540 | set_a = ISet(I_D(1,3)); |
541 | BOOST_CHECK_EQUAL(set_a ^= I_D(0,2), ISet(I_D(0,1)) + I_D(2,3)); |
542 | |
543 | //[0 2) (3 5] |
544 | // [1 3) |
545 | //[0 1) [2 3) (3 5] : a ^= b |
546 | set_a.clear(); |
547 | set_a.add(I_D(0,2)).add(C_I(3,5)); |
548 | set_b.add(I_D(1,3)); |
549 | lhs = set_a; |
550 | lhs ^= set_b; |
551 | rhs.add(I_D(0,1)).add(I_D(2,3)).add(C_I(3,5)); |
552 | BOOST_CHECK_EQUAL(lhs, rhs); |
553 | } |
554 | |
555 | |
556 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
557 | void interval_set_infix_plus_overload_4_bicremental_types() |
558 | { |
559 | typedef IntervalSet<T> IntervalSetT; |
560 | typedef typename IntervalSetT::interval_type IntervalT; |
561 | IntervalT itv = I_D(3,5); |
562 | |
563 | IntervalSetT set_a, set_b; |
564 | set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11)); |
565 | set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7)); |
566 | |
567 | BOOST_CHECK_EQUAL(set_a + set_b, set_b + set_a); |
568 | // This checks all cases of is_interval_set_derivative<T> |
569 | BOOST_CHECK_EQUAL(set_a + itv, itv + set_a); |
570 | BOOST_CHECK_EQUAL(set_b + MK_v(4), MK_v(4) + set_b); |
571 | } |
572 | |
573 | |
574 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
575 | void interval_set_infix_pipe_overload_4_bicremental_types() |
576 | { |
577 | typedef IntervalSet<T> IntervalSetT; |
578 | typedef typename IntervalSetT::interval_type IntervalT; |
579 | |
580 | IntervalT itv = I_D(3,5); |
581 | |
582 | IntervalSetT set_a, set_b; |
583 | set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11)); |
584 | set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7)); |
585 | |
586 | BOOST_CHECK_EQUAL(set_a | set_b, set_b | set_a); |
587 | //This checks all cases of is_interval_set_derivative<T> |
588 | BOOST_CHECK_EQUAL(set_a | itv, itv | set_a); |
589 | BOOST_CHECK_EQUAL(set_b | MK_v(4), MK_v(4) | set_b); |
590 | } |
591 | |
592 | |
593 | |
594 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
595 | void interval_set_infix_minus_overload_4_bicremental_types() |
596 | { |
597 | typedef IntervalSet<T> IntervalSetT; |
598 | typedef typename IntervalSetT::interval_type IntervalT; |
599 | |
600 | IntervalT itv = I_D(3,5); |
601 | |
602 | IntervalSetT set_a, set_b; |
603 | set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11)); |
604 | set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7)); |
605 | |
606 | BOOST_CHECK_EQUAL(set_a - set_b, (set_b + set_a) - set_b); |
607 | //This checks all cases of is_interval_set_derivative<T> |
608 | BOOST_CHECK_EQUAL(set_a - itv, (itv + set_a) - itv); |
609 | BOOST_CHECK_EQUAL(set_b - MK_v(4), (MK_v(4) + set_b) - MK_v(4)); |
610 | } |
611 | |
612 | |
613 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
614 | void interval_set_infix_et_overload_4_bicremental_types() |
615 | { |
616 | typedef IntervalSet<T> IntervalSetT; |
617 | typedef typename IntervalSetT::interval_type IntervalT; |
618 | |
619 | IntervalT itv = I_D(3,5); |
620 | |
621 | IntervalSetT set_a, set_b; |
622 | set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11)); |
623 | set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7)); |
624 | |
625 | BOOST_CHECK_EQUAL(set_a & set_b, set_b & set_a); |
626 | //This checks all cases of is_interval_set_derivative<T> |
627 | BOOST_CHECK_EQUAL(set_a & itv, itv & set_a); |
628 | BOOST_CHECK_EQUAL(set_b & MK_v(4), MK_v(4) & set_b); |
629 | } |
630 | |
631 | |
632 | |
633 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
634 | void interval_set_infix_caret_overload_4_bicremental_types() |
635 | { |
636 | typedef IntervalSet<T> IntervalSetT; |
637 | typedef typename IntervalSetT::interval_type IntervalT; |
638 | |
639 | IntervalT itv = I_D(3,5); |
640 | |
641 | IntervalSetT set_a, set_b; |
642 | set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11)); |
643 | set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7)); |
644 | |
645 | BOOST_CHECK_EQUAL(set_a ^ set_b, set_b ^ set_a); |
646 | //This checks all cases of is_interval_set_derivative<T> |
647 | BOOST_CHECK_EQUAL(set_a ^ itv, itv ^ set_a); |
648 | BOOST_CHECK_EQUAL(set_b ^ MK_v(4), MK_v(4) ^ set_b); |
649 | } |
650 | |
651 | |
652 | |
653 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
654 | void interval_set_find_4_bicremental_types() |
655 | { |
656 | typedef IntervalSet<T> IntervalSetT; |
657 | typedef typename IntervalSetT::const_iterator c_iterator; |
658 | |
659 | IntervalSetT set_a; |
660 | set_a.add(C_D(1,3)).add(I_I(6,11)); |
661 | |
662 | typename IntervalSetT::const_iterator found = set_a.find(MK_v(6)); |
663 | |
664 | BOOST_CHECK_EQUAL( *found, I_I(6,11) ); |
665 | |
666 | found = set_a.find(MK_v(5)); |
667 | |
668 | BOOST_CHECK_EQUAL( found == set_a.end(), true ); |
669 | |
670 | c_iterator found1 = set_a.find(MK_v(6)); |
671 | c_iterator found2 = icl::find(set_a, MK_v(6)); |
672 | |
673 | BOOST_CHECK ( found1 == found2 ); |
674 | BOOST_CHECK_EQUAL( *found1, *found2 ); |
675 | BOOST_CHECK_EQUAL( *found1, I_I(6,11) ); |
676 | |
677 | found1 = set_a.find(MK_v(5)); |
678 | |
679 | BOOST_CHECK_EQUAL( found1 == set_a.end(), true ); |
680 | |
681 | //LAW map c; key k: k in dom(c) => contains(c, *find(c, k)) |
682 | BOOST_CHECK( icl::contains(set_a, *icl::find(set_a, MK_v(2))) ); |
683 | BOOST_CHECK( icl::contains(set_a, *set_a.find(MK_v(11))) ); |
684 | |
685 | BOOST_CHECK( icl::contains(set_a, MK_v(2)) ); |
686 | BOOST_CHECK( icl::contains(set_a, MK_v(10)) ); |
687 | BOOST_CHECK( !icl::contains(set_a, MK_v(1)) ); |
688 | BOOST_CHECK( !icl::contains(set_a, MK_v(3)) ); |
689 | |
690 | BOOST_CHECK( icl::intersects(set_a, MK_v(2)) ); |
691 | BOOST_CHECK( icl::intersects(set_a, MK_v(10)) ); |
692 | BOOST_CHECK( !icl::intersects(set_a, MK_v(1)) ); |
693 | BOOST_CHECK( !icl::intersects(set_a, MK_v(3)) ); |
694 | } |
695 | |
696 | |
697 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
698 | void interval_set_intersects_4_bicremental_types() |
699 | { |
700 | typedef IntervalSet<T> IntervalSetT; |
701 | typedef typename IntervalSetT::interval_type IntervalT; |
702 | |
703 | IntervalT between = I_D(3,5); |
704 | |
705 | IntervalSetT set_a; |
706 | set_a.add(C_D(1,3)).add(I_I(6,11)); |
707 | // (1 3) [6 11] |
708 | BOOST_CHECK( icl::intersects(set_a, MK_v(2)) ); |
709 | BOOST_CHECK( icl::intersects(set_a, MK_v(11)) ); |
710 | BOOST_CHECK( icl::disjoint(set_a, MK_v(3)) ); |
711 | BOOST_CHECK( icl::disjoint(set_a, MK_v(5)) ); |
712 | |
713 | BOOST_CHECK( icl::intersects(set_a, C_D(1,3)) ); |
714 | BOOST_CHECK( icl::intersects(set_a, I_D(8,10)) ); |
715 | BOOST_CHECK( icl::disjoint(set_a, between) ); |
716 | BOOST_CHECK( icl::disjoint(set_a, I_I(0,1)) ); |
717 | |
718 | IntervalSetT to_12 = IntervalSetT(I_D(0, 13)); |
719 | IntervalSetT complement_a = to_12 - set_a; |
720 | BOOST_CHECK( icl::disjoint(set_a, complement_a) ); |
721 | BOOST_CHECK( icl::intersects(to_12, set_a) ); |
722 | |
723 | BOOST_CHECK_EQUAL( icl::lower(set_a), icl::lower(*(set_a.begin())) ); |
724 | BOOST_CHECK_EQUAL( icl::lower(set_a), MK_v(1) ); |
725 | BOOST_CHECK_EQUAL( icl::upper(set_a), icl::upper(*(set_a.rbegin())) ); |
726 | BOOST_CHECK_EQUAL( icl::upper(set_a), MK_v(11) ); |
727 | } |
728 | |
729 | |
730 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
731 | void interval_set_range_4_discrete_types() |
732 | { |
733 | typedef IntervalSet<T> IntervalSetT; |
734 | |
735 | IntervalSetT set_a; |
736 | set_a.add(C_D(1,3)).add(I_I(6,11)); |
737 | // (1 3) [6 11] |
738 | BOOST_CHECK_EQUAL( icl::first(set_a), icl::first(*(set_a.begin())) ); |
739 | BOOST_CHECK_EQUAL( icl::first(set_a), MK_v(2) ); |
740 | BOOST_CHECK_EQUAL( icl::last(set_a), icl::last(*(set_a.rbegin())) ); |
741 | BOOST_CHECK_EQUAL( icl::last(set_a), MK_v(11) ); |
742 | } |
743 | |
744 | |
745 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
746 | void interval_bitset_find_4_integral_types() |
747 | { |
748 | typedef IntervalSet<T> IntervalSetT; |
749 | typedef typename IntervalSetT::interval_type IntervalT; |
750 | |
751 | IntervalT itv = I_D(3,5); |
752 | |
753 | IntervalSetT set_a; |
754 | set_a.add(C_D(1,3)).add(I_I(6,11)); |
755 | |
756 | typename IntervalSetT::const_iterator found = set_a.find(MK_v(6)); |
757 | |
758 | BOOST_CHECK( (found->second).contains(6) ); |
759 | |
760 | found = set_a.find(MK_v(5)); |
761 | BOOST_CHECK( found == set_a.end() ); |
762 | |
763 | set_a.add(MK_v(64)); |
764 | found = set_a.find(MK_v(64)); |
765 | BOOST_CHECK( (found->second).contains(0) ); |
766 | |
767 | set_a.add(MK_v(65)); |
768 | found = set_a.find(MK_v(65)); |
769 | BOOST_CHECK( (found->second).contains(1) ); |
770 | |
771 | found = set_a.find(MK_v(66)); |
772 | BOOST_CHECK( found == set_a.end() ); |
773 | } |
774 | |
775 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
776 | void interval_set_element_iter_4_discrete_types() |
777 | { |
778 | typedef IntervalSet<T> IntervalSetT; |
779 | typedef std::vector<T> VectorT; |
780 | |
781 | IntervalSetT set_a; |
782 | set_a.add(I_I(1,3)).add(I_I(6,7)); |
783 | |
784 | VectorT vec(5), cev(5); |
785 | 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); |
786 | 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); |
787 | |
788 | VectorT dest; |
789 | // element iteration ----------------------------------------------------- |
790 | std::copy(elements_begin(set_a), elements_end(set_a), std::back_inserter(dest)); |
791 | BOOST_CHECK_EQUAL( vec == dest, true ); |
792 | |
793 | dest.clear(); |
794 | std::copy(elements_rbegin(set_a), elements_rend(set_a), std::back_inserter(dest)); |
795 | BOOST_CHECK_EQUAL( cev == dest, true ); |
796 | |
797 | dest.clear(); |
798 | std::reverse_copy(elements_begin(set_a), elements_end(set_a), std::back_inserter(dest)); |
799 | BOOST_CHECK_EQUAL( cev == dest, true ); |
800 | |
801 | dest.clear(); |
802 | std::reverse_copy(elements_rbegin(set_a), elements_rend(set_a), std::back_inserter(dest)); |
803 | BOOST_CHECK_EQUAL( vec == dest, true ); |
804 | |
805 | // range based element iteration ----------------------------------------- |
806 | dest.clear(); |
807 | boost::copy(elements(set_a), std::back_inserter(dest)); |
808 | BOOST_CHECK( vec == dest ); |
809 | |
810 | dest.clear(); |
811 | boost::reverse_copy(elements(set_a), std::back_inserter(dest)); |
812 | BOOST_CHECK( cev == dest ); |
813 | } |
814 | |
815 | |
816 | template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T> |
817 | void interval_set_move_4_discrete_types() |
818 | { |
819 | typedef IntervalSet<T> IntervalSetT; |
820 | |
821 | //JODO static_cast fails for gcc compilers |
822 | //IntervalSetT set_A(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,4))))); |
823 | IntervalSetT set_A(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,4)).add(I_D(0,0)) ))); |
824 | IntervalSetT set_B(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,2)).add(I_D(2,4)).add(I_D(0,4))))); |
825 | |
826 | BOOST_CHECK( icl::is_element_equal(set_A, set_B) ); |
827 | BOOST_CHECK_EQUAL( set_A, join(set_B) ); |
828 | |
829 | //JODO static_cast fails for gcc compilers |
830 | //set_A = boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_I(1,4)))); |
831 | set_A = boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_I(1,4)).add(I_D(0,0)))); |
832 | set_B = boost::move(static_cast<IntervalSetT&>(IntervalSetT(C_I(0,2)).insert(I_D(3,5)).add(C_D(0,5)))); |
833 | |
834 | BOOST_CHECK( icl::is_element_equal(set_A, set_B) ); |
835 | BOOST_CHECK_EQUAL( set_A, join(set_B) ); |
836 | } |
837 | |
838 | |
839 | |
840 | #endif // LIBS_ICL_TEST_TEST_INTERVAL_SET_SHARED_HPP_JOFA_080920 |
841 | |