19 |
20 |
20 #include "heap_test.h" |
21 #include "heap_test.h" |
21 |
22 |
22 |
23 |
23 using namespace lemon; |
24 using namespace lemon; |
|
25 using namespace lemon::concept; |
24 |
26 |
25 template <typename Item, typename Prio, typename ItemIntMap> |
|
26 class HeapConcept { |
|
27 public: |
|
28 |
|
29 template <typename _Heap> |
|
30 struct Constraints { |
|
31 public: |
|
32 |
|
33 void constraints() { |
|
34 Item item; |
|
35 Prio prio; |
|
36 |
|
37 ignore_unused_variable_warning(item); |
|
38 ignore_unused_variable_warning(prio); |
|
39 |
|
40 typedef typename _Heap::state_enum state_enum; |
|
41 state_enum state; |
|
42 |
|
43 ignore_unused_variable_warning(state); |
|
44 |
|
45 _Heap heap1 = _Heap(map); |
|
46 |
|
47 ignore_unused_variable_warning(heap1); |
|
48 |
|
49 heap.push(item, prio); |
|
50 |
|
51 prio = heap.prio(); |
|
52 item = heap.top(); |
|
53 |
|
54 heap.pop(); |
|
55 |
|
56 heap.set(item, prio); |
|
57 heap.decrease(item, prio); |
|
58 heap.increase(item, prio); |
|
59 prio = heap[item]; |
|
60 |
|
61 heap.erase(item); |
|
62 |
|
63 state = heap.state(item); |
|
64 |
|
65 state = _Heap::PRE_HEAP; |
|
66 state = _Heap::IN_HEAP; |
|
67 state = _Heap::POST_HEAP; |
|
68 } |
|
69 |
|
70 _Heap& heap; |
|
71 ItemIntMap& map; |
|
72 |
|
73 Constraints() : heap(0), map(0) {} |
|
74 }; |
|
75 }; |
|
76 |
27 |
77 int main() { |
28 int main() { |
78 |
29 |
79 typedef int Item; |
30 typedef int Item; |
80 typedef int Prio; |
31 typedef int Prio; |
106 |
57 |
107 { |
58 { |
108 std::cerr << "Checking Bin Heap" << std::endl; |
59 std::cerr << "Checking Bin Heap" << std::endl; |
109 |
60 |
110 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap; |
61 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap; |
111 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>(); |
62 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
112 heapSortTest<IntHeap>(100); |
63 heapSortTest<IntHeap>(100); |
113 heapIncreaseTest<IntHeap>(100); |
64 heapIncreaseTest<IntHeap>(100); |
114 |
65 |
115 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
66 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
116 checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
67 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
117 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
68 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
118 } |
69 } |
119 { |
70 { |
120 std::cerr << "Checking Fib Heap" << std::endl; |
71 std::cerr << "Checking Fib Heap" << std::endl; |
121 |
72 |
122 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap; |
73 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap; |
123 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>(); |
74 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
124 heapSortTest<IntHeap>(100); |
75 heapSortTest<IntHeap>(100); |
125 heapIncreaseTest<IntHeap>(100); |
76 heapIncreaseTest<IntHeap>(100); |
126 |
77 |
127 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
78 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap; |
128 checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
79 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
129 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
80 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
130 } |
81 } |
131 { |
82 { |
132 std::cerr << "Checking Radix Heap" << std::endl; |
83 std::cerr << "Checking Radix Heap" << std::endl; |
133 |
84 |
134 typedef RadixHeap<Item, ItemIntMap> IntHeap; |
85 typedef RadixHeap<Item, ItemIntMap> IntHeap; |
135 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>(); |
86 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>(); |
136 heapSortTest<IntHeap>(100); |
87 heapSortTest<IntHeap>(100); |
137 heapIncreaseTest<IntHeap>(100); |
88 heapIncreaseTest<IntHeap>(100); |
138 |
89 |
139 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap; |
90 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap; |
140 checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
91 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>(); |
141 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
92 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start); |
142 } |
93 } |
143 |
94 |
144 std::cout << __FILE__ ": All tests passed.\n"; |
95 std::cout << __FILE__ ": All tests passed.\n"; |
145 |
96 |