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
10
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>
15
16 namespace boost{namespace icl
17 {
18
19 namespace Interval_Set
20 {
21
22 template<class LeftT, class RightT>
23 class element_comparer
24 {
25 public:
26 typedef typename LeftT::const_iterator LeftIterT;
27 typedef typename RightT::const_iterator RightIterT;
28
29 BOOST_STATIC_CONSTANT(bool,
30 _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
31
element_comparer(const LeftT & left,const RightT & right,const LeftIterT & left_end,const RightIterT & right_end)32 element_comparer(const LeftT& left,
33 const RightT& right,
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)
38 {}
39
40 enum{nextboth, nextleft, nextright, stop};
41
42 enum
43 {
44 less = comparison::less,
45 equal = comparison::equal,
46 greater = comparison::greater
47 };
48
result() const49 int result()const{ return _result; }
50
covalues_are_equal(LeftIterT & left,RightIterT & right)51 bool covalues_are_equal(LeftIterT& left, RightIterT& right)
52 {
53 if(co_value<LeftT>(left) < co_value<RightT>(right))
54 _result = less;
55 if(co_value<RightT>(right) < co_value<LeftT>(left))
56 _result = greater;
57 return _result == equal;
58 }
59
proceed(LeftIterT & left,RightIterT & right)60 int proceed(LeftIterT& left, RightIterT& right)
61 {
62 if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
63 {
64 _prior_left = left;
65 ++left;
66 return nextleft;
67 }
68 else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
69 {
70 _prior_right = right;
71 ++right;
72 return nextright;
73 }
74 else
75 {
76 ++left;
77 ++right;
78 return nextboth;
79 }
80 }
81
next_both(LeftIterT & left,RightIterT & right)82 int next_both(LeftIterT& left, RightIterT& right)
83 {
84 if(left == _left_end)
85 {
86 _result = (right == _right_end) ? equal : less;
87 return stop;
88 }
89
90 // left != _left_end
91 if(right == _right_end)
92 {
93 _result = greater;
94 return stop;
95 }
96
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...
101 _result = less;
102 return stop;
103 }
104
105 if(lower_less(key_value<LeftT>(right), key_value<RightT>(left)))
106 { // left: same B.. = sameB...
107 // right:same A... = sameA...
108 _result = greater;
109 return stop;
110 }
111
112 if(_compare_codomain && !covalues_are_equal(left, right))
113 return stop;
114
115 return proceed(left, right);
116 }
117
next_left(LeftIterT & left,RightIterT & right)118 int next_left(LeftIterT& left, RightIterT& right)
119 {
120 if(left == _left_end)
121 { // left: same
122 // right:sameA...
123 _result = less;
124 return stop;
125 }
126
127 if(!key_value<LeftT>(_prior_left).touches(key_value<LeftT>(left)))
128 { // left: same B = sameB...
129 // right:sameA = sameA...
130 _result = greater;
131 return stop;
132 }
133
134 if(_compare_codomain && !covalues_are_equal(left, right))
135 return stop;
136
137 return proceed(left, right);
138 }
139
next_right(LeftIterT & left,RightIterT & right)140 int next_right(LeftIterT& left, RightIterT& right)
141 {
142 if(right == _right_end)
143 { // left: sameA...
144 // right:same
145 _result = greater;
146 return stop;
147 }
148
149 if(!key_value<RightT>(_prior_right).touches(key_value<RightT>(right)))
150 {
151 // left: sameA... = sameA...
152 // right:same B.. = sameB...
153 _result = less;
154 return stop;
155 }
156
157 if(_compare_codomain && !covalues_are_equal(left, right))
158 return stop;
159
160 return proceed(left, right);
161 }
162
163 private:
164 const LeftT& _left;
165 const RightT& _right;
166 LeftIterT _left_end;
167 RightIterT _right_end;
168 LeftIterT _prior_left;
169 RightIterT _prior_right;
170 int _result;
171 };
172
173
174
175 template<class LeftT, class RightT>
element_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)176 int element_compare
177 (
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
184 )
185 {
186 typedef element_comparer<LeftT,RightT> Step;
187 Step step(left, right, left_end, right_end);
188
189 typename LeftT::const_iterator left_ = left_begin;
190 typename RightT::const_iterator right_ = right_begin;
191
192 int state = Step::nextboth;
193 while(state != Step::stop)
194 {
195 switch(state){
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;
199 }
200 }
201 return step.result();
202 }
203
204
205 } // namespace Interval_Set
206
207 }} // namespace icl boost
208
209 #endif
210
211