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
12 #include <boost/icl/impl_config.hpp>
14 #if defined(ICL_USE_BOOST_MOVE_IMPLEMENTATION)
15 # include <boost/container/set.hpp>
16 #elif defined(ICL_USE_STD_IMPLEMENTATION)
18 #else // Default for implementing containers
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>
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>
39 namespace boost{namespace icl
42 /** \brief Implements a set as a set of intervals (base class) */
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
51 class interval_base_set
54 //==========================================================================
56 //==========================================================================
57 typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> type;
59 /// The designated \e derived or \e sub_type of this base class
60 typedef SubType sub_type;
62 /// Auxilliary type for overloadresolution
63 typedef type overloadable_type;
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;
73 /// The element type of the set
74 typedef DomainT element_type;
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;
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;
87 /// The size type of an interval which is mostly std::size_t
88 typedef typename size_type_of<domain_type>::type size_type;
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;
100 /// Comparison functor for keys
101 typedef exclusive_less_than<interval_type> key_compare;
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;
109 //--------------------------------------------------------------------------
110 //- Associated types: Implementation and stl related
111 //--------------------------------------------------------------------------
112 /// The allocator type of the set
113 typedef Alloc<interval_type> allocator_type;
115 /// allocator type of the corresponding element set
116 typedef Alloc<DomainT> domain_allocator_type;
118 /// Container type for the implementation
119 typedef typename ICL_IMPL_SPACE::set<interval_type,key_compare,allocator_type> ImplSetT;
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;
129 typedef typename ImplSetT::pointer pointer;
130 /// const pointer type
131 typedef typename ImplSetT::const_pointer const_pointer;
133 typedef typename ImplSetT::reference reference;
134 /// const reference type
135 typedef typename ImplSetT::const_reference const_reference;
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;
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;
155 BOOST_STATIC_CONSTANT(int, fineness = 0);
158 //==========================================================================
159 //= Construct, copy, destruct
160 //==========================================================================
161 /** Default constructor for the empty object */
162 interval_base_set(){}
164 /** Copy constructor */
165 interval_base_set(const interval_base_set& src): _set(src._set)
167 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
168 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
171 # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
172 //==========================================================================
174 //==========================================================================
176 /** Move constructor */
177 interval_base_set(interval_base_set&& src): _set(boost::move(src._set))
179 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
180 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
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);
190 //==========================================================================
193 /** Copy assignment operator */
194 interval_base_set& operator = (const interval_base_set& src)
196 this->_set = src._set;
200 # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
202 /** swap the content of containers */
203 void swap(interval_base_set& operand) { _set.swap(operand._set); }
205 //==========================================================================
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()); }
213 //==========================================================================
215 //==========================================================================
216 /** An interval set's size is it's cardinality */
217 size_type size()const
219 return icl::cardinality(*that());
222 /** Size of the iteration over this container */
223 std::size_t iterative_size()const
228 //==========================================================================
230 //==========================================================================
232 /** Find the interval, that contains element \c key_value */
233 const_iterator find(const element_type& key_value)const
235 return icl::find(*this, key_value);
236 //CL return this->_set.find(icl::singleton<segment_type>(key));
239 /** Find the first interval, that collides with interval \c key_interval */
240 const_iterator find(const interval_type& key_interval)const
242 return this->_set.find(key_interval);
245 //==========================================================================
247 //==========================================================================
249 /** Add a single element \c key to the set */
250 SubType& add(const element_type& key)
252 return icl::add(*that(), key);
255 /** Add an interval of elements \c inter_val to the set */
256 SubType& add(const segment_type& inter_val)
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
265 iterator add(iterator prior_, const segment_type& inter_val)
267 return _add(prior_, inter_val);
270 //==========================================================================
272 //==========================================================================
274 /** Subtract a single element \c key from the set */
275 SubType& subtract(const element_type& key)
277 return icl::subtract(*that(), key);
280 /** Subtract an interval of elements \c inter_val from the set */
281 SubType& subtract(const segment_type& inter_val);
283 //==========================================================================
285 //==========================================================================
286 /** Insert an element \c key into the set */
287 SubType& insert(const element_type& key)
292 /** Insert an interval of elements \c inter_val to the set */
293 SubType& insert(const segment_type& inter_val)
295 return add(inter_val);
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
301 iterator insert(iterator prior_, const segment_type& inter_val)
303 return add(prior_, inter_val);
308 //==========================================================================
310 //==========================================================================
311 /** Erase an element \c key from the set */
312 SubType& erase(const element_type& key)
314 return subtract(key);
317 /** Erase an interval of elements \c inter_val from the set */
318 SubType& erase(const segment_type& inter_val)
320 return subtract(inter_val);
323 /** Erase the interval that iterator \c position points to. */
324 void erase(iterator position)
326 _set.erase(position);
329 /** Erase all intervals in the range <tt>[first,past)</tt> of iterators. */
330 void erase(iterator first, iterator past)
332 _set.erase(first, past);
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)
341 return icl::flip(*that(), key);
344 /** If \c *this set contains \c inter_val it is erased, otherwise it is added. */
345 SubType& flip(const segment_type& inter_val)
347 return icl::flip(*that(), inter_val);
350 //==========================================================================
352 //==========================================================================
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(); }
363 iterator lower_bound(const value_type& interval)
364 { return _set.lower_bound(interval); }
366 iterator upper_bound(const value_type& interval)
367 { return _set.upper_bound(interval); }
369 const_iterator lower_bound(const value_type& interval)const
370 { return _set.lower_bound(interval); }
372 const_iterator upper_bound(const value_type& interval)const
373 { return _set.upper_bound(interval); }
375 std::pair<iterator,iterator> equal_range(const key_type& interval)
377 return std::pair<iterator,iterator>
378 (_set.lower_bound(interval), _set.upper_bound(interval));
381 std::pair<const_iterator,const_iterator>
382 equal_range(const key_type& interval)const
384 return std::pair<const_iterator,const_iterator>
385 (_set.lower_bound(interval), _set.upper_bound(interval));
389 iterator _add(const segment_type& addend);
390 iterator _add(iterator prior, const segment_type& addend);
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_);
399 sub_type* that() { return static_cast<sub_type*>(this); }
400 const sub_type* that()const { return static_cast<const sub_type*>(this); }
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_)
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.
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);
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);
428 // [----- inter_val ---- . . .
429 // ...[-- first_ --...
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_)
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);
442 // . . . --------- . . . addend interval
443 // [-- it_ --) has a common part with the first overval
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_)
451 interval_type cur_interval;
454 cur_interval = *it_ ;
455 add_segment(rest_interval, it_);
457 rest_interval = left_subtract(rest_interval, cur_interval);
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_)
465 iterator prior_ = cyclic_prior(*this, it_);
466 interval_type cur_itv = *it_;
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);
474 interval_type end_gap = left_subtract(inter_val, cur_itv);
475 if(!icl::is_empty(end_gap))
476 // [---------------end_gap)
478 it_ = this->_set.insert(it_, end_gap);
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);
484 if(!icl::is_empty(right_resid))
487 // [-- it_ --right_resid)
488 const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid);
489 it_ = this->_set.insert(it_, right_resid);
494 //==============================================================================
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)
502 typedef typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator iterator;
503 if(icl::is_empty(addend))
504 return this->_set.end();
506 std::pair<iterator,bool> insertion = this->_set.insert(addend);
509 return that()->handle_inserted(insertion.first);
512 iterator last_ = prior(this->_set.upper_bound(addend));
513 return that()->add_over(addend, last_);
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)
522 typedef typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator iterator;
523 if(icl::is_empty(addend))
526 iterator insertion = this->_set.insert(prior_, addend);
528 if(*insertion == addend)
529 return that()->handle_inserted(insertion);
532 iterator last_ = prior(this->_set.upper_bound(addend));
533 return that()->add_over(addend, last_);
537 //==============================================================================
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)
544 if(icl::is_empty(minuend))
547 std::pair<iterator, iterator> exterior = equal_range(minuend);
548 if(exterior.first == exterior.second)
551 iterator first_ = exterior.first;
552 iterator end_ = exterior.second;
553 iterator last_ = prior(end_);
555 interval_type left_resid = right_subtract(*first_, minuend);
556 interval_type right_resid;
558 right_resid = left_subtract(*last_ , minuend);
560 this->_set.erase(first_, end_);
562 if(!icl::is_empty(left_resid))
563 this->_set.insert(left_resid);
565 if(!icl::is_empty(right_resid))
566 this->_set.insert(right_resid);
571 //-----------------------------------------------------------------------------
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> >
578 typedef is_set<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > type;
579 BOOST_STATIC_CONSTANT(bool, value = true);
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> >
586 typedef is_interval_container<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > type;
587 BOOST_STATIC_CONSTANT(bool, value = true);
592 }} // namespace icl boost