diff -r d8475431bbbb -r 8e85e6bbefdf src/test/heap_test.h --- a/src/test/heap_test.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,110 +0,0 @@ -// -+- c++ -+- - -#include -#include - -#include - -class IntIntMap : public std::vector { -public: - typedef std::vector 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 -void heapSortTest(int n) { - typedef _Heap Heap; - IntIntMap map(n, -1); - - Heap heap(map); - - std::vector 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 -void heapIncreaseTest(int n) { - typedef _Heap Heap; - IntIntMap map(n, -1); - - Heap heap(map); - - std::vector v(n); - - for (int i = 0; i < n; ++i) { - v[i] = rand() % 1000; - heap.push(i, v[i]); - } - for (int i = 0; i < n; ++i) { - v[i] += rand() % 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 -struct DefHeapTraits : public _Traits { - typedef _Heap Heap; -}; - -template -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, 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) && dijkstra.pred(v) != INVALID ) { - 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!"); - } - } - -}