# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 2008-07-11 15:01:49
# Node ID 215bfc30b14fb8defcf1c0e00acde84abc1b3a28
# Parent  a5ee729dc1e10eb45f0925d2956766671f1c3d63

Cleaning of heap test and bug fix in heap concept check (ticket #100)

 * The dijkstra heap test's digraph is inlined into the source file
 * The random sequences are fixed
 * The content of the header is moved to the source file
 * Only the binary heap is checked

diff --git a/lemon/concepts/heap.h b/lemon/concepts/heap.h
--- a/lemon/concepts/heap.h
+++ b/lemon/concepts/heap.h
@@ -181,12 +181,10 @@
 
 	  Item item;
 	  Prio prio;
-	  State state;
 	  item=Item();
 	  prio=Prio();
 	  ignore_unused_variable_warning(item);
 	  ignore_unused_variable_warning(prio);
-	  ignore_unused_variable_warning(state);
 
 	  OwnItem own_item;
 	  OwnPrio own_prio;
@@ -203,7 +201,9 @@
 	  ignore_unused_variable_warning(heap2);
 	  
 	  int s = heap.size();
+	  ignore_unused_variable_warning(s);
 	  bool e = heap.empty();
+	  ignore_unused_variable_warning(e);
 
 	  prio = heap.prio();
 	  item = heap.top();
@@ -227,14 +227,9 @@
 	  heap.erase(own_item);
 	  heap.clear();
 
-	  state = heap.state(item);
-	  heap.state(item, state);
-	  state = heap.state(own_item);
+	  own_state = heap.state(own_item);
 	  heap.state(own_item, own_state);
 
-	  state = _Heap::PRE_HEAP;
-	  state = _Heap::IN_HEAP;
-	  state = _Heap::POST_HEAP;
 	  own_state = _Heap::PRE_HEAP;
 	  own_state = _Heap::IN_HEAP;
 	  own_state = _Heap::POST_HEAP;
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -13,6 +13,7 @@
   graph_copy_test
   graph_test
   graph_utils_test
+  heap_test
   kruskal_test
   maps_test
   path_test
diff --git a/test/Makefile.am b/test/Makefile.am
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -3,7 +3,6 @@
 
 noinst_HEADERS += \
 	test/graph_test.h \
-	test/heap_test.h \
 	test/graph_maps_test.h \
         test/test_tools.h
 
@@ -18,6 +17,7 @@
 	test/graph_copy_test \
 	test/graph_test \
 	test/graph_utils_test \
+	test/heap_test \
 	test/kruskal_test \
         test/maps_test \
         test/random_test \
@@ -40,7 +40,7 @@
 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
-# test_heap_test_SOURCES = test/heap_test.cc
+test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
 test_maps_test_SOURCES = test/maps_test.cc
 test_path_test_SOURCES = test/path_test.cc
diff --git a/test/heap_test.cc b/test/heap_test.cc
--- a/test/heap_test.cc
+++ b/test/heap_test.cc
@@ -24,113 +24,163 @@
 #include <lemon/concept_check.h>
 #include <lemon/concepts/heap.h>
 
-#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
 
-#include <lemon/digraph_reader.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/dijkstra.h>
+#include <lemon/maps.h>
 
 #include <lemon/bin_heap.h>
-#include <lemon/fib_heap.h>
-#include <lemon/radix_heap.h>
-#include <lemon/bucket_heap.h>
 
 #include "test_tools.h"
 
-#include "heap_test.h"
-
-#include <lemon/time_measure.h>
-
 using namespace lemon;
 using namespace lemon::concepts;
 
+typedef ListDigraph Digraph;
+DIGRAPH_TYPEDEFS(Digraph);
+
+char test_lgf[] = 
+  "@nodes\n" 
+  "label\n"	
+  "0\n"	
+  "1\n"	
+  "2\n"	
+  "3\n"	
+  "4\n"	
+  "5\n"	
+  "6\n"	
+  "7\n"	
+  "8\n"	
+  "9\n"	
+  "@arcs\n" 
+  "		label	capacity\n"	
+  "0	5	0	94\n"	
+  "3	9	1	11\n"	
+  "8	7	2	83\n"	
+  "1	2	3	94\n"	
+  "5	7	4	35\n"	
+  "7	4	5	84\n"	
+  "9	5	6	38\n"	
+  "0	4	7	96\n"	
+  "6	7	8	6\n"	
+  "3	1	9	27\n"	
+  "5	2	10	77\n"	
+  "5	6	11	69\n"	
+  "6	5	12	41\n"	
+  "4	6	13	70\n"	
+  "3	2	14	45\n"	
+  "7	9	15	93\n"	
+  "5	9	16	50\n"	
+  "9	0	17	94\n"	
+  "9	6	18	67\n"	
+  "0	9	19	86\n"	
+  "@attributes\n" 
+  "source 3\n";
+
+int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
+int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
+
+int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
+
+template <typename Heap>
+void heapSortTest() {
+  RangeMap<int> map(test_len, -1);
+
+  Heap heap(map);
+  
+  std::vector<int> v(test_len);
+
+  for (int i = 0; i < test_len; ++i) {
+    v[i] = test_seq[i];
+    heap.push(i, v[i]);
+  }
+  std::sort(v.begin(), v.end());
+  for (int i = 0; i < test_len; ++i) {
+    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
+    heap.pop();
+  }
+}
+
+template <typename Heap>
+void heapIncreaseTest() {
+  RangeMap<int> map(test_len, -1);
+
+  Heap heap(map);
+  
+  std::vector<int> v(test_len);
+
+  for (int i = 0; i < test_len; ++i) {
+    v[i] = test_seq[i];
+    heap.push(i, v[i]);
+  }
+  for (int i = 0; i < test_len; ++i) {
+    v[i] += test_inc[i];
+    heap.increase(i, v[i]);
+  }
+  std::sort(v.begin(), v.end());
+  for (int i = 0; i < test_len; ++i) {
+    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
+    heap.pop();
+  }
+}
+
+
+
+template <typename Heap>
+void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 
+		      Node source) {
+  
+  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
+    Create dijkstra(digraph, length);
+
+  dijkstra.run(source);
+
+  for(ArcIt a(digraph); a != INVALID; ++a) {
+    Node s = digraph.source(a); 
+    Node t = digraph.target(a);
+    if (dijkstra.reached(s)) {
+      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
+      	     "Error in a shortest path tree!");
+    }
+  }
+
+  for(NodeIt n(digraph); n != INVALID; ++n) {
+    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
+      Arc a = dijkstra.predArc(n);
+      Node s = digraph.source(a);
+      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
+	     "Error in a shortest path tree!");
+    }
+  }
+
+}
+
 int main() {
 
   typedef int Item;
   typedef int Prio;
-  typedef IntIntMap ItemIntMap;
+  typedef RangeMap<int> ItemIntMap;
+  
+  Digraph digraph;
+  IntArcMap length(digraph);
+  Node source;
 
-  typedef ListDigraph Digraph;
-
-  typedef Digraph::Arc Arc;
-  typedef Digraph::Node Node;
-  typedef Digraph::ArcIt ArcIt;
-  typedef Digraph::NodeIt NodeIt;
-  typedef Digraph::ArcMap<int> LengthMap;
-
-  Digraph digraph;
-  LengthMap length(digraph);
-  Node start;
-
-  /// \todo create own test digraph
-
-  std::string f_name;
-  if( getenv("srcdir") )
-    f_name = std::string(getenv("srcdir"));
-  else f_name = ".";
-  f_name += "/test/dijkstra_test.lgf";
-  
-  std::ifstream input(f_name.c_str());
-  check(input, "Input file '" << f_name << "' not found.");
-  DigraphReader<Digraph>(input, digraph).
-    readArcMap("capacity", length).
-    readNode("source", start).
+  std::istringstream input(test_lgf);
+  digraphReader(input, digraph).
+    arcMap("capacity", length).
+    node("source", source).
     run();  
  
   {
-    std::cout << "Checking Bin Heap" << std::endl;
-
     typedef BinHeap<Prio, ItemIntMap> IntHeap;
     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
     
-    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
-  }
-  {
-    std::cout << "Checking Fib Heap" << std::endl;
-
-    typedef FibHeap<Prio, ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
-
-    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
-  }
-  {
-    std::cout << "Checking Radix Heap" << std::endl;
-
-    typedef RadixHeap<ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
-
-    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
-  }
-
-  {
-    std::cout << "Checking Bucket Heap" << std::endl;
-
-    typedef BucketHeap<ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
-
-    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
+    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
   }
 
   return 0;
diff --git a/test/heap_test.h b/test/heap_test.h
deleted file mode 100644
--- a/test/heap_test.h
+++ /dev/null
@@ -1,123 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2008
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#include <vector>
-#include <algorithm>
-
-#include <lemon/dijkstra.h>
-
-class IntIntMap : public std::vector<int> {
-public:
-  typedef std::vector<int> Parent;
-
-  typedef int Key;
-  typedef int Value;
-
-  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] = rnd[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] = rnd[1000];
-    heap.push(i, v[i]);
-  }
-  for (int i = 0; i < n; ++i) {
-    v[i] += rnd[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 _Digraph, typename _LengthMap, typename _Heap>
-void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length,
-		      typename _Digraph::Node& start) {
-
-  typedef _Heap Heap;
-  typedef _Digraph Digraph;
-  typedef _LengthMap LengthMap;
-
-  typedef typename Digraph::Node Node;
-  typedef typename Digraph::Arc Arc;
-  typedef typename Digraph::NodeIt NodeIt;
-  typedef typename Digraph::ArcIt ArcIt;
-
-  typename Dijkstra<Digraph, LengthMap>::template DefStandardHeap<Heap>::
-    Create dijkstra(digraph, length);
-
-  dijkstra.run(start);
-
-  for(ArcIt e(digraph); e!=INVALID; ++e) {
-    Node u=digraph.source(e); 
-    Node v=digraph.target(e);
-    if (dijkstra.reached(u)) {
-      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
-      	     "Error in a shortest path tree arc!");
-    }
-  }
-
-  for(NodeIt v(digraph); v!=INVALID; ++v) {
-    if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) {
-      Arc e=dijkstra.predArc(v);
-      Node u=digraph.source(e);
-      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
-	     "Error in a shortest path tree arc!");
-    }
-  }
-
-}