77 run(); |
77 run(); |
78 |
78 |
79 { |
79 { |
80 std::cerr << "Checking Bin Heap" << std::endl; |
80 std::cerr << "Checking Bin Heap" << std::endl; |
81 |
81 |
82 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap; |
82 typedef BinHeap<Prio, ItemIntMap> IntHeap; |
83 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
83 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
84 heapSortTest<IntHeap>(100); |
84 heapSortTest<IntHeap>(100); |
85 heapIncreaseTest<IntHeap>(100); |
85 heapIncreaseTest<IntHeap>(100); |
86 |
86 |
87 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
87 typedef FibHeap<Prio, Graph::NodeMap<int> > NodeHeap; |
88 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
88 checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>(); |
89 Timer timer; |
89 Timer timer; |
90 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
90 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
91 std::cout << timer << std::endl; |
91 std::cout << timer << std::endl; |
92 } |
92 } |
93 { |
93 { |
94 std::cerr << "Checking Fib Heap" << std::endl; |
94 std::cerr << "Checking Fib Heap" << std::endl; |
95 |
95 |
96 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap; |
96 typedef FibHeap<Prio, ItemIntMap> IntHeap; |
97 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
97 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
98 heapSortTest<IntHeap>(100); |
98 heapSortTest<IntHeap>(100); |
99 heapIncreaseTest<IntHeap>(100); |
99 heapIncreaseTest<IntHeap>(100); |
100 |
100 |
101 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
101 typedef FibHeap<Prio, Graph::NodeMap<int> > NodeHeap; |
102 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
102 checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>(); |
103 Timer timer; |
103 Timer timer; |
104 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
104 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
105 std::cout << timer << std::endl; |
105 std::cout << timer << std::endl; |
106 } |
106 } |
107 { |
107 { |
108 std::cerr << "Checking Radix Heap" << std::endl; |
108 std::cerr << "Checking Radix Heap" << std::endl; |
109 |
109 |
110 typedef RadixHeap<Item, ItemIntMap> IntHeap; |
110 typedef RadixHeap<ItemIntMap> IntHeap; |
111 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
111 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
112 heapSortTest<IntHeap>(100); |
112 heapSortTest<IntHeap>(100); |
113 heapIncreaseTest<IntHeap>(100); |
113 heapIncreaseTest<IntHeap>(100); |
114 |
114 |
115 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap; |
115 typedef RadixHeap<Graph::NodeMap<int> > NodeHeap; |
116 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
116 checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>(); |
117 Timer timer; |
117 Timer timer; |
118 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
118 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
119 std::cout << timer << std::endl; |
119 std::cout << timer << std::endl; |
120 } |
120 } |
121 |
121 |
122 { |
122 { |
123 std::cerr << "Checking Bucket Heap" << std::endl; |
123 std::cerr << "Checking Bucket Heap" << std::endl; |
124 |
124 |
125 typedef BucketHeap<Item, ItemIntMap> IntHeap; |
125 typedef BucketHeap<ItemIntMap> IntHeap; |
126 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
126 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); |
127 heapSortTest<IntHeap>(100); |
127 heapSortTest<IntHeap>(100); |
128 heapIncreaseTest<IntHeap>(100); |
128 heapIncreaseTest<IntHeap>(100); |
129 |
129 |
130 typedef BucketHeap<Node, Graph::NodeMap<int> > NodeHeap; |
130 typedef BucketHeap<Graph::NodeMap<int> > NodeHeap; |
131 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
131 checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>(); |
132 Timer timer; |
132 Timer timer; |
133 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
133 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
134 std::cout << timer << std::endl; |
134 std::cout << timer << std::endl; |
135 } |
135 } |
136 |
136 |