]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |