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_SET_HPP_JOFA_100920
9 #define BOOST_ICL_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
10
11 #include <boost/icl/type_traits/is_combinable.hpp>
12 #include <boost/icl/type_traits/interval_type_of.hpp>
13 #include <boost/icl/detail/set_algo.hpp>
14 #include <boost/icl/detail/interval_set_algo.hpp>
15 #include <boost/icl/concept/interval.hpp>
16
17 namespace boost{ namespace icl
18 {
19
20 //==============================================================================
21 //= Containedness<IntervalSet>
22 //==============================================================================
23 //------------------------------------------------------------------------------
24 //- bool contains(c T&, c P&) T:{S} P:{e i S} fragment_types
25 //------------------------------------------------------------------------------
26 template<class Type>
27 typename enable_if<is_interval_set<Type>, bool>::type
contains(const Type & super,const typename Type::element_type & element)28 contains(const Type& super, const typename Type::element_type& element)
29 {
30 return !(icl::find(super, element) == super.end());
31 }
32
33 template<class Type>
34 typename enable_if<is_interval_set<Type>, bool>::type
contains(const Type & super,const typename Type::segment_type & inter_val)35 contains(const Type& super, const typename Type::segment_type& inter_val)
36 {
37 typedef typename Type::const_iterator const_iterator;
38 if(icl::is_empty(inter_val))
39 return true;
40
41 std::pair<const_iterator, const_iterator> exterior
42 = super.equal_range(inter_val);
43 if(exterior.first == exterior.second)
44 return false;
45
46 const_iterator last_overlap = cyclic_prior(super, exterior.second);
47
48 return
49 icl::contains(hull(*(exterior.first), *last_overlap), inter_val)
50 && Interval_Set::is_joinable(super, exterior.first, last_overlap);
51 }
52
53 template<class Type, class OperandT>
54 typename enable_if<has_same_concept<is_interval_set, Type, OperandT>,
55 bool>::type
contains(const Type & super,const OperandT & sub)56 contains(const Type& super, const OperandT& sub)
57 {
58 return Interval_Set::contains(super, sub);
59 }
60
61 //==============================================================================
62 //= Addition<IntervalSet>
63 //==============================================================================
64 //------------------------------------------------------------------------------
65 //- T& add(T&, c P&) T:{S} P:{e i} fragment_types
66 //------------------------------------------------------------------------------
67 template<class Type>
68 typename enable_if<is_interval_set<Type>, Type>::type&
add(Type & object,const typename Type::segment_type & operand)69 add(Type& object, const typename Type::segment_type& operand)
70 {
71 return object.add(operand);
72 }
73
74 template<class Type>
75 inline typename enable_if<is_interval_set<Type>, Type>::type&
add(Type & object,const typename Type::element_type & operand)76 add(Type& object, const typename Type::element_type& operand)
77 {
78 typedef typename Type::segment_type segment_type;
79 return icl::add(object, icl::singleton<segment_type>(operand));
80 }
81
82 //------------------------------------------------------------------------------
83 //- T& add(T&, J, c P&) T:{S} P:{i} interval_type
84 //------------------------------------------------------------------------------
85 template<class Type>
86 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
add(Type & object,typename Type::iterator prior,const typename Type::segment_type & operand)87 add(Type& object, typename Type::iterator prior,
88 const typename Type::segment_type& operand)
89 {
90 return object.add(prior, operand);
91 }
92
93 //==============================================================================
94 //= Insertion<IntervalSet>
95 //==============================================================================
96 //------------------------------------------------------------------------------
97 //- T& insert(T&, c P&) T:{S} P:{e i} fragment_types
98 //------------------------------------------------------------------------------
99 template<class Type>
100 inline typename enable_if<is_interval_set<Type>, Type>::type&
insert(Type & object,const typename Type::segment_type & operand)101 insert(Type& object, const typename Type::segment_type& operand)
102 {
103 return icl::add(object, operand);
104 }
105
106 template<class Type>
107 inline typename enable_if<is_interval_set<Type>, Type>::type&
insert(Type & object,const typename Type::element_type & operand)108 insert(Type& object, const typename Type::element_type& operand)
109 {
110 return icl::add(object, operand);
111 }
112
113 //------------------------------------------------------------------------------
114 //- T& insert(T&, J, c P&) T:{S} P:{i} with hint
115 //------------------------------------------------------------------------------
116 template<class Type>
117 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
insert(Type & object,typename Type::iterator prior,const typename Type::segment_type & operand)118 insert(Type& object, typename Type::iterator prior,
119 const typename Type::segment_type& operand)
120 {
121 return icl::add(object, prior, operand);
122 }
123
124 //==============================================================================
125 //= Subtraction<IntervalSet>
126 //==============================================================================
127 //------------------------------------------------------------------------------
128 //- T& subtract(T&, c P&) T:{S} P:{e i} fragment_type
129 //------------------------------------------------------------------------------
130 template<class Type>
131 typename enable_if<is_interval_set<Type>, Type>::type&
subtract(Type & object,const typename Type::segment_type & operand)132 subtract(Type& object, const typename Type::segment_type& operand)
133 {
134 return object.subtract(operand);
135 }
136
137 template<class Type>
138 inline typename enable_if<is_interval_set<Type>, Type>::type&
subtract(Type & object,const typename Type::element_type & operand)139 subtract(Type& object, const typename Type::element_type& operand)
140 {
141 typedef typename Type::segment_type segment_type;
142 return icl::subtract(object, icl::singleton<segment_type>(operand));
143 }
144
145 //==============================================================================
146 //= Erasure<IntervalSet>
147 //==============================================================================
148 //------------------------------------------------------------------------------
149 //- T& erase(T&, c P&) T:{S} P:{e i} fragment_types
150 //------------------------------------------------------------------------------
151 template<class Type>
152 typename enable_if<is_interval_set<Type>, Type>::type&
erase(Type & object,const typename Type::segment_type & minuend)153 erase(Type& object, const typename Type::segment_type& minuend)
154 {
155 return icl::subtract(object, minuend);
156 }
157
158 template<class Type>
159 typename enable_if<is_interval_set<Type>, Type>::type&
erase(Type & object,const typename Type::element_type & minuend)160 erase(Type& object, const typename Type::element_type& minuend)
161 {
162 return icl::subtract(object, minuend);
163 }
164
165 //==============================================================================
166 //= Intersection
167 //==============================================================================
168 //------------------------------------------------------------------------------
169 //- void add_intersection(T&, c T&, c P&) T:{S} P:{e i} fragment_types
170 //------------------------------------------------------------------------------
171 template<class Type>
172 typename enable_if<is_interval_set<Type>, void>::type
add_intersection(Type & section,const Type & object,const typename Type::element_type & operand)173 add_intersection(Type& section, const Type& object,
174 const typename Type::element_type& operand)
175 {
176 typedef typename Type::const_iterator const_iterator;
177 const_iterator found = icl::find(object, operand);
178 if(found != object.end())
179 icl::add(section, operand);
180 }
181
182
183 template<class Type>
184 typename enable_if<is_interval_set<Type>, void>::type
add_intersection(Type & section,const Type & object,const typename Type::segment_type & segment)185 add_intersection(Type& section, const Type& object,
186 const typename Type::segment_type& segment)
187 {
188 typedef typename Type::const_iterator const_iterator;
189 typedef typename Type::iterator iterator;
190 typedef typename Type::interval_type interval_type;
191
192 if(icl::is_empty(segment))
193 return;
194
195 std::pair<const_iterator, const_iterator> exterior
196 = object.equal_range(segment);
197 if(exterior.first == exterior.second)
198 return;
199
200 iterator prior_ = section.end();
201 for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
202 {
203 interval_type common_interval = key_value<Type>(it_) & segment;
204 if(!icl::is_empty(common_interval))
205 prior_ = section.insert(prior_, common_interval);
206 }
207 }
208
209 //==============================================================================
210 //= Symmetric difference<IntervalSet>
211 //==============================================================================
212 //------------------------------------------------------------------------------
213 //- T& flip(T&, c P&) T:{S} P:{e i S'} fragment_types
214 //------------------------------------------------------------------------------
215 template<class Type>
216 typename enable_if<is_interval_set<Type>, Type>::type&
flip(Type & object,const typename Type::element_type & operand)217 flip(Type& object, const typename Type::element_type& operand)
218 {
219 if(icl::contains(object, operand))
220 return object -= operand;
221 else
222 return object += operand;
223 }
224
225 template<class Type>
226 typename enable_if<is_interval_set<Type>, Type>::type&
flip(Type & object,const typename Type::segment_type & segment)227 flip(Type& object, const typename Type::segment_type& segment)
228 {
229 typedef typename Type::const_iterator const_iterator;
230 typedef typename Type::interval_type interval_type;
231 // That which is common shall be subtracted
232 // That which is not shall be added
233 // So x has to be 'complementary added' or flipped
234 interval_type span = segment;
235 std::pair<const_iterator, const_iterator> exterior
236 = object.equal_range(span);
237
238 const_iterator fst_ = exterior.first;
239 const_iterator end_ = exterior.second;
240
241 interval_type covered, left_over;
242 const_iterator it_ = fst_;
243 while(it_ != end_)
244 {
245 covered = *it_++;
246 //[a ... : span
247 // [b ... : covered
248 //[a b) : left_over
249 left_over = right_subtract(span, covered);
250 icl::subtract(object, span & covered); //That which is common shall be subtracted
251 icl::add(object, left_over); //That which is not shall be added
252
253 //... d) : span
254 //... c) : covered
255 // [c d) : span'
256 span = left_subtract(span, covered);
257 }
258
259 //If span is not empty here, it_ is not in the set so it_ shall be added
260 icl::add(object, span);
261 return object;
262 }
263
264
265 template<class Type, class OperandT>
266 typename enable_if<is_concept_compatible<is_interval_set, Type, OperandT>, Type>::type&
flip(Type & object,const OperandT & operand)267 flip(Type& object, const OperandT& operand)
268 {
269 typedef typename OperandT::const_iterator const_iterator;
270
271 if(operand.empty())
272 return object;
273
274 const_iterator common_lwb, common_upb;
275
276 if(!Set::common_range(common_lwb, common_upb, operand, object))
277 return object += operand;
278
279 const_iterator it_ = operand.begin();
280
281 // All elements of operand left of the common range are added
282 while(it_ != common_lwb)
283 icl::add(object, *it_++);
284 // All elements of operand in the common range are symmertrically subtracted
285 while(it_ != common_upb)
286 icl::flip(object, *it_++);
287 // All elements of operand right of the common range are added
288 while(it_ != operand.end())
289 icl::add(object, *it_++);
290
291 return object;
292 }
293
294 //==============================================================================
295 //= Set selection
296 //==============================================================================
297 template<class Type>
298 typename enable_if<is_interval_set<Type>, Type>::type&
domain(Type & dom,const Type & object)299 domain(Type& dom, const Type& object)
300 {
301 typedef typename Type::const_iterator const_iterator;
302 typedef typename Type::iterator iterator;
303 dom.clear();
304 const_iterator it_ = object.begin();
305 iterator prior_ = dom.end();
306
307 while(it_ != object.end())
308 prior_ = icl::insert(dom, prior_, *it_++);
309
310 return dom;
311 }
312
313 template<class Type>
314 typename enable_if<is_interval_set<Type>, Type>::type&
between(Type & in_between,const Type & object)315 between(Type& in_between, const Type& object)
316 {
317 typedef typename Type::const_iterator const_iterator;
318 typedef typename Type::iterator iterator;
319 in_between.clear();
320 const_iterator it_ = object.begin(), pred_;
321 iterator prior_ = in_between.end();
322
323 if(it_ != object.end())
324 pred_ = it_++;
325
326 while(it_ != object.end())
327 prior_ = icl::insert(in_between, prior_,
328 icl::between(*pred_++, *it_++));
329
330 return in_between;
331 }
332
333
334 //==============================================================================
335 //= Streaming
336 //==============================================================================
337 template<class CharType, class CharTraits, class Type>
338 typename enable_if<is_interval_set<Type>,
339 std::basic_ostream<CharType, CharTraits> >::type&
operator <<(std::basic_ostream<CharType,CharTraits> & stream,const Type & object)340 operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
341 {
342 stream << "{";
343 ICL_const_FORALL(typename Type, it_, object)
344 stream << (*it_);
345
346 return stream << "}";
347 }
348
349
350 }} // namespace boost icl
351
352 #endif
353
354
355