NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/radix_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_RADIX_HEAP_H
18 #define LEMON_RADIX_HEAP_H
22 ///\brief Radix Heap implementation.
25 #include <lemon/error.h>
29 /// \brief Exception thrown by RadixHeap.
31 /// This Exception is thrown when a smaller priority
32 /// is inserted into the \e RadixHeap then the last time erased.
34 /// \author Balazs Dezso
36 class UnderFlowPriorityError : public RuntimeError {
38 virtual const char* exceptionName() const {
39 return "lemon::UnderFlowPriorityError";
45 /// \brief A Radix Heap implementation.
47 /// This class implements the \e radix \e heap data structure. A \e heap
48 /// is a data structure for storing items with specified values called \e
49 /// priorities in such a way that finding the item with minimum priority is
50 /// efficient. This heap type can store only items with \e int priority.
51 /// In a heap one can change the priority of an item, add or erase an
52 /// item, but the priority cannot be decreased under the last removed
55 /// \param _Item Type of the items to be stored.
56 /// \param _ItemIntMap A read and writable Item int map, used internally
57 /// to handle the cross references.
61 /// \author Balazs Dezso
63 template <typename _Item, typename _ItemIntMap>
69 typedef _ItemIntMap ItemIntMap;
71 /// \brief Type to represent the items states.
73 /// Each Item element have a state associated to it. It may be "in heap",
74 /// "pre heap" or "post heap". The latter two are indifferent from the
75 /// heap's point of view, but may be useful to the user.
77 /// The ItemIntMap \e should be initialized in such way that it maps
78 /// PRE_HEAP (-1) to any element to be put in the heap...
91 RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
97 RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
100 std::vector<RadixItem> data;
101 std::vector<RadixBox> boxes;
107 /// \brief The constructor.
111 /// \param _iim It should be given to the constructor, since it is used
112 /// internally to handle the cross references. The value of the map
113 /// should be PRE_HEAP (-1) for each element.
115 /// \param minimal The initial minimal value of the heap.
116 /// \param capacity It determines the initial capacity of the heap.
117 RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
119 boxes.push_back(RadixBox(minimal, 1));
120 boxes.push_back(RadixBox(minimal + 1, 1));
121 while (lower(boxes.size() - 1, capacity + minimal - 1)) {
126 /// The number of items stored in the heap.
128 /// \brief Returns the number of items stored in the heap.
129 int size() const { return data.size(); }
130 /// \brief Checks if the heap stores no items.
132 /// Returns \c true if and only if the heap stores no items.
133 bool empty() const { return data.empty(); }
135 /// \brief Make empty this heap.
137 /// Make empty this heap.
138 void clear(int minimal = 0, int capacity = 0) {
139 for (int i = 0; i < (int)data.size(); ++i) {
140 iim[data[i].item] = -2;
142 data.clear(); boxes.clear();
143 boxes.push_back(RadixBox(minimal, 1));
144 boxes.push_back(RadixBox(minimal + 1, 1));
145 while (lower(boxes.size() - 1, capacity + minimal - 1)) {
152 bool upper(int box, Prio prio) {
153 return prio < boxes[box].min;
156 bool lower(int box, Prio prio) {
157 return prio >= boxes[box].min + boxes[box].size;
160 /// \brief Remove item from the box list.
161 void remove(int index) {
162 if (data[index].prev >= 0) {
163 data[data[index].prev].next = data[index].next;
165 boxes[data[index].box].first = data[index].next;
167 if (data[index].next >= 0) {
168 data[data[index].next].prev = data[index].prev;
172 /// \brief Insert item into the box list.
173 void insert(int box, int index) {
174 if (boxes[box].first == -1) {
175 boxes[box].first = index;
176 data[index].next = data[index].prev = -1;
178 data[index].next = boxes[box].first;
179 data[boxes[box].first].prev = index;
180 data[index].prev = -1;
181 boxes[box].first = index;
183 data[index].box = box;
186 /// \brief Add a new box to the box list.
188 int min = boxes.back().min + boxes.back().size;
189 int size = 2 * boxes.back().size;
190 boxes.push_back(RadixBox(min, size));
193 /// \brief Move an item up into the proper box.
194 void bubble_up(int index) {
195 if (!lower(data[index].box, data[index].prio)) return;
197 int box = findUp(data[index].box, data[index].prio);
201 /// \brief Find up the proper box for the item with the given prio.
202 int findUp(int start, int prio) {
203 while (lower(start, prio)) {
204 if (++start == (int)boxes.size()) {
211 /// \brief Move an item down into the proper box.
212 void bubble_down(int index) {
213 if (!upper(data[index].box, data[index].prio)) return;
215 int box = findDown(data[index].box, data[index].prio);
219 /// \brief Find up the proper box for the item with the given prio.
220 int findDown(int start, int prio) {
221 while (upper(start, prio)) {
222 if (--start < 0) throw UnderFlowPriorityError();
227 /// \brief Find the first not empty box.
230 while (boxes[first].first == -1) ++first;
234 /// \brief Gives back the minimal prio of the box.
235 int minValue(int box) {
236 int min = data[boxes[box].first].prio;
237 for (int k = boxes[box].first; k != -1; k = data[k].next) {
238 if (data[k].prio < min) min = data[k].prio;
243 /// \brief Rearrange the items of the heap and makes the
244 /// first box not empty.
246 int box = findFirst();
247 if (box == 0) return;
248 int min = minValue(box);
249 for (int i = 0; i <= box; ++i) {
251 min += boxes[i].size;
253 int curr = boxes[box].first, next;
255 next = data[curr].next;
261 void relocate_last(int index) {
262 if (index != (int)data.size() - 1) {
263 data[index] = data.back();
264 if (data[index].prev != -1) {
265 data[data[index].prev].next = index;
267 boxes[data[index].box].first = index;
269 if (data[index].next != -1) {
270 data[data[index].next].prev = index;
272 iim[data[index].item] = index;
279 /// \brief Insert an item into the heap with the given priority.
281 /// Adds \c i to the heap with priority \c p.
282 /// \param i The item to insert.
283 /// \param p The priority of the item.
284 void push(const Item &i, const Prio &p) {
287 data.push_back(RadixItem(i, p));
288 while (lower(boxes.size() - 1, p)) {
291 int box = findDown(boxes.size() - 1, p);
295 /// \brief Returns the item with minimum priority.
297 /// This method returns the item with minimum priority.
298 /// \pre The heap must be nonempty.
300 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
301 return data[boxes[0].first].item;
304 /// \brief Returns the minimum priority.
306 /// It returns the minimum priority.
307 /// \pre The heap must be nonempty.
309 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
310 return data[boxes[0].first].prio;
313 /// \brief Deletes the item with minimum priority.
315 /// This method deletes the item with minimum priority.
316 /// \pre The heap must be non-empty.
319 int index = boxes[0].first;
320 iim[data[index].item] = POST_HEAP;
322 relocate_last(index);
325 /// \brief Deletes \c i from the heap.
327 /// This method deletes item \c i from the heap, if \c i was
328 /// already stored in the heap.
329 /// \param i The item to erase.
330 void erase(const Item &i) {
334 relocate_last(index);
337 /// \brief Returns the priority of \c i.
339 /// This function returns the priority of item \c i.
340 /// \pre \c i must be in the heap.
341 /// \param i The item.
342 Prio operator[](const Item &i) const {
344 return data[idx].prio;
347 /// \brief \c i gets to the heap with priority \c p independently
348 /// if \c i was already there.
350 /// This method calls \ref push(\c i, \c p) if \c i is not stored
351 /// in the heap and sets the priority of \c i to \c p otherwise.
352 /// It may throw an \e UnderFlowPriorityException.
353 /// \param i The item.
354 /// \param p The priority.
355 void set(const Item &i, const Prio &p) {
360 else if( p >= data[idx].prio ) {
370 /// \brief Decreases the priority of \c i to \c p.
372 /// This method decreases the priority of item \c i to \c p.
373 /// \pre \c i must be stored in the heap with priority at least \c p, and
374 /// \c should be greater or equal to the last removed item's priority.
375 /// \param i The item.
376 /// \param p The priority.
377 void decrease(const Item &i, const Prio &p) {
383 /// \brief Increases the priority of \c i to \c p.
385 /// This method sets the priority of item \c i to \c p.
386 /// \pre \c i must be stored in the heap with priority at most \c p
387 /// \param i The item.
388 /// \param p The priority.
389 void increase(const Item &i, const Prio &p) {
395 /// \brief Returns if \c item is in, has already been in, or has
396 /// never been in the heap.
398 /// This method returns PRE_HEAP if \c item has never been in the
399 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
400 /// otherwise. In the latter case it is possible that \c item will
401 /// get back to the heap again.
402 /// \param i The item.
403 state_enum state(const Item &i) const {
406 return state_enum(s);
409 }; // class RadixHeap
416 #endif // LEMON_RADIX_HEAP_H