text: /*-----------------------------------------------------------------------------+
  Copyright (c) 2008-2009: Joachim Faulhaber
  +------------------------------------------------------------------------------+
     Distributed under the Boost Software License, Version 1.0.
        (See accompanying file LICENCE.txt or copy at
             http://www.boost.org/LICENSE_1_0.txt)
  +-----------------------------------------------------------------------------*/
  #ifndef BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705
  #define BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705
  
  #include <boost/assert.hpp>
  #include <boost/icl/type_traits/is_map.hpp>
  #include <boost/icl/interval_set.hpp>
  #include <boost/icl/interval_base_map.hpp>
  
  namespace boost{namespace icl
  {
  
  template<class DomainT, class CodomainT, class Traits, 
           ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, 
           ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  class split_interval_map;
  
  /** \brief implements a map as a map of intervals - on insertion 
      overlapping intervals are split and associated values are combined.*/
  template
  <
      typename DomainT,
      typename CodomainT,
      class Traits = icl::partial_absorber,
      ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(std::less, DomainT),
      ICL_COMBINE Combine  = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
      ICL_SECTION Section  = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT), 
      ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
      ICL_ALLOC   Alloc    = std::allocator
  >
  class interval_map:
  
      public interval_base_map<interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 
                               DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
  {
  public:
      typedef Traits traits;
      typedef       interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type;
      typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> split_type;
      typedef type overloadable_type;
      typedef type joint_type;
      typedef interval_base_map<type, 
                                DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;
  
      typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
      typedef typename base_type::iterator      iterator;
      typedef typename base_type::value_type    value_type;
      typedef typename base_type::element_type  element_type;
      typedef typename base_type::segment_type  segment_type;
      typedef typename base_type::domain_type   domain_type;
      typedef typename base_type::codomain_type codomain_type;
      typedef typename base_type::domain_mapping_type domain_mapping_type;
      typedef typename base_type::interval_mapping_type interval_mapping_type;
      typedef typename base_type::ImplMapT ImplMapT;
  
      typedef typename base_type::size_type     size_type;
      typedef typename base_type::codomain_combine codomain_combine;
  
      typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type;
      typedef interval_set_type set_type;
      typedef set_type          key_object_type;
  
      enum { fineness = 1 };
  
  public:
      //==========================================================================
      //= Construct, copy, destruct
      //==========================================================================
      /// Default constructor for the empty object
      interval_map(): base_type() {}
      /// Copy constructor
      interval_map(const interval_map& src): base_type(src) {}
  
  
      /// Copy constructor for base_type
      template<class SubType>
      explicit interval_map
          (const interval_base_map<SubType,DomainT,CodomainT,
                                   Traits,Compare,Combine,Section,Interval,Alloc>& src)
      { this->assign(src); }
  
      explicit interval_map(domain_mapping_type& base_pair): base_type()
      { this->add(base_pair); }
  
      explicit interval_map(const value_type& value_pair): base_type()
      { this->add(value_pair); }
  
      /// Assignment operator
      template<class SubType>
      interval_map& operator =
          (const interval_base_map<SubType,DomainT,CodomainT,
                                   Traits,Compare,Combine,Section,Interval,Alloc>& src)
      { this->assign(src); return *this; }
  
      /// Assignment from a base interval_map.
      template<class SubType>
      void assign(const interval_base_map<SubType,DomainT,CodomainT,
                                          Traits,Compare,Combine,Section,Interval,Alloc>& src)
      {
          typedef interval_base_map<SubType,DomainT,CodomainT,
                                    Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
          this->clear();
          // Can be implemented via _map.insert: Interval joining not necessary.
          iterator prior_ = this->_map.end();
          ICL_const_FORALL(typename base_map_type, it_, src) 
              prior_ = this->add(prior_, *it_); 
      }
  
  private:
      // Private functions that shall be accessible by the baseclass:
      friend class
          interval_base_map <interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 
                                          DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
  
      iterator handle_inserted(iterator it_)
      {
          return segmental::join_neighbours(*this, it_); 
      }
  
      void handle_inserted(iterator prior_, iterator it_)
      {
          if(prior_ != this->_map.end() && segmental::joinable(*this, prior_, it_))
              segmental::join_on_right(*this, prior_, it_);
      }
  
      template<class Combiner>
      void handle_left_combined(iterator it_)
      {
          if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(it_->second))
              this->_map.erase(it_);
          else
              segmental::join_left(*this, it_);
      }
  
      template<class Combiner>
      void handle_combined(iterator it_)
      {
          if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(it_->second))
              this->_map.erase(it_);
          else
              segmental::join_neighbours(*this, it_);
      }
  
      template<class Combiner>
      void handle_preceeded_combined(iterator prior_, iterator& it_)
      {
          if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(it_->second))
          {
              this->_map.erase(it_);
              it_ = prior_;
          }
          else // After a new combination (e.g. combiner=max) joining neighbours may be possible
              segmental::join_neighbours(*this, it_);
      }
  
      template<class Combiner>
      void handle_succeeded_combined(iterator it_, iterator next_)
      {
          if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(it_->second))
          {
              this->_map.erase(it_);
              segmental::join_right(*this, next_);
          }
          else
          {
              segmental::join_left(*this, it_);
              segmental::join_neighbours(*this, next_);
          }
      }
  
  
  
      void handle_reinserted(iterator insertion_)
      { 
          segmental::join_right(*this, insertion_); 
      }
  
  
      template<class Combiner>
      void gap_insert_at(iterator& it_, iterator prior_, 
                         const interval_type& end_gap, const codomain_type& co_val)
      {
          if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(it_->second))
          {
              this->_map.erase(it_);
              it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
              segmental::join_right(*this, it_);
          }
          else 
          {
              segmental::join_left(*this, it_);
              iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
              it_ = segmental::join_neighbours(*this, inserted_);
          }
      }
  
  } ;
  
  
  //-----------------------------------------------------------------------------
  // type traits
  //-----------------------------------------------------------------------------
  template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  struct is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
  { 
      typedef is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
      BOOST_STATIC_CONSTANT(bool, value = true); 
  };
  
  template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  struct has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
  { 
      typedef has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
      BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value)); 
  };
  
  
  template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  struct is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
  {
      typedef is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
      BOOST_STATIC_CONSTANT(bool, value = true); 
  };
  
  template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  struct absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
  {
      typedef absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
      BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities)); 
  };
  
  template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  struct is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
  {
      typedef is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
      BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total)); 
  };
  
  
  //-----------------------------------------------------------------------------
  // type representation
  //-----------------------------------------------------------------------------
  template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
  struct type_to_string<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
  {
      static std::string apply()
      { 
          return "itv_map<"+ type_to_string<DomainT>::apply()   + ","
                           + type_to_string<CodomainT>::apply() + ","
                           + type_to_string<Traits>::apply()    + ">"; 
      }
  };
  
  }} // namespace icl boost
  
  #endif
  
  
  