diff -r d8475431bbbb -r 8e85e6bbefdf test/heap_test.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/heap_test.h	Mon May 23 04:48:14 2005 +0000
@@ -0,0 +1,110 @@
+// -+- c++ -+-
+
+#include <vector>
+#include <algorithm>
+
+#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 _Heap>
+void heapIncreaseTest(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]);
+  }
+  for (int i = 0; i < n; ++i) {
+    v[i] += rand() % 1000;
+    heap.increase(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 increase test.");
+    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) && dijkstra.pred(v) != INVALID ) {
+      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!");
+    }
+  }
+
+}