icl/concept/interval_associator.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2010-2010: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_CONCEPT_INTERVAL_ASSOCIATOR_HPP_JOFA_100920
0009 #define BOOST_ICL_CONCEPT_INTERVAL_ASSOCIATOR_HPP_JOFA_100920
0010
0011 #include <boost/range/iterator_range.hpp>
0012 #include <boost/icl/type_traits/domain_type_of.hpp>
0013 #include <boost/icl/type_traits/interval_type_of.hpp>
0014 #include <boost/icl/type_traits/is_combinable.hpp>
0015 #include <boost/icl/detail/set_algo.hpp>
0016 #include <boost/icl/detail/map_algo.hpp>
0017 #include <boost/icl/detail/interval_set_algo.hpp>
0018 #include <boost/icl/detail/interval_map_algo.hpp>
0019 #include <boost/icl/concept/interval.hpp>
0020
0021 namespace boost{ namespace icl
0022 {
0023
0024 //==============================================================================
0025 //= Containedness<IntervalSet|IntervalMap>
0026 //==============================================================================
0027 //------------------------------------------------------------------------------
0028 //- bool within(c T&, c P&) T={Set,Map} P={e i b p S M}
0029 //------------------------------------------------------------------------------
0030 template<class SubT, class SuperT>
0031 typename enable_if<is_interval_container<SuperT>, bool>::type
0032 within(const SubT& sub, const SuperT& super)
0033 {
0034     return icl::contains(super, sub);
0035 }
0036
0037 //==============================================================================
0038 //= Equivalences and Orderings<IntervalSet|IntervalMap>
0039 //==============================================================================
0040 template<class Type>
0041 inline typename enable_if<is_interval_container<Type>, bool>::type
0042 operator == (const Type& left, const Type& right)
0043 {
0044     return Set::lexicographical_equal(left, right);
0045 }
0046
0047 template<class Type>
0048 inline typename enable_if<is_interval_container<Type>, bool>::type
0049 operator < (const Type& left, const Type& right)
0050 {
0051     typedef typename Type::segment_compare segment_compare;
0052     return std::lexicographical_compare(
0053         left.begin(), left.end(), right.begin(), right.end(),
0054         segment_compare()
0055         );
0056 }
0057
0058 /** Returns true, if \c left and \c right contain the same elements.
0059     Complexity: linear. */
0060 template<class LeftT, class RightT>
0061 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
0062 is_element_equal(const LeftT& left, const RightT& right)
0063 {
0064     return Interval_Set::is_element_equal(left, right);
0065 }
0066
0067 /** Returns true, if \c left is lexicographically less than \c right.
0068     Intervals are interpreted as sequence of elements.
0069     Complexity: linear. */
0070 template<class LeftT, class RightT>
0071 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
0072 is_element_less(const LeftT& left, const RightT& right)
0073 {
0074     return Interval_Set::is_element_less(left, right);
0075 }
0076
0077 /** Returns true, if \c left is lexicographically greater than \c right.
0078     Intervals are interpreted as sequence of elements.
0079     Complexity: linear. */
0080 template<class LeftT, class RightT>
0081 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
0082 is_element_greater(const LeftT& left, const RightT& right)
0083 {
0084     return Interval_Set::is_element_greater(left, right);
0085 }
0086
0087 //------------------------------------------------------------------------------
0088 template<class LeftT, class RightT>
0089 typename enable_if<is_inter_combinable<LeftT, RightT>, int>::type
0090 inclusion_compare(const LeftT& left, const RightT& right)
0091 {
0092     return Interval_Set::subset_compare(left, right,
0093                                         left.begin(), left.end(),
0094                                         right.begin(), right.end());
0095 }
0096
0097 //------------------------------------------------------------------------------
0098 template<class LeftT, class RightT>
0099 typename enable_if< is_concept_compatible<is_interval_map, LeftT, RightT>,
0100                     bool >::type
0101 is_distinct_equal(const LeftT& left, const RightT& right)
0102 {
0103     return Map::lexicographical_distinct_equal(left, right);
0104 }
0105
0106 //==============================================================================
0107 //= Size<IntervalSet|IntervalMap>
0108 //==============================================================================
0109 template<class Type>
0110 typename enable_if<is_interval_container<Type>, std::size_t>::type
0111 iterative_size(const Type& object)
0112 {
0113     return object.iterative_size();
0114 }
0115
0116 template<class Type>
0117 typename enable_if
0118 < mpl::and_< is_interval_container<Type>
0119            , is_discrete<typename Type::domain_type> >
0120 , typename Type::size_type
0121 >::type
0122 cardinality(const Type& object)
0123 {
0124     typedef typename Type::size_type size_type;
0125     //CL typedef typename Type::interval_type interval_type;
0126
0127     size_type size = identity_element<size_type>::value();
0128     ICL_const_FORALL(typename Type, it, object)
0129         size += icl::cardinality(key_value<Type>(it));
0130     return size;
0131
0132 }
0133
0134 template<class Type>
0135 typename enable_if
0136 < mpl::and_< is_interval_container<Type>
0137            , mpl::not_<is_discrete<typename Type::domain_type> > >
0138 , typename Type::size_type
0139 >::type
0140 cardinality(const Type& object)
0141 {
0142     typedef typename Type::size_type size_type;
0143     //CL typedef typename Type::interval_type interval_type;
0144
0145     size_type size = identity_element<size_type>::value();
0146     size_type interval_size;
0147     ICL_const_FORALL(typename Type, it, object)
0148     {
0149         interval_size = icl::cardinality(key_value<Type>(it));
0150         if(interval_size == icl::infinity<size_type>::value())
0151             return interval_size;
0152         else
0153             size += interval_size;
0154     }
0155     return size;
0156 }
0157
0158 template<class Type>
0159 inline typename enable_if<is_interval_container<Type>, typename Type::size_type>::type
0160 size(const Type& object)
0161 {
0162     return icl::cardinality(object);
0163 }
0164
0165 template<class Type>
0166 typename enable_if<is_interval_container<Type>, typename Type::difference_type>::type
0167 length(const Type& object)
0168 {
0169     typedef typename Type::difference_type difference_type;
0170     typedef typename Type::const_iterator  const_iterator;
0171     difference_type length = identity_element<difference_type>::value();
0172     const_iterator it_ = object.begin();
0173
0174     while(it_ != object.end())
0175         length += icl::length(key_value<Type>(it_++));
0176     return length;
0177 }
0178
0179 template<class Type>
0180 typename enable_if<is_interval_container<Type>, std::size_t>::type
0181 interval_count(const Type& object)
0182 {
0183     return icl::iterative_size(object);
0184 }
0185
0186
0187 template<class Type>
0188 typename enable_if< is_interval_container<Type>
0189                   , typename Type::difference_type >::type
0190 distance(const Type& object)
0191 {
0192     typedef typename Type::difference_type DiffT;
0193     typedef typename Type::const_iterator const_iterator;
0194     const_iterator it_ = object.begin(), pred_;
0195     DiffT dist = identity_element<DiffT>::value();
0196
0197     if(it_ != object.end())
0198         pred_ = it_++;
0199
0200     while(it_ != object.end())
0201         dist += icl::distance(key_value<Type>(pred_++), key_value<Type>(it_++));
0202
0203     return dist;
0204 }
0205
0206 //==============================================================================
0207 //= Range<IntervalSet|IntervalMap>
0208 //==============================================================================
0209 template<class Type>
0210 typename enable_if<is_interval_container<Type>,
0211                    typename Type::interval_type>::type
0212 hull(const Type& object)
0213 {
0214     return
0215         icl::is_empty(object)
0216             ? identity_element<typename Type::interval_type>::value()
0217             : icl::hull( key_value<Type>(object.begin()),
0218                          key_value<Type>(object.rbegin()) );
0219 }
0220
0221 template<class Type>
0222 typename enable_if<is_interval_container<Type>,
0223                    typename domain_type_of<Type>::type>::type
0224 lower(const Type& object)
0225 {
0226     typedef typename domain_type_of<Type>::type DomainT;
0227     return
0228         icl::is_empty(object)
0229             ? unit_element<DomainT>::value()
0230             : icl::lower( key_value<Type>(object.begin()) );
0231 }
0232
0233 template<class Type>
0234 typename enable_if<is_interval_container<Type>,
0235                    typename domain_type_of<Type>::type>::type
0236 upper(const Type& object)
0237 {
0238     typedef typename domain_type_of<Type>::type DomainT;
0239     return
0240         icl::is_empty(object)
0241             ? identity_element<DomainT>::value()
0242             : icl::upper( key_value<Type>(object.rbegin()) );
0243 }
0244
0245 //------------------------------------------------------------------------------
0246 template<class Type>
0247 typename enable_if
0248 < mpl::and_< is_interval_container<Type>
0249            , is_discrete<typename domain_type_of<Type>::type> >
0250 , typename domain_type_of<Type>::type>::type
0251 first(const Type& object)
0252 {
0253     typedef typename domain_type_of<Type>::type DomainT;
0254     return
0255         icl::is_empty(object)
0256             ? unit_element<DomainT>::value()
0257             : icl::first( key_value<Type>(object.begin()) );
0258 }
0259
0260 template<class Type>
0261 typename enable_if
0262 < mpl::and_< is_interval_container<Type>
0263            , is_discrete<typename domain_type_of<Type>::type> >
0264 , typename domain_type_of<Type>::type>::type
0265 last(const Type& object)
0266 {
0267     typedef typename domain_type_of<Type>::type DomainT;
0268     return
0269         icl::is_empty(object)
0270             ? identity_element<DomainT>::value()
0271             : icl::last( key_value<Type>(object.rbegin()) );
0272 }
0273
0274
0275 //==============================================================================
0276 //= Addition<IntervalSet|IntervalMap>
0277 //==============================================================================
0278 //------------------------------------------------------------------------------
0279 //- T& op +=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
0280 //------------------------------------------------------------------------------
0281 /* \par \b Requires: \c OperandT is an addable derivative type of \c Type.
0282     \b Effects: \c operand is added to \c object.
0283     \par \b Returns: A reference to \c object.
0284     \b Complexity:
0285 \code
0286                   \ OperandT:
0287                    \         element     segment
0288 Type:
0289        interval container    O(log n)     O(n)
0290
0291              interval_set               amortized
0292     spearate_interval_set                O(log n)
0293
0294 n = object.interval_count()
0295 \endcode
0296
0297 For the addition of \b elements or \b segments
0298 complexity is \b logarithmic or \b linear respectively.
0299 For \c interval_sets and \c separate_interval_sets addition of segments
0300 is \b amortized \b logarithmic.
0301 */
0302 template<class Type, class OperandT>
0303 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
0304 operator += (Type& object, const OperandT& operand)
0305 {
0306     return icl::add(object, operand);
0307 }
0308
0309
0310 //------------------------------------------------------------------------------
0311 //- T& op +=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
0312 //------------------------------------------------------------------------------
0313 /** \par \b Requires: \c OperandT is an interval container addable to \c Type.
0314     \b Effects: \c operand is added to \c object.
0315     \par \b Returns: A reference to \c object.
0316     \b Complexity: loglinear */
0317 template<class Type, class OperandT>
0318 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
0319 operator += (Type& object, const OperandT& operand)
0320 {
0321     typename Type::iterator prior_ = object.end();
0322     ICL_const_FORALL(typename OperandT, elem_, operand)
0323         prior_ = icl::add(object, prior_, *elem_);
0324
0325     return object;
0326 }
0327
0328
0329 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0330 //------------------------------------------------------------------------------
0331 //- T op + (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
0332 //------------------------------------------------------------------------------
0333 /** \par \b Requires: \c object and \c operand are addable.
0334     \b Effects: \c operand is added to \c object.
0335     \par \b Efficieny: There is one additional copy of
0336     \c Type \c object compared to inplace \c operator \c += */
0337 template<class Type, class OperandT>
0338 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0339 operator + (Type object, const OperandT& operand)
0340 {
0341     return object += operand;
0342 }
0343
0344 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0345
0346 template<class Type, class OperandT>
0347 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0348 operator + (const Type& object, const OperandT& operand)
0349 {
0350     Type temp = object;
0351     return boost::move(temp += operand);
0352 }
0353
0354 template<class Type, class OperandT>
0355 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0356 operator + (Type&& object, const OperandT& operand)
0357 {
0358     return boost::move(object += operand);
0359 }
0360
0361 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0362
0363 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0364 //------------------------------------------------------------------------------
0365 //- T op + (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'}
0366 //------------------------------------------------------------------------------
0367 /** \par \b Requires: \c object and \c operand are addable.
0368     \b Effects: \c operand is added to \c object.
0369     \par \b Efficieny: There is one additional copy of
0370     \c Type \c object compared to inplace \c operator \c += */
0371 template<class Type, class OperandT>
0372 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0373 operator + (const OperandT& operand, Type object)
0374 {
0375     return object += operand;
0376 }
0377
0378 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0379
0380 template<class Type, class OperandT>
0381 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0382 operator + (const OperandT& operand, const Type& object)
0383 {
0384     Type temp = object;
0385     return boost::move(temp += operand);
0386 }
0387
0388 template<class Type, class OperandT>
0389 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0390 operator + (const OperandT& operand, Type&& object)
0391 {
0392     return boost::move(object += operand);
0393 }
0394
0395 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0396
0397 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0398 //------------------------------------------------------------------------------
0399 //- T op + (T, c P&) T:{S}|{M} P:{S}|{M}
0400 //------------------------------------------------------------------------------
0401 /** \par \b Requires: \c object and \c operand are addable.
0402     \b Effects: \c operand is added to \c object.
0403     \par \b Efficieny: There is one additional copy of
0404     \c Type \c object compared to inplace \c operator \c += */
0405 template<class Type>
0406 typename enable_if<is_interval_container<Type>, Type>::type
0407 operator + (Type object, const Type& operand)
0408 {
0409     return object += operand;
0410 }
0411
0412 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0413
0414 template<class Type>
0415 typename enable_if<is_interval_container<Type>, Type>::type
0416 operator + (const Type& object, const Type& operand)
0417 {
0418     Type temp = object;
0419     return boost::move(temp += operand);
0420 }
0421
0422 template<class Type>
0423 typename enable_if<is_interval_container<Type>, Type>::type
0424 operator + (Type&& object, const Type& operand)
0425 {
0426     return boost::move(object += operand);
0427 }
0428
0429 template<class Type>
0430 typename enable_if<is_interval_container<Type>, Type>::type
0431 operator + (const Type& operand, Type&& object)
0432 {
0433     return boost::move(object += operand);
0434 }
0435
0436 template<class Type>
0437 typename enable_if<is_interval_container<Type>, Type>::type
0438 operator + (Type&& object, Type&& operand)
0439 {
0440     return boost::move(object += operand);
0441 }
0442
0443 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0444
0445 //------------------------------------------------------------------------------
0446 //- Addition |=, |
0447 //------------------------------------------------------------------------------
0448
0449 //------------------------------------------------------------------------------
0450 //- T& op |=(c P&) T:{S}|{M} P:{e i}|{b p}
0451 //------------------------------------------------------------------------------
0452 /** \par \b Requires: Types \c Type and \c OperandT are addable.
0453     \par \b Effects: \c operand is added to \c object.
0454     \par \b Returns: A reference to \c object.
0455     \b Complexity:
0456 \code
0457                   \ OperandT:                      interval
0458                    \         element     segment   container
0459 Type:
0460        interval container    O(log n)     O(n)     O(m log(n+m))
0461
0462              interval_set               amortized
0463     spearate_interval_set                O(log n)
0464
0465 n = object.interval_count()
0466 m = operand.interval_count()
0467 \endcode
0468
0469 For the addition of \b elements, \b segments and \b interval \b containers
0470 complexity is \b logarithmic, \b linear and \b loglinear respectively.
0471 For \c interval_sets and \c separate_interval_sets addition of segments
0472 is \b amortized \b logarithmic.
0473 */
0474 template<class Type, class OperandT>
0475 typename enable_if<is_right_intra_combinable<Type, OperandT>, Type>::type&
0476 operator |= (Type& object, const OperandT& operand)
0477 {
0478     return object += operand;
0479 }
0480
0481 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0482 //------------------------------------------------------------------------------
0483 //- T op | (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
0484 //------------------------------------------------------------------------------
0485 /** \par \b Requires: \c object and \c operand are addable.
0486     \b Effects: \c operand is added to \c object.
0487     \par \b Efficieny: There is one additional copy of
0488     \c Type \c object compared to inplace \c operator \c |= */
0489 template<class Type, class OperandT>
0490 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0491 operator | (Type object, const OperandT& operand)
0492 {
0493     return object += operand;
0494 }
0495
0496 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0497
0498 template<class Type, class OperandT>
0499 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0500 operator | (const Type& object, const OperandT& operand)
0501 {
0502     Type temp = object;
0503     return boost::move(temp += operand);
0504 }
0505
0506 template<class Type, class OperandT>
0507 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0508 operator | (Type&& object, const OperandT& operand)
0509 {
0510     return boost::move(object += operand);
0511 }
0512
0513 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0514
0515 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0516 //------------------------------------------------------------------------------
0517 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
0518 //------------------------------------------------------------------------------
0519 /** \par \b Requires: \c object and \c operand are addable.
0520     \b Effects: \c operand is added to \c object.
0521     \par \b Efficieny: There is one additional copy of
0522     \c Type \c object compared to inplace \c operator \c |= */
0523 template<class Type, class OperandT>
0524 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0525 operator | (const OperandT& operand, Type object)
0526 {
0527     return object += operand;
0528 }
0529
0530 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0531
0532 template<class Type, class OperandT>
0533 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0534 operator | (const OperandT& operand, const Type& object)
0535 {
0536     Type temp = object;
0537     return boost::move(temp += operand);
0538 }
0539
0540 template<class Type, class OperandT>
0541 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
0542 operator | (const OperandT& operand, Type&& object)
0543 {
0544     return boost::move(object += operand);
0545 }
0546
0547 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0548
0549 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0550 //------------------------------------------------------------------------------
0551 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
0552 //------------------------------------------------------------------------------
0553 /** \par \b Requires: \c object and \c operand are addable.
0554     \b Effects: \c operand is added to \c object.
0555     \par \b Efficieny: There is one additional copy of
0556     \c Type \c object compared to inplace \c operator \c |= */
0557 template<class Type>
0558 typename enable_if<is_interval_container<Type>, Type>::type
0559 operator | (Type object, const Type& operand)
0560 {
0561     return object += operand;
0562 }
0563 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0564
0565 template<class Type>
0566 typename enable_if<is_interval_container<Type>, Type>::type
0567 operator | (const Type& object, const Type& operand)
0568 {
0569     Type temp = object;
0570     return boost::move(temp += operand);
0571 }
0572
0573 template<class Type>
0574 typename enable_if<is_interval_container<Type>, Type>::type
0575 operator | (Type&& object, const Type& operand)
0576 {
0577     return boost::move(object += operand);
0578 }
0579
0580 template<class Type>
0581 typename enable_if<is_interval_container<Type>, Type>::type
0582 operator | (const Type& operand, Type&& object)
0583 {
0584     return boost::move(object += operand);
0585 }
0586
0587 template<class Type>
0588 typename enable_if<is_interval_container<Type>, Type>::type
0589 operator | (Type&& object, Type&& operand)
0590 {
0591     return boost::move(object += operand);
0592 }
0593
0594 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0595
0596
0597 //==============================================================================
0598 //= Insertion<IntervalSet|IntervalSet>
0599 //==============================================================================
0600 //------------------------------------------------------------------------------
0601 //- T& insert(T&, c P&) T:{S}|{M} P:{S'}|{M'}
0602 //------------------------------------------------------------------------------
0603 template<class Type, class OperandT>
0604 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
0605 insert(Type& object, const OperandT& operand)
0606 {
0607     typename Type::iterator prior_ = object.end();
0608     ICL_const_FORALL(typename OperandT, elem_, operand)
0609         insert(object, prior_, *elem_);
0610
0611     return object;
0612 }
0613
0614 //==============================================================================
0615 //= Erasure<IntervalSet|IntervalSet>
0616 //==============================================================================
0617 //------------------------------------------------------------------------------
0618 //- T& erase(T&, c P&) T:{S}|{M} P:{S'}|{S' M'}
0619 //------------------------------------------------------------------------------
0620 template<class Type, class OperandT>
0621 typename enable_if<combines_right_to_interval_container<Type, OperandT>,
0622                    Type>::type&
0623 erase(Type& object, const OperandT& operand)
0624 {
0625     typedef typename OperandT::const_iterator const_iterator;
0626
0627     if(icl::is_empty(operand))
0628         return object;
0629
0630     const_iterator common_lwb, common_upb;
0631     if(!Set::common_range(common_lwb, common_upb, operand, object))
0632         return object;
0633
0634     const_iterator it_ = common_lwb;
0635     while(it_ != common_upb)
0636         icl::erase(object, *it_++);
0637
0638     return object;
0639 }
0640
0641 //==============================================================================
0642 //= Subtraction<IntervalSet|IntervalSet>
0643 //==============================================================================
0644 //------------------------------------------------------------------------------
0645 //- T& op -= (c P&) T:{M} P:{M'}
0646 //------------------------------------------------------------------------------
0647 /** \par \b Requires: Types \c Type and \c OperandT are subtractable.
0648     \par \b Effects: \c operand is subtracted from \c object.
0649     \par \b Returns: A reference to \c object.
0650     \b Complexity:
0651 \code
0652                   \ OperandT:                      interval
0653                    \         element    segment    container
0654 Type:
0655        interval container    O(log n)     O(n)     O(m log(n+m))
0656
0657                                        amortized
0658             interval_sets               O(log n)
0659
0660 n = object.interval_count()
0661 m = operand.interval_count()
0662 \endcode
0663
0664 For the subtraction of \em elements, \b segments and \b interval \b containers
0665 complexity is \b logarithmic, \b linear and \b loglinear respectively.
0666 For interval sets subtraction of segments
0667 is \b amortized \b logarithmic.
0668 */
0669 template<class Type, class OperandT>
0670 typename enable_if<is_concept_compatible<is_interval_map, Type, OperandT>,
0671                    Type>::type&
0672 operator -=(Type& object, const OperandT& operand)
0673 {
0674     ICL_const_FORALL(typename OperandT, elem_, operand)
0675         icl::subtract(object, *elem_);
0676
0677     return object;
0678 }
0679
0680 //------------------------------------------------------------------------------
0681 //- T& op -= (c P&) T:{S}|{M} P:{e i}|{b p}
0682 //------------------------------------------------------------------------------
0683 template<class Type, class OperandT>
0684 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
0685 operator -= (Type& object, const OperandT& operand)
0686 {
0687     return icl::subtract(object, operand);
0688 }
0689
0690 //------------------------------------------------------------------------------
0691 //- T& op -= (c P&) T:{M} P:{e i}
0692 //------------------------------------------------------------------------------
0693 template<class Type, class OperandT>
0694 typename enable_if<is_cross_derivative<Type, OperandT>, Type>::type&
0695 operator -= (Type& object, const OperandT& operand)
0696 {
0697     return icl::erase(object, operand);
0698 }
0699
0700 //------------------------------------------------------------------------------
0701 //- T& op -= (c P&) T:{S M} P:{S'}
0702 //------------------------------------------------------------------------------
0703 template<class Type, class IntervalSetT>
0704 typename enable_if<combines_right_to_interval_set<Type, IntervalSetT>,
0705                    Type>::type&
0706 operator -= (Type& object, const IntervalSetT& operand)
0707 {
0708     return erase(object, operand);
0709 }
0710
0711 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0712 //------------------------------------------------------------------------------
0713 //- T op - (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
0714 //------------------------------------------------------------------------------
0715 template<class Type, class OperandT>
0716 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
0717 operator - (Type object, const OperandT& operand)
0718 {
0719     return object -= operand;
0720 }
0721
0722 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0723
0724 template<class Type, class OperandT>
0725 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
0726 operator - (const Type& object, const OperandT& operand)
0727 {
0728     Type temp = object;
0729     return boost::move(temp -= operand);
0730 }
0731
0732 template<class Type, class OperandT>
0733 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
0734 operator - (Type&& object, const OperandT& operand)
0735 {
0736     return boost::move(object -= operand);
0737 }
0738
0739 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0740
0741 //==============================================================================
0742 //= Intersection<IntervalSet|IntervalSet>
0743 //==============================================================================
0744 //------------------------------------------------------------------------------
0745 //- void add_intersection(T&, c T&, c P&) T:{S M} P:{S'}
0746 //------------------------------------------------------------------------------
0747 template<class Type, class OperandT>
0748 typename enable_if<mpl::and_<is_interval_set<Type>,
0749                              combines_right_to_interval_set<Type, OperandT> >,
0750                    void>::type
0751 add_intersection(Type& section, const Type& object, const OperandT& operand)
0752 {
0753     typedef typename OperandT::const_iterator const_iterator;
0754
0755     if(operand.empty())
0756         return;
0757
0758     const_iterator common_lwb, common_upb;
0759     if(!Set::common_range(common_lwb, common_upb, operand, object))
0760         return;
0761
0762     const_iterator it_ = common_lwb;
0763     while(it_ != common_upb)
0764         icl::add_intersection(section, object, key_value<OperandT>(it_++));
0765 }
0766
0767 //------------------------------------------------------------------------------
0768 //- T& op &=(T&, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
0769 //------------------------------------------------------------------------------
0770 template<class Type, class OperandT>
0771 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type&
0772 operator &= (Type& object, const OperandT& operand)
0773 {
0774     Type intersection;
0775     add_intersection(intersection, object, operand);
0776     object.swap(intersection);
0777     return object;
0778 }
0779
0780 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0781 //------------------------------------------------------------------------------
0782 //- T op & (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
0783 //------------------------------------------------------------------------------
0784 template<class Type, class OperandT>
0785 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
0786 operator & (Type object, const OperandT& operand)
0787 {
0788     return object &= operand;
0789 }
0790
0791 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0792
0793 template<class Type, class OperandT>
0794 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
0795 operator & (const Type& object, const OperandT& operand)
0796 {
0797     Type temp = object;
0798     return boost::move(temp &= operand);
0799 }
0800
0801 template<class Type, class OperandT>
0802 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
0803 operator & (Type&& object, const OperandT& operand)
0804 {
0805     return boost::move(object &= operand);
0806 }
0807
0808 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0809
0810 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0811 //------------------------------------------------------------------------------
0812 //- T op & (c P&, T) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
0813 //------------------------------------------------------------------------------
0814 template<class Type, class OperandT>
0815 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
0816 operator & (const OperandT& operand, Type object)
0817 {
0818     return object &= operand;
0819 }
0820
0821 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0822
0823 template<class Type, class OperandT>
0824 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
0825 operator & (const OperandT& operand, const Type& object)
0826 {
0827     Type temp = object;
0828     return boost::move(temp &= operand);
0829 }
0830
0831 template<class Type, class OperandT>
0832 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
0833 operator & (const OperandT& operand, Type&& object)
0834 {
0835     return boost::move(object &= operand);
0836 }
0837
0838 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0839
0840 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0841 //------------------------------------------------------------------------------
0842 //- T op & (T, c T&) T:{S M}
0843 //------------------------------------------------------------------------------
0844 template<class Type>
0845 typename enable_if<is_interval_container<Type>, Type>::type
0846 operator & (Type object, const Type& operand)
0847 {
0848     return object &= operand;
0849 }
0850
0851 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0852
0853 template<class Type>
0854 typename enable_if<is_interval_container<Type>, Type>::type
0855 operator & (const Type& object, const Type& operand)
0856 {
0857     Type temp = object;
0858     return boost::move(temp &= operand);
0859 }
0860
0861 template<class Type>
0862 typename enable_if<is_interval_container<Type>, Type>::type
0863 operator & (Type&& object, const Type& operand)
0864 {
0865     return boost::move(object &= operand);
0866 }
0867
0868 template<class Type>
0869 typename enable_if<is_interval_container<Type>, Type>::type
0870 operator & (const Type& operand, Type&& object)
0871 {
0872     return boost::move(object &= operand);
0873 }
0874
0875 template<class Type>
0876 typename enable_if<is_interval_container<Type>, Type>::type
0877 operator & (Type&& object, Type&& operand)
0878 {
0879     return boost::move(object &= operand);
0880 }
0881
0882 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0883
0884 //------------------------------------------------------------------------------
0885 //- intersects<IntervalSet|IntervalMap>
0886 //------------------------------------------------------------------------------
0887 //------------------------------------------------------------------------------
0888 //- bool intersects(c T&, c P&) T:{S}|{M} P:{e i}
0889 //------------------------------------------------------------------------------
0890 template<class Type, class CoType>
0891 typename enable_if<mpl::and_< is_interval_container<Type>
0892                             , boost::is_same<CoType, typename domain_type_of<Type>::type> >,
0893                    bool>::type
0894 intersects(const Type& left, const CoType& right)
0895 {
0896     return icl::contains(left, right);
0897 }
0898
0899 template<class Type, class CoType>
0900 typename enable_if<mpl::and_< is_interval_container<Type>
0901                             , boost::is_same<CoType, typename interval_type_of<Type>::type> >,
0902                    bool>::type
0903 intersects(const Type& left, const CoType& right)
0904 {
0905     return !is_empty(right) && icl::find(left, right) != left.end();
0906 }
0907
0908
0909 template<class LeftT, class RightT>
0910 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
0911                              , mpl::or_<is_total<LeftT>, is_total<RightT> > >
0912                   , bool>::type
0913 intersects(const LeftT&, const RightT&)
0914 {
0915     return true;
0916 }
0917
0918 template<class LeftT, class RightT>
0919 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
0920                              , mpl::not_<mpl::or_< is_total<LeftT>
0921                                                  , is_total<RightT> > > >
0922                   , bool>::type
0923 intersects(const LeftT& left, const RightT& right)
0924 {
0925     typedef typename RightT::const_iterator const_iterator;
0926     LeftT intersection;
0927
0928     const_iterator right_common_lower_, right_common_upper_;
0929     if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
0930         return false;
0931
0932     const_iterator it_ = right_common_lower_;
0933     while(it_ != right_common_upper_)
0934     {
0935         icl::add_intersection(intersection, left, *it_++);
0936         if(!icl::is_empty(intersection))
0937             return true;
0938     }
0939     return false;
0940 }
0941
0942 template<class LeftT, class RightT>
0943 typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type
0944 intersects(const LeftT& left, const RightT& right)
0945 {
0946     typedef typename RightT::const_iterator const_iterator;
0947     LeftT intersection;
0948
0949     if(icl::is_empty(left) || icl::is_empty(right))
0950         return false;
0951
0952     const_iterator right_common_lower_, right_common_upper_;
0953     if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
0954         return false;
0955
0956     typename RightT::const_iterator it_ = right_common_lower_;
0957     while(it_ != right_common_upper_)
0958     {
0959         icl::add_intersection(intersection, left, key_value<RightT>(it_++));
0960         if(!icl::is_empty(intersection))
0961             return true;
0962     }
0963
0964     return false;
0965 }
0966
0967 /** \b Returns true, if \c left and \c right have no common elements.
0968     Intervals are interpreted as sequence of elements.
0969     \b Complexity: loglinear, if \c left and \c right are interval containers. */
0970 template<class LeftT, class RightT>
0971 typename enable_if<is_inter_combinable<LeftT, RightT>, bool>::type
0972 disjoint(const LeftT& left, const RightT& right)
0973 {
0974     return !intersects(left, right);
0975 }
0976
0977 /** \b Returns true, if \c left and \c right have no common elements.
0978     Intervals are interpreted as sequence of elements.
0979     \b Complexity: logarithmic, if \c AssociateT is an element type \c Type::element_type.
0980     linear, if \c AssociateT is a segment type \c Type::segment_type. */
0981 template<class Type, class AssociateT>
0982 typename enable_if<is_inter_derivative<Type, AssociateT>, bool>::type
0983 disjoint(const Type& left, const AssociateT& right)
0984 {
0985     return !intersects(left,right);
0986 }
0987
0988
0989 //==============================================================================
0990 //= Symmetric difference<IntervalSet|IntervalSet>
0991 //==============================================================================
0992 //------------------------------------------------------------------------------
0993 //- Symmetric difference ^=, ^
0994 //------------------------------------------------------------------------------
0995 //------------------------------------------------------------------------------
0996 //- T& op ^=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
0997 //------------------------------------------------------------------------------
0998 template<class Type, class OperandT>
0999 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
1000 operator ^= (Type& object, const OperandT& operand)
1001 {
1002     return icl::flip(object, operand);
1003 }
1004
1005 //------------------------------------------------------------------------------
1006 //- T& op ^=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
1007 //------------------------------------------------------------------------------
1008 template<class Type, class OperandT>
1009 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
1010 operator ^= (Type& object, const OperandT& operand)
1011 {
1012     return icl::flip(object, operand);
1013 }
1014
1015 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1016 //------------------------------------------------------------------------------
1017 //- T op ^ (T, c P&) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
1018 //------------------------------------------------------------------------------
1019 template<class Type, class OperandT>
1020 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1021 operator ^ (Type object, const OperandT& operand)
1022 {
1023     return object ^= operand;
1024 }
1025
1026 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1027
1028 template<class Type, class OperandT>
1029 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1030 operator ^ (const Type& object, const OperandT& operand)
1031 {
1032     Type temp = object;
1033     return boost::move(temp ^= operand);
1034 }
1035
1036 template<class Type, class OperandT>
1037 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1038 operator ^ (Type&& object, const OperandT& operand)
1039 {
1040     return boost::move(object ^= operand);
1041 }
1042
1043 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1044
1045 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1046 //------------------------------------------------------------------------------
1047 //- T op ^ (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
1048 //------------------------------------------------------------------------------
1049 template<class Type, class OperandT>
1050 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1051 operator ^ (const OperandT& operand, Type object)
1052 {
1053     return object ^= operand;
1054 }
1055
1056 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1057
1058 template<class Type, class OperandT>
1059 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1060 operator ^ (const OperandT& operand, const Type& object)
1061 {
1062     Type temp = object;
1063     return boost::move(temp ^= operand);
1064 }
1065
1066 template<class Type, class OperandT>
1067 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
1068 operator ^ (const OperandT& operand, Type&& object)
1069 {
1070     return boost::move(object ^= operand);
1071 }
1072
1073 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1074
1075 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1076 //------------------------------------------------------------------------------
1077 //- T op ^ (T, c T&) T:{S M}
1078 //------------------------------------------------------------------------------
1079 template<class Type>
1080 typename enable_if<is_interval_container<Type>, Type>::type
1081 operator ^ (typename Type::overloadable_type object, const Type& operand)
1082 {
1083     return object ^= operand;
1084 }
1085
1086 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1087
1088 template<class Type>
1089 typename enable_if<is_interval_container<Type>, Type>::type
1090 operator ^ (const Type& object, const Type& operand)
1091 {
1092     Type temp = object;
1093     return boost::move(temp ^= operand);
1094 }
1095
1096 template<class Type>
1097 typename enable_if<is_interval_container<Type>, Type>::type
1098 operator ^ (Type&& object, const Type& operand)
1099 {
1100     return boost::move(object ^= operand);
1101 }
1102
1103 template<class Type>
1104 typename enable_if<is_interval_container<Type>, Type>::type
1105 operator ^ (const Type& operand, Type&& object)
1106 {
1107     return boost::move(object ^= operand);
1108 }
1109
1110 template<class Type>
1111 typename enable_if<is_interval_container<Type>, Type>::type
1112 operator ^ (Type&& object, Type&& operand)
1113 {
1114     return boost::move(object ^= operand);
1115 }
1116
1117 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1118
1119 //==========================================================================
1120 //= Element Iteration <IntervalSet|IntervalMap>
1121 //==========================================================================
1122 //--------------------------------------------------------------------------
1123 //- Forward
1124 //--------------------------------------------------------------------------
1125 template<class Type>
1126 typename enable_if
1127 <mpl::and_< is_interval_container<Type>
1128           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1129 typename Type::element_iterator>::type
1130 elements_begin(Type& object)
1131 {
1132     return typename Type::element_iterator(object.begin());
1133 }
1134
1135 template<class Type>
1136 typename enable_if
1137 <mpl::and_< is_interval_container<Type>
1138           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1139 typename Type::element_iterator>::type
1140 elements_end(Type& object)
1141 {
1142     return typename Type::element_iterator(object.end());
1143 }
1144
1145 template<class Type>
1146 typename enable_if
1147 <mpl::and_< is_interval_container<Type>
1148           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1149 typename Type::element_const_iterator>::type
1150 elements_begin(const Type& object)
1151 {
1152     return typename Type::element_const_iterator(object.begin());
1153 }
1154
1155 template<class Type>
1156 typename enable_if
1157 <mpl::and_< is_interval_container<Type>
1158           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1159 typename Type::element_const_iterator>::type
1160 elements_end(const Type& object)
1161 {
1162     return typename Type::element_const_iterator(object.end());
1163 }
1164
1165 template<class Type>
1166 typename enable_if
1167 <mpl::and_< is_interval_container<Type>
1168           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1169 iterator_range<typename Type::element_iterator> >::type
1170 elements(Type& object)
1171 {
1172     return
1173     make_iterator_range( typename Type::element_iterator(object.begin())
1174                        , typename Type::element_iterator(object.end())  );
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 iterator_range<typename Type::element_const_iterator> >::type
1182 elements(Type const& object)
1183 {
1184     return
1185     make_iterator_range( typename Type::element_const_iterator(object.begin())
1186                        , typename Type::element_const_iterator(object.end())  );
1187 }
1188
1189 //--------------------------------------------------------------------------
1190 //- Reverse
1191 //--------------------------------------------------------------------------
1192 template<class Type>
1193 typename enable_if
1194 <mpl::and_< is_interval_container<Type>
1195           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1196 typename Type::element_reverse_iterator>::type
1197 elements_rbegin(Type& object)
1198 {
1199     return typename Type::element_reverse_iterator(object.rbegin());
1200 }
1201
1202 template<class Type>
1203 typename enable_if
1204 <mpl::and_< is_interval_container<Type>
1205           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1206 typename Type::element_reverse_iterator>::type
1207 elements_rend(Type& object)
1208 {
1209     return typename Type::element_reverse_iterator(object.rend());
1210 }
1211
1212 template<class Type>
1213 typename enable_if
1214 <mpl::and_< is_interval_container<Type>
1215           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1216 typename Type::element_const_reverse_iterator>::type
1217 elements_rbegin(const Type& object)
1218 {
1219     return typename Type::element_const_reverse_iterator(object.rbegin());
1220 }
1221
1222 template<class Type>
1223 typename enable_if
1224 <mpl::and_< is_interval_container<Type>
1225           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1226 typename Type::element_const_reverse_iterator>::type
1227 elements_rend(const Type& object)
1228 {
1229     return typename Type::element_const_reverse_iterator(object.rend());
1230 }
1231
1232 }} // namespace boost icl
1233
1234 #endif
1235
1236