]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
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 | ||
22 | namespace boost{ namespace icl | |
23 | { | |
24 | ||
25 | template<class Type> | |
26 | inline typename enable_if<is_interval_map<Type>, typename Type::segment_type>::type | |
27 | make_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 | //------------------------------------------------------------------------------ | |
41 | template<class Type> | |
42 | typename enable_if<is_interval_map<Type>, bool>::type | |
43 | contains(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 | ||
50 | template<class Type> | |
51 | typename enable_if<is_interval_map<Type>, bool>::type | |
52 | contains(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 | ||
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) | |
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 | //------------------------------------------------------------------------------ | |
86 | template<class Type, class CoType> | |
87 | typename enable_if< mpl::and_< is_interval_map<Type> | |
88 | , is_total<Type> | |
89 | , is_cross_derivative<Type, CoType> > | |
90 | , bool>::type | |
91 | contains(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 | //------------------------------------------------------------------------------ | |
99 | template<class Type> | |
100 | typename enable_if< mpl::and_< is_interval_map<Type> | |
101 | , mpl::not_<is_total<Type> > > | |
102 | , bool>::type | |
103 | contains(const Type& super, const typename Type::domain_type& key) | |
104 | { | |
105 | return icl::find(super, key) != super.end(); | |
106 | } | |
107 | ||
108 | template<class Type> | |
109 | typename enable_if< mpl::and_< is_interval_map<Type> | |
110 | , mpl::not_<is_total<Type> > > | |
111 | , bool>::type | |
112 | contains(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 | ||
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> > > | |
133 | , bool>::type | |
134 | contains(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 | //------------------------------------------------------------------------------ | |
145 | template<class Type> | |
146 | typename enable_if<is_interval_map<Type>, Type>::type& | |
147 | add(Type& object, const typename Type::segment_type& operand) | |
148 | { | |
149 | return object.add(operand); | |
150 | } | |
151 | ||
152 | template<class Type> | |
153 | typename enable_if<is_interval_map<Type>, Type>::type& | |
154 | add(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 | //------------------------------------------------------------------------------ | |
162 | template<class Type> | |
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) | |
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 | //------------------------------------------------------------------------------ | |
176 | template<class Type> | |
177 | typename enable_if<is_interval_map<Type>, Type>::type& | |
178 | insert(Type& object, const typename Type::segment_type& operand) | |
179 | { | |
180 | return object.insert(operand); | |
181 | } | |
182 | ||
183 | template<class Type> | |
184 | inline typename enable_if<is_interval_map<Type>, Type>::type& | |
185 | insert(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 | //------------------------------------------------------------------------------ | |
193 | template<class Type> | |
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) | |
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 | //------------------------------------------------------------------------------ | |
208 | template<class Type> | |
209 | typename enable_if<is_interval_map<Type>, Type>::type& | |
210 | erase(Type& object, const typename Type::interval_type& operand) | |
211 | { | |
212 | return object.erase(operand); | |
213 | } | |
214 | ||
215 | template<class Type> | |
216 | typename enable_if<is_interval_map<Type>, Type>::type& | |
217 | erase(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 | //------------------------------------------------------------------------------ | |
226 | template<class Type> | |
227 | typename enable_if<is_interval_map<Type>, Type>::type& | |
228 | erase(Type& object, const typename Type::segment_type& operand) | |
229 | { | |
230 | return object.erase(operand); | |
231 | } | |
232 | ||
233 | template<class Type> | |
234 | inline typename enable_if<is_interval_map<Type>, Type>::type& | |
235 | erase(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 | //------------------------------------------------------------------------------ | |
246 | template<class Type> | |
247 | typename enable_if<is_interval_map<Type>, Type>::type& | |
248 | subtract(Type& object, const typename Type::segment_type& operand) | |
249 | { | |
250 | return object.subtract(operand); | |
251 | } | |
252 | ||
253 | template<class Type> | |
254 | typename enable_if<is_interval_map<Type>, Type>::type& | |
255 | subtract(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 | //------------------------------------------------------------------------------ | |
263 | template<class Type> | |
264 | typename enable_if<is_interval_map<Type>, Type>::type& | |
265 | subtract(Type& object, const typename Type::domain_type& operand) | |
266 | { | |
267 | return object.erase(operand); | |
268 | } | |
269 | ||
270 | template<class Type> | |
271 | typename enable_if<is_interval_map<Type>, Type>::type& | |
272 | subtract(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 | //------------------------------------------------------------------------------ | |
283 | template<class Type> | |
284 | typename enable_if<is_interval_map<Type>, Type>::type& | |
285 | set_at(Type& object, const typename Type::segment_type& operand) | |
286 | { | |
287 | icl::erase(object, operand.first); | |
288 | return icl::insert(object, operand); | |
289 | } | |
290 | ||
291 | template<class Type> | |
292 | typename enable_if<is_interval_map<Type>, Type>::type& | |
293 | set_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 | //------------------------------------------------------------------------------ | |
304 | template<class Type> | |
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) | |
308 | { | |
309 | //CL typedef typename Type::segment_type segment_type; | |
310 | object.add_intersection(section, make_segment<Type>(operand)); | |
311 | } | |
312 | ||
313 | template<class Type> | |
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) | |
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 | //------------------------------------------------------------------------------ | |
324 | template<class Type, class MapT> | |
325 | typename enable_if | |
326 | < | |
327 | mpl::and_< is_total<Type> | |
328 | , is_concept_compatible<is_interval_map, Type, MapT> > | |
329 | , void | |
330 | >::type | |
331 | add_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 | //------------------------------------------------------------------------------ | |
340 | template<class Type, class MapT> | |
341 | typename enable_if | |
342 | < | |
343 | mpl::and_< mpl::not_<is_total<Type> > | |
344 | , is_concept_compatible<is_interval_map, Type, MapT> > | |
345 | , void | |
346 | >::type | |
347 | add_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 | //------------------------------------------------------------------------------ | |
366 | template<class Type> | |
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) | |
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 | ||
380 | template<class Type> | |
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) | |
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 | ||
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) | |
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 | //------------------------------------------------------------------------------ | |
429 | template<class Type, class OperandT> | |
430 | typename 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 | |
435 | intersects(const Type&, const OperandT&) | |
436 | { | |
437 | return true; | |
438 | } | |
439 | ||
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> >, | |
444 | bool>::type | |
445 | intersects(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 | ||
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> >, | |
455 | bool>::type | |
456 | intersects(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 | //------------------------------------------------------------------------------ | |
467 | template<class Type> | |
468 | typename enable_if<is_interval_map<Type>, Type>::type& | |
469 | flip(Type& object, const typename Type::segment_type& operand) | |
470 | { | |
471 | return object.flip(operand); | |
472 | } | |
473 | ||
474 | template<class Type> | |
475 | inline typename enable_if<is_interval_map<Type>, Type>::type& | |
476 | flip(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 | //------------------------------------------------------------------------------ | |
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, | |
488 | Type, OperandT > | |
489 | > | |
490 | , Type>::type& | |
491 | flip(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 | |
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, | |
508 | Type, OperandT > | |
509 | > | |
510 | , Type>::type& | |
511 | flip(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 | //------------------------------------------------------------------------------ | |
532 | template<class Type, class OperandT> | |
533 | typename enable_if< mpl::and_< mpl::not_<is_total<Type> > | |
534 | , is_concept_compatible<is_interval_map, | |
535 | Type, OperandT > | |
536 | > | |
537 | , Type>::type& | |
538 | flip(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 | //============================================================================== | |
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) | |
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 | ||
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) | |
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 | //============================================================================== | |
604 | template<class MapT, class Predicate> | |
605 | typename enable_if<is_interval_map<MapT>, MapT>::type& | |
606 | erase_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 | ||
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) | |
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 | ||
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) | |
631 | { | |
632 | icl::clear(object); | |
633 | return add_if(object, src, pred); | |
634 | } | |
635 | ||
636 | ||
637 | //============================================================================== | |
638 | //= Morphisms | |
639 | //============================================================================== | |
640 | template<class Type> | |
641 | typename enable_if<mpl::and_< is_interval_map<Type> | |
642 | , absorbs_identities<Type> >, Type>::type& | |
643 | absorb_identities(Type& object) | |
644 | { | |
645 | return object; | |
646 | } | |
647 | ||
648 | template<class Type> | |
649 | typename enable_if<mpl::and_< is_interval_map<Type> | |
650 | , mpl::not_<absorbs_identities<Type> > >, Type>::type& | |
651 | absorb_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 | //============================================================================== | |
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) | |
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 |