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
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>
20 namespace boost{namespace icl
25 #pragma warning(disable:4127) // conditional expression is constant
28 namespace Interval_Set
31 //------------------------------------------------------------------------------
32 template<class LeftT, class RightT>
33 struct settic_codomain_compare
35 static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
37 return inclusion_compare( icl::co_value<LeftT>(left_),
38 icl::co_value<RightT>(right_));
42 template<class LeftT, class RightT>
43 struct atomic_codomain_compare
45 static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
47 if(icl::co_value<LeftT>(left_) == icl::co_value<RightT>(right_))
48 return inclusion::equal;
50 return inclusion::unrelated;
54 template<class LeftT, class RightT>
55 struct empty_codomain_compare
57 static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator)
59 return inclusion::equal;
63 template<class LeftT, class RightT>
64 struct map_codomain_compare
66 static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
68 using namespace boost::mpl;
69 typedef typename LeftT::codomain_type LeftCodomainT;
70 typedef typename RightT::codomain_type RightCodomainT;
74 bool_<is_concept_equivalent<is_set,LeftCodomainT,
75 RightCodomainT>::value>,
76 settic_codomain_compare<LeftT,RightT>,
77 atomic_codomain_compare<LeftT,RightT>
79 ::type::apply(left_, right_);
84 //------------------------------------------------------------------------------
85 template<class LeftT, class RightT>
89 subset_comparer& operator = (const subset_comparer&);
91 typedef typename LeftT::const_iterator LeftIterT;
92 typedef typename RightT::const_iterator RightIterT;
94 BOOST_STATIC_CONSTANT(bool,
95 _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
98 subset_comparer(const LeftT& left,
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)
106 enum{nextboth, nextleft, nextright, stop};
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
116 int result()const{ return _result; }
119 int co_compare(LeftIterT& left, RightIterT& right)
121 using namespace boost::mpl;
125 bool_<is_concept_equivalent<is_interval_map,LeftT,RightT>::value>,
126 map_codomain_compare<LeftT,RightT>,
127 empty_codomain_compare<LeftT,RightT>
129 ::type::apply(left,right);
132 int restrict_result(int state) { return _result &= state; }
134 int proceed(LeftIterT& left, RightIterT& right)
136 if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
143 else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
146 _prior_right = right;
150 else//key_value<LeftT>(left).upper_equal(key_value<RightT>(right))
159 int next_both(LeftIterT& left, RightIterT& right)
161 if(left == _left_end && right == _right_end)
163 else if(left == _left_end)
164 { // left: ....end left could be subset
166 restrict_result(subset);
169 else if(right == _right_end)
170 { // left: ....[.. left could be superset
172 restrict_result(superset);
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)
183 LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
184 if(joint_ == _left.end())
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)
204 RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
205 if(joint_ == _right.end())
218 // left and right have intervals with nonempty intersection:
219 if(_compare_codomain)
220 if(unrelated == restrict_result(co_compare(left,right)))
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
227 if(unrelated == restrict_result(superset))
230 else if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
231 { // left: .... [.. left can be subset
233 if(unrelated == restrict_result(subset))
236 //else key_value<LeftT>(right).lower_equal(key_value<RightT>(left))
237 // left: ....[.. both can be equal
239 // nothing to do: proceed
241 return proceed(left, right);
244 int next_left(LeftIterT& left, RightIterT& right)
246 if(left == _left_end)
247 { // left: ..)end left could be subset
249 restrict_result(subset);
252 else if(!touches(key_value<LeftT>(_prior_left), key_value<LeftT>(left)))
255 if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
256 { // ..) [.. left could be subset
258 if(unrelated == restrict_result(subset))
263 if(_compare_codomain && intersects(key_value<LeftT>(left),key_value<RightT>(right)) )
264 if(unrelated == restrict_result(co_compare(left,right)))
268 { // left: ..)[.. left could be subset
270 if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
271 if(unrelated == restrict_result(co_compare(left,right)))
275 return proceed(left, right);
279 int next_right(LeftIterT& left, RightIterT& right)
281 if(right == _right_end)
282 { // left: ......) left could be superset
284 restrict_result(superset);
287 else if(!touches(key_value<RightT>(_prior_right), key_value<RightT>(right)))
288 { // left: .........)
290 if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
291 { // [....) left could be superset
293 if(unrelated == restrict_result(superset))
298 if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
299 if(unrelated == restrict_result(co_compare(left,right)))
304 if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
305 if(unrelated == restrict_result(co_compare(left,right)))
309 return proceed(left, right);
314 const RightT& _right;
316 RightIterT _right_end;
317 LeftIterT _prior_left;
318 RightIterT _prior_right;
326 //------------------------------------------------------------------------------
327 // Subset/superset comparison on ranges of two interval container
328 //------------------------------------------------------------------------------
329 template<class LeftT, class RightT>
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
340 typedef subset_comparer<LeftT,RightT> Step;
341 Step step(left, right, left_end, right_end);
343 typename LeftT::const_iterator left_ = left_begin;
344 typename RightT::const_iterator right_ = right_begin;
346 int state = Step::nextboth;
347 while(state != Step::stop)
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;
355 return step.result();
359 } // namespace Interval_Set
365 }} // namespace icl boost