diff options
Diffstat (limited to 'boost/icl/concept/interval_associator.hpp')
| -rw-r--r-- | boost/icl/concept/interval_associator.hpp | 1211 |
1 files changed, 1211 insertions, 0 deletions
diff --git a/boost/icl/concept/interval_associator.hpp b/boost/icl/concept/interval_associator.hpp new file mode 100644 index 0000000000..75d8622af3 --- /dev/null +++ b/boost/icl/concept/interval_associator.hpp @@ -0,0 +1,1211 @@ +/*-----------------------------------------------------------------------------+ +Copyright (c) 2010-2010: Joachim Faulhaber ++------------------------------------------------------------------------------+ + Distributed under the Boost Software License, Version 1.0. + (See accompanying file LICENCE.txt or copy at + http://www.boost.org/LICENSE_1_0.txt) ++-----------------------------------------------------------------------------*/ +#ifndef BOOST_ICL_CONCEPT_INTERVAL_ASSOCIATOR_HPP_JOFA_100920 +#define BOOST_ICL_CONCEPT_INTERVAL_ASSOCIATOR_HPP_JOFA_100920 + +#include <boost/icl/type_traits/domain_type_of.hpp> +#include <boost/icl/type_traits/interval_type_of.hpp> +#include <boost/icl/type_traits/is_combinable.hpp> +#include <boost/icl/detail/set_algo.hpp> +#include <boost/icl/detail/map_algo.hpp> +#include <boost/icl/detail/interval_set_algo.hpp> +#include <boost/icl/detail/interval_map_algo.hpp> +#include <boost/icl/concept/interval.hpp> + +namespace boost{ namespace icl +{ + +//============================================================================== +//= Containedness<IntervalSet|IntervalMap> +//============================================================================== +//------------------------------------------------------------------------------ +//- bool within(c T&, c P&) T={Set,Map} P={e i b p S M} +//------------------------------------------------------------------------------ +template<class SubT, class SuperT> +typename enable_if<is_interval_container<SuperT>, bool>::type +within(const SubT& sub, const SuperT& super) +{ + return icl::contains(super, sub); +} + +//============================================================================== +//= Equivalences and Orderings<IntervalSet|IntervalMap> +//============================================================================== +template<class Type> +inline typename enable_if<is_interval_container<Type>, bool>::type +operator == (const Type& left, const Type& right) +{ + return Set::lexicographical_equal(left, right); +} + +template<class Type> +inline typename enable_if<is_interval_container<Type>, bool>::type +operator < (const Type& left, const Type& right) +{ + typedef typename Type::segment_compare segment_compare; + return std::lexicographical_compare( + left.begin(), left.end(), right.begin(), right.end(), + segment_compare() + ); +} + +/** Returns true, if \c left and \c right contain the same elements. + Complexity: linear. */ +template<class LeftT, class RightT> +typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type +is_element_equal(const LeftT& left, const RightT& right) +{ + return Interval_Set::is_element_equal(left, right); +} + +/** Returns true, if \c left is lexicographically less than \c right. + Intervals are interpreted as sequence of elements. + Complexity: linear. */ +template<class LeftT, class RightT> +typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type +is_element_less(const LeftT& left, const RightT& right) +{ + return Interval_Set::is_element_less(left, right); +} + +/** Returns true, if \c left is lexicographically greater than \c right. + Intervals are interpreted as sequence of elements. + Complexity: linear. */ +template<class LeftT, class RightT> +typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type +is_element_greater(const LeftT& left, const RightT& right) +{ + return Interval_Set::is_element_greater(left, right); +} + +//------------------------------------------------------------------------------ +template<class LeftT, class RightT> +typename enable_if<is_inter_combinable<LeftT, RightT>, int>::type +inclusion_compare(const LeftT& left, const RightT& right) +{ + return Interval_Set::subset_compare(left, right, + left.begin(), left.end(), + right.begin(), right.end()); +} + +//------------------------------------------------------------------------------ +template<class LeftT, class RightT> +typename enable_if< is_concept_compatible<is_interval_map, LeftT, RightT>, + bool >::type +is_distinct_equal(const LeftT& left, const RightT& right) +{ + return Map::lexicographical_distinct_equal(left, right); +} + +//============================================================================== +//= Size<IntervalSet|IntervalMap> +//============================================================================== +template<class Type> +typename enable_if<is_interval_container<Type>, std::size_t>::type +iterative_size(const Type& object) +{ + return object.iterative_size(); +} + +template<class Type> +typename enable_if +< mpl::and_< is_interval_container<Type> + , is_discrete<typename Type::domain_type> > +, typename Type::size_type +>::type +cardinality(const Type& object) +{ + typedef typename Type::size_type size_type; + typedef typename Type::interval_type interval_type; + + size_type size = identity_element<size_type>::value(); + ICL_const_FORALL(typename Type, it, object) + size += icl::cardinality(key_value<Type>(it)); + return size; + +} + +template<class Type> +typename enable_if +< mpl::and_< is_interval_container<Type> + , mpl::not_<is_discrete<typename Type::domain_type> > > +, typename Type::size_type +>::type +cardinality(const Type& object) +{ + typedef typename Type::size_type size_type; + typedef typename Type::interval_type interval_type; + + size_type size = identity_element<size_type>::value(); + size_type interval_size; + ICL_const_FORALL(typename Type, it, object) + { + interval_size = icl::cardinality(key_value<Type>(it)); + if(interval_size == icl::infinity<size_type>::value()) + return interval_size; + else + size += interval_size; + } + return size; +} + +template<class Type> +inline typename enable_if<is_interval_container<Type>, typename Type::size_type>::type +size(const Type& object) +{ + return icl::cardinality(object); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, typename Type::difference_type>::type +length(const Type& object) +{ + typedef typename Type::difference_type difference_type; + typedef typename Type::const_iterator const_iterator; + difference_type length = identity_element<difference_type>::value(); + const_iterator it_ = object.begin(); + + while(it_ != object.end()) + length += icl::length(key_value<Type>(it_++)); + return length; +} + +template<class Type> +typename enable_if<is_interval_container<Type>, std::size_t>::type +interval_count(const Type& object) +{ + return icl::iterative_size(object); +} + + +template<class Type> +typename enable_if< is_interval_container<Type> + , typename Type::difference_type >::type +distance(const Type& object) +{ + typedef typename Type::difference_type DiffT; + typedef typename Type::const_iterator const_iterator; + const_iterator it_ = object.begin(), pred_; + DiffT dist = identity_element<DiffT>::value(); + + if(it_ != object.end()) + pred_ = it_++; + + while(it_ != object.end()) + dist += icl::distance(key_value<Type>(pred_++), key_value<Type>(it_++)); + + return dist; +} + +//============================================================================== +//= Range<IntervalSet|IntervalMap> +//============================================================================== +template<class Type> +typename enable_if<is_interval_container<Type>, + typename Type::interval_type>::type +hull(const Type& object) +{ + return + icl::is_empty(object) + ? identity_element<typename Type::interval_type>::value() + : icl::hull( key_value<Type>(object.begin()), + key_value<Type>(object.rbegin()) ); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, + typename domain_type_of<Type>::type>::type +lower(const Type& object) +{ + typedef typename domain_type_of<Type>::type DomainT; + return + icl::is_empty(object) + ? unit_element<DomainT>::value() + : icl::lower( key_value<Type>(object.begin()) ); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, + typename domain_type_of<Type>::type>::type +upper(const Type& object) +{ + typedef typename domain_type_of<Type>::type DomainT; + return + icl::is_empty(object) + ? identity_element<DomainT>::value() + : icl::upper( key_value<Type>(object.rbegin()) ); +} + +//------------------------------------------------------------------------------ +template<class Type> +typename enable_if +< mpl::and_< is_interval_container<Type> + , is_discrete<typename domain_type_of<Type>::type> > +, typename domain_type_of<Type>::type>::type +first(const Type& object) +{ + typedef typename domain_type_of<Type>::type DomainT; + return + icl::is_empty(object) + ? unit_element<DomainT>::value() + : icl::first( key_value<Type>(object.begin()) ); +} + +template<class Type> +typename enable_if +< mpl::and_< is_interval_container<Type> + , is_discrete<typename domain_type_of<Type>::type> > +, typename domain_type_of<Type>::type>::type +last(const Type& object) +{ + typedef typename domain_type_of<Type>::type DomainT; + return + icl::is_empty(object) + ? identity_element<DomainT>::value() + : icl::last( key_value<Type>(object.rbegin()) ); +} + + +//============================================================================== +//= Addition<IntervalSet|IntervalMap> +//============================================================================== +//------------------------------------------------------------------------------ +//- T& op +=(T&, c P&) T:{S}|{M} P:{e i}|{b p} +//------------------------------------------------------------------------------ +/* \par \b Requires: \c OperandT is an addable derivative type of \c Type. + \b Effects: \c operand is added to \c object. + \par \b Returns: A reference to \c object. + \b Complexity: +\code + \ OperandT: + \ element segment +Type: + interval container O(log n) O(n) + + interval_set amortized + spearate_interval_set O(log n) + +n = object.interval_count() +\endcode + +For the addition of \b elements or \b segments +complexity is \b logarithmic or \b linear respectively. +For \c interval_sets and \c separate_interval_sets addition of segments +is \b amortized \b logarithmic. +*/ +template<class Type, class OperandT> +typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type& +operator += (Type& object, const OperandT& operand) +{ + return icl::add(object, operand); +} + + +//------------------------------------------------------------------------------ +//- T& op +=(T&, c P&) T:{S}|{M} P:{S'}|{M'} +//------------------------------------------------------------------------------ +/** \par \b Requires: \c OperandT is an interval container addable to \c Type. + \b Effects: \c operand is added to \c object. + \par \b Returns: A reference to \c object. + \b Complexity: loglinear */ +template<class Type, class OperandT> +typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type& +operator += (Type& object, const OperandT& operand) +{ + typename Type::iterator prior_ = object.end(); + ICL_const_FORALL(typename OperandT, elem_, operand) + prior_ = icl::add(object, prior_, *elem_); + + return object; +} + + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op + (T, c P&) T:{S}|{M} P:{e i S}|{b p M} +//------------------------------------------------------------------------------ +/** \par \b Requires: \c object and \c operand are addable. + \b Effects: \c operand is added to \c object. + \par \b Efficieny: There is one additional copy of + \c Type \c object compared to inplace \c operator \c += */ +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator + (Type object, const OperandT& operand) +{ + return object += operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator + (const Type& object, const OperandT& operand) +{ + Type temp = object; + return boost::move(temp += operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator + (Type&& object, const OperandT& operand) +{ + return boost::move(object += operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op + (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'} +//------------------------------------------------------------------------------ +/** \par \b Requires: \c object and \c operand are addable. + \b Effects: \c operand is added to \c object. + \par \b Efficieny: There is one additional copy of + \c Type \c object compared to inplace \c operator \c += */ +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator + (const OperandT& operand, Type object) +{ + return object += operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator + (const OperandT& operand, const Type& object) +{ + Type temp = object; + return boost::move(temp += operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator + (const OperandT& operand, Type&& object) +{ + return boost::move(object += operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op + (T, c P&) T:{S}|{M} P:{S}|{M} +//------------------------------------------------------------------------------ +/** \par \b Requires: \c object and \c operand are addable. + \b Effects: \c operand is added to \c object. + \par \b Efficieny: There is one additional copy of + \c Type \c object compared to inplace \c operator \c += */ +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator + (Type object, const Type& operand) +{ + return object += operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator + (const Type& object, const Type& operand) +{ + Type temp = object; + return boost::move(temp += operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator + (Type&& object, const Type& operand) +{ + return boost::move(object += operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator + (const Type& operand, Type&& object) +{ + return boost::move(object += operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator + (Type&& object, Type&& operand) +{ + return boost::move(object += operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +//------------------------------------------------------------------------------ +//- Addition |=, | +//------------------------------------------------------------------------------ + +//------------------------------------------------------------------------------ +//- T& op |=(c P&) T:{S}|{M} P:{e i}|{b p} +//------------------------------------------------------------------------------ +/** \par \b Requires: Types \c Type and \c OperandT are addable. + \par \b Effects: \c operand is added to \c object. + \par \b Returns: A reference to \c object. + \b Complexity: +\code + \ OperandT: interval + \ element segment container +Type: + interval container O(log n) O(n) O(m log(n+m)) + + interval_set amortized + spearate_interval_set O(log n) + +n = object.interval_count() +m = operand.interval_count() +\endcode + +For the addition of \b elements, \b segments and \b interval \b containers +complexity is \b logarithmic, \b linear and \b loglinear respectively. +For \c interval_sets and \c separate_interval_sets addition of segments +is \b amortized \b logarithmic. +*/ +template<class Type, class OperandT> +typename enable_if<is_right_intra_combinable<Type, OperandT>, Type>::type& +operator |= (Type& object, const OperandT& operand) +{ + return object += operand; +} + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op | (T, c P&) T:{S}|{M} P:{e i S}|{b p M} +//------------------------------------------------------------------------------ +/** \par \b Requires: \c object and \c operand are addable. + \b Effects: \c operand is added to \c object. + \par \b Efficieny: There is one additional copy of + \c Type \c object compared to inplace \c operator \c |= */ +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator | (Type object, const OperandT& operand) +{ + return object += operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator | (const Type& object, const OperandT& operand) +{ + Type temp = object; + return boost::move(temp += operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator | (Type&& object, const OperandT& operand) +{ + return boost::move(object += operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op | (T, c P&) T:{S}|{M} P:{S}|{M} +//------------------------------------------------------------------------------ +/** \par \b Requires: \c object and \c operand are addable. + \b Effects: \c operand is added to \c object. + \par \b Efficieny: There is one additional copy of + \c Type \c object compared to inplace \c operator \c |= */ +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator | (const OperandT& operand, Type object) +{ + return object += operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator | (const OperandT& operand, const Type& object) +{ + Type temp = object; + return boost::move(temp += operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator | (const OperandT& operand, Type&& object) +{ + return boost::move(object += operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op | (T, c P&) T:{S}|{M} P:{S}|{M} +//------------------------------------------------------------------------------ +/** \par \b Requires: \c object and \c operand are addable. + \b Effects: \c operand is added to \c object. + \par \b Efficieny: There is one additional copy of + \c Type \c object compared to inplace \c operator \c |= */ +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator | (Type object, const Type& operand) +{ + return object += operand; +} +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator | (const Type& object, const Type& operand) +{ + Type temp = object; + return boost::move(temp += operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator | (Type&& object, const Type& operand) +{ + return boost::move(object += operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator | (const Type& operand, Type&& object) +{ + return boost::move(object += operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator | (Type&& object, Type&& operand) +{ + return boost::move(object += operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + + +//============================================================================== +//= Insertion<IntervalSet|IntervalSet> +//============================================================================== +//------------------------------------------------------------------------------ +//- T& insert(T&, c P&) T:{S}|{M} P:{S'}|{M'} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type& +insert(Type& object, const OperandT& operand) +{ + typename Type::iterator prior_ = object.end(); + ICL_const_FORALL(typename OperandT, elem_, operand) + insert(object, *elem_); + + return object; +} + +//============================================================================== +//= Erasure<IntervalSet|IntervalSet> +//============================================================================== +//------------------------------------------------------------------------------ +//- T& erase(T&, c P&) T:{S}|{M} P:{S'}|{S' M'} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<combines_right_to_interval_container<Type, OperandT>, + Type>::type& +erase(Type& object, const OperandT& operand) +{ + typedef typename OperandT::const_iterator const_iterator; + + if(icl::is_empty(operand)) + return object; + + const_iterator common_lwb, common_upb; + if(!Set::common_range(common_lwb, common_upb, operand, object)) + return object; + + const_iterator it_ = common_lwb; + while(it_ != common_upb) + icl::erase(object, *it_++); + + return object; +} + +//============================================================================== +//= Subtraction<IntervalSet|IntervalSet> +//============================================================================== +//------------------------------------------------------------------------------ +//- T& op -= (c P&) T:{M} P:{M'} +//------------------------------------------------------------------------------ +/** \par \b Requires: Types \c Type and \c OperandT are subtractable. + \par \b Effects: \c operand is subtracted from \c object. + \par \b Returns: A reference to \c object. + \b Complexity: +\code + \ OperandT: interval + \ element segment container +Type: + interval container O(log n) O(n) O(m log(n+m)) + + amortized + interval_sets O(log n) + +n = object.interval_count() +m = operand.interval_count() +\endcode + +For the subtraction of \em elements, \b segments and \b interval \b containers +complexity is \b logarithmic, \b linear and \b loglinear respectively. +For interval sets subtraction of segments +is \b amortized \b logarithmic. +*/ +template<class Type, class OperandT> +typename enable_if<is_concept_compatible<is_interval_map, Type, OperandT>, + Type>::type& +operator -=(Type& object, const OperandT& operand) +{ + ICL_const_FORALL(typename OperandT, elem_, operand) + icl::subtract(object, *elem_); + + return object; +} + +//------------------------------------------------------------------------------ +//- T& op -= (c P&) T:{S}|{M} P:{e i}|{b p} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type& +operator -= (Type& object, const OperandT& operand) +{ + return icl::subtract(object, operand); +} + +//------------------------------------------------------------------------------ +//- T& op -= (c P&) T:{M} P:{e i} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_cross_derivative<Type, OperandT>, Type>::type& +operator -= (Type& object, const OperandT& operand) +{ + return icl::erase(object, operand); +} + +//------------------------------------------------------------------------------ +//- T& op -= (c P&) T:{S M} P:{S'} +//------------------------------------------------------------------------------ +template<class Type, class IntervalSetT> +typename enable_if<combines_right_to_interval_set<Type, IntervalSetT>, + Type>::type& +operator -= (Type& object, const IntervalSetT& operand) +{ + return erase(object, operand); +} + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op - (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type +operator - (Type object, const OperandT& operand) +{ + return object -= operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type +operator - (const Type& object, const OperandT& operand) +{ + Type temp = object; + return boost::move(temp -= operand); +} + +template<class Type, class OperandT> +typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type +operator - (Type&& object, const OperandT& operand) +{ + return boost::move(object -= operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +//============================================================================== +//= Intersection<IntervalSet|IntervalSet> +//============================================================================== +//------------------------------------------------------------------------------ +//- void add_intersection(T&, c T&, c P&) T:{S M} P:{S'} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<mpl::and_<is_interval_set<Type>, + combines_right_to_interval_set<Type, OperandT> >, + void>::type +add_intersection(Type& section, const Type& object, const OperandT& operand) +{ + typedef typename OperandT::const_iterator const_iterator; + + if(operand.empty()) + return; + + const_iterator common_lwb, common_upb; + if(!Set::common_range(common_lwb, common_upb, operand, object)) + return; + + const_iterator it_ = common_lwb; + while(it_ != common_upb) + icl::add_intersection(section, object, key_value<OperandT>(it_++)); +} + +//------------------------------------------------------------------------------ +//- T& op &=(T&, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type& +operator &= (Type& object, const OperandT& operand) +{ + Type intersection; + add_intersection(intersection, object, operand); + object.swap(intersection); + return object; +} + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op & (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type +operator & (Type object, const OperandT& operand) +{ + return object &= operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type +operator & (const Type& object, const OperandT& operand) +{ + Type temp = object; + return boost::move(temp &= operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type +operator & (Type&& object, const OperandT& operand) +{ + return boost::move(object &= operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op & (c P&, T) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type +operator & (const OperandT& operand, Type object) +{ + return object &= operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type +operator & (const OperandT& operand, const Type& object) +{ + Type temp = object; + return boost::move(temp &= operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type +operator & (const OperandT& operand, Type&& object) +{ + return boost::move(object &= operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op & (T, c T&) T:{S M} +//------------------------------------------------------------------------------ +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator & (Type object, const Type& operand) +{ + return object &= operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator & (const Type& object, const Type& operand) +{ + Type temp = object; + return boost::move(temp &= operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator & (Type&& object, const Type& operand) +{ + return boost::move(object &= operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator & (const Type& operand, Type&& object) +{ + return boost::move(object &= operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator & (Type&& object, Type&& operand) +{ + return boost::move(object &= operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +//------------------------------------------------------------------------------ +//- intersects<IntervalSet|IntervalMap> +//------------------------------------------------------------------------------ +//------------------------------------------------------------------------------ +//- bool intersects(c T&, c P&) T:{S}|{M} P:{e i} +//------------------------------------------------------------------------------ +template<class Type, class CoType> +typename enable_if<mpl::and_< is_interval_container<Type> + , boost::is_same<CoType, typename domain_type_of<Type>::type> >, + bool>::type +intersects(const Type& left, const CoType& right) +{ + return icl::contains(left, right); +} + +template<class Type, class CoType> +typename enable_if<mpl::and_< is_interval_container<Type> + , boost::is_same<CoType, typename interval_type_of<Type>::type> >, + bool>::type +intersects(const Type& left, const CoType& right) +{ + return icl::find(left, right) != left.end(); +} + + +template<class LeftT, class RightT> +typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT> + , mpl::or_<is_total<LeftT>, is_total<RightT> > > + , bool>::type +intersects(const LeftT&, const RightT&) +{ + return true; +} + +template<class LeftT, class RightT> +typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT> + , mpl::not_<mpl::or_< is_total<LeftT> + , is_total<RightT> > > > + , bool>::type +intersects(const LeftT& left, const RightT& right) +{ + typedef typename RightT::const_iterator const_iterator; + LeftT intersection; + + const_iterator right_common_lower_, right_common_upper_; + if(!Set::common_range(right_common_lower_, right_common_upper_, right, left)) + return false; + + const_iterator it_ = right_common_lower_; + while(it_ != right_common_upper_) + { + icl::add_intersection(intersection, left, *it_++); + if(!icl::is_empty(intersection)) + return true; + } + return false; +} + +template<class LeftT, class RightT> +typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type +intersects(const LeftT& left, const RightT& right) +{ + typedef typename RightT::const_iterator const_iterator; + LeftT intersection; + + if(icl::is_empty(left) || icl::is_empty(right)) + return false; + + const_iterator right_common_lower_, right_common_upper_; + if(!Set::common_range(right_common_lower_, right_common_upper_, right, left)) + return false; + + typename RightT::const_iterator it_ = right_common_lower_; + while(it_ != right_common_upper_) + { + icl::add_intersection(intersection, left, key_value<RightT>(it_++)); + if(!icl::is_empty(intersection)) + return true; + } + + return false; +} + +/** \b Returns true, if \c left and \c right have no common elements. + Intervals are interpreted as sequence of elements. + \b Complexity: loglinear, if \c left and \c right are interval containers. */ +template<class LeftT, class RightT> +typename enable_if<is_inter_combinable<LeftT, RightT>, bool>::type +disjoint(const LeftT& left, const RightT& right) +{ + return !intersects(left, right); +} + +/** \b Returns true, if \c left and \c right have no common elements. + Intervals are interpreted as sequence of elements. + \b Complexity: logarithmic, if \c AssociateT is an element type \c Type::element_type. + linear, if \c AssociateT is a segment type \c Type::segment_type. */ +template<class Type, class AssociateT> +typename enable_if<is_inter_derivative<Type, AssociateT>, bool>::type +disjoint(const Type& left, const AssociateT& right) +{ + return !intersects(left,right); +} + + +//============================================================================== +//= Symmetric difference<IntervalSet|IntervalSet> +//============================================================================== +//------------------------------------------------------------------------------ +//- Symmetric difference ^=, ^ +//------------------------------------------------------------------------------ +//------------------------------------------------------------------------------ +//- T& op ^=(T&, c P&) T:{S}|{M} P:{S'}|{M'} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type& +operator ^= (Type& object, const OperandT& operand) +{ + return icl::flip(object, operand); +} + +//------------------------------------------------------------------------------ +//- T& op ^=(T&, c P&) T:{S}|{M} P:{e i}|{b p} +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type& +operator ^= (Type& object, const OperandT& operand) +{ + return icl::flip(object, operand); +} + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op ^ (T, c P&) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator ^ (Type object, const OperandT& operand) +{ + return object ^= operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator ^ (const Type& object, const OperandT& operand) +{ + Type temp = object; + return boost::move(temp ^= operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator ^ (Type&& object, const OperandT& operand) +{ + return boost::move(object ^= operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op ^ (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser +//------------------------------------------------------------------------------ +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator ^ (const OperandT& operand, Type object) +{ + return object ^= operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator ^ (const OperandT& operand, const Type& object) +{ + Type temp = object; + return boost::move(temp ^= operand); +} + +template<class Type, class OperandT> +typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type +operator ^ (const OperandT& operand, Type&& object) +{ + return boost::move(object ^= operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +#ifdef BOOST_NO_RVALUE_REFERENCES +//------------------------------------------------------------------------------ +//- T op ^ (T, c T&) T:{S M} +//------------------------------------------------------------------------------ +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator ^ (typename Type::overloadable_type object, const Type& operand) +{ + return object ^= operand; +} + +#else //BOOST_NO_RVALUE_REFERENCES + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator ^ (const Type& object, const Type& operand) +{ + Type temp = object; + return boost::move(temp ^= operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator ^ (Type&& object, const Type& operand) +{ + return boost::move(object ^= operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator ^ (const Type& operand, Type&& object) +{ + return boost::move(object ^= operand); +} + +template<class Type> +typename enable_if<is_interval_container<Type>, Type>::type +operator ^ (Type&& object, Type&& operand) +{ + return boost::move(object ^= operand); +} + +#endif //BOOST_NO_RVALUE_REFERENCES + +//========================================================================== +//= Element Iteration <IntervalSet|IntervalMap> +//========================================================================== +//-------------------------------------------------------------------------- +//- Forward +//-------------------------------------------------------------------------- +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_iterator>::type +elements_begin(Type& object) +{ + return typename Type::element_iterator(object.begin()); +} + +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_iterator>::type +elements_end(Type& object) +{ + return typename Type::element_iterator(object.end()); +} + +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_const_iterator>::type +elements_begin(const Type& object) +{ + return typename Type::element_const_iterator(object.begin()); +} + +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_const_iterator>::type +elements_end(const Type& object) +{ + return typename Type::element_const_iterator(object.end()); +} + +//-------------------------------------------------------------------------- +//- Reverse +//-------------------------------------------------------------------------- +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_reverse_iterator>::type +elements_rbegin(Type& object) +{ + return typename Type::element_reverse_iterator(object.rbegin()); +} + +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_reverse_iterator>::type +elements_rend(Type& object) +{ + return typename Type::element_reverse_iterator(object.rend()); +} + +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_const_reverse_iterator>::type +elements_rbegin(const Type& object) +{ + return typename Type::element_const_reverse_iterator(object.rbegin()); +} + +template<class Type> +typename enable_if +<mpl::and_< is_interval_container<Type> + , mpl::not_<is_continuous_interval<typename Type::interval_type> > >, +typename Type::element_const_reverse_iterator>::type +elements_rend(const Type& object) +{ + return typename Type::element_const_reverse_iterator(object.rend()); +} + +}} // namespace boost icl + +#endif + + |