]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*-----------------------------------------------------------------------------+ |
2 | Copyright (c) 2008-2010: Joachim Faulhaber | |
3 | +------------------------------------------------------------------------------+ | |
4 | Distributed under the Boost Software License, Version 1.0. | |
5 | (See accompanying file LICENCE.txt or copy at | |
6 | http://www.boost.org/LICENSE_1_0.txt) | |
7 | +-----------------------------------------------------------------------------*/ | |
8 | #ifndef BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005 | |
9 | #define BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005 | |
10 | ||
11 | #include <boost/next_prior.hpp> | |
12 | #include <boost/icl/detail/notate.hpp> | |
13 | #include <boost/icl/detail/relation_state.hpp> | |
14 | #include <boost/icl/type_traits/identity_element.hpp> | |
15 | #include <boost/icl/type_traits/is_map.hpp> | |
16 | #include <boost/icl/type_traits/is_total.hpp> | |
17 | #include <boost/icl/type_traits/is_combinable.hpp> | |
18 | #include <boost/icl/concept/set_value.hpp> | |
19 | #include <boost/icl/concept/map_value.hpp> | |
20 | #include <boost/icl/interval_combining_style.hpp> | |
21 | #include <boost/icl/detail/element_comparer.hpp> | |
22 | #include <boost/icl/detail/interval_subset_comparer.hpp> | |
23 | #include <boost/icl/detail/associated_value.hpp> | |
24 | ||
25 | namespace boost{namespace icl | |
26 | { | |
27 | ||
28 | namespace Interval_Set | |
29 | { | |
30 | ||
31 | //------------------------------------------------------------------------------ | |
32 | // Lexicographical comparison on ranges of two interval container | |
33 | //------------------------------------------------------------------------------ | |
34 | ||
35 | template<class LeftT, class RightT> | |
36 | bool is_element_equal(const LeftT& left, const RightT& right) | |
37 | { | |
38 | return subset_compare | |
39 | ( | |
40 | left, right, | |
41 | left.begin(), left.end(), | |
42 | right.begin(), right.end() | |
43 | ) == inclusion::equal; | |
44 | } | |
45 | ||
46 | template<class LeftT, class RightT> | |
47 | bool is_element_less(const LeftT& left, const RightT& right) | |
48 | { | |
49 | return element_compare | |
50 | ( | |
51 | left, right, | |
52 | left.begin(), left.end(), | |
53 | right.begin(), right.end() | |
54 | ) == comparison::less; | |
55 | } | |
56 | ||
57 | template<class LeftT, class RightT> | |
58 | bool is_element_greater(const LeftT& left, const RightT& right) | |
59 | { | |
60 | return element_compare | |
61 | ( | |
62 | left, right, | |
63 | left.begin(), left.end(), | |
64 | right.begin(), right.end() | |
65 | ) == comparison::greater; | |
66 | } | |
67 | ||
68 | //------------------------------------------------------------------------------ | |
69 | // Subset/superset compare on ranges of two interval container | |
70 | //------------------------------------------------------------------------------ | |
71 | ||
72 | template<class IntervalContainerT> | |
73 | bool is_joinable(const IntervalContainerT& container, | |
74 | typename IntervalContainerT::const_iterator first, | |
75 | typename IntervalContainerT::const_iterator past) | |
76 | { | |
77 | if(first == container.end()) | |
78 | return true; | |
79 | ||
80 | typename IntervalContainerT::const_iterator it_ = first, next_ = first; | |
81 | ++next_; | |
82 | ||
83 | while(next_ != container.end() && it_ != past) | |
84 | if(!icl::touches(key_value<IntervalContainerT>(it_++), | |
85 | key_value<IntervalContainerT>(next_++))) | |
86 | return false; | |
87 | ||
88 | return true; | |
89 | } | |
90 | ||
91 | ||
92 | template<class LeftT, class RightT> | |
93 | bool is_inclusion_equal(const LeftT& left, const RightT& right) | |
94 | { | |
95 | return subset_compare | |
96 | ( | |
97 | left, right, | |
98 | left.begin(), left.end(), | |
99 | right.begin(), right.end() | |
100 | ) == inclusion::equal; | |
101 | } | |
102 | ||
103 | template<class LeftT, class RightT> | |
104 | typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>, | |
105 | is_total<RightT> >, | |
106 | bool>::type | |
107 | within(const LeftT&, const RightT&) | |
108 | { | |
109 | return true; | |
110 | } | |
111 | ||
112 | template<class LeftT, class RightT> | |
113 | typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>, | |
114 | mpl::not_<is_total<RightT> > >, | |
115 | bool>::type | |
116 | within(const LeftT& sub, const RightT& super) | |
117 | { | |
118 | int result = | |
119 | subset_compare | |
120 | ( | |
121 | sub, super, | |
122 | sub.begin(), sub.end(), | |
123 | super.begin(), super.end() | |
124 | ); | |
125 | return result == inclusion::subset || result == inclusion::equal; | |
126 | } | |
127 | ||
128 | ||
129 | template<class LeftT, class RightT> | |
130 | typename enable_if<is_concept_combinable<is_interval_map, is_interval_map, LeftT, RightT>, | |
131 | bool>::type | |
132 | within(const LeftT& sub, const RightT& super) | |
133 | { | |
134 | int result = | |
135 | subset_compare | |
136 | ( | |
137 | sub, super, | |
138 | sub.begin(), sub.end(), | |
139 | super.begin(), super.end() | |
140 | ); | |
141 | return result == inclusion::subset || result == inclusion::equal; | |
142 | } | |
143 | ||
144 | template<class LeftT, class RightT> | |
145 | typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>, | |
146 | bool>::type | |
147 | within(const LeftT& sub, const RightT& super) | |
148 | { | |
149 | int result = | |
150 | subset_compare | |
151 | ( | |
152 | sub, super, | |
153 | sub.begin(), sub.end(), | |
154 | super.begin(), super.end() | |
155 | ); | |
156 | return result == inclusion::subset || result == inclusion::equal; | |
157 | } | |
158 | ||
159 | ||
160 | ||
161 | template<class LeftT, class RightT> | |
162 | typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>, | |
163 | is_total<LeftT> >, | |
164 | bool>::type | |
165 | contains(const LeftT&, const RightT&) | |
166 | { | |
167 | return true; | |
168 | } | |
169 | ||
170 | template<class LeftT, class RightT> | |
171 | typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>, | |
172 | mpl::not_<is_total<LeftT> > >, | |
173 | bool>::type | |
174 | contains(const LeftT& super, const RightT& sub) | |
175 | { | |
176 | int result = | |
177 | subset_compare | |
178 | ( | |
179 | super, sub, | |
180 | super.begin(), super.end(), | |
181 | sub.begin(), sub.end() | |
182 | ); | |
183 | return result == inclusion::superset || result == inclusion::equal; | |
184 | } | |
185 | ||
186 | template<class LeftT, class RightT> | |
187 | typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>, | |
188 | bool>::type | |
189 | contains(const LeftT& super, const RightT& sub) | |
190 | { | |
191 | int result = | |
192 | subset_compare | |
193 | ( | |
194 | super, sub, | |
195 | super.begin(), super.end(), | |
196 | sub.begin(), sub.end() | |
197 | ); | |
198 | return result == inclusion::superset || result == inclusion::equal; | |
199 | } | |
200 | ||
201 | template<class IntervalContainerT> | |
202 | bool is_dense(const IntervalContainerT& container, | |
203 | typename IntervalContainerT::const_iterator first, | |
204 | typename IntervalContainerT::const_iterator past) | |
205 | { | |
206 | if(first == container.end()) | |
207 | return true; | |
208 | ||
209 | typename IntervalContainerT::const_iterator it_ = first, next_ = first; | |
210 | ++next_; | |
211 | ||
212 | while(next_ != container.end() && it_ != past) | |
213 | if(!icl::touches(key_value<IntervalContainerT>(it_++), | |
214 | key_value<IntervalContainerT>(next_++))) | |
215 | return false; | |
216 | ||
217 | return true; | |
218 | } | |
219 | ||
220 | } // namespace Interval_Set | |
221 | ||
222 | namespace segmental | |
223 | { | |
224 | ||
225 | template<class Type> | |
226 | inline bool joinable(const Type& _Type, typename Type::iterator& some, typename Type::iterator& next) | |
227 | { | |
228 | // assert: next != end && some++ == next | |
229 | return touches(key_value<Type>(some), key_value<Type>(next)) | |
230 | && co_equal(some, next, &_Type, &_Type); | |
231 | } | |
232 | ||
233 | template<class Type> | |
234 | inline void join_nodes(Type& object, typename Type::iterator& left_, | |
235 | typename Type::iterator& right_) | |
236 | { | |
237 | typedef typename Type::interval_type interval_type; | |
238 | interval_type right_interval = key_value<Type>(right_); | |
239 | object.erase(right_); | |
240 | const_cast<interval_type&>(key_value<Type>(left_)) | |
241 | = hull(key_value<Type>(left_), right_interval); | |
242 | } | |
243 | ||
244 | template<class Type> | |
245 | inline typename Type::iterator | |
246 | join_on_left(Type& object, typename Type::iterator& left_, | |
247 | typename Type::iterator& right_) | |
248 | { | |
249 | //CL typedef typename Type::interval_type interval_type; | |
250 | // both left and right are in the set and they are neighbours | |
251 | BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_))); | |
252 | BOOST_ASSERT(joinable(object, left_, right_)); | |
253 | ||
254 | join_nodes(object, left_, right_); | |
255 | return left_; | |
256 | } | |
257 | ||
258 | template<class Type> | |
259 | inline typename Type::iterator | |
260 | join_on_right(Type& object, typename Type::iterator& left_, | |
261 | typename Type::iterator& right_) | |
262 | { | |
263 | //CL typedef typename Type::interval_type interval_type; | |
264 | // both left and right are in the map and they are neighbours | |
265 | BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_))); | |
266 | BOOST_ASSERT(joinable(object, left_, right_)); | |
267 | ||
268 | join_nodes(object, left_, right_); | |
269 | right_ = left_; | |
270 | return right_; | |
271 | } | |
272 | ||
273 | template<class Type> | |
274 | typename Type::iterator join_left(Type& object, typename Type::iterator& it_) | |
275 | { | |
276 | typedef typename Type::iterator iterator; | |
277 | ||
278 | if(it_ == object.begin()) | |
279 | return it_; | |
280 | ||
281 | // there is a predecessor | |
282 | iterator pred_ = it_; | |
283 | if(joinable(object, --pred_, it_)) | |
284 | return join_on_right(object, pred_, it_); | |
285 | ||
286 | return it_; | |
287 | } | |
288 | ||
289 | template<class Type> | |
290 | typename Type::iterator join_right(Type& object, typename Type::iterator& it_) | |
291 | { | |
292 | typedef typename Type::iterator iterator; | |
293 | ||
294 | if(it_ == object.end()) | |
295 | return it_; | |
296 | ||
297 | // there is a successor | |
298 | iterator succ_ = it_; | |
299 | ||
300 | if(++succ_ != object.end() && joinable(object, it_, succ_)) | |
301 | return join_on_left(object, it_, succ_); | |
302 | ||
303 | return it_; | |
304 | } | |
305 | ||
306 | template<class Type> | |
307 | typename Type::iterator join_neighbours(Type& object, typename Type::iterator& it_) | |
308 | { | |
309 | join_left (object, it_); | |
310 | return join_right(object, it_); | |
311 | } | |
312 | ||
313 | template<class Type> | |
314 | inline typename Type::iterator | |
315 | join_under(Type& object, const typename Type::value_type& addend) | |
316 | { | |
317 | //ASSERT: There is at least one interval in object that overlaps with addend | |
318 | typedef typename Type::iterator iterator; | |
319 | typedef typename Type::interval_type interval_type; | |
320 | typedef typename Type::value_type value_type; | |
321 | ||
322 | std::pair<iterator,iterator> overlap = object.equal_range(addend); | |
323 | iterator first_ = overlap.first, | |
324 | end_ = overlap.second, | |
325 | last_ = end_; --last_; | |
326 | ||
327 | iterator second_= first_; ++second_; | |
328 | ||
329 | interval_type left_resid = right_subtract(key_value<Type>(first_), addend); | |
330 | interval_type right_resid = left_subtract(key_value<Type>(last_) , addend); | |
331 | ||
332 | object.erase(second_, end_); | |
333 | ||
334 | const_cast<value_type&>(key_value<Type>(first_)) | |
335 | = hull(hull(left_resid, addend), right_resid); | |
336 | return first_; | |
337 | } | |
338 | ||
339 | template<class Type> | |
340 | inline typename Type::iterator | |
341 | join_under(Type& object, const typename Type::value_type& addend, | |
342 | typename Type::iterator last_) | |
343 | { | |
344 | //ASSERT: There is at least one interval in object that overlaps with addend | |
345 | typedef typename Type::iterator iterator; | |
346 | typedef typename Type::interval_type interval_type; | |
347 | typedef typename Type::value_type value_type; | |
348 | ||
349 | iterator first_ = object.lower_bound(addend); | |
350 | //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val)); | |
351 | iterator second_= boost::next(first_), end_ = boost::next(last_); | |
352 | ||
353 | interval_type left_resid = right_subtract(key_value<Type>(first_), addend); | |
354 | interval_type right_resid = left_subtract(key_value<Type>(last_) , addend); | |
355 | ||
356 | object.erase(second_, end_); | |
357 | ||
358 | const_cast<value_type&>(key_value<Type>(first_)) | |
359 | = hull(hull(left_resid, addend), right_resid); | |
360 | return first_; | |
361 | } | |
362 | ||
363 | } // namespace segmental | |
364 | ||
365 | namespace Interval_Set | |
366 | { | |
367 | using namespace segmental; | |
368 | ||
369 | template<class Type, int combining_style> | |
370 | struct on_style; | |
371 | ||
372 | template<class Type> | |
373 | struct on_style<Type, interval_combine::joining> | |
374 | { | |
375 | typedef on_style type; | |
376 | typedef typename Type::interval_type interval_type; | |
377 | typedef typename Type::iterator iterator; | |
378 | ||
379 | inline static iterator handle_inserted(Type& object, iterator inserted_) | |
380 | { return join_neighbours(object, inserted_); } | |
381 | ||
382 | inline static iterator add_over | |
383 | (Type& object, const interval_type& addend, iterator last_) | |
384 | { | |
385 | iterator joined_ = join_under(object, addend, last_); | |
386 | return join_neighbours(object, joined_); | |
387 | } | |
388 | ||
389 | inline static iterator add_over | |
390 | (Type& object, const interval_type& addend) | |
391 | { | |
392 | iterator joined_ = join_under(object, addend); | |
393 | return join_neighbours(object, joined_); | |
394 | } | |
395 | }; | |
396 | ||
397 | template<class Type> | |
398 | struct on_style<Type, interval_combine::separating> | |
399 | { | |
400 | typedef on_style type; | |
401 | typedef typename Type::interval_type interval_type; | |
402 | typedef typename Type::iterator iterator; | |
403 | ||
404 | inline static iterator handle_inserted(Type&, iterator inserted_) | |
405 | { return inserted_; } | |
406 | ||
407 | inline static iterator add_over | |
408 | (Type& object, const interval_type& addend, iterator last_) | |
409 | { | |
410 | return join_under(object, addend, last_); | |
411 | } | |
412 | ||
413 | inline static iterator add_over | |
414 | (Type& object, const interval_type& addend) | |
415 | { | |
416 | return join_under(object, addend); | |
417 | } | |
418 | }; | |
419 | ||
420 | template<class Type> | |
421 | struct on_style<Type, interval_combine::splitting> | |
422 | { | |
423 | typedef on_style type; | |
424 | typedef typename Type::interval_type interval_type; | |
425 | typedef typename Type::iterator iterator; | |
426 | ||
427 | inline static iterator handle_inserted(Type&, iterator inserted_) | |
428 | { return inserted_; } | |
429 | ||
430 | inline static iterator add_over | |
431 | (Type& object, const interval_type& addend, iterator last_) | |
432 | { | |
433 | iterator first_ = object.lower_bound(addend); | |
434 | //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val)); | |
435 | ||
436 | iterator it_ = first_; | |
437 | interval_type rest_interval = addend; | |
438 | ||
439 | add_front(object, rest_interval, it_); | |
440 | add_main (object, rest_interval, it_, last_); | |
441 | add_rear (object, rest_interval, it_); | |
442 | return it_; | |
443 | } | |
444 | ||
445 | inline static iterator add_over | |
446 | (Type& object, const interval_type& addend) | |
447 | { | |
448 | std::pair<iterator,iterator> overlap = object.equal_range(addend); | |
449 | iterator first_ = overlap.first, | |
450 | end_ = overlap.second, | |
451 | last_ = end_; --last_; | |
452 | ||
453 | iterator it_ = first_; | |
454 | interval_type rest_interval = addend; | |
455 | ||
456 | add_front(object, rest_interval, it_); | |
457 | add_main (object, rest_interval, it_, last_); | |
458 | add_rear (object, rest_interval, it_); | |
459 | ||
460 | return it_; | |
461 | } | |
462 | }; | |
463 | ||
464 | ||
465 | template<class Type> | |
466 | void add_front(Type& object, const typename Type::interval_type& inter_val, | |
467 | typename Type::iterator& first_) | |
468 | { | |
469 | typedef typename Type::interval_type interval_type; | |
470 | typedef typename Type::iterator iterator; | |
471 | // If the collision sequence has a left residual 'left_resid' it will | |
472 | // be split, to provide a standardized start of algorithms: | |
473 | // The addend interval 'inter_val' covers the beginning of the collision sequence. | |
474 | ||
475 | // only for the first there can be a left_resid: a part of *first_ left of inter_val | |
476 | interval_type left_resid = right_subtract(key_value<Type>(first_), inter_val); | |
477 | ||
478 | if(!icl::is_empty(left_resid)) | |
479 | { // [------------ . . . | |
480 | // [left_resid---first_ --- . . . | |
481 | iterator prior_ = cyclic_prior(object, first_); | |
482 | const_cast<interval_type&>(key_value<Type>(first_)) | |
483 | = left_subtract(key_value<Type>(first_), left_resid); | |
484 | //NOTE: Only splitting | |
485 | object._insert(prior_, icl::make_value<Type>(left_resid, co_value<Type>(first_))); | |
486 | } | |
487 | ||
488 | //POST: | |
489 | // [----- inter_val ---- . . . | |
490 | // ...[-- first_ --... | |
491 | } | |
492 | ||
493 | ||
494 | template<class Type> | |
495 | void add_segment(Type& object, const typename Type::interval_type& inter_val, | |
496 | typename Type::iterator& it_ ) | |
497 | { | |
498 | typedef typename Type::interval_type interval_type; | |
499 | interval_type lead_gap = right_subtract(inter_val, *it_); | |
500 | if(!icl::is_empty(lead_gap)) | |
501 | // [lead_gap--- . . . | |
502 | // [prior_) [-- it_ ... | |
503 | object._insert(prior(it_), lead_gap); | |
504 | ||
505 | // . . . --------- . . . addend interval | |
506 | // [-- it_ --) has a common part with the first overval | |
507 | ++it_; | |
508 | } | |
509 | ||
510 | ||
511 | template<class Type> | |
512 | void add_main(Type& object, typename Type::interval_type& rest_interval, | |
513 | typename Type::iterator& it_, | |
514 | const typename Type::iterator& last_) | |
515 | { | |
516 | typedef typename Type::interval_type interval_type; | |
517 | interval_type cur_interval; | |
518 | while(it_ != last_) | |
519 | { | |
520 | cur_interval = *it_ ; | |
521 | add_segment(object, rest_interval, it_); | |
522 | // shrink interval | |
523 | rest_interval = left_subtract(rest_interval, cur_interval); | |
524 | } | |
525 | } | |
526 | ||
527 | ||
528 | template<class Type> | |
529 | void add_rear(Type& object, const typename Type::interval_type& inter_val, | |
530 | typename Type::iterator& it_ ) | |
531 | { | |
532 | typedef typename Type::interval_type interval_type; | |
533 | typedef typename Type::iterator iterator; | |
534 | ||
535 | iterator prior_ = cyclic_prior(object, it_); | |
536 | interval_type cur_itv = *it_; | |
537 | ||
538 | interval_type lead_gap = right_subtract(inter_val, cur_itv); | |
539 | if(!icl::is_empty(lead_gap)) | |
540 | // [lead_gap--- . . . | |
541 | // [prior_) [-- it_ ... | |
542 | object._insert(prior_, lead_gap); | |
543 | ||
544 | interval_type end_gap = left_subtract(inter_val, cur_itv); | |
545 | if(!icl::is_empty(end_gap)) | |
546 | // [---------------end_gap) | |
547 | // [-- it_ --) | |
548 | it_ = object._insert(it_, end_gap); | |
549 | else | |
550 | { | |
551 | // only for the last there can be a right_resid: a part of *it_ right of addend | |
552 | interval_type right_resid = left_subtract(cur_itv, inter_val); | |
553 | ||
554 | if(!icl::is_empty(right_resid)) | |
555 | { | |
556 | // [--------------) | |
557 | // [-- it_ --right_resid) | |
558 | const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid); | |
559 | it_ = object._insert(it_, right_resid); | |
560 | } | |
561 | } | |
562 | } | |
563 | ||
564 | ||
565 | //============================================================================== | |
566 | //= Addition | |
567 | //============================================================================== | |
568 | template<class Type> | |
569 | typename Type::iterator | |
570 | add(Type& object, const typename Type::value_type& addend) | |
571 | { | |
572 | //CL typedef typename Type::interval_type interval_type; | |
573 | typedef typename Type::iterator iterator; | |
574 | typedef typename on_style<Type, Type::fineness>::type on_style_; | |
575 | ||
576 | if(icl::is_empty(addend)) | |
577 | return object.end(); | |
578 | ||
579 | std::pair<iterator,bool> insertion = object._insert(addend); | |
580 | ||
581 | if(insertion.second) | |
582 | return on_style_::handle_inserted(object, insertion.first); | |
583 | else | |
584 | return on_style_::add_over(object, addend, insertion.first); | |
585 | } | |
586 | ||
587 | ||
588 | template<class Type> | |
589 | typename Type::iterator | |
590 | add(Type& object, typename Type::iterator prior_, | |
591 | const typename Type::value_type& addend) | |
592 | { | |
593 | //CL typedef typename Type::interval_type interval_type; | |
594 | typedef typename Type::iterator iterator; | |
595 | typedef typename on_style<Type, Type::fineness>::type on_style_; | |
596 | ||
597 | if(icl::is_empty(addend)) | |
598 | return prior_; | |
599 | ||
600 | iterator insertion = object._insert(prior_, addend); | |
601 | ||
602 | if(*insertion == addend) | |
603 | return on_style_::handle_inserted(object, insertion); | |
604 | else | |
605 | return on_style_::add_over(object, addend); | |
606 | } | |
607 | ||
608 | ||
609 | //============================================================================== | |
610 | //= Subtraction | |
611 | //============================================================================== | |
612 | template<class Type> | |
613 | void subtract(Type& object, const typename Type::value_type& minuend) | |
614 | { | |
615 | typedef typename Type::iterator iterator; | |
616 | typedef typename Type::interval_type interval_type; | |
617 | //CL typedef typename Type::value_type value_type; | |
618 | ||
619 | if(icl::is_empty(minuend)) return; | |
620 | ||
621 | std::pair<iterator, iterator> exterior = object.equal_range(minuend); | |
622 | if(exterior.first == exterior.second) return; | |
623 | ||
624 | iterator first_ = exterior.first; | |
625 | iterator end_ = exterior.second; | |
626 | iterator last_ = end_; --last_; | |
627 | ||
628 | interval_type leftResid = right_subtract(*first_, minuend); | |
629 | interval_type rightResid; | |
630 | if(first_ != end_ ) | |
631 | rightResid = left_subtract(*last_ , minuend); | |
632 | ||
633 | object.erase(first_, end_); | |
634 | ||
635 | if(!icl::is_empty(leftResid)) | |
636 | object._insert(leftResid); | |
637 | ||
638 | if(!icl::is_empty(rightResid)) | |
639 | object._insert(rightResid); | |
640 | } | |
641 | ||
642 | ||
643 | } // namespace Interval_Set | |
644 | ||
645 | }} // namespace icl boost | |
646 | ||
647 | #endif | |
648 |