1 /*=============================================================================
2 Copyright (c) 2010 Tim Blechmann
3
4 Use, modification and distribution is subject to the Boost Software
5 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7 =============================================================================*/
8
9 #include <iostream>
10 #include <iomanip>
11
12 #include "../../../boost/heap/fibonacci_heap.hpp"
13
14 using std::cout;
15 using std::endl;
16 using namespace boost::heap;
17
18 //[ basic_interface
19 // PriorityQueue is expected to be a max-heap of integer values
20 template <typename PriorityQueue>
basic_interface(void)21 void basic_interface(void)
22 {
23 PriorityQueue pq;
24
25 pq.push(2);
26 pq.push(3);
27 pq.push(1);
28
29 cout << "Priority Queue: popped elements" << endl;
30 cout << pq.top() << " "; // 3
31 pq.pop();
32 cout << pq.top() << " "; // 2
33 pq.pop();
34 cout << pq.top() << " "; // 1
35 pq.pop();
36 cout << endl;
37 }
38 //]
39
40 //[ iterator_interface
41 // PriorityQueue is expected to be a max-heap of integer values
42 template <typename PriorityQueue>
iterator_interface(void)43 void iterator_interface(void)
44 {
45 PriorityQueue pq;
46
47 pq.push(2);
48 pq.push(3);
49 pq.push(1);
50
51 typename PriorityQueue::iterator begin = pq.begin();
52 typename PriorityQueue::iterator end = pq.end();
53
54 cout << "Priority Queue: iteration" << endl;
55 for (typename PriorityQueue::iterator it = begin; it != end; ++it)
56 cout << *it << " "; // 1, 2, 3 in unspecified order
57 cout << endl;
58 }
59 //]
60
61 //[ ordered_iterator_interface
62 // PriorityQueue is expected to be a max-heap of integer values
63 template <typename PriorityQueue>
ordered_iterator_interface(void)64 void ordered_iterator_interface(void)
65 {
66 PriorityQueue pq;
67
68 pq.push(2);
69 pq.push(3);
70 pq.push(1);
71
72 typename PriorityQueue::ordered_iterator begin = pq.ordered_begin();
73 typename PriorityQueue::ordered_iterator end = pq.ordered_end();
74
75 cout << "Priority Queue: ordered iteration" << endl;
76 for (typename PriorityQueue::ordered_iterator it = begin; it != end; ++it)
77 cout << *it << " "; // 3, 2, 1 (i.e. 1, 2, 3 in heap order)
78 cout << endl;
79 }
80 //]
81
82
83 //[ merge_interface
84 // PriorityQueue is expected to be a max-heap of integer values
85 template <typename PriorityQueue>
merge_interface(void)86 void merge_interface(void)
87 {
88 PriorityQueue pq;
89
90 pq.push(3);
91 pq.push(5);
92 pq.push(1);
93
94 PriorityQueue pq2;
95
96 pq2.push(2);
97 pq2.push(4);
98 pq2.push(0);
99
100 pq.merge(pq2);
101
102 cout << "Priority Queue: merge" << endl;
103 cout << "first queue: ";
104 while (!pq.empty()) {
105 cout << pq.top() << " "; // 5 4 3 2 1 0
106 pq.pop();
107 }
108 cout << endl;
109
110 cout << "second queue: ";
111 while (!pq2.empty()) {
112 cout << pq2.top() << " "; // 4 2 0
113 pq2.pop();
114 }
115 cout << endl;
116 }
117 //]
118
119 //[ heap_merge_algorithm
120 // PriorityQueue is expected to be a max-heap of integer values
121 template <typename PriorityQueue>
heap_merge_algorithm(void)122 void heap_merge_algorithm(void)
123 {
124 PriorityQueue pq;
125
126 pq.push(3);
127 pq.push(5);
128 pq.push(1);
129
130 PriorityQueue pq2;
131
132 pq2.push(2);
133 pq2.push(4);
134 pq2.push(0);
135
136 boost::heap::heap_merge(pq, pq2);
137
138 cout << "Priority Queue: merge" << endl;
139 cout << "first queue: ";
140 while (!pq.empty()) {
141 cout << pq.top() << " "; // 5 4 3 2 1 0
142 pq.pop();
143 }
144 cout << endl;
145
146 cout << "second queue: ";
147 while (!pq2.empty()) {
148 cout << pq2.top() << " "; // 4 2 0
149 pq2.pop();
150 }
151 cout << endl;
152 }
153 //]
154
155 //[ mutable_interface
156 // PriorityQueue is expected to be a max-heap of integer values
157 template <typename PriorityQueue>
mutable_interface(void)158 void mutable_interface(void)
159 {
160 PriorityQueue pq;
161 typedef typename PriorityQueue::handle_type handle_t;
162
163 handle_t t3 = pq.push(3);
164 handle_t t5 = pq.push(5);
165 handle_t t1 = pq.push(1);
166
167 pq.update(t3, 4);
168 pq.increase(t5, 7);
169 pq.decrease(t1, 0);
170
171 cout << "Priority Queue: update" << endl;
172 while (!pq.empty()) {
173 cout << pq.top() << " "; // 7, 4, 0
174 pq.pop();
175 }
176 cout << endl;
177 }
178 //]
179
180 //[ mutable_fixup_interface
181 // PriorityQueue is expected to be a max-heap of integer values
182 template <typename PriorityQueue>
mutable_fixup_interface(void)183 void mutable_fixup_interface(void)
184 {
185 PriorityQueue pq;
186 typedef typename PriorityQueue::handle_type handle_t;
187
188 handle_t t3 = pq.push(3);
189 handle_t t5 = pq.push(5);
190 handle_t t1 = pq.push(1);
191
192 *t3 = 4;
193 pq.update(t3);
194
195 *t5 = 7;
196 pq.increase(t5);
197
198 *t1 = 0;
199 pq.decrease(t1);
200
201 cout << "Priority Queue: update with fixup" << endl;
202 while (!pq.empty()) {
203 cout << pq.top() << " "; // 7, 4, 0
204 pq.pop();
205 }
206 cout << endl;
207 }
208 //]
209
210 //[ mutable_interface_handle_in_value
211 struct heap_data
212 {
213 fibonacci_heap<heap_data>::handle_type handle;
214 int payload;
215
heap_dataheap_data216 heap_data(int i):
217 payload(i)
218 {}
219
operator <heap_data220 bool operator<(heap_data const & rhs) const
221 {
222 return payload < rhs.payload;
223 }
224 };
225
mutable_interface_handle_in_value(void)226 void mutable_interface_handle_in_value(void)
227 {
228 fibonacci_heap<heap_data> heap;
229 heap_data f(2);
230
231 fibonacci_heap<heap_data>::handle_type handle = heap.push(f);
232 (*handle).handle = handle; // store handle in node
233 }
234 //]
235
236
main(void)237 int main(void)
238 {
239 using boost::heap::fibonacci_heap;
240
241 cout << std::setw(2);
242
243 basic_interface<fibonacci_heap<int> >();
244 cout << endl;
245
246 iterator_interface<fibonacci_heap<int> >();
247 cout << endl;
248
249 ordered_iterator_interface<fibonacci_heap<int> >();
250 cout << endl;
251
252 merge_interface<fibonacci_heap<int> >();
253 cout << endl;
254
255 mutable_interface<fibonacci_heap<int> >();
256 cout << endl;
257
258 mutable_fixup_interface<fibonacci_heap<int> >();
259
260 mutable_interface_handle_in_value();
261 }
262