Chris@16: /*-----------------------------------------------------------------------------+
Chris@16: Copyright (c) 2008-2012: 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_INTERVAL_MAP_HPP_JOFA_080705
Chris@16: #define BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/icl/type_traits/is_map.hpp>
Chris@16: #include <boost/icl/interval_set.hpp>
Chris@16: #include <boost/icl/interval_base_map.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: template<class DomainT, class CodomainT, class Traits, 
Chris@16:          ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, 
Chris@16:          ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
Chris@16: class split_interval_map;
Chris@16: 
Chris@16: /** \brief implements a map as a map of intervals - on insertion 
Chris@16:     overlapping intervals are split and associated values are combined.*/
Chris@16: template
Chris@16: <
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_map:
Chris@16: 
Chris@16:     public interval_base_map<interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 
Chris@16:                              DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
Chris@16: {
Chris@16: public:
Chris@16:     typedef Traits traits;
Chris@16:     typedef       interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type;
Chris@16:     typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> split_type;
Chris@16:     typedef type overloadable_type;
Chris@16:     typedef type joint_type;
Chris@16:     typedef interval_base_map<type, 
Chris@16:                               DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;
Chris@16: 
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
Chris@16:     typedef typename base_type::iterator      iterator;
Chris@16:     typedef typename base_type::value_type    value_type;
Chris@16:     typedef typename base_type::element_type  element_type;
Chris@16:     typedef typename base_type::segment_type  segment_type;
Chris@16:     typedef typename base_type::domain_type   domain_type;
Chris@16:     typedef typename base_type::codomain_type codomain_type;
Chris@16:     typedef typename base_type::domain_mapping_type domain_mapping_type;
Chris@16:     typedef typename base_type::interval_mapping_type interval_mapping_type;
Chris@16:     typedef typename base_type::ImplMapT ImplMapT;
Chris@16: 
Chris@16:     typedef typename base_type::size_type     size_type;
Chris@16:     typedef typename base_type::codomain_combine codomain_combine;
Chris@16: 
Chris@16:     typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type;
Chris@16:     typedef interval_set_type set_type;
Chris@16:     typedef set_type          key_object_type;
Chris@16: 
Chris@16:     enum { fineness = 1 };
Chris@16: 
Chris@16: public:
Chris@16:     //==========================================================================
Chris@16:     //= Construct, copy, destruct
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /// Default constructor for the empty object
Chris@16:     interval_map(): base_type() {}
Chris@16: 
Chris@16:     /// Copy constructor
Chris@16:     interval_map(const interval_map& src): base_type(src) {}
Chris@16: 
Chris@16:     /// Copy constructor for base_type
Chris@16:     template<class SubType>
Chris@16:     explicit interval_map
Chris@16:         (const interval_base_map<SubType,DomainT,CodomainT,
Chris@16:                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
Chris@16:     { this->assign(src); }
Chris@16: 
Chris@16:     explicit interval_map(const domain_mapping_type& base_pair): base_type()
Chris@16:     { this->add(base_pair); }
Chris@16: 
Chris@16:     explicit interval_map(const value_type& value_pair): base_type()
Chris@16:     { this->add(value_pair); }
Chris@16: 
Chris@16: 
Chris@16:     /// Assignment from a base interval_map.
Chris@16:     template<class SubType>
Chris@16:     void assign(const interval_base_map<SubType,DomainT,CodomainT,
Chris@16:                                         Traits,Compare,Combine,Section,Interval,Alloc>& src)
Chris@16:     {
Chris@16:         typedef interval_base_map<SubType,DomainT,CodomainT,
Chris@16:                                   Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
Chris@16:         this->clear();
Chris@16:         iterator prior_ = this->_map.end();
Chris@16:         ICL_const_FORALL(typename base_map_type, it_, src) 
Chris@16:             prior_ = this->add(prior_, *it_); 
Chris@16:     }
Chris@16: 
Chris@101:     /// Assignment operator for base type
Chris@101:     template<class SubType>
Chris@101:     interval_map& operator =
Chris@101:         (const interval_base_map<SubType,DomainT,CodomainT,
Chris@101:                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
Chris@101:     { 
Chris@101:         this->assign(src); 
Chris@101:         return *this; 
Chris@101:     }
Chris@101: 
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_map(interval_map&& src)
Chris@16:         : base_type(boost::move(src))
Chris@16:     {}
Chris@16: 
Chris@16:     /// Move assignment operator
Chris@101:     interval_map& operator = (interval_map src)
Chris@16:     { 
Chris@16:         base_type::operator=(boost::move(src));
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@101: #   else
Chris@101: 
Chris@101:     /// Assignment operator
Chris@101:     interval_map& operator = (const interval_map& src)
Chris@101:     { 
Chris@101:         base_type::operator=(src);
Chris@101:         return *this;
Chris@101:     }
Chris@101: 
Chris@16: #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16: private:
Chris@16:     // Private functions that shall be accessible by the baseclass:
Chris@16:     friend class
Chris@16:         interval_base_map <interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 
Chris@16:                                         DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
Chris@16: 
Chris@16:     iterator handle_inserted(iterator it_)
Chris@16:     {
Chris@16:         return segmental::join_neighbours(*this, it_); 
Chris@16:     }
Chris@16: 
Chris@16:     void handle_inserted(iterator prior_, iterator it_)
Chris@16:     {
Chris@16:         if(prior_ != this->_map.end() && segmental::joinable(*this, prior_, it_))
Chris@16:             segmental::join_on_right(*this, prior_, it_);
Chris@16:     }
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void handle_left_combined(iterator it_)
Chris@16:     {
Chris@16:         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
Chris@16:             this->_map.erase(it_);
Chris@16:         else
Chris@16:             segmental::join_left(*this, it_);
Chris@16:     }
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void handle_combined(iterator it_)
Chris@16:     {
Chris@16:         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
Chris@16:             this->_map.erase(it_);
Chris@16:         else
Chris@16:             segmental::join_neighbours(*this, it_);
Chris@16:     }
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void handle_preceeded_combined(iterator prior_, iterator& it_)
Chris@16:     {
Chris@16:         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
Chris@16:         {
Chris@16:             this->_map.erase(it_);
Chris@16:             it_ = prior_;
Chris@16:         }
Chris@16:         else // After a new combination (e.g. combiner=max) joining neighbours may be possible
Chris@16:             segmental::join_neighbours(*this, it_);
Chris@16:     }
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void handle_succeeded_combined(iterator it_, iterator next_)
Chris@16:     {
Chris@16:         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
Chris@16:         {
Chris@16:             this->_map.erase(it_);
Chris@16:             segmental::join_right(*this, next_);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             segmental::join_left(*this, it_);
Chris@16:             segmental::join_neighbours(*this, next_);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:     void handle_reinserted(iterator insertion_)
Chris@16:     { 
Chris@16:         segmental::join_right(*this, insertion_); 
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template<class Combiner>
Chris@16:     void gap_insert_at(iterator& it_, iterator prior_, 
Chris@16:                        const interval_type& end_gap, const codomain_type& co_val)
Chris@16:     {
Chris@16:         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
Chris@16:         {
Chris@16:             this->_map.erase(it_);
Chris@16:             it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
Chris@16:             segmental::join_right(*this, it_);
Chris@16:         }
Chris@16:         else 
Chris@16:         {
Chris@16:             segmental::join_left(*this, it_);
Chris@16:             iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
Chris@16:             it_ = segmental::join_neighbours(*this, inserted_);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: } ;
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // type traits
Chris@16: //-----------------------------------------------------------------------------
Chris@16: template <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: struct is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template <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: struct has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef has_inverse<icl::interval_map<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: 
Chris@16: template <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: struct is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: {
Chris@16:     typedef is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template <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: struct absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: {
Chris@16:     typedef absorbs_identities<icl::interval_map<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 <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: struct is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: {
Chris@16:     typedef is_total<icl::interval_map<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: // type representation
Chris@16: //-----------------------------------------------------------------------------
Chris@16: template <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: struct type_to_string<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
Chris@16: {
Chris@16:     static std::string apply()
Chris@16:     { 
Chris@16:         return "itv_map<"+ type_to_string<DomainT>::apply()   + ","
Chris@16:                          + type_to_string<CodomainT>::apply() + ","
Chris@16:                          + type_to_string<Traits>::apply()    + ">"; 
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: }} // namespace icl boost
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: