#include <boost/heap/fibonacci_heap.hpp>
#include <boost/heap/priority_queue.hpp>
#include <boost/heap/binomial_heap.hpp>
#include <boost/heap/d_ary_heap.hpp>
#include <queue>
#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;

const int NUM_ITER = 100000;

template<class T>
void test(const char *name)
{
	T pq;

	auto ts = system_clock::now();
    for(int i=0; i<NUM_ITER; i++){
        pq.push(rand());
    }
    for(int i=0; i<NUM_ITER; i++){
        pq.pop();
    }
    double ts1 = duration_cast<nanoseconds>(system_clock::now() - ts).count();
    cout << name << " " << ts1/(double)NUM_ITER << " ns\n";
}

template<class T>
void test_mod(const char *name)
{
	T pq;
	
	std::vector<typename T::handle_type> handles;
	handles.reserve(NUM_ITER);

	auto ts = system_clock::now();
    for(int i=0; i<NUM_ITER; i++){
        handles.push_back(pq.push(rand()));
    }
    for(int i=0; i<NUM_ITER; i++){
    	pq.update(handles[i], rand());
    }
    for(int i=0; i<NUM_ITER; i++){
        pq.pop();
    }
    double ts1 = duration_cast<nanoseconds>(system_clock::now() - ts).count();
    cout << name << " " << ts1/(double)NUM_ITER << " ns\n";
}


int main(){
    std::priority_queue<int> pq;
    std::priority_queue<int, std::deque<int> > pqd;
    boost::heap::priority_queue<int> bpq;
    boost::heap::fibonacci_heap<int> bfh;
    boost::heap::binomial_heap<int> bbh;


    cout << "NUM_ITER:" << NUM_ITER << "\n";
    
    test<std::priority_queue<int>>("std::priority_queue<int>");
    test<std::priority_queue<int, std::deque<int> >>("std::priority_queue<int, std::deque<int> >");
    test<boost::heap::priority_queue<int>>("boost::heap::priority_queue<int>");
    test<boost::heap::fibonacci_heap<int>>("boost::heap::fibonacci_heap<int>");
    test<boost::heap::binomial_heap<int>>("boost::heap::binomial_heap<int>");
    test<boost::heap::d_ary_heap<int, boost::heap::arity<8>>>("boost::heap::d_ary_heap<int, boost::heap::arity<8>>");
    
    cout << "\n with mutablity:" << std::endl;
    
    test_mod<boost::heap::fibonacci_heap<int>>("boost::heap::fibonacci_heap<int>");
    test_mod<boost::heap::binomial_heap<int>>("boost::heap::binomial_heap<int>");
    test_mod<boost::heap::d_ary_heap<int, boost::heap::arity<8>, boost::heap::mutable_<true>>>("boost::heap::d_ary_heap<int, boost::heap::arity<8>, boost::heap::mutable_<true>>");
}