]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/icl/include/boost/icl/concept/interval_map.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / icl / include / boost / icl / concept / interval_map.hpp
CommitLineData
7c673cae
FG		 1/*-----------------------------------------------------------------------------+
2Copyright (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
10
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>
16
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>
21
22namespace boost{ namespace icl
23{
24
25template<class Type>
26inline typename enable_if<is_interval_map<Type>, typename Type::segment_type>::type
27make_segment(const typename Type::element_type& element)
28{
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);
32}
33
34
35//==============================================================================
36//= Containedness<IntervalMap>
37//==============================================================================
38//------------------------------------------------------------------------------
39//- bool contains(c T&, c P&) T:{M} P:{b p M} fragment_types
40//------------------------------------------------------------------------------
41template<class Type>
42typename enable_if<is_interval_map<Type>, bool>::type
43contains(const Type& super, const typename Type::element_type& key_value_pair)
44{
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;
48}
49
50template<class Type>
51typename enable_if<is_interval_map<Type>, bool>::type
52contains(const Type& super, const typename Type::segment_type& sub_segment)
53{
54 typedef typename Type::interval_type interval_type;
55 typedef typename Type::const_iterator const_iterator;
56
57 interval_type sub_interval = sub_segment.first;
58 if(icl::is_empty(sub_interval))
59 return true;
60
61 std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
62 if(exterior.first == exterior.second)
63 return false;
64
65 const_iterator last_overlap = prior(exterior.second);
66
67 if(!(sub_segment.second == exterior.first->second) )
68 return false;
69
70 return
71 icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
72 && Interval_Map::is_joinable(super, exterior.first, last_overlap);
73}
74
75template<class Type, class CoType>
76typename enable_if<is_concept_compatible<is_interval_map, Type, CoType>, bool>::type
77contains(const Type& super, const CoType& sub)
78{
79 return Interval_Set::within(sub, super);
80}
81
82
83//------------------------------------------------------------------------------
84//- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : total
85//------------------------------------------------------------------------------
86template<class Type, class CoType>
87typename enable_if< mpl::and_< is_interval_map<Type>
88 , is_total<Type>
89 , is_cross_derivative<Type, CoType> >
90 , bool>::type
91contains(const Type&, const CoType&)
92{
93 return true;
94}
95
96//------------------------------------------------------------------------------
97//- bool contains(c T&, c P&) T:{M} P:{e i S} key_types : partial
98//------------------------------------------------------------------------------
99template<class Type>
100typename enable_if< mpl::and_< is_interval_map<Type>
101 , mpl::not_<is_total<Type> > >
102 , bool>::type
103contains(const Type& super, const typename Type::domain_type& key)
104{
105 return icl::find(super, key) != super.end();
106}
107
108template<class Type>
109typename enable_if< mpl::and_< is_interval_map<Type>
110 , mpl::not_<is_total<Type> > >
111 , bool>::type
112contains(const Type& super, const typename Type::interval_type& sub_interval)
113{
114 typedef typename Type::const_iterator const_iterator;
115
116 if(icl::is_empty(sub_interval))
117 return true;
118
119 std::pair<const_iterator, const_iterator> exterior = super.equal_range(sub_interval);
120 if(exterior.first == exterior.second)
121 return false;
122
123 const_iterator last_overlap = prior(exterior.second);
124
125 return
126 icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
127 && Interval_Set::is_joinable(super, exterior.first, last_overlap);
128}
129
130template<class Type, class KeyT>
131typename enable_if< mpl::and_< is_concept_combinable<is_interval_map, is_interval_set, Type, KeyT>
132 , mpl::not_<is_total<Type> > >
133 , bool>::type
134contains(const Type& super, const KeyT& sub)
135{
136 return Interval_Set::within(sub, super);
137}
138
139//==============================================================================
140//= Addition<IntervalMap>
141//==============================================================================
142//------------------------------------------------------------------------------
143//- T& add(T&, c P&) T:{M} P:{b p} fragment_types
144//------------------------------------------------------------------------------
145template<class Type>
146typename enable_if<is_interval_map<Type>, Type>::type&
147add(Type& object, const typename Type::segment_type& operand)
148{
149 return object.add(operand);
150}
151
152template<class Type>
153typename enable_if<is_interval_map<Type>, Type>::type&
154add(Type& object, const typename Type::element_type& operand)
155{
156 return icl::add(object, make_segment<Type>(operand));
157}
158
159//------------------------------------------------------------------------------
160//- T& add(T&, J, c P&) T:{M} P:{p} segment_type
161//------------------------------------------------------------------------------
162template<class Type>
163typename enable_if<is_interval_map<Type>, typename Type::iterator >::type
164add(Type& object, typename Type::iterator prior_,
165 const typename Type::segment_type& operand)
166{
167 return object.add(prior_, operand);
168}
169
170//==============================================================================
171//= Insertion<IntervalMap>
172//==============================================================================
173//------------------------------------------------------------------------------
174//- T& insert(T&, c P&) T:{M} P:{b p} fragment_types
175//------------------------------------------------------------------------------
176template<class Type>
177typename enable_if<is_interval_map<Type>, Type>::type&
178insert(Type& object, const typename Type::segment_type& operand)
179{
180 return object.insert(operand);
181}
182
183template<class Type>
184inline typename enable_if<is_interval_map<Type>, Type>::type&
185insert(Type& object, const typename Type::element_type& operand)
186{
187 return icl::insert(object, make_segment<Type>(operand));
188}
189
190//------------------------------------------------------------------------------
191//- T& insert(T&, J, c P&) T:{M} P:{p} with hint
192//------------------------------------------------------------------------------
193template<class Type>
194typename enable_if<is_interval_map<Type>, typename Type::iterator>::type
195insert(Type& object, typename Type::iterator prior,
196 const typename Type::segment_type& operand)
197{
198 return object.insert(prior, operand);
199}
200
201
202//==============================================================================
203//= Erasure<IntervalMap>
204//==============================================================================
205//------------------------------------------------------------------------------
206//- T& erase(T&, c P&) T:{M} P:{e i} key_types
207//------------------------------------------------------------------------------
208template<class Type>
209typename enable_if<is_interval_map<Type>, Type>::type&
210erase(Type& object, const typename Type::interval_type& operand)
211{
212 return object.erase(operand);
213}
214
215template<class Type>
216typename enable_if<is_interval_map<Type>, Type>::type&
217erase(Type& object, const typename Type::domain_type& operand)
218{
219 typedef typename Type::interval_type interval_type;
220 return icl::erase(object, icl::singleton<interval_type>(operand));
221}
222
223//------------------------------------------------------------------------------
224//- T& erase(T&, c P&) T:{M} P:{b p} fragment_types
225//------------------------------------------------------------------------------
226template<class Type>
227typename enable_if<is_interval_map<Type>, Type>::type&
228erase(Type& object, const typename Type::segment_type& operand)
229{
230 return object.erase(operand);
231}
232
233template<class Type>
234inline typename enable_if<is_interval_map<Type>, Type>::type&
235erase(Type& object, const typename Type::element_type& operand)
236{
237 return icl::erase(object, make_segment<Type>(operand));
238}
239
240//==============================================================================
241//= Subtraction<IntervalMap>
242//==============================================================================
243//------------------------------------------------------------------------------
244//- T& subtract(T&, c P&) T:{M} P:{b p} fragment_types
245//------------------------------------------------------------------------------
246template<class Type>
247typename enable_if<is_interval_map<Type>, Type>::type&
248subtract(Type& object, const typename Type::segment_type& operand)
249{
250 return object.subtract(operand);
251}
252
253template<class Type>
254typename enable_if<is_interval_map<Type>, Type>::type&
255subtract(Type& object, const typename Type::element_type& operand)
256{
257 return icl::subtract(object, make_segment<Type>(operand));
258}
259
260//------------------------------------------------------------------------------
261//- T& subtract(T&, c P&) T:{M} P:{e i} key_types
262//------------------------------------------------------------------------------
263template<class Type>
264typename enable_if<is_interval_map<Type>, Type>::type&
265subtract(Type& object, const typename Type::domain_type& operand)
266{
267 return object.erase(operand);
268}
269
270template<class Type>
271typename enable_if<is_interval_map<Type>, Type>::type&
272subtract(Type& object, const typename Type::interval_type& operand)
273{
274 return object.erase(operand);
275}
276
277//==============================================================================
278//= Selective Update<IntervalMap>
279//==============================================================================
280//------------------------------------------------------------------------------
281//- T& set_at(T&, c P&) T:{M} P:{e i}
282//------------------------------------------------------------------------------
283template<class Type>
284typename enable_if<is_interval_map<Type>, Type>::type&
285set_at(Type& object, const typename Type::segment_type& operand)
286{
287 icl::erase(object, operand.first);
288 return icl::insert(object, operand);
289}
290
291template<class Type>
292typename enable_if<is_interval_map<Type>, Type>::type&
293set_at(Type& object, const typename Type::element_type& operand)
294{
295 return icl::set_at(object, make_segment<Type>(operand));
296}
297
298//==============================================================================
299//= Intersection<IntervalMap>
300//==============================================================================
301//------------------------------------------------------------------------------
302//- T& subtract(T&, c P&) T:{M} P:{b p} fragment_type
303//------------------------------------------------------------------------------
304template<class Type>
305typename enable_if<is_interval_map<Type>, void>::type
306add_intersection(Type& section, const Type& object,
307 const typename Type::element_type& operand)
308{
309 //CL typedef typename Type::segment_type segment_type;
310 object.add_intersection(section, make_segment<Type>(operand));
311}
312
313template<class Type>
314typename enable_if<is_interval_map<Type>, void>::type
315add_intersection(Type& section, const Type& object,
316 const typename Type::segment_type& operand)
317{
318 object.add_intersection(section, operand);
319}
320
321//------------------------------------------------------------------------------
322//- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type total
323//------------------------------------------------------------------------------
324template<class Type, class MapT>
325typename enable_if
326<
327 mpl::and_< is_total<Type>
328 , is_concept_compatible<is_interval_map, Type, MapT> >
329 , void
330>::type
331add_intersection(Type& section, const Type& object, const MapT& operand)
332{
333 section += object;
334 section += operand;
335}
336
337//------------------------------------------------------------------------------
338//- T& subtract(T&, c P&) T:{M} P:{M'} map fragment_type partial
339//------------------------------------------------------------------------------
340template<class Type, class MapT>
341typename enable_if
342<
343 mpl::and_< mpl::not_<is_total<Type> >
344 , is_concept_compatible<is_interval_map, Type, MapT> >
345 , void
346>::type
347add_intersection(Type& section, const Type& object, const MapT& operand)
348{
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;
352
353 if(operand.empty())
354 return;
355 const_iterator common_lwb, common_upb;
356 if(!Set::common_range(common_lwb, common_upb, operand, object))
357 return;
358 const_iterator it_ = common_lwb;
359 while(it_ != common_upb)
360 add_intersection(section, object, *it_++);
361}
362
363//------------------------------------------------------------------------------
364//- T& subtract(T&, c P&) T:{M} P:{e i S} key_type
365//------------------------------------------------------------------------------
366template<class Type>
367typename enable_if<is_interval_map<Type>, void>::type
368add_intersection(Type& section, const Type& object,
369 const typename Type::domain_type& key_value)
370{
371 typedef typename Type::interval_type interval_type;
372 typedef typename Type::segment_type segment_type;
373 typedef typename Type::const_iterator const_iterator;
374
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));
378}
379
380template<class Type>
381typename enable_if<is_interval_map<Type>, void>::type
382add_intersection(Type& section, const Type& object,
383 const typename Type::interval_type& inter_val)
384{
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;
389
390 if(icl::is_empty(inter_val))
391 return;
392
393 std::pair<const_iterator, const_iterator> exterior
394 = object.equal_range(inter_val);
395 if(exterior.first == exterior.second)
396 return;
397
398 iterator prior_ = section.end();
399 for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
400 {
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) );
405 }
406}
407
408template<class Type, class KeySetT>
409typename enable_if<is_concept_combinable<is_interval_map, is_interval_set, Type, KeySetT>, void>::type
410add_intersection(Type& section, const Type& object, const KeySetT& key_set)
411{
412 typedef typename KeySetT::const_iterator const_iterator;
413
414 if(icl::is_empty(key_set))
415 return;
416
417 const_iterator common_lwb, common_upb;
418 if(!Set::common_range(common_lwb, common_upb, key_set, object))
419 return;
420
421 const_iterator it_ = common_lwb;
422 while(it_ != common_upb)
423 add_intersection(section, object, *it_++);
424}
425
426//------------------------------------------------------------------------------
427//- intersects<IntervalMaps> fragment_types
428//------------------------------------------------------------------------------
429template<class Type, class OperandT>
430typename enable_if<mpl::and_< is_interval_map<Type>
431 , is_total<Type>
432 , boost::is_same< OperandT
433 , typename segment_type_of<Type>::type> >,
434 bool>::type
435intersects(const Type&, const OperandT&)
436{
437 return true;
438}
439
440template<class Type, class OperandT>
441typename 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> >,
444 bool>::type
445intersects(const Type& object, const OperandT& operand)
446{
447 Type intersection;
448 icl::add_intersection(intersection, object, operand);
449 return !icl::is_empty(intersection);
450}
451
452template<class Type, class OperandT>
453typename enable_if<mpl::and_< is_interval_map<Type>
454 , boost::is_same<OperandT, typename element_type_of<Type>::type> >,
455 bool>::type
456intersects(const Type& object, const OperandT& operand)
457{
458 return icl::intersects(object, make_segment<Type>(operand));
459}
460
461//==============================================================================
462//= Symmetric difference<IntervalMap>
463//==============================================================================
464//------------------------------------------------------------------------------
465//- T& flip(T&, c P&) T:{M} P:{b p} fragment_types
466//------------------------------------------------------------------------------
467template<class Type>
468typename enable_if<is_interval_map<Type>, Type>::type&
469flip(Type& object, const typename Type::segment_type& operand)
470{
471 return object.flip(operand);
472}
473
474template<class Type>
475inline typename enable_if<is_interval_map<Type>, Type>::type&
476flip(Type& object, const typename Type::element_type& operand)
477{
478 return icl::flip(object, make_segment<Type>(operand));
479}
480
481//------------------------------------------------------------------------------
482//- T& flip(T&, c P&) T:{M} P:{M'} total absorber
483//------------------------------------------------------------------------------
484template<class Type, class OperandT>
485typename enable_if< mpl::and_< is_total<Type>
486 , absorbs_identities<Type>
487 , is_concept_compatible<is_interval_map,
488 Type, OperandT >
489 >
490 , Type>::type&
491flip(Type& object, const OperandT&)
492{
493 object.clear();
494 return object;
495}
496
497//------------------------------------------------------------------------------
498//- T& flip(T&, c P&) T:{M} P:{M'} total enricher
499//------------------------------------------------------------------------------
500#ifdef BOOST_MSVC
501#pragma warning(push)
502#pragma warning(disable:4127) // conditional expression is constant
503#endif
504template<class Type, class OperandT>
505typename enable_if< mpl::and_< is_total<Type>
506 , mpl::not_<absorbs_identities<Type> >
507 , is_concept_compatible<is_interval_map,
508 Type, OperandT >
509 >
510 , Type>::type&
511flip(Type& object, const OperandT& operand)
512{
513 typedef typename Type::codomain_type codomain_type;
514
515 object += operand;
516 ICL_FORALL(typename Type, it_, object)
517 (*it_).second = identity_element<codomain_type>::value();
518
519 if(mpl::not_<is_interval_splitter<Type> >::value)
520 icl::join(object);
521
522 return object;
523}
524#ifdef BOOST_MSVC
525#pragma warning(pop)
526#endif
527
528
529//------------------------------------------------------------------------------
530//- T& flip(T&, c P&) T:{M} P:{M'} partial
531//------------------------------------------------------------------------------
532template<class Type, class OperandT>
533typename enable_if< mpl::and_< mpl::not_<is_total<Type> >
534 , is_concept_compatible<is_interval_map,
535 Type, OperandT >
536 >
537 , Type>::type&
538flip(Type& object, const OperandT& operand)
539{
540 typedef typename OperandT::const_iterator const_iterator;
541 //CL typedef typename Type::codomain_type codomain_type;
542
543 const_iterator common_lwb, common_upb;
544
545 if(!Set::common_range(common_lwb, common_upb, operand, object))
546 return object += operand;
547
548 const_iterator it_ = operand.begin();
549
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_++);
559
560 return object;
561}
562
563//==============================================================================
564//= Set selection
565//==============================================================================
566template<class Type, class SetT>
567typename enable_if<is_concept_combinable<is_interval_set, is_interval_map,
568 SetT, Type>, SetT>::type&
569domain(SetT& result, const Type& object)
570{
571 typedef typename SetT::iterator set_iterator;
572 result.clear();
573 set_iterator prior_ = result.end();
574 ICL_const_FORALL(typename Type, it_, object)
575 prior_ = icl::insert(result, prior_, (*it_).first);
576
577 return result;
578}
579
580template<class Type, class SetT>
581typename enable_if<is_concept_combinable<is_interval_set, is_interval_map,
582 SetT, Type>, SetT>::type&
583between(SetT& in_between, const Type& object)
584{
585 typedef typename Type::const_iterator const_iterator;
586 typedef typename SetT::iterator set_iterator;
587 in_between.clear();
588 const_iterator it_ = object.begin(), pred_;
589 set_iterator prior_ = in_between.end();
590
591 if(it_ != object.end())
592 pred_ = it_++;
593
594 while(it_ != object.end())
595 prior_ = icl::insert(in_between, prior_,
596 between((*pred_++).first, (*it_++).first));
597
598 return in_between;
599}
600
601//==============================================================================
602//= Manipulation by predicates
603//==============================================================================
604template<class MapT, class Predicate>
605typename enable_if<is_interval_map<MapT>, MapT>::type&
606erase_if(const Predicate& pred, MapT& object)
607{
608 typename MapT::iterator it_ = object.begin();
609 while(it_ != object.end())
610 if(pred(*it_))
611 object.erase(it_++);
612 else ++it_;
613 return object;
614}
615
616template<class MapT, class Predicate>
617inline typename enable_if<is_interval_map<MapT>, MapT>::type&
618add_if(const Predicate& pred, MapT& object, const MapT& src)
619{
620 typename MapT::const_iterator it_ = src.begin();
621 while(it_ != src.end())
622 if(pred(*it_))
623 icl::add(object, *it_++);
624
625 return object;
626}
627
628template<class MapT, class Predicate>
629inline typename enable_if<is_interval_map<MapT>, MapT>::type&
630assign_if(const Predicate& pred, MapT& object, const MapT& src)
631{
632 icl::clear(object);
633 return add_if(object, src, pred);
634}
635
636
637//==============================================================================
638//= Morphisms
639//==============================================================================
640template<class Type>
641typename enable_if<mpl::and_< is_interval_map<Type>
642 , absorbs_identities<Type> >, Type>::type&
643absorb_identities(Type& object)
644{
645 return object;
646}
647
648template<class Type>
649typename enable_if<mpl::and_< is_interval_map<Type>
650 , mpl::not_<absorbs_identities<Type> > >, Type>::type&
651absorb_identities(Type& object)
652{
653 typedef typename Type::segment_type segment_type;
654 return icl::erase_if(content_is_identity_element<segment_type>(), object);
655}
656
657//==============================================================================
658//= Streaming
659//==============================================================================
660template<class CharType, class CharTraits, class Type>
661typename enable_if<is_interval_map<Type>,
662 std::basic_ostream<CharType, CharTraits> >::type&
663operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
664{
665 stream << "{";
666 ICL_const_FORALL(typename Type, it_, object)
667 stream << "(" << (*it_).first << "->" << (*it_).second << ")";
668
669 return stream << "}";
670}
671
672
673}} // namespace boost icl
674
675#endif
676
677
Ceph