Chris@16: // boost heap: heap node helper classes
Chris@16: //
Chris@16: // Copyright (C) 2010 Tim Blechmann
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
Chris@16: #define BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: #include <boost/heap/heap_concepts.hpp>
Chris@16: 
Chris@16: #ifdef BOOST_HEAP_SANITYCHECKS
Chris@16: #define BOOST_HEAP_ASSERT BOOST_ASSERT
Chris@16: #else
Chris@16: #define BOOST_HEAP_ASSERT(expression)
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost  {
Chris@16: namespace heap   {
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <typename Heap1, typename Heap2>
Chris@16: bool value_equality(Heap1 const & lhs, Heap2 const & rhs,
Chris@16:                     typename Heap1::value_type lval, typename Heap2::value_type rval)
Chris@16: {
Chris@16:     typename Heap1::value_compare const & cmp = lhs.value_comp();
Chris@16:     bool ret = !(cmp(lval, rval)) && !(cmp(rval, lval));
Chris@16: 
Chris@16:     // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
Chris@16:     BOOST_ASSERT((ret == (!(rhs.value_comp()(lval, rval)) && !(rhs.value_comp()(rval, lval)))));
Chris@16: 
Chris@16:     return ret;
Chris@16: }
Chris@16: 
Chris@16: template <typename Heap1, typename Heap2>
Chris@16: bool value_compare(Heap1 const & lhs, Heap2 const & rhs,
Chris@16:                     typename Heap1::value_type lval, typename Heap2::value_type rval)
Chris@16: {
Chris@16:     typename Heap1::value_compare const & cmp = lhs.value_comp();
Chris@16:     bool ret = cmp(lval, rval);
Chris@16: 
Chris@16:     // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
Chris@16:     BOOST_ASSERT((ret == rhs.value_comp()(lval, rval)));
Chris@16:     return ret;
Chris@16: }
Chris@16: 
Chris@16: struct heap_equivalence_copy
Chris@16: {
Chris@16:     template <typename Heap1, typename Heap2>
Chris@16:     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
Chris@16:         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
Chris@16: 
Chris@16:         // if this assertion is triggered, the value_compare types are incompatible
Chris@16:         BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
Chris@16: 
Chris@16:         if (Heap1::constant_time_size && Heap2::constant_time_size)
Chris@16:             if (lhs.size() != rhs.size())
Chris@16:                 return false;
Chris@16: 
Chris@16:         if (lhs.empty() && rhs.empty())
Chris@16:             return true;
Chris@16: 
Chris@16:         Heap1 lhs_copy(lhs);
Chris@16:         Heap2 rhs_copy(rhs);
Chris@16: 
Chris@16:         while (true) {
Chris@16:             if (!value_equality(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
Chris@16:                 return false;
Chris@16: 
Chris@16:             lhs_copy.pop();
Chris@16:             rhs_copy.pop();
Chris@16: 
Chris@16:             if (lhs_copy.empty() && rhs_copy.empty())
Chris@16:                 return true;
Chris@16: 
Chris@16:             if (lhs_copy.empty())
Chris@16:                 return false;
Chris@16: 
Chris@16:             if (rhs_copy.empty())
Chris@16:                 return false;
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: struct heap_equivalence_iteration
Chris@16: {
Chris@16:     template <typename Heap1, typename Heap2>
Chris@16:     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
Chris@16:         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
Chris@16: 
Chris@16:         // if this assertion is triggered, the value_compare types are incompatible
Chris@16:         BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
Chris@16: 
Chris@16:         if (Heap1::constant_time_size && Heap2::constant_time_size)
Chris@16:             if (lhs.size() != rhs.size())
Chris@16:                 return false;
Chris@16: 
Chris@16:         if (lhs.empty() && rhs.empty())
Chris@16:             return true;
Chris@16: 
Chris@16:         typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
Chris@16:         typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
Chris@16:         typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
Chris@16:         typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
Chris@16:         while (true) {
Chris@16:             if (!value_equality(lhs, rhs, *it1, *it2))
Chris@16:                 return false;
Chris@16: 
Chris@16:             ++it1;
Chris@16:             ++it2;
Chris@16: 
Chris@16:             if (it1 == it1_end && it2 == it2_end)
Chris@16:                 return true;
Chris@16: 
Chris@16:             if (it1 == it1_end || it2 == it2_end)
Chris@16:                 return false;
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename Heap1,
Chris@16:           typename Heap2
Chris@16:          >
Chris@16: bool heap_equality(Heap1 const & lhs, Heap2 const & rhs)
Chris@16: {
Chris@16:     const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
Chris@16: 
Chris@16:     typedef typename boost::mpl::if_c<use_ordered_iterators,
Chris@16:                                       heap_equivalence_iteration,
Chris@16:                                       heap_equivalence_copy
Chris@16:                                      >::type equivalence_check;
Chris@16: 
Chris@16:     equivalence_check eq_check;
Chris@16:     return eq_check(lhs, rhs);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: struct heap_compare_iteration
Chris@16: {
Chris@16:     template <typename Heap1,
Chris@16:               typename Heap2
Chris@16:              >
Chris@16:     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
Chris@16:     {
Chris@16:         typename Heap1::size_type left_size = lhs.size();
Chris@16:         typename Heap2::size_type right_size = rhs.size();
Chris@16:         if (left_size < right_size)
Chris@16:             return true;
Chris@16: 
Chris@16:         if (left_size > right_size)
Chris@16:             return false;
Chris@16: 
Chris@16:         typename Heap1::ordered_iterator it1 = lhs.ordered_begin();
Chris@16:         typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
Chris@16:         typename Heap1::ordered_iterator it2 = rhs.ordered_begin();
Chris@16:         typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
Chris@16:         while (true) {
Chris@16:             if (value_compare(lhs, rhs, *it1, *it2))
Chris@16:                 return true;
Chris@16: 
Chris@16:             if (value_compare(lhs, rhs, *it2, *it1))
Chris@16:                 return false;
Chris@16: 
Chris@16:             ++it1;
Chris@16:             ++it2;
Chris@16: 
Chris@16:             if (it1 == it1_end && it2 == it2_end)
Chris@16:                 return true;
Chris@16: 
Chris@16:             if (it1 == it1_end || it2 == it2_end)
Chris@16:                 return false;
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: struct heap_compare_copy
Chris@16: {
Chris@16:     template <typename Heap1,
Chris@16:               typename Heap2
Chris@16:              >
Chris@16:     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
Chris@16:     {
Chris@16:         typename Heap1::size_type left_size = lhs.size();
Chris@16:         typename Heap2::size_type right_size = rhs.size();
Chris@16:         if (left_size < right_size)
Chris@16:             return true;
Chris@16: 
Chris@16:         if (left_size > right_size)
Chris@16:             return false;
Chris@16: 
Chris@16:         Heap1 lhs_copy(lhs);
Chris@16:         Heap2 rhs_copy(rhs);
Chris@16: 
Chris@16:         while (true) {
Chris@16:             if (value_compare(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
Chris@16:                 return true;
Chris@16: 
Chris@16:             if (value_compare(lhs_copy, rhs_copy, rhs_copy.top(), lhs_copy.top()))
Chris@16:                 return false;
Chris@16: 
Chris@16:             lhs_copy.pop();
Chris@16:             rhs_copy.pop();
Chris@16: 
Chris@16:             if (lhs_copy.empty() && rhs_copy.empty())
Chris@16:                 return false;
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Heap1,
Chris@16:           typename Heap2
Chris@16:          >
Chris@16: bool heap_compare(Heap1 const & lhs, Heap2 const & rhs)
Chris@16: {
Chris@16:     const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
Chris@16: 
Chris@16:     typedef typename boost::mpl::if_c<use_ordered_iterators,
Chris@16:                                       heap_compare_iteration,
Chris@16:                                       heap_compare_copy
Chris@16:                                      >::type compare_check;
Chris@16: 
Chris@16:     compare_check check_object;
Chris@16:     return check_object(lhs, rhs);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: 
Chris@16: #undef BOOST_HEAP_ASSERT
Chris@16: 
Chris@16: #endif // BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP