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_INTERVAL_BASE_MAP_HPP_JOFA_990223 10 #define BOOST_ICL_INTERVAL_BASE_MAP_HPP_JOFA_990223 11 12 #include <limits> 13 #include <boost/type_traits/ice.hpp> 14 #include <boost/mpl/and.hpp> 15 #include <boost/mpl/or.hpp> 16 #include <boost/mpl/not.hpp> 17 18 #include <boost/icl/detail/notate.hpp> 19 #include <boost/icl/detail/design_config.hpp> 20 #include <boost/icl/detail/on_absorbtion.hpp> 21 #include <boost/icl/detail/interval_map_algo.hpp> 22 23 #include <boost/icl/associative_interval_container.hpp> 24 25 #include <boost/icl/type_traits/is_interval_splitter.hpp> 26 #include <boost/icl/map.hpp> 27 28 namespace boost{namespace icl 29 { 30 31 template<class DomainT, class CodomainT> 32 struct mapping_pair 33 { 34 DomainT key; 35 CodomainT data; 36 mapping_pairboost::icl::mapping_pair37 mapping_pair():key(), data(){} 38 mapping_pairboost::icl::mapping_pair39 mapping_pair(const DomainT& key_value, const CodomainT& data_value) 40 :key(key_value), data(data_value){} 41 mapping_pairboost::icl::mapping_pair42 mapping_pair(const std::pair<DomainT,CodomainT>& std_pair) 43 :key(std_pair.first), data(std_pair.second){} 44 }; 45 46 /** \brief Implements a map as a map of intervals (base class) */ 47 template 48 < 49 class SubType, 50 typename DomainT, 51 typename CodomainT, 52 class Traits = icl::partial_absorber, 53 ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT), 54 ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT), 55 ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT), 56 ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare), 57 ICL_ALLOC Alloc = std::allocator 58 > 59 class interval_base_map 60 { 61 public: 62 //========================================================================== 63 //= Associated types 64 //========================================================================== 65 typedef interval_base_map<SubType,DomainT,CodomainT, 66 Traits,Compare,Combine,Section,Interval,Alloc> 67 type; 68 69 /// The designated \e derived or \e sub_type of this base class 70 typedef SubType sub_type; 71 72 /// Auxilliary type for overloadresolution 73 typedef type overloadable_type; 74 75 /// Traits of an itl map 76 typedef Traits traits; 77 78 //-------------------------------------------------------------------------- 79 //- Associated types: Related types 80 //-------------------------------------------------------------------------- 81 /// The atomized type representing the corresponding container of elements 82 typedef typename icl::map<DomainT,CodomainT, 83 Traits,Compare,Combine,Section,Alloc> atomized_type; 84 85 //-------------------------------------------------------------------------- 86 //- Associated types: Data 87 //-------------------------------------------------------------------------- 88 /// Domain type (type of the keys) of the map 89 typedef DomainT domain_type; 90 typedef typename boost::call_traits<DomainT>::param_type domain_param; 91 /// Domain type (type of the keys) of the map 92 typedef CodomainT codomain_type; 93 /// Auxiliary type to help the compiler resolve ambiguities when using std::make_pair 94 typedef mapping_pair<domain_type,codomain_type> domain_mapping_type; 95 /// Conceptual is a map a set of elements of type \c element_type 96 typedef domain_mapping_type element_type; 97 /// The interval type of the map 98 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 99 /// Auxiliary type for overload resolution 100 typedef std::pair<interval_type,CodomainT> interval_mapping_type; 101 /// Type of an interval containers segment, that is spanned by an interval 102 typedef std::pair<interval_type,CodomainT> segment_type; 103 104 //-------------------------------------------------------------------------- 105 //- Associated types: Size 106 //-------------------------------------------------------------------------- 107 /// The difference type of an interval which is sometimes different form the domain_type 108 typedef typename difference_type_of<domain_type>::type difference_type; 109 /// The size type of an interval which is mostly std::size_t 110 typedef typename size_type_of<domain_type>::type size_type; 111 112 //-------------------------------------------------------------------------- 113 //- Associated types: Functors 114 //-------------------------------------------------------------------------- 115 /// Comparison functor for domain values 116 typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare; 117 typedef ICL_COMPARE_DOMAIN(Compare,segment_type) segment_compare; 118 /// Combine functor for codomain value aggregation 119 typedef ICL_COMBINE_CODOMAIN(Combine,CodomainT) codomain_combine; 120 /// Inverse Combine functor for codomain value aggregation 121 typedef typename inverse<codomain_combine>::type inverse_codomain_combine; 122 /// Intersection functor for codomain values 123 124 typedef typename mpl::if_ 125 <has_set_semantics<codomain_type> 126 , ICL_SECTION_CODOMAIN(Section,CodomainT) 127 , codomain_combine 128 >::type codomain_intersect; 129 130 131 /// Inverse Combine functor for codomain value intersection 132 typedef typename inverse<codomain_intersect>::type inverse_codomain_intersect; 133 134 /// Comparison functor for intervals which are keys as well 135 typedef exclusive_less_than<interval_type> interval_compare; 136 137 /// Comparison functor for keys 138 typedef exclusive_less_than<interval_type> key_compare; 139 140 //-------------------------------------------------------------------------- 141 //- Associated types: Implementation and stl related 142 //-------------------------------------------------------------------------- 143 /// The allocator type of the set 144 typedef Alloc<std::pair<const interval_type, codomain_type> > 145 allocator_type; 146 147 /// Container type for the implementation 148 typedef ICL_IMPL_SPACE::map<interval_type,codomain_type, 149 key_compare,allocator_type> ImplMapT; 150 151 /// key type of the implementing container 152 typedef typename ImplMapT::key_type key_type; 153 /// value type of the implementing container 154 typedef typename ImplMapT::value_type value_type; 155 /// data type of the implementing container 156 typedef typename ImplMapT::value_type::second_type data_type; 157 158 /// pointer type 159 typedef typename ImplMapT::pointer pointer; 160 /// const pointer type 161 typedef typename ImplMapT::const_pointer const_pointer; 162 /// reference type 163 typedef typename ImplMapT::reference reference; 164 /// const reference type 165 typedef typename ImplMapT::const_reference const_reference; 166 167 /// iterator for iteration over intervals 168 typedef typename ImplMapT::iterator iterator; 169 /// const_iterator for iteration over intervals 170 typedef typename ImplMapT::const_iterator const_iterator; 171 /// iterator for reverse iteration over intervals 172 typedef typename ImplMapT::reverse_iterator reverse_iterator; 173 /// const_iterator for iteration over intervals 174 typedef typename ImplMapT::const_reverse_iterator const_reverse_iterator; 175 176 /// element iterator: Depreciated, see documentation. 177 typedef boost::icl::element_iterator<iterator> element_iterator; 178 /// const element iterator: Depreciated, see documentation. 179 typedef boost::icl::element_iterator<const_iterator> element_const_iterator; 180 /// element reverse iterator: Depreciated, see documentation. 181 typedef boost::icl::element_iterator<reverse_iterator> element_reverse_iterator; 182 /// element const reverse iterator: Depreciated, see documentation. 183 typedef boost::icl::element_iterator<const_reverse_iterator> element_const_reverse_iterator; 184 185 typedef typename on_absorbtion<type, codomain_combine, 186 Traits::absorbs_identities>::type on_codomain_absorbtion; 187 188 public: 189 BOOST_STATIC_CONSTANT(bool, 190 is_total_invertible = ( Traits::is_total 191 && has_inverse<codomain_type>::value)); 192 193 BOOST_STATIC_CONSTANT(int, fineness = 0); 194 195 public: 196 197 //========================================================================== 198 //= Construct, copy, destruct 199 //========================================================================== 200 /** Default constructor for the empty object */ interval_base_map()201 interval_base_map() 202 { 203 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>)); 204 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>)); 205 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>)); 206 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>)); 207 } 208 209 /** Copy constructor */ interval_base_map(const interval_base_map & src)210 interval_base_map(const interval_base_map& src): _map(src._map) 211 { 212 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>)); 213 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>)); 214 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>)); 215 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>)); 216 } 217 218 # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 219 //========================================================================== 220 //= Move semantics 221 //========================================================================== 222 223 /** Move constructor */ interval_base_map(interval_base_map && src)224 interval_base_map(interval_base_map&& src): _map(boost::move(src._map)) 225 { 226 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>)); 227 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>)); 228 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>)); 229 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>)); 230 } 231 232 /** Move assignment operator */ operator =(interval_base_map src)233 interval_base_map& operator = (interval_base_map src) 234 { //call by value sice 'src' is a "sink value" 235 this->_map = boost::move(src._map); 236 return *this; 237 } 238 239 //========================================================================== 240 # else 241 242 /** Copy assignment operator */ operator =(const interval_base_map & src)243 interval_base_map& operator = (const interval_base_map& src) 244 { 245 this->_map = src._map; 246 return *this; 247 } 248 249 # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 250 251 /** swap the content of containers */ swap(interval_base_map & object)252 void swap(interval_base_map& object) { _map.swap(object._map); } 253 254 //========================================================================== 255 //= Containedness 256 //========================================================================== 257 /** clear the map */ clear()258 void clear() { icl::clear(*that()); } 259 260 /** is the map empty? */ empty() const261 bool empty()const { return icl::is_empty(*that()); } 262 263 //========================================================================== 264 //= Size 265 //========================================================================== 266 /** An interval map's size is it's cardinality */ size() const267 size_type size()const 268 { 269 return icl::cardinality(*that()); 270 } 271 272 /** Size of the iteration over this container */ iterative_size() const273 std::size_t iterative_size()const 274 { 275 return _map.size(); 276 } 277 278 //========================================================================== 279 //= Selection 280 //========================================================================== 281 282 /** Find the interval value pair, that contains \c key */ find(const domain_type & key_value) const283 const_iterator find(const domain_type& key_value)const 284 { 285 return icl::find(*this, key_value); 286 } 287 288 /** Find the first interval value pair, that collides with interval 289 \c key_interval */ find(const interval_type & key_interval) const290 const_iterator find(const interval_type& key_interval)const 291 { 292 return _map.find(key_interval); 293 } 294 295 /** Total select function. */ operator ()(const domain_type & key_value) const296 codomain_type operator()(const domain_type& key_value)const 297 { 298 const_iterator it_ = icl::find(*this, key_value); 299 return it_==end() ? identity_element<codomain_type>::value() 300 : (*it_).second; 301 } 302 303 //========================================================================== 304 //= Addition 305 //========================================================================== 306 307 /** Addition of a key value pair to the map */ add(const element_type & key_value_pair)308 SubType& add(const element_type& key_value_pair) 309 { 310 return icl::add(*that(), key_value_pair); 311 } 312 313 /** Addition of an interval value pair to the map. */ add(const segment_type & interval_value_pair)314 SubType& add(const segment_type& interval_value_pair) 315 { 316 this->template _add<codomain_combine>(interval_value_pair); 317 return *that(); 318 } 319 320 /** Addition of an interval value pair \c interval_value_pair to the map. 321 Iterator \c prior_ is a hint to the position \c interval_value_pair can be 322 inserted after. */ add(iterator prior_,const segment_type & interval_value_pair)323 iterator add(iterator prior_, const segment_type& interval_value_pair) 324 { 325 return this->template _add<codomain_combine>(prior_, interval_value_pair); 326 } 327 328 //========================================================================== 329 //= Subtraction 330 //========================================================================== 331 /** Subtraction of a key value pair from the map */ subtract(const element_type & key_value_pair)332 SubType& subtract(const element_type& key_value_pair) 333 { 334 return icl::subtract(*that(), key_value_pair); 335 } 336 337 /** Subtraction of an interval value pair from the map. */ subtract(const segment_type & interval_value_pair)338 SubType& subtract(const segment_type& interval_value_pair) 339 { 340 on_invertible<type, is_total_invertible> 341 ::subtract(*that(), interval_value_pair); 342 return *that(); 343 } 344 345 //========================================================================== 346 //= Insertion 347 //========================================================================== 348 /** Insertion of a \c key_value_pair into the map. */ insert(const element_type & key_value_pair)349 SubType& insert(const element_type& key_value_pair) 350 { 351 return icl::insert(*that(), key_value_pair); 352 } 353 354 /** Insertion of an \c interval_value_pair into the map. */ insert(const segment_type & interval_value_pair)355 SubType& insert(const segment_type& interval_value_pair) 356 { 357 _insert(interval_value_pair); 358 return *that(); 359 } 360 361 /** Insertion of an \c interval_value_pair into the map. Iterator \c prior_. 362 serves as a hint to insert after the element \c prior point to. */ insert(iterator prior,const segment_type & interval_value_pair)363 iterator insert(iterator prior, const segment_type& interval_value_pair) 364 { 365 return _insert(prior, interval_value_pair); 366 } 367 368 /** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */ set(const element_type & key_value_pair)369 SubType& set(const element_type& key_value_pair) 370 { 371 return icl::set_at(*that(), key_value_pair); 372 } 373 374 /** With <tt>interval_value_pair = (I,v)</tt> set value \c v 375 for all keys in interval \c I in the map. */ set(const segment_type & interval_value_pair)376 SubType& set(const segment_type& interval_value_pair) 377 { 378 return icl::set_at(*that(), interval_value_pair); 379 } 380 381 //========================================================================== 382 //= Erasure 383 //========================================================================== 384 /** Erase a \c key_value_pair from the map. */ erase(const element_type & key_value_pair)385 SubType& erase(const element_type& key_value_pair) 386 { 387 icl::erase(*that(), key_value_pair); 388 return *that(); 389 } 390 391 /** Erase an \c interval_value_pair from the map. */ 392 SubType& erase(const segment_type& interval_value_pair); 393 394 /** Erase a key value pair for \c key. */ erase(const domain_type & key)395 SubType& erase(const domain_type& key) 396 { 397 return icl::erase(*that(), key); 398 } 399 400 /** Erase all value pairs within the range of the 401 interval <tt>inter_val</tt> from the map. */ 402 SubType& erase(const interval_type& inter_val); 403 404 405 /** Erase all value pairs within the range of the interval that iterator 406 \c position points to. */ erase(iterator position)407 void erase(iterator position){ this->_map.erase(position); } 408 409 /** Erase all value pairs for a range of iterators <tt>[first,past)</tt>. */ erase(iterator first,iterator past)410 void erase(iterator first, iterator past){ this->_map.erase(first, past); } 411 412 //========================================================================== 413 //= Intersection 414 //========================================================================== 415 /** The intersection of \c interval_value_pair and \c *this map is added to \c section. */ add_intersection(SubType & section,const segment_type & interval_value_pair) const416 void add_intersection(SubType& section, const segment_type& interval_value_pair)const 417 { 418 on_definedness<SubType, Traits::is_total> 419 ::add_intersection(section, *that(), interval_value_pair); 420 } 421 422 //========================================================================== 423 //= Symmetric difference 424 //========================================================================== 425 /** If \c *this map contains \c key_value_pair it is erased, otherwise it is added. */ flip(const element_type & key_value_pair)426 SubType& flip(const element_type& key_value_pair) 427 { 428 return icl::flip(*that(), key_value_pair); 429 } 430 431 /** If \c *this map contains \c interval_value_pair it is erased, otherwise it is added. */ flip(const segment_type & interval_value_pair)432 SubType& flip(const segment_type& interval_value_pair) 433 { 434 on_total_absorbable<SubType, Traits::is_total, Traits::absorbs_identities> 435 ::flip(*that(), interval_value_pair); 436 return *that(); 437 } 438 439 //========================================================================== 440 //= Iterator related 441 //========================================================================== 442 lower_bound(const key_type & interval)443 iterator lower_bound(const key_type& interval) 444 { return _map.lower_bound(interval); } 445 upper_bound(const key_type & interval)446 iterator upper_bound(const key_type& interval) 447 { return _map.upper_bound(interval); } 448 lower_bound(const key_type & interval) const449 const_iterator lower_bound(const key_type& interval)const 450 { return _map.lower_bound(interval); } 451 upper_bound(const key_type & interval) const452 const_iterator upper_bound(const key_type& interval)const 453 { return _map.upper_bound(interval); } 454 equal_range(const key_type & interval)455 std::pair<iterator,iterator> equal_range(const key_type& interval) 456 { 457 return std::pair<iterator,iterator> 458 (lower_bound(interval), upper_bound(interval)); 459 } 460 461 std::pair<const_iterator,const_iterator> equal_range(const key_type & interval) const462 equal_range(const key_type& interval)const 463 { 464 return std::pair<const_iterator,const_iterator> 465 (lower_bound(interval), upper_bound(interval)); 466 } 467 begin()468 iterator begin() { return _map.begin(); } end()469 iterator end() { return _map.end(); } begin() const470 const_iterator begin()const { return _map.begin(); } end() const471 const_iterator end()const { return _map.end(); } rbegin()472 reverse_iterator rbegin() { return _map.rbegin(); } rend()473 reverse_iterator rend() { return _map.rend(); } rbegin() const474 const_reverse_iterator rbegin()const { return _map.rbegin(); } rend() const475 const_reverse_iterator rend()const { return _map.rend(); } 476 477 private: 478 template<class Combiner> 479 iterator _add(const segment_type& interval_value_pair); 480 481 template<class Combiner> 482 iterator _add(iterator prior_, const segment_type& interval_value_pair); 483 484 template<class Combiner> 485 void _subtract(const segment_type& interval_value_pair); 486 487 iterator _insert(const segment_type& interval_value_pair); 488 iterator _insert(iterator prior_, const segment_type& interval_value_pair); 489 490 private: 491 template<class Combiner> 492 void add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_); 493 494 template<class Combiner> 495 void add_main(interval_type& inter_val, const CodomainT& co_val, 496 iterator& it_, const iterator& last_); 497 498 template<class Combiner> 499 void add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_); 500 501 void add_front(const interval_type& inter_val, iterator& first_); 502 503 private: 504 void subtract_front(const interval_type& inter_val, iterator& first_); 505 506 template<class Combiner> 507 void subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_); 508 509 template<class Combiner> 510 void subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_); 511 512 private: 513 void insert_main(const interval_type&, const CodomainT&, iterator&, const iterator&); 514 void erase_rest ( interval_type&, const CodomainT&, iterator&, const iterator&); 515 516 template<class FragmentT> total_add_intersection(SubType & section,const FragmentT & fragment) const517 void total_add_intersection(SubType& section, const FragmentT& fragment)const 518 { 519 section += *that(); 520 section.add(fragment); 521 } 522 partial_add_intersection(SubType & section,const segment_type & operand) const523 void partial_add_intersection(SubType& section, const segment_type& operand)const 524 { 525 interval_type inter_val = operand.first; 526 if(icl::is_empty(inter_val)) 527 return; 528 529 std::pair<const_iterator, const_iterator> exterior = equal_range(inter_val); 530 if(exterior.first == exterior.second) 531 return; 532 533 for(const_iterator it_=exterior.first; it_ != exterior.second; it_++) 534 { 535 interval_type common_interval = (*it_).first & inter_val; 536 if(!icl::is_empty(common_interval)) 537 { 538 section.template _add<codomain_combine> (value_type(common_interval, (*it_).second) ); 539 section.template _add<codomain_intersect>(value_type(common_interval, operand.second)); 540 } 541 } 542 } 543 partial_add_intersection(SubType & section,const element_type & operand) const544 void partial_add_intersection(SubType& section, const element_type& operand)const 545 { 546 partial_add_intersection(section, make_segment<type>(operand)); 547 } 548 549 550 protected: 551 552 template <class Combiner> gap_insert(iterator prior_,const interval_type & inter_val,const codomain_type & co_val)553 iterator gap_insert(iterator prior_, const interval_type& inter_val, 554 const codomain_type& co_val ) 555 { 556 // inter_val is not conained in this map. Insertion will be successful 557 BOOST_ASSERT(this->_map.find(inter_val) == this->_map.end()); 558 BOOST_ASSERT((!on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val))); 559 return this->_map.insert(prior_, value_type(inter_val, version<Combiner>()(co_val))); 560 } 561 562 template <class Combiner> 563 std::pair<iterator, bool> add_at(const iterator & prior_,const interval_type & inter_val,const codomain_type & co_val)564 add_at(const iterator& prior_, const interval_type& inter_val, 565 const codomain_type& co_val ) 566 { 567 // Never try to insert an identity element into an identity element absorber here: 568 BOOST_ASSERT((!(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val)))); 569 570 iterator inserted_ 571 = this->_map.insert(prior_, value_type(inter_val, Combiner::identity_element())); 572 573 if((*inserted_).first == inter_val && (*inserted_).second == Combiner::identity_element()) 574 { 575 Combiner()((*inserted_).second, co_val); 576 return std::pair<iterator,bool>(inserted_, true); 577 } 578 else 579 return std::pair<iterator,bool>(inserted_, false); 580 } 581 582 std::pair<iterator, bool> insert_at(const iterator & prior_,const interval_type & inter_val,const codomain_type & co_val)583 insert_at(const iterator& prior_, const interval_type& inter_val, 584 const codomain_type& co_val ) 585 { 586 iterator inserted_ 587 = this->_map.insert(prior_, value_type(inter_val, co_val)); 588 589 if(inserted_ == prior_) 590 return std::pair<iterator,bool>(inserted_, false); 591 else if((*inserted_).first == inter_val) 592 return std::pair<iterator,bool>(inserted_, true); 593 else 594 return std::pair<iterator,bool>(inserted_, false); 595 } 596 597 598 protected: that()599 sub_type* that() { return static_cast<sub_type*>(this); } that() const600 const sub_type* that()const { return static_cast<const sub_type*>(this); } 601 602 protected: 603 ImplMapT _map; 604 605 606 private: 607 //-------------------------------------------------------------------------- 608 template<class Type, bool is_total_invertible> 609 struct on_invertible; 610 611 template<class Type> 612 struct on_invertible<Type, true> 613 { 614 typedef typename Type::segment_type segment_type; 615 typedef typename Type::inverse_codomain_combine inverse_codomain_combine; 616 subtractboost::icl::interval_base_map::on_invertible617 static void subtract(Type& object, const segment_type& operand) 618 { object.template _add<inverse_codomain_combine>(operand); } 619 }; 620 621 template<class Type> 622 struct on_invertible<Type, false> 623 { 624 typedef typename Type::segment_type segment_type; 625 typedef typename Type::inverse_codomain_combine inverse_codomain_combine; 626 subtractboost::icl::interval_base_map::on_invertible627 static void subtract(Type& object, const segment_type& operand) 628 { object.template _subtract<inverse_codomain_combine>(operand); } 629 }; 630 631 friend struct on_invertible<type, true>; 632 friend struct on_invertible<type, false>; 633 //-------------------------------------------------------------------------- 634 635 //-------------------------------------------------------------------------- 636 template<class Type, bool is_total> 637 struct on_definedness; 638 639 template<class Type> 640 struct on_definedness<Type, true> 641 { add_intersectionboost::icl::interval_base_map::on_definedness642 static void add_intersection(Type& section, const Type& object, 643 const segment_type& operand) 644 { object.total_add_intersection(section, operand); } 645 }; 646 647 template<class Type> 648 struct on_definedness<Type, false> 649 { add_intersectionboost::icl::interval_base_map::on_definedness650 static void add_intersection(Type& section, const Type& object, 651 const segment_type& operand) 652 { object.partial_add_intersection(section, operand); } 653 }; 654 655 friend struct on_definedness<type, true>; 656 friend struct on_definedness<type, false>; 657 //-------------------------------------------------------------------------- 658 659 //-------------------------------------------------------------------------- 660 template<class Type, bool has_set_semantics> 661 struct on_codomain_model; 662 663 template<class Type> 664 struct on_codomain_model<Type, true> 665 { 666 typedef typename Type::interval_type interval_type; 667 typedef typename Type::codomain_type codomain_type; 668 typedef typename Type::segment_type segment_type; 669 typedef typename Type::codomain_combine codomain_combine; 670 typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect; 671 addboost::icl::interval_base_map::on_codomain_model672 static void add(Type& intersection, interval_type& common_interval, 673 const codomain_type& flip_value, const codomain_type& co_value) 674 { 675 codomain_type common_value = flip_value; 676 inverse_codomain_intersect()(common_value, co_value); 677 intersection.template 678 _add<codomain_combine>(segment_type(common_interval, common_value)); 679 } 680 }; 681 682 template<class Type> 683 struct on_codomain_model<Type, false> 684 { 685 typedef typename Type::interval_type interval_type; 686 typedef typename Type::codomain_type codomain_type; 687 typedef typename Type::segment_type segment_type; 688 typedef typename Type::codomain_combine codomain_combine; 689 addboost::icl::interval_base_map::on_codomain_model690 static void add(Type& intersection, interval_type& common_interval, 691 const codomain_type&, const codomain_type&) 692 { 693 intersection.template 694 _add<codomain_combine>(segment_type(common_interval, 695 identity_element<codomain_type>::value())); 696 } 697 }; 698 699 friend struct on_codomain_model<type, true>; 700 friend struct on_codomain_model<type, false>; 701 //-------------------------------------------------------------------------- 702 703 704 //-------------------------------------------------------------------------- 705 template<class Type, bool is_total, bool absorbs_identities> 706 struct on_total_absorbable; 707 708 template<class Type> 709 struct on_total_absorbable<Type, true, true> 710 { flipboost::icl::interval_base_map::on_total_absorbable711 static void flip(Type& object, const typename Type::segment_type&) 712 { icl::clear(object); } 713 }; 714 715 #ifdef BOOST_MSVC 716 #pragma warning(push) 717 #pragma warning(disable:4127) // conditional expression is constant 718 #endif 719 720 template<class Type> 721 struct on_total_absorbable<Type, true, false> 722 { 723 typedef typename Type::segment_type segment_type; 724 typedef typename Type::codomain_type codomain_type; 725 flipboost::icl::interval_base_map::on_total_absorbable726 static void flip(Type& object, const segment_type& operand) 727 { 728 object += operand; 729 ICL_FORALL(typename Type, it_, object) 730 (*it_).second = identity_element<codomain_type>::value(); 731 732 if(mpl::not_<is_interval_splitter<Type> >::value) 733 icl::join(object); 734 } 735 }; 736 737 #ifdef BOOST_MSVC 738 #pragma warning(pop) 739 #endif 740 741 template<class Type, bool absorbs_identities> 742 struct on_total_absorbable<Type, false, absorbs_identities> 743 { 744 typedef typename Type::segment_type segment_type; 745 typedef typename Type::codomain_type codomain_type; 746 typedef typename Type::interval_type interval_type; 747 typedef typename Type::value_type value_type; 748 typedef typename Type::const_iterator const_iterator; 749 typedef typename Type::set_type set_type; 750 typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect; 751 flipboost::icl::interval_base_map::on_total_absorbable752 static void flip(Type& object, const segment_type& interval_value_pair) 753 { 754 // That which is common shall be subtracted 755 // That which is not shall be added 756 // So interval_value_pair has to be 'complementary added' or flipped 757 interval_type span = interval_value_pair.first; 758 std::pair<const_iterator, const_iterator> exterior 759 = object.equal_range(span); 760 761 const_iterator first_ = exterior.first; 762 const_iterator end_ = exterior.second; 763 764 interval_type covered, left_over, common_interval; 765 const codomain_type& x_value = interval_value_pair.second; 766 const_iterator it_ = first_; 767 768 set_type eraser; 769 Type intersection; 770 771 while(it_ != end_ ) 772 { 773 const codomain_type& co_value = (*it_).second; 774 covered = (*it_++).first; 775 //[a ... : span 776 // [b ... : covered 777 //[a b) : left_over 778 left_over = right_subtract(span, covered); 779 780 //That which is common ... 781 common_interval = span & covered; 782 if(!icl::is_empty(common_interval)) 783 { 784 // ... shall be subtracted 785 icl::add(eraser, common_interval); 786 787 on_codomain_model<Type, has_set_semantics<codomain_type>::value> 788 ::add(intersection, common_interval, x_value, co_value); 789 } 790 791 icl::add(object, value_type(left_over, x_value)); //That which is not shall be added 792 // Because this is a collision free addition I don't have to distinguish codomain_types. 793 794 //... d) : span 795 //... c) : covered 796 // [c d) : span' 797 span = left_subtract(span, covered); 798 } 799 800 //If span is not empty here, it is not in the set so it shall be added 801 icl::add(object, value_type(span, x_value)); 802 803 //finally rewrite the common segments 804 icl::erase(object, eraser); 805 object += intersection; 806 } 807 }; 808 //-------------------------------------------------------------------------- 809 } ; 810 811 812 //============================================================================== 813 //= Addition detail 814 //============================================================================== 815 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 816 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> add_front(const interval_type & inter_val,iterator & first_)817 ::add_front(const interval_type& inter_val, iterator& first_) 818 { 819 // If the collision sequence has a left residual 'left_resid' it will 820 // be split, to provide a standardized start of algorithms: 821 // The addend interval 'inter_val' covers the beginning of the collision sequence. 822 823 // only for the first there can be a left_resid: a part of *first_ left of inter_val 824 interval_type left_resid = right_subtract((*first_).first, inter_val); 825 826 if(!icl::is_empty(left_resid)) 827 { // [------------ . . . 828 // [left_resid---first_ --- . . . 829 iterator prior_ = cyclic_prior(*this, first_); 830 const_cast<interval_type&>((*first_).first) 831 = left_subtract((*first_).first, left_resid); 832 //NOTE: Only splitting 833 this->_map.insert(prior_, segment_type(left_resid, (*first_).second)); 834 } 835 //POST: 836 // [----- inter_val ---- . . . 837 // ...[-- first_ --... 838 } 839 840 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 841 template<class Combiner> 842 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> add_segment(const interval_type & inter_val,const CodomainT & co_val,iterator & it_)843 ::add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_) 844 { 845 interval_type lead_gap = right_subtract(inter_val, (*it_).first); 846 if(!icl::is_empty(lead_gap)) 847 { 848 // [lead_gap--- . . . 849 // [-- it_ ... 850 iterator prior_ = it_==this->_map.begin()? it_ : prior(it_); 851 iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val); 852 that()->handle_inserted(prior_, inserted_); 853 } 854 855 // . . . --------- . . . addend interval 856 // [-- it_ --) has a common part with the first overval 857 Combiner()((*it_).second, co_val); 858 that()->template handle_left_combined<Combiner>(it_++); 859 } 860 861 862 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 863 template<class Combiner> 864 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> add_main(interval_type & inter_val,const CodomainT & co_val,iterator & it_,const iterator & last_)865 ::add_main(interval_type& inter_val, const CodomainT& co_val, 866 iterator& it_, const iterator& last_) 867 { 868 interval_type cur_interval; 869 while(it_!=last_) 870 { 871 cur_interval = (*it_).first ; 872 add_segment<Combiner>(inter_val, co_val, it_); 873 // shrink interval 874 inter_val = left_subtract(inter_val, cur_interval); 875 } 876 } 877 878 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 879 template<class Combiner> 880 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> add_rear(const interval_type & inter_val,const CodomainT & co_val,iterator & it_)881 ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_) 882 { 883 iterator prior_ = cyclic_prior(*that(), it_); 884 interval_type cur_itv = (*it_).first ; 885 886 interval_type lead_gap = right_subtract(inter_val, cur_itv); 887 if(!icl::is_empty(lead_gap)) 888 { // [lead_gap--- . . . 889 // [prior) [-- it_ ... 890 iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val); 891 that()->handle_inserted(prior_, inserted_); 892 } 893 894 interval_type end_gap = left_subtract(inter_val, cur_itv); 895 if(!icl::is_empty(end_gap)) 896 { 897 // [----------------end_gap) 898 // . . . -- it_ --) 899 Combiner()((*it_).second, co_val); 900 that()->template gap_insert_at<Combiner>(it_, prior_, end_gap, co_val); 901 } 902 else 903 { 904 // only for the last there can be a right_resid: a part of *it_ right of x 905 interval_type right_resid = left_subtract(cur_itv, inter_val); 906 907 if(icl::is_empty(right_resid)) 908 { 909 // [---------------) 910 // [-- it_ ---) 911 Combiner()((*it_).second, co_val); 912 that()->template handle_preceeded_combined<Combiner>(prior_, it_); 913 } 914 else 915 { 916 // [--------------) 917 // [-- it_ --right_resid) 918 const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid); 919 920 //NOTE: This is NOT an insertion that has to take care for correct application of 921 // the Combiner functor. It only reestablished that state after splitting the 922 // 'it_' interval value pair. Using _map_insert<Combiner> does not work here. 923 iterator insertion_ = this->_map.insert(it_, value_type(right_resid, (*it_).second)); 924 that()->handle_reinserted(insertion_); 925 926 Combiner()((*it_).second, co_val); 927 that()->template handle_preceeded_combined<Combiner>(insertion_, it_); 928 } 929 } 930 } 931 932 933 //============================================================================== 934 //= Addition 935 //============================================================================== 936 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 937 template<class Combiner> 938 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 939 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _add(const segment_type & addend)940 ::_add(const segment_type& addend) 941 { 942 typedef typename on_absorbtion<type,Combiner, 943 absorbs_identities<type>::value>::type on_absorbtion_; 944 945 const interval_type& inter_val = addend.first; 946 if(icl::is_empty(inter_val)) 947 return this->_map.end(); 948 949 const codomain_type& co_val = addend.second; 950 if(on_absorbtion_::is_absorbable(co_val)) 951 return this->_map.end(); 952 953 std::pair<iterator,bool> insertion 954 = this->_map.insert(value_type(inter_val, version<Combiner>()(co_val))); 955 956 if(insertion.second) 957 return that()->handle_inserted(insertion.first); 958 else 959 { 960 // Detect the first and the end iterator of the collision sequence 961 iterator first_ = this->_map.lower_bound(inter_val), 962 last_ = prior(this->_map.upper_bound(inter_val)); 963 //assert(end_ == this->_map.upper_bound(inter_val)); 964 iterator it_ = first_; 965 interval_type rest_interval = inter_val; 966 967 add_front (rest_interval, it_ ); 968 add_main<Combiner>(rest_interval, co_val, it_, last_); 969 add_rear<Combiner>(rest_interval, co_val, it_ ); 970 return it_; 971 } 972 } 973 974 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 975 template<class Combiner> 976 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 977 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _add(iterator prior_,const segment_type & addend)978 ::_add(iterator prior_, const segment_type& addend) 979 { 980 typedef typename on_absorbtion<type,Combiner, 981 absorbs_identities<type>::value>::type on_absorbtion_; 982 983 const interval_type& inter_val = addend.first; 984 if(icl::is_empty(inter_val)) 985 return prior_; 986 987 const codomain_type& co_val = addend.second; 988 if(on_absorbtion_::is_absorbable(co_val)) 989 return prior_; 990 991 std::pair<iterator,bool> insertion 992 = add_at<Combiner>(prior_, inter_val, co_val); 993 994 if(insertion.second) 995 return that()->handle_inserted(insertion.first); 996 else 997 { 998 // Detect the first and the end iterator of the collision sequence 999 std::pair<iterator,iterator> overlap = equal_range(inter_val); 1000 iterator it_ = overlap.first, 1001 last_ = prior(overlap.second); 1002 interval_type rest_interval = inter_val; 1003 1004 add_front (rest_interval, it_ ); 1005 add_main<Combiner>(rest_interval, co_val, it_, last_); 1006 add_rear<Combiner>(rest_interval, co_val, it_ ); 1007 return it_; 1008 } 1009 } 1010 1011 //============================================================================== 1012 //= Subtraction detail 1013 //============================================================================== 1014 1015 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1016 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> subtract_front(const interval_type & inter_val,iterator & it_)1017 ::subtract_front(const interval_type& inter_val, iterator& it_) 1018 { 1019 interval_type left_resid = right_subtract((*it_).first, inter_val); 1020 1021 if(!icl::is_empty(left_resid)) // [--- inter_val ---) 1022 { //[prior_) [left_resid)[--- it_ . . . 1023 iterator prior_ = cyclic_prior(*this, it_); 1024 const_cast<interval_type&>((*it_).first) = left_subtract((*it_).first, left_resid); 1025 this->_map.insert(prior_, value_type(left_resid, (*it_).second)); 1026 // The segemnt *it_ is split at inter_val.first(), so as an invariant 1027 // segment *it_ is always "under" inter_val and a left_resid is empty. 1028 } 1029 } 1030 1031 1032 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1033 template<class Combiner> 1034 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> subtract_main(const CodomainT & co_val,iterator & it_,const iterator & last_)1035 ::subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_) 1036 { 1037 while(it_ != last_) 1038 { 1039 Combiner()((*it_).second, co_val); 1040 that()->template handle_left_combined<Combiner>(it_++); 1041 } 1042 } 1043 1044 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1045 template<class Combiner> 1046 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> subtract_rear(interval_type & inter_val,const CodomainT & co_val,iterator & it_)1047 ::subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_) 1048 { 1049 interval_type right_resid = left_subtract((*it_).first, inter_val); 1050 1051 if(icl::is_empty(right_resid)) 1052 { 1053 Combiner()((*it_).second, co_val); 1054 that()->template handle_combined<Combiner>(it_); 1055 } 1056 else 1057 { 1058 const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid); 1059 iterator next_ = this->_map.insert(it_, value_type(right_resid, (*it_).second)); 1060 Combiner()((*it_).second, co_val); 1061 that()->template handle_succeeded_combined<Combiner>(it_, next_); 1062 } 1063 } 1064 1065 //============================================================================== 1066 //= Subtraction 1067 //============================================================================== 1068 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1069 template<class Combiner> 1070 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _subtract(const segment_type & minuend)1071 ::_subtract(const segment_type& minuend) 1072 { 1073 interval_type inter_val = minuend.first; 1074 if(icl::is_empty(inter_val)) 1075 return; 1076 1077 const codomain_type& co_val = minuend.second; 1078 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val)) 1079 return; 1080 1081 std::pair<iterator, iterator> exterior = equal_range(inter_val); 1082 if(exterior.first == exterior.second) 1083 return; 1084 1085 iterator last_ = prior(exterior.second); 1086 iterator it_ = exterior.first; 1087 subtract_front (inter_val, it_ ); 1088 subtract_main <Combiner>( co_val, it_, last_); 1089 subtract_rear <Combiner>(inter_val, co_val, it_ ); 1090 } 1091 1092 //============================================================================== 1093 //= Insertion 1094 //============================================================================== 1095 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1096 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> insert_main(const interval_type & inter_val,const CodomainT & co_val,iterator & it_,const iterator & last_)1097 ::insert_main(const interval_type& inter_val, const CodomainT& co_val, 1098 iterator& it_, const iterator& last_) 1099 { 1100 iterator end_ = boost::next(last_); 1101 iterator prior_ = cyclic_prior(*this,it_), inserted_; 1102 interval_type rest_interval = inter_val, left_gap, cur_itv; 1103 interval_type last_interval = last_ ->first; 1104 1105 while(it_ != end_ ) 1106 { 1107 cur_itv = (*it_).first ; 1108 left_gap = right_subtract(rest_interval, cur_itv); 1109 1110 if(!icl::is_empty(left_gap)) 1111 { 1112 inserted_ = this->_map.insert(prior_, value_type(left_gap, co_val)); 1113 it_ = that()->handle_inserted(inserted_); 1114 } 1115 1116 // shrink interval 1117 rest_interval = left_subtract(rest_interval, cur_itv); 1118 prior_ = it_; 1119 ++it_; 1120 } 1121 1122 //insert_rear(rest_interval, co_val, last_): 1123 interval_type end_gap = left_subtract(rest_interval, last_interval); 1124 if(!icl::is_empty(end_gap)) 1125 { 1126 inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val)); 1127 it_ = that()->handle_inserted(inserted_); 1128 } 1129 else 1130 it_ = prior_; 1131 } 1132 1133 1134 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1135 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 1136 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _insert(const segment_type & addend)1137 ::_insert(const segment_type& addend) 1138 { 1139 interval_type inter_val = addend.first; 1140 if(icl::is_empty(inter_val)) 1141 return this->_map.end(); 1142 1143 const codomain_type& co_val = addend.second; 1144 if(on_codomain_absorbtion::is_absorbable(co_val)) 1145 return this->_map.end(); 1146 1147 std::pair<iterator,bool> insertion = this->_map.insert(addend); 1148 1149 if(insertion.second) 1150 return that()->handle_inserted(insertion.first); 1151 else 1152 { 1153 // Detect the first and the end iterator of the collision sequence 1154 iterator first_ = this->_map.lower_bound(inter_val), 1155 last_ = prior(this->_map.upper_bound(inter_val)); 1156 //assert((++last_) == this->_map.upper_bound(inter_val)); 1157 iterator it_ = first_; 1158 insert_main(inter_val, co_val, it_, last_); 1159 return it_; 1160 } 1161 } 1162 1163 1164 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1165 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 1166 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _insert(iterator prior_,const segment_type & addend)1167 ::_insert(iterator prior_, const segment_type& addend) 1168 { 1169 interval_type inter_val = addend.first; 1170 if(icl::is_empty(inter_val)) 1171 return prior_; 1172 1173 const codomain_type& co_val = addend.second; 1174 if(on_codomain_absorbtion::is_absorbable(co_val)) 1175 return prior_; 1176 1177 std::pair<iterator,bool> insertion = insert_at(prior_, inter_val, co_val); 1178 1179 if(insertion.second) 1180 return that()->handle_inserted(insertion.first); 1181 { 1182 // Detect the first and the end iterator of the collision sequence 1183 std::pair<iterator,iterator> overlap = equal_range(inter_val); 1184 iterator it_ = overlap.first, 1185 last_ = prior(overlap.second); 1186 insert_main(inter_val, co_val, it_, last_); 1187 return it_; 1188 } 1189 } 1190 1191 //============================================================================== 1192 //= Erasure segment_type 1193 //============================================================================== 1194 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1195 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> erase_rest(interval_type & inter_val,const CodomainT & co_val,iterator & it_,const iterator & last_)1196 ::erase_rest(interval_type& inter_val, const CodomainT& co_val, 1197 iterator& it_, const iterator& last_) 1198 { 1199 // For all intervals within loop: (*it_).first are contained_in inter_val 1200 while(it_ != last_) 1201 if((*it_).second == co_val) 1202 this->_map.erase(it_++); 1203 else it_++; 1204 1205 //erase_rear: 1206 if((*it_).second == co_val) 1207 { 1208 interval_type right_resid = left_subtract((*it_).first, inter_val); 1209 if(icl::is_empty(right_resid)) 1210 this->_map.erase(it_); 1211 else 1212 const_cast<interval_type&>((*it_).first) = right_resid; 1213 } 1214 } 1215 1216 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1217 inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> erase(const segment_type & minuend)1218 ::erase(const segment_type& minuend) 1219 { 1220 interval_type inter_val = minuend.first; 1221 if(icl::is_empty(inter_val)) 1222 return *that(); 1223 1224 const codomain_type& co_val = minuend.second; 1225 if(on_codomain_absorbtion::is_absorbable(co_val)) 1226 return *that(); 1227 1228 std::pair<iterator,iterator> exterior = equal_range(inter_val); 1229 if(exterior.first == exterior.second) 1230 return *that(); 1231 1232 iterator first_ = exterior.first, end_ = exterior.second, 1233 last_ = cyclic_prior(*this, end_); 1234 iterator second_= first_; ++second_; 1235 1236 if(first_ == last_) 1237 { // [----inter_val----) 1238 // .....first_==last_..... 1239 // only for the last there can be a right_resid: a part of *it_ right of minuend 1240 interval_type right_resid = left_subtract((*first_).first, inter_val); 1241 1242 if((*first_).second == co_val) 1243 { 1244 interval_type left_resid = right_subtract((*first_).first, inter_val); 1245 if(!icl::is_empty(left_resid)) // [----inter_val----) 1246 { // [left_resid)..first_==last_...... 1247 const_cast<interval_type&>((*first_).first) = left_resid; 1248 if(!icl::is_empty(right_resid)) 1249 this->_map.insert(first_, value_type(right_resid, co_val)); 1250 } 1251 else if(!icl::is_empty(right_resid)) 1252 const_cast<interval_type&>((*first_).first) = right_resid; 1253 else 1254 this->_map.erase(first_); 1255 } 1256 } 1257 else 1258 { 1259 // first AND NOT last 1260 if((*first_).second == co_val) 1261 { 1262 interval_type left_resid = right_subtract((*first_).first, inter_val); 1263 if(icl::is_empty(left_resid)) 1264 this->_map.erase(first_); 1265 else 1266 const_cast<interval_type&>((*first_).first) = left_resid; 1267 } 1268 1269 erase_rest(inter_val, co_val, second_, last_); 1270 } 1271 1272 return *that(); 1273 } 1274 1275 //============================================================================== 1276 //= Erasure key_type 1277 //============================================================================== 1278 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 1279 inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> erase(const interval_type & minuend)1280 ::erase(const interval_type& minuend) 1281 { 1282 if(icl::is_empty(minuend)) 1283 return *that(); 1284 1285 std::pair<iterator, iterator> exterior = equal_range(minuend); 1286 if(exterior.first == exterior.second) 1287 return *that(); 1288 1289 iterator first_ = exterior.first, 1290 end_ = exterior.second, 1291 last_ = prior(end_); 1292 1293 interval_type left_resid = right_subtract((*first_).first, minuend); 1294 interval_type right_resid = left_subtract(last_ ->first, minuend); 1295 1296 if(first_ == last_ ) 1297 if(!icl::is_empty(left_resid)) 1298 { 1299 const_cast<interval_type&>((*first_).first) = left_resid; 1300 if(!icl::is_empty(right_resid)) 1301 this->_map.insert(first_, value_type(right_resid, (*first_).second)); 1302 } 1303 else if(!icl::is_empty(right_resid)) 1304 const_cast<interval_type&>((*first_).first) = left_subtract((*first_).first, minuend); 1305 else 1306 this->_map.erase(first_); 1307 else 1308 { // [-------- minuend ---------) 1309 // [left_resid fst) . . . . [lst right_resid) 1310 iterator second_= first_; ++second_; 1311 1312 iterator start_ = icl::is_empty(left_resid)? first_: second_; 1313 iterator stop_ = icl::is_empty(right_resid)? end_ : last_ ; 1314 this->_map.erase(start_, stop_); //erase [start_, stop_) 1315 1316 if(!icl::is_empty(left_resid)) 1317 const_cast<interval_type&>((*first_).first) = left_resid; 1318 1319 if(!icl::is_empty(right_resid)) 1320 const_cast<interval_type&>(last_ ->first) = right_resid; 1321 } 1322 1323 return *that(); 1324 } 1325 1326 //----------------------------------------------------------------------------- 1327 // type traits 1328 //----------------------------------------------------------------------------- 1329 template 1330 < 1331 class SubType, 1332 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1333 > 1334 struct is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1335 { 1336 typedef is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1337 BOOST_STATIC_CONSTANT(bool, value = true); 1338 }; 1339 1340 template 1341 < 1342 class SubType, 1343 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1344 > 1345 struct has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1346 { 1347 typedef has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1348 BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value)); 1349 }; 1350 1351 template 1352 < 1353 class SubType, 1354 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1355 > 1356 struct is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1357 { 1358 typedef is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1359 BOOST_STATIC_CONSTANT(bool, value = true); 1360 }; 1361 1362 template 1363 < 1364 class SubType, 1365 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1366 > 1367 struct absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1368 { 1369 typedef absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1370 BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities)); 1371 }; 1372 1373 template 1374 < 1375 class SubType, 1376 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1377 > 1378 struct is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1379 { 1380 typedef is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1381 BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total)); 1382 }; 1383 1384 1385 1386 }} // namespace icl boost 1387 1388 #endif 1389 1390 1391