1 // boost heap: heap node helper classes
3 // Copyright (C) 2010 Tim Blechmann
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)
9 #ifndef BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
10 #define BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
12 #include <boost/assert.hpp>
13 #include <boost/static_assert.hpp>
14 #include <boost/concept/assert.hpp>
15 #include <boost/heap/heap_concepts.hpp>
17 #ifdef BOOST_HEAP_SANITYCHECKS
18 #define BOOST_HEAP_ASSERT BOOST_ASSERT
20 #define BOOST_HEAP_ASSERT(expression)
27 template <typename Heap1, typename Heap2>
28 bool value_equality(Heap1 const & lhs, Heap2 const & rhs,
29 typename Heap1::value_type lval, typename Heap2::value_type rval)
31 typename Heap1::value_compare const & cmp = lhs.value_comp();
32 bool ret = !(cmp(lval, rval)) && !(cmp(rval, lval));
34 // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
35 BOOST_ASSERT((ret == (!(rhs.value_comp()(lval, rval)) && !(rhs.value_comp()(rval, lval)))));
40 template <typename Heap1, typename Heap2>
41 bool value_compare(Heap1 const & lhs, Heap2 const & rhs,
42 typename Heap1::value_type lval, typename Heap2::value_type rval)
44 typename Heap1::value_compare const & cmp = lhs.value_comp();
45 bool ret = cmp(lval, rval);
47 // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
48 BOOST_ASSERT((ret == rhs.value_comp()(lval, rval)));
52 struct heap_equivalence_copy
54 template <typename Heap1, typename Heap2>
55 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
57 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
58 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
60 // if this assertion is triggered, the value_compare types are incompatible
61 BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
63 if (Heap1::constant_time_size && Heap2::constant_time_size)
64 if (lhs.size() != rhs.size())
67 if (lhs.empty() && rhs.empty())
74 if (!value_equality(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
80 if (lhs_copy.empty() && rhs_copy.empty())
93 struct heap_equivalence_iteration
95 template <typename Heap1, typename Heap2>
96 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
98 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
99 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
101 // if this assertion is triggered, the value_compare types are incompatible
102 BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
104 if (Heap1::constant_time_size && Heap2::constant_time_size)
105 if (lhs.size() != rhs.size())
108 if (lhs.empty() && rhs.empty())
111 typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
112 typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
113 typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
114 typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
116 if (!value_equality(lhs, rhs, *it1, *it2))
122 if (it1 == it1_end && it2 == it2_end)
125 if (it1 == it1_end || it2 == it2_end)
132 template <typename Heap1,
135 bool heap_equality(Heap1 const & lhs, Heap2 const & rhs)
137 const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
139 typedef typename boost::mpl::if_c<use_ordered_iterators,
140 heap_equivalence_iteration,
141 heap_equivalence_copy
142 >::type equivalence_check;
144 equivalence_check eq_check;
145 return eq_check(lhs, rhs);
149 struct heap_compare_iteration
151 template <typename Heap1,
154 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
156 typename Heap1::size_type left_size = lhs.size();
157 typename Heap2::size_type right_size = rhs.size();
158 if (left_size < right_size)
161 if (left_size > right_size)
164 typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
165 typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
166 typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
167 typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
169 if (value_compare(lhs, rhs, *it1, *it2))
172 if (value_compare(lhs, rhs, *it2, *it1))
178 if (it1 == it1_end && it2 == it2_end)
181 if (it1 == it1_end || it2 == it2_end)
187 struct heap_compare_copy
189 template <typename Heap1,
192 bool operator()(Heap1 const & lhs, Heap2 const & rhs)
194 typename Heap1::size_type left_size = lhs.size();
195 typename Heap2::size_type right_size = rhs.size();
196 if (left_size < right_size)
199 if (left_size > right_size)
206 if (value_compare(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
209 if (value_compare(lhs_copy, rhs_copy, rhs_copy.top(), lhs_copy.top()))
215 if (lhs_copy.empty() && rhs_copy.empty())
221 template <typename Heap1,
224 bool heap_compare(Heap1 const & lhs, Heap2 const & rhs)
226 const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
228 typedef typename boost::mpl::if_c<use_ordered_iterators,
229 heap_compare_iteration,
231 >::type compare_check;
233 compare_check check_object;
234 return check_object(lhs, rhs);
238 } /* namespace detail */
239 } /* namespace heap */
240 } /* namespace boost */
243 #undef BOOST_HEAP_ASSERT
245 #endif // BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP