src/test/heap_test.cc
author deba
Tue, 05 Apr 2005 12:30:46 +0000
changeset 1307 d4acebef7276
parent 1206 9c398137c2cb
child 1325 916ec8699dc3
permissions -rw-r--r--
Stuffs moved into bits
     1 // -*- c++ -*-
     2 
     3 #include <iostream>
     4 #include <fstream>
     5 #include <string>
     6 #include <vector>
     7 
     8 #include <lemon/concept_check.h>
     9 
    10 #include <lemon/smart_graph.h>
    11 
    12 #include <lemon/graph_reader.h>
    13 
    14 #include <lemon/bin_heap.h>
    15 #include <lemon/fib_heap.h>
    16 #include <lemon/radix_heap.h>
    17 
    18 #include "test_tools.h"
    19 
    20 #include "heap_test.h"
    21 
    22 
    23 using namespace lemon;
    24 
    25 template <typename Item, typename Prio, typename ItemIntMap>
    26 class HeapConcept {
    27 public:  
    28 
    29   template <typename _Heap>
    30   struct Constraints {
    31   public:
    32     
    33     void constraints() {
    34       Item item;
    35       Prio prio;
    36 
    37       ignore_unused_variable_warning(item);
    38       ignore_unused_variable_warning(prio);
    39 
    40       typedef typename _Heap::state_enum state_enum;
    41       state_enum state;
    42 
    43       ignore_unused_variable_warning(state);
    44       
    45       _Heap heap1 = _Heap(map);
    46 
    47       ignore_unused_variable_warning(heap1);
    48       
    49       heap.push(item, prio);
    50 
    51       prio = heap.prio();
    52       item = heap.top();
    53 
    54       heap.pop();
    55 
    56       heap.set(item, prio);
    57       heap.decrease(item, prio);
    58       heap.increase(item, prio);
    59       prio = heap[item];
    60 
    61       heap.erase(item);
    62 
    63       state = heap.state(item);
    64 
    65       state = _Heap::PRE_HEAP;
    66       state = _Heap::IN_HEAP;
    67       state = _Heap::POST_HEAP;
    68     }
    69     
    70     _Heap& heap;
    71     ItemIntMap& map;
    72   };
    73 };
    74 
    75 int main() {
    76 
    77   typedef int Item;
    78   typedef int Prio;
    79   typedef IntIntMap ItemIntMap;
    80 
    81   typedef ListGraph Graph;
    82 
    83   typedef Graph::Edge Edge;
    84   typedef Graph::Node Node;
    85   typedef Graph::EdgeIt EdgeIt;
    86   typedef Graph::NodeIt NodeIt;
    87   typedef Graph::EdgeMap<int> LengthMap;
    88 
    89   Graph graph;
    90   LengthMap length(graph);
    91   Node start;
    92 
    93   /// \todo create own test graph
    94 
    95   std::string f_name;
    96   if( getenv("srcdir") )
    97     f_name = std::string(getenv("srcdir"));
    98   else f_name = ".";
    99   f_name += "/dijkstra_test.lgf";
   100   
   101   std::ifstream input(f_name.c_str());
   102   check(input, "Input file '" << f_name << "' not found.");
   103   readGraph(input, graph, length, start);  
   104  
   105   {
   106     std::cerr << "Checking Bin Heap" << std::endl;
   107 
   108     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
   109     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
   110     heapSortTest<IntHeap>(100);
   111     heapIncreaseTest<IntHeap>(100);
   112     
   113     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
   114     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
   115     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
   116   }
   117   {
   118     std::cerr << "Checking Fib Heap" << std::endl;
   119 
   120     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
   121     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
   122     heapSortTest<IntHeap>(100);
   123     heapIncreaseTest<IntHeap>(100);
   124 
   125     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
   126     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
   127     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
   128   }
   129   {
   130     std::cerr << "Checking Radix Heap" << std::endl;
   131 
   132     typedef RadixHeap<Item, ItemIntMap> IntHeap;
   133     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
   134     heapSortTest<IntHeap>(100);
   135     heapIncreaseTest<IntHeap>(100);
   136 
   137     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
   138     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
   139     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
   140   }
   141 
   142   std::cout << __FILE__ ": All tests passed.\n";
   143 
   144   return 0;
   145 }