A strange compilation failure (under cygwin) is fixed.
Version 0.3 should be fixed as well.
2 * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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.
23 ///\todo It should be documented.
26 #include <lemon/error.h>
30 /// \addtogroup auxdat
33 /// A Radix Heap implementation.
35 ///\todo Please document...
40 class UnderFlowPriorityException : public RuntimeError {
42 virtual const char* exceptionName() const {
43 return "lemon::UnderFlowPriorityException";
47 template <typename _Item, typename _ItemIntMap>
52 // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
54 typedef _ItemIntMap ItemIntMap;
57 * Each Item element have a state associated to it. It may be "in heap",
58 * "pre heap" or "post heap". The later two are indifferent from the
59 * heap's point of view, but may be useful to the user.
61 * The ItemIntMap _should_ be initialized in such way, that it maps
62 * PRE_HEAP (-1) to any element to be put in the heap...
64 ///\todo it is used nowhere
78 RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
84 RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
87 std::vector<RadixItem> data;
88 std::vector<RadixBox> boxes;
95 explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
96 boxes.push_back(RadixBox(0, 1));
97 boxes.push_back(RadixBox(1, 1));
101 RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
102 boxes.push_back(RadixBox(0, 1));
103 boxes.push_back(RadixBox(1, 1));
104 while (upper(boxes.back(), capacity)) {
110 int size() const { return data.size(); }
112 bool empty() const { return data.empty(); }
116 bool upper(int box, Prio prio) {
117 return prio < boxes[box].min;
120 bool lower(int box, Prio prio) {
121 return prio >= boxes[box].min + boxes[box].size;
124 /// \brief Remove item from the box list.
125 void remove(int index) {
126 if (data[index].prev >= 0) {
127 data[data[index].prev].next = data[index].next;
129 boxes[data[index].box].first = data[index].next;
131 if (data[index].next >= 0) {
132 data[data[index].next].prev = data[index].prev;
136 /// \brief Insert item into the box list.
137 void insert(int box, int index) {
138 if (boxes[box].first == -1) {
139 boxes[box].first = index;
140 data[index].next = data[index].prev = -1;
142 data[index].next = boxes[box].first;
143 data[boxes[box].first].prev = index;
144 data[index].prev = -1;
145 boxes[box].first = index;
147 data[index].box = box;
150 /// \brief Add a new box to the box list.
152 int min = boxes.back().min + boxes.back().size;
153 int size = 2 * boxes.back().size;
154 boxes.push_back(RadixBox(min, size));
157 /// \brief Move an item up into the proper box.
158 void bubble_up(int index) {
159 if (!lower(data[index].box, data[index].prio)) return;
161 int box = findUp(data[index].box, data[index].prio);
165 /// \brief Find up the proper box for the item with the given prio.
166 int findUp(int start, int prio) {
167 while (lower(start, prio)) {
168 if (++start == (int)boxes.size()) {
175 /// \brief Move an item down into the proper box.
176 void bubble_down(int index) {
177 if (!upper(data[index].box, data[index].prio)) return;
179 int box = findDown(data[index].box, data[index].prio);
183 /// \brief Find up the proper box for the item with the given prio.
184 int findDown(int start, int prio) {
185 while (upper(start, prio)) {
186 if (--start < 0) throw UnderFlowPriorityException();
191 /// \brief Find the first not empty box.
194 while (boxes[first].first == -1) ++first;
198 /// \brief Gives back the minimal prio of the box.
199 int minValue(int box) {
200 int min = data[boxes[box].first].prio;
201 for (int k = boxes[box].first; k != -1; k = data[k].next) {
202 if (data[k].prio < min) min = data[k].prio;
207 /// \brief Rearrange the items of the heap and makes the
208 /// first box not empty.
210 // print(); printf("moveDown\n"); fflush(stdout);
211 int box = findFirst();
212 if (box == 0) return;
213 int min = minValue(box);
214 for (int i = 0; i <= box; ++i) {
216 min += boxes[i].size;
218 int curr = boxes[box].first, next;
220 next = data[curr].next;
226 void relocate_last(int index) {
227 if (index != (int)data.size() - 1) {
228 data[index] = data.back();
229 if (data[index].prev != -1) {
230 data[data[index].prev].next = index;
232 boxes[data[index].box].first = index;
234 if (data[index].next != -1) {
235 data[data[index].next].prev = index;
237 iim[data[index].item] = index;
245 void push(const Item &i, const Prio &p) {
249 data.push_back(RadixItem(i, p));
250 while (lower(boxes.size() - 1, p)) {
253 int box = findDown(boxes.size() - 1, p);
255 // printf("Push %d\n", p);
261 // print(); printf("top\n"); fflush(stdout);
262 const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
263 return data[boxes[0].first].item;
264 // print(); printf("top_end\n"); fflush(stdout);
267 /// Returns the prio of the top element of the heap.
269 // print(); printf("prio\n"); fflush(stdout);
270 const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
271 return data[boxes[0].first].prio;
276 // print(); printf("pop\n"); fflush(stdout);
278 int index = boxes[0].first;
279 iim[data[index].item] = POST_HEAP;
281 relocate_last(index);
287 void erase(const Item &i) {
291 relocate_last(index);
295 Prio operator[](const Item &i) const {
297 return data[idx].prio;
301 void set(const Item &i, const Prio &p) {
306 else if( p >= data[idx].prio ) {
316 void decrease(const Item &i, const Prio &p) {
317 // print(); printf("decrease\n"); fflush(stdout);
324 void increase(const Item &i, const Prio &p) {
331 state_enum state(const Item &i) const {
334 return state_enum(s);
337 // void print() const {
338 // for (int i = 0; i < boxes.size(); ++i) {
339 // printf("(%d, %d) ", boxes[i].min, boxes[i].size);
340 // for (int k = boxes[i].first; k != -1; k = data[k].next) {
341 // printf("%d ", data[k].prio);
348 }; // class RadixHeap
355 #endif // LEMON_RADIX_HEAP_H