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
24namespace boost {
25namespace heap {
26namespace detail {
27
28template <typename Heap1, typename Heap2>
29bool 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
41template <typename Heap1, typename Heap2>
42bool 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
53struct heap_equivalence_copy
54{
55 template <typename Heap1, typename Heap2>
56 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
94struct heap_equivalence_iteration
95{
96 template <typename Heap1, typename Heap2>
97 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
133template <typename Heap1,
134 typename Heap2
135 >
136bool 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
150struct heap_compare_iteration
151{
152 template <typename Heap1,
153 typename Heap2
154 >
155 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
188struct heap_compare_copy
189{
190 template <typename Heap1,
191 typename Heap2
192 >
193 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
222template <typename Heap1,
223 typename Heap2
224 >
225bool 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

source code of boost/libs/heap/include/boost/heap/detail/heap_comparison.hpp