ceph/src/boost/boost/icl/concept/interval_associator.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_ASSOCIATOR_HPP_JOFA_100920
   9 #define BOOST_ICL_CONCEPT_INTERVAL_ASSOCIATOR_HPP_JOFA_100920
  10
  11 #include <boost/icl/type_traits/domain_type_of.hpp>
  12 #include <boost/icl/type_traits/interval_type_of.hpp>
  13 #include <boost/icl/type_traits/is_combinable.hpp>
  14 #include <boost/icl/detail/set_algo.hpp>
  15 #include <boost/icl/detail/map_algo.hpp>
  16 #include <boost/icl/detail/interval_set_algo.hpp>
  17 #include <boost/icl/detail/interval_map_algo.hpp>
  18 #include <boost/icl/concept/interval.hpp>
  19
  20 namespace boost{ namespace icl
  21 {
  22
  23 //==============================================================================
  24 //= Containedness<IntervalSet|IntervalMap>
  25 //==============================================================================
  26 //------------------------------------------------------------------------------
  27 //- bool within(c T&, c P&) T={Set,Map} P={e i b p S M}
  28 //------------------------------------------------------------------------------
  29 template<class SubT, class SuperT>
  30 typename enable_if<is_interval_container<SuperT>, bool>::type
  31 within(const SubT& sub, const SuperT& super)
  32 {
  33     return icl::contains(super, sub);
  34 }
  35
  36 //==============================================================================
  37 //= Equivalences and Orderings<IntervalSet|IntervalMap>
  38 //==============================================================================
  39 template<class Type>
  40 inline typename enable_if<is_interval_container<Type>, bool>::type
  41 operator == (const Type& left, const Type& right)
  42 {
  43     return Set::lexicographical_equal(left, right);
  44 }
  45
  46 template<class Type>
  47 inline typename enable_if<is_interval_container<Type>, bool>::type
  48 operator < (const Type& left, const Type& right)
  49 {
  50     typedef typename Type::segment_compare segment_compare;
  51     return std::lexicographical_compare(
  52         left.begin(), left.end(), right.begin(), right.end(),
  53         segment_compare()
  54         );
  55 }
  56
  57 /** Returns true, if \c left and \c right contain the same elements.
  58     Complexity: linear. */
  59 template<class LeftT, class RightT>
  60 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
  61 is_element_equal(const LeftT& left, const RightT& right)
  62 {
  63     return Interval_Set::is_element_equal(left, right);
  64 }
  65
  66 /** Returns true, if \c left is lexicographically less than \c right.
  67     Intervals are interpreted as sequence of elements.
  68     Complexity: linear. */
  69 template<class LeftT, class RightT>
  70 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
  71 is_element_less(const LeftT& left, const RightT& right)
  72 {
  73     return Interval_Set::is_element_less(left, right);
  74 }
  75
  76 /** Returns true, if \c left is lexicographically greater than \c right.
  77     Intervals are interpreted as sequence of elements.
  78     Complexity: linear. */
  79 template<class LeftT, class RightT>
  80 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
  81 is_element_greater(const LeftT& left, const RightT& right)
  82 {
  83     return Interval_Set::is_element_greater(left, right);
  84 }
  85
  86 //------------------------------------------------------------------------------
  87 template<class LeftT, class RightT>
  88 typename enable_if<is_inter_combinable<LeftT, RightT>, int>::type
  89 inclusion_compare(const LeftT& left, const RightT& right)
  90 {
  91     return Interval_Set::subset_compare(left, right,
  92                                         left.begin(), left.end(),
  93                                         right.begin(), right.end());
  94 }
  95
  96 //------------------------------------------------------------------------------
  97 template<class LeftT, class RightT>
  98 typename enable_if< is_concept_compatible<is_interval_map, LeftT, RightT>,
  99                     bool >::type
 100 is_distinct_equal(const LeftT& left, const RightT& right)
 101 {
 102     return Map::lexicographical_distinct_equal(left, right);
 103 }
 104
 105 //==============================================================================
 106 //= Size<IntervalSet|IntervalMap>
 107 //==============================================================================
 108 template<class Type>
 109 typename enable_if<is_interval_container<Type>, std::size_t>::type
 110 iterative_size(const Type& object)
 111 {
 112     return object.iterative_size();
 113 }
 114
 115 template<class Type>
 116 typename enable_if
 117 < mpl::and_< is_interval_container<Type>
 118            , is_discrete<typename Type::domain_type> >
 119 , typename Type::size_type
 120 >::type
 121 cardinality(const Type& object)
 122 {
 123     typedef typename Type::size_type size_type;
 124     //CL typedef typename Type::interval_type interval_type;
 125
 126     size_type size = identity_element<size_type>::value();
 127     ICL_const_FORALL(typename Type, it, object)
 128         size += icl::cardinality(key_value<Type>(it));
 129     return size;
 130
 131 }
 132
 133 template<class Type>
 134 typename enable_if
 135 < mpl::and_< is_interval_container<Type>
 136            , mpl::not_<is_discrete<typename Type::domain_type> > >
 137 , typename Type::size_type
 138 >::type
 139 cardinality(const Type& object)
 140 {
 141     typedef typename Type::size_type size_type;
 142     //CL typedef typename Type::interval_type interval_type;
 143
 144     size_type size = identity_element<size_type>::value();
 145     size_type interval_size;
 146     ICL_const_FORALL(typename Type, it, object)
 147     {
 148         interval_size = icl::cardinality(key_value<Type>(it));
 149         if(interval_size == icl::infinity<size_type>::value())
 150             return interval_size;
 151         else
 152             size += interval_size;
 153     }
 154     return size;
 155 }
 156
 157 template<class Type>
 158 inline typename enable_if<is_interval_container<Type>, typename Type::size_type>::type
 159 size(const Type& object)
 160 {
 161     return icl::cardinality(object);
 162 }
 163
 164 template<class Type>
 165 typename enable_if<is_interval_container<Type>, typename Type::difference_type>::type
 166 length(const Type& object)
 167 {
 168     typedef typename Type::difference_type difference_type;
 169     typedef typename Type::const_iterator  const_iterator;
 170     difference_type length = identity_element<difference_type>::value();
 171     const_iterator it_ = object.begin();
 172
 173     while(it_ != object.end())
 174         length += icl::length(key_value<Type>(it_++));
 175     return length;
 176 }
 177
 178 template<class Type>
 179 typename enable_if<is_interval_container<Type>, std::size_t>::type
 180 interval_count(const Type& object)
 181 {
 182     return icl::iterative_size(object);
 183 }
 184
 185
 186 template<class Type>
 187 typename enable_if< is_interval_container<Type>
 188                   , typename Type::difference_type >::type
 189 distance(const Type& object)
 190 {
 191     typedef typename Type::difference_type DiffT;
 192     typedef typename Type::const_iterator const_iterator;
 193     const_iterator it_ = object.begin(), pred_;
 194     DiffT dist = identity_element<DiffT>::value();
 195
 196     if(it_ != object.end())
 197         pred_ = it_++;
 198
 199     while(it_ != object.end())
 200         dist += icl::distance(key_value<Type>(pred_++), key_value<Type>(it_++));
 201
 202     return dist;
 203 }
 204
 205 //==============================================================================
 206 //= Range<IntervalSet|IntervalMap>
 207 //==============================================================================
 208 template<class Type>
 209 typename enable_if<is_interval_container<Type>,
 210                    typename Type::interval_type>::type
 211 hull(const Type& object)
 212 {
 213     return
 214         icl::is_empty(object)
 215             ? identity_element<typename Type::interval_type>::value()
 216             : icl::hull( key_value<Type>(object.begin()),
 217                          key_value<Type>(object.rbegin()) );
 218 }
 219
 220 template<class Type>
 221 typename enable_if<is_interval_container<Type>,
 222                    typename domain_type_of<Type>::type>::type
 223 lower(const Type& object)
 224 {
 225     typedef typename domain_type_of<Type>::type DomainT;
 226     return
 227         icl::is_empty(object)
 228             ? unit_element<DomainT>::value()
 229             : icl::lower( key_value<Type>(object.begin()) );
 230 }
 231
 232 template<class Type>
 233 typename enable_if<is_interval_container<Type>,
 234                    typename domain_type_of<Type>::type>::type
 235 upper(const Type& object)
 236 {
 237     typedef typename domain_type_of<Type>::type DomainT;
 238     return
 239         icl::is_empty(object)
 240             ? identity_element<DomainT>::value()
 241             : icl::upper( key_value<Type>(object.rbegin()) );
 242 }
 243
 244 //------------------------------------------------------------------------------
 245 template<class Type>
 246 typename enable_if
 247 < mpl::and_< is_interval_container<Type>
 248            , is_discrete<typename domain_type_of<Type>::type> >
 249 , typename domain_type_of<Type>::type>::type
 250 first(const Type& object)
 251 {
 252     typedef typename domain_type_of<Type>::type DomainT;
 253     return
 254         icl::is_empty(object)
 255             ? unit_element<DomainT>::value()
 256             : icl::first( key_value<Type>(object.begin()) );
 257 }
 258
 259 template<class Type>
 260 typename enable_if
 261 < mpl::and_< is_interval_container<Type>
 262            , is_discrete<typename domain_type_of<Type>::type> >
 263 , typename domain_type_of<Type>::type>::type
 264 last(const Type& object)
 265 {
 266     typedef typename domain_type_of<Type>::type DomainT;
 267     return
 268         icl::is_empty(object)
 269             ? identity_element<DomainT>::value()
 270             : icl::last( key_value<Type>(object.rbegin()) );
 271 }
 272
 273
 274 //==============================================================================
 275 //= Addition<IntervalSet|IntervalMap>
 276 //==============================================================================
 277 //------------------------------------------------------------------------------
 278 //- T& op +=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
 279 //------------------------------------------------------------------------------
 280 /* \par \b Requires: \c OperandT is an addable derivative type of \c Type.
 281     \b Effects: \c operand is added to \c object.
 282     \par \b Returns: A reference to \c object.
 283     \b Complexity:
 284 \code
 285                   \ OperandT:
 286                    \         element     segment
 287 Type:
 288        interval container    O(log n)     O(n)
 289
 290              interval_set               amortized
 291     spearate_interval_set                O(log n)
 292
 293 n = object.interval_count()
 294 \endcode
 295
 296 For the addition of \b elements or \b segments
 297 complexity is \b logarithmic or \b linear respectively.
 298 For \c interval_sets and \c separate_interval_sets addition of segments
 299 is \b amortized \b logarithmic.
 300 */
 301 template<class Type, class OperandT>
 302 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
 303 operator += (Type& object, const OperandT& operand)
 304 {
 305     return icl::add(object, operand);
 306 }
 307
 308
 309 //------------------------------------------------------------------------------
 310 //- T& op +=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
 311 //------------------------------------------------------------------------------
 312 /** \par \b Requires: \c OperandT is an interval container addable to \c Type.
 313     \b Effects: \c operand is added to \c object.
 314     \par \b Returns: A reference to \c object.
 315     \b Complexity: loglinear */
 316 template<class Type, class OperandT>
 317 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
 318 operator += (Type& object, const OperandT& operand)
 319 {
 320     typename Type::iterator prior_ = object.end();
 321     ICL_const_FORALL(typename OperandT, elem_, operand)
 322         prior_ = icl::add(object, prior_, *elem_);
 323
 324     return object;
 325 }
 326
 327
 328 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 329 //------------------------------------------------------------------------------
 330 //- T op + (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
 331 //------------------------------------------------------------------------------
 332 /** \par \b Requires: \c object and \c operand are addable.
 333     \b Effects: \c operand is added to \c object.
 334     \par \b Efficieny: There is one additional copy of
 335     \c Type \c object compared to inplace \c operator \c += */
 336 template<class Type, class OperandT>
 337 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 338 operator + (Type object, const OperandT& operand)
 339 {
 340     return object += operand;
 341 }
 342
 343 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 344
 345 template<class Type, class OperandT>
 346 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 347 operator + (const Type& object, const OperandT& operand)
 348 {
 349     Type temp = object;
 350     return boost::move(temp += operand);
 351 }
 352
 353 template<class Type, class OperandT>
 354 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 355 operator + (Type&& object, const OperandT& operand)
 356 {
 357     return boost::move(object += operand);
 358 }
 359
 360 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 361
 362 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 363 //------------------------------------------------------------------------------
 364 //- T op + (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'}
 365 //------------------------------------------------------------------------------
 366 /** \par \b Requires: \c object and \c operand are addable.
 367     \b Effects: \c operand is added to \c object.
 368     \par \b Efficieny: There is one additional copy of
 369     \c Type \c object compared to inplace \c operator \c += */
 370 template<class Type, class OperandT>
 371 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 372 operator + (const OperandT& operand, Type object)
 373 {
 374     return object += operand;
 375 }
 376
 377 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 378
 379 template<class Type, class OperandT>
 380 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 381 operator + (const OperandT& operand, const Type& object)
 382 {
 383     Type temp = object;
 384     return boost::move(temp += operand);
 385 }
 386
 387 template<class Type, class OperandT>
 388 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 389 operator + (const OperandT& operand, Type&& object)
 390 {
 391     return boost::move(object += operand);
 392 }
 393
 394 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 395
 396 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 397 //------------------------------------------------------------------------------
 398 //- T op + (T, c P&) T:{S}|{M} P:{S}|{M}
 399 //------------------------------------------------------------------------------
 400 /** \par \b Requires: \c object and \c operand are addable.
 401     \b Effects: \c operand is added to \c object.
 402     \par \b Efficieny: There is one additional copy of
 403     \c Type \c object compared to inplace \c operator \c += */
 404 template<class Type>
 405 typename enable_if<is_interval_container<Type>, Type>::type
 406 operator + (Type object, const Type& operand)
 407 {
 408     return object += operand;
 409 }
 410
 411 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 412
 413 template<class Type>
 414 typename enable_if<is_interval_container<Type>, Type>::type
 415 operator + (const Type& object, const Type& operand)
 416 {
 417     Type temp = object;
 418     return boost::move(temp += operand);
 419 }
 420
 421 template<class Type>
 422 typename enable_if<is_interval_container<Type>, Type>::type
 423 operator + (Type&& object, const Type& operand)
 424 {
 425     return boost::move(object += operand);
 426 }
 427
 428 template<class Type>
 429 typename enable_if<is_interval_container<Type>, Type>::type
 430 operator + (const Type& operand, Type&& object)
 431 {
 432     return boost::move(object += operand);
 433 }
 434
 435 template<class Type>
 436 typename enable_if<is_interval_container<Type>, Type>::type
 437 operator + (Type&& object, Type&& operand)
 438 {
 439     return boost::move(object += operand);
 440 }
 441
 442 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 443
 444 //------------------------------------------------------------------------------
 445 //- Addition |=, |
 446 //------------------------------------------------------------------------------
 447
 448 //------------------------------------------------------------------------------
 449 //- T& op |=(c P&) T:{S}|{M} P:{e i}|{b p}
 450 //------------------------------------------------------------------------------
 451 /** \par \b Requires: Types \c Type and \c OperandT are addable.
 452     \par \b Effects: \c operand is added to \c object.
 453     \par \b Returns: A reference to \c object.
 454     \b Complexity:
 455 \code
 456                   \ OperandT:                      interval
 457                    \         element     segment   container
 458 Type:
 459        interval container    O(log n)     O(n)     O(m log(n+m))
 460
 461              interval_set               amortized
 462     spearate_interval_set                O(log n)
 463
 464 n = object.interval_count()
 465 m = operand.interval_count()
 466 \endcode
 467
 468 For the addition of \b elements, \b segments and \b interval \b containers
 469 complexity is \b logarithmic, \b linear and \b loglinear respectively.
 470 For \c interval_sets and \c separate_interval_sets addition of segments
 471 is \b amortized \b logarithmic.
 472 */
 473 template<class Type, class OperandT>
 474 typename enable_if<is_right_intra_combinable<Type, OperandT>, Type>::type&
 475 operator |= (Type& object, const OperandT& operand)
 476 {
 477     return object += operand;
 478 }
 479
 480 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 481 //------------------------------------------------------------------------------
 482 //- T op | (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
 483 //------------------------------------------------------------------------------
 484 /** \par \b Requires: \c object and \c operand are addable.
 485     \b Effects: \c operand is added to \c object.
 486     \par \b Efficieny: There is one additional copy of
 487     \c Type \c object compared to inplace \c operator \c |= */
 488 template<class Type, class OperandT>
 489 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 490 operator | (Type object, const OperandT& operand)
 491 {
 492     return object += operand;
 493 }
 494
 495 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 496
 497 template<class Type, class OperandT>
 498 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 499 operator | (const Type& object, const OperandT& operand)
 500 {
 501     Type temp = object;
 502     return boost::move(temp += operand);
 503 }
 504
 505 template<class Type, class OperandT>
 506 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 507 operator | (Type&& object, const OperandT& operand)
 508 {
 509     return boost::move(object += operand);
 510 }
 511
 512 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 513
 514 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 515 //------------------------------------------------------------------------------
 516 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
 517 //------------------------------------------------------------------------------
 518 /** \par \b Requires: \c object and \c operand are addable.
 519     \b Effects: \c operand is added to \c object.
 520     \par \b Efficieny: There is one additional copy of
 521     \c Type \c object compared to inplace \c operator \c |= */
 522 template<class Type, class OperandT>
 523 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 524 operator | (const OperandT& operand, Type object)
 525 {
 526     return object += operand;
 527 }
 528
 529 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 530
 531 template<class Type, class OperandT>
 532 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 533 operator | (const OperandT& operand, const Type& object)
 534 {
 535     Type temp = object;
 536     return boost::move(temp += operand);
 537 }
 538
 539 template<class Type, class OperandT>
 540 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
 541 operator | (const OperandT& operand, Type&& object)
 542 {
 543     return boost::move(object += operand);
 544 }
 545
 546 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 547
 548 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 549 //------------------------------------------------------------------------------
 550 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
 551 //------------------------------------------------------------------------------
 552 /** \par \b Requires: \c object and \c operand are addable.
 553     \b Effects: \c operand is added to \c object.
 554     \par \b Efficieny: There is one additional copy of
 555     \c Type \c object compared to inplace \c operator \c |= */
 556 template<class Type>
 557 typename enable_if<is_interval_container<Type>, Type>::type
 558 operator | (Type object, const Type& operand)
 559 {
 560     return object += operand;
 561 }
 562 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 563
 564 template<class Type>
 565 typename enable_if<is_interval_container<Type>, Type>::type
 566 operator | (const Type& object, const Type& operand)
 567 {
 568     Type temp = object;
 569     return boost::move(temp += operand);
 570 }
 571
 572 template<class Type>
 573 typename enable_if<is_interval_container<Type>, Type>::type
 574 operator | (Type&& object, const Type& operand)
 575 {
 576     return boost::move(object += operand);
 577 }
 578
 579 template<class Type>
 580 typename enable_if<is_interval_container<Type>, Type>::type
 581 operator | (const Type& operand, Type&& object)
 582 {
 583     return boost::move(object += operand);
 584 }
 585
 586 template<class Type>
 587 typename enable_if<is_interval_container<Type>, Type>::type
 588 operator | (Type&& object, Type&& operand)
 589 {
 590     return boost::move(object += operand);
 591 }
 592
 593 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 594
 595
 596 //==============================================================================
 597 //= Insertion<IntervalSet|IntervalSet>
 598 //==============================================================================
 599 //------------------------------------------------------------------------------
 600 //- T& insert(T&, c P&) T:{S}|{M} P:{S'}|{M'}
 601 //------------------------------------------------------------------------------
 602 template<class Type, class OperandT>
 603 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
 604 insert(Type& object, const OperandT& operand)
 605 {
 606     typename Type::iterator prior_ = object.end();
 607     ICL_const_FORALL(typename OperandT, elem_, operand)
 608         insert(object, prior_, *elem_);
 609
 610     return object;
 611 }
 612
 613 //==============================================================================
 614 //= Erasure<IntervalSet|IntervalSet>
 615 //==============================================================================
 616 //------------------------------------------------------------------------------
 617 //- T& erase(T&, c P&) T:{S}|{M} P:{S'}|{S' M'}
 618 //------------------------------------------------------------------------------
 619 template<class Type, class OperandT>
 620 typename enable_if<combines_right_to_interval_container<Type, OperandT>,
 621                    Type>::type&
 622 erase(Type& object, const OperandT& operand)
 623 {
 624     typedef typename OperandT::const_iterator const_iterator;
 625
 626     if(icl::is_empty(operand))
 627         return object;
 628
 629     const_iterator common_lwb, common_upb;
 630     if(!Set::common_range(common_lwb, common_upb, operand, object))
 631         return object;
 632
 633     const_iterator it_ = common_lwb;
 634     while(it_ != common_upb)
 635         icl::erase(object, *it_++);
 636
 637     return object;
 638 }
 639
 640 //==============================================================================
 641 //= Subtraction<IntervalSet|IntervalSet>
 642 //==============================================================================
 643 //------------------------------------------------------------------------------
 644 //- T& op -= (c P&) T:{M} P:{M'}
 645 //------------------------------------------------------------------------------
 646 /** \par \b Requires: Types \c Type and \c OperandT are subtractable.
 647     \par \b Effects: \c operand is subtracted from \c object.
 648     \par \b Returns: A reference to \c object.
 649     \b Complexity:
 650 \code
 651                   \ OperandT:                      interval
 652                    \         element    segment    container
 653 Type:
 654        interval container    O(log n)     O(n)     O(m log(n+m))
 655
 656                                        amortized
 657             interval_sets               O(log n)
 658
 659 n = object.interval_count()
 660 m = operand.interval_count()
 661 \endcode
 662
 663 For the subtraction of \em elements, \b segments and \b interval \b containers
 664 complexity is \b logarithmic, \b linear and \b loglinear respectively.
 665 For interval sets subtraction of segments
 666 is \b amortized \b logarithmic.
 667 */
 668 template<class Type, class OperandT>
 669 typename enable_if<is_concept_compatible<is_interval_map, Type, OperandT>,
 670                    Type>::type&
 671 operator -=(Type& object, const OperandT& operand)
 672 {
 673     ICL_const_FORALL(typename OperandT, elem_, operand)
 674         icl::subtract(object, *elem_);
 675
 676     return object;
 677 }
 678
 679 //------------------------------------------------------------------------------
 680 //- T& op -= (c P&) T:{S}|{M} P:{e i}|{b p}
 681 //------------------------------------------------------------------------------
 682 template<class Type, class OperandT>
 683 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
 684 operator -= (Type& object, const OperandT& operand)
 685 {
 686     return icl::subtract(object, operand);
 687 }
 688
 689 //------------------------------------------------------------------------------
 690 //- T& op -= (c P&) T:{M} P:{e i}
 691 //------------------------------------------------------------------------------
 692 template<class Type, class OperandT>
 693 typename enable_if<is_cross_derivative<Type, OperandT>, Type>::type&
 694 operator -= (Type& object, const OperandT& operand)
 695 {
 696     return icl::erase(object, operand);
 697 }
 698
 699 //------------------------------------------------------------------------------
 700 //- T& op -= (c P&) T:{S M} P:{S'}
 701 //------------------------------------------------------------------------------
 702 template<class Type, class IntervalSetT>
 703 typename enable_if<combines_right_to_interval_set<Type, IntervalSetT>,
 704                    Type>::type&
 705 operator -= (Type& object, const IntervalSetT& operand)
 706 {
 707     return erase(object, operand);
 708 }
 709
 710 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 711 //------------------------------------------------------------------------------
 712 //- T op - (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
 713 //------------------------------------------------------------------------------
 714 template<class Type, class OperandT>
 715 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
 716 operator - (Type object, const OperandT& operand)
 717 {
 718     return object -= operand;
 719 }
 720
 721 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 722
 723 template<class Type, class OperandT>
 724 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
 725 operator - (const Type& object, const OperandT& operand)
 726 {
 727     Type temp = object;
 728     return boost::move(temp -= operand);
 729 }
 730
 731 template<class Type, class OperandT>
 732 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
 733 operator - (Type&& object, const OperandT& operand)
 734 {
 735     return boost::move(object -= operand);
 736 }
 737
 738 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 739
 740 //==============================================================================
 741 //= Intersection<IntervalSet|IntervalSet>
 742 //==============================================================================
 743 //------------------------------------------------------------------------------
 744 //- void add_intersection(T&, c T&, c P&) T:{S M} P:{S'}
 745 //------------------------------------------------------------------------------
 746 template<class Type, class OperandT>
 747 typename enable_if<mpl::and_<is_interval_set<Type>,
 748                              combines_right_to_interval_set<Type, OperandT> >,
 749                    void>::type
 750 add_intersection(Type& section, const Type& object, const OperandT& operand)
 751 {
 752     typedef typename OperandT::const_iterator const_iterator;
 753
 754     if(operand.empty())
 755         return;
 756
 757     const_iterator common_lwb, common_upb;
 758     if(!Set::common_range(common_lwb, common_upb, operand, object))
 759         return;
 760
 761     const_iterator it_ = common_lwb;
 762     while(it_ != common_upb)
 763         icl::add_intersection(section, object, key_value<OperandT>(it_++));
 764 }
 765
 766 //------------------------------------------------------------------------------
 767 //- T& op &=(T&, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
 768 //------------------------------------------------------------------------------
 769 template<class Type, class OperandT>
 770 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type&
 771 operator &= (Type& object, const OperandT& operand)
 772 {
 773     Type intersection;
 774     add_intersection(intersection, object, operand);
 775     object.swap(intersection);
 776     return object;
 777 }
 778
 779 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 780 //------------------------------------------------------------------------------
 781 //- T op & (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
 782 //------------------------------------------------------------------------------
 783 template<class Type, class OperandT>
 784 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
 785 operator & (Type object, const OperandT& operand)
 786 {
 787     return object &= operand;
 788 }
 789
 790 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 791
 792 template<class Type, class OperandT>
 793 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
 794 operator & (const Type& object, const OperandT& operand)
 795 {
 796     Type temp = object;
 797     return boost::move(temp &= operand);
 798 }
 799
 800 template<class Type, class OperandT>
 801 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
 802 operator & (Type&& object, const OperandT& operand)
 803 {
 804     return boost::move(object &= operand);
 805 }
 806
 807 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 808
 809 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 810 //------------------------------------------------------------------------------
 811 //- T op & (c P&, T) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
 812 //------------------------------------------------------------------------------
 813 template<class Type, class OperandT>
 814 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
 815 operator & (const OperandT& operand, Type object)
 816 {
 817     return object &= operand;
 818 }
 819
 820 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 821
 822 template<class Type, class OperandT>
 823 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
 824 operator & (const OperandT& operand, const Type& object)
 825 {
 826     Type temp = object;
 827     return boost::move(temp &= operand);
 828 }
 829
 830 template<class Type, class OperandT>
 831 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
 832 operator & (const OperandT& operand, Type&& object)
 833 {
 834     return boost::move(object &= operand);
 835 }
 836
 837 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 838
 839 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 840 //------------------------------------------------------------------------------
 841 //- T op & (T, c T&) T:{S M}
 842 //------------------------------------------------------------------------------
 843 template<class Type>
 844 typename enable_if<is_interval_container<Type>, Type>::type
 845 operator & (Type object, const Type& operand)
 846 {
 847     return object &= operand;
 848 }
 849
 850 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 851
 852 template<class Type>
 853 typename enable_if<is_interval_container<Type>, Type>::type
 854 operator & (const Type& object, const Type& operand)
 855 {
 856     Type temp = object;
 857     return boost::move(temp &= operand);
 858 }
 859
 860 template<class Type>
 861 typename enable_if<is_interval_container<Type>, Type>::type
 862 operator & (Type&& object, const Type& operand)
 863 {
 864     return boost::move(object &= operand);
 865 }
 866
 867 template<class Type>
 868 typename enable_if<is_interval_container<Type>, Type>::type
 869 operator & (const Type& operand, Type&& object)
 870 {
 871     return boost::move(object &= operand);
 872 }
 873
 874 template<class Type>
 875 typename enable_if<is_interval_container<Type>, Type>::type
 876 operator & (Type&& object, Type&& operand)
 877 {
 878     return boost::move(object &= operand);
 879 }
 880
 881 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 882
 883 //------------------------------------------------------------------------------
 884 //- intersects<IntervalSet|IntervalMap>
 885 //------------------------------------------------------------------------------
 886 //------------------------------------------------------------------------------
 887 //- bool intersects(c T&, c P&) T:{S}|{M} P:{e i}
 888 //------------------------------------------------------------------------------
 889 template<class Type, class CoType>
 890 typename enable_if<mpl::and_< is_interval_container<Type>
 891                             , boost::is_same<CoType, typename domain_type_of<Type>::type> >,
 892                    bool>::type
 893 intersects(const Type& left, const CoType& right)
 894 {
 895     return icl::contains(left, right);
 896 }
 897
 898 template<class Type, class CoType>
 899 typename enable_if<mpl::and_< is_interval_container<Type>
 900                             , boost::is_same<CoType, typename interval_type_of<Type>::type> >,
 901                    bool>::type
 902 intersects(const Type& left, const CoType& right)
 903 {
 904     return icl::find(left, right) != left.end();
 905 }
 906
 907
 908 template<class LeftT, class RightT>
 909 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
 910                              , mpl::or_<is_total<LeftT>, is_total<RightT> > >
 911                   , bool>::type
 912 intersects(const LeftT&, const RightT&)
 913 {
 914     return true;
 915 }
 916
 917 template<class LeftT, class RightT>
 918 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
 919                              , mpl::not_<mpl::or_< is_total<LeftT>
 920                                                  , is_total<RightT> > > >
 921                   , bool>::type
 922 intersects(const LeftT& left, const RightT& right)
 923 {
 924     typedef typename RightT::const_iterator const_iterator;
 925     LeftT intersection;
 926
 927     const_iterator right_common_lower_, right_common_upper_;
 928     if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
 929         return false;
 930
 931     const_iterator it_ = right_common_lower_;
 932     while(it_ != right_common_upper_)
 933     {
 934         icl::add_intersection(intersection, left, *it_++);
 935         if(!icl::is_empty(intersection))
 936             return true;
 937     }
 938     return false;
 939 }
 940
 941 template<class LeftT, class RightT>
 942 typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type
 943 intersects(const LeftT& left, const RightT& right)
 944 {
 945     typedef typename RightT::const_iterator const_iterator;
 946     LeftT intersection;
 947
 948     if(icl::is_empty(left) || icl::is_empty(right))
 949         return false;
 950
 951     const_iterator right_common_lower_, right_common_upper_;
 952     if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
 953         return false;
 954
 955     typename RightT::const_iterator it_ = right_common_lower_;
 956     while(it_ != right_common_upper_)
 957     {
 958         icl::add_intersection(intersection, left, key_value<RightT>(it_++));
 959         if(!icl::is_empty(intersection))
 960             return true;
 961     }
 962
 963     return false;
 964 }
 965
 966 /** \b Returns true, if \c left and \c right have no common elements.
 967     Intervals are interpreted as sequence of elements.
 968     \b Complexity: loglinear, if \c left and \c right are interval containers. */
 969 template<class LeftT, class RightT>
 970 typename enable_if<is_inter_combinable<LeftT, RightT>, bool>::type
 971 disjoint(const LeftT& left, const RightT& right)
 972 {
 973     return !intersects(left, right);
 974 }
 975
 976 /** \b Returns true, if \c left and \c right have no common elements.
 977     Intervals are interpreted as sequence of elements.
 978     \b Complexity: logarithmic, if \c AssociateT is an element type \c Type::element_type.
 979     linear, if \c AssociateT is a segment type \c Type::segment_type. */
 980 template<class Type, class AssociateT>
 981 typename enable_if<is_inter_derivative<Type, AssociateT>, bool>::type
 982 disjoint(const Type& left, const AssociateT& right)
 983 {
 984     return !intersects(left,right);
 985 }
 986
 987
 988 //==============================================================================
 989 //= Symmetric difference<IntervalSet|IntervalSet>
 990 //==============================================================================
 991 //------------------------------------------------------------------------------
 992 //- Symmetric difference ^=, ^
 993 //------------------------------------------------------------------------------
 994 //------------------------------------------------------------------------------
 995 //- T& op ^=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
 996 //------------------------------------------------------------------------------
 997 template<class Type, class OperandT>
 998 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
 999 operator ^= (Type& object, const OperandT& operand)
1000 {
1001     return icl::flip(object, operand);
1002 }
1003
1004 //------------------------------------------------------------------------------
1005 //- T& op ^=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
1006 //------------------------------------------------------------------------------
1007 template<class Type, class OperandT>
1008 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
1009 operator ^= (Type& object, const OperandT& operand)
1010 {
1011     return icl::flip(object, operand);
1012 }
1013
1014 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1015 //------------------------------------------------------------------------------
1016 //- T op ^ (T, c P&) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
1017 //------------------------------------------------------------------------------
1018 template<class Type, class OperandT>
1019 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1020 operator ^ (Type object, const OperandT& operand)
1021 {
1022     return object ^= operand;
1023 }
1024
1025 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1026
1027 template<class Type, class OperandT>
1028 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1029 operator ^ (const Type& object, const OperandT& operand)
1030 {
1031     Type temp = object;
1032     return boost::move(temp ^= operand);
1033 }
1034
1035 template<class Type, class OperandT>
1036 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1037 operator ^ (Type&& object, const OperandT& operand)
1038 {
1039     return boost::move(object ^= operand);
1040 }
1041
1042 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1043
1044 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1045 //------------------------------------------------------------------------------
1046 //- T op ^ (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
1047 //------------------------------------------------------------------------------
1048 template<class Type, class OperandT>
1049 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1050 operator ^ (const OperandT& operand, Type object)
1051 {
1052     return object ^= operand;
1053 }
1054
1055 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1056
1057 template<class Type, class OperandT>
1058 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1059 operator ^ (const OperandT& operand, const Type& object)
1060 {
1061     Type temp = object;
1062     return boost::move(temp ^= operand);
1063 }
1064
1065 template<class Type, class OperandT>
1066 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1067 operator ^ (const OperandT& operand, Type&& object)
1068 {
1069     return boost::move(object ^= operand);
1070 }
1071
1072 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1073
1074 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1075 //------------------------------------------------------------------------------
1076 //- T op ^ (T, c T&) T:{S M}
1077 //------------------------------------------------------------------------------
1078 template<class Type>
1079 typename enable_if<is_interval_container<Type>, Type>::type
1080 operator ^ (typename Type::overloadable_type object, const Type& operand)
1081 {
1082     return object ^= operand;
1083 }
1084
1085 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1086
1087 template<class Type>
1088 typename enable_if<is_interval_container<Type>, Type>::type
1089 operator ^ (const Type& object, const Type& operand)
1090 {
1091     Type temp = object;
1092     return boost::move(temp ^= operand);
1093 }
1094
1095 template<class Type>
1096 typename enable_if<is_interval_container<Type>, Type>::type
1097 operator ^ (Type&& object, const Type& operand)
1098 {
1099     return boost::move(object ^= operand);
1100 }
1101
1102 template<class Type>
1103 typename enable_if<is_interval_container<Type>, Type>::type
1104 operator ^ (const Type& operand, Type&& object)
1105 {
1106     return boost::move(object ^= operand);
1107 }
1108
1109 template<class Type>
1110 typename enable_if<is_interval_container<Type>, Type>::type
1111 operator ^ (Type&& object, Type&& operand)
1112 {
1113     return boost::move(object ^= operand);
1114 }
1115
1116 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1117
1118 //==========================================================================
1119 //= Element Iteration <IntervalSet|IntervalMap>
1120 //==========================================================================
1121 //--------------------------------------------------------------------------
1122 //- Forward
1123 //--------------------------------------------------------------------------
1124 template<class Type>
1125 typename enable_if
1126 <mpl::and_< is_interval_container<Type>
1127           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1128 typename Type::element_iterator>::type
1129 elements_begin(Type& object)
1130 {
1131     return typename Type::element_iterator(object.begin());
1132 }
1133
1134 template<class Type>
1135 typename enable_if
1136 <mpl::and_< is_interval_container<Type>
1137           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1138 typename Type::element_iterator>::type
1139 elements_end(Type& object)
1140 {
1141     return typename Type::element_iterator(object.end());
1142 }
1143
1144 template<class Type>
1145 typename enable_if
1146 <mpl::and_< is_interval_container<Type>
1147           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1148 typename Type::element_const_iterator>::type
1149 elements_begin(const Type& object)
1150 {
1151     return typename Type::element_const_iterator(object.begin());
1152 }
1153
1154 template<class Type>
1155 typename enable_if
1156 <mpl::and_< is_interval_container<Type>
1157           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1158 typename Type::element_const_iterator>::type
1159 elements_end(const Type& object)
1160 {
1161     return typename Type::element_const_iterator(object.end());
1162 }
1163
1164 //--------------------------------------------------------------------------
1165 //- Reverse
1166 //--------------------------------------------------------------------------
1167 template<class Type>
1168 typename enable_if
1169 <mpl::and_< is_interval_container<Type>
1170           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1171 typename Type::element_reverse_iterator>::type
1172 elements_rbegin(Type& object)
1173 {
1174     return typename Type::element_reverse_iterator(object.rbegin());
1175 }
1176
1177 template<class Type>
1178 typename enable_if
1179 <mpl::and_< is_interval_container<Type>
1180           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1181 typename Type::element_reverse_iterator>::type
1182 elements_rend(Type& object)
1183 {
1184     return typename Type::element_reverse_iterator(object.rend());
1185 }
1186
1187 template<class Type>
1188 typename enable_if
1189 <mpl::and_< is_interval_container<Type>
1190           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1191 typename Type::element_const_reverse_iterator>::type
1192 elements_rbegin(const Type& object)
1193 {
1194     return typename Type::element_const_reverse_iterator(object.rbegin());
1195 }
1196
1197 template<class Type>
1198 typename enable_if
1199 <mpl::and_< is_interval_container<Type>
1200           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1201 typename Type::element_const_reverse_iterator>::type
1202 elements_rend(const Type& object)
1203 {
1204     return typename Type::element_const_reverse_iterator(object.rend());
1205 }
1206
1207 }} // namespace boost icl
1208
1209 #endif
1210
1211