# HG changeset patch
# User deba
# Date 1109956223 0
# Node ID 04e5825000c5fc9d53ea8e1fcf8754da571b13c0
# Parent  448f76e44b247b57b4ef144367e144ce1fbbc8ae
concept and checking functions for heaps

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;
+}
diff -r 448f76e44b24 -r 04e5825000c5 src/test/heap_test.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/heap_test.h	Fri Mar 04 17:10:23 2005 +0000
@@ -0,0 +1,87 @@
+// -+- 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!");
+    }
+  }
+
+}