1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/radix_heap.h Fri Mar 04 17:09:24 2005 +0000
1.3 @@ -0,0 +1,355 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_RADIX_HEAP_H
1.21 +#define LEMON_RADIX_HEAP_H
1.22 +
1.23 +///\ingroup auxdat
1.24 +///\file
1.25 +///\brief Radix Heap implementation.
1.26 +///\todo It should be documented.
1.27 +
1.28 +#include <vector>
1.29 +#include <lemon/error.h>
1.30 +
1.31 +namespace lemon {
1.32 +
1.33 + /// \addtogroup auxdat
1.34 + /// @{
1.35 +
1.36 + /// A Binary Heap implementation.
1.37 +
1.38 + ///\todo Please document...
1.39 + ///
1.40 + ///\sa BinHeap
1.41 + ///\sa Dijkstra
1.42 +
1.43 + class UnderFlowPriorityException : public RuntimeError {
1.44 + public:
1.45 + virtual const char* exceptionName() const {
1.46 + return "lemon::UnderFlowPriorityException";
1.47 + }
1.48 + };
1.49 +
1.50 + template <typename _Item, typename _ItemIntMap>
1.51 + class RadixHeap {
1.52 +
1.53 + public:
1.54 + typedef _Item Item;
1.55 + // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
1.56 + typedef int Prio;
1.57 + typedef _ItemIntMap ItemIntMap;
1.58 +
1.59 + /**
1.60 + * Each Item element have a state associated to it. It may be "in heap",
1.61 + * "pre heap" or "post heap". The later two are indifferent from the
1.62 + * heap's point of view, but may be useful to the user.
1.63 + *
1.64 + * The ItemIntMap _should_ be initialized in such way, that it maps
1.65 + * PRE_HEAP (-1) to any element to be put in the heap...
1.66 + */
1.67 + ///\todo it is used nowhere
1.68 + ///
1.69 + enum state_enum {
1.70 + IN_HEAP = 0,
1.71 + PRE_HEAP = -1,
1.72 + POST_HEAP = -2
1.73 + };
1.74 +
1.75 + private:
1.76 +
1.77 + struct RadixItem {
1.78 + int prev, next, box;
1.79 + Item item;
1.80 + int prio;
1.81 + RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
1.82 + };
1.83 +
1.84 + struct RadixBox {
1.85 + int first;
1.86 + int min, size;
1.87 + RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
1.88 + };
1.89 +
1.90 + std::vector<RadixItem> data;
1.91 + std::vector<RadixBox> boxes;
1.92 +
1.93 + ItemIntMap &iim;
1.94 +
1.95 +
1.96 + public:
1.97 + ///\e
1.98 + explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
1.99 + boxes.push_back(RadixBox(0, 1));
1.100 + boxes.push_back(RadixBox(1, 1));
1.101 + }
1.102 +
1.103 + ///\e
1.104 + RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
1.105 + boxes.push_back(RadixBox(0, 1));
1.106 + boxes.push_back(RadixBox(1, 1));
1.107 + while (upper(boxes.back(), capacity)) {
1.108 + extend();
1.109 + }
1.110 + }
1.111 +
1.112 + ///\e
1.113 + int size() const { return data.size(); }
1.114 + ///\e
1.115 + bool empty() const { return data.empty(); }
1.116 +
1.117 + private:
1.118 +
1.119 + bool upper(int box, Prio prio) {
1.120 + return prio < boxes[box].min;
1.121 + }
1.122 +
1.123 + bool lower(int box, Prio prio) {
1.124 + return prio >= boxes[box].min + boxes[box].size;
1.125 + }
1.126 +
1.127 + /// \brief Remove item from the box list.
1.128 + void remove(int index) {
1.129 + if (data[index].prev >= 0) {
1.130 + data[data[index].prev].next = data[index].next;
1.131 + } else {
1.132 + boxes[data[index].box].first = data[index].next;
1.133 + }
1.134 + if (data[index].next >= 0) {
1.135 + data[data[index].next].prev = data[index].prev;
1.136 + }
1.137 + }
1.138 +
1.139 + /// \brief Insert item into the box list.
1.140 + void insert(int box, int index) {
1.141 + if (boxes[box].first == -1) {
1.142 + boxes[box].first = index;
1.143 + data[index].next = data[index].prev = -1;
1.144 + } else {
1.145 + data[index].next = boxes[box].first;
1.146 + data[boxes[box].first].prev = index;
1.147 + data[index].prev = -1;
1.148 + boxes[box].first = index;
1.149 + }
1.150 + data[index].box = box;
1.151 + }
1.152 +
1.153 + /// \brief Add a new box to the box list.
1.154 + void extend() {
1.155 + int min = boxes.back().min + boxes.back().size;
1.156 + int size = 2 * boxes.back().size;
1.157 + boxes.push_back(RadixBox(min, size));
1.158 + }
1.159 +
1.160 + /// \brief Move an item up into the proper box.
1.161 + void bubble_up(int index) {
1.162 + if (!lower(data[index].box, index)) return;
1.163 + remove(index);
1.164 + int box = findUp(data[index].box, data[index].prio);
1.165 + insert(box, index);
1.166 + }
1.167 +
1.168 + /// \brief Find up the proper box for the item with the given prio.
1.169 + int findUp(int start, int prio) {
1.170 + while (lower(start, prio)) {
1.171 + if (++start == (int)boxes.size()) {
1.172 + extend();
1.173 + }
1.174 + }
1.175 + return start;
1.176 + }
1.177 +
1.178 + /// \brief Move an item down into the proper box.
1.179 + void bubble_down(int index) {
1.180 + if (!upper(data[index].box, data[index].prio)) return;
1.181 + remove(index);
1.182 + int box = findDown(data[index].box, data[index].prio);
1.183 + insert(box, index);
1.184 + }
1.185 +
1.186 + /// \brief Find up the proper box for the item with the given prio.
1.187 + int findDown(int start, int prio) {
1.188 + while (upper(start, prio)) {
1.189 + if (--start < 0) throw UnderFlowPriorityException();
1.190 + }
1.191 + return start;
1.192 + }
1.193 +
1.194 + /// \brief Find the first not empty box.
1.195 + int findFirst() {
1.196 + int first = 0;
1.197 + while (boxes[first].first == -1) ++first;
1.198 + return first;
1.199 + }
1.200 +
1.201 + /// \brief Gives back the minimal prio of the box.
1.202 + int minValue(int box) {
1.203 + int min = data[boxes[box].first].prio;
1.204 + for (int k = boxes[box].first; k != -1; k = data[k].next) {
1.205 + if (data[k].prio < min) min = data[k].prio;
1.206 + }
1.207 + return min;
1.208 + }
1.209 +
1.210 + /// \brief Rearrange the items of the heap and makes the
1.211 + /// first box not empty.
1.212 + void moveDown() {
1.213 + // print(); printf("moveDown\n"); fflush(stdout);
1.214 + int box = findFirst();
1.215 + if (box == 0) return;
1.216 + int min = minValue(box);
1.217 + for (int i = 0; i <= box; ++i) {
1.218 + boxes[i].min = min;
1.219 + min += boxes[i].size;
1.220 + }
1.221 + int curr = boxes[box].first, next;
1.222 + while (curr != -1) {
1.223 + next = data[curr].next;
1.224 + bubble_down(curr);
1.225 + curr = next;
1.226 + }
1.227 + }
1.228 +
1.229 + void relocate_last(int index) {
1.230 + if (index != (int)data.size() - 1) {
1.231 + data[index] = data.back();
1.232 + if (data[index].prev != -1) {
1.233 + data[data[index].prev].next = index;
1.234 + } else {
1.235 + boxes[data[index].box].first = index;
1.236 + }
1.237 + if (data[index].next != -1) {
1.238 + data[data[index].next].prev = index;
1.239 + }
1.240 + iim[data[index].item] = index;
1.241 + }
1.242 + data.pop_back();
1.243 + }
1.244 +
1.245 + public:
1.246 +
1.247 + ///\e
1.248 + void push(const Item &i, const Prio &p) {
1.249 + fflush(stdout);
1.250 + int n = data.size();
1.251 + iim.set(i, n);
1.252 + data.push_back(RadixItem(i, p));
1.253 + while (lower(boxes.size() - 1, p)) {
1.254 + extend();
1.255 + }
1.256 + int box = findDown(boxes.size() - 1, p);
1.257 + insert(box, n);
1.258 + // printf("Push %d\n", p);
1.259 + //print();
1.260 + }
1.261 +
1.262 + ///\e
1.263 + Item top() const {
1.264 + // print(); printf("top\n"); fflush(stdout);
1.265 + const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
1.266 + return data[boxes[0].first].item;
1.267 + // print(); printf("top_end\n"); fflush(stdout);
1.268 + }
1.269 +
1.270 + /// Returns the prio of the top element of the heap.
1.271 + Prio prio() const {
1.272 + // print(); printf("prio\n"); fflush(stdout);
1.273 + const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
1.274 + return data[boxes[0].first].prio;
1.275 + }
1.276 +
1.277 + ///\e
1.278 + void pop() {
1.279 + // print(); printf("pop\n"); fflush(stdout);
1.280 + moveDown();
1.281 + int index = boxes[0].first;
1.282 + iim[data[index].item] = POST_HEAP;
1.283 + remove(index);
1.284 + relocate_last(index);
1.285 + // printf("Pop \n");
1.286 + //print();
1.287 + }
1.288 +
1.289 + ///\e
1.290 + void erase(const Item &i) {
1.291 + int index = iim[i];
1.292 + iim[i] = POST_HEAP;
1.293 + remove(index);
1.294 + relocate_last(index);
1.295 + }
1.296 +
1.297 + ///\e
1.298 + Prio operator[](const Item &i) const {
1.299 + int idx = iim[i];
1.300 + return data[idx].prio;
1.301 + }
1.302 +
1.303 + ///\e
1.304 + void set(const Item &i, const Prio &p) {
1.305 + int idx = iim[i];
1.306 + if( idx < 0 ) {
1.307 + push(i, p);
1.308 + }
1.309 + else if( p >= data[idx].prio ) {
1.310 + data[idx].prio = p;
1.311 + bubble_up(idx);
1.312 + } else {
1.313 + data[idx].prio = p;
1.314 + bubble_down(idx);
1.315 + }
1.316 + }
1.317 +
1.318 + ///\e
1.319 + void decrease(const Item &i, const Prio &p) {
1.320 + // print(); printf("decrease\n"); fflush(stdout);
1.321 + int idx = iim[i];
1.322 + data[idx].prio = p;
1.323 + bubble_down(idx);
1.324 + }
1.325 +
1.326 + ///\e
1.327 + void increase(const Item &i, const Prio &p) {
1.328 + int idx = iim[i];
1.329 + data[idx].prio = p;
1.330 + bubble_up(idx);
1.331 + }
1.332 +
1.333 + ///\e
1.334 + state_enum state(const Item &i) const {
1.335 + int s = iim[i];
1.336 + if( s >= 0 ) s = 0;
1.337 + return state_enum(s);
1.338 + }
1.339 +
1.340 + void print() const {
1.341 + for (int i = 0; i < boxes.size(); ++i) {
1.342 + printf("(%d, %d) ", boxes[i].min, boxes[i].size);
1.343 + for (int k = boxes[i].first; k != -1; k = data[k].next) {
1.344 + printf("%d ", data[k].prio);
1.345 + }
1.346 + printf("\n");
1.347 + }
1.348 + fflush(stdout);
1.349 + }
1.350 +
1.351 + }; // class RadixHeap
1.352 +
1.353 +
1.354 + ///@}
1.355 +
1.356 +} // namespace lemon
1.357 +
1.358 +#endif // LEMON_RADIX_HEAP_H