1 /*-----------------------------------------------------------------------------+
2 Copyright (c) 2010-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_CONCEPT_INTERVAL_ASSOCIATOR_HPP_JOFA_100920
9 #define BOOST_ICL_CONCEPT_INTERVAL_ASSOCIATOR_HPP_JOFA_100920
10 
11 #include <boost/range/iterator_range.hpp>
12 #include <boost/icl/type_traits/domain_type_of.hpp>
13 #include <boost/icl/type_traits/interval_type_of.hpp>
14 #include <boost/icl/type_traits/is_combinable.hpp>
15 #include <boost/icl/detail/set_algo.hpp>
16 #include <boost/icl/detail/map_algo.hpp>
17 #include <boost/icl/detail/interval_set_algo.hpp>
18 #include <boost/icl/detail/interval_map_algo.hpp>
19 #include <boost/icl/concept/interval.hpp>
20 
21 namespace boost{ namespace icl
22 {
23 
24 //==============================================================================
25 //= Containedness<IntervalSet|IntervalMap>
26 //==============================================================================
27 //------------------------------------------------------------------------------
28 //- bool within(c T&, c P&) T={Set,Map} P={e i b p S M}
29 //------------------------------------------------------------------------------
30 template<class SubT, class SuperT>
31 typename enable_if<is_interval_container<SuperT>, bool>::type
within(const SubT & sub,const SuperT & super)32 within(const SubT& sub, const SuperT& super)
33 {
34     return icl::contains(super, sub);
35 }
36 
37 //==============================================================================
38 //= Equivalences and Orderings<IntervalSet|IntervalMap>
39 //==============================================================================
40 template<class Type>
41 inline typename enable_if<is_interval_container<Type>, bool>::type
operator ==(const Type & left,const Type & right)42 operator == (const Type& left, const Type& right)
43 {
44     return Set::lexicographical_equal(left, right);
45 }
46 
47 template<class Type>
48 inline typename enable_if<is_interval_container<Type>, bool>::type
operator <(const Type & left,const Type & right)49 operator < (const Type& left, const Type& right)
50 {
51     typedef typename Type::segment_compare segment_compare;
52     return std::lexicographical_compare(
53         left.begin(), left.end(), right.begin(), right.end(),
54         segment_compare()
55         );
56 }
57 
58 /** Returns true, if \c left and \c right contain the same elements.
59     Complexity: linear. */
60 template<class LeftT, class RightT>
61 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
is_element_equal(const LeftT & left,const RightT & right)62 is_element_equal(const LeftT& left, const RightT& right)
63 {
64     return Interval_Set::is_element_equal(left, right);
65 }
66 
67 /** Returns true, if \c left is lexicographically less than \c right.
68     Intervals are interpreted as sequence of elements.
69     Complexity: linear. */
70 template<class LeftT, class RightT>
71 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
is_element_less(const LeftT & left,const RightT & right)72 is_element_less(const LeftT& left, const RightT& right)
73 {
74     return Interval_Set::is_element_less(left, right);
75 }
76 
77 /** Returns true, if \c left is lexicographically greater than \c right.
78     Intervals are interpreted as sequence of elements.
79     Complexity: linear. */
80 template<class LeftT, class RightT>
81 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
is_element_greater(const LeftT & left,const RightT & right)82 is_element_greater(const LeftT& left, const RightT& right)
83 {
84     return Interval_Set::is_element_greater(left, right);
85 }
86 
87 //------------------------------------------------------------------------------
88 template<class LeftT, class RightT>
89 typename enable_if<is_inter_combinable<LeftT, RightT>, int>::type
inclusion_compare(const LeftT & left,const RightT & right)90 inclusion_compare(const LeftT& left, const RightT& right)
91 {
92     return Interval_Set::subset_compare(left, right,
93                                         left.begin(), left.end(),
94                                         right.begin(), right.end());
95 }
96 
97 //------------------------------------------------------------------------------
98 template<class LeftT, class RightT>
99 typename enable_if< is_concept_compatible<is_interval_map, LeftT, RightT>,
100                     bool >::type
is_distinct_equal(const LeftT & left,const RightT & right)101 is_distinct_equal(const LeftT& left, const RightT& right)
102 {
103     return Map::lexicographical_distinct_equal(left, right);
104 }
105 
106 //==============================================================================
107 //= Size<IntervalSet|IntervalMap>
108 //==============================================================================
109 template<class Type>
110 typename enable_if<is_interval_container<Type>, std::size_t>::type
iterative_size(const Type & object)111 iterative_size(const Type& object)
112 {
113     return object.iterative_size();
114 }
115 
116 template<class Type>
117 typename enable_if
118 < mpl::and_< is_interval_container<Type>
119            , is_discrete<typename Type::domain_type> >
120 , typename Type::size_type
121 >::type
cardinality(const Type & object)122 cardinality(const Type& object)
123 {
124     typedef typename Type::size_type size_type;
125     //CL typedef typename Type::interval_type interval_type;
126 
127     size_type size = identity_element<size_type>::value();
128     ICL_const_FORALL(typename Type, it, object)
129         size += icl::cardinality(key_value<Type>(it));
130     return size;
131 
132 }
133 
134 template<class Type>
135 typename enable_if
136 < mpl::and_< is_interval_container<Type>
137            , mpl::not_<is_discrete<typename Type::domain_type> > >
138 , typename Type::size_type
139 >::type
cardinality(const Type & object)140 cardinality(const Type& object)
141 {
142     typedef typename Type::size_type size_type;
143     //CL typedef typename Type::interval_type interval_type;
144 
145     size_type size = identity_element<size_type>::value();
146     size_type interval_size;
147     ICL_const_FORALL(typename Type, it, object)
148     {
149         interval_size = icl::cardinality(key_value<Type>(it));
150         if(interval_size == icl::infinity<size_type>::value())
151             return interval_size;
152         else
153             size += interval_size;
154     }
155     return size;
156 }
157 
158 template<class Type>
159 inline typename enable_if<is_interval_container<Type>, typename Type::size_type>::type
size(const Type & object)160 size(const Type& object)
161 {
162     return icl::cardinality(object);
163 }
164 
165 template<class Type>
166 typename enable_if<is_interval_container<Type>, typename Type::difference_type>::type
length(const Type & object)167 length(const Type& object)
168 {
169     typedef typename Type::difference_type difference_type;
170     typedef typename Type::const_iterator  const_iterator;
171     difference_type length = identity_element<difference_type>::value();
172     const_iterator it_ = object.begin();
173 
174     while(it_ != object.end())
175         length += icl::length(key_value<Type>(it_++));
176     return length;
177 }
178 
179 template<class Type>
180 typename enable_if<is_interval_container<Type>, std::size_t>::type
interval_count(const Type & object)181 interval_count(const Type& object)
182 {
183     return icl::iterative_size(object);
184 }
185 
186 
187 template<class Type>
188 typename enable_if< is_interval_container<Type>
189                   , typename Type::difference_type >::type
distance(const Type & object)190 distance(const Type& object)
191 {
192     typedef typename Type::difference_type DiffT;
193     typedef typename Type::const_iterator const_iterator;
194     const_iterator it_ = object.begin(), pred_;
195     DiffT dist = identity_element<DiffT>::value();
196 
197     if(it_ != object.end())
198         pred_ = it_++;
199 
200     while(it_ != object.end())
201         dist += icl::distance(key_value<Type>(pred_++), key_value<Type>(it_++));
202 
203     return dist;
204 }
205 
206 //==============================================================================
207 //= Range<IntervalSet|IntervalMap>
208 //==============================================================================
209 template<class Type>
210 typename enable_if<is_interval_container<Type>,
211                    typename Type::interval_type>::type
hull(const Type & object)212 hull(const Type& object)
213 {
214     return
215         icl::is_empty(object)
216             ? identity_element<typename Type::interval_type>::value()
217             : icl::hull( key_value<Type>(object.begin()),
218                          key_value<Type>(object.rbegin()) );
219 }
220 
221 template<class Type>
222 typename enable_if<is_interval_container<Type>,
223                    typename domain_type_of<Type>::type>::type
lower(const Type & object)224 lower(const Type& object)
225 {
226     typedef typename domain_type_of<Type>::type DomainT;
227     return
228         icl::is_empty(object)
229             ? unit_element<DomainT>::value()
230             : icl::lower( key_value<Type>(object.begin()) );
231 }
232 
233 template<class Type>
234 typename enable_if<is_interval_container<Type>,
235                    typename domain_type_of<Type>::type>::type
upper(const Type & object)236 upper(const Type& object)
237 {
238     typedef typename domain_type_of<Type>::type DomainT;
239     return
240         icl::is_empty(object)
241             ? identity_element<DomainT>::value()
242             : icl::upper( key_value<Type>(object.rbegin()) );
243 }
244 
245 //------------------------------------------------------------------------------
246 template<class Type>
247 typename enable_if
248 < mpl::and_< is_interval_container<Type>
249            , is_discrete<typename domain_type_of<Type>::type> >
250 , typename domain_type_of<Type>::type>::type
first(const Type & object)251 first(const Type& object)
252 {
253     typedef typename domain_type_of<Type>::type DomainT;
254     return
255         icl::is_empty(object)
256             ? unit_element<DomainT>::value()
257             : icl::first( key_value<Type>(object.begin()) );
258 }
259 
260 template<class Type>
261 typename enable_if
262 < mpl::and_< is_interval_container<Type>
263            , is_discrete<typename domain_type_of<Type>::type> >
264 , typename domain_type_of<Type>::type>::type
last(const Type & object)265 last(const Type& object)
266 {
267     typedef typename domain_type_of<Type>::type DomainT;
268     return
269         icl::is_empty(object)
270             ? identity_element<DomainT>::value()
271             : icl::last( key_value<Type>(object.rbegin()) );
272 }
273 
274 
275 //==============================================================================
276 //= Addition<IntervalSet|IntervalMap>
277 //==============================================================================
278 //------------------------------------------------------------------------------
279 //- T& op +=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
280 //------------------------------------------------------------------------------
281 /* \par \b Requires: \c OperandT is an addable derivative type of \c Type.
282     \b Effects: \c operand is added to \c object.
283     \par \b Returns: A reference to \c object.
284     \b Complexity:
285 \code
286                   \ OperandT:
287                    \         element     segment
288 Type:
289        interval container    O(log n)     O(n)
290 
291              interval_set               amortized
292     spearate_interval_set                O(log n)
293 
294 n = object.interval_count()
295 \endcode
296 
297 For the addition of \b elements or \b segments
298 complexity is \b logarithmic or \b linear respectively.
299 For \c interval_sets and \c separate_interval_sets addition of segments
300 is \b amortized \b logarithmic.
301 */
302 template<class Type, class OperandT>
303 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
operator +=(Type & object,const OperandT & operand)304 operator += (Type& object, const OperandT& operand)
305 {
306     return icl::add(object, operand);
307 }
308 
309 
310 //------------------------------------------------------------------------------
311 //- T& op +=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
312 //------------------------------------------------------------------------------
313 /** \par \b Requires: \c OperandT is an interval container addable to \c Type.
314     \b Effects: \c operand is added to \c object.
315     \par \b Returns: A reference to \c object.
316     \b Complexity: loglinear */
317 template<class Type, class OperandT>
318 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
operator +=(Type & object,const OperandT & operand)319 operator += (Type& object, const OperandT& operand)
320 {
321     typename Type::iterator prior_ = object.end();
322     ICL_const_FORALL(typename OperandT, elem_, operand)
323         prior_ = icl::add(object, prior_, *elem_);
324 
325     return object;
326 }
327 
328 
329 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
330 //------------------------------------------------------------------------------
331 //- T op + (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
332 //------------------------------------------------------------------------------
333 /** \par \b Requires: \c object and \c operand are addable.
334     \b Effects: \c operand is added to \c object.
335     \par \b Efficieny: There is one additional copy of
336     \c Type \c object compared to inplace \c operator \c += */
337 template<class Type, class OperandT>
338 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(Type object,const OperandT & operand)339 operator + (Type object, const OperandT& operand)
340 {
341     return object += operand;
342 }
343 
344 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
345 
346 template<class Type, class OperandT>
347 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(const Type & object,const OperandT & operand)348 operator + (const Type& object, const OperandT& operand)
349 {
350     Type temp = object;
351     return boost::move(temp += operand);
352 }
353 
354 template<class Type, class OperandT>
355 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(Type && object,const OperandT & operand)356 operator + (Type&& object, const OperandT& operand)
357 {
358     return boost::move(object += operand);
359 }
360 
361 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
362 
363 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
364 //------------------------------------------------------------------------------
365 //- T op + (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'}
366 //------------------------------------------------------------------------------
367 /** \par \b Requires: \c object and \c operand are addable.
368     \b Effects: \c operand is added to \c object.
369     \par \b Efficieny: There is one additional copy of
370     \c Type \c object compared to inplace \c operator \c += */
371 template<class Type, class OperandT>
372 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(const OperandT & operand,Type object)373 operator + (const OperandT& operand, Type object)
374 {
375     return object += operand;
376 }
377 
378 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
379 
380 template<class Type, class OperandT>
381 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(const OperandT & operand,const Type & object)382 operator + (const OperandT& operand, const Type& object)
383 {
384     Type temp = object;
385     return boost::move(temp += operand);
386 }
387 
388 template<class Type, class OperandT>
389 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(const OperandT & operand,Type && object)390 operator + (const OperandT& operand, Type&& object)
391 {
392     return boost::move(object += operand);
393 }
394 
395 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
396 
397 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
398 //------------------------------------------------------------------------------
399 //- T op + (T, c P&) T:{S}|{M} P:{S}|{M}
400 //------------------------------------------------------------------------------
401 /** \par \b Requires: \c object and \c operand are addable.
402     \b Effects: \c operand is added to \c object.
403     \par \b Efficieny: There is one additional copy of
404     \c Type \c object compared to inplace \c operator \c += */
405 template<class Type>
406 typename enable_if<is_interval_container<Type>, Type>::type
operator +(Type object,const Type & operand)407 operator + (Type object, const Type& operand)
408 {
409     return object += operand;
410 }
411 
412 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
413 
414 template<class Type>
415 typename enable_if<is_interval_container<Type>, Type>::type
operator +(const Type & object,const Type & operand)416 operator + (const Type& object, const Type& operand)
417 {
418     Type temp = object;
419     return boost::move(temp += operand);
420 }
421 
422 template<class Type>
423 typename enable_if<is_interval_container<Type>, Type>::type
operator +(Type && object,const Type & operand)424 operator + (Type&& object, const Type& operand)
425 {
426     return boost::move(object += operand);
427 }
428 
429 template<class Type>
430 typename enable_if<is_interval_container<Type>, Type>::type
operator +(const Type & operand,Type && object)431 operator + (const Type& operand, Type&& object)
432 {
433     return boost::move(object += operand);
434 }
435 
436 template<class Type>
437 typename enable_if<is_interval_container<Type>, Type>::type
operator +(Type && object,Type && operand)438 operator + (Type&& object, Type&& operand)
439 {
440     return boost::move(object += operand);
441 }
442 
443 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
444 
445 //------------------------------------------------------------------------------
446 //- Addition |=, |
447 //------------------------------------------------------------------------------
448 
449 //------------------------------------------------------------------------------
450 //- T& op |=(c P&) T:{S}|{M} P:{e i}|{b p}
451 //------------------------------------------------------------------------------
452 /** \par \b Requires: Types \c Type and \c OperandT are addable.
453     \par \b Effects: \c operand is added to \c object.
454     \par \b Returns: A reference to \c object.
455     \b Complexity:
456 \code
457                   \ OperandT:                      interval
458                    \         element     segment   container
459 Type:
460        interval container    O(log n)     O(n)     O(m log(n+m))
461 
462              interval_set               amortized
463     spearate_interval_set                O(log n)
464 
465 n = object.interval_count()
466 m = operand.interval_count()
467 \endcode
468 
469 For the addition of \b elements, \b segments and \b interval \b containers
470 complexity is \b logarithmic, \b linear and \b loglinear respectively.
471 For \c interval_sets and \c separate_interval_sets addition of segments
472 is \b amortized \b logarithmic.
473 */
474 template<class Type, class OperandT>
475 typename enable_if<is_right_intra_combinable<Type, OperandT>, Type>::type&
operator |=(Type & object,const OperandT & operand)476 operator |= (Type& object, const OperandT& operand)
477 {
478     return object += operand;
479 }
480 
481 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
482 //------------------------------------------------------------------------------
483 //- T op | (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
484 //------------------------------------------------------------------------------
485 /** \par \b Requires: \c object and \c operand are addable.
486     \b Effects: \c operand is added to \c object.
487     \par \b Efficieny: There is one additional copy of
488     \c Type \c object compared to inplace \c operator \c |= */
489 template<class Type, class OperandT>
490 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(Type object,const OperandT & operand)491 operator | (Type object, const OperandT& operand)
492 {
493     return object += operand;
494 }
495 
496 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
497 
498 template<class Type, class OperandT>
499 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(const Type & object,const OperandT & operand)500 operator | (const Type& object, const OperandT& operand)
501 {
502     Type temp = object;
503     return boost::move(temp += operand);
504 }
505 
506 template<class Type, class OperandT>
507 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(Type && object,const OperandT & operand)508 operator | (Type&& object, const OperandT& operand)
509 {
510     return boost::move(object += operand);
511 }
512 
513 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
514 
515 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
516 //------------------------------------------------------------------------------
517 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
518 //------------------------------------------------------------------------------
519 /** \par \b Requires: \c object and \c operand are addable.
520     \b Effects: \c operand is added to \c object.
521     \par \b Efficieny: There is one additional copy of
522     \c Type \c object compared to inplace \c operator \c |= */
523 template<class Type, class OperandT>
524 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(const OperandT & operand,Type object)525 operator | (const OperandT& operand, Type object)
526 {
527     return object += operand;
528 }
529 
530 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
531 
532 template<class Type, class OperandT>
533 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(const OperandT & operand,const Type & object)534 operator | (const OperandT& operand, const Type& object)
535 {
536     Type temp = object;
537     return boost::move(temp += operand);
538 }
539 
540 template<class Type, class OperandT>
541 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(const OperandT & operand,Type && object)542 operator | (const OperandT& operand, Type&& object)
543 {
544     return boost::move(object += operand);
545 }
546 
547 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
548 
549 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
550 //------------------------------------------------------------------------------
551 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
552 //------------------------------------------------------------------------------
553 /** \par \b Requires: \c object and \c operand are addable.
554     \b Effects: \c operand is added to \c object.
555     \par \b Efficieny: There is one additional copy of
556     \c Type \c object compared to inplace \c operator \c |= */
557 template<class Type>
558 typename enable_if<is_interval_container<Type>, Type>::type
operator |(Type object,const Type & operand)559 operator | (Type object, const Type& operand)
560 {
561     return object += operand;
562 }
563 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
564 
565 template<class Type>
566 typename enable_if<is_interval_container<Type>, Type>::type
operator |(const Type & object,const Type & operand)567 operator | (const Type& object, const Type& operand)
568 {
569     Type temp = object;
570     return boost::move(temp += operand);
571 }
572 
573 template<class Type>
574 typename enable_if<is_interval_container<Type>, Type>::type
operator |(Type && object,const Type & operand)575 operator | (Type&& object, const Type& operand)
576 {
577     return boost::move(object += operand);
578 }
579 
580 template<class Type>
581 typename enable_if<is_interval_container<Type>, Type>::type
operator |(const Type & operand,Type && object)582 operator | (const Type& operand, Type&& object)
583 {
584     return boost::move(object += operand);
585 }
586 
587 template<class Type>
588 typename enable_if<is_interval_container<Type>, Type>::type
operator |(Type && object,Type && operand)589 operator | (Type&& object, Type&& operand)
590 {
591     return boost::move(object += operand);
592 }
593 
594 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
595 
596 
597 //==============================================================================
598 //= Insertion<IntervalSet|IntervalSet>
599 //==============================================================================
600 //------------------------------------------------------------------------------
601 //- T& insert(T&, c P&) T:{S}|{M} P:{S'}|{M'}
602 //------------------------------------------------------------------------------
603 template<class Type, class OperandT>
604 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
insert(Type & object,const OperandT & operand)605 insert(Type& object, const OperandT& operand)
606 {
607     typename Type::iterator prior_ = object.end();
608     ICL_const_FORALL(typename OperandT, elem_, operand)
609         insert(object, prior_, *elem_);
610 
611     return object;
612 }
613 
614 //==============================================================================
615 //= Erasure<IntervalSet|IntervalSet>
616 //==============================================================================
617 //------------------------------------------------------------------------------
618 //- T& erase(T&, c P&) T:{S}|{M} P:{S'}|{S' M'}
619 //------------------------------------------------------------------------------
620 template<class Type, class OperandT>
621 typename enable_if<combines_right_to_interval_container<Type, OperandT>,
622                    Type>::type&
erase(Type & object,const OperandT & operand)623 erase(Type& object, const OperandT& operand)
624 {
625     typedef typename OperandT::const_iterator const_iterator;
626 
627     if(icl::is_empty(operand))
628         return object;
629 
630     const_iterator common_lwb, common_upb;
631     if(!Set::common_range(common_lwb, common_upb, operand, object))
632         return object;
633 
634     const_iterator it_ = common_lwb;
635     while(it_ != common_upb)
636         icl::erase(object, *it_++);
637 
638     return object;
639 }
640 
641 //==============================================================================
642 //= Subtraction<IntervalSet|IntervalSet>
643 //==============================================================================
644 //------------------------------------------------------------------------------
645 //- T& op -= (c P&) T:{M} P:{M'}
646 //------------------------------------------------------------------------------
647 /** \par \b Requires: Types \c Type and \c OperandT are subtractable.
648     \par \b Effects: \c operand is subtracted from \c object.
649     \par \b Returns: A reference to \c object.
650     \b Complexity:
651 \code
652                   \ OperandT:                      interval
653                    \         element    segment    container
654 Type:
655        interval container    O(log n)     O(n)     O(m log(n+m))
656 
657                                        amortized
658             interval_sets               O(log n)
659 
660 n = object.interval_count()
661 m = operand.interval_count()
662 \endcode
663 
664 For the subtraction of \em elements, \b segments and \b interval \b containers
665 complexity is \b logarithmic, \b linear and \b loglinear respectively.
666 For interval sets subtraction of segments
667 is \b amortized \b logarithmic.
668 */
669 template<class Type, class OperandT>
670 typename enable_if<is_concept_compatible<is_interval_map, Type, OperandT>,
671                    Type>::type&
operator -=(Type & object,const OperandT & operand)672 operator -=(Type& object, const OperandT& operand)
673 {
674     ICL_const_FORALL(typename OperandT, elem_, operand)
675         icl::subtract(object, *elem_);
676 
677     return object;
678 }
679 
680 //------------------------------------------------------------------------------
681 //- T& op -= (c P&) T:{S}|{M} P:{e i}|{b p}
682 //------------------------------------------------------------------------------
683 template<class Type, class OperandT>
684 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
operator -=(Type & object,const OperandT & operand)685 operator -= (Type& object, const OperandT& operand)
686 {
687     return icl::subtract(object, operand);
688 }
689 
690 //------------------------------------------------------------------------------
691 //- T& op -= (c P&) T:{M} P:{e i}
692 //------------------------------------------------------------------------------
693 template<class Type, class OperandT>
694 typename enable_if<is_cross_derivative<Type, OperandT>, Type>::type&
operator -=(Type & object,const OperandT & operand)695 operator -= (Type& object, const OperandT& operand)
696 {
697     return icl::erase(object, operand);
698 }
699 
700 //------------------------------------------------------------------------------
701 //- T& op -= (c P&) T:{S M} P:{S'}
702 //------------------------------------------------------------------------------
703 template<class Type, class IntervalSetT>
704 typename enable_if<combines_right_to_interval_set<Type, IntervalSetT>,
705                    Type>::type&
operator -=(Type & object,const IntervalSetT & operand)706 operator -= (Type& object, const IntervalSetT& operand)
707 {
708     return erase(object, operand);
709 }
710 
711 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
712 //------------------------------------------------------------------------------
713 //- T op - (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
714 //------------------------------------------------------------------------------
715 template<class Type, class OperandT>
716 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
operator -(Type object,const OperandT & operand)717 operator - (Type object, const OperandT& operand)
718 {
719     return object -= operand;
720 }
721 
722 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
723 
724 template<class Type, class OperandT>
725 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
operator -(const Type & object,const OperandT & operand)726 operator - (const Type& object, const OperandT& operand)
727 {
728     Type temp = object;
729     return boost::move(temp -= operand);
730 }
731 
732 template<class Type, class OperandT>
733 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
operator -(Type && object,const OperandT & operand)734 operator - (Type&& object, const OperandT& operand)
735 {
736     return boost::move(object -= operand);
737 }
738 
739 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
740 
741 //==============================================================================
742 //= Intersection<IntervalSet|IntervalSet>
743 //==============================================================================
744 //------------------------------------------------------------------------------
745 //- void add_intersection(T&, c T&, c P&) T:{S M} P:{S'}
746 //------------------------------------------------------------------------------
747 template<class Type, class OperandT>
748 typename enable_if<mpl::and_<is_interval_set<Type>,
749                              combines_right_to_interval_set<Type, OperandT> >,
750                    void>::type
add_intersection(Type & section,const Type & object,const OperandT & operand)751 add_intersection(Type& section, const Type& object, const OperandT& operand)
752 {
753     typedef typename OperandT::const_iterator const_iterator;
754 
755     if(operand.empty())
756         return;
757 
758     const_iterator common_lwb, common_upb;
759     if(!Set::common_range(common_lwb, common_upb, operand, object))
760         return;
761 
762     const_iterator it_ = common_lwb;
763     while(it_ != common_upb)
764         icl::add_intersection(section, object, key_value<OperandT>(it_++));
765 }
766 
767 //------------------------------------------------------------------------------
768 //- T& op &=(T&, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
769 //------------------------------------------------------------------------------
770 template<class Type, class OperandT>
771 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type&
operator &=(Type & object,const OperandT & operand)772 operator &= (Type& object, const OperandT& operand)
773 {
774     Type intersection;
775     add_intersection(intersection, object, operand);
776     object.swap(intersection);
777     return object;
778 }
779 
780 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
781 //------------------------------------------------------------------------------
782 //- T op & (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
783 //------------------------------------------------------------------------------
784 template<class Type, class OperandT>
785 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(Type object,const OperandT & operand)786 operator & (Type object, const OperandT& operand)
787 {
788     return object &= operand;
789 }
790 
791 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
792 
793 template<class Type, class OperandT>
794 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(const Type & object,const OperandT & operand)795 operator & (const Type& object, const OperandT& operand)
796 {
797     Type temp = object;
798     return boost::move(temp &= operand);
799 }
800 
801 template<class Type, class OperandT>
802 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(Type && object,const OperandT & operand)803 operator & (Type&& object, const OperandT& operand)
804 {
805     return boost::move(object &= operand);
806 }
807 
808 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
809 
810 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
811 //------------------------------------------------------------------------------
812 //- T op & (c P&, T) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
813 //------------------------------------------------------------------------------
814 template<class Type, class OperandT>
815 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(const OperandT & operand,Type object)816 operator & (const OperandT& operand, Type object)
817 {
818     return object &= operand;
819 }
820 
821 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
822 
823 template<class Type, class OperandT>
824 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(const OperandT & operand,const Type & object)825 operator & (const OperandT& operand, const Type& object)
826 {
827     Type temp = object;
828     return boost::move(temp &= operand);
829 }
830 
831 template<class Type, class OperandT>
832 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(const OperandT & operand,Type && object)833 operator & (const OperandT& operand, Type&& object)
834 {
835     return boost::move(object &= operand);
836 }
837 
838 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
839 
840 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
841 //------------------------------------------------------------------------------
842 //- T op & (T, c T&) T:{S M}
843 //------------------------------------------------------------------------------
844 template<class Type>
845 typename enable_if<is_interval_container<Type>, Type>::type
operator &(Type object,const Type & operand)846 operator & (Type object, const Type& operand)
847 {
848     return object &= operand;
849 }
850 
851 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
852 
853 template<class Type>
854 typename enable_if<is_interval_container<Type>, Type>::type
operator &(const Type & object,const Type & operand)855 operator & (const Type& object, const Type& operand)
856 {
857     Type temp = object;
858     return boost::move(temp &= operand);
859 }
860 
861 template<class Type>
862 typename enable_if<is_interval_container<Type>, Type>::type
operator &(Type && object,const Type & operand)863 operator & (Type&& object, const Type& operand)
864 {
865     return boost::move(object &= operand);
866 }
867 
868 template<class Type>
869 typename enable_if<is_interval_container<Type>, Type>::type
operator &(const Type & operand,Type && object)870 operator & (const Type& operand, Type&& object)
871 {
872     return boost::move(object &= operand);
873 }
874 
875 template<class Type>
876 typename enable_if<is_interval_container<Type>, Type>::type
operator &(Type && object,Type && operand)877 operator & (Type&& object, Type&& operand)
878 {
879     return boost::move(object &= operand);
880 }
881 
882 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
883 
884 //------------------------------------------------------------------------------
885 //- intersects<IntervalSet|IntervalMap>
886 //------------------------------------------------------------------------------
887 //------------------------------------------------------------------------------
888 //- bool intersects(c T&, c P&) T:{S}|{M} P:{e i}
889 //------------------------------------------------------------------------------
890 template<class Type, class CoType>
891 typename enable_if<mpl::and_< is_interval_container<Type>
892                             , boost::is_same<CoType, typename domain_type_of<Type>::type> >,
893                    bool>::type
intersects(const Type & left,const CoType & right)894 intersects(const Type& left, const CoType& right)
895 {
896     return icl::contains(left, right);
897 }
898 
899 template<class Type, class CoType>
900 typename enable_if<mpl::and_< is_interval_container<Type>
901                             , boost::is_same<CoType, typename interval_type_of<Type>::type> >,
902                    bool>::type
intersects(const Type & left,const CoType & right)903 intersects(const Type& left, const CoType& right)
904 {
905     return icl::find(left, right) != left.end();
906 }
907 
908 
909 template<class LeftT, class RightT>
910 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
911                              , mpl::or_<is_total<LeftT>, is_total<RightT> > >
912                   , bool>::type
intersects(const LeftT &,const RightT &)913 intersects(const LeftT&, const RightT&)
914 {
915     return true;
916 }
917 
918 template<class LeftT, class RightT>
919 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
920                              , mpl::not_<mpl::or_< is_total<LeftT>
921                                                  , is_total<RightT> > > >
922                   , bool>::type
intersects(const LeftT & left,const RightT & right)923 intersects(const LeftT& left, const RightT& right)
924 {
925     typedef typename RightT::const_iterator const_iterator;
926     LeftT intersection;
927 
928     const_iterator right_common_lower_, right_common_upper_;
929     if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
930         return false;
931 
932     const_iterator it_ = right_common_lower_;
933     while(it_ != right_common_upper_)
934     {
935         icl::add_intersection(intersection, left, *it_++);
936         if(!icl::is_empty(intersection))
937             return true;
938     }
939     return false;
940 }
941 
942 template<class LeftT, class RightT>
943 typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type
intersects(const LeftT & left,const RightT & right)944 intersects(const LeftT& left, const RightT& right)
945 {
946     typedef typename RightT::const_iterator const_iterator;
947     LeftT intersection;
948 
949     if(icl::is_empty(left) || icl::is_empty(right))
950         return false;
951 
952     const_iterator right_common_lower_, right_common_upper_;
953     if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
954         return false;
955 
956     typename RightT::const_iterator it_ = right_common_lower_;
957     while(it_ != right_common_upper_)
958     {
959         icl::add_intersection(intersection, left, key_value<RightT>(it_++));
960         if(!icl::is_empty(intersection))
961             return true;
962     }
963 
964     return false;
965 }
966 
967 /** \b Returns true, if \c left and \c right have no common elements.
968     Intervals are interpreted as sequence of elements.
969     \b Complexity: loglinear, if \c left and \c right are interval containers. */
970 template<class LeftT, class RightT>
971 typename enable_if<is_inter_combinable<LeftT, RightT>, bool>::type
disjoint(const LeftT & left,const RightT & right)972 disjoint(const LeftT& left, const RightT& right)
973 {
974     return !intersects(left, right);
975 }
976 
977 /** \b Returns true, if \c left and \c right have no common elements.
978     Intervals are interpreted as sequence of elements.
979     \b Complexity: logarithmic, if \c AssociateT is an element type \c Type::element_type.
980     linear, if \c AssociateT is a segment type \c Type::segment_type. */
981 template<class Type, class AssociateT>
982 typename enable_if<is_inter_derivative<Type, AssociateT>, bool>::type
disjoint(const Type & left,const AssociateT & right)983 disjoint(const Type& left, const AssociateT& right)
984 {
985     return !intersects(left,right);
986 }
987 
988 
989 //==============================================================================
990 //= Symmetric difference<IntervalSet|IntervalSet>
991 //==============================================================================
992 //------------------------------------------------------------------------------
993 //- Symmetric difference ^=, ^
994 //------------------------------------------------------------------------------
995 //------------------------------------------------------------------------------
996 //- T& op ^=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
997 //------------------------------------------------------------------------------
998 template<class Type, class OperandT>
999 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
operator ^=(Type & object,const OperandT & operand)1000 operator ^= (Type& object, const OperandT& operand)
1001 {
1002     return icl::flip(object, operand);
1003 }
1004 
1005 //------------------------------------------------------------------------------
1006 //- T& op ^=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
1007 //------------------------------------------------------------------------------
1008 template<class Type, class OperandT>
1009 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
operator ^=(Type & object,const OperandT & operand)1010 operator ^= (Type& object, const OperandT& operand)
1011 {
1012     return icl::flip(object, operand);
1013 }
1014 
1015 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1016 //------------------------------------------------------------------------------
1017 //- T op ^ (T, c P&) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
1018 //------------------------------------------------------------------------------
1019 template<class Type, class OperandT>
1020 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(Type object,const OperandT & operand)1021 operator ^ (Type object, const OperandT& operand)
1022 {
1023     return object ^= operand;
1024 }
1025 
1026 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1027 
1028 template<class Type, class OperandT>
1029 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(const Type & object,const OperandT & operand)1030 operator ^ (const Type& object, const OperandT& operand)
1031 {
1032     Type temp = object;
1033     return boost::move(temp ^= operand);
1034 }
1035 
1036 template<class Type, class OperandT>
1037 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(Type && object,const OperandT & operand)1038 operator ^ (Type&& object, const OperandT& operand)
1039 {
1040     return boost::move(object ^= operand);
1041 }
1042 
1043 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1044 
1045 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1046 //------------------------------------------------------------------------------
1047 //- T op ^ (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
1048 //------------------------------------------------------------------------------
1049 template<class Type, class OperandT>
1050 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(const OperandT & operand,Type object)1051 operator ^ (const OperandT& operand, Type object)
1052 {
1053     return object ^= operand;
1054 }
1055 
1056 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1057 
1058 template<class Type, class OperandT>
1059 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(const OperandT & operand,const Type & object)1060 operator ^ (const OperandT& operand, const Type& object)
1061 {
1062     Type temp = object;
1063     return boost::move(temp ^= operand);
1064 }
1065 
1066 template<class Type, class OperandT>
1067 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(const OperandT & operand,Type && object)1068 operator ^ (const OperandT& operand, Type&& object)
1069 {
1070     return boost::move(object ^= operand);
1071 }
1072 
1073 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1074 
1075 #ifdef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1076 //------------------------------------------------------------------------------
1077 //- T op ^ (T, c T&) T:{S M}
1078 //------------------------------------------------------------------------------
1079 template<class Type>
1080 typename enable_if<is_interval_container<Type>, Type>::type
operator ^(typename Type::overloadable_type object,const Type & operand)1081 operator ^ (typename Type::overloadable_type object, const Type& operand)
1082 {
1083     return object ^= operand;
1084 }
1085 
1086 #else //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1087 
1088 template<class Type>
1089 typename enable_if<is_interval_container<Type>, Type>::type
operator ^(const Type & object,const Type & operand)1090 operator ^ (const Type& object, const Type& operand)
1091 {
1092     Type temp = object;
1093     return boost::move(temp ^= operand);
1094 }
1095 
1096 template<class Type>
1097 typename enable_if<is_interval_container<Type>, Type>::type
operator ^(Type && object,const Type & operand)1098 operator ^ (Type&& object, const Type& operand)
1099 {
1100     return boost::move(object ^= operand);
1101 }
1102 
1103 template<class Type>
1104 typename enable_if<is_interval_container<Type>, Type>::type
operator ^(const Type & operand,Type && object)1105 operator ^ (const Type& operand, Type&& object)
1106 {
1107     return boost::move(object ^= operand);
1108 }
1109 
1110 template<class Type>
1111 typename enable_if<is_interval_container<Type>, Type>::type
operator ^(Type && object,Type && operand)1112 operator ^ (Type&& object, Type&& operand)
1113 {
1114     return boost::move(object ^= operand);
1115 }
1116 
1117 #endif //BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
1118 
1119 //==========================================================================
1120 //= Element Iteration <IntervalSet|IntervalMap>
1121 //==========================================================================
1122 //--------------------------------------------------------------------------
1123 //- Forward
1124 //--------------------------------------------------------------------------
1125 template<class Type>
1126 typename enable_if
1127 <mpl::and_< is_interval_container<Type>
1128           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1129 typename Type::element_iterator>::type
elements_begin(Type & object)1130 elements_begin(Type& object)
1131 {
1132     return typename Type::element_iterator(object.begin());
1133 }
1134 
1135 template<class Type>
1136 typename enable_if
1137 <mpl::and_< is_interval_container<Type>
1138           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1139 typename Type::element_iterator>::type
elements_end(Type & object)1140 elements_end(Type& object)
1141 {
1142     return typename Type::element_iterator(object.end());
1143 }
1144 
1145 template<class Type>
1146 typename enable_if
1147 <mpl::and_< is_interval_container<Type>
1148           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1149 typename Type::element_const_iterator>::type
elements_begin(const Type & object)1150 elements_begin(const Type& object)
1151 {
1152     return typename Type::element_const_iterator(object.begin());
1153 }
1154 
1155 template<class Type>
1156 typename enable_if
1157 <mpl::and_< is_interval_container<Type>
1158           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1159 typename Type::element_const_iterator>::type
elements_end(const Type & object)1160 elements_end(const Type& object)
1161 {
1162     return typename Type::element_const_iterator(object.end());
1163 }
1164 
1165 template<class Type>
1166 typename enable_if
1167 <mpl::and_< is_interval_container<Type>
1168           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1169 iterator_range<typename Type::element_iterator> >::type
elements(Type & object)1170 elements(Type& object)
1171 {
1172     return
1173     make_iterator_range( typename Type::element_iterator(object.begin())
1174                        , typename Type::element_iterator(object.end())  );
1175 }
1176 
1177 template<class Type>
1178 typename enable_if
1179 <mpl::and_< is_interval_container<Type>
1180           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1181 iterator_range<typename Type::element_const_iterator> >::type
elements(Type const & object)1182 elements(Type const& object)
1183 {
1184     return
1185     make_iterator_range( typename Type::element_const_iterator(object.begin())
1186                        , typename Type::element_const_iterator(object.end())  );
1187 }
1188 
1189 //--------------------------------------------------------------------------
1190 //- Reverse
1191 //--------------------------------------------------------------------------
1192 template<class Type>
1193 typename enable_if
1194 <mpl::and_< is_interval_container<Type>
1195           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1196 typename Type::element_reverse_iterator>::type
elements_rbegin(Type & object)1197 elements_rbegin(Type& object)
1198 {
1199     return typename Type::element_reverse_iterator(object.rbegin());
1200 }
1201 
1202 template<class Type>
1203 typename enable_if
1204 <mpl::and_< is_interval_container<Type>
1205           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1206 typename Type::element_reverse_iterator>::type
elements_rend(Type & object)1207 elements_rend(Type& object)
1208 {
1209     return typename Type::element_reverse_iterator(object.rend());
1210 }
1211 
1212 template<class Type>
1213 typename enable_if
1214 <mpl::and_< is_interval_container<Type>
1215           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1216 typename Type::element_const_reverse_iterator>::type
elements_rbegin(const Type & object)1217 elements_rbegin(const Type& object)
1218 {
1219     return typename Type::element_const_reverse_iterator(object.rbegin());
1220 }
1221 
1222 template<class Type>
1223 typename enable_if
1224 <mpl::and_< is_interval_container<Type>
1225           , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
1226 typename Type::element_const_reverse_iterator>::type
elements_rend(const Type & object)1227 elements_rend(const Type& object)
1228 {
1229     return typename Type::element_const_reverse_iterator(object.rend());
1230 }
1231 
1232 }} // namespace boost icl
1233 
1234 #endif
1235 
1236 
1237