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