1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/test/heap_test.h	Fri Mar 04 17:10:23 2005 +0000
     1.3 @@ -0,0 +1,87 @@
     1.4 +// -+- c++ -+-
     1.5 +#include <vector>
     1.6 +#include <algorithm>
     1.7 +
     1.8 +#include <lemon/bin_heap.h>
     1.9 +#include <lemon/fib_heap.h>
    1.10 +#include <lemon/radix_heap.h>
    1.11 +
    1.12 +#include <lemon/dijkstra.h>
    1.13 +
    1.14 +class IntIntMap : public std::vector<int> {
    1.15 +public:
    1.16 +  typedef std::vector<int> Parent;
    1.17 +
    1.18 +  IntIntMap() : Parent() {}
    1.19 +  IntIntMap(int n) : Parent(n) {}
    1.20 +  IntIntMap(int n, int v) : Parent(n, v) {}
    1.21 +
    1.22 +  void set(int key, int value) {
    1.23 +    Parent::operator[](key) = value;
    1.24 +  }
    1.25 +};
    1.26 +
    1.27 +
    1.28 +template <typename _Heap>
    1.29 +void heapSortTest(int n) {
    1.30 +  typedef _Heap Heap;
    1.31 +  IntIntMap map(n, -1);
    1.32 +
    1.33 +  Heap heap(map);
    1.34 +  
    1.35 +  std::vector<int> v(n);
    1.36 +
    1.37 +  for (int i = 0; i < n; ++i) {
    1.38 +    v[i] = rand() % 1000;
    1.39 +    heap.push(i, v[i]);
    1.40 +  }
    1.41 +  std::sort(v.begin(), v.end());
    1.42 +  for (int i = 0; i < n; ++i) {
    1.43 +    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
    1.44 +    heap.pop();
    1.45 +  }
    1.46 +}
    1.47 +
    1.48 +template <typename _Traits, typename _Heap>
    1.49 +struct DefHeapTraits : public _Traits {
    1.50 +  typedef _Heap Heap;
    1.51 +};
    1.52 +
    1.53 +template <typename _Graph, typename _LengthMap, typename _Heap>
    1.54 +void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
    1.55 +		      typename _Graph::Node& start) {
    1.56 +
    1.57 +  typedef _Heap Heap;
    1.58 +  typedef _Graph Graph;
    1.59 +  typedef _LengthMap LengthMap;
    1.60 +
    1.61 +  typedef typename Graph::Node Node;
    1.62 +  typedef typename Graph::Edge Edge;
    1.63 +  typedef typename Graph::NodeIt NodeIt;
    1.64 +  typedef typename Graph::EdgeIt EdgeIt;
    1.65 +
    1.66 +  Dijkstra<Graph, LengthMap, 
    1.67 +    DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> > 
    1.68 +    dijkstra(graph, length);
    1.69 +
    1.70 +  dijkstra.run(start);
    1.71 +
    1.72 +  for(EdgeIt e(graph); e!=INVALID; ++e) {
    1.73 +    Node u=graph.source(e); 
    1.74 +    Node v=graph.target(e);
    1.75 +    if (dijkstra.reached(u)) {
    1.76 +      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
    1.77 +	     "Error in a shortest path tree edge!");
    1.78 +    }
    1.79 +  }
    1.80 +
    1.81 +  for(NodeIt v(graph); v!=INVALID; ++v) {
    1.82 +    if ( dijkstra.reached(v) ) {
    1.83 +      Edge e=dijkstra.pred(v);
    1.84 +      Node u=graph.source(e);
    1.85 +      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
    1.86 +	     "Error in a shortest path tree edge!");
    1.87 +    }
    1.88 +  }
    1.89 +
    1.90 +}