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
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>
17 namespace boost{ namespace icl
20 //==============================================================================
21 //= Containedness<IntervalSet>
22 //==============================================================================
23 //------------------------------------------------------------------------------
24 //- bool contains(c T&, c P&) T:{S} P:{e i S} fragment_types
25 //------------------------------------------------------------------------------
27 typename enable_if<is_interval_set<Type>, bool>::type
28 contains(const Type& super, const typename Type::element_type& element)
30 return !(icl::find(super, element) == super.end());
34 typename enable_if<is_interval_set<Type>, bool>::type
35 contains(const Type& super, const typename Type::segment_type& inter_val)
37 typedef typename Type::const_iterator const_iterator;
38 if(icl::is_empty(inter_val))
41 std::pair<const_iterator, const_iterator> exterior
42 = super.equal_range(inter_val);
43 if(exterior.first == exterior.second)
46 const_iterator last_overlap = cyclic_prior(super, exterior.second);
49 icl::contains(hull(*(exterior.first), *last_overlap), inter_val)
50 && Interval_Set::is_joinable(super, exterior.first, last_overlap);
53 template<class Type, class OperandT>
54 typename enable_if<has_same_concept<is_interval_set, Type, OperandT>,
56 contains(const Type& super, const OperandT& sub)
58 return Interval_Set::contains(super, sub);
61 //==============================================================================
62 //= Addition<IntervalSet>
63 //==============================================================================
64 //------------------------------------------------------------------------------
65 //- T& add(T&, c P&) T:{S} P:{e i} fragment_types
66 //------------------------------------------------------------------------------
68 typename enable_if<is_interval_set<Type>, Type>::type&
69 add(Type& object, const typename Type::segment_type& operand)
71 return object.add(operand);
75 inline typename enable_if<is_interval_set<Type>, Type>::type&
76 add(Type& object, const typename Type::element_type& operand)
78 typedef typename Type::segment_type segment_type;
79 return icl::add(object, icl::singleton<segment_type>(operand));
82 //------------------------------------------------------------------------------
83 //- T& add(T&, J, c P&) T:{S} P:{i} interval_type
84 //------------------------------------------------------------------------------
86 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
87 add(Type& object, typename Type::iterator prior,
88 const typename Type::segment_type& operand)
90 return object.add(prior, operand);
93 //==============================================================================
94 //= Insertion<IntervalSet>
95 //==============================================================================
96 //------------------------------------------------------------------------------
97 //- T& insert(T&, c P&) T:{S} P:{e i} fragment_types
98 //------------------------------------------------------------------------------
100 inline typename enable_if<is_interval_set<Type>, Type>::type&
101 insert(Type& object, const typename Type::segment_type& operand)
103 return icl::add(object, operand);
107 inline typename enable_if<is_interval_set<Type>, Type>::type&
108 insert(Type& object, const typename Type::element_type& operand)
110 return icl::add(object, operand);
113 //------------------------------------------------------------------------------
114 //- T& insert(T&, J, c P&) T:{S} P:{i} with hint
115 //------------------------------------------------------------------------------
117 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
118 insert(Type& object, typename Type::iterator prior,
119 const typename Type::segment_type& operand)
121 return icl::add(object, prior, operand);
124 //==============================================================================
125 //= Subtraction<IntervalSet>
126 //==============================================================================
127 //------------------------------------------------------------------------------
128 //- T& subtract(T&, c P&) T:{S} P:{e i} fragment_type
129 //------------------------------------------------------------------------------
131 typename enable_if<is_interval_set<Type>, Type>::type&
132 subtract(Type& object, const typename Type::segment_type& operand)
134 return object.subtract(operand);
138 inline typename enable_if<is_interval_set<Type>, Type>::type&
139 subtract(Type& object, const typename Type::element_type& operand)
141 typedef typename Type::segment_type segment_type;
142 return icl::subtract(object, icl::singleton<segment_type>(operand));
145 //==============================================================================
146 //= Erasure<IntervalSet>
147 //==============================================================================
148 //------------------------------------------------------------------------------
149 //- T& erase(T&, c P&) T:{S} P:{e i} fragment_types
150 //------------------------------------------------------------------------------
152 typename enable_if<is_interval_set<Type>, Type>::type&
153 erase(Type& object, const typename Type::segment_type& minuend)
155 return icl::subtract(object, minuend);
159 typename enable_if<is_interval_set<Type>, Type>::type&
160 erase(Type& object, const typename Type::element_type& minuend)
162 return icl::subtract(object, minuend);
165 //==============================================================================
167 //==============================================================================
168 //------------------------------------------------------------------------------
169 //- void add_intersection(T&, c T&, c P&) T:{S} P:{e i} fragment_types
170 //------------------------------------------------------------------------------
172 typename enable_if<is_interval_set<Type>, void>::type
173 add_intersection(Type& section, const Type& object,
174 const typename Type::element_type& operand)
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);
184 typename enable_if<is_interval_set<Type>, void>::type
185 add_intersection(Type& section, const Type& object,
186 const typename Type::segment_type& segment)
188 typedef typename Type::const_iterator const_iterator;
189 typedef typename Type::iterator iterator;
190 typedef typename Type::interval_type interval_type;
192 if(icl::is_empty(segment))
195 std::pair<const_iterator, const_iterator> exterior
196 = object.equal_range(segment);
197 if(exterior.first == exterior.second)
200 iterator prior_ = section.end();
201 for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
203 interval_type common_interval = key_value<Type>(it_) & segment;
204 if(!icl::is_empty(common_interval))
205 prior_ = section.insert(prior_, common_interval);
209 //==============================================================================
210 //= Symmetric difference<IntervalSet>
211 //==============================================================================
212 //------------------------------------------------------------------------------
213 //- T& flip(T&, c P&) T:{S} P:{e i S'} fragment_types
214 //------------------------------------------------------------------------------
216 typename enable_if<is_interval_set<Type>, Type>::type&
217 flip(Type& object, const typename Type::element_type& operand)
219 if(icl::contains(object, operand))
220 return object -= operand;
222 return object += operand;
226 typename enable_if<is_interval_set<Type>, Type>::type&
227 flip(Type& object, const typename Type::segment_type& segment)
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);
238 const_iterator fst_ = exterior.first;
239 const_iterator end_ = exterior.second;
241 interval_type covered, left_over;
242 const_iterator it_ = fst_;
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
256 span = left_subtract(span, covered);
259 //If span is not empty here, it_ is not in the set so it_ shall be added
260 icl::add(object, span);
265 template<class Type, class OperandT>
266 typename enable_if<is_concept_compatible<is_interval_set, Type, OperandT>, Type>::type&
267 flip(Type& object, const OperandT& operand)
269 typedef typename OperandT::const_iterator const_iterator;
274 const_iterator common_lwb, common_upb;
276 if(!Set::common_range(common_lwb, common_upb, operand, object))
277 return object += operand;
279 const_iterator it_ = operand.begin();
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_++);
294 //==============================================================================
296 //==============================================================================
298 typename enable_if<is_interval_set<Type>, Type>::type&
299 domain(Type& dom, const Type& object)
301 typedef typename Type::const_iterator const_iterator;
302 typedef typename Type::iterator iterator;
304 const_iterator it_ = object.begin();
305 iterator prior_ = dom.end();
307 while(it_ != object.end())
308 prior_ = icl::insert(dom, prior_, *it_++);
314 typename enable_if<is_interval_set<Type>, Type>::type&
315 between(Type& in_between, const Type& object)
317 typedef typename Type::const_iterator const_iterator;
318 typedef typename Type::iterator iterator;
320 const_iterator it_ = object.begin(), pred_;
321 iterator prior_ = in_between.end();
323 if(it_ != object.end())
326 while(it_ != object.end())
327 prior_ = icl::insert(in_between, prior_,
328 icl::between(*pred_++, *it_++));
334 //==============================================================================
336 //==============================================================================
337 template<class CharType, class CharTraits, class Type>
338 typename enable_if<is_interval_set<Type>,
339 std::basic_ostream<CharType, CharTraits> >::type&
340 operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
343 ICL_const_FORALL(typename Type, it_, object)
346 return stream << "}";
350 }} // namespace boost icl