1 /*-----------------------------------------------------------------------------+ 2 Copyright (c) 2008-2012: Joachim Faulhaber 3 +------------------------------------------------------------------------------+ 4 Distributed under the Boost Software License, Version 1.0. 5 (See accompanying file LICENCE.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt) 7 +-----------------------------------------------------------------------------*/ 8 #ifndef BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705 9 #define BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705 10 11 #include <boost/assert.hpp> 12 #include <boost/icl/type_traits/is_map.hpp> 13 #include <boost/icl/interval_set.hpp> 14 #include <boost/icl/interval_base_map.hpp> 15 16 namespace boost{namespace icl 17 { 18 19 template<class DomainT, class CodomainT, class Traits, 20 ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, 21 ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 22 class split_interval_map; 23 24 /** \brief implements a map as a map of intervals - on insertion 25 overlapping intervals are split and associated values are combined.*/ 26 template 27 < 28 typename DomainT, 29 typename CodomainT, 30 class Traits = icl::partial_absorber, 31 ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT), 32 ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT), 33 ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT), 34 ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare), 35 ICL_ALLOC Alloc = std::allocator 36 > 37 class interval_map: 38 39 public interval_base_map<interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 40 DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> 41 { 42 public: 43 typedef Traits traits; 44 typedef interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type; 45 typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> split_type; 46 typedef type overloadable_type; 47 typedef type joint_type; 48 typedef interval_base_map<type, 49 DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type; 50 51 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 52 typedef typename base_type::iterator iterator; 53 typedef typename base_type::value_type value_type; 54 typedef typename base_type::element_type element_type; 55 typedef typename base_type::segment_type segment_type; 56 typedef typename base_type::domain_type domain_type; 57 typedef typename base_type::codomain_type codomain_type; 58 typedef typename base_type::domain_mapping_type domain_mapping_type; 59 typedef typename base_type::interval_mapping_type interval_mapping_type; 60 typedef typename base_type::ImplMapT ImplMapT; 61 62 typedef typename base_type::size_type size_type; 63 typedef typename base_type::codomain_combine codomain_combine; 64 65 typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type; 66 typedef interval_set_type set_type; 67 typedef set_type key_object_type; 68 69 enum { fineness = 1 }; 70 71 public: 72 //========================================================================== 73 //= Construct, copy, destruct 74 //========================================================================== 75 76 /// Default constructor for the empty object interval_map()77 interval_map(): base_type() {} 78 79 /// Copy constructor interval_map(const interval_map & src)80 interval_map(const interval_map& src): base_type(src) {} 81 82 /// Copy constructor for base_type 83 template<class SubType> interval_map(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> & src)84 explicit interval_map 85 (const interval_base_map<SubType,DomainT,CodomainT, 86 Traits,Compare,Combine,Section,Interval,Alloc>& src) 87 { this->assign(src); } 88 interval_map(const domain_mapping_type & base_pair)89 explicit interval_map(const domain_mapping_type& base_pair): base_type() 90 { this->add(base_pair); } 91 interval_map(const value_type & value_pair)92 explicit interval_map(const value_type& value_pair): base_type() 93 { this->add(value_pair); } 94 95 96 /// Assignment from a base interval_map. 97 template<class SubType> assign(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> & src)98 void assign(const interval_base_map<SubType,DomainT,CodomainT, 99 Traits,Compare,Combine,Section,Interval,Alloc>& src) 100 { 101 typedef interval_base_map<SubType,DomainT,CodomainT, 102 Traits,Compare,Combine,Section,Interval,Alloc> base_map_type; 103 this->clear(); 104 iterator prior_ = this->_map.end(); 105 ICL_const_FORALL(typename base_map_type, it_, src) 106 prior_ = this->add(prior_, *it_); 107 } 108 109 /// Assignment operator for base type 110 template<class SubType> operator =(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> & src)111 interval_map& operator = 112 (const interval_base_map<SubType,DomainT,CodomainT, 113 Traits,Compare,Combine,Section,Interval,Alloc>& src) 114 { 115 this->assign(src); 116 return *this; 117 } 118 119 # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 120 //========================================================================== 121 //= Move semantics 122 //========================================================================== 123 124 /// Move constructor interval_map(interval_map && src)125 interval_map(interval_map&& src) 126 : base_type(boost::move(src)) 127 {} 128 129 /// Move assignment operator operator =(interval_map src)130 interval_map& operator = (interval_map src) 131 { 132 base_type::operator=(boost::move(src)); 133 return *this; 134 } 135 136 //========================================================================== 137 # else 138 139 /// Assignment operator operator =(const interval_map & src)140 interval_map& operator = (const interval_map& src) 141 { 142 base_type::operator=(src); 143 return *this; 144 } 145 146 # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 147 148 private: 149 // Private functions that shall be accessible by the baseclass: 150 friend class 151 interval_base_map <interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>, 152 DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>; 153 handle_inserted(iterator it_)154 iterator handle_inserted(iterator it_) 155 { 156 return segmental::join_neighbours(*this, it_); 157 } 158 handle_inserted(iterator prior_,iterator it_)159 void handle_inserted(iterator prior_, iterator it_) 160 { 161 if(prior_ != this->_map.end() && segmental::joinable(*this, prior_, it_)) 162 segmental::join_on_right(*this, prior_, it_); 163 } 164 165 template<class Combiner> handle_left_combined(iterator it_)166 void handle_left_combined(iterator it_) 167 { 168 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second)) 169 this->_map.erase(it_); 170 else 171 segmental::join_left(*this, it_); 172 } 173 174 template<class Combiner> handle_combined(iterator it_)175 void handle_combined(iterator it_) 176 { 177 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second)) 178 this->_map.erase(it_); 179 else 180 segmental::join_neighbours(*this, it_); 181 } 182 183 template<class Combiner> handle_preceeded_combined(iterator prior_,iterator & it_)184 void handle_preceeded_combined(iterator prior_, iterator& it_) 185 { 186 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second)) 187 { 188 this->_map.erase(it_); 189 it_ = prior_; 190 } 191 else // After a new combination (e.g. combiner=max) joining neighbours may be possible 192 segmental::join_neighbours(*this, it_); 193 } 194 195 template<class Combiner> handle_succeeded_combined(iterator it_,iterator next_)196 void handle_succeeded_combined(iterator it_, iterator next_) 197 { 198 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second)) 199 { 200 this->_map.erase(it_); 201 segmental::join_right(*this, next_); 202 } 203 else 204 { 205 segmental::join_left(*this, it_); 206 segmental::join_neighbours(*this, next_); 207 } 208 } 209 210 211 handle_reinserted(iterator insertion_)212 void handle_reinserted(iterator insertion_) 213 { 214 segmental::join_right(*this, insertion_); 215 } 216 217 218 template<class Combiner> gap_insert_at(iterator & it_,iterator prior_,const interval_type & end_gap,const codomain_type & co_val)219 void gap_insert_at(iterator& it_, iterator prior_, 220 const interval_type& end_gap, const codomain_type& co_val) 221 { 222 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second)) 223 { 224 this->_map.erase(it_); 225 it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val); 226 segmental::join_right(*this, it_); 227 } 228 else 229 { 230 segmental::join_left(*this, it_); 231 iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val); 232 it_ = segmental::join_neighbours(*this, inserted_); 233 } 234 } 235 236 } ; 237 238 239 //----------------------------------------------------------------------------- 240 // type traits 241 //----------------------------------------------------------------------------- 242 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 243 struct is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 244 { 245 typedef is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 246 BOOST_STATIC_CONSTANT(bool, value = true); 247 }; 248 249 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 250 struct has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 251 { 252 typedef has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 253 BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value)); 254 }; 255 256 257 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 258 struct is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 259 { 260 typedef is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 261 BOOST_STATIC_CONSTANT(bool, value = true); 262 }; 263 264 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 265 struct absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 266 { 267 typedef absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 268 BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities)); 269 }; 270 271 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 272 struct is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 273 { 274 typedef is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 275 BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total)); 276 }; 277 278 279 //----------------------------------------------------------------------------- 280 // type representation 281 //----------------------------------------------------------------------------- 282 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 283 struct type_to_string<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 284 { applyboost::icl::type_to_string285 static std::string apply() 286 { 287 return "itv_map<"+ type_to_string<DomainT>::apply() + "," 288 + type_to_string<CodomainT>::apply() + "," 289 + type_to_string<Traits>::apply() + ">"; 290 } 291 }; 292 293 }} // namespace icl boost 294 295 #endif 296 297 298