Ticket #11394: boost_binomial_heap_bug.cpp

// compile as: 
//              g++ boost_binomial_heap_bug.cpp -o boost_binomial_heap_bug
//
#include <iostream>
#include <cassert>

//#define BOOST_HEAP_SANITYCHECKS
#include <boost/heap/fibonacci_heap.hpp>
#include <boost/heap/binomial_heap.hpp>

typedef struct node_t {
        int value;
        int weight;

        explicit node_t(int v, int w) {
                value = v;
                weight = w;
        }
} node_t;

typedef struct node_comparator {
        inline
        bool operator()(const node_t &n1, const node_t &n2) const {
                return n1.weight > n2.weight;
        }
} node_comparator;

typedef boost::heap::fibonacci_heap<node_t, boost::heap::compare<node_comparator> > fibonacci_heap_t;
typedef boost::heap::binomial_heap<node_t, boost::heap::compare<node_comparator>, boost::heap::stable<true> > binomial_stable_heap_t;
typedef boost::heap::binomial_heap<node_t, boost::heap::compare<node_comparator> > binomial_unstable_heap_t;

template <typename T>
void check_heap(T &heap) {
        int heap_size = 0;

        for (int i = 0; i < 3; i++) {
                heap.push(node_t(i, 9));
                heap_size++;
        }

        assert (heap_size == heap.size());

        while (!heap.empty()) {
                const node_t &e = heap.top();
                heap.pop();

                heap_size--;

                assert (heap_size == heap.size());
        }
}
int main(void) {
        std::cout << "Checking fibonacci heap...\n";
        fibonacci_heap_t fheap;
        check_heap(fheap);

        std::cout << "Checking binomial stable heap...\n";
        binomial_stable_heap_t bsheap;
        check_heap(bsheap);

        std::cout << "Checking binomial unstable  heap...\n";
        binomial_unstable_heap_t buheap;
        check_heap(buheap);
        return EXIT_SUCCESS;
}