ceph/src/boost/libs/heap/include/boost/heap/detail/heap_comparison.hpp

   1 // boost heap: heap node helper classes
   2 //
   3 // Copyright (C) 2010 Tim Blechmann
   4 //
   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)
   8
   9 #ifndef BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
  10 #define BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP
  11
  12 #include <boost/assert.hpp>
  13 #include <boost/static_assert.hpp>
  14 #include <boost/concept/assert.hpp>
  15 #include <boost/heap/heap_concepts.hpp>
  16
  17 #ifdef BOOST_HEAP_SANITYCHECKS
  18 #define BOOST_HEAP_ASSERT BOOST_ASSERT
  19 #else
  20 #define BOOST_HEAP_ASSERT(expression)
  21 #endif
  22
  23 namespace boost  {
  24 namespace heap   {
  25 namespace detail {
  26
  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)
  30 {
  31     typename Heap1::value_compare const & cmp = lhs.value_comp();
  32     bool ret = !(cmp(lval, rval)) && !(cmp(rval, lval));
  33
  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)))));
  36
  37     return ret;
  38 }
  39
  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)
  43 {
  44     typename Heap1::value_compare const & cmp = lhs.value_comp();
  45     bool ret = cmp(lval, rval);
  46
  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)));
  49     return ret;
  50 }
  51
  52 struct heap_equivalence_copy
  53 {
  54     template <typename Heap1, typename Heap2>
  55     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
  56     {
  57         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
  58         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
  59
  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));
  62
  63         if (Heap1::constant_time_size && Heap2::constant_time_size)
  64             if (lhs.size() != rhs.size())
  65                 return false;
  66
  67         if (lhs.empty() && rhs.empty())
  68             return true;
  69
  70         Heap1 lhs_copy(lhs);
  71         Heap2 rhs_copy(rhs);
  72
  73         while (true) {
  74             if (!value_equality(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
  75                 return false;
  76
  77             lhs_copy.pop();
  78             rhs_copy.pop();
  79
  80             if (lhs_copy.empty() && rhs_copy.empty())
  81                 return true;
  82
  83             if (lhs_copy.empty())
  84                 return false;
  85
  86             if (rhs_copy.empty())
  87                 return false;
  88         }
  89     }
  90 };
  91
  92
  93 struct heap_equivalence_iteration
  94 {
  95     template <typename Heap1, typename Heap2>
  96     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
  97     {
  98         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
  99         BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
 100
 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));
 103
 104         if (Heap1::constant_time_size && Heap2::constant_time_size)
 105             if (lhs.size() != rhs.size())
 106                 return false;
 107
 108         if (lhs.empty() && rhs.empty())
 109             return true;
 110
 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();
 115         while (true) {
 116             if (!value_equality(lhs, rhs, *it1, *it2))
 117                 return false;
 118
 119             ++it1;
 120             ++it2;
 121
 122             if (it1 == it1_end && it2 == it2_end)
 123                 return true;
 124
 125             if (it1 == it1_end || it2 == it2_end)
 126                 return false;
 127         }
 128     }
 129 };
 130
 131
 132 template <typename Heap1,
 133           typename Heap2
 134          >
 135 bool heap_equality(Heap1 const & lhs, Heap2 const & rhs)
 136 {
 137     const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
 138
 139     typedef typename boost::mpl::if_c<use_ordered_iterators,
 140                                       heap_equivalence_iteration,
 141                                       heap_equivalence_copy
 142                                      >::type equivalence_check;
 143
 144     equivalence_check eq_check;
 145     return eq_check(lhs, rhs);
 146 }
 147
 148
 149 struct heap_compare_iteration
 150 {
 151     template <typename Heap1,
 152               typename Heap2
 153              >
 154     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
 155     {
 156         typename Heap1::size_type left_size = lhs.size();
 157         typename Heap2::size_type right_size = rhs.size();
 158         if (left_size < right_size)
 159             return true;
 160
 161         if (left_size > right_size)
 162             return false;
 163
 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();
 168         while (true) {
 169             if (value_compare(lhs, rhs, *it1, *it2))
 170                 return true;
 171
 172             if (value_compare(lhs, rhs, *it2, *it1))
 173                 return false;
 174
 175             ++it1;
 176             ++it2;
 177
 178             if (it1 == it1_end && it2 == it2_end)
 179                 return true;
 180
 181             if (it1 == it1_end || it2 == it2_end)
 182                 return false;
 183         }
 184     }
 185 };
 186
 187 struct heap_compare_copy
 188 {
 189     template <typename Heap1,
 190               typename Heap2
 191              >
 192     bool operator()(Heap1 const & lhs, Heap2 const & rhs)
 193     {
 194         typename Heap1::size_type left_size = lhs.size();
 195         typename Heap2::size_type right_size = rhs.size();
 196         if (left_size < right_size)
 197             return true;
 198
 199         if (left_size > right_size)
 200             return false;
 201
 202         Heap1 lhs_copy(lhs);
 203         Heap2 rhs_copy(rhs);
 204
 205         while (true) {
 206             if (value_compare(lhs_copy, rhs_copy, lhs_copy.top(), rhs_copy.top()))
 207                 return true;
 208
 209             if (value_compare(lhs_copy, rhs_copy, rhs_copy.top(), lhs_copy.top()))
 210                 return false;
 211
 212             lhs_copy.pop();
 213             rhs_copy.pop();
 214
 215             if (lhs_copy.empty() && rhs_copy.empty())
 216                 return false;
 217         }
 218     }
 219 };
 220
 221 template <typename Heap1,
 222           typename Heap2
 223          >
 224 bool heap_compare(Heap1 const & lhs, Heap2 const & rhs)
 225 {
 226     const bool use_ordered_iterators = Heap1::has_ordered_iterators && Heap2::has_ordered_iterators;
 227
 228     typedef typename boost::mpl::if_c<use_ordered_iterators,
 229                                       heap_compare_iteration,
 230                                       heap_compare_copy
 231                                      >::type compare_check;
 232
 233     compare_check check_object;
 234     return check_object(lhs, rhs);
 235 }
 236
 237
 238 } /* namespace detail */
 239 } /* namespace heap */
 240 } /* namespace boost */
 241
 242
 243 #undef BOOST_HEAP_ASSERT
 244
 245 #endif // BOOST_HEAP_DETAIL_HEAP_COMPARISON_HPP