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/icl/type_traits/domain_type_of.hpp>
12 #include <boost/icl/type_traits/interval_type_of.hpp>
13 #include <boost/icl/type_traits/is_combinable.hpp>
14 #include <boost/icl/detail/set_algo.hpp>
15 #include <boost/icl/detail/map_algo.hpp>
16 #include <boost/icl/detail/interval_set_algo.hpp>
17 #include <boost/icl/detail/interval_map_algo.hpp>
18 #include <boost/icl/concept/interval.hpp>
19
20 namespace boost{ namespace icl
21 {
22
23 //==============================================================================
24 //= Containedness<IntervalSet|IntervalMap>
25 //==============================================================================
26 //------------------------------------------------------------------------------
27 //- bool within(c T&, c P&) T={Set,Map} P={e i b p S M}
28 //------------------------------------------------------------------------------
29 template<class SubT, class SuperT>
30 typename enable_if<is_interval_container<SuperT>, bool>::type
within(const SubT & sub,const SuperT & super)31 within(const SubT& sub, const SuperT& super)
32 {
33 return icl::contains(super, sub);
34 }
35
36 //==============================================================================
37 //= Equivalences and Orderings<IntervalSet|IntervalMap>
38 //==============================================================================
39 template<class Type>
40 inline typename enable_if<is_interval_container<Type>, bool>::type
operator ==(const Type & left,const Type & right)41 operator == (const Type& left, const Type& right)
42 {
43 return Set::lexicographical_equal(left, right);
44 }
45
46 template<class Type>
47 inline typename enable_if<is_interval_container<Type>, bool>::type
operator <(const Type & left,const Type & right)48 operator < (const Type& left, const Type& right)
49 {
50 typedef typename Type::segment_compare segment_compare;
51 return std::lexicographical_compare(
52 left.begin(), left.end(), right.begin(), right.end(),
53 segment_compare()
54 );
55 }
56
57 /** Returns true, if \c left and \c right contain the same elements.
58 Complexity: linear. */
59 template<class LeftT, class RightT>
60 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
is_element_equal(const LeftT & left,const RightT & right)61 is_element_equal(const LeftT& left, const RightT& right)
62 {
63 return Interval_Set::is_element_equal(left, right);
64 }
65
66 /** Returns true, if \c left is lexicographically less than \c right.
67 Intervals are interpreted as sequence of elements.
68 Complexity: linear. */
69 template<class LeftT, class RightT>
70 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
is_element_less(const LeftT & left,const RightT & right)71 is_element_less(const LeftT& left, const RightT& right)
72 {
73 return Interval_Set::is_element_less(left, right);
74 }
75
76 /** Returns true, if \c left is lexicographically greater than \c right.
77 Intervals are interpreted as sequence of elements.
78 Complexity: linear. */
79 template<class LeftT, class RightT>
80 typename enable_if<is_intra_combinable<LeftT, RightT>, bool>::type
is_element_greater(const LeftT & left,const RightT & right)81 is_element_greater(const LeftT& left, const RightT& right)
82 {
83 return Interval_Set::is_element_greater(left, right);
84 }
85
86 //------------------------------------------------------------------------------
87 template<class LeftT, class RightT>
88 typename enable_if<is_inter_combinable<LeftT, RightT>, int>::type
inclusion_compare(const LeftT & left,const RightT & right)89 inclusion_compare(const LeftT& left, const RightT& right)
90 {
91 return Interval_Set::subset_compare(left, right,
92 left.begin(), left.end(),
93 right.begin(), right.end());
94 }
95
96 //------------------------------------------------------------------------------
97 template<class LeftT, class RightT>
98 typename enable_if< is_concept_compatible<is_interval_map, LeftT, RightT>,
99 bool >::type
is_distinct_equal(const LeftT & left,const RightT & right)100 is_distinct_equal(const LeftT& left, const RightT& right)
101 {
102 return Map::lexicographical_distinct_equal(left, right);
103 }
104
105 //==============================================================================
106 //= Size<IntervalSet|IntervalMap>
107 //==============================================================================
108 template<class Type>
109 typename enable_if<is_interval_container<Type>, std::size_t>::type
iterative_size(const Type & object)110 iterative_size(const Type& object)
111 {
112 return object.iterative_size();
113 }
114
115 template<class Type>
116 typename enable_if
117 < mpl::and_< is_interval_container<Type>
118 , is_discrete<typename Type::domain_type> >
119 , typename Type::size_type
120 >::type
cardinality(const Type & object)121 cardinality(const Type& object)
122 {
123 typedef typename Type::size_type size_type;
124 typedef typename Type::interval_type interval_type;
125
126 size_type size = identity_element<size_type>::value();
127 ICL_const_FORALL(typename Type, it, object)
128 size += icl::cardinality(key_value<Type>(it));
129 return size;
130
131 }
132
133 template<class Type>
134 typename enable_if
135 < mpl::and_< is_interval_container<Type>
136 , mpl::not_<is_discrete<typename Type::domain_type> > >
137 , typename Type::size_type
138 >::type
cardinality(const Type & object)139 cardinality(const Type& object)
140 {
141 typedef typename Type::size_type size_type;
142 typedef typename Type::interval_type interval_type;
143
144 size_type size = identity_element<size_type>::value();
145 size_type interval_size;
146 ICL_const_FORALL(typename Type, it, object)
147 {
148 interval_size = icl::cardinality(key_value<Type>(it));
149 if(interval_size == icl::infinity<size_type>::value())
150 return interval_size;
151 else
152 size += interval_size;
153 }
154 return size;
155 }
156
157 template<class Type>
158 inline typename enable_if<is_interval_container<Type>, typename Type::size_type>::type
size(const Type & object)159 size(const Type& object)
160 {
161 return icl::cardinality(object);
162 }
163
164 template<class Type>
165 typename enable_if<is_interval_container<Type>, typename Type::difference_type>::type
length(const Type & object)166 length(const Type& object)
167 {
168 typedef typename Type::difference_type difference_type;
169 typedef typename Type::const_iterator const_iterator;
170 difference_type length = identity_element<difference_type>::value();
171 const_iterator it_ = object.begin();
172
173 while(it_ != object.end())
174 length += icl::length(key_value<Type>(it_++));
175 return length;
176 }
177
178 template<class Type>
179 typename enable_if<is_interval_container<Type>, std::size_t>::type
interval_count(const Type & object)180 interval_count(const Type& object)
181 {
182 return icl::iterative_size(object);
183 }
184
185
186 template<class Type>
187 typename enable_if< is_interval_container<Type>
188 , typename Type::difference_type >::type
distance(const Type & object)189 distance(const Type& object)
190 {
191 typedef typename Type::difference_type DiffT;
192 typedef typename Type::const_iterator const_iterator;
193 const_iterator it_ = object.begin(), pred_;
194 DiffT dist = identity_element<DiffT>::value();
195
196 if(it_ != object.end())
197 pred_ = it_++;
198
199 while(it_ != object.end())
200 dist += icl::distance(key_value<Type>(pred_++), key_value<Type>(it_++));
201
202 return dist;
203 }
204
205 //==============================================================================
206 //= Range<IntervalSet|IntervalMap>
207 //==============================================================================
208 template<class Type>
209 typename enable_if<is_interval_container<Type>,
210 typename Type::interval_type>::type
hull(const Type & object)211 hull(const Type& object)
212 {
213 return
214 icl::is_empty(object)
215 ? identity_element<typename Type::interval_type>::value()
216 : icl::hull( key_value<Type>(object.begin()),
217 key_value<Type>(object.rbegin()) );
218 }
219
220 template<class Type>
221 typename enable_if<is_interval_container<Type>,
222 typename domain_type_of<Type>::type>::type
lower(const Type & object)223 lower(const Type& object)
224 {
225 typedef typename domain_type_of<Type>::type DomainT;
226 return
227 icl::is_empty(object)
228 ? unit_element<DomainT>::value()
229 : icl::lower( key_value<Type>(object.begin()) );
230 }
231
232 template<class Type>
233 typename enable_if<is_interval_container<Type>,
234 typename domain_type_of<Type>::type>::type
upper(const Type & object)235 upper(const Type& object)
236 {
237 typedef typename domain_type_of<Type>::type DomainT;
238 return
239 icl::is_empty(object)
240 ? identity_element<DomainT>::value()
241 : icl::upper( key_value<Type>(object.rbegin()) );
242 }
243
244 //------------------------------------------------------------------------------
245 template<class Type>
246 typename enable_if
247 < mpl::and_< is_interval_container<Type>
248 , is_discrete<typename domain_type_of<Type>::type> >
249 , typename domain_type_of<Type>::type>::type
first(const Type & object)250 first(const Type& object)
251 {
252 typedef typename domain_type_of<Type>::type DomainT;
253 return
254 icl::is_empty(object)
255 ? unit_element<DomainT>::value()
256 : icl::first( key_value<Type>(object.begin()) );
257 }
258
259 template<class Type>
260 typename enable_if
261 < mpl::and_< is_interval_container<Type>
262 , is_discrete<typename domain_type_of<Type>::type> >
263 , typename domain_type_of<Type>::type>::type
last(const Type & object)264 last(const Type& object)
265 {
266 typedef typename domain_type_of<Type>::type DomainT;
267 return
268 icl::is_empty(object)
269 ? identity_element<DomainT>::value()
270 : icl::last( key_value<Type>(object.rbegin()) );
271 }
272
273
274 //==============================================================================
275 //= Addition<IntervalSet|IntervalMap>
276 //==============================================================================
277 //------------------------------------------------------------------------------
278 //- T& op +=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
279 //------------------------------------------------------------------------------
280 /* \par \b Requires: \c OperandT is an addable derivative type of \c Type.
281 \b Effects: \c operand is added to \c object.
282 \par \b Returns: A reference to \c object.
283 \b Complexity:
284 \code
285 \ OperandT:
286 \ element segment
287 Type:
288 interval container O(log n) O(n)
289
290 interval_set amortized
291 spearate_interval_set O(log n)
292
293 n = object.interval_count()
294 \endcode
295
296 For the addition of \b elements or \b segments
297 complexity is \b logarithmic or \b linear respectively.
298 For \c interval_sets and \c separate_interval_sets addition of segments
299 is \b amortized \b logarithmic.
300 */
301 template<class Type, class OperandT>
302 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
operator +=(Type & object,const OperandT & operand)303 operator += (Type& object, const OperandT& operand)
304 {
305 return icl::add(object, operand);
306 }
307
308
309 //------------------------------------------------------------------------------
310 //- T& op +=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
311 //------------------------------------------------------------------------------
312 /** \par \b Requires: \c OperandT is an interval container addable to \c Type.
313 \b Effects: \c operand is added to \c object.
314 \par \b Returns: A reference to \c object.
315 \b Complexity: loglinear */
316 template<class Type, class OperandT>
317 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
operator +=(Type & object,const OperandT & operand)318 operator += (Type& object, const OperandT& operand)
319 {
320 typename Type::iterator prior_ = object.end();
321 ICL_const_FORALL(typename OperandT, elem_, operand)
322 prior_ = icl::add(object, prior_, *elem_);
323
324 return object;
325 }
326
327
328 //------------------------------------------------------------------------------
329 //- T op + (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
330 //------------------------------------------------------------------------------
331 /** \par \b Requires: \c object and \c operand are addable.
332 \b Effects: \c operand is added to \c object.
333 \par \b Efficieny: There is one additional copy of
334 \c Type \c object compared to inplace \c operator \c += */
335 template<class Type, class OperandT>
336 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(Type object,const OperandT & operand)337 operator + (Type object, const OperandT& operand)
338 {
339 return object += operand;
340 }
341
342 //------------------------------------------------------------------------------
343 //- T op + (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'}
344 //------------------------------------------------------------------------------
345 /** \par \b Requires: \c object and \c operand are addable.
346 \b Effects: \c operand is added to \c object.
347 \par \b Efficieny: There is one additional copy of
348 \c Type \c object compared to inplace \c operator \c += */
349 template<class Type, class OperandT>
350 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator +(const OperandT & operand,Type object)351 operator + (const OperandT& operand, Type object)
352 {
353 return object += operand;
354 }
355
356 //------------------------------------------------------------------------------
357 //- T op + (T, c P&) T:{S}|{M} P:{S}|{M}
358 //------------------------------------------------------------------------------
359 /** \par \b Requires: \c object and \c operand are addable.
360 \b Effects: \c operand is added to \c object.
361 \par \b Efficieny: There is one additional copy of
362 \c Type \c object compared to inplace \c operator \c += */
363 template<class Type>
364 typename enable_if<is_interval_container<Type>, Type>::type
operator +(Type object,const Type & operand)365 operator + (Type object, const Type& operand)
366 {
367 return object += operand;
368 }
369
370
371 //------------------------------------------------------------------------------
372 //- Addition |=, |
373 //------------------------------------------------------------------------------
374
375 //------------------------------------------------------------------------------
376 //- T& op |=(c P&) T:{S}|{M} P:{e i}|{b p}
377 //------------------------------------------------------------------------------
378 /** \par \b Requires: Types \c Type and \c OperandT are addable.
379 \par \b Effects: \c operand is added to \c object.
380 \par \b Returns: A reference to \c object.
381 \b Complexity:
382 \code
383 \ OperandT: interval
384 \ element segment container
385 Type:
386 interval container O(log n) O(n) O(m log(n+m))
387
388 interval_set amortized
389 spearate_interval_set O(log n)
390
391 n = object.interval_count()
392 m = operand.interval_count()
393 \endcode
394
395 For the addition of \b elements, \b segments and \b interval \b containers
396 complexity is \b logarithmic, \b linear and \b loglinear respectively.
397 For \c interval_sets and \c separate_interval_sets addition of segments
398 is \b amortized \b logarithmic.
399 */
400 template<class Type, class OperandT>
401 typename enable_if<is_right_intra_combinable<Type, OperandT>, Type>::type&
operator |=(Type & object,const OperandT & operand)402 operator |= (Type& object, const OperandT& operand)
403 {
404 return object += operand;
405 }
406
407 //------------------------------------------------------------------------------
408 //- T op | (T, c P&) T:{S}|{M} P:{e i S}|{b p M}
409 //------------------------------------------------------------------------------
410 /** \par \b Requires: \c object and \c operand are addable.
411 \b Effects: \c operand is added to \c object.
412 \par \b Efficieny: There is one additional copy of
413 \c Type \c object compared to inplace \c operator \c |= */
414 template<class Type, class OperandT>
415 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(Type object,const OperandT & operand)416 operator | (Type object, const OperandT& operand)
417 {
418 return object += operand;
419 }
420
421 //------------------------------------------------------------------------------
422 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
423 //------------------------------------------------------------------------------
424 /** \par \b Requires: \c object and \c operand are addable.
425 \b Effects: \c operand is added to \c object.
426 \par \b Efficieny: There is one additional copy of
427 \c Type \c object compared to inplace \c operator \c |= */
428 template<class Type, class OperandT>
429 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator |(const OperandT & operand,Type object)430 operator | (const OperandT& operand, Type object)
431 {
432 return object += operand;
433 }
434
435 //------------------------------------------------------------------------------
436 //- T op | (T, c P&) T:{S}|{M} P:{S}|{M}
437 //------------------------------------------------------------------------------
438 /** \par \b Requires: \c object and \c operand are addable.
439 \b Effects: \c operand is added to \c object.
440 \par \b Efficieny: There is one additional copy of
441 \c Type \c object compared to inplace \c operator \c |= */
442 template<class Type>
443 typename enable_if<is_interval_container<Type>, Type>::type
operator |(Type object,const Type & operand)444 operator | (Type object, const Type& operand)
445 {
446 return object += operand;
447 }
448
449 //==============================================================================
450 //= Insertion<IntervalSet|IntervalSet>
451 //==============================================================================
452 //------------------------------------------------------------------------------
453 //- T& insert(T&, c P&) T:{S}|{M} P:{S'}|{M'}
454 //------------------------------------------------------------------------------
455 template<class Type, class OperandT>
456 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
insert(Type & object,const OperandT & operand)457 insert(Type& object, const OperandT& operand)
458 {
459 typename Type::iterator prior_ = object.end();
460 ICL_const_FORALL(typename OperandT, elem_, operand)
461 insert(object, *elem_);
462
463 return object;
464 }
465
466 //==============================================================================
467 //= Erasure<IntervalSet|IntervalSet>
468 //==============================================================================
469 //------------------------------------------------------------------------------
470 //- T& erase(T&, c P&) T:{S}|{M} P:{S'}|{S' M'}
471 //------------------------------------------------------------------------------
472 template<class Type, class OperandT>
473 typename enable_if<combines_right_to_interval_container<Type, OperandT>,
474 Type>::type&
erase(Type & object,const OperandT & operand)475 erase(Type& object, const OperandT& operand)
476 {
477 typedef typename OperandT::const_iterator const_iterator;
478
479 if(icl::is_empty(operand))
480 return object;
481
482 const_iterator common_lwb, common_upb;
483 if(!Set::common_range(common_lwb, common_upb, operand, object))
484 return object;
485
486 const_iterator it_ = common_lwb;
487 while(it_ != common_upb)
488 icl::erase(object, *it_++);
489
490 return object;
491 }
492
493 //==============================================================================
494 //= Subtraction<IntervalSet|IntervalSet>
495 //==============================================================================
496 //------------------------------------------------------------------------------
497 //- T& op -= (c P&) T:{M} P:{M'}
498 //------------------------------------------------------------------------------
499 /** \par \b Requires: Types \c Type and \c OperandT are subtractable.
500 \par \b Effects: \c operand is subtracted from \c object.
501 \par \b Returns: A reference to \c object.
502 \b Complexity:
503 \code
504 \ OperandT: interval
505 \ element segment container
506 Type:
507 interval container O(log n) O(n) O(m log(n+m))
508
509 amortized
510 interval_sets O(log n)
511
512 n = object.interval_count()
513 m = operand.interval_count()
514 \endcode
515
516 For the subtraction of \em elements, \b segments and \b interval \b containers
517 complexity is \b logarithmic, \b linear and \b loglinear respectively.
518 For interval sets subtraction of segments
519 is \b amortized \b logarithmic.
520 */
521 template<class Type, class OperandT>
522 typename enable_if<is_concept_compatible<is_interval_map, Type, OperandT>,
523 Type>::type&
operator -=(Type & object,const OperandT & operand)524 operator -=(Type& object, const OperandT& operand)
525 {
526 ICL_const_FORALL(typename OperandT, elem_, operand)
527 icl::subtract(object, *elem_);
528
529 return object;
530 }
531
532 //------------------------------------------------------------------------------
533 //- T& op -= (c P&) T:{S}|{M} P:{e i}|{b p}
534 //------------------------------------------------------------------------------
535 template<class Type, class OperandT>
536 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
operator -=(Type & object,const OperandT & operand)537 operator -= (Type& object, const OperandT& operand)
538 {
539 return icl::subtract(object, operand);
540 }
541
542 //------------------------------------------------------------------------------
543 //- T& op -= (c P&) T:{M} P:{e i}
544 //------------------------------------------------------------------------------
545 template<class Type, class OperandT>
546 typename enable_if<is_cross_derivative<Type, OperandT>, Type>::type&
operator -=(Type & object,const OperandT & operand)547 operator -= (Type& object, const OperandT& operand)
548 {
549 return icl::erase(object, operand);
550 }
551
552 //------------------------------------------------------------------------------
553 //- T& op -= (c P&) T:{S M} P:{S'}
554 //------------------------------------------------------------------------------
555 template<class Type, class IntervalSetT>
556 typename enable_if<combines_right_to_interval_set<Type, IntervalSetT>,
557 Type>::type&
operator -=(Type & object,const IntervalSetT & operand)558 operator -= (Type& object, const IntervalSetT& operand)
559 {
560 return erase(object, operand);
561 }
562
563
564 //------------------------------------------------------------------------------
565 //- T op - (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
566 //------------------------------------------------------------------------------
567 template<class Type, class OperandT>
568 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type
operator -(Type object,const OperandT & operand)569 operator - (Type object, const OperandT& operand)
570 {
571 return object -= operand;
572 }
573
574
575 //==============================================================================
576 //= Intersection<IntervalSet|IntervalSet>
577 //==============================================================================
578 //------------------------------------------------------------------------------
579 //- void add_intersection(T&, c T&, c P&) T:{S M} P:{S'}
580 //------------------------------------------------------------------------------
581 template<class Type, class OperandT>
582 typename enable_if<mpl::and_<is_interval_set<Type>,
583 combines_right_to_interval_set<Type, OperandT> >,
584 void>::type
add_intersection(Type & section,const Type & object,const OperandT & operand)585 add_intersection(Type& section, const Type& object, const OperandT& operand)
586 {
587 typedef typename OperandT::const_iterator const_iterator;
588
589 if(operand.empty())
590 return;
591
592 const_iterator common_lwb, common_upb;
593 if(!Set::common_range(common_lwb, common_upb, operand, object))
594 return;
595
596 const_iterator it_ = common_lwb;
597 while(it_ != common_upb)
598 icl::add_intersection(section, object, key_value<OperandT>(it_++));
599 }
600
601 //------------------------------------------------------------------------------
602 //- T& op &=(T&, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'}
603 //------------------------------------------------------------------------------
604 template<class Type, class OperandT>
605 typename enable_if<is_right_inter_combinable<Type, OperandT>, Type>::type&
operator &=(Type & object,const OperandT & operand)606 operator &= (Type& object, const OperandT& operand)
607 {
608 Type intersection;
609 add_intersection(intersection, object, operand);
610 object.swap(intersection);
611 return object;
612 }
613
614 //------------------------------------------------------------------------------
615 //- T op & (T, c P&) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
616 //------------------------------------------------------------------------------
617 template<class Type, class OperandT>
618 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(Type object,const OperandT & operand)619 operator & (Type object, const OperandT& operand)
620 {
621 return object &= operand;
622 }
623
624 //------------------------------------------------------------------------------
625 //- T op & (c P&, T) T:{S}|{M} P:{e i S'}|{e i b p S' M'} S<S' M<M' <:coarser
626 //------------------------------------------------------------------------------
627 template<class Type, class OperandT>
628 typename enable_if<is_binary_inter_combinable<Type, OperandT>, Type>::type
operator &(const OperandT & operand,Type object)629 operator & (const OperandT& operand, Type object)
630 {
631 return object &= operand;
632 }
633
634 //------------------------------------------------------------------------------
635 //- T op & (T, c T&) T:{S M}
636 //------------------------------------------------------------------------------
637 template<class Type>
638 typename enable_if<is_interval_container<Type>, Type>::type
operator &(Type object,const Type & operand)639 operator & (Type object, const Type& operand)
640 {
641 return object &= operand;
642 }
643
644 //------------------------------------------------------------------------------
645 //- intersects<IntervalSet|IntervalMap>
646 //------------------------------------------------------------------------------
647 //------------------------------------------------------------------------------
648 //- bool intersects(c T&, c P&) T:{S}|{M} P:{e i}
649 //------------------------------------------------------------------------------
650 template<class Type, class CoType>
651 typename enable_if<mpl::and_< is_interval_container<Type>
652 , boost::is_same<CoType, typename domain_type_of<Type>::type> >,
653 bool>::type
intersects(const Type & left,const CoType & right)654 intersects(const Type& left, const CoType& right)
655 {
656 return icl::contains(left, right);
657 }
658
659 template<class Type, class CoType>
660 typename enable_if<mpl::and_< is_interval_container<Type>
661 , boost::is_same<CoType, typename interval_type_of<Type>::type> >,
662 bool>::type
intersects(const Type & left,const CoType & right)663 intersects(const Type& left, const CoType& right)
664 {
665 return icl::find(left, right) != left.end();
666 }
667
668
669 template<class LeftT, class RightT>
670 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
671 , mpl::or_<is_total<LeftT>, is_total<RightT> > >
672 , bool>::type
intersects(const LeftT &,const RightT &)673 intersects(const LeftT&, const RightT&)
674 {
675 return true;
676 }
677
678 template<class LeftT, class RightT>
679 typename enable_if< mpl::and_< is_intra_combinable<LeftT, RightT>
680 , mpl::not_<mpl::or_< is_total<LeftT>
681 , is_total<RightT> > > >
682 , bool>::type
intersects(const LeftT & left,const RightT & right)683 intersects(const LeftT& left, const RightT& right)
684 {
685 typedef typename RightT::const_iterator const_iterator;
686 LeftT intersection;
687
688 const_iterator right_common_lower_, right_common_upper_;
689 if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
690 return false;
691
692 const_iterator it_ = right_common_lower_;
693 while(it_ != right_common_upper_)
694 {
695 icl::add_intersection(intersection, left, *it_++);
696 if(!icl::is_empty(intersection))
697 return true;
698 }
699 return false;
700 }
701
702 template<class LeftT, class RightT>
703 typename enable_if<is_cross_combinable<LeftT, RightT>, bool>::type
intersects(const LeftT & left,const RightT & right)704 intersects(const LeftT& left, const RightT& right)
705 {
706 typedef typename RightT::const_iterator const_iterator;
707 LeftT intersection;
708
709 if(icl::is_empty(left) || icl::is_empty(right))
710 return false;
711
712 const_iterator right_common_lower_, right_common_upper_;
713 if(!Set::common_range(right_common_lower_, right_common_upper_, right, left))
714 return false;
715
716 typename RightT::const_iterator it_ = right_common_lower_;
717 while(it_ != right_common_upper_)
718 {
719 icl::add_intersection(intersection, left, key_value<RightT>(it_++));
720 if(!icl::is_empty(intersection))
721 return true;
722 }
723
724 return false;
725 }
726
727 /** \b Returns true, if \c left and \c right have no common elements.
728 Intervals are interpreted as sequence of elements.
729 \b Complexity: loglinear, if \c left and \c right are interval containers. */
730 template<class LeftT, class RightT>
731 typename enable_if<is_inter_combinable<LeftT, RightT>, bool>::type
disjoint(const LeftT & left,const RightT & right)732 disjoint(const LeftT& left, const RightT& right)
733 {
734 return !intersects(left, right);
735 }
736
737 /** \b Returns true, if \c left and \c right have no common elements.
738 Intervals are interpreted as sequence of elements.
739 \b Complexity: logarithmic, if \c AssociateT is an element type \c Type::element_type.
740 linear, if \c AssociateT is a segment type \c Type::segment_type. */
741 template<class Type, class AssociateT>
742 typename enable_if<is_inter_derivative<Type, AssociateT>, bool>::type
disjoint(const Type & left,const AssociateT & right)743 disjoint(const Type& left, const AssociateT& right)
744 {
745 return !intersects(left,right);
746 }
747
748
749 //==============================================================================
750 //= Symmetric difference<IntervalSet|IntervalSet>
751 //==============================================================================
752 //------------------------------------------------------------------------------
753 //- Symmetric difference ^=, ^
754 //------------------------------------------------------------------------------
755 //------------------------------------------------------------------------------
756 //- T& op ^=(T&, c P&) T:{S}|{M} P:{S'}|{M'}
757 //------------------------------------------------------------------------------
758 template<class Type, class OperandT>
759 typename enable_if<is_intra_combinable<Type, OperandT>, Type>::type&
operator ^=(Type & object,const OperandT & operand)760 operator ^= (Type& object, const OperandT& operand)
761 {
762 return icl::flip(object, operand);
763 }
764
765 //------------------------------------------------------------------------------
766 //- T& op ^=(T&, c P&) T:{S}|{M} P:{e i}|{b p}
767 //------------------------------------------------------------------------------
768 template<class Type, class OperandT>
769 typename enable_if<is_intra_derivative<Type, OperandT>, Type>::type&
operator ^=(Type & object,const OperandT & operand)770 operator ^= (Type& object, const OperandT& operand)
771 {
772 return icl::flip(object, operand);
773 }
774
775 //------------------------------------------------------------------------------
776 //- T op ^ (T, c P&) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
777 //------------------------------------------------------------------------------
778 template<class Type, class OperandT>
779 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(Type object,const OperandT & operand)780 operator ^ (Type object, const OperandT& operand)
781 {
782 return object ^= operand;
783 }
784
785 //------------------------------------------------------------------------------
786 //- T op ^ (c P&, T) T:{S}|{M} P:{e i S'}|{b p M'} S<S' M<M' <:coarser
787 //------------------------------------------------------------------------------
788 template<class Type, class OperandT>
789 typename enable_if<is_binary_intra_combinable<Type, OperandT>, Type>::type
operator ^(const OperandT & operand,Type object)790 operator ^ (const OperandT& operand, Type object)
791 {
792 return object ^= operand;
793 }
794
795 //------------------------------------------------------------------------------
796 //- T op ^ (T, c T&) T:{S M}
797 //------------------------------------------------------------------------------
798 template<class Type>
799 typename enable_if<is_interval_container<Type>, Type>::type
operator ^(typename Type::overloadable_type object,const Type & operand)800 operator ^ (typename Type::overloadable_type object, const Type& operand)
801 {
802 return object ^= operand;
803 }
804
805 //==========================================================================
806 //= Element Iteration <IntervalSet|IntervalMap>
807 //==========================================================================
808 //--------------------------------------------------------------------------
809 //- Forward
810 //--------------------------------------------------------------------------
811 template<class Type>
812 typename enable_if
813 <mpl::and_< is_interval_container<Type>
814 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
815 typename Type::element_iterator>::type
elements_begin(Type & object)816 elements_begin(Type& object)
817 {
818 return typename Type::element_iterator(object.begin());
819 }
820
821 template<class Type>
822 typename enable_if
823 <mpl::and_< is_interval_container<Type>
824 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
825 typename Type::element_iterator>::type
elements_end(Type & object)826 elements_end(Type& object)
827 {
828 return typename Type::element_iterator(object.end());
829 }
830
831 template<class Type>
832 typename enable_if
833 <mpl::and_< is_interval_container<Type>
834 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
835 typename Type::element_const_iterator>::type
elements_begin(const Type & object)836 elements_begin(const Type& object)
837 {
838 return typename Type::element_const_iterator(object.begin());
839 }
840
841 template<class Type>
842 typename enable_if
843 <mpl::and_< is_interval_container<Type>
844 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
845 typename Type::element_const_iterator>::type
elements_end(const Type & object)846 elements_end(const Type& object)
847 {
848 return typename Type::element_const_iterator(object.end());
849 }
850
851 //--------------------------------------------------------------------------
852 //- Reverse
853 //--------------------------------------------------------------------------
854 template<class Type>
855 typename enable_if
856 <mpl::and_< is_interval_container<Type>
857 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
858 typename Type::element_reverse_iterator>::type
elements_rbegin(Type & object)859 elements_rbegin(Type& object)
860 {
861 return typename Type::element_reverse_iterator(object.rbegin());
862 }
863
864 template<class Type>
865 typename enable_if
866 <mpl::and_< is_interval_container<Type>
867 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
868 typename Type::element_reverse_iterator>::type
elements_rend(Type & object)869 elements_rend(Type& object)
870 {
871 return typename Type::element_reverse_iterator(object.rend());
872 }
873
874 template<class Type>
875 typename enable_if
876 <mpl::and_< is_interval_container<Type>
877 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
878 typename Type::element_const_reverse_iterator>::type
elements_rbegin(const Type & object)879 elements_rbegin(const Type& object)
880 {
881 return typename Type::element_const_reverse_iterator(object.rbegin());
882 }
883
884 template<class Type>
885 typename enable_if
886 <mpl::and_< is_interval_container<Type>
887 , mpl::not_<is_continuous_interval<typename Type::interval_type> > >,
888 typename Type::element_const_reverse_iterator>::type
elements_rend(const Type & object)889 elements_rend(const Type& object)
890 {
891 return typename Type::element_const_reverse_iterator(object.rend());
892 }
893
894 }} // namespace boost icl
895
896 #endif
897
898
899