1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2009 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_FOURARY_HEAP_H |
|
20 #define LEMON_FOURARY_HEAP_H |
|
21 |
|
22 ///\ingroup heaps |
|
23 ///\file |
|
24 ///\brief Fourary heap implementation. |
|
25 |
|
26 #include <vector> |
|
27 #include <utility> |
|
28 #include <functional> |
|
29 |
|
30 namespace lemon { |
|
31 |
|
32 /// \ingroup heaps |
|
33 /// |
|
34 ///\brief Fourary heap data structure. |
|
35 /// |
|
36 /// This class implements the \e fourary \e heap data structure. |
|
37 /// It fully conforms to the \ref concepts::Heap "heap concept". |
|
38 /// |
|
39 /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap" |
|
40 /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap", |
|
41 /// but its nodes have at most four children, instead of two. |
|
42 /// |
|
43 /// \tparam PR Type of the priorities of the items. |
|
44 /// \tparam IM A read-writable item map with \c int values, used |
|
45 /// internally to handle the cross references. |
|
46 /// \tparam CMP A functor class for comparing the priorities. |
|
47 /// The default is \c std::less<PR>. |
|
48 /// |
|
49 ///\sa BinHeap |
|
50 ///\sa KaryHeap |
|
51 #ifdef DOXYGEN |
|
52 template <typename PR, typename IM, typename CMP> |
|
53 #else |
|
54 template <typename PR, typename IM, typename CMP = std::less<PR> > |
|
55 #endif |
|
56 class FouraryHeap { |
|
57 public: |
|
58 /// Type of the item-int map. |
|
59 typedef IM ItemIntMap; |
|
60 /// Type of the priorities. |
|
61 typedef PR Prio; |
|
62 /// Type of the items stored in the heap. |
|
63 typedef typename ItemIntMap::Key Item; |
|
64 /// Type of the item-priority pairs. |
|
65 typedef std::pair<Item,Prio> Pair; |
|
66 /// Functor type for comparing the priorities. |
|
67 typedef CMP Compare; |
|
68 |
|
69 /// \brief Type to represent the states of the items. |
|
70 /// |
|
71 /// Each item has a state associated to it. It can be "in heap", |
|
72 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
|
73 /// heap's point of view, but may be useful to the user. |
|
74 /// |
|
75 /// The item-int map must be initialized in such way that it assigns |
|
76 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
|
77 enum State { |
|
78 IN_HEAP = 0, ///< = 0. |
|
79 PRE_HEAP = -1, ///< = -1. |
|
80 POST_HEAP = -2 ///< = -2. |
|
81 }; |
|
82 |
|
83 private: |
|
84 std::vector<Pair> _data; |
|
85 Compare _comp; |
|
86 ItemIntMap &_iim; |
|
87 |
|
88 public: |
|
89 /// \brief Constructor. |
|
90 /// |
|
91 /// Constructor. |
|
92 /// \param map A map that assigns \c int values to the items. |
|
93 /// It is used internally to handle the cross references. |
|
94 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
|
95 explicit FouraryHeap(ItemIntMap &map) : _iim(map) {} |
|
96 |
|
97 /// \brief Constructor. |
|
98 /// |
|
99 /// Constructor. |
|
100 /// \param map A map that assigns \c int values to the items. |
|
101 /// It is used internally to handle the cross references. |
|
102 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
|
103 /// \param comp The function object used for comparing the priorities. |
|
104 FouraryHeap(ItemIntMap &map, const Compare &comp) |
|
105 : _iim(map), _comp(comp) {} |
|
106 |
|
107 /// \brief The number of items stored in the heap. |
|
108 /// |
|
109 /// This function returns the number of items stored in the heap. |
|
110 int size() const { return _data.size(); } |
|
111 |
|
112 /// \brief Check if the heap is empty. |
|
113 /// |
|
114 /// This function returns \c true if the heap is empty. |
|
115 bool empty() const { return _data.empty(); } |
|
116 |
|
117 /// \brief Make the heap empty. |
|
118 /// |
|
119 /// This functon makes the heap empty. |
|
120 /// It does not change the cross reference map. If you want to reuse |
|
121 /// a heap that is not surely empty, you should first clear it and |
|
122 /// then you should set the cross reference map to \c PRE_HEAP |
|
123 /// for each item. |
|
124 void clear() { _data.clear(); } |
|
125 |
|
126 private: |
|
127 static int parent(int i) { return (i-1)/4; } |
|
128 static int firstChild(int i) { return 4*i+1; } |
|
129 |
|
130 bool less(const Pair &p1, const Pair &p2) const { |
|
131 return _comp(p1.second, p2.second); |
|
132 } |
|
133 |
|
134 void bubbleUp(int hole, Pair p) { |
|
135 int par = parent(hole); |
|
136 while( hole>0 && less(p,_data[par]) ) { |
|
137 move(_data[par],hole); |
|
138 hole = par; |
|
139 par = parent(hole); |
|
140 } |
|
141 move(p, hole); |
|
142 } |
|
143 |
|
144 void bubbleDown(int hole, Pair p, int length) { |
|
145 if( length>1 ) { |
|
146 int child = firstChild(hole); |
|
147 while( child+3<length ) { |
|
148 int min=child; |
|
149 if( less(_data[++child], _data[min]) ) min=child; |
|
150 if( less(_data[++child], _data[min]) ) min=child; |
|
151 if( less(_data[++child], _data[min]) ) min=child; |
|
152 if( !less(_data[min], p) ) |
|
153 goto ok; |
|
154 move(_data[min], hole); |
|
155 hole = min; |
|
156 child = firstChild(hole); |
|
157 } |
|
158 if ( child<length ) { |
|
159 int min = child; |
|
160 if( ++child<length && less(_data[child], _data[min]) ) min=child; |
|
161 if( ++child<length && less(_data[child], _data[min]) ) min=child; |
|
162 if( less(_data[min], p) ) { |
|
163 move(_data[min], hole); |
|
164 hole = min; |
|
165 } |
|
166 } |
|
167 } |
|
168 ok: |
|
169 move(p, hole); |
|
170 } |
|
171 |
|
172 void move(const Pair &p, int i) { |
|
173 _data[i] = p; |
|
174 _iim.set(p.first, i); |
|
175 } |
|
176 |
|
177 public: |
|
178 /// \brief Insert a pair of item and priority into the heap. |
|
179 /// |
|
180 /// This function inserts \c p.first to the heap with priority |
|
181 /// \c p.second. |
|
182 /// \param p The pair to insert. |
|
183 /// \pre \c p.first must not be stored in the heap. |
|
184 void push(const Pair &p) { |
|
185 int n = _data.size(); |
|
186 _data.resize(n+1); |
|
187 bubbleUp(n, p); |
|
188 } |
|
189 |
|
190 /// \brief Insert an item into the heap with the given priority. |
|
191 /// |
|
192 /// This function inserts the given item into the heap with the |
|
193 /// given priority. |
|
194 /// \param i The item to insert. |
|
195 /// \param p The priority of the item. |
|
196 /// \pre \e i must not be stored in the heap. |
|
197 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } |
|
198 |
|
199 /// \brief Return the item having minimum priority. |
|
200 /// |
|
201 /// This function returns the item having minimum priority. |
|
202 /// \pre The heap must be non-empty. |
|
203 Item top() const { return _data[0].first; } |
|
204 |
|
205 /// \brief The minimum priority. |
|
206 /// |
|
207 /// This function returns the minimum priority. |
|
208 /// \pre The heap must be non-empty. |
|
209 Prio prio() const { return _data[0].second; } |
|
210 |
|
211 /// \brief Remove the item having minimum priority. |
|
212 /// |
|
213 /// This function removes the item having minimum priority. |
|
214 /// \pre The heap must be non-empty. |
|
215 void pop() { |
|
216 int n = _data.size()-1; |
|
217 _iim.set(_data[0].first, POST_HEAP); |
|
218 if (n>0) bubbleDown(0, _data[n], n); |
|
219 _data.pop_back(); |
|
220 } |
|
221 |
|
222 /// \brief Remove the given item from the heap. |
|
223 /// |
|
224 /// This function removes the given item from the heap if it is |
|
225 /// already stored. |
|
226 /// \param i The item to delete. |
|
227 /// \pre \e i must be in the heap. |
|
228 void erase(const Item &i) { |
|
229 int h = _iim[i]; |
|
230 int n = _data.size()-1; |
|
231 _iim.set(_data[h].first, POST_HEAP); |
|
232 if( h<n ) { |
|
233 if( less(_data[parent(h)], _data[n]) ) |
|
234 bubbleDown(h, _data[n], n); |
|
235 else |
|
236 bubbleUp(h, _data[n]); |
|
237 } |
|
238 _data.pop_back(); |
|
239 } |
|
240 |
|
241 /// \brief The priority of the given item. |
|
242 /// |
|
243 /// This function returns the priority of the given item. |
|
244 /// \param i The item. |
|
245 /// \pre \e i must be in the heap. |
|
246 Prio operator[](const Item &i) const { |
|
247 int idx = _iim[i]; |
|
248 return _data[idx].second; |
|
249 } |
|
250 |
|
251 /// \brief Set the priority of an item or insert it, if it is |
|
252 /// not stored in the heap. |
|
253 /// |
|
254 /// This method sets the priority of the given item if it is |
|
255 /// already stored in the heap. Otherwise it inserts the given |
|
256 /// item into the heap with the given priority. |
|
257 /// \param i The item. |
|
258 /// \param p The priority. |
|
259 void set(const Item &i, const Prio &p) { |
|
260 int idx = _iim[i]; |
|
261 if( idx < 0 ) |
|
262 push(i,p); |
|
263 else if( _comp(p, _data[idx].second) ) |
|
264 bubbleUp(idx, Pair(i,p)); |
|
265 else |
|
266 bubbleDown(idx, Pair(i,p), _data.size()); |
|
267 } |
|
268 |
|
269 /// \brief Decrease the priority of an item to the given value. |
|
270 /// |
|
271 /// This function decreases the priority of an item to the given value. |
|
272 /// \param i The item. |
|
273 /// \param p The priority. |
|
274 /// \pre \e i must be stored in the heap with priority at least \e p. |
|
275 void decrease(const Item &i, const Prio &p) { |
|
276 int idx = _iim[i]; |
|
277 bubbleUp(idx, Pair(i,p)); |
|
278 } |
|
279 |
|
280 /// \brief Increase the priority of an item to the given value. |
|
281 /// |
|
282 /// This function increases the priority of an item to the given value. |
|
283 /// \param i The item. |
|
284 /// \param p The priority. |
|
285 /// \pre \e i must be stored in the heap with priority at most \e p. |
|
286 void increase(const Item &i, const Prio &p) { |
|
287 int idx = _iim[i]; |
|
288 bubbleDown(idx, Pair(i,p), _data.size()); |
|
289 } |
|
290 |
|
291 /// \brief Return the state of an item. |
|
292 /// |
|
293 /// This method returns \c PRE_HEAP if the given item has never |
|
294 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
|
295 /// and \c POST_HEAP otherwise. |
|
296 /// In the latter case it is possible that the item will get back |
|
297 /// to the heap again. |
|
298 /// \param i The item. |
|
299 State state(const Item &i) const { |
|
300 int s = _iim[i]; |
|
301 if (s>=0) s=0; |
|
302 return State(s); |
|
303 } |
|
304 |
|
305 /// \brief Set the state of an item in the heap. |
|
306 /// |
|
307 /// This function sets the state of the given item in the heap. |
|
308 /// It can be used to manually clear the heap when it is important |
|
309 /// to achive better time complexity. |
|
310 /// \param i The item. |
|
311 /// \param st The state. It should not be \c IN_HEAP. |
|
312 void state(const Item& i, State st) { |
|
313 switch (st) { |
|
314 case POST_HEAP: |
|
315 case PRE_HEAP: |
|
316 if (state(i) == IN_HEAP) erase(i); |
|
317 _iim[i] = st; |
|
318 break; |
|
319 case IN_HEAP: |
|
320 break; |
|
321 } |
|
322 } |
|
323 |
|
324 /// \brief Replace an item in the heap. |
|
325 /// |
|
326 /// This function replaces item \c i with item \c j. |
|
327 /// Item \c i must be in the heap, while \c j must be out of the heap. |
|
328 /// After calling this method, item \c i will be out of the |
|
329 /// heap and \c j will be in the heap with the same prioriority |
|
330 /// as item \c i had before. |
|
331 void replace(const Item& i, const Item& j) { |
|
332 int idx = _iim[i]; |
|
333 _iim.set(i, _iim[j]); |
|
334 _iim.set(j, idx); |
|
335 _data[idx].first = j; |
|
336 } |
|
337 |
|
338 }; // class FouraryHeap |
|
339 |
|
340 } // namespace lemon |
|
341 |
|
342 #endif // LEMON_FOURARY_HEAP_H |
|