[Boost-bugs] [Boost C++ Libraries] #13087: Boost::binomial_heap Merge error

Subject: [Boost-bugs] [Boost C++ Libraries] #13087: Boost::binomial_heap Merge error
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-06-20 17:27:54

#13087: Boost::binomial_heap Merge error
------------------------------+--------------------------
 Reporter:  jun.kudo@…        |      Owner:  timblechmann
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  heap
  Version:  Boost 1.64.0      |   Severity:  Problem
 Keywords:                    |
------------------------------+--------------------------
 Configured with BOOST_HEAP_SANITYCHECKS turned on.
 Binomial heap hits an assertion failure during the second merge routine in
 the attached example.

 {{{
 #include "boost/heap/binomial_heap.hpp"
 typedef boost::heap::binomial_heap<int> Heap;

 int main(int argc, char* argv[]) {
   Heap heap0;
   size_t heap0_size = 13;
   size_t max_range = 100;
   for (size_t ix = 0; ix < heap0_size; ++ix) {
     heap0.push(rand() % max_range);
   }

   Heap heap1;
   size_t heap1_size = 5;
   for (size_t ix = 0; ix < heap1_size; ++ix) {
     heap1.push(rand() % max_range);
   }
   heap0.merge(heap1);

   Heap heap2;
   size_t heap2_size = 1;
   for (size_t ix = 0; ix < heap2_size; ++ix) {
     heap2.push(rand() % max_range);
   }
   heap2.merge(heap0);

 }
 }}}

 When heap1 is merged into heap0, the underlying forest incorrectly
 contains two 2-degree trees.  This error is later caught in a sanity
 assertion check when heap0 is merged into heap2.

 I believe the error stems the case identified by line 668 in
 binomial_heap.hpp.  When the two root degrees are equal and a carry tree
 with degree less than both exist, the carry tree is inserted into trees.
 However, after this insertion, the this_iterator is incorrectly iterated
 forward which causes the algorithm to behave incorrectly.  In the case
 provided above, this causes the merge algorithm to skip the degree-2 /
 degree-2 merge between this and rhs, and instead causes rhs's degree-2
 tree to be simple inserted into trees.

--
Ticket URL: <https://svn.boost.org/trac10/boost/ticket/13087>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.