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_ELEMENT_COMPARER_HPP_JOFA_090202
9 #define BOOST_ICL_ELEMENT_COMPARER_HPP_JOFA_090202
11 #include <boost/mpl/and.hpp>
12 #include <boost/icl/type_traits/is_map.hpp>
13 #include <boost/icl/detail/notate.hpp>
14 #include <boost/icl/type_traits/identity_element.hpp>
16 namespace boost{namespace icl
19 namespace Interval_Set
22 template<class LeftT, class RightT>
23 class element_comparer
26 typedef typename LeftT::const_iterator LeftIterT;
27 typedef typename RightT::const_iterator RightIterT;
29 BOOST_STATIC_CONSTANT(bool,
30 _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
32 element_comparer(const LeftT& left,
34 const LeftIterT& left_end,
35 const RightIterT& right_end)
36 : _left(left), _right(right),
37 _left_end(left_end), _right_end(right_end), _result(equal)
40 enum{nextboth, nextleft, nextright, stop};
44 less = comparison::less,
45 equal = comparison::equal,
46 greater = comparison::greater
49 int result()const{ return _result; }
51 bool covalues_are_equal(LeftIterT& left, RightIterT& right)
53 if(co_value<LeftT>(left) < co_value<RightT>(right))
55 if(co_value<RightT>(right) < co_value<LeftT>(left))
57 return _result == equal;
60 int proceed(LeftIterT& left, RightIterT& right)
62 if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
68 else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
82 int next_both(LeftIterT& left, RightIterT& right)
86 _result = (right == _right_end) ? equal : less;
91 if(right == _right_end)
97 // The starting intervals have to begin equally
98 if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
99 { // left: same A... = sameA...
100 // right:same B.. = sameB...
105 if(lower_less(key_value<LeftT>(right), key_value<RightT>(left)))
106 { // left: same B.. = sameB...
107 // right:same A... = sameA...
112 if(_compare_codomain && !covalues_are_equal(left, right))
115 return proceed(left, right);
118 int next_left(LeftIterT& left, RightIterT& right)
120 if(left == _left_end)
127 if(!key_value<LeftT>(_prior_left).touches(key_value<LeftT>(left)))
128 { // left: same B = sameB...
129 // right:sameA = sameA...
134 if(_compare_codomain && !covalues_are_equal(left, right))
137 return proceed(left, right);
140 int next_right(LeftIterT& left, RightIterT& right)
142 if(right == _right_end)
149 if(!key_value<RightT>(_prior_right).touches(key_value<RightT>(right)))
151 // left: sameA... = sameA...
152 // right:same B.. = sameB...
157 if(_compare_codomain && !covalues_are_equal(left, right))
160 return proceed(left, right);
165 const RightT& _right;
167 RightIterT _right_end;
168 LeftIterT _prior_left;
169 RightIterT _prior_right;
175 template<class LeftT, class RightT>
178 const LeftT& left, //sub
179 const RightT& right, //super
180 typename LeftT::const_iterator left_begin,
181 typename LeftT::const_iterator left_end,
182 typename RightT::const_iterator right_begin,
183 typename RightT::const_iterator right_end
186 typedef element_comparer<LeftT,RightT> Step;
187 Step step(left, right, left_end, right_end);
189 typename LeftT::const_iterator left_ = left_begin;
190 typename RightT::const_iterator right_ = right_begin;
192 int state = Step::nextboth;
193 while(state != Step::stop)
196 case Step::nextboth: state = step.next_both (left_, right_); break;
197 case Step::nextleft: state = step.next_left (left_, right_); break;
198 case Step::nextright: state = step.next_right(left_, right_); break;
201 return step.result();
205 } // namespace Interval_Set
207 }} // namespace icl boost