ceph/src/boost/libs/icl/include/boost/icl/concept/interval.hpp

   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