deba@1728: // -*- c++ -*- deba@1206: deba@1187: #include deba@1187: #include deba@1187: deba@1187: #include deba@1187: deba@1187: class IntIntMap : public std::vector { deba@1187: public: deba@1187: typedef std::vector Parent; deba@1187: deba@1187: IntIntMap() : Parent() {} deba@1187: IntIntMap(int n) : Parent(n) {} deba@1187: IntIntMap(int n, int v) : Parent(n, v) {} deba@1187: deba@1187: void set(int key, int value) { deba@1187: Parent::operator[](key) = value; deba@1187: } deba@1187: }; deba@1187: deba@1187: deba@1187: template deba@1187: void heapSortTest(int n) { deba@1187: typedef _Heap Heap; deba@1187: IntIntMap map(n, -1); deba@1187: deba@1187: Heap heap(map); deba@1187: deba@1187: std::vector v(n); deba@1187: deba@1187: for (int i = 0; i < n; ++i) { deba@1187: v[i] = rand() % 1000; deba@1187: heap.push(i, v[i]); deba@1187: } deba@1187: std::sort(v.begin(), v.end()); deba@1187: for (int i = 0; i < n; ++i) { deba@1187: check(v[i] == heap.prio() ,"Wrong order in heap sort."); deba@1187: heap.pop(); deba@1187: } deba@1187: } deba@1187: deba@1206: template deba@1206: void heapIncreaseTest(int n) { deba@1206: typedef _Heap Heap; deba@1206: IntIntMap map(n, -1); deba@1206: deba@1206: Heap heap(map); deba@1206: deba@1206: std::vector v(n); deba@1206: deba@1206: for (int i = 0; i < n; ++i) { deba@1206: v[i] = rand() % 1000; deba@1206: heap.push(i, v[i]); deba@1206: } deba@1206: for (int i = 0; i < n; ++i) { deba@1206: v[i] += rand() % 1000; deba@1206: heap.increase(i, v[i]); deba@1206: } deba@1206: std::sort(v.begin(), v.end()); deba@1206: for (int i = 0; i < n; ++i) { deba@1206: check(v[i] == heap.prio() ,"Wrong order in heap increase test."); deba@1206: heap.pop(); deba@1206: } deba@1206: } deba@1206: deba@1206: deba@1206: deba@1187: template deba@1187: void dijkstraHeapTest(_Graph& graph, _LengthMap& length, deba@1187: typename _Graph::Node& start) { deba@1187: deba@1187: typedef _Heap Heap; deba@1187: typedef _Graph Graph; deba@1187: typedef _LengthMap LengthMap; deba@1187: deba@1187: typedef typename Graph::Node Node; deba@1187: typedef typename Graph::Edge Edge; deba@1187: typedef typename Graph::NodeIt NodeIt; deba@1187: typedef typename Graph::EdgeIt EdgeIt; deba@1187: deba@1745: typename Dijkstra::template DefStandardHeap:: deba@1728: Create dijkstra(graph, length); deba@1187: deba@1187: dijkstra.run(start); deba@1187: deba@1187: for(EdgeIt e(graph); e!=INVALID; ++e) { deba@1187: Node u=graph.source(e); deba@1187: Node v=graph.target(e); deba@1187: if (dijkstra.reached(u)) { deba@1187: check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e], deba@1728: "Error in a shortest path tree edge!"); deba@1187: } deba@1187: } deba@1187: deba@1187: for(NodeIt v(graph); v!=INVALID; ++v) { deba@1206: if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) { deba@1187: Edge e=dijkstra.pred(v); deba@1187: Node u=graph.source(e); deba@1187: check( dijkstra.dist(v) - dijkstra .dist(u) == length[e], deba@1187: "Error in a shortest path tree edge!"); deba@1187: } deba@1187: } deba@1187: deba@1187: }