// 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;
}