]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*-----------------------------------------------------------------------------+ |
2 | Copyright (c) 2010-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 BOOST_ICL_CONCEPT_INTERVAL_HPP_JOFA_100323 | |
9 | #define BOOST_ICL_CONCEPT_INTERVAL_HPP_JOFA_100323 | |
10 | ||
11 | #include <boost/assert.hpp> | |
12 | #include <boost/utility/enable_if.hpp> | |
13 | #include <boost/mpl/and.hpp> | |
14 | #include <boost/mpl/or.hpp> | |
15 | #include <boost/mpl/not.hpp> | |
16 | #include <boost/icl/detail/design_config.hpp> | |
17 | #include <boost/icl/type_traits/unit_element.hpp> | |
18 | #include <boost/icl/type_traits/identity_element.hpp> | |
19 | #include <boost/icl/type_traits/infinity.hpp> | |
20 | #include <boost/icl/type_traits/succ_pred.hpp> | |
21 | #include <boost/icl/type_traits/is_numeric.hpp> | |
22 | #include <boost/icl/type_traits/is_discrete.hpp> | |
23 | #include <boost/icl/type_traits/is_continuous.hpp> | |
24 | #include <boost/icl/type_traits/is_asymmetric_interval.hpp> | |
25 | #include <boost/icl/type_traits/is_discrete_interval.hpp> | |
26 | #include <boost/icl/type_traits/is_continuous_interval.hpp> | |
27 | ||
28 | #include <boost/icl/concept/interval_bounds.hpp> | |
29 | #include <boost/icl/interval_traits.hpp> | |
30 | #include <boost/icl/dynamic_interval_traits.hpp> | |
31 | ||
32 | ||
33 | namespace boost{namespace icl | |
34 | { | |
35 | ||
36 | //============================================================================== | |
37 | //= Ordering | |
38 | //============================================================================== | |
39 | template<class Type> | |
40 | inline typename enable_if<is_interval<Type>, bool>::type | |
41 | domain_less(const typename interval_traits<Type>::domain_type& left, | |
42 | const typename interval_traits<Type>::domain_type& right) | |
43 | { | |
44 | return typename interval_traits<Type>::domain_compare()(left, right); | |
45 | } | |
46 | ||
47 | template<class Type> | |
48 | inline typename enable_if<is_interval<Type>, bool>::type | |
49 | domain_less_equal(const typename interval_traits<Type>::domain_type& left, | |
50 | const typename interval_traits<Type>::domain_type& right) | |
51 | { | |
52 | return !(typename interval_traits<Type>::domain_compare()(right, left)); | |
53 | } | |
54 | ||
55 | template<class Type> | |
56 | inline typename enable_if<is_interval<Type>, bool>::type | |
57 | domain_equal(const typename interval_traits<Type>::domain_type& left, | |
58 | const typename interval_traits<Type>::domain_type& right) | |
59 | { | |
60 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
61 | return !(domain_compare()(left, right)) && !(domain_compare()(right, left)); | |
62 | } | |
63 | ||
64 | template<class Type> | |
65 | inline typename enable_if< is_interval<Type> | |
66 | , typename interval_traits<Type>::domain_type>::type | |
67 | domain_next(const typename interval_traits<Type>::domain_type value) | |
68 | { | |
69 | typedef typename interval_traits<Type>::domain_type domain_type; | |
70 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
71 | return icl::successor<domain_type,domain_compare>::apply(value); | |
72 | } | |
73 | ||
74 | template<class Type> | |
75 | inline typename enable_if< is_interval<Type> | |
76 | , typename interval_traits<Type>::domain_type>::type | |
77 | domain_prior(const typename interval_traits<Type>::domain_type value) | |
78 | { | |
79 | typedef typename interval_traits<Type>::domain_type domain_type; | |
80 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
81 | return icl::predecessor<domain_type,domain_compare>::apply(value); | |
82 | } | |
83 | ||
84 | //============================================================================== | |
85 | //= Construct<Interval> singleton | |
86 | //============================================================================== | |
87 | template<class Type> | |
88 | typename enable_if | |
89 | < | |
90 | mpl::and_< is_static_right_open<Type> | |
91 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
92 | , Type | |
93 | >::type | |
94 | singleton(const typename interval_traits<Type>::domain_type& value) | |
95 | { | |
96 | //ASSERT: This always creates an interval with exactly one element | |
97 | return interval_traits<Type>::construct(value, domain_next<Type>(value)); | |
98 | } | |
99 | ||
100 | template<class Type> | |
101 | typename enable_if | |
102 | < | |
103 | mpl::and_< is_static_left_open<Type> | |
104 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
105 | , Type | |
106 | >::type | |
107 | singleton(const typename interval_traits<Type>::domain_type& value) | |
108 | { | |
109 | //ASSERT: This always creates an interval with exactly one element | |
110 | typedef typename interval_traits<Type>::domain_type domain_type; | |
111 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
112 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
113 | ::is_less_than(value) )); | |
114 | ||
115 | return interval_traits<Type>::construct(domain_prior<Type>(value), value); | |
116 | } | |
117 | ||
118 | template<class Type> | |
119 | typename enable_if<is_discrete_static_open<Type>, Type>::type | |
120 | singleton(const typename interval_traits<Type>::domain_type& value) | |
121 | { | |
122 | //ASSERT: This always creates an interval with exactly one element | |
123 | typedef typename interval_traits<Type>::domain_type domain_type; | |
124 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
125 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
126 | ::is_less_than(value))); | |
127 | ||
128 | return interval_traits<Type>::construct( domain_prior<Type>(value) | |
129 | , domain_next<Type>(value)); | |
130 | } | |
131 | ||
132 | template<class Type> | |
133 | typename enable_if<is_discrete_static_closed<Type>, Type>::type | |
134 | singleton(const typename interval_traits<Type>::domain_type& value) | |
135 | { | |
136 | //ASSERT: This always creates an interval with exactly one element | |
137 | return interval_traits<Type>::construct(value, value); | |
138 | } | |
139 | ||
140 | template<class Type> | |
141 | typename enable_if<has_dynamic_bounds<Type>, Type>::type | |
142 | singleton(const typename interval_traits<Type>::domain_type& value) | |
143 | { | |
144 | return dynamic_interval_traits<Type>::construct(value, value, interval_bounds::closed()); | |
145 | } | |
146 | ||
147 | namespace detail | |
148 | { | |
149 | ||
150 | //============================================================================== | |
151 | //= Construct<Interval> unit_trail == generalized singleton | |
152 | // The smallest interval on an incrementable (and decrementable) type that can | |
153 | // be constructed using ++ and -- and such that it contains a given value. | |
154 | // If 'Type' is discrete, 'unit_trail' and 'singleton' are identical. So we | |
155 | // can view 'unit_trail' as a generalized singleton for static intervals of | |
156 | // continuous types. | |
157 | //============================================================================== | |
158 | template<class Type> | |
159 | typename enable_if | |
160 | < | |
161 | mpl::and_< is_static_right_open<Type> | |
162 | , boost::detail::is_incrementable<typename interval_traits<Type>::domain_type> > | |
163 | , Type | |
164 | >::type | |
165 | unit_trail(const typename interval_traits<Type>::domain_type& value) | |
166 | { | |
167 | return interval_traits<Type>::construct(value, domain_next<Type>(value)); | |
168 | } | |
169 | ||
170 | template<class Type> | |
171 | typename enable_if | |
172 | < | |
173 | mpl::and_< is_static_left_open<Type> | |
174 | , boost::detail::is_incrementable<typename interval_traits<Type>::domain_type> > | |
175 | , Type | |
176 | >::type | |
177 | unit_trail(const typename interval_traits<Type>::domain_type& value) | |
178 | { | |
179 | typedef typename interval_traits<Type>::domain_type domain_type; | |
180 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
181 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
182 | ::is_less_than(value) )); | |
183 | ||
184 | return interval_traits<Type>::construct(domain_prior<Type>(value), value); | |
185 | } | |
186 | ||
187 | template<class Type> | |
188 | typename enable_if | |
189 | < | |
190 | mpl::and_< is_static_open<Type> | |
191 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
192 | , Type | |
193 | >::type | |
194 | unit_trail(const typename interval_traits<Type>::domain_type& value) | |
195 | { | |
196 | typedef typename interval_traits<Type>::domain_type domain_type; | |
197 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
198 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
199 | ::is_less_than(value))); | |
200 | ||
201 | return interval_traits<Type>::construct( domain_prior<Type>(value) | |
202 | , domain_next<Type>(value)); | |
203 | } | |
204 | ||
205 | template<class Type> | |
206 | typename enable_if | |
207 | < | |
208 | mpl::and_< is_static_closed<Type> | |
209 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
210 | , Type | |
211 | >::type | |
212 | unit_trail(const typename interval_traits<Type>::domain_type& value) | |
213 | { | |
214 | return interval_traits<Type>::construct(value, value); | |
215 | } | |
216 | ||
217 | //NOTE: statically bounded closed or open intervals of continuous domain types | |
218 | // are NOT supported by ICL. They can not be used with interval containers | |
219 | // consistently. | |
220 | ||
221 | ||
222 | template<class Type> | |
223 | typename enable_if<has_dynamic_bounds<Type>, Type>::type | |
224 | unit_trail(const typename interval_traits<Type>::domain_type& value) | |
225 | { | |
226 | return dynamic_interval_traits<Type>::construct(value, value, interval_bounds::closed()); | |
227 | } | |
228 | ||
229 | } //namespace detail | |
230 | ||
231 | //============================================================================== | |
232 | //= Construct<Interval> multon | |
233 | //============================================================================== | |
234 | template<class Type> | |
235 | typename enable_if<has_static_bounds<Type>, Type>::type | |
236 | construct(const typename interval_traits<Type>::domain_type& low, | |
237 | const typename interval_traits<Type>::domain_type& up ) | |
238 | { | |
239 | return interval_traits<Type>::construct(low, up); | |
240 | } | |
241 | ||
242 | template<class Type> | |
243 | typename enable_if<has_dynamic_bounds<Type>, Type>::type | |
244 | construct(const typename interval_traits<Type>::domain_type& low, | |
245 | const typename interval_traits<Type>::domain_type& up, | |
246 | interval_bounds bounds = interval_bounds::right_open()) | |
247 | { | |
248 | return dynamic_interval_traits<Type>::construct(low, up, bounds); | |
249 | } | |
250 | ||
251 | ||
252 | //- construct form bounded values ---------------------------------------------- | |
253 | template<class Type> | |
254 | typename enable_if<has_dynamic_bounds<Type>, Type>::type | |
255 | construct(const typename Type::bounded_domain_type& low, | |
256 | const typename Type::bounded_domain_type& up) | |
257 | { | |
258 | return dynamic_interval_traits<Type>::construct_bounded(low, up); | |
259 | } | |
260 | ||
261 | template<class Type> | |
262 | typename enable_if<is_interval<Type>, Type>::type | |
263 | span(const typename interval_traits<Type>::domain_type& left, | |
264 | const typename interval_traits<Type>::domain_type& right) | |
265 | { | |
266 | if(interval_traits<Type>::domain_compare()(left,right)) | |
267 | return construct<Type>(left, right); | |
268 | else | |
269 | return construct<Type>(right, left); | |
270 | } | |
271 | ||
272 | ||
273 | //============================================================================== | |
274 | template<class Type> | |
275 | typename enable_if<is_static_right_open<Type>, Type>::type | |
276 | hull(const typename interval_traits<Type>::domain_type& left, | |
277 | const typename interval_traits<Type>::domain_type& right) | |
278 | { | |
279 | if(interval_traits<Type>::domain_compare()(left,right)) | |
280 | return construct<Type>(left, domain_next<Type>(right)); | |
281 | else | |
282 | return construct<Type>(right, domain_next<Type>(left)); | |
283 | } | |
284 | ||
285 | template<class Type> | |
286 | typename enable_if<is_static_left_open<Type>, Type>::type | |
287 | hull(const typename interval_traits<Type>::domain_type& left, | |
288 | const typename interval_traits<Type>::domain_type& right) | |
289 | { | |
290 | typedef typename interval_traits<Type>::domain_type domain_type; | |
291 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
292 | if(interval_traits<Type>::domain_compare()(left,right)) | |
293 | { | |
294 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
295 | ::is_less_than(left) )); | |
296 | return construct<Type>(domain_prior<Type>(left), right); | |
297 | } | |
298 | else | |
299 | { | |
300 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
301 | ::is_less_than(right) )); | |
302 | return construct<Type>(domain_prior<Type>(right), left); | |
303 | } | |
304 | } | |
305 | ||
306 | template<class Type> | |
307 | typename enable_if<is_static_closed<Type>, Type>::type | |
308 | hull(const typename interval_traits<Type>::domain_type& left, | |
309 | const typename interval_traits<Type>::domain_type& right) | |
310 | { | |
311 | if(interval_traits<Type>::domain_compare()(left,right)) | |
312 | return construct<Type>(left, right); | |
313 | else | |
314 | return construct<Type>(right, left); | |
315 | } | |
316 | ||
317 | template<class Type> | |
318 | typename enable_if<is_static_open<Type>, Type>::type | |
319 | hull(const typename interval_traits<Type>::domain_type& left, | |
320 | const typename interval_traits<Type>::domain_type& right) | |
321 | { | |
322 | typedef typename interval_traits<Type>::domain_type domain_type; | |
323 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
324 | if(interval_traits<Type>::domain_compare()(left,right)) | |
325 | { | |
326 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
327 | ::is_less_than(left) )); | |
328 | return construct<Type>( domain_prior<Type>(left) | |
329 | , domain_next<Type>(right)); | |
330 | } | |
331 | else | |
332 | { | |
333 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
334 | ::is_less_than(right) )); | |
335 | return construct<Type>( domain_prior<Type>(right) | |
336 | , domain_next<Type>(left)); | |
337 | } | |
338 | } | |
339 | ||
340 | template<class Type> | |
341 | typename enable_if<has_dynamic_bounds<Type>, Type>::type | |
342 | hull(const typename interval_traits<Type>::domain_type& left, | |
343 | const typename interval_traits<Type>::domain_type& right) | |
344 | { | |
345 | if(interval_traits<Type>::domain_compare()(left,right)) | |
346 | return construct<Type>(left, right, interval_bounds::closed()); | |
347 | else | |
348 | return construct<Type>(right, left, interval_bounds::closed()); | |
349 | } | |
350 | ||
351 | //============================================================================== | |
352 | //= Selection | |
353 | //============================================================================== | |
354 | ||
355 | template<class Type> | |
356 | inline typename enable_if<is_interval<Type>, | |
357 | typename interval_traits<Type>::domain_type>::type | |
358 | lower(const Type& object) | |
359 | { | |
360 | return interval_traits<Type>::lower(object); | |
361 | } | |
362 | ||
363 | template<class Type> | |
364 | inline typename enable_if<is_interval<Type>, | |
365 | typename interval_traits<Type>::domain_type>::type | |
366 | upper(const Type& object) | |
367 | { | |
368 | return interval_traits<Type>::upper(object); | |
369 | } | |
370 | ||
371 | ||
372 | //- first ---------------------------------------------------------------------- | |
373 | template<class Type> | |
374 | inline typename | |
375 | enable_if< mpl::or_<is_static_right_open<Type>, is_static_closed<Type> > | |
376 | , typename interval_traits<Type>::domain_type>::type | |
377 | first(const Type& object) | |
378 | { | |
379 | return lower(object); | |
380 | } | |
381 | ||
382 | template<class Type> | |
383 | inline typename | |
384 | enable_if< mpl::and_< mpl::or_<is_static_left_open<Type>, is_static_open<Type> > | |
385 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
386 | , typename interval_traits<Type>::domain_type>::type | |
387 | first(const Type& object) | |
388 | { | |
389 | return domain_next<Type>(lower(object)); | |
390 | } | |
391 | ||
392 | template<class Type> | |
393 | inline typename enable_if<is_discrete_interval<Type>, | |
394 | typename interval_traits<Type>::domain_type>::type | |
395 | first(const Type& object) | |
396 | { | |
397 | return is_left_closed(object.bounds()) ? | |
398 | lower(object) : | |
399 | domain_next<Type>(lower(object)); | |
400 | } | |
401 | ||
402 | //- last ----------------------------------------------------------------------- | |
403 | template<class Type> | |
404 | inline typename | |
405 | enable_if< mpl::or_<is_static_left_open<Type>, is_static_closed<Type> > | |
406 | , typename interval_traits<Type>::domain_type>::type | |
407 | last(const Type& object) | |
408 | { | |
409 | return upper(object); | |
410 | } | |
411 | ||
412 | template<class Type> | |
413 | inline typename | |
414 | enable_if< mpl::and_< mpl::or_<is_static_right_open<Type>, is_static_open<Type> > | |
415 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
416 | , typename interval_traits<Type>::domain_type>::type | |
417 | last(const Type& object) | |
418 | { | |
419 | typedef typename interval_traits<Type>::domain_type domain_type; | |
420 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
421 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
422 | ::is_less_than(upper(object)) )); | |
423 | return domain_prior<Type>(upper(object)); | |
424 | } | |
425 | ||
426 | template<class Type> | |
427 | inline typename enable_if<is_discrete_interval<Type>, | |
428 | typename interval_traits<Type>::domain_type>::type | |
429 | last(const Type& object) | |
430 | { | |
431 | typedef typename interval_traits<Type>::domain_type domain_type; | |
432 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
433 | BOOST_ASSERT((numeric_minimum<domain_type, domain_compare, is_numeric<domain_type>::value> | |
434 | ::is_less_than_or(upper(object), is_right_closed(object.bounds())) )); | |
435 | return is_right_closed(object.bounds()) ? | |
436 | upper(object) : | |
437 | domain_prior<Type>(upper(object)); | |
438 | } | |
439 | ||
440 | //- last_next ------------------------------------------------------------------ | |
441 | template<class Type> | |
442 | inline typename | |
443 | enable_if< mpl::and_< mpl::or_<is_static_left_open<Type>, is_static_closed<Type> > | |
444 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
445 | , typename interval_traits<Type>::domain_type>::type | |
446 | last_next(const Type& object) | |
447 | { | |
448 | return domain_next<Type>(upper(object)); | |
449 | } | |
450 | ||
451 | template<class Type> | |
452 | inline typename | |
453 | enable_if< mpl::and_< mpl::or_<is_static_right_open<Type>, is_static_open<Type> > | |
454 | , is_discrete<typename interval_traits<Type>::domain_type> > | |
455 | , typename interval_traits<Type>::domain_type>::type | |
456 | last_next(const Type& object) | |
457 | { | |
458 | //CL typedef typename interval_traits<Type>::domain_type domain_type; | |
459 | return upper(object); // NOTE: last_next is implemented to avoid calling pred(object) | |
460 | } // For unsigned integral types this may cause underflow. | |
461 | ||
462 | template<class Type> | |
463 | inline typename enable_if<is_discrete_interval<Type>, | |
464 | typename interval_traits<Type>::domain_type>::type | |
465 | last_next(const Type& object) | |
466 | { | |
467 | return is_right_closed(object.bounds()) ? | |
468 | domain_next<Type>(upper(object)): | |
469 | upper(object) ; | |
470 | } | |
471 | ||
472 | //------------------------------------------------------------------------------ | |
473 | template<class Type> | |
474 | typename enable_if<has_dynamic_bounds<Type>, | |
475 | typename Type::bounded_domain_type>::type | |
476 | bounded_lower(const Type& object) | |
477 | { | |
478 | return typename | |
479 | Type::bounded_domain_type(lower(object), object.bounds().left()); | |
480 | } | |
481 | ||
482 | template<class Type> | |
483 | typename enable_if<has_dynamic_bounds<Type>, | |
484 | typename Type::bounded_domain_type>::type | |
485 | reverse_bounded_lower(const Type& object) | |
486 | { | |
487 | return typename | |
488 | Type::bounded_domain_type(lower(object), | |
489 | object.bounds().reverse_left()); | |
490 | } | |
491 | ||
492 | template<class Type> | |
493 | typename enable_if<has_dynamic_bounds<Type>, | |
494 | typename Type::bounded_domain_type>::type | |
495 | bounded_upper(const Type& object) | |
496 | { | |
497 | return typename | |
498 | Type::bounded_domain_type(upper(object), | |
499 | object.bounds().right()); | |
500 | } | |
501 | ||
502 | template<class Type> | |
503 | typename enable_if<has_dynamic_bounds<Type>, | |
504 | typename Type::bounded_domain_type>::type | |
505 | reverse_bounded_upper(const Type& object) | |
506 | { | |
507 | return typename | |
508 | Type::bounded_domain_type(upper(object), | |
509 | object.bounds().reverse_right()); | |
510 | } | |
511 | ||
512 | //- bounds --------------------------------------------------------------------- | |
513 | template<class Type> | |
514 | inline typename enable_if<has_dynamic_bounds<Type>, interval_bounds>::type | |
515 | bounds(const Type& object) | |
516 | { | |
517 | return object.bounds(); | |
518 | } | |
519 | ||
520 | template<class Type> | |
521 | inline typename enable_if<has_static_bounds<Type>, interval_bounds>::type | |
522 | bounds(const Type&) | |
523 | { | |
524 | return interval_bounds(interval_bound_type<Type>::value); | |
525 | } | |
526 | ||
527 | ||
528 | //============================================================================== | |
529 | //= Emptieness | |
530 | //============================================================================== | |
531 | /** Is the interval empty? */ | |
532 | template<class Type> | |
533 | typename boost::enable_if<is_asymmetric_interval<Type>, bool>::type | |
534 | is_empty(const Type& object) | |
535 | { | |
536 | return domain_less_equal<Type>(upper(object), lower(object)); | |
537 | } | |
538 | ||
539 | template<class Type> | |
540 | typename boost::enable_if<is_static_closed<Type>, bool>::type | |
541 | is_empty(const Type& object) | |
542 | { | |
543 | return domain_less<Type>(upper(object), lower(object)); | |
544 | } | |
545 | ||
546 | template<class Type> | |
547 | typename boost::enable_if<is_static_open<Type>, bool>::type | |
548 | is_empty(const Type& object) | |
549 | { | |
550 | return domain_less_equal<Type>(upper(object), lower(object) ) | |
551 | || domain_less_equal<Type>(upper(object), domain_next<Type>(lower(object))); | |
552 | } | |
553 | ||
554 | template<class Type> | |
555 | typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
556 | is_empty(const Type& object) | |
557 | { | |
558 | if(object.bounds() == interval_bounds::closed()) | |
559 | return domain_less<Type>(upper(object), lower(object)); | |
560 | else if(object.bounds() == interval_bounds::open()) | |
561 | return domain_less_equal<Type>(upper(object), lower(object) ) | |
562 | || domain_less_equal<Type>(upper(object), domain_next<Type>(lower(object))); | |
563 | else | |
564 | return domain_less_equal<Type>(upper(object), lower(object)); | |
565 | } | |
566 | ||
567 | template<class Type> | |
568 | typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
569 | is_empty(const Type& object) | |
570 | { | |
571 | return domain_less<Type>(upper(object), lower(object)) | |
572 | || ( domain_equal<Type>(upper(object), lower(object)) | |
573 | && object.bounds() != interval_bounds::closed() ); | |
574 | } | |
575 | ||
576 | //============================================================================== | |
577 | //= Orderings, containedness (non empty) | |
578 | //============================================================================== | |
579 | namespace non_empty | |
580 | { | |
581 | ||
582 | template<class Type> | |
583 | inline typename boost::enable_if<is_asymmetric_interval<Type>, bool>::type | |
584 | exclusive_less(const Type& left, const Type& right) | |
585 | { | |
586 | BOOST_ASSERT(!(icl::is_empty(left) || icl::is_empty(right))); | |
587 | return domain_less_equal<Type>(upper(left), lower(right)); | |
588 | } | |
589 | ||
590 | template<class Type> | |
591 | inline typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
592 | exclusive_less(const Type& left, const Type& right) | |
593 | { | |
594 | BOOST_ASSERT(!(icl::is_empty(left) || icl::is_empty(right))); | |
595 | return domain_less<Type>(last(left), first(right)); | |
596 | } | |
597 | ||
598 | template<class Type> | |
599 | inline typename boost:: | |
600 | enable_if<has_symmetric_bounds<Type>, bool>::type | |
601 | exclusive_less(const Type& left, const Type& right) | |
602 | { | |
603 | BOOST_ASSERT(!(icl::is_empty(left) || icl::is_empty(right))); | |
604 | return domain_less<Type>(last(left), first(right)); | |
605 | } | |
606 | ||
607 | template<class Type> | |
608 | inline typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
609 | exclusive_less(const Type& left, const Type& right) | |
610 | { | |
611 | BOOST_ASSERT(!(icl::is_empty(left) || icl::is_empty(right))); | |
612 | return domain_less <Type>(upper(left), lower(right)) | |
613 | || ( domain_equal<Type>(upper(left), lower(right)) | |
614 | && inner_bounds(left,right) != interval_bounds::open() ); | |
615 | } | |
616 | ||
617 | template<class Type> | |
618 | inline typename boost::enable_if<is_interval<Type>, bool>::type | |
619 | contains(const Type& super, const Type& sub) | |
620 | { | |
621 | return lower_less_equal(super,sub) && upper_less_equal(sub,super); | |
622 | } | |
623 | ||
624 | ||
625 | } //namespace non_empty | |
626 | ||
627 | ||
628 | //- contains ------------------------------------------------------------------- | |
629 | template<class Type> | |
630 | inline typename boost::enable_if<is_interval<Type>, bool>::type | |
631 | contains(const Type& super, const Type& sub) | |
632 | { | |
633 | return icl::is_empty(sub) || non_empty::contains(super, sub); | |
634 | } | |
635 | ||
636 | template<class Type> | |
637 | typename boost::enable_if<is_discrete_static<Type>, bool>::type | |
638 | contains(const Type& super, const typename interval_traits<Type>::domain_type& element) | |
639 | { | |
640 | return domain_less_equal<Type>(icl::first(super), element ) | |
641 | && domain_less_equal<Type>( element, icl::last(super)); | |
642 | } | |
643 | ||
644 | template<class Type> | |
645 | typename boost::enable_if<is_continuous_left_open<Type>, bool>::type | |
646 | contains(const Type& super, const typename interval_traits<Type>::domain_type& element) | |
647 | { | |
648 | return domain_less <Type>(icl::lower(super), element ) | |
649 | && domain_less_equal<Type>( element, icl::upper(super)); | |
650 | } | |
651 | ||
652 | template<class Type> | |
653 | typename boost::enable_if<is_continuous_right_open<Type>, bool>::type | |
654 | contains(const Type& super, const typename interval_traits<Type>::domain_type& element) | |
655 | { | |
656 | return domain_less_equal<Type>(icl::lower(super), element ) | |
657 | && domain_less <Type>( element, icl::upper(super)); | |
658 | } | |
659 | ||
660 | template<class Type> | |
661 | typename boost::enable_if<has_dynamic_bounds<Type>, bool>::type | |
662 | contains(const Type& super, const typename interval_traits<Type>::domain_type& element) | |
663 | { | |
664 | return | |
665 | (is_left_closed(super.bounds()) | |
666 | ? domain_less_equal<Type>(lower(super), element) | |
667 | : domain_less<Type>(lower(super), element)) | |
668 | && | |
669 | (is_right_closed(super.bounds()) | |
670 | ? domain_less_equal<Type>(element, upper(super)) | |
671 | : domain_less<Type>(element, upper(super))); | |
672 | } | |
673 | ||
674 | //- within --------------------------------------------------------------------- | |
675 | template<class Type> | |
676 | inline typename boost::enable_if<is_interval<Type>, bool>::type | |
677 | within(const Type& sub, const Type& super) | |
678 | { | |
679 | return contains(super,sub); | |
680 | } | |
681 | ||
682 | ||
683 | //============================================================================== | |
684 | //= Equivalences and Orderings | |
685 | //============================================================================== | |
686 | //- exclusive_less ------------------------------------------------------------- | |
687 | /** Maximal element of <tt>left</tt> is less than the minimal element of | |
688 | <tt>right</tt> */ | |
689 | template<class Type> | |
690 | inline typename boost::enable_if<is_asymmetric_interval<Type>, bool>::type | |
691 | exclusive_less(const Type& left, const Type& right) | |
692 | { | |
693 | return icl::is_empty(left) || icl::is_empty(right) | |
694 | || domain_less_equal<Type>(upper(left), lower(right)); | |
695 | } | |
696 | ||
697 | template<class Type> | |
698 | inline typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
699 | exclusive_less(const Type& left, const Type& right) | |
700 | { | |
701 | return icl::is_empty(left) || icl::is_empty(right) | |
702 | || domain_less<Type>(last(left), first(right)); | |
703 | } | |
704 | ||
705 | template<class Type> | |
706 | inline typename boost:: | |
707 | enable_if<has_symmetric_bounds<Type>, bool>::type | |
708 | exclusive_less(const Type& left, const Type& right) | |
709 | { | |
710 | return icl::is_empty(left) || icl::is_empty(right) | |
711 | || domain_less<Type>(last(left), first(right)); | |
712 | } | |
713 | ||
714 | template<class Type> | |
715 | inline typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
716 | exclusive_less(const Type& left, const Type& right) | |
717 | { | |
718 | return icl::is_empty(left) || icl::is_empty(right) | |
719 | || domain_less<Type>(upper(left), lower(right)) | |
720 | || ( domain_equal<Type>(upper(left), lower(right)) | |
721 | && inner_bounds(left,right) != interval_bounds::open() ); | |
722 | } | |
723 | ||
724 | ||
725 | //------------------------------------------------------------------------------ | |
726 | template<class Type> | |
727 | typename boost::enable_if<has_static_bounds<Type>, bool>::type | |
728 | lower_less(const Type& left, const Type& right) | |
729 | { | |
730 | return domain_less<Type>(lower(left), lower(right)); | |
731 | } | |
732 | ||
733 | template<class Type> | |
734 | typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
735 | lower_less(const Type& left, const Type& right) | |
736 | { | |
737 | return domain_less<Type>(first(left), first(right)); | |
738 | } | |
739 | ||
740 | template<class Type> | |
741 | typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
742 | lower_less(const Type& left, const Type& right) | |
743 | { | |
744 | if(left_bounds(left,right) == interval_bounds::right_open()) //'[(' == 10 | |
745 | return domain_less_equal<Type>(lower(left), lower(right)); | |
746 | else | |
747 | return domain_less<Type>(lower(left), lower(right)); | |
748 | } | |
749 | ||
750 | ||
751 | //------------------------------------------------------------------------------ | |
752 | template<class Type> | |
753 | typename boost::enable_if<has_static_bounds<Type>, bool>::type | |
754 | upper_less(const Type& left, const Type& right) | |
755 | { | |
756 | return domain_less<Type>(upper(left), upper(right)); | |
757 | } | |
758 | ||
759 | template<class Type> | |
760 | typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
761 | upper_less(const Type& left, const Type& right) | |
762 | { | |
763 | return domain_less<Type>(last(left), last(right)); | |
764 | } | |
765 | ||
766 | template<class Type> | |
767 | typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
768 | upper_less(const Type& left, const Type& right) | |
769 | { | |
770 | if(right_bounds(left,right) == interval_bounds::left_open()) | |
771 | return domain_less_equal<Type>(upper(left), upper(right)); | |
772 | else | |
773 | return domain_less<Type>(upper(left), upper(right)); | |
774 | } | |
775 | ||
776 | //------------------------------------------------------------------------------ | |
777 | template<class Type> | |
778 | typename boost::enable_if<has_dynamic_bounds<Type>, | |
779 | typename Type::bounded_domain_type >::type | |
780 | lower_min(const Type& left, const Type& right) | |
781 | { | |
782 | return lower_less(left, right) ? bounded_lower(left) : bounded_lower(right); | |
783 | } | |
784 | ||
785 | //------------------------------------------------------------------------------ | |
786 | template<class Type> | |
787 | typename boost::enable_if<has_dynamic_bounds<Type>, | |
788 | typename Type::bounded_domain_type >::type | |
789 | lower_max(const Type& left, const Type& right) | |
790 | { | |
791 | return lower_less(left, right) ? bounded_lower(right) : bounded_lower(left); | |
792 | } | |
793 | ||
794 | //------------------------------------------------------------------------------ | |
795 | template<class Type> | |
796 | typename boost::enable_if<has_dynamic_bounds<Type>, | |
797 | typename Type::bounded_domain_type >::type | |
798 | upper_max(const Type& left, const Type& right) | |
799 | { | |
800 | return upper_less(left, right) ? bounded_upper(right) : bounded_upper(left); | |
801 | } | |
802 | ||
803 | //------------------------------------------------------------------------------ | |
804 | template<class Type> | |
805 | typename boost::enable_if<has_dynamic_bounds<Type>, | |
806 | typename Type::bounded_domain_type >::type | |
807 | upper_min(const Type& left, const Type& right) | |
808 | { | |
809 | return upper_less(left, right) ? bounded_upper(left) : bounded_upper(right); | |
810 | } | |
811 | ||
812 | ||
813 | //------------------------------------------------------------------------------ | |
814 | template<class Type> | |
815 | typename boost::enable_if<is_asymmetric_interval<Type>, bool>::type | |
816 | lower_equal(const Type& left, const Type& right) | |
817 | { | |
818 | return domain_equal<Type>(lower(left), lower(right)); | |
819 | } | |
820 | ||
821 | template<class Type> | |
822 | typename boost::enable_if<has_symmetric_bounds<Type>, bool>::type | |
823 | lower_equal(const Type& left, const Type& right) | |
824 | { | |
825 | return domain_equal<Type>(first(left), first(right)); | |
826 | } | |
827 | ||
828 | template<class Type> | |
829 | typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
830 | lower_equal(const Type& left, const Type& right) | |
831 | { | |
832 | return domain_equal<Type>(first(left), first(right)); | |
833 | } | |
834 | ||
835 | template<class Type> | |
836 | typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
837 | lower_equal(const Type& left, const Type& right) | |
838 | { | |
839 | return (left.bounds().left()==right.bounds().left()) | |
840 | && domain_equal<Type>(lower(left), lower(right)); | |
841 | } | |
842 | ||
843 | ||
844 | //------------------------------------------------------------------------------ | |
845 | template<class Type> | |
846 | typename boost::enable_if<is_asymmetric_interval<Type>, bool>::type | |
847 | upper_equal(const Type& left, const Type& right) | |
848 | { | |
849 | return domain_equal<Type>(upper(left), upper(right)); | |
850 | } | |
851 | ||
852 | template<class Type> | |
853 | typename boost::enable_if<has_symmetric_bounds<Type>, bool>::type | |
854 | upper_equal(const Type& left, const Type& right) | |
855 | { | |
856 | return domain_equal<Type>(last(left), last(right)); | |
857 | } | |
858 | ||
859 | template<class Type> | |
860 | typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
861 | upper_equal(const Type& left, const Type& right) | |
862 | { | |
863 | return domain_equal<Type>(last(left), last(right)); | |
864 | } | |
865 | ||
866 | template<class Type> | |
867 | typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
868 | upper_equal(const Type& left, const Type& right) | |
869 | { | |
870 | return (left.bounds().right()==right.bounds().right()) | |
871 | && domain_equal<Type>(upper(left), upper(right)); | |
872 | } | |
873 | ||
874 | //------------------------------------------------------------------------------ | |
875 | template<class Type> | |
876 | typename boost::enable_if<is_interval<Type>, bool>::type | |
877 | lower_less_equal(const Type& left, const Type& right) | |
878 | { | |
879 | return lower_less(left,right) || lower_equal(left,right); | |
880 | } | |
881 | ||
882 | template<class Type> | |
883 | typename boost::enable_if<is_interval<Type>, bool>::type | |
884 | upper_less_equal(const Type& left, const Type& right) | |
885 | { | |
886 | return upper_less(left,right) || upper_equal(left,right); | |
887 | } | |
888 | ||
889 | ||
890 | //- operator == ---------------------------------------------------------------- | |
891 | template<class Type> | |
892 | typename boost::enable_if<is_interval<Type>, bool>::type | |
893 | operator == (const Type& left, const Type& right) | |
894 | { | |
895 | return (icl::is_empty(left) && icl::is_empty(right)) | |
896 | || (lower_equal(left,right) && upper_equal(left,right)); | |
897 | } | |
898 | ||
899 | template<class Type> | |
900 | typename boost::enable_if<is_interval<Type>, bool>::type | |
901 | operator != (const Type& left, const Type& right) | |
902 | { | |
903 | return !(left == right); | |
904 | } | |
905 | ||
906 | //- operator < ----------------------------------------------------------------- | |
907 | template<class Type> | |
908 | typename boost::enable_if<is_interval<Type>, bool>::type | |
909 | operator < (const Type& left, const Type& right) | |
910 | { | |
911 | if(icl::is_empty(left)) | |
912 | return !icl::is_empty(right); | |
913 | else | |
914 | return lower_less(left,right) | |
915 | || (lower_equal(left,right) && upper_less(left,right)); | |
916 | } | |
917 | ||
918 | template<class Type> | |
919 | inline typename boost::enable_if<is_interval<Type>, bool>::type | |
920 | operator > (const Type& left, const Type& right) | |
921 | { | |
922 | return right < left; | |
923 | } | |
924 | ||
925 | ||
926 | ||
927 | //------------------------------------------------------------------------------ | |
928 | template<class Type> | |
929 | typename boost::enable_if<is_asymmetric_interval<Type>, bool>::type | |
930 | touches(const Type& left, const Type& right) | |
931 | { | |
932 | return domain_equal<Type>(upper(left), lower(right)); | |
933 | } | |
934 | ||
935 | template<class Type> | |
936 | typename boost::enable_if<has_symmetric_bounds<Type>, bool>::type | |
937 | touches(const Type& left, const Type& right) | |
938 | { | |
939 | return domain_equal<Type>(last_next(left), first(right)); | |
940 | } | |
941 | ||
942 | template<class Type> | |
943 | typename boost::enable_if<is_discrete_interval<Type>, bool>::type | |
944 | touches(const Type& left, const Type& right) | |
945 | { | |
946 | return domain_equal<Type>(domain_next<Type>(last(left)), first(right)); | |
947 | } | |
948 | ||
949 | template<class Type> | |
950 | typename boost::enable_if<is_continuous_interval<Type>, bool>::type | |
951 | touches(const Type& left, const Type& right) | |
952 | { | |
953 | return is_complementary(inner_bounds(left,right)) | |
954 | && domain_equal<Type>(upper(left), lower(right)); | |
955 | } | |
956 | ||
957 | ||
958 | //============================================================================== | |
959 | //= Size | |
960 | //============================================================================== | |
961 | //- cardinality ---------------------------------------------------------------- | |
962 | ||
963 | template<class Type> | |
964 | typename boost::enable_if<is_continuous_interval<Type>, | |
965 | typename size_type_of<interval_traits<Type> >::type>::type | |
966 | cardinality(const Type& object) | |
967 | { | |
968 | typedef typename size_type_of<interval_traits<Type> >::type SizeT; | |
969 | if(icl::is_empty(object)) | |
970 | return icl::identity_element<SizeT>::value(); | |
971 | else if( object.bounds() == interval_bounds::closed() | |
972 | && domain_equal<Type>(lower(object), upper(object))) | |
973 | return icl::unit_element<SizeT>::value(); | |
974 | else | |
975 | return icl::infinity<SizeT>::value(); | |
976 | } | |
977 | ||
978 | template<class Type> | |
979 | typename boost::enable_if<is_discrete_interval<Type>, | |
980 | typename size_type_of<interval_traits<Type> >::type>::type | |
981 | cardinality(const Type& object) | |
982 | { | |
983 | typedef typename size_type_of<interval_traits<Type> >::type SizeT; | |
984 | return icl::is_empty(object) ? identity_element<SizeT>::value() | |
985 | : static_cast<SizeT>(last_next(object) - first(object)); | |
986 | } | |
987 | ||
988 | template<class Type> | |
989 | typename boost::enable_if<is_continuous_asymmetric<Type>, | |
990 | typename size_type_of<interval_traits<Type> >::type>::type | |
991 | cardinality(const Type& object) | |
992 | { | |
993 | typedef typename size_type_of<interval_traits<Type> >::type SizeT; | |
994 | if(icl::is_empty(object)) | |
995 | return icl::identity_element<SizeT>::value(); | |
996 | else | |
997 | return icl::infinity<SizeT>::value(); | |
998 | } | |
999 | ||
1000 | template<class Type> | |
1001 | typename boost::enable_if<is_discrete_asymmetric<Type>, | |
1002 | typename size_type_of<interval_traits<Type> >::type>::type | |
1003 | cardinality(const Type& object) | |
1004 | { | |
1005 | typedef typename size_type_of<interval_traits<Type> >::type SizeT; | |
1006 | return icl::is_empty(object) ? identity_element<SizeT>::value() | |
1007 | : static_cast<SizeT>(last_next(object) - first(object)); | |
1008 | } | |
1009 | ||
1010 | template<class Type> | |
1011 | typename boost::enable_if<has_symmetric_bounds<Type>, | |
1012 | typename size_type_of<interval_traits<Type> >::type>::type | |
1013 | cardinality(const Type& object) | |
1014 | { | |
1015 | typedef typename size_type_of<interval_traits<Type> >::type SizeT; | |
1016 | return icl::is_empty(object) ? identity_element<SizeT>::value() | |
1017 | : static_cast<SizeT>(last_next(object) - first(object)); | |
1018 | } | |
1019 | ||
1020 | ||
1021 | ||
1022 | //- size ----------------------------------------------------------------------- | |
1023 | template<class Type> | |
1024 | inline typename enable_if<is_interval<Type>, | |
1025 | typename size_type_of<interval_traits<Type> >::type>::type | |
1026 | size(const Type& object) | |
1027 | { | |
1028 | return cardinality(object); | |
1029 | } | |
1030 | ||
1031 | //- length --------------------------------------------------------------------- | |
1032 | template<class Type> | |
1033 | inline typename boost::enable_if<is_continuous_interval<Type>, | |
1034 | typename difference_type_of<interval_traits<Type> >::type>::type | |
1035 | length(const Type& object) | |
1036 | { | |
1037 | typedef typename difference_type_of<interval_traits<Type> >::type DiffT; | |
1038 | return icl::is_empty(object) ? identity_element<DiffT>::value() | |
1039 | : upper(object) - lower(object); | |
1040 | } | |
1041 | ||
1042 | template<class Type> | |
1043 | inline typename boost::enable_if<is_discrete_interval<Type>, | |
1044 | typename difference_type_of<interval_traits<Type> >::type>::type | |
1045 | length(const Type& object) | |
1046 | { | |
1047 | typedef typename difference_type_of<interval_traits<Type> >::type DiffT; | |
1048 | return icl::is_empty(object) ? identity_element<DiffT>::value() | |
1049 | : last_next(object) - first(object); | |
1050 | } | |
1051 | ||
1052 | template<class Type> | |
1053 | typename boost::enable_if<is_continuous_asymmetric<Type>, | |
1054 | typename difference_type_of<interval_traits<Type> >::type>::type | |
1055 | length(const Type& object) | |
1056 | { | |
1057 | typedef typename difference_type_of<interval_traits<Type> >::type DiffT; | |
1058 | return icl::is_empty(object) ? identity_element<DiffT>::value() | |
1059 | : upper(object) - lower(object); | |
1060 | } | |
1061 | ||
1062 | template<class Type> | |
1063 | inline typename boost::enable_if<is_discrete_static<Type>, | |
1064 | typename difference_type_of<interval_traits<Type> >::type>::type | |
1065 | length(const Type& object) | |
1066 | { | |
1067 | typedef typename difference_type_of<interval_traits<Type> >::type DiffT; | |
1068 | return icl::is_empty(object) ? identity_element<DiffT>::value() | |
1069 | : last_next(object) - first(object); | |
1070 | } | |
1071 | ||
1072 | //- iterative_size ------------------------------------------------------------- | |
1073 | template<class Type> | |
1074 | inline typename enable_if<is_interval<Type>, | |
1075 | typename size_type_of<interval_traits<Type> >::type>::type | |
1076 | iterative_size(const Type&) | |
1077 | { | |
1078 | return 2; | |
1079 | } | |
1080 | ||
1081 | ||
1082 | //============================================================================== | |
1083 | //= Addition | |
1084 | //============================================================================== | |
1085 | //- hull ----------------------------------------------------------------------- | |
1086 | /** \c hull returns the smallest interval containing \c left and \c right. */ | |
1087 | template<class Type> | |
1088 | typename boost::enable_if<has_static_bounds<Type>, Type>::type | |
1089 | hull(Type left, const Type& right) | |
1090 | { | |
1091 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
1092 | ||
1093 | if(icl::is_empty(right)) | |
1094 | return left; | |
1095 | else if(icl::is_empty(left)) | |
1096 | return right; | |
1097 | ||
1098 | return | |
1099 | construct<Type> | |
1100 | ( | |
1101 | (std::min)(lower(left), lower(right), domain_compare()), | |
1102 | (std::max)(upper(left), upper(right), domain_compare()) | |
1103 | ); | |
1104 | } | |
1105 | ||
1106 | template<class Type> | |
1107 | typename boost::enable_if<has_dynamic_bounds<Type>, Type>::type | |
1108 | hull(Type left, const Type& right) | |
1109 | { | |
1110 | if(icl::is_empty(right)) | |
1111 | return left; | |
1112 | else if(icl::is_empty(left)) | |
1113 | return right; | |
1114 | ||
1115 | return dynamic_interval_traits<Type>::construct_bounded | |
1116 | ( | |
1117 | lower_min(left, right), | |
1118 | upper_max(left, right) | |
1119 | ); | |
1120 | } | |
1121 | ||
1122 | //============================================================================== | |
1123 | //= Subtraction | |
1124 | //============================================================================== | |
1125 | //- left_subtract -------------------------------------------------------------- | |
1126 | /** subtract \c left_minuend from the \c right interval on it's left side. | |
1127 | Return the difference: The part of \c right right of \c left_minuend. | |
1128 | \code | |
1129 | right_over = right - left_minuend; //on the left. | |
1130 | ... d) : right | |
1131 | ... c) : left_minuend | |
1132 | [c d) : right_over | |
1133 | \endcode | |
1134 | */ | |
1135 | template<class Type> | |
1136 | typename boost::enable_if<is_asymmetric_interval<Type>, Type>::type | |
1137 | left_subtract(Type right, const Type& left_minuend) | |
1138 | { | |
1139 | if(exclusive_less(left_minuend, right)) | |
1140 | return right; | |
1141 | ||
1142 | return construct<Type>(upper(left_minuend), upper(right)); | |
1143 | } | |
1144 | ||
1145 | template<class Type> | |
1146 | typename boost::enable_if<is_static_closed<Type>, Type>::type | |
1147 | left_subtract(Type right, const Type& left_minuend) | |
1148 | { | |
1149 | if(exclusive_less(left_minuend, right)) | |
1150 | return right; | |
1151 | else if(upper_less_equal(right, left_minuend)) | |
1152 | return identity_element<Type>::value(); | |
1153 | ||
1154 | return construct<Type>(domain_next<Type>(upper(left_minuend)), upper(right)); | |
1155 | } | |
1156 | ||
1157 | template<class Type> | |
1158 | typename boost::enable_if<is_static_open<Type>, Type>::type | |
1159 | left_subtract(Type right, const Type& left_minuend) | |
1160 | { | |
1161 | if(exclusive_less(left_minuend, right)) | |
1162 | return right; | |
1163 | ||
1164 | return construct<Type>(domain_prior<Type>(upper(left_minuend)), upper(right)); | |
1165 | } | |
1166 | ||
1167 | template<class Type> | |
1168 | typename boost::enable_if<has_dynamic_bounds<Type>, Type>::type | |
1169 | left_subtract(Type right, const Type& left_minuend) | |
1170 | { | |
1171 | if(exclusive_less(left_minuend, right)) | |
1172 | return right; | |
1173 | return dynamic_interval_traits<Type>::construct_bounded | |
1174 | ( reverse_bounded_upper(left_minuend), bounded_upper(right) ); | |
1175 | } | |
1176 | ||
1177 | ||
1178 | //- right_subtract ------------------------------------------------------------- | |
1179 | /** subtract \c right_minuend from the \c left interval on it's right side. | |
1180 | Return the difference: The part of \c left left of \c right_minuend. | |
1181 | \code | |
1182 | left_over = left - right_minuend; //on the right side. | |
1183 | [a ... : left | |
1184 | [b ... : right_minuend | |
1185 | [a b) : left_over | |
1186 | \endcode | |
1187 | */ | |
1188 | template<class Type> | |
1189 | typename boost::enable_if<is_asymmetric_interval<Type>, Type>::type | |
1190 | right_subtract(Type left, const Type& right_minuend) | |
1191 | { | |
1192 | if(exclusive_less(left, right_minuend)) | |
1193 | return left; | |
1194 | return construct<Type>(lower(left), lower(right_minuend)); | |
1195 | } | |
1196 | ||
1197 | template<class Type> | |
1198 | typename boost::enable_if<is_static_closed<Type>, Type>::type | |
1199 | right_subtract(Type left, const Type& right_minuend) | |
1200 | { | |
1201 | if(exclusive_less(left, right_minuend)) | |
1202 | return left; | |
1203 | else if(lower_less_equal(right_minuend, left)) | |
1204 | return identity_element<Type>::value(); | |
1205 | ||
1206 | return construct<Type>(lower(left), domain_prior<Type>(lower(right_minuend))); | |
1207 | } | |
1208 | ||
1209 | template<class Type> | |
1210 | typename boost::enable_if<is_static_open<Type>, Type>::type | |
1211 | right_subtract(Type left, const Type& right_minuend) | |
1212 | { | |
1213 | if(exclusive_less(left, right_minuend)) | |
1214 | return left; | |
1215 | ||
1216 | return construct<Type>(lower(left), domain_next<Type>(lower(right_minuend))); | |
1217 | } | |
1218 | ||
1219 | template<class Type> | |
1220 | typename boost::enable_if<has_dynamic_bounds<Type>, Type>::type | |
1221 | right_subtract(Type left, const Type& right_minuend) | |
1222 | { | |
1223 | if(exclusive_less(left, right_minuend)) | |
1224 | return left; | |
1225 | ||
1226 | return dynamic_interval_traits<Type>::construct_bounded | |
1227 | ( bounded_lower(left), reverse_bounded_lower(right_minuend) ); | |
1228 | } | |
1229 | ||
1230 | //============================================================================== | |
1231 | //= Intersection | |
1232 | //============================================================================== | |
1233 | //- operator & ----------------------------------------------------------------- | |
1234 | /** Returns the intersection of \c left and \c right interval. */ | |
1235 | template<class Type> | |
1236 | typename boost::enable_if<is_asymmetric_interval<Type>, Type>::type | |
1237 | operator & (Type left, const Type& right) | |
1238 | { | |
1239 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
1240 | ||
1241 | if(icl::is_empty(left) || icl::is_empty(right)) | |
1242 | return identity_element<Type>::value(); | |
1243 | else | |
1244 | return | |
1245 | construct<Type> | |
1246 | ( | |
1247 | (std::max)(icl::lower(left), icl::lower(right), domain_compare()), | |
1248 | (std::min)(icl::upper(left), icl::upper(right), domain_compare()) | |
1249 | ); | |
1250 | } | |
1251 | ||
1252 | template<class Type> | |
1253 | typename boost::enable_if<has_symmetric_bounds<Type>, Type>::type | |
1254 | operator & (Type left, const Type& right) | |
1255 | { | |
1256 | typedef typename interval_traits<Type>::domain_compare domain_compare; | |
1257 | ||
1258 | if(icl::is_empty(left) || icl::is_empty(right)) | |
1259 | return identity_element<Type>::value(); | |
1260 | else | |
1261 | return | |
1262 | construct<Type> | |
1263 | ( | |
1264 | (std::max)(icl::lower(left), icl::lower(right), domain_compare()), | |
1265 | (std::min)(icl::upper(left), icl::upper(right), domain_compare()) | |
1266 | ); | |
1267 | } | |
1268 | ||
1269 | template<class Type> | |
1270 | typename boost::enable_if<has_dynamic_bounds<Type>, Type>::type | |
1271 | operator & (Type left, const Type& right) | |
1272 | { | |
1273 | if(icl::is_empty(left) || icl::is_empty(right)) | |
1274 | return identity_element<Type>::value(); | |
1275 | else | |
1276 | return dynamic_interval_traits<Type>::construct_bounded | |
1277 | ( | |
1278 | lower_max(left, right), | |
1279 | upper_min(left, right) | |
1280 | ); | |
1281 | } | |
1282 | ||
1283 | ||
1284 | //- intersects ----------------------------------------------------------------- | |
1285 | template<class Type> | |
1286 | typename boost::enable_if<is_interval<Type>, bool>::type | |
1287 | intersects(const Type& left, const Type& right) | |
1288 | { | |
1289 | return !( icl::is_empty(left) || icl::is_empty(right) | |
1290 | || exclusive_less(left,right) || exclusive_less(right,left)); | |
1291 | } | |
1292 | ||
1293 | //- disjoint ------------------------------------------------------------------- | |
1294 | template<class Type> | |
1295 | typename boost::enable_if<is_interval<Type>, bool>::type | |
1296 | disjoint(const Type& left, const Type& right) | |
1297 | { | |
1298 | return icl::is_empty(left) || icl::is_empty(right) | |
1299 | || exclusive_less(left,right) || exclusive_less(right,left); | |
1300 | } | |
1301 | ||
1302 | //============================================================================== | |
1303 | //= Complement | |
1304 | //============================================================================== | |
1305 | ||
1306 | template<class Type> | |
1307 | typename boost::enable_if<is_asymmetric_interval<Type>, Type>::type | |
1308 | inner_complement(const Type& left, const Type& right) | |
1309 | { | |
1310 | if(icl::is_empty(left) || icl::is_empty(right)) | |
1311 | return identity_element<Type>::value(); | |
1312 | else if(exclusive_less(left, right)) | |
1313 | return construct<Type>(upper(left), lower(right)); | |
1314 | else if(exclusive_less(right, left)) | |
1315 | return construct<Type>(upper(right), lower(left)); | |
1316 | else | |
1317 | return identity_element<Type>::value(); | |
1318 | } | |
1319 | ||
1320 | template<class Type> | |
1321 | typename boost::enable_if<is_discrete_static_closed<Type>, Type>::type | |
1322 | inner_complement(const Type& left, const Type& right) | |
1323 | { | |
1324 | if(icl::is_empty(left) || icl::is_empty(right)) | |
1325 | return identity_element<Type>::value(); | |
1326 | else if(exclusive_less(left, right)) | |
1327 | return construct<Type>(domain_next<Type>(upper(left)), domain_prior<Type>(lower(right))); | |
1328 | else if(exclusive_less(right, left)) | |
1329 | return construct<Type>(domain_next<Type>(upper(right)), domain_prior<Type>(lower(left))); | |
1330 | else | |
1331 | return identity_element<Type>::value(); | |
1332 | } | |
1333 | ||
1334 | template<class Type> | |
1335 | typename boost::enable_if<is_discrete_static_open<Type>, Type>::type | |
1336 | inner_complement(const Type& left, const Type& right) | |
1337 | { | |
1338 | if(icl::is_empty(left) || icl::is_empty(right)) | |
1339 | return identity_element<Type>::value(); | |
1340 | else if(exclusive_less(left, right)) | |
1341 | return construct<Type>(last(left), first(right)); | |
1342 | else if(exclusive_less(right, left)) | |
1343 | return construct<Type>(last(right), first(left)); | |
1344 | else | |
1345 | return identity_element<Type>::value(); | |
1346 | } | |
1347 | ||
1348 | template<class Type> | |
1349 | typename boost::enable_if<has_dynamic_bounds<Type>, Type>::type | |
1350 | inner_complement(const Type& left, const Type& right) | |
1351 | { | |
1352 | if(icl::is_empty(left) || icl::is_empty(right)) | |
1353 | return identity_element<Type>::value(); | |
1354 | else if(exclusive_less(left, right)) | |
1355 | return right_subtract(left_subtract(hull(left, right), left), right); | |
1356 | else if(exclusive_less(right, left)) | |
1357 | return right_subtract(left_subtract(hull(right, left), right), left); | |
1358 | else | |
1359 | return identity_element<Type>::value(); | |
1360 | } | |
1361 | ||
1362 | template<class Type> | |
1363 | inline typename boost::enable_if<is_interval<Type>, Type>::type | |
1364 | between(const Type& left, const Type& right) | |
1365 | { | |
1366 | return inner_complement(left, right); | |
1367 | } | |
1368 | ||
1369 | ||
1370 | ||
1371 | //============================================================================== | |
1372 | //= Distance | |
1373 | //============================================================================== | |
1374 | template<class Type> | |
1375 | typename boost:: | |
1376 | enable_if< mpl::and_< is_interval<Type> | |
1377 | , has_difference<typename interval_traits<Type>::domain_type> | |
1378 | , is_discrete<typename interval_traits<Type>::domain_type> | |
1379 | > | |
1380 | , typename difference_type_of<interval_traits<Type> >::type>::type | |
1381 | distance(const Type& x1, const Type& x2) | |
1382 | { | |
1383 | typedef typename difference_type_of<interval_traits<Type> >::type difference_type; | |
1384 | ||
1385 | if(icl::is_empty(x1) || icl::is_empty(x2)) | |
1386 | return icl::identity_element<difference_type>::value(); | |
1387 | else if(domain_less<Type>(last(x1), first(x2))) | |
1388 | return static_cast<difference_type>(icl::pred(first(x2) - last(x1))); | |
1389 | else if(domain_less<Type>(last(x2), first(x1))) | |
1390 | return static_cast<difference_type>(icl::pred(first(x1) - last(x2))); | |
1391 | else | |
1392 | return icl::identity_element<difference_type>::value(); | |
1393 | } | |
1394 | ||
1395 | template<class Type> | |
1396 | typename boost:: | |
1397 | enable_if< mpl::and_< is_interval<Type> | |
1398 | , has_difference<typename interval_traits<Type>::domain_type> | |
1399 | , is_continuous<typename interval_traits<Type>::domain_type> | |
1400 | > | |
1401 | , typename difference_type_of<interval_traits<Type> >::type>::type | |
1402 | distance(const Type& x1, const Type& x2) | |
1403 | { | |
1404 | typedef typename difference_type_of<interval_traits<Type> >::type DiffT; | |
1405 | ||
1406 | if(icl::is_empty(x1) || icl::is_empty(x2)) | |
1407 | return icl::identity_element<DiffT>::value(); | |
1408 | else if(domain_less<Type>(upper(x1), lower(x2))) | |
1409 | return lower(x2) - upper(x1); | |
1410 | else if(domain_less<Type>(upper(x2), lower(x1))) | |
1411 | return lower(x1) - upper(x2); | |
1412 | else | |
1413 | return icl::identity_element<DiffT>::value(); | |
1414 | } | |
1415 | ||
1416 | //============================================================================== | |
1417 | //= Streaming, representation | |
1418 | //============================================================================== | |
1419 | template<class Type> | |
1420 | typename boost:: | |
1421 | enable_if< mpl::or_< is_static_left_open<Type> | |
1422 | , is_static_open<Type> >, std::string>::type | |
1423 | left_bracket(const Type&) { return "("; } | |
1424 | ||
1425 | template<class Type> | |
1426 | typename boost:: | |
1427 | enable_if< mpl::or_< is_static_right_open<Type> | |
1428 | , is_static_closed<Type> >, std::string>::type | |
1429 | left_bracket(const Type&) { return "["; } | |
1430 | ||
1431 | template<class Type> | |
1432 | typename boost::enable_if<has_dynamic_bounds<Type>, std::string>::type | |
1433 | left_bracket(const Type& object) | |
1434 | { | |
1435 | return left_bracket(object.bounds()); | |
1436 | } | |
1437 | ||
1438 | //------------------------------------------------------------------------------ | |
1439 | template<class Type> | |
1440 | typename boost:: | |
1441 | enable_if< mpl::or_< is_static_right_open<Type> | |
1442 | , is_static_open<Type> >, std::string>::type | |
1443 | right_bracket(const Type&) { return ")"; } | |
1444 | ||
1445 | template<class Type> | |
1446 | typename boost:: | |
1447 | enable_if< mpl::or_< is_static_left_open<Type> | |
1448 | , is_static_closed<Type> >, std::string>::type | |
1449 | right_bracket(const Type&) { return "]"; } | |
1450 | ||
1451 | template<class Type> | |
1452 | typename boost::enable_if<has_dynamic_bounds<Type>, std::string>::type | |
1453 | right_bracket(const Type& object) | |
1454 | { | |
1455 | return right_bracket(object.bounds()); | |
1456 | } | |
1457 | ||
1458 | //------------------------------------------------------------------------------ | |
1459 | template<class CharType, class CharTraits, class Type> | |
1460 | typename boost::enable_if<is_interval<Type>, | |
1461 | std::basic_ostream<CharType, CharTraits> >::type& | |
1462 | operator << (std::basic_ostream<CharType, CharTraits> &stream, Type const& object) | |
1463 | { | |
1464 | if(boost::icl::is_empty(object)) | |
1465 | return stream << left_bracket<Type>(object) << right_bracket<Type>(object); | |
1466 | else | |
1467 | return stream << left_bracket<Type>(object) | |
1468 | << interval_traits<Type>::lower(object) | |
1469 | << "," | |
1470 | << interval_traits<Type>::upper(object) | |
1471 | << right_bracket<Type>(object) ; | |
1472 | } | |
1473 | ||
1474 | }} // namespace icl boost | |
1475 | ||
1476 | #endif | |
1477 |