zhipuzi_pos_windows/include/boost/heap/detail/heap_comparison.hpp

// boost heap: heap node helper classes
//
// Copyright (C) 2010 Tim Blechmann
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
#define BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP

#include <boost/assert.hpp>
#include <boost/concept/assert.hpp>
#include <boost/heap/heap_concepts.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits/conditional.hpp>

#ifdef BOOST_HEAP_SANITYCHECKS
#    define BOOST_HEAP_ASSERT BOOST_ASSERT
#else
#    define BOOST_HEAP_ASSERT( expression ) static_assert( true, "force semicolon" )
#endif

namespace boost { namespace heap { namespace detail {

template < typename Heap1, typename Heap2 >
bool value_equality( Heap1 const& lhs, Heap2 const& rhs, typename Heap1::value_type lval, typename Heap2::value_type rval )
{
    (void)rhs;
    typename Heap1::value_compare const& cmp = lhs.value_comp();
    bool                                 ret = !( cmp( lval, rval ) ) && !( cmp( rval, lval ) );

    // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
    BOOST_ASSERT( ( ret == ( !( rhs.value_comp()( lval, rval ) ) && !( rhs.value_comp()( rval, lval ) ) ) ) );

    return ret;
}

template < typename Heap1, typename Heap2 >
bool value_compare( Heap1 const& lhs, Heap2 const& rhs, typename Heap1::value_type lval, typename Heap2::value_type rval )
{
    (void)rhs;
    typename Heap1::value_compare const& cmp = lhs.value_comp();
    bool                                 ret = cmp( lval, rval );

    // if this assertion is triggered, the value_compare objects of lhs and rhs return different values
    BOOST_ASSERT( ( ret == rhs.value_comp()( lval, rval ) ) );
    return ret;
}

struct heap_equivalence_copy
{
    template < typename Heap1, typename Heap2 >
    bool operator()( Heap1 const& lhs, Heap2 const& rhs )
    {
        BOOST_CONCEPT_ASSERT( (boost::heap::PriorityQueue< Heap1 >));
        BOOST_CONCEPT_ASSERT( (boost::heap::PriorityQueue< Heap2 >));

        // if this assertion is triggered, the value_compare types are incompatible
        BOOST_STATIC_ASSERT( ( std::is_same< typename Heap1::value_compare, typename Heap2::value_compare >::value ) );

        if ( Heap1::constant_time_size && Heap2::constant_time_size )
            if ( lhs.size() != rhs.size() )
                return false;

        if ( lhs.empty() && rhs.empty() )
            return true;

        Heap1 lhs_copy( lhs );
        Heap2 rhs_copy( rhs );

        while ( true ) {
            if ( !value_equality( lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top() ) )
                return false;

            lhs_copy.pop();
            rhs_copy.pop();

            if ( lhs_copy.empty() && rhs_copy.empty() )
                return true;

            if ( lhs_copy.empty() )
                return false;

            if ( rhs_copy.empty() )
                return false;
        }
    }
};


struct heap_equivalence_iteration
{
    template < typename Heap1, typename Heap2 >
    bool operator()( Heap1 const& lhs, Heap2 const& rhs )
    {
        BOOST_CONCEPT_ASSERT( (boost::heap::PriorityQueue< Heap1 >));
        BOOST_CONCEPT_ASSERT( (boost::heap::PriorityQueue< Heap2 >));

        // if this assertion is triggered, the value_compare types are incompatible
        BOOST_STATIC_ASSERT( ( std::is_same< typename Heap1::value_compare, typename Heap2::value_compare >::value ) );

        if ( Heap1::constant_time_size && Heap2::constant_time_size )
            if ( lhs.size() != rhs.size() )
                return false;

        if ( lhs.empty() && rhs.empty() )
            return true;

        typename Heap1::ordered_iterator it1     = lhs.ordered_begin();
        typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
        typename Heap1::ordered_iterator it2     = rhs.ordered_begin();
        typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
        while ( true ) {
            if ( !value_equality( lhs, rhs, *it1, *it2 ) )
                return false;

            ++it1;
            ++it2;

            if ( it1 == it1_end && it2 == it2_end )
                return true;

            if ( it1 == it1_end || it2 == it2_end )
                return false;
        }
    }
};


template < typename Heap1, typename Heap2 >
bool heap_equality( Heap1 const& lhs, Heap2 const& rhs )
{
    const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;

    typedef typename std::conditional< use_ordered_iterators, heap_equivalence_iteration, heap_equivalence_copy >::type
        equivalence_check;

    equivalence_check eq_check;
    return eq_check( lhs, rhs );
}


struct heap_compare_iteration
{
    template < typename Heap1, typename Heap2 >
    bool operator()( Heap1 const& lhs, Heap2 const& rhs )
    {
        typename Heap1::size_type left_size  = lhs.size();
        typename Heap2::size_type right_size = rhs.size();
        if ( left_size < right_size )
            return true;

        if ( left_size > right_size )
            return false;

        typename Heap1::ordered_iterator it1     = lhs.ordered_begin();
        typename Heap1::ordered_iterator it1_end = lhs.ordered_end();
        typename Heap1::ordered_iterator it2     = rhs.ordered_begin();
        typename Heap1::ordered_iterator it2_end = rhs.ordered_end();
        while ( true ) {
            if ( value_compare( lhs, rhs, *it1, *it2 ) )
                return true;

            if ( value_compare( lhs, rhs, *it2, *it1 ) )
                return false;

            ++it1;
            ++it2;

            if ( it1 == it1_end && it2 == it2_end )
                return true;

            if ( it1 == it1_end || it2 == it2_end )
                return false;
        }
    }
};

struct heap_compare_copy
{
    template < typename Heap1, typename Heap2 >
    bool operator()( Heap1 const& lhs, Heap2 const& rhs )
    {
        typename Heap1::size_type left_size  = lhs.size();
        typename Heap2::size_type right_size = rhs.size();
        if ( left_size < right_size )
            return true;

        if ( left_size > right_size )
            return false;

        Heap1 lhs_copy( lhs );
        Heap2 rhs_copy( rhs );

        while ( true ) {
            if ( value_compare( lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top() ) )
                return true;

            if ( value_compare( lhs_copy, rhs_copy, rhs_copy.top(), lhs_copy.top() ) )
                return false;

            lhs_copy.pop();
            rhs_copy.pop();

            if ( lhs_copy.empty() && rhs_copy.empty() )
                return false;
        }
    }
};

template < typename Heap1, typename Heap2 >
bool heap_compare( Heap1 const& lhs, Heap2 const& rhs )
{
    const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;

    typedef
        typename std::conditional< use_ordered_iterators, heap_compare_iteration, heap_compare_copy >::type compare_check;

    compare_check check_object;
    return check_object( lhs, rhs );
}


}}} // namespace boost::heap::detail


#undef BOOST_HEAP_ASSERT

#endif // BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP