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