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_MAP_HPP_JOFA_100920
9 #define BOOST_ICL_CONCEPT_INTERVAL_MAP_HPP_JOFA_100920
11 #include <boost/icl/type_traits/element_type_of.hpp>
12 #include <boost/icl/type_traits/segment_type_of.hpp>
13 #include <boost/icl/type_traits/absorbs_identities.hpp>
14 #include <boost/icl/type_traits/is_combinable.hpp>
15 #include <boost/icl/type_traits/is_interval_splitter.hpp>
17 #include <boost/icl/detail/set_algo.hpp>
18 #include <boost/icl/detail/interval_map_algo.hpp>
19 #include <boost/icl/concept/interval.hpp>
20 #include <boost/icl/concept/joinable.hpp>
22 namespace boost{ namespace icl
26 inline typename enable_if<is_interval_map<Type>, typename Type::segment_type>::type
27 make_segment(const typename Type::element_type& element)
29 typedef typename Type::interval_type interval_type;
30 typedef typename Type::segment_type segment_type;
31 return segment_type(icl::singleton<interval_type>(element.key), element.data);
35 //==============================================================================
36 //= Containedness<IntervalMap>
37 //==============================================================================
38 //------------------------------------------------------------------------------
39 //- bool contains(c T&, c P&) T:{M} P:{b p M} fragment_types
40 //------------------------------------------------------------------------------
42 typename enable_if<is_interval_map<Type>, bool>::type
43 contains(const Type& super, const typename Type::element_type& key_value_pair)
45 typedef typename Type::const_iterator const_iterator;
46 const_iterator it_ = icl::find(super, key_value_pair.key);
47 return it_ != super.end() && (*it_).second == key_value_pair.data;
51 typename enable_if<is_interval_map<Type>, bool>::type
52 contains(const Type& super, const typename Type::segment_type& sub_segment)
54 typedef typename Type::interval_type interval_type;
55 typedef typename Type::const_iterator const_iterator;
57 interval_type sub_interval = sub_segment.first;
58 if(icl::is_empty(sub_interval))
61 std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
62 if(exterior.first == exterior.second)
65 const_iterator last_overlap = prior(exterior.second);
67 if(!(sub_segment.second == exterior.first->second) )
71 icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
72 && Interval_Map::is_joinable(super, exterior.first, last_overlap);
75 template<class Type, class CoType>
76 typename enable_if<is_concept_compatible<is_interval_map, Type, CoType>, bool>::type
77 contains(const Type& super, const CoType& sub)
79 return Interval_Set::within(sub, super);
83 //------------------------------------------------------------------------------
84 //- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : total
85 //------------------------------------------------------------------------------
86 template<class Type, class CoType>
87 typename enable_if< mpl::and_< is_interval_map<Type>
89 , is_cross_derivative<Type, CoType> >
91 contains(const Type&, const CoType&)
96 //------------------------------------------------------------------------------
97 //- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : partial
98 //------------------------------------------------------------------------------
100 typename enable_if< mpl::and_< is_interval_map<Type>
101 , mpl::not_<is_total<Type> > >
103 contains(const Type& super, const typename Type::domain_type& key)
105 return icl::find(super, key) != super.end();
109 typename enable_if< mpl::and_< is_interval_map<Type>
110 , mpl::not_<is_total<Type> > >
112 contains(const Type& super, const typename Type::interval_type& sub_interval)
114 typedef typename Type::const_iterator const_iterator;
116 if(icl::is_empty(sub_interval))
119 std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
120 if(exterior.first == exterior.second)
123 const_iterator last_overlap = prior(exterior.second);
126 icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
127 && Interval_Set::is_joinable(super, exterior.first, last_overlap);
130 template<class Type, class KeyT>
131 typename enable_if< mpl::and_< is_concept_combinable<is_interval_map, is_interval_set, Type, KeyT>
132 , mpl::not_<is_total<Type> > >
134 contains(const Type& super, const KeyT& sub)
136 return Interval_Set::within(sub, super);
139 //==============================================================================
140 //= Addition<IntervalMap>
141 //==============================================================================
142 //------------------------------------------------------------------------------
143 //- T& add(T&, c P&) T:{M} P:{b p} fragment_types
144 //------------------------------------------------------------------------------
146 typename enable_if<is_interval_map<Type>, Type>::type&
147 add(Type& object, const typename Type::segment_type& operand)
149 return object.add(operand);
153 typename enable_if<is_interval_map<Type>, Type>::type&
154 add(Type& object, const typename Type::element_type& operand)
156 return icl::add(object, make_segment<Type>(operand));
159 //------------------------------------------------------------------------------
160 //- T& add(T&, J, c P&) T:{M} P:{p} segment_type
161 //------------------------------------------------------------------------------
163 typename enable_if<is_interval_map<Type>, typename Type::iterator >::type
164 add(Type& object, typename Type::iterator prior_,
165 const typename Type::segment_type& operand)
167 return object.add(prior_, operand);
170 //==============================================================================
171 //= Insertion<IntervalMap>
172 //==============================================================================
173 //------------------------------------------------------------------------------
174 //- T& insert(T&, c P&) T:{M} P:{b p} fragment_types
175 //------------------------------------------------------------------------------
177 typename enable_if<is_interval_map<Type>, Type>::type&
178 insert(Type& object, const typename Type::segment_type& operand)
180 return object.insert(operand);
184 inline typename enable_if<is_interval_map<Type>, Type>::type&
185 insert(Type& object, const typename Type::element_type& operand)
187 return icl::insert(object, make_segment<Type>(operand));
190 //------------------------------------------------------------------------------
191 //- T& insert(T&, J, c P&) T:{M} P:{p} with hint
192 //------------------------------------------------------------------------------
194 typename enable_if<is_interval_map<Type>, typename Type::iterator>::type
195 insert(Type& object, typename Type::iterator prior,
196 const typename Type::segment_type& operand)
198 return object.insert(prior, operand);
202 //==============================================================================
203 //= Erasure<IntervalMap>
204 //==============================================================================
205 //------------------------------------------------------------------------------
206 //- T& erase(T&, c P&) T:{M} P:{e i} key_types
207 //------------------------------------------------------------------------------
209 typename enable_if<is_interval_map<Type>, Type>::type&
210 erase(Type& object, const typename Type::interval_type& operand)
212 return object.erase(operand);
216 typename enable_if<is_interval_map<Type>, Type>::type&
217 erase(Type& object, const typename Type::domain_type& operand)
219 typedef typename Type::interval_type interval_type;
220 return icl::erase(object, icl::singleton<interval_type>(operand));
223 //------------------------------------------------------------------------------
224 //- T& erase(T&, c P&) T:{M} P:{b p} fragment_types
225 //------------------------------------------------------------------------------
227 typename enable_if<is_interval_map<Type>, Type>::type&
228 erase(Type& object, const typename Type::segment_type& operand)
230 return object.erase(operand);
234 inline typename enable_if<is_interval_map<Type>, Type>::type&
235 erase(Type& object, const typename Type::element_type& operand)
237 return icl::erase(object, make_segment<Type>(operand));
240 //==============================================================================
241 //= Subtraction<IntervalMap>
242 //==============================================================================
243 //------------------------------------------------------------------------------
244 //- T& subtract(T&, c P&) T:{M} P:{b p} fragment_types
245 //------------------------------------------------------------------------------
247 typename enable_if<is_interval_map<Type>, Type>::type&
248 subtract(Type& object, const typename Type::segment_type& operand)
250 return object.subtract(operand);
254 typename enable_if<is_interval_map<Type>, Type>::type&
255 subtract(Type& object, const typename Type::element_type& operand)
257 return icl::subtract(object, make_segment<Type>(operand));
260 //------------------------------------------------------------------------------
261 //- T& subtract(T&, c P&) T:{M} P:{e i} key_types
262 //------------------------------------------------------------------------------
264 typename enable_if<is_interval_map<Type>, Type>::type&
265 subtract(Type& object, const typename Type::domain_type& operand)
267 return object.erase(operand);
271 typename enable_if<is_interval_map<Type>, Type>::type&
272 subtract(Type& object, const typename Type::interval_type& operand)
274 return object.erase(operand);
277 //==============================================================================
278 //= Selective Update<IntervalMap>
279 //==============================================================================
280 //------------------------------------------------------------------------------
281 //- T& set_at(T&, c P&) T:{M} P:{e i}
282 //------------------------------------------------------------------------------
284 typename enable_if<is_interval_map<Type>, Type>::type&
285 set_at(Type& object, const typename Type::segment_type& operand)
287 icl::erase(object, operand.first);
288 return icl::insert(object, operand);
292 typename enable_if<is_interval_map<Type>, Type>::type&
293 set_at(Type& object, const typename Type::element_type& operand)
295 return icl::set_at(object, make_segment<Type>(operand));
298 //==============================================================================
299 //= Intersection<IntervalMap>
300 //==============================================================================
301 //------------------------------------------------------------------------------
302 //- T& subtract(T&, c P&) T:{M} P:{b p} fragment_type
303 //------------------------------------------------------------------------------
305 typename enable_if<is_interval_map<Type>, void>::type
306 add_intersection(Type& section, const Type& object,
307 const typename Type::element_type& operand)
309 //CL typedef typename Type::segment_type segment_type;
310 object.add_intersection(section, make_segment<Type>(operand));
314 typename enable_if<is_interval_map<Type>, void>::type
315 add_intersection(Type& section, const Type& object,
316 const typename Type::segment_type& operand)
318 object.add_intersection(section, operand);
321 //------------------------------------------------------------------------------
322 //- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type total
323 //------------------------------------------------------------------------------
324 template<class Type, class MapT>
327 mpl::and_< is_total<Type>
328 , is_concept_compatible<is_interval_map, Type, MapT> >
331 add_intersection(Type& section, const Type& object, const MapT& operand)
337 //------------------------------------------------------------------------------
338 //- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type partial
339 //------------------------------------------------------------------------------
340 template<class Type, class MapT>
343 mpl::and_< mpl::not_<is_total<Type> >
344 , is_concept_compatible<is_interval_map, Type, MapT> >
347 add_intersection(Type& section, const Type& object, const MapT& operand)
349 //CL typedef typename Type::segment_type segment_type;
350 //CL typedef typename Type::interval_type interval_type;
351 typedef typename MapT::const_iterator const_iterator;
355 const_iterator common_lwb, common_upb;
356 if(!Set::common_range(common_lwb, common_upb, operand, object))
358 const_iterator it_ = common_lwb;
359 while(it_ != common_upb)
360 add_intersection(section, object, *it_++);
363 //------------------------------------------------------------------------------
364 //- T& subtract(T&, c P&) T:{M} P:{e i S} key_type
365 //------------------------------------------------------------------------------
367 typename enable_if<is_interval_map<Type>, void>::type
368 add_intersection(Type& section, const Type& object,
369 const typename Type::domain_type& key_value)
371 typedef typename Type::interval_type interval_type;
372 typedef typename Type::segment_type segment_type;
373 typedef typename Type::const_iterator const_iterator;
375 const_iterator it_ = icl::find(object, key_value);
376 if(it_ != object.end())
377 add(section, segment_type(interval_type(key_value),(*it_).second));
381 typename enable_if<is_interval_map<Type>, void>::type
382 add_intersection(Type& section, const Type& object,
383 const typename Type::interval_type& inter_val)
385 typedef typename Type::interval_type interval_type;
386 typedef typename Type::value_type value_type;
387 typedef typename Type::const_iterator const_iterator;
388 typedef typename Type::iterator iterator;
390 if(icl::is_empty(inter_val))
393 std::pair<const_iterator, const_iterator> exterior
394 = object.equal_range(inter_val);
395 if(exterior.first == exterior.second)
398 iterator prior_ = section.end();
399 for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
401 interval_type common_interval = (*it_).first & inter_val;
402 if(!icl::is_empty(common_interval))
403 prior_ = add(section, prior_,
404 value_type(common_interval, (*it_).second) );
408 template<class Type, class KeySetT>
409 typename enable_if<is_concept_combinable<is_interval_map, is_interval_set, Type, KeySetT>, void>::type
410 add_intersection(Type& section, const Type& object, const KeySetT& key_set)
412 typedef typename KeySetT::const_iterator const_iterator;
414 if(icl::is_empty(key_set))
417 const_iterator common_lwb, common_upb;
418 if(!Set::common_range(common_lwb, common_upb, key_set, object))
421 const_iterator it_ = common_lwb;
422 while(it_ != common_upb)
423 add_intersection(section, object, *it_++);
426 //------------------------------------------------------------------------------
427 //- intersects<IntervalMaps> fragment_types
428 //------------------------------------------------------------------------------
429 template<class Type, class OperandT>
430 typename enable_if<mpl::and_< is_interval_map<Type>
432 , boost::is_same< OperandT
433 , typename segment_type_of<Type>::type> >,
435 intersects(const Type&, const OperandT&)
440 template<class Type, class OperandT>
441 typename enable_if<mpl::and_< is_interval_map<Type>
442 , mpl::not_<is_total<Type> >
443 , boost::is_same<OperandT, typename segment_type_of<Type>::type> >,
445 intersects(const Type& object, const OperandT& operand)
448 icl::add_intersection(intersection, object, operand);
449 return !icl::is_empty(intersection);
452 template<class Type, class OperandT>
453 typename enable_if<mpl::and_< is_interval_map<Type>
454 , boost::is_same<OperandT, typename element_type_of<Type>::type> >,
456 intersects(const Type& object, const OperandT& operand)
458 return icl::intersects(object, make_segment<Type>(operand));
461 //==============================================================================
462 //= Symmetric difference<IntervalMap>
463 //==============================================================================
464 //------------------------------------------------------------------------------
465 //- T& flip(T&, c P&) T:{M} P:{b p} fragment_types
466 //------------------------------------------------------------------------------
468 typename enable_if<is_interval_map<Type>, Type>::type&
469 flip(Type& object, const typename Type::segment_type& operand)
471 return object.flip(operand);
475 inline typename enable_if<is_interval_map<Type>, Type>::type&
476 flip(Type& object, const typename Type::element_type& operand)
478 return icl::flip(object, make_segment<Type>(operand));
481 //------------------------------------------------------------------------------
482 //- T& flip(T&, c P&) T:{M} P:{M'} total absorber
483 //------------------------------------------------------------------------------
484 template<class Type, class OperandT>
485 typename enable_if< mpl::and_< is_total<Type>
486 , absorbs_identities<Type>
487 , is_concept_compatible<is_interval_map,
491 flip(Type& object, const OperandT&)
497 //------------------------------------------------------------------------------
498 //- T& flip(T&, c P&) T:{M} P:{M'} total enricher
499 //------------------------------------------------------------------------------
501 #pragma warning(push)
502 #pragma warning(disable:4127) // conditional expression is constant
504 template<class Type, class OperandT>
505 typename enable_if< mpl::and_< is_total<Type>
506 , mpl::not_<absorbs_identities<Type> >
507 , is_concept_compatible<is_interval_map,
511 flip(Type& object, const OperandT& operand)
513 typedef typename Type::codomain_type codomain_type;
516 ICL_FORALL(typename Type, it_, object)
517 (*it_).second = identity_element<codomain_type>::value();
519 if(mpl::not_<is_interval_splitter<Type> >::value)
529 //------------------------------------------------------------------------------
530 //- T& flip(T&, c P&) T:{M} P:{M'} partial
531 //------------------------------------------------------------------------------
532 template<class Type, class OperandT>
533 typename enable_if< mpl::and_< mpl::not_<is_total<Type> >
534 , is_concept_compatible<is_interval_map,
538 flip(Type& object, const OperandT& operand)
540 typedef typename OperandT::const_iterator const_iterator;
541 //CL typedef typename Type::codomain_type codomain_type;
543 const_iterator common_lwb, common_upb;
545 if(!Set::common_range(common_lwb, common_upb, operand, object))
546 return object += operand;
548 const_iterator it_ = operand.begin();
550 // All elements of operand left of the common range are added
551 while(it_ != common_lwb)
552 icl::add(object, *it_++);
553 // All elements of operand in the common range are symmetrically subtracted
554 while(it_ != common_upb)
555 icl::flip(object, *it_++);
556 // All elements of operand right of the common range are added
557 while(it_ != operand.end())
558 icl::add(object, *it_++);
563 //==============================================================================
565 //==============================================================================
566 template<class Type, class SetT>
567 typename enable_if<is_concept_combinable<is_interval_set, is_interval_map,
568 SetT, Type>, SetT>::type&
569 domain(SetT& result, const Type& object)
571 typedef typename SetT::iterator set_iterator;
573 set_iterator prior_ = result.end();
574 ICL_const_FORALL(typename Type, it_, object)
575 prior_ = icl::insert(result, prior_, (*it_).first);
580 template<class Type, class SetT>
581 typename enable_if<is_concept_combinable<is_interval_set, is_interval_map,
582 SetT, Type>, SetT>::type&
583 between(SetT& in_between, const Type& object)
585 typedef typename Type::const_iterator const_iterator;
586 typedef typename SetT::iterator set_iterator;
588 const_iterator it_ = object.begin(), pred_;
589 set_iterator prior_ = in_between.end();
591 if(it_ != object.end())
594 while(it_ != object.end())
595 prior_ = icl::insert(in_between, prior_,
596 between((*pred_++).first, (*it_++).first));
601 //==============================================================================
602 //= Manipulation by predicates
603 //==============================================================================
604 template<class MapT, class Predicate>
605 typename enable_if<is_interval_map<MapT>, MapT>::type&
606 erase_if(const Predicate& pred, MapT& object)
608 typename MapT::iterator it_ = object.begin();
609 while(it_ != object.end())
616 template<class MapT, class Predicate>
617 inline typename enable_if<is_interval_map<MapT>, MapT>::type&
618 add_if(const Predicate& pred, MapT& object, const MapT& src)
620 typename MapT::const_iterator it_ = src.begin();
621 while(it_ != src.end())
623 icl::add(object, *it_++);
628 template<class MapT, class Predicate>
629 inline typename enable_if<is_interval_map<MapT>, MapT>::type&
630 assign_if(const Predicate& pred, MapT& object, const MapT& src)
633 return add_if(object, src, pred);
637 //==============================================================================
639 //==============================================================================
641 typename enable_if<mpl::and_< is_interval_map<Type>
642 , absorbs_identities<Type> >, Type>::type&
643 absorb_identities(Type& object)
649 typename enable_if<mpl::and_< is_interval_map<Type>
650 , mpl::not_<absorbs_identities<Type> > >, Type>::type&
651 absorb_identities(Type& object)
653 typedef typename Type::segment_type segment_type;
654 return icl::erase_if(content_is_identity_element<segment_type>(), object);
657 //==============================================================================
659 //==============================================================================
660 template<class CharType, class CharTraits, class Type>
661 typename enable_if<is_interval_map<Type>,
662 std::basic_ostream<CharType, CharTraits> >::type&
663 operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
666 ICL_const_FORALL(typename Type, it_, object)
667 stream << "(" << (*it_).first << "->" << (*it_).second << ")";
669 return stream << "}";
673 }} // namespace boost icl