1 // boost heap: heap node helper classes
2 //
3 // Copyright (C) 2010 Tim Blechmann
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 #ifndef BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
10 #define BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
11
12 #include <boost/assert.hpp>
13 #include <boost/static_assert.hpp>
14 #include <boost/concept/assert.hpp>
15 #include <boost/heap/heap_concepts.hpp>
16 #include <boost/type_traits/conditional.hpp>
17
18 #ifdef BOOST_HEAP_SANITYCHECKS
19 #define BOOST_HEAP_ASSERT BOOST_ASSERT
20 #else
21 #define BOOST_HEAP_ASSERT(expression)
22 #endif
23
24 namespace boost {
25 namespace heap {
26 namespace detail {
27
28 template <typename Heap1, typename Heap2>
value_equality(Heap1 const & lhs,Heap2 const & rhs,typename Heap1::value_type lval,typename Heap2::value_type rval)29 bool value_equality(Heap1 const & lhs, Heap2 const & rhs,
30 typename Heap1::value_type lval, typename Heap2::value_type rval)
31 {
32 typename Heap1::value_compare const & cmp = lhs.value_comp();
33 bool ret = !(cmp(lval, rval)) && !(cmp(rval, lval));
34
35 // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
36 BOOST_ASSERT((ret == (!(rhs.value_comp()(lval, rval)) && !(rhs.value_comp()(rval, lval)))));
37
38 return ret;
39 }
40
41 template <typename Heap1, typename Heap2>
value_compare(Heap1 const & lhs,Heap2 const & rhs,typename Heap1::value_type lval,typename Heap2::value_type rval)42 bool value_compare(Heap1 const & lhs, Heap2 const & rhs,
43 typename Heap1::value_type lval, typename Heap2::value_type rval)
44 {
45 typename Heap1::value_compare const & cmp = lhs.value_comp();
46 bool ret = cmp(lval, rval);
47
48 // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
49 BOOST_ASSERT((ret == rhs.value_comp()(lval, rval)));
50 return ret;
51 }
52
53 struct heap_equivalence_copy
54 {
55 template <typename Heap1, typename Heap2>
operator ()boost::heap::detail::heap_equivalence_copy56 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
57 {
58 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
59 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
60
61 // if this assertion is triggered, the value_compare types are incompatible
62 BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
63
64 if (Heap1::constant_time_size && Heap2::constant_time_size)
65 if (lhs.size() != rhs.size())
66 return false;
67
68 if (lhs.empty() && rhs.empty())
69 return true;
70
71 Heap1 lhs_copy(lhs);
72 Heap2 rhs_copy(rhs);
73
74 while (true) {
75 if (!value_equality(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
76 return false;
77
78 lhs_copy.pop();
79 rhs_copy.pop();
80
81 if (lhs_copy.empty() && rhs_copy.empty())
82 return true;
83
84 if (lhs_copy.empty())
85 return false;
86
87 if (rhs_copy.empty())
88 return false;
89 }
90 }
91 };
92
93
94 struct heap_equivalence_iteration
95 {
96 template <typename Heap1, typename Heap2>
operator ()boost::heap::detail::heap_equivalence_iteration97 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
98 {
99 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
100 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
101
102 // if this assertion is triggered, the value_compare types are incompatible
103 BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
104
105 if (Heap1::constant_time_size && Heap2::constant_time_size)
106 if (lhs.size() != rhs.size())
107 return false;
108
109 if (lhs.empty() && rhs.empty())
110 return true;
111
112 typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
113 typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
114 typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
115 typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
116 while (true) {
117 if (!value_equality(lhs, rhs, *it1, *it2))
118 return false;
119
120 ++it1;
121 ++it2;
122
123 if (it1 == it1_end && it2 == it2_end)
124 return true;
125
126 if (it1 == it1_end || it2 == it2_end)
127 return false;
128 }
129 }
130 };
131
132
133 template <typename Heap1,
134 typename Heap2
135 >
heap_equality(Heap1 const & lhs,Heap2 const & rhs)136 bool heap_equality(Heap1 const & lhs, Heap2 const & rhs)
137 {
138 const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
139
140 typedef typename boost::conditional<use_ordered_iterators,
141 heap_equivalence_iteration,
142 heap_equivalence_copy
143 >::type equivalence_check;
144
145 equivalence_check eq_check;
146 return eq_check(lhs, rhs);
147 }
148
149
150 struct heap_compare_iteration
151 {
152 template <typename Heap1,
153 typename Heap2
154 >
operator ()boost::heap::detail::heap_compare_iteration155 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
156 {
157 typename Heap1::size_type left_size = lhs.size();
158 typename Heap2::size_type right_size = rhs.size();
159 if (left_size < right_size)
160 return true;
161
162 if (left_size > right_size)
163 return false;
164
165 typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
166 typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
167 typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
168 typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
169 while (true) {
170 if (value_compare(lhs, rhs, *it1, *it2))
171 return true;
172
173 if (value_compare(lhs, rhs, *it2, *it1))
174 return false;
175
176 ++it1;
177 ++it2;
178
179 if (it1 == it1_end && it2 == it2_end)
180 return true;
181
182 if (it1 == it1_end || it2 == it2_end)
183 return false;
184 }
185 }
186 };
187
188 struct heap_compare_copy
189 {
190 template <typename Heap1,
191 typename Heap2
192 >
operator ()boost::heap::detail::heap_compare_copy193 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
194 {
195 typename Heap1::size_type left_size = lhs.size();
196 typename Heap2::size_type right_size = rhs.size();
197 if (left_size < right_size)
198 return true;
199
200 if (left_size > right_size)
201 return false;
202
203 Heap1 lhs_copy(lhs);
204 Heap2 rhs_copy(rhs);
205
206 while (true) {
207 if (value_compare(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
208 return true;
209
210 if (value_compare(lhs_copy, rhs_copy, rhs_copy.top(), lhs_copy.top()))
211 return false;
212
213 lhs_copy.pop();
214 rhs_copy.pop();
215
216 if (lhs_copy.empty() && rhs_copy.empty())
217 return false;
218 }
219 }
220 };
221
222 template <typename Heap1,
223 typename Heap2
224 >
heap_compare(Heap1 const & lhs,Heap2 const & rhs)225 bool heap_compare(Heap1 const & lhs, Heap2 const & rhs)
226 {
227 const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
228
229 typedef typename boost::conditional<use_ordered_iterators,
230 heap_compare_iteration,
231 heap_compare_copy
232 >::type compare_check;
233
234 compare_check check_object;
235 return check_object(lhs, rhs);
236 }
237
238
239 } /* namespace detail */
240 } /* namespace heap */
241 } /* namespace boost */
242
243
244 #undef BOOST_HEAP_ASSERT
245
246 #endif // BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
247