1 /*-----------------------------------------------------------------------------+
2 Copyright (c) 2008-2009: 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_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
9 #define BOOST_ICL_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
10
11 #include <boost/icl/type_traits/is_map.hpp>
12 #include <boost/icl/detail/notate.hpp>
13 #include <boost/icl/detail/relation_state.hpp>
14 #include <boost/icl/type_traits/identity_element.hpp>
15 #include <boost/icl/type_traits/is_concept_equivalent.hpp>
16 #include <boost/icl/type_traits/is_interval_container.hpp>
17 #include <boost/icl/type_traits/is_set.hpp>
18 #include <boost/icl/concept/interval_set_value.hpp>
19
20 namespace boost{namespace icl
21 {
22
23 #ifdef BOOST_MSVC
24 #pragma warning(push)
25 #pragma warning(disable:4127) // conditional expression is constant
26 #endif
27
28 namespace Interval_Set
29 {
30
31 //------------------------------------------------------------------------------
32 template<class LeftT, class RightT>
33 struct settic_codomain_compare
34 {
applyboost::icl::Interval_Set::settic_codomain_compare35 static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
36 {
37 return inclusion_compare( icl::co_value<LeftT>(left_),
38 icl::co_value<RightT>(right_));
39 }
40 };
41
42 template<class LeftT, class RightT>
43 struct atomic_codomain_compare
44 {
applyboost::icl::Interval_Set::atomic_codomain_compare45 static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
46 {
47 if(icl::co_value<LeftT>(left_) == icl::co_value<RightT>(right_))
48 return inclusion::equal;
49 else
50 return inclusion::unrelated;
51 }
52 };
53
54 template<class LeftT, class RightT>
55 struct empty_codomain_compare
56 {
applyboost::icl::Interval_Set::empty_codomain_compare57 static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator)
58 {
59 return inclusion::equal;
60 }
61 };
62
63 template<class LeftT, class RightT>
64 struct map_codomain_compare
65 {
applyboost::icl::Interval_Set::map_codomain_compare66 static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
67 {
68 using namespace boost::mpl;
69 typedef typename LeftT::codomain_type LeftCodomainT;
70 typedef typename RightT::codomain_type RightCodomainT;
71
72 return
73 if_<
74 bool_<is_concept_equivalent<is_set,LeftCodomainT,
75 RightCodomainT>::value>,
76 settic_codomain_compare<LeftT,RightT>,
77 atomic_codomain_compare<LeftT,RightT>
78 >
79 ::type::apply(left_, right_);
80 }
81 };
82
83
84 //------------------------------------------------------------------------------
85 template<class LeftT, class RightT>
86 class subset_comparer
87 {
88 private:
89 subset_comparer& operator = (const subset_comparer&);
90 public:
91 typedef typename LeftT::const_iterator LeftIterT;
92 typedef typename RightT::const_iterator RightIterT;
93
94 BOOST_STATIC_CONSTANT(bool,
95 _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
96
97
subset_comparer(const LeftT & left,const RightT & right,const LeftIterT & left_end,const RightIterT & right_end)98 subset_comparer(const LeftT& left,
99 const RightT& right,
100 const LeftIterT& left_end,
101 const RightIterT& right_end)
102 : _left(left), _right(right),
103 _left_end(left_end), _right_end(right_end), _result(equal)
104 {}
105
106 enum{nextboth, nextleft, nextright, stop};
107
108 enum
109 {
110 unrelated = inclusion::unrelated,
111 subset = inclusion::subset, // left is_subset_of right
112 superset = inclusion::superset, // left is_superset_of right
113 equal = inclusion::equal // equal = subset | superset
114 };
115
result() const116 int result()const{ return _result; }
117
118
co_compare(LeftIterT & left,RightIterT & right)119 int co_compare(LeftIterT& left, RightIterT& right)
120 {
121 using namespace boost::mpl;
122
123 return
124 if_<
125 bool_<is_concept_equivalent<is_interval_map,LeftT,RightT>::value>,
126 map_codomain_compare<LeftT,RightT>,
127 empty_codomain_compare<LeftT,RightT>
128 >
129 ::type::apply(left,right);
130 }
131
restrict_result(int state)132 int restrict_result(int state) { return _result &= state; }
133
proceed(LeftIterT & left,RightIterT & right)134 int proceed(LeftIterT& left, RightIterT& right)
135 {
136 if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
137 { // left ..)
138 // right .....)
139 _prior_left = left;
140 ++left;
141 return nextleft;
142 }
143 else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
144 { // left .....)
145 // right ..)
146 _prior_right = right;
147 ++right;
148 return nextright;
149 }
150 else//key_value<LeftT>(left).upper_equal(key_value<RightT>(right))
151 { // left ..)
152 // right ..)
153 ++left;
154 ++right;
155 return nextboth;
156 }
157 }
158
next_both(LeftIterT & left,RightIterT & right)159 int next_both(LeftIterT& left, RightIterT& right)
160 {
161 if(left == _left_end && right == _right_end)
162 return stop;
163 else if(left == _left_end)
164 { // left: ....end left could be subset
165 // right:....[..
166 restrict_result(subset);
167 return stop;
168 }
169 else if(right == _right_end)
170 { // left: ....[.. left could be superset
171 // right:....end
172 restrict_result(superset);
173 return stop;
174 }
175 else if(exclusive_less(key_value<LeftT>(left), key_value<RightT>(right)))
176 { // left: [..) . . .[---) left could be superset
177 // right: [..).... if [---) exists
178 restrict_result(superset);
179 if(unrelated == _result)
180 return stop;
181 else
182 {
183 LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
184 if(joint_ == _left.end())
185 {
186 _result = unrelated;
187 return stop;
188 }
189 else
190 {
191 left = joint_;
192 return nextboth;
193 }
194 }
195 }
196 else if(exclusive_less(key_value<RightT>(right), key_value<LeftT>(left)))
197 { // left: [.. left could be subset
198 // right:....) . . .[---) if [---) exists
199 restrict_result(subset);
200 if(unrelated == _result)
201 return stop;
202 else
203 {
204 RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
205 if(joint_ == _right.end())
206 {
207 _result = unrelated;
208 return stop;
209 }
210 else
211 {
212 right = joint_;
213 return nextboth;
214 }
215 }
216 }
217
218 // left and right have intervals with nonempty intersection:
219 if(_compare_codomain)
220 if(unrelated == restrict_result(co_compare(left,right)))
221 return stop;
222
223 // examine left borders only. Right borders are checked in proceed
224 if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
225 { // left: ....[... left could be superset
226 // right:.... [..
227 if(unrelated == restrict_result(superset))
228 return stop;
229 }
230 else if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
231 { // left: .... [.. left can be subset
232 // right:....[...
233 if(unrelated == restrict_result(subset))
234 return stop;
235 }
236 //else key_value<LeftT>(right).lower_equal(key_value<RightT>(left))
237 // left: ....[.. both can be equal
238 // right:....[..
239 // nothing to do: proceed
240
241 return proceed(left, right);
242 }
243
next_left(LeftIterT & left,RightIterT & right)244 int next_left(LeftIterT& left, RightIterT& right)
245 {
246 if(left == _left_end)
247 { // left: ..)end left could be subset
248 // right:......)
249 restrict_result(subset);
250 return stop;
251 }
252 else if(!touches(key_value<LeftT>(_prior_left), key_value<LeftT>(left)))
253 { // left: ..) [..
254 // right:.........)
255 if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
256 { // ..) [.. left could be subset
257 // ..........)
258 if(unrelated == restrict_result(subset))
259 return stop;
260 }
261 //else ..) [...
262 // [..
263 if(_compare_codomain && intersects(key_value<LeftT>(left),key_value<RightT>(right)) )
264 if(unrelated == restrict_result(co_compare(left,right)))
265 return stop;
266 }
267 else
268 { // left: ..)[.. left could be subset
269 // right:.......)
270 if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
271 if(unrelated == restrict_result(co_compare(left,right)))
272 return stop;
273 }
274
275 return proceed(left, right);
276 }
277
278
next_right(LeftIterT & left,RightIterT & right)279 int next_right(LeftIterT& left, RightIterT& right)
280 {
281 if(right == _right_end)
282 { // left: ......) left could be superset
283 // right:..)end
284 restrict_result(superset);
285 return stop;
286 }
287 else if(!touches(key_value<RightT>(_prior_right), key_value<RightT>(right)))
288 { // left: .........)
289 // right:..) [..
290 if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
291 { // [....) left could be superset
292 // ..) [..
293 if(unrelated == restrict_result(superset))
294 return stop;
295 }
296 //else [....)
297 // ..) [..
298 if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
299 if(unrelated == restrict_result(co_compare(left,right)))
300 return stop;
301 }
302 else
303 {
304 if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
305 if(unrelated == restrict_result(co_compare(left,right)))
306 return stop;
307 }
308
309 return proceed(left, right);
310 }
311
312 private:
313 const LeftT& _left;
314 const RightT& _right;
315 LeftIterT _left_end;
316 RightIterT _right_end;
317 LeftIterT _prior_left;
318 RightIterT _prior_right;
319 int _result;
320 };
321
322
323
324
325
326 //------------------------------------------------------------------------------
327 // Subset/superset comparison on ranges of two interval container
328 //------------------------------------------------------------------------------
329 template<class LeftT, class RightT>
subset_compare(const LeftT & left,const RightT & right,typename LeftT::const_iterator left_begin,typename LeftT::const_iterator left_end,typename RightT::const_iterator right_begin,typename RightT::const_iterator right_end)330 int subset_compare
331 (
332 const LeftT& left, //sub
333 const RightT& right, //super
334 typename LeftT::const_iterator left_begin,
335 typename LeftT::const_iterator left_end,
336 typename RightT::const_iterator right_begin,
337 typename RightT::const_iterator right_end
338 )
339 {
340 typedef subset_comparer<LeftT,RightT> Step;
341 Step step(left, right, left_end, right_end);
342
343 typename LeftT::const_iterator left_ = left_begin;
344 typename RightT::const_iterator right_ = right_begin;
345
346 int state = Step::nextboth;
347 while(state != Step::stop)
348 {
349 switch(state){
350 case Step::nextboth: state = step.next_both(left_, right_); break;
351 case Step::nextleft: state = step.next_left(left_, right_); break;
352 case Step::nextright: state = step.next_right(left_, right_); break;
353 }
354 }
355 return step.result();
356 }
357
358
359 } // namespace Interval_Set
360
361 #ifdef BOOST_MSVC
362 #pragma warning(pop)
363 #endif
364
365 }} // namespace icl boost
366
367 #endif
368
369