1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/test/heap_test.cc	Fri Mar 04 17:10:23 2005 +0000
     1.3 @@ -0,0 +1,123 @@
     1.4 +// -*- c++ -*-
     1.5 +
     1.6 +#include <iostream>
     1.7 +#include <fstream>
     1.8 +#include <vector>
     1.9 +
    1.10 +#include <lemon/concept_check.h>
    1.11 +
    1.12 +#include <lemon/bin_heap.h>
    1.13 +#include <lemon/fib_heap.h>
    1.14 +#include <lemon/radix_heap.h>
    1.15 +
    1.16 +#include <lemon/dimacs.h>
    1.17 +
    1.18 +#include "test_tools.h"
    1.19 +#include "heap_test.h"
    1.20 +#include "map_test.h"
    1.21 +
    1.22 +
    1.23 +using namespace lemon;
    1.24 +
    1.25 +template <typename Item, typename Prio, typename ItemIntMap>
    1.26 +class HeapConcept {
    1.27 +public:  
    1.28 +
    1.29 +  template <typename _Heap>
    1.30 +  struct Constraints {
    1.31 +  public:
    1.32 +    
    1.33 +    void constraints() {
    1.34 +      Item item;
    1.35 +      Prio prio;
    1.36 +
    1.37 +      typedef typename _Heap::state_enum state_enum;
    1.38 +      state_enum state;
    1.39 +      
    1.40 +      _Heap heap1 = _Heap(map);
    1.41 +      
    1.42 +      heap.push(item, prio);
    1.43 +
    1.44 +      prio = heap.prio();
    1.45 +      item = heap.top();
    1.46 +
    1.47 +      heap.pop();
    1.48 +
    1.49 +      heap.set(item, prio);
    1.50 +      heap.decrease(item, prio);
    1.51 +      heap.increase(item, prio);
    1.52 +      prio = heap[item];
    1.53 +
    1.54 +      heap.erase(item);
    1.55 +
    1.56 +      state = heap.state(item);
    1.57 +
    1.58 +      state = _Heap::PRE_HEAP;
    1.59 +      state = _Heap::IN_HEAP;
    1.60 +      state = _Heap::POST_HEAP;
    1.61 +    }
    1.62 +    
    1.63 +    _Heap& heap;
    1.64 +    ItemIntMap& map;
    1.65 +  };
    1.66 +};
    1.67 +
    1.68 +int main() {
    1.69 +
    1.70 +  typedef int Item;
    1.71 +  typedef int Prio;
    1.72 +  typedef IntIntMap ItemIntMap;
    1.73 +
    1.74 +  typedef ListGraph Graph;
    1.75 +
    1.76 +  typedef Graph::Edge Edge;
    1.77 +  typedef Graph::Node Node;
    1.78 +  typedef Graph::EdgeIt EdgeIt;
    1.79 +  typedef Graph::NodeIt NodeIt;
    1.80 +  typedef Graph::EdgeMap<int> LengthMap;
    1.81 +
    1.82 +  Graph graph;
    1.83 +  LengthMap length(graph);
    1.84 +  Node start;
    1.85 +
    1.86 +  std::ifstream input("preflow_graph.dim");
    1.87 +  readDimacs(input, graph, length, start);  
    1.88 + 
    1.89 +  {
    1.90 +    std::cerr << "Checking Bin Heap" << std::endl;
    1.91 +
    1.92 +    typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
    1.93 +    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
    1.94 +    heapSortTest<IntHeap>(20);
    1.95 +    
    1.96 +    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
    1.97 +    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
    1.98 +    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
    1.99 +  }
   1.100 +  {
   1.101 +    std::cerr << "Checking Fib Heap" << std::endl;
   1.102 +
   1.103 +    typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
   1.104 +    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
   1.105 +    heapSortTest<IntHeap>(20);
   1.106 +
   1.107 +    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
   1.108 +    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
   1.109 +    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
   1.110 +  }
   1.111 +  {
   1.112 +    std::cerr << "Checking Radix Heap" << std::endl;
   1.113 +
   1.114 +    typedef RadixHeap<Item, ItemIntMap> IntHeap;
   1.115 +    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
   1.116 +    heapSortTest<IntHeap>(20);
   1.117 +
   1.118 +    typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
   1.119 +    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
   1.120 +    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
   1.121 +  }
   1.122 +
   1.123 +  std::cout << __FILE__ ": All tests passed.\n";
   1.124 +
   1.125 +  return 0;
   1.126 +}