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