boost/icl/interval_base_set.hpp

   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 */
 162     interval_base_set(){}
 163
 164     /** Copy constructor */
 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 */
 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 */
 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 */
 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 */
 203     void swap(interval_base_set& operand) { _set.swap(operand._set); }
 204
 205     //==========================================================================
 206     //= Containedness
 207     //==========================================================================
 208     /** sets the container empty */
 209     void clear() { icl::clear(*that()); }
 210     /** is the container empty? */
 211     bool empty()const { return icl::is_empty(*that()); }
 212
 213     //==========================================================================
 214     //= Size
 215     //==========================================================================
 216     /** An interval set's size is it's cardinality */
 217     size_type size()const
 218     {
 219         return icl::cardinality(*that());
 220     }
 221
 222     /** Size of the iteration over this container */
 223     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 */
 233     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 */
 240     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 */
 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 */
 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. */
 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 */
 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 */
 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 */
 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. */
 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 */
 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 */
 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. */
 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. */
 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. */
 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. */
 345     SubType& flip(const segment_type& inter_val)
 346     {
 347         return icl::flip(*that(), inter_val);
 348     }
 349
 350     //==========================================================================
 351     //= Iterator related
 352     //==========================================================================
 353
 354     iterator begin() { return _set.begin(); }
 355     iterator end()   { return _set.end(); }
 356     const_iterator begin()const { return _set.begin(); }
 357     const_iterator end()const   { return _set.end(); }
 358     reverse_iterator rbegin() { return _set.rbegin(); }
 359     reverse_iterator rend()   { return _set.rend(); }
 360     const_reverse_iterator rbegin()const { return _set.rbegin(); }
 361     const_reverse_iterator rend()const   { return _set.rend(); }
 362
 363     iterator lower_bound(const value_type& interval)
 364     { return _set.lower_bound(interval); }
 365
 366     iterator upper_bound(const value_type& interval)
 367     { return _set.upper_bound(interval); }
 368
 369     const_iterator lower_bound(const value_type& interval)const
 370     { return _set.lower_bound(interval); }
 371
 372     const_iterator upper_bound(const value_type& interval)const
 373     { return _set.upper_bound(interval); }
 374
 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>
 382         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:
 399     sub_type* that() { return static_cast<sub_type*>(this); }
 400     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>
 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>
 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(prior(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>
 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>
 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>
 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>
 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>
 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
 596