// -+- c++ -+-

#include <vector>

#include <algorithm>

#include <lemon/bin_heap.h>

#include <lemon/fib_heap.h>

#include <lemon/radix_heap.h>

#include <lemon/dijkstra.h>

class IntIntMap : public std::vector<int> {

public:

  typedef std::vector<int> Parent;

  IntIntMap() : Parent() {}

  IntIntMap(int n) : Parent(n) {}

  IntIntMap(int n, int v) : Parent(n, v) {}

  void set(int key, int value) {

    Parent::operator[](key) = value;

  }

};

template <typename _Heap>

void heapSortTest(int n) {

  typedef _Heap Heap;

  IntIntMap map(n, -1);

  Heap heap(map);

  std::vector<int> v(n);

  for (int i = 0; i < n; ++i) {

    v[i] = rand() % 1000;

    heap.push(i, v[i]);

  }

  std::sort(v.begin(), v.end());

  for (int i = 0; i < n; ++i) {

    check(v[i] == heap.prio() ,"Wrong order in heap sort.");

    heap.pop();

  }

}

template <typename _Traits, typename _Heap>

struct DefHeapTraits : public _Traits {

  typedef _Heap Heap;

};

template <typename _Graph, typename _LengthMap, typename _Heap>

void dijkstraHeapTest(_Graph& graph, _LengthMap& length,

		      typename _Graph::Node& start) {

  typedef _Heap Heap;

  typedef _Graph Graph;

  typedef _LengthMap LengthMap;

  typedef typename Graph::Node Node;

  typedef typename Graph::Edge Edge;

  typedef typename Graph::NodeIt NodeIt;

  typedef typename Graph::EdgeIt EdgeIt;

  Dijkstra<Graph, LengthMap, 

    DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> > 

    dijkstra(graph, length);

  dijkstra.run(start);

  for(EdgeIt e(graph); e!=INVALID; ++e) {

    Node u=graph.source(e); 

    Node v=graph.target(e);

    if (dijkstra.reached(u)) {

      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],

	     "Error in a shortest path tree edge!");

    }

  }

  for(NodeIt v(graph); v!=INVALID; ++v) {

    if ( dijkstra.reached(v) ) {

      Edge e=dijkstra.pred(v);

      Node u=graph.source(e);

      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],

	     "Error in a shortest path tree edge!");

    }

  }

}