1.1 --- a/src/test/heap_test.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,110 +0,0 @@
1.4 -// -+- c++ -+-
1.5 -
1.6 -#include <vector>
1.7 -#include <algorithm>
1.8 -
1.9 -#include <lemon/dijkstra.h>
1.10 -
1.11 -class IntIntMap : public std::vector<int> {
1.12 -public:
1.13 - typedef std::vector<int> Parent;
1.14 -
1.15 - IntIntMap() : Parent() {}
1.16 - IntIntMap(int n) : Parent(n) {}
1.17 - IntIntMap(int n, int v) : Parent(n, v) {}
1.18 -
1.19 - void set(int key, int value) {
1.20 - Parent::operator[](key) = value;
1.21 - }
1.22 -};
1.23 -
1.24 -
1.25 -template <typename _Heap>
1.26 -void heapSortTest(int n) {
1.27 - typedef _Heap Heap;
1.28 - IntIntMap map(n, -1);
1.29 -
1.30 - Heap heap(map);
1.31 -
1.32 - std::vector<int> v(n);
1.33 -
1.34 - for (int i = 0; i < n; ++i) {
1.35 - v[i] = rand() % 1000;
1.36 - heap.push(i, v[i]);
1.37 - }
1.38 - std::sort(v.begin(), v.end());
1.39 - for (int i = 0; i < n; ++i) {
1.40 - check(v[i] == heap.prio() ,"Wrong order in heap sort.");
1.41 - heap.pop();
1.42 - }
1.43 -}
1.44 -
1.45 -template <typename _Heap>
1.46 -void heapIncreaseTest(int n) {
1.47 - typedef _Heap Heap;
1.48 - IntIntMap map(n, -1);
1.49 -
1.50 - Heap heap(map);
1.51 -
1.52 - std::vector<int> v(n);
1.53 -
1.54 - for (int i = 0; i < n; ++i) {
1.55 - v[i] = rand() % 1000;
1.56 - heap.push(i, v[i]);
1.57 - }
1.58 - for (int i = 0; i < n; ++i) {
1.59 - v[i] += rand() % 1000;
1.60 - heap.increase(i, v[i]);
1.61 - }
1.62 - std::sort(v.begin(), v.end());
1.63 - for (int i = 0; i < n; ++i) {
1.64 - check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
1.65 - heap.pop();
1.66 - }
1.67 -}
1.68 -
1.69 -
1.70 -
1.71 -template <typename _Traits, typename _Heap>
1.72 -struct DefHeapTraits : public _Traits {
1.73 - typedef _Heap Heap;
1.74 -};
1.75 -
1.76 -template <typename _Graph, typename _LengthMap, typename _Heap>
1.77 -void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
1.78 - typename _Graph::Node& start) {
1.79 -
1.80 - typedef _Heap Heap;
1.81 - typedef _Graph Graph;
1.82 - typedef _LengthMap LengthMap;
1.83 -
1.84 - typedef typename Graph::Node Node;
1.85 - typedef typename Graph::Edge Edge;
1.86 - typedef typename Graph::NodeIt NodeIt;
1.87 - typedef typename Graph::EdgeIt EdgeIt;
1.88 -
1.89 - Dijkstra<Graph, LengthMap,
1.90 - DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> >
1.91 - dijkstra(graph, length);
1.92 -
1.93 - dijkstra.run(start);
1.94 -
1.95 - for(EdgeIt e(graph); e!=INVALID; ++e) {
1.96 - Node u=graph.source(e);
1.97 - Node v=graph.target(e);
1.98 - if (dijkstra.reached(u)) {
1.99 - check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
1.100 - "Error in a shortest path tree edge!");
1.101 - }
1.102 - }
1.103 -
1.104 - for(NodeIt v(graph); v!=INVALID; ++v) {
1.105 - if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) {
1.106 - Edge e=dijkstra.pred(v);
1.107 - Node u=graph.source(e);
1.108 - check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
1.109 - "Error in a shortest path tree edge!");
1.110 - }
1.111 - }
1.112 -
1.113 -}