1 /*-----------------------------------------------------------------------------+ 2 Copyright (c) 2007-2011: 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_SET_H_JOFA_990223 10 #define BOOST_ICL_INTERVAL_BASE_SET_H_JOFA_990223 11 12 #include <boost/icl/impl_config.hpp> 13 14 #if defined(ICL_USE_BOOST_MOVE_IMPLEMENTATION) 15 # include <boost/container/set.hpp> 16 #elif defined(ICL_USE_STD_IMPLEMENTATION) 17 # include <set> 18 #else // Default for implementing containers 19 # include <set> 20 #endif 21 22 #include <limits> 23 #include <boost/next_prior.hpp> 24 #include <boost/icl/associative_interval_container.hpp> 25 #include <boost/icl/type_traits/interval_type_default.hpp> 26 #include <boost/icl/interval.hpp> 27 #include <boost/icl/type_traits/infinity.hpp> 28 #include <boost/icl/type_traits/is_interval_joiner.hpp> 29 #include <boost/icl/type_traits/is_interval_separator.hpp> 30 #include <boost/icl/type_traits/is_interval_splitter.hpp> 31 #include <boost/icl/detail/interval_set_algo.hpp> 32 #include <boost/icl/detail/exclusive_less_than.hpp> 33 34 #include <boost/icl/right_open_interval.hpp> 35 #include <boost/icl/continuous_interval.hpp> 36 #include <boost/icl/detail/notate.hpp> 37 #include <boost/icl/detail/element_iterator.hpp> 38 39 namespace boost{namespace icl 40 { 41 42 /** \brief Implements a set as a set of intervals (base class) */ 43 template 44 < 45 typename SubType, 46 typename DomainT, 47 ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT), 48 ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare), 49 ICL_ALLOC Alloc = std::allocator 50 > 51 class interval_base_set 52 { 53 public: 54 //========================================================================== 55 //= Associated types 56 //========================================================================== 57 typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> type; 58 59 /// The designated \e derived or \e sub_type of this base class 60 typedef SubType sub_type; 61 62 /// Auxilliary type for overloadresolution 63 typedef type overloadable_type; 64 65 //-------------------------------------------------------------------------- 66 //- Associated types: Data 67 //-------------------------------------------------------------------------- 68 /// The domain type of the set 69 typedef DomainT domain_type; 70 /// The codomaintype is the same as domain_type 71 typedef DomainT codomain_type; 72 73 /// The element type of the set 74 typedef DomainT element_type; 75 76 /// The interval type of the set 77 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 78 /// The segment type of the set 79 typedef interval_type segment_type; 80 81 //-------------------------------------------------------------------------- 82 //- Associated types: Size 83 //-------------------------------------------------------------------------- 84 /// The difference type of an interval which is sometimes different form the data_type 85 typedef typename difference_type_of<domain_type>::type difference_type; 86 87 /// The size type of an interval which is mostly std::size_t 88 typedef typename size_type_of<domain_type>::type size_type; 89 90 91 //-------------------------------------------------------------------------- 92 //- Associated types: Order 93 //-------------------------------------------------------------------------- 94 /// Comparison functor for domain values 95 typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare; 96 typedef ICL_COMPARE_DOMAIN(Compare,segment_type) segment_compare; 97 /// Comparison functor for intervals 98 typedef exclusive_less_than<interval_type> interval_compare; 99 100 /// Comparison functor for keys 101 typedef exclusive_less_than<interval_type> key_compare; 102 103 //-------------------------------------------------------------------------- 104 //- Associated types: Related types 105 //-------------------------------------------------------------------------- 106 /// The atomized type representing the corresponding container of elements 107 typedef typename ICL_IMPL_SPACE::set<DomainT,domain_compare,Alloc<DomainT> > atomized_type; 108 109 //-------------------------------------------------------------------------- 110 //- Associated types: Implementation and stl related 111 //-------------------------------------------------------------------------- 112 /// The allocator type of the set 113 typedef Alloc<interval_type> allocator_type; 114 115 /// allocator type of the corresponding element set 116 typedef Alloc<DomainT> domain_allocator_type; 117 118 /// Container type for the implementation 119 typedef typename ICL_IMPL_SPACE::set<interval_type,key_compare,allocator_type> ImplSetT; 120 121 /// key type of the implementing container 122 typedef typename ImplSetT::key_type key_type; 123 /// data type of the implementing container 124 typedef typename ImplSetT::key_type data_type; 125 /// value type of the implementing container 126 typedef typename ImplSetT::value_type value_type; 127 128 /// pointer type 129 typedef typename ImplSetT::pointer pointer; 130 /// const pointer type 131 typedef typename ImplSetT::const_pointer const_pointer; 132 /// reference type 133 typedef typename ImplSetT::reference reference; 134 /// const reference type 135 typedef typename ImplSetT::const_reference const_reference; 136 137 /// iterator for iteration over intervals 138 typedef typename ImplSetT::iterator iterator; 139 /// const_iterator for iteration over intervals 140 typedef typename ImplSetT::const_iterator const_iterator; 141 /// iterator for reverse iteration over intervals 142 typedef typename ImplSetT::reverse_iterator reverse_iterator; 143 /// const_iterator for iteration over intervals 144 typedef typename ImplSetT::const_reverse_iterator const_reverse_iterator; 145 146 /// element iterator: Depreciated, see documentation. 147 typedef boost::icl::element_iterator<iterator> element_iterator; 148 /// element const iterator: Depreciated, see documentation. 149 typedef boost::icl::element_iterator<const_iterator> element_const_iterator; 150 /// element reverse iterator: Depreciated, see documentation. 151 typedef boost::icl::element_iterator<reverse_iterator> element_reverse_iterator; 152 /// element const reverse iterator: Depreciated, see documentation. 153 typedef boost::icl::element_iterator<const_reverse_iterator> element_const_reverse_iterator; 154 155 BOOST_STATIC_CONSTANT(int, fineness = 0); 156 157 public: 158 //========================================================================== 159 //= Construct, copy, destruct 160 //========================================================================== 161 /** Default constructor for the empty object */ interval_base_set()162 interval_base_set(){} 163 164 /** Copy constructor */ interval_base_set(const interval_base_set & src)165 interval_base_set(const interval_base_set& src): _set(src._set) 166 { 167 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>)); 168 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>)); 169 } 170 171 # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 172 //========================================================================== 173 //= Move semantics 174 //========================================================================== 175 176 /** Move constructor */ interval_base_set(interval_base_set && src)177 interval_base_set(interval_base_set&& src): _set(boost::move(src._set)) 178 { 179 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>)); 180 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>)); 181 } 182 183 /** Move assignment operator */ operator =(interval_base_set src)184 interval_base_set& operator = (interval_base_set src) 185 { //call by value sice 'src' is a "sink value" 186 this->_set = boost::move(src._set); 187 return *this; 188 } 189 190 //========================================================================== 191 # else 192 193 /** Copy assignment operator */ operator =(const interval_base_set & src)194 interval_base_set& operator = (const interval_base_set& src) 195 { 196 this->_set = src._set; 197 return *this; 198 } 199 200 # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES 201 202 /** swap the content of containers */ swap(interval_base_set & operand)203 void swap(interval_base_set& operand) { _set.swap(operand._set); } 204 205 //========================================================================== 206 //= Containedness 207 //========================================================================== 208 /** sets the container empty */ clear()209 void clear() { icl::clear(*that()); } 210 /** is the container empty? */ empty() const211 bool empty()const { return icl::is_empty(*that()); } 212 213 //========================================================================== 214 //= Size 215 //========================================================================== 216 /** An interval set's size is it's cardinality */ size() const217 size_type size()const 218 { 219 return icl::cardinality(*that()); 220 } 221 222 /** Size of the iteration over this container */ iterative_size() const223 std::size_t iterative_size()const 224 { 225 return _set.size(); 226 } 227 228 //========================================================================== 229 //= Selection 230 //========================================================================== 231 232 /** Find the interval, that contains element \c key_value */ find(const element_type & key_value) const233 const_iterator find(const element_type& key_value)const 234 { 235 return icl::find(*this, key_value); 236 //CL return this->_set.find(icl::singleton<segment_type>(key)); 237 } 238 239 /** Find the first interval, that collides with interval \c key_interval */ find(const interval_type & key_interval) const240 const_iterator find(const interval_type& key_interval)const 241 { 242 return this->_set.find(key_interval); 243 } 244 245 //========================================================================== 246 //= Addition 247 //========================================================================== 248 249 /** Add a single element \c key to the set */ add(const element_type & key)250 SubType& add(const element_type& key) 251 { 252 return icl::add(*that(), key); 253 } 254 255 /** Add an interval of elements \c inter_val to the set */ add(const segment_type & inter_val)256 SubType& add(const segment_type& inter_val) 257 { 258 _add(inter_val); 259 return *that(); 260 } 261 262 /** Add an interval of elements \c inter_val to the set. Iterator 263 \c prior_ is a hint to the position \c inter_val can be 264 inserted after. */ add(iterator prior_,const segment_type & inter_val)265 iterator add(iterator prior_, const segment_type& inter_val) 266 { 267 return _add(prior_, inter_val); 268 } 269 270 //========================================================================== 271 //= Subtraction 272 //========================================================================== 273 274 /** Subtract a single element \c key from the set */ subtract(const element_type & key)275 SubType& subtract(const element_type& key) 276 { 277 return icl::subtract(*that(), key); 278 } 279 280 /** Subtract an interval of elements \c inter_val from the set */ 281 SubType& subtract(const segment_type& inter_val); 282 283 //========================================================================== 284 //= Insertion 285 //========================================================================== 286 /** Insert an element \c key into the set */ insert(const element_type & key)287 SubType& insert(const element_type& key) 288 { 289 return add(key); 290 } 291 292 /** Insert an interval of elements \c inter_val to the set */ insert(const segment_type & inter_val)293 SubType& insert(const segment_type& inter_val) 294 { 295 return add(inter_val); 296 } 297 298 /** Insert an interval of elements \c inter_val to the set. Iterator 299 \c prior_ is a hint to the position \c inter_val can be 300 inserted after. */ insert(iterator prior_,const segment_type & inter_val)301 iterator insert(iterator prior_, const segment_type& inter_val) 302 { 303 return add(prior_, inter_val); 304 } 305 306 307 308 //========================================================================== 309 //= Erasure 310 //========================================================================== 311 /** Erase an element \c key from the set */ erase(const element_type & key)312 SubType& erase(const element_type& key) 313 { 314 return subtract(key); 315 } 316 317 /** Erase an interval of elements \c inter_val from the set */ erase(const segment_type & inter_val)318 SubType& erase(const segment_type& inter_val) 319 { 320 return subtract(inter_val); 321 } 322 323 /** Erase the interval that iterator \c position points to. */ erase(iterator position)324 void erase(iterator position) 325 { 326 _set.erase(position); 327 } 328 329 /** Erase all intervals in the range <tt>[first,past)</tt> of iterators. */ erase(iterator first,iterator past)330 void erase(iterator first, iterator past) 331 { 332 _set.erase(first, past); 333 } 334 335 //========================================================================== 336 //= Symmetric difference 337 //========================================================================== 338 /** If \c *this set contains \c key it is erased, otherwise it is added. */ flip(const element_type & key)339 SubType& flip(const element_type& key) 340 { 341 return icl::flip(*that(), key); 342 } 343 344 /** If \c *this set contains \c inter_val it is erased, otherwise it is added. */ flip(const segment_type & inter_val)345 SubType& flip(const segment_type& inter_val) 346 { 347 return icl::flip(*that(), inter_val); 348 } 349 350 //========================================================================== 351 //= Iterator related 352 //========================================================================== 353 begin()354 iterator begin() { return _set.begin(); } end()355 iterator end() { return _set.end(); } begin() const356 const_iterator begin()const { return _set.begin(); } end() const357 const_iterator end()const { return _set.end(); } rbegin()358 reverse_iterator rbegin() { return _set.rbegin(); } rend()359 reverse_iterator rend() { return _set.rend(); } rbegin() const360 const_reverse_iterator rbegin()const { return _set.rbegin(); } rend() const361 const_reverse_iterator rend()const { return _set.rend(); } 362 lower_bound(const value_type & interval)363 iterator lower_bound(const value_type& interval) 364 { return _set.lower_bound(interval); } 365 upper_bound(const value_type & interval)366 iterator upper_bound(const value_type& interval) 367 { return _set.upper_bound(interval); } 368 lower_bound(const value_type & interval) const369 const_iterator lower_bound(const value_type& interval)const 370 { return _set.lower_bound(interval); } 371 upper_bound(const value_type & interval) const372 const_iterator upper_bound(const value_type& interval)const 373 { return _set.upper_bound(interval); } 374 equal_range(const key_type & interval)375 std::pair<iterator,iterator> equal_range(const key_type& interval) 376 { 377 return std::pair<iterator,iterator> 378 (_set.lower_bound(interval), _set.upper_bound(interval)); 379 } 380 381 std::pair<const_iterator,const_iterator> equal_range(const key_type & interval) const382 equal_range(const key_type& interval)const 383 { 384 return std::pair<const_iterator,const_iterator> 385 (_set.lower_bound(interval), _set.upper_bound(interval)); 386 } 387 388 private: 389 iterator _add(const segment_type& addend); 390 iterator _add(iterator prior, const segment_type& addend); 391 392 protected: 393 void add_front(const interval_type& inter_val, iterator& first_); 394 void add_main(interval_type& inter_val, iterator& it_, const iterator& last_); 395 void add_segment(const interval_type& inter_val, iterator& it_); 396 void add_rear(const interval_type& inter_val, iterator& it_); 397 398 protected: that()399 sub_type* that() { return static_cast<sub_type*>(this); } that() const400 const sub_type* that()const { return static_cast<const sub_type*>(this); } 401 402 protected: 403 ImplSetT _set; 404 } ; 405 406 407 template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 408 inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc> add_front(const interval_type & inter_val,iterator & first_)409 ::add_front(const interval_type& inter_val, iterator& first_) 410 { 411 // If the collision sequence has a left residual 'left_resid' it will 412 // be split, to provide a standardized start of algorithms: 413 // The addend interval 'inter_val' covers the beginning of the collision sequence. 414 415 // only for the first there can be a left_resid: a part of *first_ left of inter_val 416 interval_type left_resid = right_subtract(*first_, inter_val); 417 418 if(!icl::is_empty(left_resid)) 419 { // [------------ . . . 420 // [left_resid---first_ --- . . . 421 iterator prior_ = cyclic_prior(*this, first_); 422 const_cast<interval_type&>(*first_) = left_subtract(*first_, left_resid); 423 //NOTE: Only splitting 424 this->_set.insert(prior_, left_resid); 425 } 426 427 //POST: 428 // [----- inter_val ---- . . . 429 // ...[-- first_ --... 430 } 431 432 template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 433 inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc> add_segment(const interval_type & inter_val,iterator & it_)434 ::add_segment(const interval_type& inter_val, iterator& it_) 435 { 436 interval_type lead_gap = right_subtract(inter_val, *it_); 437 if(!icl::is_empty(lead_gap)) 438 // [lead_gap--- . . . 439 // [prior_) [-- it_ ... 440 this->_set.insert(cyclic_prior(*this, it_), lead_gap); 441 442 // . . . --------- . . . addend interval 443 // [-- it_ --) has a common part with the first overval 444 ++it_; 445 } 446 447 template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 448 inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc> add_main(interval_type & rest_interval,iterator & it_,const iterator & last_)449 ::add_main(interval_type& rest_interval, iterator& it_, const iterator& last_) 450 { 451 interval_type cur_interval; 452 while(it_ != last_) 453 { 454 cur_interval = *it_ ; 455 add_segment(rest_interval, it_); 456 // shrink interval 457 rest_interval = left_subtract(rest_interval, cur_interval); 458 } 459 } 460 461 template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 462 inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc> add_rear(const interval_type & inter_val,iterator & it_)463 ::add_rear(const interval_type& inter_val, iterator& it_) 464 { 465 iterator prior_ = cyclic_prior(*this, it_); 466 interval_type cur_itv = *it_; 467 468 interval_type lead_gap = right_subtract(inter_val, cur_itv); 469 if(!icl::is_empty(lead_gap)) 470 // [lead_gap--- . . . 471 // [prior_) [-- it_ ... 472 this->_set.insert(prior_, lead_gap); 473 474 interval_type end_gap = left_subtract(inter_val, cur_itv); 475 if(!icl::is_empty(end_gap)) 476 // [---------------end_gap) 477 // [-- it_ --) 478 it_ = this->_set.insert(it_, end_gap); 479 else 480 { 481 // only for the last there can be a right_resid: a part of *it_ right of addend 482 interval_type right_resid = left_subtract(cur_itv, inter_val); 483 484 if(!icl::is_empty(right_resid)) 485 { 486 // [--------------) 487 // [-- it_ --right_resid) 488 const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid); 489 it_ = this->_set.insert(it_, right_resid); 490 } 491 } 492 } 493 494 //============================================================================== 495 //= Addition 496 //============================================================================== 497 template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 498 inline typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator 499 interval_base_set<SubType,DomainT,Compare,Interval,Alloc> _add(const segment_type & addend)500 ::_add(const segment_type& addend) 501 { 502 typedef typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator iterator; 503 if(icl::is_empty(addend)) 504 return this->_set.end(); 505 506 std::pair<iterator,bool> insertion = this->_set.insert(addend); 507 508 if(insertion.second) 509 return that()->handle_inserted(insertion.first); 510 else 511 { 512 iterator last_ = prior(this->_set.upper_bound(addend)); 513 return that()->add_over(addend, last_); 514 } 515 } 516 517 template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 518 inline typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator 519 interval_base_set<SubType,DomainT,Compare,Interval,Alloc> _add(iterator prior_,const segment_type & addend)520 ::_add(iterator prior_, const segment_type& addend) 521 { 522 typedef typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator iterator; 523 if(icl::is_empty(addend)) 524 return prior_; 525 526 iterator insertion = this->_set.insert(prior_, addend); 527 528 if(*insertion == addend) 529 return that()->handle_inserted(insertion); 530 else 531 { 532 iterator last_ = prior(this->_set.upper_bound(addend)); 533 return that()->add_over(addend, last_); 534 } 535 } 536 537 //============================================================================== 538 //= Subtraction 539 //============================================================================== 540 template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 541 inline SubType& interval_base_set<SubType,DomainT,Compare,Interval,Alloc> subtract(const segment_type & minuend)542 ::subtract(const segment_type& minuend) 543 { 544 if(icl::is_empty(minuend)) 545 return *that(); 546 547 std::pair<iterator, iterator> exterior = equal_range(minuend); 548 if(exterior.first == exterior.second) 549 return *that(); 550 551 iterator first_ = exterior.first; 552 iterator end_ = exterior.second; 553 iterator last_ = prior(end_); 554 555 interval_type left_resid = right_subtract(*first_, minuend); 556 interval_type right_resid; 557 if(first_ != end_) 558 right_resid = left_subtract(*last_ , minuend); 559 560 this->_set.erase(first_, end_); 561 562 if(!icl::is_empty(left_resid)) 563 this->_set.insert(left_resid); 564 565 if(!icl::is_empty(right_resid)) 566 this->_set.insert(right_resid); 567 568 return *that(); 569 } 570 571 //----------------------------------------------------------------------------- 572 // type traits 573 //----------------------------------------------------------------------------- 574 template<class SubType, 575 class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 576 struct is_set<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > 577 { 578 typedef is_set<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > type; 579 BOOST_STATIC_CONSTANT(bool, value = true); 580 }; 581 582 template<class SubType, 583 class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc> 584 struct is_interval_container<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > 585 { 586 typedef is_interval_container<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > type; 587 BOOST_STATIC_CONSTANT(bool, value = true); 588 }; 589 590 591 592 }} // namespace icl boost 593 594 #endif 595