heap/detail/heap_comparison.hpp

0001 // boost heap: heap node helper classes
0002 //
0003 // Copyright (C) 2010 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
0010 #define BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
0011
0012 #include <boost/assert.hpp>
0013 #include <boost/static_assert.hpp>
0014 #include <boost/concept/assert.hpp>
0015 #include <boost/heap/heap_concepts.hpp>
0016 #include <boost/type_traits/conditional.hpp>
0017
0018 #ifdef BOOST_HEAP_SANITYCHECKS
0019 #define BOOST_HEAP_ASSERT BOOST_ASSERT
0020 #else
0021 #define BOOST_HEAP_ASSERT(expression)
0022 #endif
0023
0024 namespace boost  {
0025 namespace heap   {
0026 namespace detail {
0027
0028 template <typename Heap1, typename Heap2>
0029 bool value_equality(Heap1 const & lhs, Heap2 const & rhs,
0030                     typename Heap1::value_type lval, typename Heap2::value_type rval)
0031 {
0032     typename Heap1::value_compare const & cmp = lhs.value_comp();
0033     bool ret = !(cmp(lval, rval)) && !(cmp(rval, lval));
0034
0035     // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
0036     BOOST_ASSERT((ret == (!(rhs.value_comp()(lval, rval)) && !(rhs.value_comp()(rval, lval)))));
0037
0038     return ret;
0039 }
0040
0041 template <typename Heap1, typename Heap2>
0042 bool value_compare(Heap1 const & lhs, Heap2 const & rhs,
0043                     typename Heap1::value_type lval, typename Heap2::value_type rval)
0044 {
0045     typename Heap1::value_compare const & cmp = lhs.value_comp();
0046     bool ret = cmp(lval, rval);
0047
0048     // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
0049     BOOST_ASSERT((ret == rhs.value_comp()(lval, rval)));
0050     return ret;
0051 }
0052
0053 struct heap_equivalence_copy
0054 {
0055     template <typename Heap1, typename Heap2>
0056     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
0057     {
0058         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
0059         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
0060
0061         // if this assertion is triggered, the value_compare types are incompatible
0062         BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
0063
0064         if (Heap1::constant_time_size && Heap2::constant_time_size)
0065             if (lhs.size() != rhs.size())
0066                 return false;
0067
0068         if (lhs.empty() && rhs.empty())
0069             return true;
0070
0071         Heap1 lhs_copy(lhs);
0072         Heap2 rhs_copy(rhs);
0073
0074         while (true) {
0075             if (!value_equality(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
0076                 return false;
0077
0078             lhs_copy.pop();
0079             rhs_copy.pop();
0080
0081             if (lhs_copy.empty() && rhs_copy.empty())
0082                 return true;
0083
0084             if (lhs_copy.empty())
0085                 return false;
0086
0087             if (rhs_copy.empty())
0088                 return false;
0089         }
0090     }
0091 };
0092
0093
0094 struct heap_equivalence_iteration
0095 {
0096     template <typename Heap1, typename Heap2>
0097     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
0098     {
0099         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
0100         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
0101
0102         // if this assertion is triggered, the value_compare types are incompatible
0103         BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
0104
0105         if (Heap1::constant_time_size && Heap2::constant_time_size)
0106             if (lhs.size() != rhs.size())
0107                 return false;
0108
0109         if (lhs.empty() && rhs.empty())
0110             return true;
0111
0112         typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
0113         typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
0114         typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
0115         typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
0116         while (true) {
0117             if (!value_equality(lhs, rhs, *it1, *it2))
0118                 return false;
0119
0120             ++it1;
0121             ++it2;
0122
0123             if (it1 == it1_end && it2 == it2_end)
0124                 return true;
0125
0126             if (it1 == it1_end || it2 == it2_end)
0127                 return false;
0128         }
0129     }
0130 };
0131
0132
0133 template <typename Heap1,
0134           typename Heap2
0135          >
0136 bool heap_equality(Heap1 const & lhs, Heap2 const & rhs)
0137 {
0138     const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
0139
0140     typedef typename boost::conditional<use_ordered_iterators,
0141                                       heap_equivalence_iteration,
0142                                       heap_equivalence_copy
0143                                      >::type equivalence_check;
0144
0145     equivalence_check eq_check;
0146     return eq_check(lhs, rhs);
0147 }
0148
0149
0150 struct heap_compare_iteration
0151 {
0152     template <typename Heap1,
0153               typename Heap2
0154              >
0155     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
0156     {
0157         typename Heap1::size_type left_size = lhs.size();
0158         typename Heap2::size_type right_size = rhs.size();
0159         if (left_size < right_size)
0160             return true;
0161
0162         if (left_size > right_size)
0163             return false;
0164
0165         typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
0166         typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
0167         typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
0168         typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
0169         while (true) {
0170             if (value_compare(lhs, rhs, *it1, *it2))
0171                 return true;
0172
0173             if (value_compare(lhs, rhs, *it2, *it1))
0174                 return false;
0175
0176             ++it1;
0177             ++it2;
0178
0179             if (it1 == it1_end && it2 == it2_end)
0180                 return true;
0181
0182             if (it1 == it1_end || it2 == it2_end)
0183                 return false;
0184         }
0185     }
0186 };
0187
0188 struct heap_compare_copy
0189 {
0190     template <typename Heap1,
0191               typename Heap2
0192              >
0193     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
0194     {
0195         typename Heap1::size_type left_size = lhs.size();
0196         typename Heap2::size_type right_size = rhs.size();
0197         if (left_size < right_size)
0198             return true;
0199
0200         if (left_size > right_size)
0201             return false;
0202
0203         Heap1 lhs_copy(lhs);
0204         Heap2 rhs_copy(rhs);
0205
0206         while (true) {
0207             if (value_compare(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
0208                 return true;
0209
0210             if (value_compare(lhs_copy, rhs_copy, rhs_copy.top(), lhs_copy.top()))
0211                 return false;
0212
0213             lhs_copy.pop();
0214             rhs_copy.pop();
0215
0216             if (lhs_copy.empty() && rhs_copy.empty())
0217                 return false;
0218         }
0219     }
0220 };
0221
0222 template <typename Heap1,
0223           typename Heap2
0224          >
0225 bool heap_compare(Heap1 const & lhs, Heap2 const & rhs)
0226 {
0227     const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
0228
0229     typedef typename boost::conditional<use_ordered_iterators,
0230                                       heap_compare_iteration,
0231                                       heap_compare_copy
0232                                      >::type compare_check;
0233
0234     compare_check check_object;
0235     return check_object(lhs, rhs);
0236 }
0237
0238
0239 } /* namespace detail */
0240 } /* namespace heap */
0241 } /* namespace boost */
0242
0243
0244 #undef BOOST_HEAP_ASSERT
0245
0246 #endif // BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP