diff -r 448f76e44b24 -r 04e5825000c5 src/test/heap_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/heap_test.cc	Fri Mar 04 17:10:23 2005 +0000
@@ -0,0 +1,123 @@
+// -*- c++ -*-
+
+#include <iostream>
+#include <fstream>
+#include <vector>
+
+#include <lemon/concept_check.h>
+
+#include <lemon/bin_heap.h>
+#include <lemon/fib_heap.h>
+#include <lemon/radix_heap.h>
+
+#include <lemon/dimacs.h>
+
+#include "test_tools.h"
+#include "heap_test.h"
+#include "map_test.h"
+
+
+using namespace lemon;
+
+template <typename Item, typename Prio, typename ItemIntMap>
+class HeapConcept {
+public:  
+
+  template <typename _Heap>
+  struct Constraints {
+  public:
+    
+    void constraints() {
+      Item item;
+      Prio prio;
+
+      typedef typename _Heap::state_enum state_enum;
+      state_enum state;
+      
+      _Heap heap1 = _Heap(map);
+      
+      heap.push(item, prio);
+
+      prio = heap.prio();
+      item = heap.top();
+
+      heap.pop();
+
+      heap.set(item, prio);
+      heap.decrease(item, prio);
+      heap.increase(item, prio);
+      prio = heap[item];
+
+      heap.erase(item);
+
+      state = heap.state(item);
+
+      state = _Heap::PRE_HEAP;
+      state = _Heap::IN_HEAP;
+      state = _Heap::POST_HEAP;
+    }
+    
+    _Heap& heap;
+    ItemIntMap& map;
+  };
+};
+
+int main() {
+
+  typedef int Item;
+  typedef int Prio;
+  typedef IntIntMap ItemIntMap;
+
+  typedef ListGraph Graph;
+
+  typedef Graph::Edge Edge;
+  typedef Graph::Node Node;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::EdgeMap<int> LengthMap;
+
+  Graph graph;
+  LengthMap length(graph);
+  Node start;
+
+  std::ifstream input("preflow_graph.dim");
+  readDimacs(input, graph, length, start);  
+ 
+  {
+    std::cerr << "Checking Bin Heap" << std::endl;
+
+    typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
+    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>(20);
+    
+    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
+    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
+    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
+  }
+  {
+    std::cerr << "Checking Fib Heap" << std::endl;
+
+    typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
+    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>(20);
+
+    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
+    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
+    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
+  }
+  {
+    std::cerr << "Checking Radix Heap" << std::endl;
+
+    typedef RadixHeap<Item, ItemIntMap> IntHeap;
+    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>(20);
+
+    typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
+    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
+    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
+  }
+
+  std::cout << __FILE__ ": All tests passed.\n";
+
+  return 0;
+}