Chris@16: /*-----------------------------------------------------------------------------+
Chris@16: Copyright (c) 2007-2012: Joachim Faulhaber
Chris@16: Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
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_INTERVAL_BASE_MAP_HPP_JOFA_990223
Chris@16: #define BOOST_ICL_INTERVAL_BASE_MAP_HPP_JOFA_990223
Chris@16: 
Chris@16: #include <limits>
Chris@16: #include <boost/type_traits/ice.hpp>
Chris@16: #include <boost/mpl/and.hpp>
Chris@16: #include <boost/mpl/or.hpp>
Chris@16: #include <boost/mpl/not.hpp>
Chris@16: 
Chris@16: #include <boost/icl/detail/notate.hpp>
Chris@16: #include <boost/icl/detail/design_config.hpp>
Chris@16: #include <boost/icl/detail/on_absorbtion.hpp>
Chris@16: #include <boost/icl/detail/interval_map_algo.hpp>
Chris@16: 
Chris@16: #include <boost/icl/associative_interval_container.hpp>
Chris@16: 
Chris@16: #include <boost/icl/type_traits/is_interval_splitter.hpp>
Chris@16: #include <boost/icl/map.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: template<class DomainT, class CodomainT>
Chris@16: struct mapping_pair
Chris@16: {
Chris@16:     DomainT   key;
Chris@16:     CodomainT data;
Chris@16: 
Chris@16:     mapping_pair():key(), data(){}
Chris@16: 
Chris@16:     mapping_pair(const DomainT& key_value, const CodomainT& data_value)
Chris@16:         :key(key_value), data(data_value){}
Chris@16: 
Chris@16:     mapping_pair(const std::pair<DomainT,CodomainT>& std_pair)
Chris@16:         :key(std_pair.first), data(std_pair.second){}
Chris@16: };
Chris@16: 
Chris@16: /** \brief Implements a map as a map of intervals (base class) */
Chris@16: template
Chris@16: <
Chris@16:     class SubType,
Chris@16:     typename DomainT,
Chris@16:     typename CodomainT,
Chris@16:     class Traits = icl::partial_absorber,
Chris@16:     ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
Chris@16:     ICL_COMBINE Combine  = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
Chris@16:     ICL_SECTION Section  = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT), 
Chris@16:     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
Chris@16:     ICL_ALLOC   Alloc    = std::allocator
Chris@16: >
Chris@16: class interval_base_map
Chris@16: {
Chris@16: public:
Chris@16:     //==========================================================================
Chris@16:     //= Associated types
Chris@16:     //==========================================================================
Chris@16:     typedef interval_base_map<SubType,DomainT,CodomainT,
Chris@16:                               Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:                               type;
Chris@16: 
Chris@16:     /// The designated \e derived or \e sub_type of this base class
Chris@16:     typedef SubType sub_type;
Chris@16: 
Chris@16:     /// Auxilliary type for overloadresolution
Chris@16:     typedef type overloadable_type;
Chris@16: 
Chris@16:     /// Traits of an itl map
Chris@16:     typedef Traits traits;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Related types
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// The atomized type representing the corresponding container of elements
Chris@16:     typedef typename icl::map<DomainT,CodomainT,
Chris@16:                               Traits,Compare,Combine,Section,Alloc> atomized_type;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Data
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// Domain type (type of the keys) of the map
Chris@16:     typedef DomainT   domain_type;
Chris@16:     typedef typename boost::call_traits<DomainT>::param_type domain_param;
Chris@16:     /// Domain type (type of the keys) of the map
Chris@16:     typedef CodomainT codomain_type;
Chris@16:     /// Auxiliary type to help the compiler resolve ambiguities when using std::make_pair
Chris@16:     typedef mapping_pair<domain_type,codomain_type> domain_mapping_type;
Chris@16:     /// Conceptual is a map a set of elements of type \c element_type
Chris@16:     typedef domain_mapping_type element_type;
Chris@16:     /// The interval type of the map
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
Chris@16:     /// Auxiliary type for overload resolution
Chris@16:     typedef std::pair<interval_type,CodomainT> interval_mapping_type;
Chris@16:     /// Type of an interval containers segment, that is spanned by an interval
Chris@16:     typedef std::pair<interval_type,CodomainT> segment_type;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Size
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// The difference type of an interval which is sometimes different form the domain_type
Chris@16:     typedef typename difference_type_of<domain_type>::type difference_type;
Chris@16:     /// The size type of an interval which is mostly std::size_t
Chris@16:     typedef typename size_type_of<domain_type>::type size_type;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Functors
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// Comparison functor for domain values
Chris@16:     typedef ICL_COMPARE_DOMAIN(Compare,DomainT)      domain_compare;
Chris@16:     typedef ICL_COMPARE_DOMAIN(Compare,segment_type) segment_compare;
Chris@16:     /// Combine functor for codomain value aggregation
Chris@16:     typedef ICL_COMBINE_CODOMAIN(Combine,CodomainT)  codomain_combine;
Chris@16:     /// Inverse Combine functor for codomain value aggregation
Chris@16:     typedef typename inverse<codomain_combine>::type inverse_codomain_combine;
Chris@16:     /// Intersection functor for codomain values
Chris@16: 
Chris@16:     typedef typename mpl::if_
Chris@16:     <has_set_semantics<codomain_type>
Chris@16:     , ICL_SECTION_CODOMAIN(Section,CodomainT)     
Chris@16:     , codomain_combine
Chris@16:     >::type                                            codomain_intersect;
Chris@16: 
Chris@16: 
Chris@16:     /// Inverse Combine functor for codomain value intersection
Chris@16:     typedef typename inverse<codomain_intersect>::type inverse_codomain_intersect;
Chris@16: 
Chris@16:     /// Comparison functor for intervals which are keys as well
Chris@16:     typedef exclusive_less_than<interval_type> interval_compare;
Chris@16: 
Chris@16:     /// Comparison functor for keys
Chris@16:     typedef exclusive_less_than<interval_type> key_compare;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Implementation and stl related
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// The allocator type of the set
Chris@16:     typedef Alloc<std::pair<const interval_type, codomain_type> > 
Chris@16:         allocator_type;
Chris@16: 
Chris@16:     /// Container type for the implementation 
Chris@16:     typedef ICL_IMPL_SPACE::map<interval_type,codomain_type,
Chris@16:                                 key_compare,allocator_type> ImplMapT;
Chris@16: 
Chris@16:     /// key type of the implementing container
Chris@16:     typedef typename ImplMapT::key_type   key_type;
Chris@16:     /// value type of the implementing container
Chris@16:     typedef typename ImplMapT::value_type value_type;
Chris@16:     /// data type of the implementing container
Chris@16:     typedef typename ImplMapT::value_type::second_type data_type;
Chris@16: 
Chris@16:     /// pointer type
Chris@16:     typedef typename ImplMapT::pointer         pointer;
Chris@16:     /// const pointer type
Chris@16:     typedef typename ImplMapT::const_pointer   const_pointer;
Chris@16:     /// reference type
Chris@16:     typedef typename ImplMapT::reference       reference;
Chris@16:     /// const reference type
Chris@16:     typedef typename ImplMapT::const_reference const_reference;
Chris@16: 
Chris@16:     /// iterator for iteration over intervals
Chris@16:     typedef typename ImplMapT::iterator iterator;
Chris@16:     /// const_iterator for iteration over intervals
Chris@16:     typedef typename ImplMapT::const_iterator const_iterator;
Chris@16:     /// iterator for reverse iteration over intervals
Chris@16:     typedef typename ImplMapT::reverse_iterator reverse_iterator;
Chris@16:     /// const_iterator for iteration over intervals
Chris@16:     typedef typename ImplMapT::const_reverse_iterator const_reverse_iterator;
Chris@16: 
Chris@16:     /// element iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<iterator> element_iterator; 
Chris@16:     /// const element iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<const_iterator> element_const_iterator; 
Chris@16:     /// element reverse iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<reverse_iterator> element_reverse_iterator; 
Chris@16:     /// element const reverse iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<const_reverse_iterator> element_const_reverse_iterator; 
Chris@16:     
Chris@16:     typedef typename on_absorbtion<type, codomain_combine, 
Chris@16:                                 Traits::absorbs_identities>::type on_codomain_absorbtion;
Chris@16: 
Chris@16: public:
Chris@16:     BOOST_STATIC_CONSTANT(bool, 
Chris@16:         is_total_invertible = (   Traits::is_total 
Chris@16:                                && has_inverse<codomain_type>::value));
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(int, fineness = 0); 
Chris@16: 
Chris@16: public:
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Construct, copy, destruct
Chris@16:     //==========================================================================
Chris@16:     /** Default constructor for the empty object */
Chris@16:     interval_base_map()
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
Chris@16:     }
Chris@16: 
Chris@16:     /** Copy constructor */
Chris@16:     interval_base_map(const interval_base_map& src): _map(src._map)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
Chris@16:     }
Chris@16: 
Chris@16: #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16:     //==========================================================================
Chris@16:     //= Move semantics
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Move constructor */
Chris@16:     interval_base_map(interval_base_map&& src): _map(boost::move(src._map))
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
Chris@16:     }
Chris@16: 
Chris@16:     /** Move assignment operator */
Chris@101:     interval_base_map& operator = (interval_base_map src) 
Chris@101:     {                           //call by value sice 'src' is a "sink value" 
Chris@16:         this->_map = boost::move(src._map);
Chris@16:         return *this; 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@101: #   else 
Chris@101: 
Chris@101:     /** Copy assignment operator */
Chris@101:     interval_base_map& operator = (const interval_base_map& src) 
Chris@101:     { 
Chris@101:         this->_map = src._map;
Chris@101:         return *this; 
Chris@101:     }
Chris@101: 
Chris@16: #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16:     /** swap the content of containers */
Chris@16:     void swap(interval_base_map& object) { _map.swap(object._map); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Containedness
Chris@16:     //==========================================================================
Chris@16:     /** clear the map */
Chris@16:     void clear() { icl::clear(*that()); }
Chris@16: 
Chris@16:     /** is the map empty? */
Chris@16:     bool empty()const { return icl::is_empty(*that()); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Size
Chris@16:     //==========================================================================
Chris@16:     /** An interval map's size is it's cardinality */
Chris@16:     size_type size()const
Chris@16:     {
Chris@16:         return icl::cardinality(*that());
Chris@16:     }
Chris@16: 
Chris@16:     /** Size of the iteration over this container */
Chris@16:     std::size_t iterative_size()const 
Chris@16:     { 
Chris@16:         return _map.size(); 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Selection
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Find the interval value pair, that contains \c key */
Chris@16:     const_iterator find(const domain_type& key_value)const
Chris@16:     { 
Chris@16:         return icl::find(*this, key_value);
Chris@16:     }
Chris@16: 
Chris@16:     /** Find the first interval value pair, that collides with interval 
Chris@16:         \c key_interval */
Chris@16:     const_iterator find(const interval_type& key_interval)const
Chris@16:     { 
Chris@16:         return _map.find(key_interval); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Total select function. */
Chris@16:     codomain_type operator()(const domain_type& key_value)const
Chris@16:     {
Chris@16:         const_iterator it_ = icl::find(*this, key_value);
Chris@16:         return it_==end() ? identity_element<codomain_type>::value()
Chris@16:                           : (*it_).second;
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Addition
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Addition of a key value pair to the map */
Chris@16:     SubType& add(const element_type& key_value_pair) 
Chris@16:     {
Chris@16:         return icl::add(*that(), key_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     /** Addition of an interval value pair to the map. */
Chris@16:     SubType& add(const segment_type& interval_value_pair) 
Chris@16:     {
Chris@16:         this->template _add<codomain_combine>(interval_value_pair);
Chris@16:         return *that();
Chris@16:     }
Chris@16: 
Chris@16:     /** Addition of an interval value pair \c interval_value_pair to the map. 
Chris@16:         Iterator \c prior_ is a hint to the position \c interval_value_pair can be 
Chris@16:         inserted after. */
Chris@16:     iterator add(iterator prior_, const segment_type& interval_value_pair) 
Chris@16:     {
Chris@16:         return this->template _add<codomain_combine>(prior_, interval_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Subtraction
Chris@16:     //==========================================================================
Chris@16:     /** Subtraction of a key value pair from the map */
Chris@16:     SubType& subtract(const element_type& key_value_pair)
Chris@16:     { 
Chris@16:         return icl::subtract(*that(), key_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     /** Subtraction of an interval value pair from the map. */
Chris@16:     SubType& subtract(const segment_type& interval_value_pair)
Chris@16:     {
Chris@16:         on_invertible<type, is_total_invertible>
Chris@16:             ::subtract(*that(), interval_value_pair);
Chris@16:         return *that();
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Insertion
Chris@16:     //==========================================================================
Chris@16:     /** Insertion of a \c key_value_pair into the map. */
Chris@16:     SubType& insert(const element_type& key_value_pair) 
Chris@16:     {
Chris@16:         return icl::insert(*that(), key_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     /** Insertion of an \c interval_value_pair into the map. */
Chris@16:     SubType& insert(const segment_type& interval_value_pair)
Chris@16:     { 
Chris@16:         _insert(interval_value_pair); 
Chris@16:         return *that();
Chris@16:     }
Chris@16: 
Chris@16:     /** Insertion of an \c interval_value_pair into the map. Iterator \c prior_. 
Chris@16:         serves as a hint to insert after the element \c prior point to. */
Chris@16:     iterator insert(iterator prior, const segment_type& interval_value_pair)
Chris@16:     { 
Chris@16:         return _insert(prior, interval_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     /** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */
Chris@16:     SubType& set(const element_type& key_value_pair) 
Chris@16:     { 
Chris@16:         return icl::set_at(*that(), key_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     /** With <tt>interval_value_pair = (I,v)</tt> set value \c v 
Chris@16:         for all keys in interval \c I in the map. */
Chris@16:     SubType& set(const segment_type& interval_value_pair)
Chris@16:     { 
Chris@16:         return icl::set_at(*that(), interval_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Erasure
Chris@16:     //==========================================================================
Chris@16:     /** Erase a \c key_value_pair from the map. */
Chris@16:     SubType& erase(const element_type& key_value_pair) 
Chris@16:     { 
Chris@16:         icl::erase(*that(), key_value_pair);
Chris@16:         return *that();
Chris@16:     }
Chris@16: 
Chris@16:     /** Erase an \c interval_value_pair from the map. */
Chris@16:     SubType& erase(const segment_type& interval_value_pair);
Chris@16: 
Chris@16:     /** Erase a key value pair for \c key. */
Chris@16:     SubType& erase(const domain_type& key) 
Chris@16:     { 
Chris@16:         return icl::erase(*that(), key); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Erase all value pairs within the range of the 
Chris@16:         interval <tt>inter_val</tt> from the map.   */
Chris@16:     SubType& erase(const interval_type& inter_val);
Chris@16: 
Chris@16: 
Chris@16:     /** Erase all value pairs within the range of the interval that iterator 
Chris@16:         \c position points to. */
Chris@16:     void erase(iterator position){ this->_map.erase(position); }
Chris@16: 
Chris@16:     /** Erase all value pairs for a range of iterators <tt>[first,past)</tt>. */
Chris@16:     void erase(iterator first, iterator past){ this->_map.erase(first, past); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Intersection
Chris@16:     //==========================================================================
Chris@16:     /** The intersection of \c interval_value_pair and \c *this map is added to \c section. */
Chris@16:     void add_intersection(SubType& section, const segment_type& interval_value_pair)const
Chris@16:     {
Chris@16:         on_definedness<SubType, Traits::is_total>
Chris@16:             ::add_intersection(section, *that(), interval_value_pair);
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Symmetric difference
Chris@16:     //==========================================================================
Chris@16:     /** If \c *this map contains \c key_value_pair it is erased, otherwise it is added. */
Chris@16:     SubType& flip(const element_type& key_value_pair)
Chris@16:     { 
Chris@16:         return icl::flip(*that(), key_value_pair); 
Chris@16:     }
Chris@16: 
Chris@16:     /** If \c *this map contains \c interval_value_pair it is erased, otherwise it is added. */
Chris@16:     SubType& flip(const segment_type& interval_value_pair)
Chris@16:     {
Chris@16:         on_total_absorbable<SubType, Traits::is_total, Traits::absorbs_identities>
Chris@16:             ::flip(*that(), interval_value_pair);
Chris@16:         return *that();
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Iterator related
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     iterator lower_bound(const key_type& interval)
Chris@16:     { return _map.lower_bound(interval); }
Chris@16: 
Chris@16:     iterator upper_bound(const key_type& interval)
Chris@16:     { return _map.upper_bound(interval); }
Chris@16: 
Chris@16:     const_iterator lower_bound(const key_type& interval)const
Chris@16:     { return _map.lower_bound(interval); }
Chris@16: 
Chris@16:     const_iterator upper_bound(const key_type& interval)const
Chris@16:     { return _map.upper_bound(interval); }
Chris@16: 
Chris@16:     std::pair<iterator,iterator> equal_range(const key_type& interval)
Chris@16:     { 
Chris@16:         return std::pair<iterator,iterator>
Chris@16:                (lower_bound(interval), upper_bound(interval)); 
Chris@16:     }
Chris@16: 
Chris@16:     std::pair<const_iterator,const_iterator> 
Chris@16:         equal_range(const key_type& interval)const
Chris@16:     { 
Chris@16:         return std::pair<const_iterator,const_iterator>
Chris@16:                (lower_bound(interval), upper_bound(interval)); 
Chris@16:     }
Chris@16: 
Chris@16:     iterator begin() { return _map.begin(); }
Chris@16:     iterator end()   { return _map.end(); }
Chris@16:     const_iterator begin()const { return _map.begin(); }
Chris@16:     const_iterator end()const   { return _map.end(); }
Chris@16:     reverse_iterator rbegin() { return _map.rbegin(); }
Chris@16:     reverse_iterator rend()   { return _map.rend(); }
Chris@16:     const_reverse_iterator rbegin()const { return _map.rbegin(); }
Chris@16:     const_reverse_iterator rend()const   { return _map.rend(); }
Chris@16: 
Chris@16: private:
Chris@16:     template<class Combiner>
Chris@16:     iterator _add(const segment_type& interval_value_pair);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     iterator _add(iterator prior_, const segment_type& interval_value_pair);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void _subtract(const segment_type& interval_value_pair);
Chris@16: 
Chris@16:     iterator _insert(const segment_type& interval_value_pair);
Chris@16:     iterator _insert(iterator prior_, const segment_type& interval_value_pair);
Chris@16: 
Chris@16: private:
Chris@16:     template<class Combiner>
Chris@16:     void add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void add_main(interval_type& inter_val, const CodomainT& co_val, 
Chris@16:                   iterator& it_, const iterator& last_);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
Chris@16: 
Chris@16:     void add_front(const interval_type& inter_val, iterator& first_);
Chris@16: 
Chris@16: private:
Chris@16:     void subtract_front(const interval_type& inter_val, iterator& first_);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_);
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_);
Chris@16: 
Chris@16: private:
Chris@16:     void insert_main(const interval_type&, const CodomainT&, iterator&, const iterator&);
Chris@16:     void erase_rest (      interval_type&, const CodomainT&, iterator&, const iterator&);
Chris@16: 
Chris@16:     template<class FragmentT>
Chris@16:     void total_add_intersection(SubType& section, const FragmentT& fragment)const
Chris@16:     {
Chris@16:         section += *that();
Chris@16:         section.add(fragment);
Chris@16:     }
Chris@16: 
Chris@16:     void partial_add_intersection(SubType& section, const segment_type& operand)const
Chris@16:     {
Chris@16:         interval_type inter_val = operand.first;
Chris@16:         if(icl::is_empty(inter_val)) 
Chris@16:             return;
Chris@16: 
Chris@16:         std::pair<const_iterator, const_iterator> exterior = equal_range(inter_val);
Chris@16:         if(exterior.first == exterior.second)
Chris@16:             return;
Chris@16: 
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:             {
Chris@16:                 section.template _add<codomain_combine>  (value_type(common_interval, (*it_).second) );
Chris@16:                 section.template _add<codomain_intersect>(value_type(common_interval, operand.second));
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void partial_add_intersection(SubType& section, const element_type& operand)const
Chris@16:     {
Chris@16:         partial_add_intersection(section, make_segment<type>(operand));
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: protected:
Chris@16: 
Chris@16:     template <class Combiner>
Chris@16:     iterator gap_insert(iterator prior_, const interval_type& inter_val, 
Chris@16:                                          const codomain_type& co_val   )
Chris@16:     {
Chris@16:         // inter_val is not conained in this map. Insertion will be successful
Chris@16:         BOOST_ASSERT(this->_map.find(inter_val) == this->_map.end());
Chris@16:         BOOST_ASSERT((!on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val)));
Chris@16:         return this->_map.insert(prior_, value_type(inter_val, version<Combiner>()(co_val)));
Chris@16:     }
Chris@16: 
Chris@16:     template <class Combiner>
Chris@16:     std::pair<iterator, bool>
Chris@16:     add_at(const iterator& prior_, const interval_type& inter_val, 
Chris@16:                                    const codomain_type& co_val   )
Chris@16:     {
Chris@16:         // Never try to insert an identity element into an identity element absorber here:
Chris@16:         BOOST_ASSERT((!(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val))));
Chris@16: 
Chris@16:         iterator inserted_ 
Chris@16:             = this->_map.insert(prior_, value_type(inter_val, Combiner::identity_element()));
Chris@16: 
Chris@16:         if((*inserted_).first == inter_val && (*inserted_).second == Combiner::identity_element())
Chris@16:         {
Chris@16:             Combiner()((*inserted_).second, co_val);
Chris@16:             return std::pair<iterator,bool>(inserted_, true);
Chris@16:         }
Chris@16:         else
Chris@16:             return std::pair<iterator,bool>(inserted_, false);
Chris@16:     }
Chris@16: 
Chris@16:     std::pair<iterator, bool>
Chris@16:     insert_at(const iterator& prior_, const interval_type& inter_val, 
Chris@16:                                       const codomain_type& co_val   )
Chris@16:     {
Chris@16:         iterator inserted_
Chris@16:             = this->_map.insert(prior_, value_type(inter_val, co_val));
Chris@16: 
Chris@16:         if(inserted_ == prior_)
Chris@16:             return std::pair<iterator,bool>(inserted_, false);
Chris@16:         else if((*inserted_).first == inter_val)
Chris@16:             return std::pair<iterator,bool>(inserted_, true);
Chris@16:         else
Chris@16:             return std::pair<iterator,bool>(inserted_, false);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: protected:
Chris@16:     sub_type* that() { return static_cast<sub_type*>(this); }
Chris@16:     const sub_type* that()const { return static_cast<const sub_type*>(this); }
Chris@16: 
Chris@16: protected:
Chris@16:     ImplMapT _map;
Chris@16: 
Chris@16: 
Chris@16: private:
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool is_total_invertible>
Chris@16:     struct on_invertible;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_invertible<Type, true>
Chris@16:     {
Chris@16:         typedef typename Type::segment_type segment_type;
Chris@16:         typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
Chris@16: 
Chris@16:         static void subtract(Type& object, const segment_type& operand)
Chris@16:         { object.template _add<inverse_codomain_combine>(operand); }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_invertible<Type, false>
Chris@16:     {
Chris@16:         typedef typename Type::segment_type segment_type;
Chris@16:         typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
Chris@16: 
Chris@16:         static void subtract(Type& object, const segment_type& operand)
Chris@16:         { object.template _subtract<inverse_codomain_combine>(operand); }
Chris@16:     };
Chris@16: 
Chris@16:     friend struct on_invertible<type, true>;
Chris@16:     friend struct on_invertible<type, false>;
Chris@16:     //--------------------------------------------------------------------------
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool is_total>
Chris@16:     struct on_definedness;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_definedness<Type, true>
Chris@16:     {
Chris@16:         static void add_intersection(Type& section, const Type& object, 
Chris@16:                                      const segment_type& operand)
Chris@16:         { object.total_add_intersection(section, operand); }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_definedness<Type, false>
Chris@16:     {
Chris@16:         static void add_intersection(Type& section, const Type& object, 
Chris@16:                                      const segment_type& operand)
Chris@16:         { object.partial_add_intersection(section, operand); }
Chris@16:     };
Chris@16: 
Chris@16:     friend struct on_definedness<type, true>;
Chris@16:     friend struct on_definedness<type, false>;
Chris@16:     //--------------------------------------------------------------------------
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool has_set_semantics> 
Chris@16:     struct on_codomain_model;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_codomain_model<Type, true>
Chris@16:     {
Chris@16:         typedef typename Type::interval_type interval_type;
Chris@16:         typedef typename Type::codomain_type codomain_type;
Chris@16:         typedef typename Type::segment_type  segment_type;
Chris@16:         typedef typename Type::codomain_combine codomain_combine;
Chris@16:         typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
Chris@16: 
Chris@16:         static void add(Type& intersection, interval_type& common_interval, 
Chris@16:                         const codomain_type& flip_value, const codomain_type& co_value)
Chris@16:         {
Chris@16:             codomain_type common_value = flip_value;
Chris@16:             inverse_codomain_intersect()(common_value, co_value);
Chris@16:             intersection.template 
Chris@16:                 _add<codomain_combine>(segment_type(common_interval, common_value));
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_codomain_model<Type, false>
Chris@16:     {
Chris@16:         typedef typename Type::interval_type interval_type;
Chris@16:         typedef typename Type::codomain_type codomain_type;
Chris@16:         typedef typename Type::segment_type  segment_type;
Chris@16:         typedef typename Type::codomain_combine codomain_combine;
Chris@16: 
Chris@16:         static void add(Type& intersection, interval_type& common_interval, 
Chris@16:                         const codomain_type&, const codomain_type&)
Chris@16:         {
Chris@16:             intersection.template 
Chris@16:               _add<codomain_combine>(segment_type(common_interval, 
Chris@16:                                                   identity_element<codomain_type>::value()));
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     friend struct on_codomain_model<type, true>;
Chris@16:     friend struct on_codomain_model<type, false>;
Chris@16:     //--------------------------------------------------------------------------
Chris@16: 
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     template<class Type, bool is_total, bool absorbs_identities>
Chris@16:     struct on_total_absorbable;
Chris@16: 
Chris@16:     template<class Type>
Chris@16:     struct on_total_absorbable<Type, true, true>
Chris@16:     {
Chris@16:         static void flip(Type& object, const typename Type::segment_type&)
Chris@16:         { icl::clear(object); }
Chris@16:     };
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: 
Chris@16:     template<class Type>
Chris@16:     struct on_total_absorbable<Type, true, false>
Chris@16:     {
Chris@16:         typedef typename Type::segment_type  segment_type;
Chris@16:         typedef typename Type::codomain_type codomain_type;
Chris@16: 
Chris@16:         static void flip(Type& object, const segment_type& operand)
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:     };
Chris@16: 
Chris@16: #ifdef BOOST_MSVC
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16:     template<class Type, bool absorbs_identities>
Chris@16:     struct on_total_absorbable<Type, false, absorbs_identities>
Chris@16:     {
Chris@16:         typedef typename Type::segment_type   segment_type;
Chris@16:         typedef typename Type::codomain_type  codomain_type;
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::set_type       set_type;
Chris@16:         typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
Chris@16: 
Chris@16:         static void flip(Type& object, const segment_type& interval_value_pair)
Chris@16:         {
Chris@16:             // That which is common shall be subtracted
Chris@16:             // That which is not shall be added
Chris@16:             // So interval_value_pair has to be 'complementary added' or flipped
Chris@16:             interval_type span = interval_value_pair.first;
Chris@16:             std::pair<const_iterator, const_iterator> exterior 
Chris@16:                 = object.equal_range(span);
Chris@16: 
Chris@16:             const_iterator first_ = exterior.first;
Chris@16:             const_iterator end_   = exterior.second;
Chris@16: 
Chris@16:             interval_type covered, left_over, common_interval;
Chris@16:             const codomain_type& x_value = interval_value_pair.second;
Chris@16:             const_iterator it_ = first_;
Chris@16: 
Chris@16:             set_type eraser;
Chris@16:             Type     intersection;
Chris@16: 
Chris@16:             while(it_ != end_  ) 
Chris@16:             {
Chris@16:                 const codomain_type& co_value = (*it_).second;
Chris@16:                 covered = (*it_++).first;
Chris@16:                 //[a      ...  : span
Chris@16:                 //     [b ...  : covered
Chris@16:                 //[a  b)       : left_over
Chris@16:                 left_over = right_subtract(span, covered);
Chris@16: 
Chris@16:                 //That which is common ...
Chris@16:                 common_interval = span & covered;
Chris@16:                 if(!icl::is_empty(common_interval))
Chris@16:                 {
Chris@16:                     // ... shall be subtracted
Chris@16:                     icl::add(eraser, common_interval);
Chris@16: 
Chris@16:                     on_codomain_model<Type, has_set_semantics<codomain_type>::value>
Chris@16:                         ::add(intersection, common_interval, x_value, co_value);
Chris@16:                 }
Chris@16: 
Chris@16:                 icl::add(object, value_type(left_over, x_value)); //That which is not shall be added
Chris@16:                 // Because this is a collision free addition I don't have to distinguish codomain_types.
Chris@16: 
Chris@16:                 //...      d) : span
Chris@16:                 //... c)      : covered
Chris@16:                 //     [c  d) : span'
Chris@16:                 span = left_subtract(span, covered);
Chris@16:             }
Chris@16: 
Chris@16:             //If span is not empty here, it is not in the set so it shall be added
Chris@16:             icl::add(object, value_type(span, x_value));
Chris@16: 
Chris@16:             //finally rewrite the common segments
Chris@16:             icl::erase(object, eraser);
Chris@16:             object += intersection;
Chris@16:         }
Chris@16:     };
Chris@16:     //--------------------------------------------------------------------------
Chris@16: } ;
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition detail
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::add_front(const interval_type& inter_val, iterator& first_)
Chris@16: {
Chris@16:     // If the collision sequence has a left residual 'left_resid' it will
Chris@16:     // be split, to provide a standardized start of algorithms:
Chris@16:     // The addend interval 'inter_val' covers the beginning of the collision sequence.
Chris@16: 
Chris@16:     // only for the first there can be a left_resid: a part of *first_ left of inter_val
Chris@16:     interval_type left_resid = right_subtract((*first_).first, inter_val);
Chris@16: 
Chris@16:     if(!icl::is_empty(left_resid))
Chris@16:     {   //            [------------ . . .
Chris@16:         // [left_resid---first_ --- . . .
Chris@16:         iterator prior_ = cyclic_prior(*this, first_);
Chris@16:         const_cast<interval_type&>((*first_).first) 
Chris@16:             = left_subtract((*first_).first, left_resid);
Chris@16:         //NOTE: Only splitting
Chris@16:         this->_map.insert(prior_, segment_type(left_resid, (*first_).second));
Chris@16:     }
Chris@16:     //POST:
Chris@16:     // [----- inter_val ---- . . .
Chris@16:     // ...[-- first_ --...
Chris@16: }
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
Chris@16: {
Chris@16:     interval_type lead_gap = right_subtract(inter_val, (*it_).first);
Chris@16:     if(!icl::is_empty(lead_gap))
Chris@16:     {
Chris@16:         // [lead_gap--- . . .
Chris@16:         //          [-- it_ ...
Chris@101:         iterator prior_ = it_==this->_map.begin()? it_ : prior(it_); 
Chris@16:         iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
Chris@16:         that()->handle_inserted(prior_, inserted_);
Chris@16:     }
Chris@16: 
Chris@16:     // . . . --------- . . . addend interval
Chris@16:     //      [-- it_ --)      has a common part with the first overval
Chris@16:     Combiner()((*it_).second, co_val);
Chris@16:     that()->template handle_left_combined<Combiner>(it_++);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::add_main(interval_type& inter_val, const CodomainT& co_val, 
Chris@16:                iterator& it_, const iterator& last_)
Chris@16: {
Chris@16:     interval_type cur_interval;
Chris@16:     while(it_!=last_)
Chris@16:     {
Chris@16:         cur_interval = (*it_).first ;
Chris@16:         add_segment<Combiner>(inter_val, co_val, it_);
Chris@16:         // shrink interval
Chris@16:         inter_val = left_subtract(inter_val, cur_interval);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
Chris@16: {
Chris@16:     iterator prior_ = cyclic_prior(*that(), it_);
Chris@16:     interval_type cur_itv = (*it_).first ;
Chris@16: 
Chris@16:     interval_type lead_gap = right_subtract(inter_val, cur_itv);
Chris@16:     if(!icl::is_empty(lead_gap))
Chris@16:     {   //         [lead_gap--- . . .
Chris@16:         // [prior)          [-- it_ ...
Chris@16:         iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
Chris@16:         that()->handle_inserted(prior_, inserted_);
Chris@16:     }
Chris@16: 
Chris@16:     interval_type end_gap = left_subtract(inter_val, cur_itv);
Chris@16:     if(!icl::is_empty(end_gap))
Chris@16:     {
Chris@16:         // [----------------end_gap)
Chris@16:         //  . . . -- it_ --)
Chris@16:         Combiner()((*it_).second, co_val);
Chris@16:         that()->template gap_insert_at<Combiner>(it_, prior_, end_gap, co_val);
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         // only for the last there can be a right_resid: a part of *it_ right of x
Chris@16:         interval_type right_resid = left_subtract(cur_itv, inter_val);
Chris@16: 
Chris@16:         if(icl::is_empty(right_resid))
Chris@16:         {
Chris@16:             // [---------------)
Chris@16:             //      [-- it_ ---)
Chris@16:             Combiner()((*it_).second, co_val);
Chris@16:             that()->template handle_preceeded_combined<Combiner>(prior_, it_);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             // [--------------)
Chris@16:             //      [-- it_ --right_resid)
Chris@16:             const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid);
Chris@16: 
Chris@16:             //NOTE: This is NOT an insertion that has to take care for correct application of
Chris@16:             // the Combiner functor. It only reestablished that state after splitting the
Chris@16:             // 'it_' interval value pair. Using _map_insert<Combiner> does not work here.
Chris@16:             iterator insertion_ = this->_map.insert(it_, value_type(right_resid, (*it_).second));
Chris@16:             that()->handle_reinserted(insertion_);
Chris@16: 
Chris@16:             Combiner()((*it_).second, co_val);
Chris@16:             that()->template handle_preceeded_combined<Combiner>(insertion_, it_);
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
Chris@16:     interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::_add(const segment_type& addend)
Chris@16: {
Chris@16:     typedef typename on_absorbtion<type,Combiner,
Chris@16:                                 absorbs_identities<type>::value>::type on_absorbtion_;
Chris@16: 
Chris@16:     const interval_type& inter_val = addend.first;
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return this->_map.end();
Chris@16: 
Chris@16:     const codomain_type& co_val = addend.second;
Chris@16:     if(on_absorbtion_::is_absorbable(co_val))
Chris@16:         return this->_map.end();
Chris@16: 
Chris@16:     std::pair<iterator,bool> insertion 
Chris@16:         = this->_map.insert(value_type(inter_val, version<Combiner>()(co_val)));
Chris@16: 
Chris@16:     if(insertion.second)
Chris@16:         return that()->handle_inserted(insertion.first);
Chris@16:     else
Chris@16:     {
Chris@16:         // Detect the first and the end iterator of the collision sequence
Chris@16:         iterator first_ = this->_map.lower_bound(inter_val),
Chris@101:                  last_  = prior(this->_map.upper_bound(inter_val));
Chris@16:         //assert(end_ == this->_map.upper_bound(inter_val));
Chris@16:         iterator it_ = first_;
Chris@16:         interval_type rest_interval = inter_val;
Chris@16: 
Chris@16:         add_front         (rest_interval,         it_       );
Chris@16:         add_main<Combiner>(rest_interval, co_val, it_, last_);
Chris@16:         add_rear<Combiner>(rest_interval, co_val, it_       );
Chris@16:         return it_;
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
Chris@16:     interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::_add(iterator prior_, const segment_type& addend)
Chris@16: {
Chris@16:     typedef typename on_absorbtion<type,Combiner,
Chris@16:                                 absorbs_identities<type>::value>::type on_absorbtion_;
Chris@16: 
Chris@16:     const interval_type& inter_val = addend.first;
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return prior_;
Chris@16: 
Chris@16:     const codomain_type& co_val = addend.second;
Chris@16:     if(on_absorbtion_::is_absorbable(co_val))
Chris@16:         return prior_;
Chris@16: 
Chris@16:     std::pair<iterator,bool> insertion 
Chris@16:         = add_at<Combiner>(prior_, inter_val, co_val);
Chris@16: 
Chris@16:     if(insertion.second)
Chris@16:         return that()->handle_inserted(insertion.first);
Chris@16:     else
Chris@16:     {
Chris@16:         // Detect the first and the end iterator of the collision sequence
Chris@16:         std::pair<iterator,iterator> overlap = equal_range(inter_val);
Chris@16:         iterator it_   = overlap.first,
Chris@16:                  last_ = prior(overlap.second);
Chris@16:         interval_type rest_interval = inter_val;
Chris@16: 
Chris@16:         add_front         (rest_interval,         it_       );
Chris@16:         add_main<Combiner>(rest_interval, co_val, it_, last_);
Chris@16:         add_rear<Combiner>(rest_interval, co_val, it_       );
Chris@16:         return it_;
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction detail
Chris@16: //==============================================================================
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::subtract_front(const interval_type& inter_val, iterator& it_)
Chris@16: {
Chris@16:     interval_type left_resid = right_subtract((*it_).first, inter_val);
Chris@16: 
Chris@16:     if(!icl::is_empty(left_resid)) //                     [--- inter_val ---)
Chris@16:     {                              //[prior_) [left_resid)[--- it_ . . .
Chris@16:         iterator prior_ = cyclic_prior(*this, it_); 
Chris@16:         const_cast<interval_type&>((*it_).first) = left_subtract((*it_).first, left_resid);
Chris@16:         this->_map.insert(prior_, value_type(left_resid, (*it_).second));
Chris@16:         // The segemnt *it_ is split at inter_val.first(), so as an invariant
Chris@16:         // segment *it_ is always "under" inter_val and a left_resid is empty.
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_)
Chris@16: {
Chris@16:     while(it_ != last_)
Chris@16:     {
Chris@16:         Combiner()((*it_).second, co_val);
Chris@16:         that()->template handle_left_combined<Combiner>(it_++);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_)
Chris@16: {
Chris@16:     interval_type right_resid = left_subtract((*it_).first, inter_val);
Chris@16: 
Chris@16:     if(icl::is_empty(right_resid))
Chris@16:     {
Chris@16:         Combiner()((*it_).second, co_val);
Chris@16:         that()->template handle_combined<Combiner>(it_);
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid);
Chris@16:         iterator next_ = this->_map.insert(it_, value_type(right_resid, (*it_).second));
Chris@16:         Combiner()((*it_).second, co_val);
Chris@16:         that()->template handle_succeeded_combined<Combiner>(it_, next_);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16:     template<class Combiner>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::_subtract(const segment_type& minuend)
Chris@16: {
Chris@16:     interval_type inter_val = minuend.first;
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return;
Chris@16: 
Chris@16:     const codomain_type& co_val = minuend.second;
Chris@16:     if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val)) 
Chris@16:         return;
Chris@16: 
Chris@16:     std::pair<iterator, iterator> exterior = equal_range(inter_val);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return;
Chris@16: 
Chris@16:     iterator last_  = prior(exterior.second);
Chris@16:     iterator it_    = exterior.first;
Chris@16:     subtract_front          (inter_val,         it_       );
Chris@16:     subtract_main <Combiner>(           co_val, it_, last_);
Chris@16:     subtract_rear <Combiner>(inter_val, co_val, it_       );
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Insertion
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::insert_main(const interval_type& inter_val, const CodomainT& co_val, 
Chris@16:                   iterator& it_, const iterator& last_)
Chris@16: {
Chris@16:     iterator end_   = boost::next(last_);
Chris@101:     iterator prior_ = cyclic_prior(*this,it_), inserted_;
Chris@16:     interval_type rest_interval = inter_val, left_gap, cur_itv;
Chris@16:     interval_type last_interval = last_ ->first;
Chris@16: 
Chris@16:     while(it_ != end_  )
Chris@16:     {
Chris@16:         cur_itv = (*it_).first ;            
Chris@16:         left_gap = right_subtract(rest_interval, cur_itv);
Chris@16: 
Chris@16:         if(!icl::is_empty(left_gap))
Chris@16:         {
Chris@16:             inserted_ = this->_map.insert(prior_, value_type(left_gap, co_val));
Chris@16:             it_ = that()->handle_inserted(inserted_);
Chris@16:         }
Chris@16: 
Chris@16:         // shrink interval
Chris@16:         rest_interval = left_subtract(rest_interval, cur_itv);
Chris@16:         prior_ = it_;
Chris@16:         ++it_;
Chris@16:     }
Chris@16: 
Chris@16:     //insert_rear(rest_interval, co_val, last_):
Chris@16:     interval_type end_gap = left_subtract(rest_interval, last_interval);
Chris@16:     if(!icl::is_empty(end_gap))
Chris@16:     {
Chris@16:         inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val));
Chris@16:         it_ = that()->handle_inserted(inserted_);
Chris@16:     }
Chris@16:     else
Chris@16:         it_ = prior_;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
Chris@16:     interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::_insert(const segment_type& addend)
Chris@16: {
Chris@16:     interval_type inter_val = addend.first;
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return this->_map.end();
Chris@16: 
Chris@16:     const codomain_type& co_val = addend.second;
Chris@16:     if(on_codomain_absorbtion::is_absorbable(co_val)) 
Chris@16:         return this->_map.end();
Chris@16: 
Chris@16:     std::pair<iterator,bool> insertion = this->_map.insert(addend);
Chris@16: 
Chris@16:     if(insertion.second)
Chris@16:         return that()->handle_inserted(insertion.first);
Chris@16:     else
Chris@16:     {
Chris@16:         // Detect the first and the end iterator of the collision sequence
Chris@16:         iterator first_ = this->_map.lower_bound(inter_val),
Chris@101:                  last_  = prior(this->_map.upper_bound(inter_val));
Chris@16:         //assert((++last_) == this->_map.upper_bound(inter_val));
Chris@16:         iterator it_ = first_;
Chris@16:         insert_main(inter_val, co_val, it_, last_);
Chris@16:         return it_;
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
Chris@16:     interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::_insert(iterator prior_, const segment_type& addend)
Chris@16: {
Chris@16:     interval_type inter_val = addend.first;
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return prior_;
Chris@16: 
Chris@16:     const codomain_type& co_val = addend.second;
Chris@16:     if(on_codomain_absorbtion::is_absorbable(co_val)) 
Chris@16:         return prior_;
Chris@16: 
Chris@16:     std::pair<iterator,bool> insertion = insert_at(prior_, inter_val, co_val);
Chris@16: 
Chris@16:     if(insertion.second)
Chris@16:         return that()->handle_inserted(insertion.first);
Chris@16:     {
Chris@16:         // Detect the first and the end iterator of the collision sequence
Chris@16:         std::pair<iterator,iterator> overlap = equal_range(inter_val);
Chris@16:         iterator it_    = overlap.first,
Chris@16:                  last_  = prior(overlap.second);
Chris@16:         insert_main(inter_val, co_val, it_, last_);
Chris@16:         return it_;
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Erasure segment_type
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::erase_rest(interval_type& inter_val, const CodomainT& co_val, 
Chris@16:                  iterator& it_, const iterator& last_)
Chris@16: {
Chris@16:     // For all intervals within loop: (*it_).first are contained_in inter_val
Chris@16:     while(it_ != last_)
Chris@16:         if((*it_).second == co_val)
Chris@16:             this->_map.erase(it_++); 
Chris@16:         else it_++;
Chris@16: 
Chris@16:     //erase_rear:
Chris@16:     if((*it_).second == co_val)
Chris@16:     {
Chris@16:         interval_type right_resid = left_subtract((*it_).first, inter_val);
Chris@16:         if(icl::is_empty(right_resid))
Chris@16:             this->_map.erase(it_);
Chris@16:         else
Chris@16:             const_cast<interval_type&>((*it_).first) = right_resid;
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::erase(const segment_type& minuend)
Chris@16: {
Chris@16:     interval_type inter_val = minuend.first;
Chris@16:     if(icl::is_empty(inter_val)) 
Chris@16:         return *that();
Chris@16: 
Chris@16:     const codomain_type& co_val = minuend.second;
Chris@16:     if(on_codomain_absorbtion::is_absorbable(co_val))
Chris@16:         return *that();
Chris@16: 
Chris@16:     std::pair<iterator,iterator> exterior = equal_range(inter_val);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return *that();
Chris@16: 
Chris@16:     iterator first_ = exterior.first, end_ = exterior.second, 
Chris@16:              last_  = cyclic_prior(*this, end_);
Chris@16:     iterator second_= first_; ++second_;
Chris@16: 
Chris@16:     if(first_ == last_) 
Chris@16:     {   //     [----inter_val----)
Chris@16:         //   .....first_==last_.....
Chris@16:         // only for the last there can be a right_resid: a part of *it_ right of minuend
Chris@16:         interval_type right_resid = left_subtract((*first_).first, inter_val);
Chris@16: 
Chris@16:         if((*first_).second == co_val)
Chris@16:         {   
Chris@16:             interval_type left_resid = right_subtract((*first_).first, inter_val);
Chris@16:             if(!icl::is_empty(left_resid)) //            [----inter_val----)
Chris@16:             {                              // [left_resid)..first_==last_......
Chris@16:                 const_cast<interval_type&>((*first_).first) = left_resid;
Chris@16:                 if(!icl::is_empty(right_resid))
Chris@16:                     this->_map.insert(first_, value_type(right_resid, co_val));
Chris@16:             }
Chris@16:             else if(!icl::is_empty(right_resid))
Chris@16:                 const_cast<interval_type&>((*first_).first) = right_resid;
Chris@16:             else
Chris@16:                 this->_map.erase(first_);
Chris@16:         }
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         // first AND NOT last
Chris@16:         if((*first_).second == co_val)
Chris@16:         {
Chris@16:             interval_type left_resid = right_subtract((*first_).first, inter_val);
Chris@16:             if(icl::is_empty(left_resid))
Chris@16:                 this->_map.erase(first_);
Chris@16:             else
Chris@16:                 const_cast<interval_type&>((*first_).first) = left_resid;
Chris@16:         }
Chris@16: 
Chris@16:         erase_rest(inter_val, co_val, second_, last_);
Chris@16:     }
Chris@16: 
Chris@16:      return *that();
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Erasure key_type
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16:     ::erase(const interval_type& minuend)
Chris@16: {
Chris@16:     if(icl::is_empty(minuend)) 
Chris@16:         return *that();
Chris@16: 
Chris@16:     std::pair<iterator, iterator> exterior = equal_range(minuend);
Chris@16:     if(exterior.first == exterior.second)
Chris@16:         return *that();
Chris@16: 
Chris@16:     iterator first_ = exterior.first,
Chris@16:              end_   = exterior.second,
Chris@16:              last_  = prior(end_);
Chris@16: 
Chris@16:     interval_type left_resid  = right_subtract((*first_).first, minuend);
Chris@16:     interval_type right_resid =  left_subtract(last_ ->first, minuend);
Chris@16: 
Chris@16:     if(first_ == last_ )
Chris@16:         if(!icl::is_empty(left_resid))
Chris@16:         {
Chris@16:             const_cast<interval_type&>((*first_).first) = left_resid;
Chris@16:             if(!icl::is_empty(right_resid))
Chris@16:                 this->_map.insert(first_, value_type(right_resid, (*first_).second));
Chris@16:         }
Chris@16:         else if(!icl::is_empty(right_resid))
Chris@16:             const_cast<interval_type&>((*first_).first) = left_subtract((*first_).first, minuend);
Chris@16:         else
Chris@16:             this->_map.erase(first_);
Chris@16:     else
Chris@16:     {   //            [-------- minuend ---------)
Chris@16:         // [left_resid   fst)   . . . .    [lst  right_resid)
Chris@16:         iterator second_= first_; ++second_;
Chris@16: 
Chris@16:         iterator start_ = icl::is_empty(left_resid)? first_: second_;
Chris@16:         iterator stop_  = icl::is_empty(right_resid)? end_  : last_ ;
Chris@16:         this->_map.erase(start_, stop_); //erase [start_, stop_)
Chris@16: 
Chris@16:         if(!icl::is_empty(left_resid))
Chris@16:             const_cast<interval_type&>((*first_).first) = left_resid;
Chris@16: 
Chris@16:         if(!icl::is_empty(right_resid))
Chris@16:             const_cast<interval_type&>(last_ ->first) = right_resid;
Chris@16:     }
Chris@16: 
Chris@16:     return *that();
Chris@16: }
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // type traits
Chris@16: //-----------------------------------------------------------------------------
Chris@16: template 
Chris@16: <
Chris@16:     class SubType,
Chris@16:     class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc
Chris@16: >
Chris@16: struct is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template 
Chris@16: <
Chris@16:     class SubType,
Chris@16:     class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc
Chris@16: >
Chris@16: struct has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value)); 
Chris@16: };
Chris@16: 
Chris@16: template 
Chris@16: <
Chris@16:     class SubType,
Chris@16:     class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc
Chris@16: >
Chris@16: struct is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template 
Chris@16: <
Chris@16:     class SubType,
Chris@16:     class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc
Chris@16: >
Chris@16: struct absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: {
Chris@16:     typedef absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities)); 
Chris@16: };
Chris@16: 
Chris@16: template 
Chris@16: <
Chris@16:     class SubType,
Chris@16:     class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc
Chris@16: >
Chris@16: struct is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: {
Chris@16:     typedef is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total)); 
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: }} // namespace icl boost
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: