Chris@16: /*-----------------------------------------------------------------------------+    
Chris@16: Copyright (c) 2010-2010: Joachim Faulhaber
Chris@16: +------------------------------------------------------------------------------+
Chris@16:    Distributed under the Boost Software License, Version 1.0.
Chris@16:       (See accompanying file LICENCE.txt or copy at
Chris@16:            http://www.boost.org/LICENSE_1_0.txt)
Chris@16: +-----------------------------------------------------------------------------*/
Chris@16: #ifndef BOOST_ICL_CONCEPT_INTERVAL_MAP_HPP_JOFA_100920
Chris@16: #define BOOST_ICL_CONCEPT_INTERVAL_MAP_HPP_JOFA_100920
Chris@16: 
Chris@16: #include <boost/icl/type_traits/element_type_of.hpp>
Chris@16: #include <boost/icl/type_traits/segment_type_of.hpp>
Chris@16: #include <boost/icl/type_traits/absorbs_identities.hpp>
Chris@16: #include <boost/icl/type_traits/is_combinable.hpp>
Chris@16: #include <boost/icl/type_traits/is_interval_splitter.hpp>
Chris@16: 
Chris@16: #include <boost/icl/detail/set_algo.hpp>
Chris@16: #include <boost/icl/detail/interval_map_algo.hpp>
Chris@16: #include <boost/icl/concept/interval.hpp>
Chris@16: #include <boost/icl/concept/joinable.hpp>
Chris@16: 
Chris@16: namespace boost{ namespace icl
Chris@16: {
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_map<Type>, typename Type::segment_type>::type
Chris@16: make_segment(const typename Type::element_type& element)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::segment_type  segment_type;
Chris@16:     return segment_type(icl::singleton<interval_type>(element.key), element.data);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Containedness<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool contains(c T&, c P&) T:{M} P:{b p M} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, bool>::type
Chris@16: contains(const Type& super, const typename Type::element_type& key_value_pair)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     const_iterator it_ = icl::find(super, key_value_pair.key);
Chris@16:     return it_ != super.end() && (*it_).second == key_value_pair.data;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, bool>::type
Chris@16: contains(const Type& super, const typename Type::segment_type& sub_segment)
Chris@16: {
Chris@16:     typedef typename Type::interval_type  interval_type;
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16: 
Chris@16:     interval_type sub_interval = sub_segment.first;
Chris@16:     if(icl::is_empty(sub_interval)) 
Chris@16:         return true;
Chris@16: 
Chris@16:     std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return false;
Chris@16: 
Chris@16:     const_iterator last_overlap = prior(exterior.second);
Chris@16: 
Chris@16:     if(!(sub_segment.second == exterior.first->second) )
Chris@16:         return false;
Chris@16: 
Chris@16:     return
Chris@16:           icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
Chris@16:       &&  Interval_Map::is_joinable(super, exterior.first, last_overlap);
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class CoType>
Chris@16: typename enable_if<is_concept_compatible<is_interval_map, Type, CoType>, bool>::type
Chris@16: contains(const Type& super, const CoType& sub)
Chris@16: {
Chris@16:     return Interval_Set::within(sub, super);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : total
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type, class CoType>
Chris@16: typename enable_if< mpl::and_< is_interval_map<Type>
Chris@16:                              , is_total<Type> 
Chris@16:                              , is_cross_derivative<Type, CoType> >
Chris@16:             , bool>::type
Chris@16: contains(const Type&, const CoType&)
Chris@16: {
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : partial
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if< mpl::and_< is_interval_map<Type>
Chris@16:                              , mpl::not_<is_total<Type> > >
Chris@16:             , bool>::type
Chris@16: contains(const Type& super, const typename Type::domain_type& key)    
Chris@16: {
Chris@16:     return icl::find(super, key) != super.end();
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if< mpl::and_< is_interval_map<Type>
Chris@16:                              , mpl::not_<is_total<Type> > >
Chris@16:             , bool>::type
Chris@16: contains(const Type& super, const typename Type::interval_type& sub_interval)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16: 
Chris@16:     if(icl::is_empty(sub_interval)) 
Chris@16:         return true;
Chris@16: 
Chris@16:     std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return false;
Chris@16: 
Chris@16:     const_iterator last_overlap = prior(exterior.second);
Chris@16: 
Chris@16:     return
Chris@16:           icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
Chris@16:       &&  Interval_Set::is_joinable(super, exterior.first, last_overlap);
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class KeyT>
Chris@16: typename enable_if< mpl::and_< is_concept_combinable<is_interval_map, is_interval_set, Type, KeyT>
Chris@16:                              , mpl::not_<is_total<Type> > >
Chris@16:             , bool>::type
Chris@16: contains(const Type& super, const KeyT& sub)
Chris@16: {
Chris@16:     return Interval_Set::within(sub, super);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& add(T&, c P&) T:{M} P:{b p} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: add(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.add(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: add(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     return icl::add(object, make_segment<Type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& add(T&, J, c P&) T:{M} P:{p} segment_type
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, typename Type::iterator >::type
Chris@16: add(Type& object, typename Type::iterator      prior_,
Chris@16:             const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.add(prior_, operand);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Insertion<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& insert(T&, c P&) T:{M} P:{b p} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: insert(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.insert(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: insert(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     return icl::insert(object, make_segment<Type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& insert(T&, J, c P&) T:{M} P:{p} with hint
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, typename Type::iterator>::type
Chris@16: insert(Type& object, typename Type::iterator      prior,
Chris@16:                const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.insert(prior, operand);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Erasure<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& erase(T&, c P&) T:{M} P:{e i} key_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: erase(Type& object, const typename Type::interval_type& operand)
Chris@16: {
Chris@16:     return object.erase(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: erase(Type& object, const typename Type::domain_type& operand)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     return icl::erase(object, icl::singleton<interval_type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& erase(T&, c P&) T:{M} P:{b p} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: erase(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.erase(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: erase(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     return icl::erase(object, make_segment<Type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& subtract(T&, c P&) T:{M} P:{b p} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type& 
Chris@16: subtract(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.subtract(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: subtract(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     return icl::subtract(object, make_segment<Type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& subtract(T&, c P&) T:{M} P:{e i} key_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: subtract(Type& object, const typename Type::domain_type& operand)
Chris@16: {
Chris@16:     return object.erase(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: subtract(Type& object, const typename Type::interval_type& operand)
Chris@16: {
Chris@16:     return object.erase(operand);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Selective Update<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& set_at(T&, c P&) T:{M} P:{e i}
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: set_at(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     icl::erase(object, operand.first); 
Chris@16:     return icl::insert(object, operand); 
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: set_at(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     return icl::set_at(object, make_segment<Type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Intersection<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& subtract(T&, c P&) T:{M} P:{b p} fragment_type
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, 
Chris@16:                  const typename Type::element_type& operand)
Chris@16: {
Chris@16:     typedef typename Type::segment_type segment_type;
Chris@16:     object.add_intersection(section, make_segment<Type>(operand));
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, 
Chris@16:                  const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     object.add_intersection(section, operand);
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type total
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type, class MapT>
Chris@16: typename enable_if
Chris@16: <
Chris@16:     mpl::and_< is_total<Type>
Chris@16:              , is_concept_compatible<is_interval_map, Type, MapT> >
Chris@16:   , void
Chris@16: >::type
Chris@16: add_intersection(Type& section, const Type& object, const MapT& operand)
Chris@16: {
Chris@16:     section += object;
Chris@16:     section += operand;
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type partial
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type, class MapT>
Chris@16: typename enable_if
Chris@16: <
Chris@16:     mpl::and_< mpl::not_<is_total<Type> >
Chris@16:              , is_concept_compatible<is_interval_map, Type, MapT> >
Chris@16:   , void
Chris@16: >::type
Chris@16: add_intersection(Type& section, const Type& object, const MapT& operand)
Chris@16: {
Chris@16:     typedef typename Type::segment_type   segment_type;
Chris@16:     typedef typename Type::interval_type  interval_type;
Chris@16:     typedef typename MapT::const_iterator const_iterator;
Chris@16: 
Chris@16:     if(operand.empty()) 
Chris@16:         return;
Chris@16:     const_iterator common_lwb, common_upb;
Chris@16:     if(!Set::common_range(common_lwb, common_upb, operand, object))
Chris@16:         return;
Chris@16:     const_iterator it_ = common_lwb;
Chris@16:     while(it_ != common_upb)
Chris@16:         add_intersection(section, object, *it_++);
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& subtract(T&, c P&) T:{M} P:{e i S} key_type
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, 
Chris@16:                  const typename Type::domain_type& key_value)
Chris@16: {
Chris@16:     typedef typename Type::interval_type  interval_type;
Chris@16:     typedef typename Type::segment_type   segment_type;
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16: 
Chris@16:     const_iterator it_ = icl::find(object, key_value);
Chris@16:     if(it_ != object.end())
Chris@16:         add(section, segment_type(interval_type(key_value),(*it_).second));
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, 
Chris@16:                  const typename Type::interval_type& inter_val)
Chris@16: {
Chris@16:     typedef typename Type::interval_type  interval_type;
Chris@16:     typedef typename Type::value_type     value_type;
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     typedef typename Type::iterator       iterator;
Chris@16: 
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return;
Chris@16: 
Chris@16:     std::pair<const_iterator, const_iterator> exterior 
Chris@16:         = object.equal_range(inter_val);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return;
Chris@16: 
Chris@16:     iterator prior_ = section.end();
Chris@16:     for(const_iterator it_=exterior.first; it_ != exterior.second; it_++) 
Chris@16:     {
Chris@16:         interval_type common_interval = (*it_).first & inter_val; 
Chris@16:         if(!icl::is_empty(common_interval))
Chris@16:             prior_ = add(section, prior_, 
Chris@16:                          value_type(common_interval, (*it_).second) );
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class KeySetT>
Chris@16: typename enable_if<is_concept_combinable<is_interval_map, is_interval_set, Type, KeySetT>, void>::type
Chris@16: add_intersection(Type& section, const Type& object, const KeySetT& key_set)
Chris@16: {
Chris@16:     typedef typename KeySetT::const_iterator const_iterator;
Chris@16: 
Chris@16:     if(icl::is_empty(key_set)) 
Chris@16:         return;
Chris@16: 
Chris@16:     const_iterator common_lwb, common_upb;
Chris@16:     if(!Set::common_range(common_lwb, common_upb, key_set, object))
Chris@16:         return;
Chris@16: 
Chris@16:     const_iterator it_ = common_lwb;
Chris@16:     while(it_ != common_upb)
Chris@16:         add_intersection(section, object, *it_++);
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- intersects<IntervalMaps> fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if<mpl::and_< is_interval_map<Type>
Chris@16:                             , is_total<Type>
Chris@16:                             , boost::is_same< OperandT
Chris@16:                                             , typename segment_type_of<Type>::type> >, 
Chris@16:                    bool>::type
Chris@16: intersects(const Type&, const OperandT&)
Chris@16: {
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if<mpl::and_< is_interval_map<Type>
Chris@16:                             , mpl::not_<is_total<Type> >
Chris@16:                             , boost::is_same<OperandT, typename segment_type_of<Type>::type> >, 
Chris@16:                    bool>::type
Chris@16: intersects(const Type& object, const OperandT& operand)
Chris@16: {
Chris@16:     Type intersection;
Chris@16:     icl::add_intersection(intersection, object, operand);
Chris@16:     return !icl::is_empty(intersection); 
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if<mpl::and_< is_interval_map<Type>
Chris@16:                             , boost::is_same<OperandT, typename element_type_of<Type>::type> >, 
Chris@16:                    bool>::type
Chris@16: intersects(const Type& object, const OperandT& operand)
Chris@16: {
Chris@16:     return icl::intersects(object, make_segment<Type>(operand)); 
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Symmetric difference<IntervalMap>
Chris@16: //==============================================================================
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& flip(T&, c P&) T:{M} P:{b p} fragment_types
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: flip(Type& object, const typename Type::segment_type& operand)
Chris@16: {
Chris@16:     return object.flip(operand);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename enable_if<is_interval_map<Type>, Type>::type&
Chris@16: flip(Type& object, const typename Type::element_type& operand)
Chris@16: {
Chris@16:     return icl::flip(object, make_segment<Type>(operand));
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& flip(T&, c P&) T:{M} P:{M'} total absorber 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if< mpl::and_< is_total<Type>
Chris@16:                              , absorbs_identities<Type>
Chris@16:                              , is_concept_compatible<is_interval_map, 
Chris@16:                                                      Type, OperandT >
Chris@16:                              >
Chris@16:                   , Type>::type&
Chris@16: flip(Type& object, const OperandT&)
Chris@16: {
Chris@16:     object.clear();
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& flip(T&, c P&) T:{M} P:{M'} total enricher 
Chris@16: //------------------------------------------------------------------------------
Chris@16: #ifdef BOOST_MSVC 
Chris@16: #pragma warning(push)
Chris@16: #pragma warning(disable:4127) // conditional expression is constant
Chris@16: #endif                        
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if< mpl::and_< is_total<Type>
Chris@16:                              , mpl::not_<absorbs_identities<Type> >
Chris@16:                              , is_concept_compatible<is_interval_map, 
Chris@16:                                                      Type, OperandT >
Chris@16:                              >
Chris@16:                   , Type>::type&
Chris@16: flip(Type& object, const OperandT& operand)
Chris@16: {
Chris@16:     typedef typename Type::codomain_type  codomain_type;
Chris@16: 
Chris@16:     object += operand;
Chris@16:     ICL_FORALL(typename Type, it_, object)
Chris@16:         (*it_).second = identity_element<codomain_type>::value();
Chris@16: 
Chris@16:     if(mpl::not_<is_interval_splitter<Type> >::value)
Chris@16:         icl::join(object);
Chris@16: 
Chris@16:     return object;
Chris@16: }
Chris@16: #ifdef BOOST_MSVC
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- T& flip(T&, c P&) T:{M} P:{M'} partial 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type, class OperandT>
Chris@16: typename enable_if< mpl::and_< mpl::not_<is_total<Type> > 
Chris@16:                              , is_concept_compatible<is_interval_map, 
Chris@16:                                                      Type, OperandT >
Chris@16:                              >
Chris@16:                   , Type>::type&
Chris@16: flip(Type& object, const OperandT& operand)
Chris@16: {
Chris@16:     typedef typename OperandT::const_iterator const_iterator;
Chris@16:     typedef typename Type::codomain_type  codomain_type;
Chris@16: 
Chris@16:     const_iterator common_lwb, common_upb;
Chris@16: 
Chris@16:     if(!Set::common_range(common_lwb, common_upb, operand, object))
Chris@16:         return object += operand;
Chris@16: 
Chris@16:     const_iterator it_ = operand.begin();
Chris@16: 
Chris@16:     // All elements of operand left of the common range are added
Chris@16:     while(it_ != common_lwb)
Chris@16:         icl::add(object, *it_++);
Chris@16:     // All elements of operand in the common range are symmetrically subtracted
Chris@16:     while(it_ != common_upb)
Chris@16:         icl::flip(object, *it_++);
Chris@16:     // All elements of operand right of the common range are added
Chris@16:     while(it_ != operand.end())
Chris@16:         icl::add(object, *it_++);
Chris@16: 
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Set selection
Chris@16: //==============================================================================
Chris@16: template<class Type, class SetT>
Chris@16: typename enable_if<is_concept_combinable<is_interval_set, is_interval_map, 
Chris@16:                                          SetT, Type>, SetT>::type&
Chris@16: domain(SetT& result, const Type& object)
Chris@16: {
Chris@16:     typedef typename SetT::iterator set_iterator;
Chris@16:     result.clear(); 
Chris@16:     set_iterator prior_ = result.end();
Chris@16:     ICL_const_FORALL(typename Type, it_, object) 
Chris@16:         prior_ = icl::insert(result, prior_, (*it_).first); 
Chris@16:     
Chris@16:     return result;
Chris@16: }
Chris@16: 
Chris@16: template<class Type, class SetT>
Chris@16: typename enable_if<is_concept_combinable<is_interval_set, is_interval_map, 
Chris@16:                                          SetT, Type>, SetT>::type&
Chris@16: between(SetT& in_between, const Type& object)
Chris@16: {
Chris@16:     typedef typename Type::const_iterator const_iterator;
Chris@16:     typedef typename SetT::iterator       set_iterator;
Chris@16:     in_between.clear();
Chris@16:     const_iterator it_ = object.begin(), pred_;
Chris@16:     set_iterator   prior_ = in_between.end();
Chris@16: 
Chris@16:     if(it_ != object.end())
Chris@16:         pred_ = it_++;
Chris@16: 
Chris@16:     while(it_ != object.end())
Chris@16:         prior_ = icl::insert(in_between, prior_, 
Chris@16:                              between((*pred_++).first, (*it_++).first));
Chris@16:     
Chris@16:     return in_between;
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Manipulation by predicates
Chris@16: //==============================================================================
Chris@16: template<class MapT, class Predicate>
Chris@16: typename enable_if<is_interval_map<MapT>, MapT>::type&
Chris@16: erase_if(const Predicate& pred, MapT& object)
Chris@16: {
Chris@16:     typename MapT::iterator it_ = object.begin();
Chris@16:     while(it_ != object.end())
Chris@16:         if(pred(*it_))
Chris@16:             object.erase(it_++); 
Chris@16:         else ++it_;
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template<class MapT, class Predicate>
Chris@16: inline typename enable_if<is_interval_map<MapT>, MapT>::type&
Chris@16: add_if(const Predicate& pred, MapT& object, const MapT& src)
Chris@16: {
Chris@16:     typename MapT::const_iterator it_ = src.begin();
Chris@16:     while(it_ != src.end())
Chris@16:         if(pred(*it_)) 
Chris@16:             icl::add(object, *it_++); 
Chris@16:     
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template<class MapT, class Predicate>
Chris@16: inline typename enable_if<is_interval_map<MapT>, MapT>::type&
Chris@16: assign_if(const Predicate& pred, MapT& object, const MapT& src)
Chris@16: {
Chris@16:     icl::clear(object);
Chris@16:     return add_if(object, src, pred);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Morphisms
Chris@16: //==============================================================================
Chris@16: template<class Type>
Chris@16: typename enable_if<mpl::and_< is_interval_map<Type>
Chris@16:                             , absorbs_identities<Type> >, Type>::type&
Chris@16: absorb_identities(Type& object)
Chris@16: {
Chris@16:     return object;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename enable_if<mpl::and_< is_interval_map<Type>
Chris@16:                             , mpl::not_<absorbs_identities<Type> > >, Type>::type&
Chris@16: absorb_identities(Type& object)
Chris@16: {
Chris@16:     typedef typename Type::segment_type segment_type;
Chris@16:     return icl::erase_if(content_is_identity_element<segment_type>(), object);
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Streaming
Chris@16: //==============================================================================
Chris@16: template<class CharType, class CharTraits, class Type>
Chris@16: typename enable_if<is_interval_map<Type>, 
Chris@16:                    std::basic_ostream<CharType, CharTraits> >::type& 
Chris@16: operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
Chris@16: {
Chris@16:     stream << "{";
Chris@16:     ICL_const_FORALL(typename Type, it_, object)
Chris@16:         stream << "(" << (*it_).first << "->" << (*it_).second << ")";
Chris@16: 
Chris@16:     return stream << "}";
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost icl
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: