1 /*-----------------------------------------------------------------------------+ 2 Copyright (c) 2007-2010: 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 //= Construct, copy, destruct 198 //========================================================================== 199 /** Default constructor for the empty object */ interval_base_map()200 interval_base_map() 201 { 202 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>)); 203 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>)); 204 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>)); 205 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>)); 206 } 207 208 /** Copy constructor */ interval_base_map(const interval_base_map & src)209 interval_base_map(const interval_base_map& src): _map(src._map) 210 { 211 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>)); 212 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>)); 213 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>)); 214 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>)); 215 } 216 217 /** Assignment operator */ operator =(const interval_base_map & src)218 interval_base_map& operator = (const interval_base_map& src) 219 { 220 this->_map = src._map; 221 return *this; 222 } 223 224 /** swap the content of containers */ swap(interval_base_map & object)225 void swap(interval_base_map& object) { _map.swap(object._map); } 226 227 //========================================================================== 228 //= Containedness 229 //========================================================================== 230 /** clear the map */ clear()231 void clear() { icl::clear(*that()); } 232 233 /** is the map empty? */ empty() const234 bool empty()const { return icl::is_empty(*that()); } 235 236 //========================================================================== 237 //= Size 238 //========================================================================== 239 /** An interval map's size is it's cardinality */ size() const240 size_type size()const 241 { 242 return icl::cardinality(*that()); 243 } 244 245 /** Size of the iteration over this container */ iterative_size() const246 std::size_t iterative_size()const 247 { 248 return _map.size(); 249 } 250 251 //========================================================================== 252 //= Selection 253 //========================================================================== 254 255 /** Find the interval value pair, that contains \c key */ find(const domain_type & key_value) const256 const_iterator find(const domain_type& key_value)const 257 { 258 return icl::find(*this, key_value); 259 } 260 261 /** Find the first interval value pair, that collides with interval 262 \c key_interval */ find(const interval_type & key_interval) const263 const_iterator find(const interval_type& key_interval)const 264 { 265 return _map.find(key_interval); 266 } 267 268 /** Total select function. */ operator ()(const domain_type & key_value) const269 codomain_type operator()(const domain_type& key_value)const 270 { 271 const_iterator it_ = icl::find(*this, key_value); 272 return it_==end() ? identity_element<codomain_type>::value() 273 : (*it_).second; 274 } 275 276 //========================================================================== 277 //= Addition 278 //========================================================================== 279 280 /** Addition of a key value pair to the map */ add(const element_type & key_value_pair)281 SubType& add(const element_type& key_value_pair) 282 { 283 return icl::add(*that(), key_value_pair); 284 } 285 286 /** Addition of an interval value pair to the map. */ add(const segment_type & interval_value_pair)287 SubType& add(const segment_type& interval_value_pair) 288 { 289 this->template _add<codomain_combine>(interval_value_pair); 290 return *that(); 291 } 292 293 /** Addition of an interval value pair \c interval_value_pair to the map. 294 Iterator \c prior_ is a hint to the position \c interval_value_pair can be 295 inserted after. */ add(iterator prior_,const segment_type & interval_value_pair)296 iterator add(iterator prior_, const segment_type& interval_value_pair) 297 { 298 return this->template _add<codomain_combine>(prior_, interval_value_pair); 299 } 300 301 //========================================================================== 302 //= Subtraction 303 //========================================================================== 304 /** Subtraction of a key value pair from the map */ subtract(const element_type & key_value_pair)305 SubType& subtract(const element_type& key_value_pair) 306 { 307 return icl::subtract(*that(), key_value_pair); 308 } 309 310 /** Subtraction of an interval value pair from the map. */ subtract(const segment_type & interval_value_pair)311 SubType& subtract(const segment_type& interval_value_pair) 312 { 313 on_invertible<type, is_total_invertible> 314 ::subtract(*that(), interval_value_pair); 315 return *that(); 316 } 317 318 //========================================================================== 319 //= Insertion 320 //========================================================================== 321 /** Insertion of a \c key_value_pair into the map. */ insert(const element_type & key_value_pair)322 SubType& insert(const element_type& key_value_pair) 323 { 324 return icl::insert(*that(), key_value_pair); 325 } 326 327 /** Insertion of an \c interval_value_pair into the map. */ insert(const segment_type & interval_value_pair)328 SubType& insert(const segment_type& interval_value_pair) 329 { 330 _insert(interval_value_pair); 331 return *that(); 332 } 333 334 /** Insertion of an \c interval_value_pair into the map. Iterator \c prior_. 335 serves as a hint to insert after the element \c prior point to. */ insert(iterator prior,const segment_type & interval_value_pair)336 iterator insert(iterator prior, const segment_type& interval_value_pair) 337 { 338 return _insert(prior, interval_value_pair); 339 } 340 341 /** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */ set(const element_type & key_value_pair)342 SubType& set(const element_type& key_value_pair) 343 { 344 return icl::set_at(*that(), key_value_pair); 345 } 346 347 /** With <tt>interval_value_pair = (I,v)</tt> set value \c v 348 for all keys in interval \c I in the map. */ set(const segment_type & interval_value_pair)349 SubType& set(const segment_type& interval_value_pair) 350 { 351 return icl::set_at(*that(), interval_value_pair); 352 } 353 354 //========================================================================== 355 //= Erasure 356 //========================================================================== 357 /** Erase a \c key_value_pair from the map. */ erase(const element_type & key_value_pair)358 SubType& erase(const element_type& key_value_pair) 359 { 360 icl::erase(*that(), key_value_pair); 361 return *that(); 362 } 363 364 /** Erase an \c interval_value_pair from the map. */ 365 SubType& erase(const segment_type& interval_value_pair); 366 367 /** Erase a key value pair for \c key. */ erase(const domain_type & key)368 SubType& erase(const domain_type& key) 369 { 370 return icl::erase(*that(), key); 371 } 372 373 /** Erase all value pairs within the range of the 374 interval <tt>inter_val</tt> from the map. */ 375 SubType& erase(const interval_type& inter_val); 376 377 378 /** Erase all value pairs within the range of the interval that iterator 379 \c position points to. */ erase(iterator position)380 void erase(iterator position){ this->_map.erase(position); } 381 382 /** Erase all value pairs for a range of iterators <tt>[first,past)</tt>. */ erase(iterator first,iterator past)383 void erase(iterator first, iterator past){ this->_map.erase(first, past); } 384 385 //========================================================================== 386 //= Intersection 387 //========================================================================== 388 /** 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) const389 void add_intersection(SubType& section, const segment_type& interval_value_pair)const 390 { 391 on_definedness<SubType, Traits::is_total> 392 ::add_intersection(section, *that(), interval_value_pair); 393 } 394 395 //========================================================================== 396 //= Symmetric difference 397 //========================================================================== 398 /** If \c *this map contains \c key_value_pair it is erased, otherwise it is added. */ flip(const element_type & key_value_pair)399 SubType& flip(const element_type& key_value_pair) 400 { 401 return icl::flip(*that(), key_value_pair); 402 } 403 404 /** If \c *this map contains \c interval_value_pair it is erased, otherwise it is added. */ flip(const segment_type & interval_value_pair)405 SubType& flip(const segment_type& interval_value_pair) 406 { 407 on_total_absorbable<SubType, Traits::is_total, Traits::absorbs_identities> 408 ::flip(*that(), interval_value_pair); 409 return *that(); 410 } 411 412 //========================================================================== 413 //= Iterator related 414 //========================================================================== 415 lower_bound(const key_type & interval)416 iterator lower_bound(const key_type& interval) 417 { return _map.lower_bound(interval); } 418 upper_bound(const key_type & interval)419 iterator upper_bound(const key_type& interval) 420 { return _map.upper_bound(interval); } 421 lower_bound(const key_type & interval) const422 const_iterator lower_bound(const key_type& interval)const 423 { return _map.lower_bound(interval); } 424 upper_bound(const key_type & interval) const425 const_iterator upper_bound(const key_type& interval)const 426 { return _map.upper_bound(interval); } 427 equal_range(const key_type & interval)428 std::pair<iterator,iterator> equal_range(const key_type& interval) 429 { 430 return std::pair<iterator,iterator> 431 (lower_bound(interval), upper_bound(interval)); 432 } 433 434 std::pair<const_iterator,const_iterator> equal_range(const key_type & interval) const435 equal_range(const key_type& interval)const 436 { 437 return std::pair<const_iterator,const_iterator> 438 (lower_bound(interval), upper_bound(interval)); 439 } 440 begin()441 iterator begin() { return _map.begin(); } end()442 iterator end() { return _map.end(); } begin() const443 const_iterator begin()const { return _map.begin(); } end() const444 const_iterator end()const { return _map.end(); } rbegin()445 reverse_iterator rbegin() { return _map.rbegin(); } rend()446 reverse_iterator rend() { return _map.rend(); } rbegin() const447 const_reverse_iterator rbegin()const { return _map.rbegin(); } rend() const448 const_reverse_iterator rend()const { return _map.rend(); } 449 450 private: 451 template<class Combiner> 452 iterator _add(const segment_type& interval_value_pair); 453 454 template<class Combiner> 455 iterator _add(iterator prior_, const segment_type& interval_value_pair); 456 457 template<class Combiner> 458 void _subtract(const segment_type& interval_value_pair); 459 460 iterator _insert(const segment_type& interval_value_pair); 461 iterator _insert(iterator prior_, const segment_type& interval_value_pair); 462 463 private: 464 template<class Combiner> 465 void add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_); 466 467 template<class Combiner> 468 void add_main(interval_type& inter_val, const CodomainT& co_val, 469 iterator& it_, const iterator& last_); 470 471 template<class Combiner> 472 void add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_); 473 474 void add_front(const interval_type& inter_val, iterator& first_); 475 476 private: 477 void subtract_front(const interval_type& inter_val, iterator& first_); 478 479 template<class Combiner> 480 void subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_); 481 482 template<class Combiner> 483 void subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_); 484 485 private: 486 void insert_main(const interval_type&, const CodomainT&, iterator&, const iterator&); 487 void erase_rest ( interval_type&, const CodomainT&, iterator&, const iterator&); 488 489 template<class FragmentT> total_add_intersection(SubType & section,const FragmentT & fragment) const490 void total_add_intersection(SubType& section, const FragmentT& fragment)const 491 { 492 section += *that(); 493 section.add(fragment); 494 } 495 partial_add_intersection(SubType & section,const segment_type & operand) const496 void partial_add_intersection(SubType& section, const segment_type& operand)const 497 { 498 interval_type inter_val = operand.first; 499 if(icl::is_empty(inter_val)) 500 return; 501 502 std::pair<const_iterator, const_iterator> exterior = equal_range(inter_val); 503 if(exterior.first == exterior.second) 504 return; 505 506 for(const_iterator it_=exterior.first; it_ != exterior.second; it_++) 507 { 508 interval_type common_interval = (*it_).first & inter_val; 509 if(!icl::is_empty(common_interval)) 510 { 511 section.template _add<codomain_combine> (value_type(common_interval, (*it_).second) ); 512 section.template _add<codomain_intersect>(value_type(common_interval, operand.second)); 513 } 514 } 515 } 516 partial_add_intersection(SubType & section,const element_type & operand) const517 void partial_add_intersection(SubType& section, const element_type& operand)const 518 { 519 partial_add_intersection(section, make_segment<type>(operand)); 520 } 521 522 523 protected: 524 525 template <class Combiner> gap_insert(iterator prior_,const interval_type & inter_val,const codomain_type & co_val)526 iterator gap_insert(iterator prior_, const interval_type& inter_val, 527 const codomain_type& co_val ) 528 { 529 // inter_val is not conained in this map. Insertion will be successful 530 BOOST_ASSERT(this->_map.find(inter_val) == this->_map.end()); 531 BOOST_ASSERT((!on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val))); 532 return this->_map.insert(prior_, value_type(inter_val, version<Combiner>()(co_val))); 533 } 534 535 template <class Combiner> 536 std::pair<iterator, bool> add_at(const iterator & prior_,const interval_type & inter_val,const codomain_type & co_val)537 add_at(const iterator& prior_, const interval_type& inter_val, 538 const codomain_type& co_val ) 539 { 540 // Never try to insert an identity element into an identity element absorber here: 541 BOOST_ASSERT((!(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val)))); 542 543 iterator inserted_ 544 = this->_map.insert(prior_, value_type(inter_val, Combiner::identity_element())); 545 546 if((*inserted_).first == inter_val && (*inserted_).second == Combiner::identity_element()) 547 { 548 Combiner()((*inserted_).second, co_val); 549 return std::pair<iterator,bool>(inserted_, true); 550 } 551 else 552 return std::pair<iterator,bool>(inserted_, false); 553 } 554 555 std::pair<iterator, bool> insert_at(const iterator & prior_,const interval_type & inter_val,const codomain_type & co_val)556 insert_at(const iterator& prior_, const interval_type& inter_val, 557 const codomain_type& co_val ) 558 { 559 iterator inserted_ 560 = this->_map.insert(prior_, value_type(inter_val, co_val)); 561 562 if(inserted_ == prior_) 563 return std::pair<iterator,bool>(inserted_, false); 564 else if((*inserted_).first == inter_val) 565 return std::pair<iterator,bool>(inserted_, true); 566 else 567 return std::pair<iterator,bool>(inserted_, false); 568 } 569 570 571 protected: that()572 sub_type* that() { return static_cast<sub_type*>(this); } that() const573 const sub_type* that()const { return static_cast<const sub_type*>(this); } 574 575 protected: 576 ImplMapT _map; 577 578 579 private: 580 //-------------------------------------------------------------------------- 581 template<class Type, bool is_total_invertible> 582 struct on_invertible; 583 584 template<class Type> 585 struct on_invertible<Type, true> 586 { 587 typedef typename Type::segment_type segment_type; 588 typedef typename Type::inverse_codomain_combine inverse_codomain_combine; 589 subtractboost::icl::interval_base_map::on_invertible590 static void subtract(Type& object, const segment_type& operand) 591 { object.template _add<inverse_codomain_combine>(operand); } 592 }; 593 594 template<class Type> 595 struct on_invertible<Type, false> 596 { 597 typedef typename Type::segment_type segment_type; 598 typedef typename Type::inverse_codomain_combine inverse_codomain_combine; 599 subtractboost::icl::interval_base_map::on_invertible600 static void subtract(Type& object, const segment_type& operand) 601 { object.template _subtract<inverse_codomain_combine>(operand); } 602 }; 603 604 friend struct on_invertible<type, true>; 605 friend struct on_invertible<type, false>; 606 //-------------------------------------------------------------------------- 607 608 //-------------------------------------------------------------------------- 609 template<class Type, bool is_total> 610 struct on_definedness; 611 612 template<class Type> 613 struct on_definedness<Type, true> 614 { add_intersectionboost::icl::interval_base_map::on_definedness615 static void add_intersection(Type& section, const Type& object, 616 const segment_type& operand) 617 { object.total_add_intersection(section, operand); } 618 }; 619 620 template<class Type> 621 struct on_definedness<Type, false> 622 { add_intersectionboost::icl::interval_base_map::on_definedness623 static void add_intersection(Type& section, const Type& object, 624 const segment_type& operand) 625 { object.partial_add_intersection(section, operand); } 626 }; 627 628 friend struct on_definedness<type, true>; 629 friend struct on_definedness<type, false>; 630 //-------------------------------------------------------------------------- 631 632 //-------------------------------------------------------------------------- 633 template<class Type, bool has_set_semantics> 634 struct on_codomain_model; 635 636 template<class Type> 637 struct on_codomain_model<Type, true> 638 { 639 typedef typename Type::interval_type interval_type; 640 typedef typename Type::codomain_type codomain_type; 641 typedef typename Type::segment_type segment_type; 642 typedef typename Type::codomain_combine codomain_combine; 643 typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect; 644 addboost::icl::interval_base_map::on_codomain_model645 static void add(Type& intersection, interval_type& common_interval, 646 const codomain_type& flip_value, const codomain_type& co_value) 647 { 648 codomain_type common_value = flip_value; 649 inverse_codomain_intersect()(common_value, co_value); 650 intersection.template 651 _add<codomain_combine>(segment_type(common_interval, common_value)); 652 } 653 }; 654 655 template<class Type> 656 struct on_codomain_model<Type, false> 657 { 658 typedef typename Type::interval_type interval_type; 659 typedef typename Type::codomain_type codomain_type; 660 typedef typename Type::segment_type segment_type; 661 typedef typename Type::codomain_combine codomain_combine; 662 addboost::icl::interval_base_map::on_codomain_model663 static void add(Type& intersection, interval_type& common_interval, 664 const codomain_type&, const codomain_type&) 665 { 666 intersection.template 667 _add<codomain_combine>(segment_type(common_interval, 668 identity_element<codomain_type>::value())); 669 } 670 }; 671 672 friend struct on_codomain_model<type, true>; 673 friend struct on_codomain_model<type, false>; 674 //-------------------------------------------------------------------------- 675 676 677 //-------------------------------------------------------------------------- 678 template<class Type, bool is_total, bool absorbs_identities> 679 struct on_total_absorbable; 680 681 template<class Type> 682 struct on_total_absorbable<Type, true, true> 683 { flipboost::icl::interval_base_map::on_total_absorbable684 static void flip(Type& object, const typename Type::segment_type&) 685 { icl::clear(object); } 686 }; 687 688 #ifdef BOOST_MSVC 689 #pragma warning(push) 690 #pragma warning(disable:4127) // conditional expression is constant 691 #endif 692 693 template<class Type> 694 struct on_total_absorbable<Type, true, false> 695 { 696 typedef typename Type::segment_type segment_type; 697 typedef typename Type::codomain_type codomain_type; 698 flipboost::icl::interval_base_map::on_total_absorbable699 static void flip(Type& object, const segment_type& operand) 700 { 701 object += operand; 702 ICL_FORALL(typename Type, it_, object) 703 (*it_).second = identity_element<codomain_type>::value(); 704 705 if(mpl::not_<is_interval_splitter<Type> >::value) 706 icl::join(object); 707 } 708 }; 709 710 #ifdef BOOST_MSVC 711 #pragma warning(pop) 712 #endif 713 714 template<class Type, bool absorbs_identities> 715 struct on_total_absorbable<Type, false, absorbs_identities> 716 { 717 typedef typename Type::segment_type segment_type; 718 typedef typename Type::codomain_type codomain_type; 719 typedef typename Type::interval_type interval_type; 720 typedef typename Type::value_type value_type; 721 typedef typename Type::const_iterator const_iterator; 722 typedef typename Type::set_type set_type; 723 typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect; 724 flipboost::icl::interval_base_map::on_total_absorbable725 static void flip(Type& object, const segment_type& interval_value_pair) 726 { 727 // That which is common shall be subtracted 728 // That which is not shall be added 729 // So interval_value_pair has to be 'complementary added' or flipped 730 interval_type span = interval_value_pair.first; 731 std::pair<const_iterator, const_iterator> exterior 732 = object.equal_range(span); 733 734 const_iterator first_ = exterior.first; 735 const_iterator end_ = exterior.second; 736 737 interval_type covered, left_over, common_interval; 738 const codomain_type& x_value = interval_value_pair.second; 739 const_iterator it_ = first_; 740 741 set_type eraser; 742 Type intersection; 743 744 while(it_ != end_ ) 745 { 746 const codomain_type& co_value = (*it_).second; 747 covered = (*it_++).first; 748 //[a ... : span 749 // [b ... : covered 750 //[a b) : left_over 751 left_over = right_subtract(span, covered); 752 753 //That which is common ... 754 common_interval = span & covered; 755 if(!icl::is_empty(common_interval)) 756 { 757 // ... shall be subtracted 758 icl::add(eraser, common_interval); 759 760 on_codomain_model<Type, has_set_semantics<codomain_type>::value> 761 ::add(intersection, common_interval, x_value, co_value); 762 } 763 764 icl::add(object, value_type(left_over, x_value)); //That which is not shall be added 765 // Because this is a collision free addition I don't have to distinguish codomain_types. 766 767 //... d) : span 768 //... c) : covered 769 // [c d) : span' 770 span = left_subtract(span, covered); 771 } 772 773 //If span is not empty here, it is not in the set so it shall be added 774 icl::add(object, value_type(span, x_value)); 775 776 //finally rewrite the common segments 777 icl::erase(object, eraser); 778 object += intersection; 779 } 780 }; 781 //-------------------------------------------------------------------------- 782 } ; 783 784 785 //============================================================================== 786 //= Addition detail 787 //============================================================================== 788 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> 789 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> add_front(const interval_type & inter_val,iterator & first_)790 ::add_front(const interval_type& inter_val, iterator& first_) 791 { 792 // If the collision sequence has a left residual 'left_resid' it will 793 // be split, to provide a standardized start of algorithms: 794 // The addend interval 'inter_val' covers the beginning of the collision sequence. 795 796 // only for the first there can be a left_resid: a part of *first_ left of inter_val 797 interval_type left_resid = right_subtract((*first_).first, inter_val); 798 799 if(!icl::is_empty(left_resid)) 800 { // [------------ . . . 801 // [left_resid---first_ --- . . . 802 iterator prior_ = cyclic_prior(*this, first_); 803 const_cast<interval_type&>((*first_).first) 804 = left_subtract((*first_).first, left_resid); 805 //NOTE: Only splitting 806 this->_map.insert(prior_, segment_type(left_resid, (*first_).second)); 807 } 808 //POST: 809 // [----- inter_val ---- . . . 810 // ...[-- first_ --... 811 } 812 813 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> 814 template<class Combiner> 815 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_)816 ::add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_) 817 { 818 interval_type lead_gap = right_subtract(inter_val, (*it_).first); 819 if(!icl::is_empty(lead_gap)) 820 { 821 // [lead_gap--- . . . 822 // [-- it_ ... 823 iterator prior_ = prior(it_); 824 iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val); 825 that()->handle_inserted(prior_, inserted_); 826 } 827 828 // . . . --------- . . . addend interval 829 // [-- it_ --) has a common part with the first overval 830 Combiner()((*it_).second, co_val); 831 that()->template handle_left_combined<Combiner>(it_++); 832 } 833 834 835 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> 836 template<class Combiner> 837 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_)838 ::add_main(interval_type& inter_val, const CodomainT& co_val, 839 iterator& it_, const iterator& last_) 840 { 841 interval_type cur_interval; 842 while(it_!=last_) 843 { 844 cur_interval = (*it_).first ; 845 add_segment<Combiner>(inter_val, co_val, it_); 846 // shrink interval 847 inter_val = left_subtract(inter_val, cur_interval); 848 } 849 } 850 851 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> 852 template<class Combiner> 853 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_)854 ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_) 855 { 856 iterator prior_ = cyclic_prior(*that(), it_); 857 interval_type cur_itv = (*it_).first ; 858 859 interval_type lead_gap = right_subtract(inter_val, cur_itv); 860 if(!icl::is_empty(lead_gap)) 861 { // [lead_gap--- . . . 862 // [prior) [-- it_ ... 863 iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val); 864 that()->handle_inserted(prior_, inserted_); 865 } 866 867 interval_type end_gap = left_subtract(inter_val, cur_itv); 868 if(!icl::is_empty(end_gap)) 869 { 870 // [----------------end_gap) 871 // . . . -- it_ --) 872 Combiner()((*it_).second, co_val); 873 that()->template gap_insert_at<Combiner>(it_, prior_, end_gap, co_val); 874 } 875 else 876 { 877 // only for the last there can be a right_resid: a part of *it_ right of x 878 interval_type right_resid = left_subtract(cur_itv, inter_val); 879 880 if(icl::is_empty(right_resid)) 881 { 882 // [---------------) 883 // [-- it_ ---) 884 Combiner()((*it_).second, co_val); 885 that()->template handle_preceeded_combined<Combiner>(prior_, it_); 886 } 887 else 888 { 889 // [--------------) 890 // [-- it_ --right_resid) 891 const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid); 892 893 //NOTE: This is NOT an insertion that has to take care for correct application of 894 // the Combiner functor. It only reestablished that state after splitting the 895 // 'it_' interval value pair. Using _map_insert<Combiner> does not work here. 896 iterator insertion_ = this->_map.insert(it_, value_type(right_resid, (*it_).second)); 897 that()->handle_reinserted(insertion_); 898 899 Combiner()((*it_).second, co_val); 900 that()->template handle_preceeded_combined<Combiner>(insertion_, it_); 901 } 902 } 903 } 904 905 906 //============================================================================== 907 //= Addition 908 //============================================================================== 909 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> 910 template<class Combiner> 911 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 912 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _add(const segment_type & addend)913 ::_add(const segment_type& addend) 914 { 915 typedef typename on_absorbtion<type,Combiner, 916 absorbs_identities<type>::value>::type on_absorbtion_; 917 918 const interval_type& inter_val = addend.first; 919 if(icl::is_empty(inter_val)) 920 return this->_map.end(); 921 922 const codomain_type& co_val = addend.second; 923 if(on_absorbtion_::is_absorbable(co_val)) 924 return this->_map.end(); 925 926 std::pair<iterator,bool> insertion 927 = this->_map.insert(value_type(inter_val, version<Combiner>()(co_val))); 928 929 if(insertion.second) 930 return that()->handle_inserted(insertion.first); 931 else 932 { 933 // Detect the first and the end iterator of the collision sequence 934 iterator first_ = this->_map.lower_bound(inter_val), 935 last_ = insertion.first; 936 //assert(end_ == this->_map.upper_bound(inter_val)); 937 iterator it_ = first_; 938 interval_type rest_interval = inter_val; 939 940 add_front (rest_interval, it_ ); 941 add_main<Combiner>(rest_interval, co_val, it_, last_); 942 add_rear<Combiner>(rest_interval, co_val, it_ ); 943 return it_; 944 } 945 } 946 947 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> 948 template<class Combiner> 949 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 950 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _add(iterator prior_,const segment_type & addend)951 ::_add(iterator prior_, const segment_type& addend) 952 { 953 typedef typename on_absorbtion<type,Combiner, 954 absorbs_identities<type>::value>::type on_absorbtion_; 955 956 const interval_type& inter_val = addend.first; 957 if(icl::is_empty(inter_val)) 958 return prior_; 959 960 const codomain_type& co_val = addend.second; 961 if(on_absorbtion_::is_absorbable(co_val)) 962 return prior_; 963 964 std::pair<iterator,bool> insertion 965 = add_at<Combiner>(prior_, inter_val, co_val); 966 967 if(insertion.second) 968 return that()->handle_inserted(insertion.first); 969 else 970 { 971 // Detect the first and the end iterator of the collision sequence 972 std::pair<iterator,iterator> overlap = equal_range(inter_val); 973 iterator it_ = overlap.first, 974 last_ = prior(overlap.second); 975 interval_type rest_interval = inter_val; 976 977 add_front (rest_interval, it_ ); 978 add_main<Combiner>(rest_interval, co_val, it_, last_); 979 add_rear<Combiner>(rest_interval, co_val, it_ ); 980 return it_; 981 } 982 } 983 984 //============================================================================== 985 //= Subtraction detail 986 //============================================================================== 987 988 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> 989 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> subtract_front(const interval_type & inter_val,iterator & it_)990 ::subtract_front(const interval_type& inter_val, iterator& it_) 991 { 992 interval_type left_resid = right_subtract((*it_).first, inter_val); 993 994 if(!icl::is_empty(left_resid)) // [--- inter_val ---) 995 { //[prior_) [left_resid)[--- it_ . . . 996 iterator prior_ = cyclic_prior(*this, it_); 997 const_cast<interval_type&>((*it_).first) = left_subtract((*it_).first, left_resid); 998 this->_map.insert(prior_, value_type(left_resid, (*it_).second)); 999 // The segemnt *it_ is split at inter_val.first(), so as an invariant 1000 // segment *it_ is always "under" inter_val and a left_resid is empty. 1001 } 1002 } 1003 1004 1005 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> 1006 template<class Combiner> 1007 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_)1008 ::subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_) 1009 { 1010 while(it_ != last_) 1011 { 1012 Combiner()((*it_).second, co_val); 1013 that()->template handle_left_combined<Combiner>(it_++); 1014 } 1015 } 1016 1017 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> 1018 template<class Combiner> 1019 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_)1020 ::subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_) 1021 { 1022 interval_type right_resid = left_subtract((*it_).first, inter_val); 1023 1024 if(icl::is_empty(right_resid)) 1025 { 1026 Combiner()((*it_).second, co_val); 1027 that()->template handle_combined<Combiner>(it_); 1028 } 1029 else 1030 { 1031 const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid); 1032 iterator next_ = this->_map.insert(it_, value_type(right_resid, (*it_).second)); 1033 Combiner()((*it_).second, co_val); 1034 that()->template handle_succeeded_combined<Combiner>(it_, next_); 1035 } 1036 } 1037 1038 //============================================================================== 1039 //= Subtraction 1040 //============================================================================== 1041 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> 1042 template<class Combiner> 1043 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _subtract(const segment_type & minuend)1044 ::_subtract(const segment_type& minuend) 1045 { 1046 interval_type inter_val = minuend.first; 1047 if(icl::is_empty(inter_val)) 1048 return; 1049 1050 const codomain_type& co_val = minuend.second; 1051 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val)) 1052 return; 1053 1054 std::pair<iterator, iterator> exterior = equal_range(inter_val); 1055 if(exterior.first == exterior.second) 1056 return; 1057 1058 iterator last_ = prior(exterior.second); 1059 iterator it_ = exterior.first; 1060 subtract_front (inter_val, it_ ); 1061 subtract_main <Combiner>( co_val, it_, last_); 1062 subtract_rear <Combiner>(inter_val, co_val, it_ ); 1063 } 1064 1065 //============================================================================== 1066 //= Insertion 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 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_)1070 ::insert_main(const interval_type& inter_val, const CodomainT& co_val, 1071 iterator& it_, const iterator& last_) 1072 { 1073 iterator end_ = boost::next(last_); 1074 iterator prior_ = it_, inserted_; 1075 if(prior_ != this->_map.end()) 1076 --prior_; 1077 interval_type rest_interval = inter_val, left_gap, cur_itv; 1078 interval_type last_interval = last_ ->first; 1079 1080 while(it_ != end_ ) 1081 { 1082 cur_itv = (*it_).first ; 1083 left_gap = right_subtract(rest_interval, cur_itv); 1084 1085 if(!icl::is_empty(left_gap)) 1086 { 1087 inserted_ = this->_map.insert(prior_, value_type(left_gap, co_val)); 1088 it_ = that()->handle_inserted(inserted_); 1089 } 1090 1091 // shrink interval 1092 rest_interval = left_subtract(rest_interval, cur_itv); 1093 prior_ = it_; 1094 ++it_; 1095 } 1096 1097 //insert_rear(rest_interval, co_val, last_): 1098 interval_type end_gap = left_subtract(rest_interval, last_interval); 1099 if(!icl::is_empty(end_gap)) 1100 { 1101 inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val)); 1102 it_ = that()->handle_inserted(inserted_); 1103 } 1104 else 1105 it_ = prior_; 1106 } 1107 1108 1109 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> 1110 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 1111 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _insert(const segment_type & addend)1112 ::_insert(const segment_type& addend) 1113 { 1114 interval_type inter_val = addend.first; 1115 if(icl::is_empty(inter_val)) 1116 return this->_map.end(); 1117 1118 const codomain_type& co_val = addend.second; 1119 if(on_codomain_absorbtion::is_absorbable(co_val)) 1120 return this->_map.end(); 1121 1122 std::pair<iterator,bool> insertion = this->_map.insert(addend); 1123 1124 if(insertion.second) 1125 return that()->handle_inserted(insertion.first); 1126 else 1127 { 1128 // Detect the first and the end iterator of the collision sequence 1129 iterator first_ = this->_map.lower_bound(inter_val), 1130 last_ = insertion.first; 1131 //assert((++last_) == this->_map.upper_bound(inter_val)); 1132 iterator it_ = first_; 1133 insert_main(inter_val, co_val, it_, last_); 1134 return it_; 1135 } 1136 } 1137 1138 1139 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> 1140 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator 1141 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> _insert(iterator prior_,const segment_type & addend)1142 ::_insert(iterator prior_, const segment_type& addend) 1143 { 1144 interval_type inter_val = addend.first; 1145 if(icl::is_empty(inter_val)) 1146 return prior_; 1147 1148 const codomain_type& co_val = addend.second; 1149 if(on_codomain_absorbtion::is_absorbable(co_val)) 1150 return prior_; 1151 1152 std::pair<iterator,bool> insertion = insert_at(prior_, inter_val, co_val); 1153 1154 if(insertion.second) 1155 return that()->handle_inserted(insertion.first); 1156 { 1157 // Detect the first and the end iterator of the collision sequence 1158 std::pair<iterator,iterator> overlap = equal_range(inter_val); 1159 iterator it_ = overlap.first, 1160 last_ = prior(overlap.second); 1161 insert_main(inter_val, co_val, it_, last_); 1162 return it_; 1163 } 1164 } 1165 1166 //============================================================================== 1167 //= Erasure segment_type 1168 //============================================================================== 1169 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> 1170 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_)1171 ::erase_rest(interval_type& inter_val, const CodomainT& co_val, 1172 iterator& it_, const iterator& last_) 1173 { 1174 // For all intervals within loop: (*it_).first are contained_in inter_val 1175 while(it_ != last_) 1176 if((*it_).second == co_val) 1177 this->_map.erase(it_++); 1178 else it_++; 1179 1180 //erase_rear: 1181 if((*it_).second == co_val) 1182 { 1183 interval_type right_resid = left_subtract((*it_).first, inter_val); 1184 if(icl::is_empty(right_resid)) 1185 this->_map.erase(it_); 1186 else 1187 const_cast<interval_type&>((*it_).first) = right_resid; 1188 } 1189 } 1190 1191 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> 1192 inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> erase(const segment_type & minuend)1193 ::erase(const segment_type& minuend) 1194 { 1195 interval_type inter_val = minuend.first; 1196 if(icl::is_empty(inter_val)) 1197 return *that(); 1198 1199 const codomain_type& co_val = minuend.second; 1200 if(on_codomain_absorbtion::is_absorbable(co_val)) 1201 return *that(); 1202 1203 std::pair<iterator,iterator> exterior = equal_range(inter_val); 1204 if(exterior.first == exterior.second) 1205 return *that(); 1206 1207 iterator first_ = exterior.first, end_ = exterior.second, 1208 last_ = cyclic_prior(*this, end_); 1209 iterator second_= first_; ++second_; 1210 1211 if(first_ == last_) 1212 { // [----inter_val----) 1213 // .....first_==last_..... 1214 // only for the last there can be a right_resid: a part of *it_ right of minuend 1215 interval_type right_resid = left_subtract((*first_).first, inter_val); 1216 1217 if((*first_).second == co_val) 1218 { 1219 interval_type left_resid = right_subtract((*first_).first, inter_val); 1220 if(!icl::is_empty(left_resid)) // [----inter_val----) 1221 { // [left_resid)..first_==last_...... 1222 const_cast<interval_type&>((*first_).first) = left_resid; 1223 if(!icl::is_empty(right_resid)) 1224 this->_map.insert(first_, value_type(right_resid, co_val)); 1225 } 1226 else if(!icl::is_empty(right_resid)) 1227 const_cast<interval_type&>((*first_).first) = right_resid; 1228 else 1229 this->_map.erase(first_); 1230 } 1231 } 1232 else 1233 { 1234 // first AND NOT last 1235 if((*first_).second == co_val) 1236 { 1237 interval_type left_resid = right_subtract((*first_).first, inter_val); 1238 if(icl::is_empty(left_resid)) 1239 this->_map.erase(first_); 1240 else 1241 const_cast<interval_type&>((*first_).first) = left_resid; 1242 } 1243 1244 erase_rest(inter_val, co_val, second_, last_); 1245 } 1246 1247 return *that(); 1248 } 1249 1250 //============================================================================== 1251 //= Erasure key_type 1252 //============================================================================== 1253 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> 1254 inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> erase(const interval_type & minuend)1255 ::erase(const interval_type& minuend) 1256 { 1257 if(icl::is_empty(minuend)) 1258 return *that(); 1259 1260 std::pair<iterator, iterator> exterior = equal_range(minuend); 1261 if(exterior.first == exterior.second) 1262 return *that(); 1263 1264 iterator first_ = exterior.first, 1265 end_ = exterior.second, 1266 last_ = prior(end_); 1267 1268 interval_type left_resid = right_subtract((*first_).first, minuend); 1269 interval_type right_resid = left_subtract(last_ ->first, minuend); 1270 1271 if(first_ == last_ ) 1272 if(!icl::is_empty(left_resid)) 1273 { 1274 const_cast<interval_type&>((*first_).first) = left_resid; 1275 if(!icl::is_empty(right_resid)) 1276 this->_map.insert(first_, value_type(right_resid, (*first_).second)); 1277 } 1278 else if(!icl::is_empty(right_resid)) 1279 const_cast<interval_type&>((*first_).first) = left_subtract((*first_).first, minuend); 1280 else 1281 this->_map.erase(first_); 1282 else 1283 { // [-------- minuend ---------) 1284 // [left_resid fst) . . . . [lst right_resid) 1285 iterator second_= first_; ++second_; 1286 1287 iterator start_ = icl::is_empty(left_resid)? first_: second_; 1288 iterator stop_ = icl::is_empty(right_resid)? end_ : last_ ; 1289 this->_map.erase(start_, stop_); //erase [start_, stop_) 1290 1291 if(!icl::is_empty(left_resid)) 1292 const_cast<interval_type&>((*first_).first) = left_resid; 1293 1294 if(!icl::is_empty(right_resid)) 1295 const_cast<interval_type&>(last_ ->first) = right_resid; 1296 } 1297 1298 return *that(); 1299 } 1300 1301 //----------------------------------------------------------------------------- 1302 // type traits 1303 //----------------------------------------------------------------------------- 1304 template 1305 < 1306 class SubType, 1307 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1308 > 1309 struct is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1310 { 1311 typedef is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1312 BOOST_STATIC_CONSTANT(bool, value = true); 1313 }; 1314 1315 template 1316 < 1317 class SubType, 1318 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1319 > 1320 struct has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1321 { 1322 typedef has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1323 BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value)); 1324 }; 1325 1326 template 1327 < 1328 class SubType, 1329 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1330 > 1331 struct is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1332 { 1333 typedef is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1334 BOOST_STATIC_CONSTANT(bool, value = true); 1335 }; 1336 1337 template 1338 < 1339 class SubType, 1340 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1341 > 1342 struct absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1343 { 1344 typedef absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1345 BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities)); 1346 }; 1347 1348 template 1349 < 1350 class SubType, 1351 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc 1352 > 1353 struct is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > 1354 { 1355 typedef is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type; 1356 BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total)); 1357 }; 1358 1359 1360 1361 }} // namespace icl boost 1362 1363 #endif 1364 1365 1366