deba@681
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
deba@681
|
2 |
*
|
deba@681
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
deba@681
|
4 |
*
|
deba@681
|
5 |
* Copyright (C) 2003-2009
|
deba@681
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@681
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@681
|
8 |
*
|
deba@681
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@681
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@681
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@681
|
12 |
*
|
deba@681
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@681
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@681
|
15 |
* purpose.
|
deba@681
|
16 |
*
|
deba@681
|
17 |
*/
|
deba@681
|
18 |
|
deba@681
|
19 |
#ifndef LEMON_BUCKET_HEAP_H
|
deba@681
|
20 |
#define LEMON_BUCKET_HEAP_H
|
deba@681
|
21 |
|
deba@681
|
22 |
///\ingroup auxdat
|
deba@681
|
23 |
///\file
|
deba@681
|
24 |
///\brief Bucket Heap implementation.
|
deba@681
|
25 |
|
deba@681
|
26 |
#include <vector>
|
deba@681
|
27 |
#include <utility>
|
deba@681
|
28 |
#include <functional>
|
deba@681
|
29 |
|
deba@681
|
30 |
namespace lemon {
|
deba@681
|
31 |
|
deba@682
|
32 |
namespace _bucket_heap_bits {
|
deba@682
|
33 |
|
deba@682
|
34 |
template <bool minimize>
|
deba@682
|
35 |
struct DirectionTraits {
|
deba@682
|
36 |
static bool less(int left, int right) {
|
deba@682
|
37 |
return left < right;
|
deba@682
|
38 |
}
|
deba@682
|
39 |
static void increase(int& value) {
|
deba@682
|
40 |
++value;
|
deba@682
|
41 |
}
|
deba@682
|
42 |
};
|
deba@682
|
43 |
|
deba@682
|
44 |
template <>
|
deba@682
|
45 |
struct DirectionTraits<false> {
|
deba@682
|
46 |
static bool less(int left, int right) {
|
deba@682
|
47 |
return left > right;
|
deba@682
|
48 |
}
|
deba@682
|
49 |
static void increase(int& value) {
|
deba@682
|
50 |
--value;
|
deba@682
|
51 |
}
|
deba@682
|
52 |
};
|
deba@682
|
53 |
|
deba@682
|
54 |
}
|
deba@682
|
55 |
|
deba@681
|
56 |
/// \ingroup auxdat
|
deba@681
|
57 |
///
|
deba@681
|
58 |
/// \brief A Bucket Heap implementation.
|
deba@681
|
59 |
///
|
deba@681
|
60 |
/// This class implements the \e bucket \e heap data structure. A \e heap
|
deba@681
|
61 |
/// is a data structure for storing items with specified values called \e
|
deba@681
|
62 |
/// priorities in such a way that finding the item with minimum priority is
|
deba@681
|
63 |
/// efficient. The bucket heap is very simple implementation, it can store
|
deba@681
|
64 |
/// only integer priorities and it stores for each priority in the
|
deba@681
|
65 |
/// \f$ [0..C) \f$ range a list of items. So it should be used only when
|
deba@681
|
66 |
/// the priorities are small. It is not intended to use as dijkstra heap.
|
deba@681
|
67 |
///
|
deba@681
|
68 |
/// \param _ItemIntMap A read and writable Item int map, used internally
|
deba@681
|
69 |
/// to handle the cross references.
|
deba@681
|
70 |
/// \param minimize If the given parameter is true then the heap gives back
|
deba@681
|
71 |
/// the lowest priority.
|
deba@682
|
72 |
template <typename _ItemIntMap, bool minimize = true>
|
deba@681
|
73 |
class BucketHeap {
|
deba@681
|
74 |
|
deba@681
|
75 |
public:
|
deba@681
|
76 |
/// \e
|
deba@681
|
77 |
typedef typename _ItemIntMap::Key Item;
|
deba@681
|
78 |
/// \e
|
deba@681
|
79 |
typedef int Prio;
|
deba@681
|
80 |
/// \e
|
deba@681
|
81 |
typedef std::pair<Item, Prio> Pair;
|
deba@681
|
82 |
/// \e
|
deba@681
|
83 |
typedef _ItemIntMap ItemIntMap;
|
deba@681
|
84 |
|
deba@682
|
85 |
private:
|
deba@682
|
86 |
|
deba@682
|
87 |
typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
|
deba@682
|
88 |
|
deba@682
|
89 |
public:
|
deba@682
|
90 |
|
deba@681
|
91 |
/// \brief Type to represent the items states.
|
deba@681
|
92 |
///
|
deba@681
|
93 |
/// Each Item element have a state associated to it. It may be "in heap",
|
deba@681
|
94 |
/// "pre heap" or "post heap". The latter two are indifferent from the
|
deba@681
|
95 |
/// heap's point of view, but may be useful to the user.
|
deba@681
|
96 |
///
|
deba@681
|
97 |
/// The ItemIntMap \e should be initialized in such way that it maps
|
deba@681
|
98 |
/// PRE_HEAP (-1) to any element to be put in the heap...
|
deba@681
|
99 |
enum State {
|
deba@681
|
100 |
IN_HEAP = 0,
|
deba@681
|
101 |
PRE_HEAP = -1,
|
deba@681
|
102 |
POST_HEAP = -2
|
deba@681
|
103 |
};
|
deba@681
|
104 |
|
deba@681
|
105 |
public:
|
deba@681
|
106 |
/// \brief The constructor.
|
deba@681
|
107 |
///
|
deba@681
|
108 |
/// The constructor.
|
deba@681
|
109 |
/// \param _index should be given to the constructor, since it is used
|
deba@681
|
110 |
/// internally to handle the cross references. The value of the map
|
deba@681
|
111 |
/// should be PRE_HEAP (-1) for each element.
|
deba@681
|
112 |
explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
|
deba@681
|
113 |
|
deba@681
|
114 |
/// The number of items stored in the heap.
|
deba@681
|
115 |
///
|
deba@681
|
116 |
/// \brief Returns the number of items stored in the heap.
|
deba@681
|
117 |
int size() const { return data.size(); }
|
deba@681
|
118 |
|
deba@681
|
119 |
/// \brief Checks if the heap stores no items.
|
deba@681
|
120 |
///
|
deba@681
|
121 |
/// Returns \c true if and only if the heap stores no items.
|
deba@681
|
122 |
bool empty() const { return data.empty(); }
|
deba@681
|
123 |
|
deba@681
|
124 |
/// \brief Make empty this heap.
|
deba@681
|
125 |
///
|
deba@681
|
126 |
/// Make empty this heap. It does not change the cross reference
|
deba@681
|
127 |
/// map. If you want to reuse a heap what is not surely empty you
|
deba@681
|
128 |
/// should first clear the heap and after that you should set the
|
deba@681
|
129 |
/// cross reference map for each item to \c PRE_HEAP.
|
deba@681
|
130 |
void clear() {
|
deba@681
|
131 |
data.clear(); first.clear(); minimal = 0;
|
deba@681
|
132 |
}
|
deba@681
|
133 |
|
deba@681
|
134 |
private:
|
deba@681
|
135 |
|
deba@681
|
136 |
void relocate_last(int idx) {
|
deba@681
|
137 |
if (idx + 1 < int(data.size())) {
|
deba@681
|
138 |
data[idx] = data.back();
|
deba@681
|
139 |
if (data[idx].prev != -1) {
|
deba@681
|
140 |
data[data[idx].prev].next = idx;
|
deba@681
|
141 |
} else {
|
deba@681
|
142 |
first[data[idx].value] = idx;
|
deba@681
|
143 |
}
|
deba@681
|
144 |
if (data[idx].next != -1) {
|
deba@681
|
145 |
data[data[idx].next].prev = idx;
|
deba@681
|
146 |
}
|
deba@681
|
147 |
index[data[idx].item] = idx;
|
deba@681
|
148 |
}
|
deba@681
|
149 |
data.pop_back();
|
deba@681
|
150 |
}
|
deba@681
|
151 |
|
deba@681
|
152 |
void unlace(int idx) {
|
deba@681
|
153 |
if (data[idx].prev != -1) {
|
deba@681
|
154 |
data[data[idx].prev].next = data[idx].next;
|
deba@681
|
155 |
} else {
|
deba@681
|
156 |
first[data[idx].value] = data[idx].next;
|
deba@681
|
157 |
}
|
deba@681
|
158 |
if (data[idx].next != -1) {
|
deba@681
|
159 |
data[data[idx].next].prev = data[idx].prev;
|
deba@681
|
160 |
}
|
deba@681
|
161 |
}
|
deba@681
|
162 |
|
deba@681
|
163 |
void lace(int idx) {
|
deba@681
|
164 |
if (int(first.size()) <= data[idx].value) {
|
deba@681
|
165 |
first.resize(data[idx].value + 1, -1);
|
deba@681
|
166 |
}
|
deba@681
|
167 |
data[idx].next = first[data[idx].value];
|
deba@681
|
168 |
if (data[idx].next != -1) {
|
deba@681
|
169 |
data[data[idx].next].prev = idx;
|
deba@681
|
170 |
}
|
deba@681
|
171 |
first[data[idx].value] = idx;
|
deba@681
|
172 |
data[idx].prev = -1;
|
deba@681
|
173 |
}
|
deba@681
|
174 |
|
deba@681
|
175 |
public:
|
deba@681
|
176 |
/// \brief Insert a pair of item and priority into the heap.
|
deba@681
|
177 |
///
|
deba@681
|
178 |
/// Adds \c p.first to the heap with priority \c p.second.
|
deba@681
|
179 |
/// \param p The pair to insert.
|
deba@681
|
180 |
void push(const Pair& p) {
|
deba@681
|
181 |
push(p.first, p.second);
|
deba@681
|
182 |
}
|
deba@681
|
183 |
|
deba@681
|
184 |
/// \brief Insert an item into the heap with the given priority.
|
deba@681
|
185 |
///
|
deba@681
|
186 |
/// Adds \c i to the heap with priority \c p.
|
deba@681
|
187 |
/// \param i The item to insert.
|
deba@681
|
188 |
/// \param p The priority of the item.
|
deba@681
|
189 |
void push(const Item &i, const Prio &p) {
|
deba@681
|
190 |
int idx = data.size();
|
deba@681
|
191 |
index[i] = idx;
|
deba@681
|
192 |
data.push_back(BucketItem(i, p));
|
deba@681
|
193 |
lace(idx);
|
deba@682
|
194 |
if (Direction::less(p, minimal)) {
|
deba@681
|
195 |
minimal = p;
|
deba@681
|
196 |
}
|
deba@681
|
197 |
}
|
deba@681
|
198 |
|
deba@681
|
199 |
/// \brief Returns the item with minimum priority.
|
deba@681
|
200 |
///
|
deba@681
|
201 |
/// This method returns the item with minimum priority.
|
deba@681
|
202 |
/// \pre The heap must be nonempty.
|
deba@681
|
203 |
Item top() const {
|
deba@681
|
204 |
while (first[minimal] == -1) {
|
deba@682
|
205 |
Direction::increase(minimal);
|
deba@681
|
206 |
}
|
deba@681
|
207 |
return data[first[minimal]].item;
|
deba@681
|
208 |
}
|
deba@681
|
209 |
|
deba@681
|
210 |
/// \brief Returns the minimum priority.
|
deba@681
|
211 |
///
|
deba@681
|
212 |
/// It returns the minimum priority.
|
deba@681
|
213 |
/// \pre The heap must be nonempty.
|
deba@681
|
214 |
Prio prio() const {
|
deba@681
|
215 |
while (first[minimal] == -1) {
|
deba@682
|
216 |
Direction::increase(minimal);
|
deba@681
|
217 |
}
|
deba@681
|
218 |
return minimal;
|
deba@681
|
219 |
}
|
deba@681
|
220 |
|
deba@681
|
221 |
/// \brief Deletes the item with minimum priority.
|
deba@681
|
222 |
///
|
deba@681
|
223 |
/// This method deletes the item with minimum priority from the heap.
|
deba@681
|
224 |
/// \pre The heap must be non-empty.
|
deba@681
|
225 |
void pop() {
|
deba@681
|
226 |
while (first[minimal] == -1) {
|
deba@682
|
227 |
Direction::increase(minimal);
|
deba@681
|
228 |
}
|
deba@681
|
229 |
int idx = first[minimal];
|
deba@681
|
230 |
index[data[idx].item] = -2;
|
deba@681
|
231 |
unlace(idx);
|
deba@681
|
232 |
relocate_last(idx);
|
deba@681
|
233 |
}
|
deba@681
|
234 |
|
deba@681
|
235 |
/// \brief Deletes \c i from the heap.
|
deba@681
|
236 |
///
|
deba@681
|
237 |
/// This method deletes item \c i from the heap, if \c i was
|
deba@681
|
238 |
/// already stored in the heap.
|
deba@681
|
239 |
/// \param i The item to erase.
|
deba@681
|
240 |
void erase(const Item &i) {
|
deba@681
|
241 |
int idx = index[i];
|
deba@681
|
242 |
index[data[idx].item] = -2;
|
deba@681
|
243 |
unlace(idx);
|
deba@681
|
244 |
relocate_last(idx);
|
deba@681
|
245 |
}
|
deba@681
|
246 |
|
deba@681
|
247 |
|
deba@681
|
248 |
/// \brief Returns the priority of \c i.
|
deba@681
|
249 |
///
|
deba@681
|
250 |
/// This function returns the priority of item \c i.
|
deba@681
|
251 |
/// \pre \c i must be in the heap.
|
deba@681
|
252 |
/// \param i The item.
|
deba@681
|
253 |
Prio operator[](const Item &i) const {
|
deba@681
|
254 |
int idx = index[i];
|
deba@681
|
255 |
return data[idx].value;
|
deba@681
|
256 |
}
|
deba@681
|
257 |
|
deba@681
|
258 |
/// \brief \c i gets to the heap with priority \c p independently
|
deba@681
|
259 |
/// if \c i was already there.
|
deba@681
|
260 |
///
|
deba@681
|
261 |
/// This method calls \ref push(\c i, \c p) if \c i is not stored
|
deba@681
|
262 |
/// in the heap and sets the priority of \c i to \c p otherwise.
|
deba@681
|
263 |
/// \param i The item.
|
deba@681
|
264 |
/// \param p The priority.
|
deba@681
|
265 |
void set(const Item &i, const Prio &p) {
|
deba@681
|
266 |
int idx = index[i];
|
deba@681
|
267 |
if (idx < 0) {
|
deba@682
|
268 |
push(i, p);
|
deba@682
|
269 |
} else if (Direction::less(p, data[idx].value)) {
|
deba@682
|
270 |
decrease(i, p);
|
deba@682
|
271 |
} else {
|
deba@681
|
272 |
increase(i, p);
|
deba@681
|
273 |
}
|
deba@681
|
274 |
}
|
deba@681
|
275 |
|
deba@681
|
276 |
/// \brief Decreases the priority of \c i to \c p.
|
deba@681
|
277 |
///
|
deba@681
|
278 |
/// This method decreases the priority of item \c i to \c p.
|
deba@681
|
279 |
/// \pre \c i must be stored in the heap with priority at least \c
|
deba@681
|
280 |
/// p relative to \c Compare.
|
deba@681
|
281 |
/// \param i The item.
|
deba@681
|
282 |
/// \param p The priority.
|
deba@681
|
283 |
void decrease(const Item &i, const Prio &p) {
|
deba@681
|
284 |
int idx = index[i];
|
deba@681
|
285 |
unlace(idx);
|
deba@681
|
286 |
data[idx].value = p;
|
deba@682
|
287 |
if (Direction::less(p, minimal)) {
|
deba@681
|
288 |
minimal = p;
|
deba@681
|
289 |
}
|
deba@681
|
290 |
lace(idx);
|
deba@681
|
291 |
}
|
deba@681
|
292 |
|
deba@681
|
293 |
/// \brief Increases the priority of \c i to \c p.
|
deba@681
|
294 |
///
|
deba@681
|
295 |
/// This method sets the priority of item \c i to \c p.
|
deba@681
|
296 |
/// \pre \c i must be stored in the heap with priority at most \c
|
deba@681
|
297 |
/// p relative to \c Compare.
|
deba@681
|
298 |
/// \param i The item.
|
deba@681
|
299 |
/// \param p The priority.
|
deba@681
|
300 |
void increase(const Item &i, const Prio &p) {
|
deba@681
|
301 |
int idx = index[i];
|
deba@681
|
302 |
unlace(idx);
|
deba@681
|
303 |
data[idx].value = p;
|
deba@681
|
304 |
lace(idx);
|
deba@681
|
305 |
}
|
deba@681
|
306 |
|
deba@681
|
307 |
/// \brief Returns if \c item is in, has already been in, or has
|
deba@681
|
308 |
/// never been in the heap.
|
deba@681
|
309 |
///
|
deba@681
|
310 |
/// This method returns PRE_HEAP if \c item has never been in the
|
deba@681
|
311 |
/// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
|
deba@681
|
312 |
/// otherwise. In the latter case it is possible that \c item will
|
deba@681
|
313 |
/// get back to the heap again.
|
deba@681
|
314 |
/// \param i The item.
|
deba@681
|
315 |
State state(const Item &i) const {
|
deba@681
|
316 |
int idx = index[i];
|
deba@681
|
317 |
if (idx >= 0) idx = 0;
|
deba@681
|
318 |
return State(idx);
|
deba@681
|
319 |
}
|
deba@681
|
320 |
|
deba@681
|
321 |
/// \brief Sets the state of the \c item in the heap.
|
deba@681
|
322 |
///
|
deba@681
|
323 |
/// Sets the state of the \c item in the heap. It can be used to
|
deba@681
|
324 |
/// manually clear the heap when it is important to achive the
|
deba@681
|
325 |
/// better time complexity.
|
deba@681
|
326 |
/// \param i The item.
|
deba@681
|
327 |
/// \param st The state. It should not be \c IN_HEAP.
|
deba@681
|
328 |
void state(const Item& i, State st) {
|
deba@681
|
329 |
switch (st) {
|
deba@681
|
330 |
case POST_HEAP:
|
deba@681
|
331 |
case PRE_HEAP:
|
deba@681
|
332 |
if (state(i) == IN_HEAP) {
|
deba@681
|
333 |
erase(i);
|
deba@681
|
334 |
}
|
deba@681
|
335 |
index[i] = st;
|
deba@681
|
336 |
break;
|
deba@681
|
337 |
case IN_HEAP:
|
deba@681
|
338 |
break;
|
deba@681
|
339 |
}
|
deba@681
|
340 |
}
|
deba@681
|
341 |
|
deba@681
|
342 |
private:
|
deba@681
|
343 |
|
deba@681
|
344 |
struct BucketItem {
|
deba@681
|
345 |
BucketItem(const Item& _item, int _value)
|
deba@681
|
346 |
: item(_item), value(_value) {}
|
deba@681
|
347 |
|
deba@681
|
348 |
Item item;
|
deba@681
|
349 |
int value;
|
deba@681
|
350 |
|
deba@681
|
351 |
int prev, next;
|
deba@681
|
352 |
};
|
deba@681
|
353 |
|
deba@681
|
354 |
ItemIntMap& index;
|
deba@681
|
355 |
std::vector<int> first;
|
deba@681
|
356 |
std::vector<BucketItem> data;
|
deba@681
|
357 |
mutable int minimal;
|
deba@681
|
358 |
|
deba@681
|
359 |
}; // class BucketHeap
|
deba@681
|
360 |
|
deba@681
|
361 |
/// \ingroup auxdat
|
deba@681
|
362 |
///
|
deba@681
|
363 |
/// \brief A Simplified Bucket Heap implementation.
|
deba@681
|
364 |
///
|
deba@681
|
365 |
/// This class implements a simplified \e bucket \e heap data
|
deba@681
|
366 |
/// structure. It does not provide some functionality but it faster
|
deba@681
|
367 |
/// and simplier data structure than the BucketHeap. The main
|
deba@681
|
368 |
/// difference is that the BucketHeap stores for every key a double
|
deba@681
|
369 |
/// linked list while this class stores just simple lists. In the
|
deba@682
|
370 |
/// other way it does not support erasing each elements just the
|
deba@681
|
371 |
/// minimal and it does not supports key increasing, decreasing.
|
deba@681
|
372 |
///
|
deba@681
|
373 |
/// \param _ItemIntMap A read and writable Item int map, used internally
|
deba@681
|
374 |
/// to handle the cross references.
|
deba@681
|
375 |
/// \param minimize If the given parameter is true then the heap gives back
|
deba@681
|
376 |
/// the lowest priority.
|
deba@681
|
377 |
///
|
deba@681
|
378 |
/// \sa BucketHeap
|
deba@681
|
379 |
template <typename _ItemIntMap, bool minimize = true >
|
deba@681
|
380 |
class SimpleBucketHeap {
|
deba@681
|
381 |
|
deba@681
|
382 |
public:
|
deba@681
|
383 |
typedef typename _ItemIntMap::Key Item;
|
deba@681
|
384 |
typedef int Prio;
|
deba@681
|
385 |
typedef std::pair<Item, Prio> Pair;
|
deba@681
|
386 |
typedef _ItemIntMap ItemIntMap;
|
deba@681
|
387 |
|
deba@682
|
388 |
private:
|
deba@682
|
389 |
|
deba@682
|
390 |
typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
|
deba@682
|
391 |
|
deba@682
|
392 |
public:
|
deba@682
|
393 |
|
deba@681
|
394 |
/// \brief Type to represent the items states.
|
deba@681
|
395 |
///
|
deba@681
|
396 |
/// Each Item element have a state associated to it. It may be "in heap",
|
deba@681
|
397 |
/// "pre heap" or "post heap". The latter two are indifferent from the
|
deba@681
|
398 |
/// heap's point of view, but may be useful to the user.
|
deba@681
|
399 |
///
|
deba@681
|
400 |
/// The ItemIntMap \e should be initialized in such way that it maps
|
deba@681
|
401 |
/// PRE_HEAP (-1) to any element to be put in the heap...
|
deba@681
|
402 |
enum State {
|
deba@681
|
403 |
IN_HEAP = 0,
|
deba@681
|
404 |
PRE_HEAP = -1,
|
deba@681
|
405 |
POST_HEAP = -2
|
deba@681
|
406 |
};
|
deba@681
|
407 |
|
deba@681
|
408 |
public:
|
deba@681
|
409 |
|
deba@681
|
410 |
/// \brief The constructor.
|
deba@681
|
411 |
///
|
deba@681
|
412 |
/// The constructor.
|
deba@681
|
413 |
/// \param _index should be given to the constructor, since it is used
|
deba@681
|
414 |
/// internally to handle the cross references. The value of the map
|
deba@681
|
415 |
/// should be PRE_HEAP (-1) for each element.
|
deba@681
|
416 |
explicit SimpleBucketHeap(ItemIntMap &_index)
|
deba@681
|
417 |
: index(_index), free(-1), num(0), minimal(0) {}
|
deba@681
|
418 |
|
deba@681
|
419 |
/// \brief Returns the number of items stored in the heap.
|
deba@681
|
420 |
///
|
deba@681
|
421 |
/// The number of items stored in the heap.
|
deba@681
|
422 |
int size() const { return num; }
|
deba@681
|
423 |
|
deba@681
|
424 |
/// \brief Checks if the heap stores no items.
|
deba@681
|
425 |
///
|
deba@681
|
426 |
/// Returns \c true if and only if the heap stores no items.
|
deba@681
|
427 |
bool empty() const { return num == 0; }
|
deba@681
|
428 |
|
deba@681
|
429 |
/// \brief Make empty this heap.
|
deba@681
|
430 |
///
|
deba@681
|
431 |
/// Make empty this heap. It does not change the cross reference
|
deba@681
|
432 |
/// map. If you want to reuse a heap what is not surely empty you
|
deba@681
|
433 |
/// should first clear the heap and after that you should set the
|
deba@681
|
434 |
/// cross reference map for each item to \c PRE_HEAP.
|
deba@681
|
435 |
void clear() {
|
deba@681
|
436 |
data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
|
deba@681
|
437 |
}
|
deba@681
|
438 |
|
deba@681
|
439 |
/// \brief Insert a pair of item and priority into the heap.
|
deba@681
|
440 |
///
|
deba@681
|
441 |
/// Adds \c p.first to the heap with priority \c p.second.
|
deba@681
|
442 |
/// \param p The pair to insert.
|
deba@681
|
443 |
void push(const Pair& p) {
|
deba@681
|
444 |
push(p.first, p.second);
|
deba@681
|
445 |
}
|
deba@681
|
446 |
|
deba@681
|
447 |
/// \brief Insert an item into the heap with the given priority.
|
deba@681
|
448 |
///
|
deba@681
|
449 |
/// Adds \c i to the heap with priority \c p.
|
deba@681
|
450 |
/// \param i The item to insert.
|
deba@681
|
451 |
/// \param p The priority of the item.
|
deba@681
|
452 |
void push(const Item &i, const Prio &p) {
|
deba@681
|
453 |
int idx;
|
deba@681
|
454 |
if (free == -1) {
|
deba@681
|
455 |
idx = data.size();
|
deba@681
|
456 |
data.push_back(BucketItem(i));
|
deba@681
|
457 |
} else {
|
deba@681
|
458 |
idx = free;
|
deba@681
|
459 |
free = data[idx].next;
|
deba@681
|
460 |
data[idx].item = i;
|
deba@681
|
461 |
}
|
deba@681
|
462 |
index[i] = idx;
|
deba@681
|
463 |
if (p >= int(first.size())) first.resize(p + 1, -1);
|
deba@681
|
464 |
data[idx].next = first[p];
|
deba@681
|
465 |
first[p] = idx;
|
deba@682
|
466 |
if (Direction::less(p, minimal)) {
|
deba@681
|
467 |
minimal = p;
|
deba@681
|
468 |
}
|
deba@681
|
469 |
++num;
|
deba@681
|
470 |
}
|
deba@681
|
471 |
|
deba@681
|
472 |
/// \brief Returns the item with minimum priority.
|
deba@681
|
473 |
///
|
deba@681
|
474 |
/// This method returns the item with minimum priority.
|
deba@681
|
475 |
/// \pre The heap must be nonempty.
|
deba@681
|
476 |
Item top() const {
|
deba@681
|
477 |
while (first[minimal] == -1) {
|
deba@682
|
478 |
Direction::increase(minimal);
|
deba@681
|
479 |
}
|
deba@681
|
480 |
return data[first[minimal]].item;
|
deba@681
|
481 |
}
|
deba@681
|
482 |
|
deba@681
|
483 |
/// \brief Returns the minimum priority.
|
deba@681
|
484 |
///
|
deba@681
|
485 |
/// It returns the minimum priority.
|
deba@681
|
486 |
/// \pre The heap must be nonempty.
|
deba@681
|
487 |
Prio prio() const {
|
deba@681
|
488 |
while (first[minimal] == -1) {
|
deba@682
|
489 |
Direction::increase(minimal);
|
deba@681
|
490 |
}
|
deba@681
|
491 |
return minimal;
|
deba@681
|
492 |
}
|
deba@681
|
493 |
|
deba@681
|
494 |
/// \brief Deletes the item with minimum priority.
|
deba@681
|
495 |
///
|
deba@681
|
496 |
/// This method deletes the item with minimum priority from the heap.
|
deba@681
|
497 |
/// \pre The heap must be non-empty.
|
deba@681
|
498 |
void pop() {
|
deba@681
|
499 |
while (first[minimal] == -1) {
|
deba@682
|
500 |
Direction::increase(minimal);
|
deba@681
|
501 |
}
|
deba@681
|
502 |
int idx = first[minimal];
|
deba@681
|
503 |
index[data[idx].item] = -2;
|
deba@681
|
504 |
first[minimal] = data[idx].next;
|
deba@681
|
505 |
data[idx].next = free;
|
deba@681
|
506 |
free = idx;
|
deba@681
|
507 |
--num;
|
deba@681
|
508 |
}
|
deba@681
|
509 |
|
deba@681
|
510 |
/// \brief Returns the priority of \c i.
|
deba@681
|
511 |
///
|
deba@681
|
512 |
/// This function returns the priority of item \c i.
|
deba@681
|
513 |
/// \warning This operator is not a constant time function
|
deba@681
|
514 |
/// because it scans the whole data structure to find the proper
|
deba@681
|
515 |
/// value.
|
deba@681
|
516 |
/// \pre \c i must be in the heap.
|
deba@681
|
517 |
/// \param i The item.
|
deba@681
|
518 |
Prio operator[](const Item &i) const {
|
deba@681
|
519 |
for (int k = 0; k < first.size(); ++k) {
|
deba@681
|
520 |
int idx = first[k];
|
deba@681
|
521 |
while (idx != -1) {
|
deba@681
|
522 |
if (data[idx].item == i) {
|
deba@681
|
523 |
return k;
|
deba@681
|
524 |
}
|
deba@681
|
525 |
idx = data[idx].next;
|
deba@681
|
526 |
}
|
deba@681
|
527 |
}
|
deba@681
|
528 |
return -1;
|
deba@681
|
529 |
}
|
deba@681
|
530 |
|
deba@681
|
531 |
/// \brief Returns if \c item is in, has already been in, or has
|
deba@681
|
532 |
/// never been in the heap.
|
deba@681
|
533 |
///
|
deba@681
|
534 |
/// This method returns PRE_HEAP if \c item has never been in the
|
deba@681
|
535 |
/// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
|
deba@681
|
536 |
/// otherwise. In the latter case it is possible that \c item will
|
deba@681
|
537 |
/// get back to the heap again.
|
deba@681
|
538 |
/// \param i The item.
|
deba@681
|
539 |
State state(const Item &i) const {
|
deba@681
|
540 |
int idx = index[i];
|
deba@681
|
541 |
if (idx >= 0) idx = 0;
|
deba@681
|
542 |
return State(idx);
|
deba@681
|
543 |
}
|
deba@681
|
544 |
|
deba@681
|
545 |
private:
|
deba@681
|
546 |
|
deba@681
|
547 |
struct BucketItem {
|
deba@681
|
548 |
BucketItem(const Item& _item)
|
deba@681
|
549 |
: item(_item) {}
|
deba@681
|
550 |
|
deba@681
|
551 |
Item item;
|
deba@681
|
552 |
int next;
|
deba@681
|
553 |
};
|
deba@681
|
554 |
|
deba@681
|
555 |
ItemIntMap& index;
|
deba@681
|
556 |
std::vector<int> first;
|
deba@681
|
557 |
std::vector<BucketItem> data;
|
deba@681
|
558 |
int free, num;
|
deba@681
|
559 |
mutable int minimal;
|
deba@681
|
560 |
|
deba@681
|
561 |
}; // class SimpleBucketHeap
|
deba@681
|
562 |
|
deba@681
|
563 |
}
|
deba@681
|
564 |
|
deba@681
|
565 |
#endif
|