boost/icl/interval_map.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2008-2012: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705
0009 #define BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705
0010
0011 #include <boost/assert.hpp>
0012 #include <boost/icl/type_traits/is_map.hpp>
0013 #include <boost/icl/interval_set.hpp>
0014 #include <boost/icl/interval_base_map.hpp>
0015
0016 namespace boost{namespace icl
0017 {
0018
0019 template<class DomainT, class CodomainT, class Traits,
0020          ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section,
0021          ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0022 class split_interval_map;
0023
0024 /** \brief implements a map as a map of intervals - on insertion
0025     overlapping intervals are split and associated values are combined.*/
0026 template
0027 <
0028     typename DomainT,
0029     typename CodomainT,
0030     class Traits = icl::partial_absorber,
0031     ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
0032     ICL_COMBINE Combine  = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
0033     ICL_SECTION Section  = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
0034     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
0035     ICL_ALLOC   Alloc    = std::allocator
0036 >
0037 class interval_map:
0038
0039     public interval_base_map<interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
0040                              DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
0041 {
0042 public:
0043     typedef Traits traits;
0044     typedef       interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type;
0045     typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> split_type;
0046     typedef type overloadable_type;
0047     typedef type joint_type;
0048     typedef interval_base_map<type,
0049                               DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;
0050
0051     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
0052     typedef typename base_type::iterator      iterator;
0053     typedef typename base_type::value_type    value_type;
0054     typedef typename base_type::element_type  element_type;
0055     typedef typename base_type::segment_type  segment_type;
0056     typedef typename base_type::domain_type   domain_type;
0057     typedef typename base_type::codomain_type codomain_type;
0058     typedef typename base_type::domain_mapping_type domain_mapping_type;
0059     typedef typename base_type::interval_mapping_type interval_mapping_type;
0060     typedef typename base_type::ImplMapT ImplMapT;
0061
0062     typedef typename base_type::size_type     size_type;
0063     typedef typename base_type::codomain_combine codomain_combine;
0064
0065     typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type;
0066     typedef interval_set_type set_type;
0067     typedef set_type          key_object_type;
0068
0069     enum { fineness = 1 };
0070
0071 public:
0072     //==========================================================================
0073     //= Construct, copy, destruct
0074     //==========================================================================
0075
0076     /// Default constructor for the empty object
0077     interval_map(): base_type() {}
0078
0079     /// Copy constructor
0080     interval_map(const interval_map& src): base_type(src) {}
0081
0082     /// Copy constructor for base_type
0083     template<class SubType>
0084     explicit interval_map
0085         (const interval_base_map<SubType,DomainT,CodomainT,
0086                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
0087     { this->assign(src); }
0088
0089     explicit interval_map(const domain_mapping_type& base_pair): base_type()
0090     { this->add(base_pair); }
0091
0092     explicit interval_map(const value_type& value_pair): base_type()
0093     { this->add(value_pair); }
0094
0095
0096     /// Assignment from a base interval_map.
0097     template<class SubType>
0098     void assign(const interval_base_map<SubType,DomainT,CodomainT,
0099                                         Traits,Compare,Combine,Section,Interval,Alloc>& src)
0100     {
0101         typedef interval_base_map<SubType,DomainT,CodomainT,
0102                                   Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
0103         this->clear();
0104         iterator prior_ = this->_map.end();
0105         ICL_const_FORALL(typename base_map_type, it_, src)
0106             prior_ = this->add(prior_, *it_);
0107     }
0108
0109     /// Assignment operator for base type
0110     template<class SubType>
0111     interval_map& operator =
0112         (const interval_base_map<SubType,DomainT,CodomainT,
0113                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
0114     {
0115         this->assign(src);
0116         return *this;
0117     }
0118
0119 #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0120     //==========================================================================
0121     //= Move semantics
0122     //==========================================================================
0123
0124     /// Move constructor
0125     interval_map(interval_map&& src)
0126         : base_type(boost::move(src))
0127     {}
0128
0129     /// Move assignment operator
0130     interval_map& operator = (interval_map src)
0131     {
0132         base_type::operator=(boost::move(src));
0133         return *this;
0134     }
0135
0136     //==========================================================================
0137 #   else
0138
0139     /// Assignment operator
0140     interval_map& operator = (const interval_map& src)
0141     {
0142         base_type::operator=(src);
0143         return *this;
0144     }
0145
0146 #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
0147
0148 private:
0149     // Private functions that shall be accessible by the baseclass:
0150     friend class
0151         interval_base_map <interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
0152                                         DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
0153
0154     iterator handle_inserted(iterator it_)
0155     {
0156         return segmental::join_neighbours(*this, it_);
0157     }
0158
0159     void handle_inserted(iterator prior_, iterator it_)
0160     {
0161         if(prior_ != this->_map.end() && segmental::joinable(*this, prior_, it_))
0162             segmental::join_on_right(*this, prior_, it_);
0163     }
0164
0165     template<class Combiner>
0166     void handle_left_combined(iterator it_)
0167     {
0168         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
0169             this->_map.erase(it_);
0170         else
0171             segmental::join_left(*this, it_);
0172     }
0173
0174     template<class Combiner>
0175     void handle_combined(iterator it_)
0176     {
0177         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
0178             this->_map.erase(it_);
0179         else
0180             segmental::join_neighbours(*this, it_);
0181     }
0182
0183     template<class Combiner>
0184     void handle_preceeded_combined(iterator prior_, iterator& it_)
0185     {
0186         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
0187         {
0188             this->_map.erase(it_);
0189             it_ = prior_;
0190         }
0191         else // After a new combination (e.g. combiner=max) joining neighbours may be possible
0192             segmental::join_neighbours(*this, it_);
0193     }
0194
0195     template<class Combiner>
0196     void handle_succeeded_combined(iterator it_, iterator next_)
0197     {
0198         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
0199         {
0200             this->_map.erase(it_);
0201             segmental::join_right(*this, next_);
0202         }
0203         else
0204         {
0205             segmental::join_left(*this, it_);
0206             segmental::join_neighbours(*this, next_);
0207         }
0208     }
0209
0210
0211
0212     void handle_reinserted(iterator insertion_)
0213     {
0214         segmental::join_right(*this, insertion_);
0215     }
0216
0217
0218     template<class Combiner>
0219     void gap_insert_at(iterator& it_, iterator prior_,
0220                        const interval_type& end_gap, const codomain_type& co_val)
0221     {
0222         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
0223         {
0224             this->_map.erase(it_);
0225             it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
0226             segmental::join_right(*this, it_);
0227         }
0228         else
0229         {
0230             segmental::join_left(*this, it_);
0231             iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
0232             it_ = segmental::join_neighbours(*this, inserted_);
0233         }
0234     }
0235
0236 } ;
0237
0238
0239 //-----------------------------------------------------------------------------
0240 // type traits
0241 //-----------------------------------------------------------------------------
0242 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0243 struct is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
0244 {
0245     typedef is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
0246     BOOST_STATIC_CONSTANT(bool, value = true);
0247 };
0248
0249 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0250 struct has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
0251 {
0252     typedef has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
0253     BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value));
0254 };
0255
0256
0257 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0258 struct is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
0259 {
0260     typedef is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
0261     BOOST_STATIC_CONSTANT(bool, value = true);
0262 };
0263
0264 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0265 struct absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
0266 {
0267     typedef absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
0268     BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities));
0269 };
0270
0271 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0272 struct is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
0273 {
0274     typedef is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
0275     BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total));
0276 };
0277
0278
0279 //-----------------------------------------------------------------------------
0280 // type representation
0281 //-----------------------------------------------------------------------------
0282 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
0283 struct type_to_string<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
0284 {
0285     static std::string apply()
0286     {
0287         return "itv_map<"+ type_to_string<DomainT>::apply()   + ","
0288                          + type_to_string<CodomainT>::apply() + ","
0289                          + type_to_string<Traits>::apply()    + ">";
0290     }
0291 };
0292
0293 }} // namespace icl boost
0294
0295 #endif
0296
0297