Documentation improvments.
2 * src/lemon/radix_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 /// \brief Exception thrown by RadixHeap.
35 /// This Exception is thrown when a smaller priority
36 /// is inserted into the \e RadixHeap then the last time erased.
38 /// \author Balazs Dezso
40 class UnderFlowPriorityError : public RuntimeError {
42 virtual const char* exceptionName() const {
43 return "lemon::UnderFlowPriorityError";
47 /// \brief A Radix Heap implementation.
49 /// This class implements the \e radix \e heap data structure. A \e heap
50 /// is a data structure for storing items with specified values called \e
51 /// priorities in such a way that finding the item with minimum priority is
52 /// efficient. This heap type can store only items with \e int priority.
53 /// In a heap one can change the priority of an item, add or erase an
54 /// item, but the priority cannot be decreased under the last removed
57 /// \param _Item Type of the items to be stored.
58 /// \param _ItemIntMap A read and writable Item int map, used internally
59 /// to handle the cross references.
63 /// \author Balazs Dezso
65 template <typename _Item, typename _ItemIntMap>
71 typedef _ItemIntMap ItemIntMap;
73 /// \brief Type to represent the items states.
75 /// Each Item element have a state associated to it. It may be "in heap",
76 /// "pre heap" or "post heap". The later two are indifferent from the
77 /// heap's point of view, but may be useful to the user.
79 /// The ItemIntMap _should_ be initialized in such way, that it maps
80 /// PRE_HEAP (-1) to any element to be put in the heap...
93 RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
99 RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
102 std::vector<RadixItem> data;
103 std::vector<RadixBox> boxes;
109 /// \brief The constructor.
112 /// \param _iim should be given to the constructor, since it is used
113 /// internally to handle the cross references. The value of the map
114 /// should be PRE_HEAP (-1) for each element.
115 explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
116 boxes.push_back(RadixBox(0, 1));
117 boxes.push_back(RadixBox(1, 1));
120 /// \brief The constructor.
124 /// \param _iim It should be given to the constructor, since it is used
125 /// internally to handle the cross references. The value of the map
126 /// should be PRE_HEAP (-1) for each element.
128 /// \param capacity It determines the initial capacity of the heap.
129 RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
130 boxes.push_back(RadixBox(0, 1));
131 boxes.push_back(RadixBox(1, 1));
132 while (upper(boxes.back(), capacity)) {
137 /// The number of items stored in the heap.
139 /// \brief Returns the number of items stored in the heap.
140 int size() const { return data.size(); }
141 /// \brief Checks if the heap stores no items.
143 /// Returns \c true if and only if the heap stores no items.
144 bool empty() const { return data.empty(); }
148 bool upper(int box, Prio prio) {
149 return prio < boxes[box].min;
152 bool lower(int box, Prio prio) {
153 return prio >= boxes[box].min + boxes[box].size;
156 /// \brief Remove item from the box list.
157 void remove(int index) {
158 if (data[index].prev >= 0) {
159 data[data[index].prev].next = data[index].next;
161 boxes[data[index].box].first = data[index].next;
163 if (data[index].next >= 0) {
164 data[data[index].next].prev = data[index].prev;
168 /// \brief Insert item into the box list.
169 void insert(int box, int index) {
170 if (boxes[box].first == -1) {
171 boxes[box].first = index;
172 data[index].next = data[index].prev = -1;
174 data[index].next = boxes[box].first;
175 data[boxes[box].first].prev = index;
176 data[index].prev = -1;
177 boxes[box].first = index;
179 data[index].box = box;
182 /// \brief Add a new box to the box list.
184 int min = boxes.back().min + boxes.back().size;
185 int size = 2 * boxes.back().size;
186 boxes.push_back(RadixBox(min, size));
189 /// \brief Move an item up into the proper box.
190 void bubble_up(int index) {
191 if (!lower(data[index].box, data[index].prio)) return;
193 int box = findUp(data[index].box, data[index].prio);
197 /// \brief Find up the proper box for the item with the given prio.
198 int findUp(int start, int prio) {
199 while (lower(start, prio)) {
200 if (++start == (int)boxes.size()) {
207 /// \brief Move an item down into the proper box.
208 void bubble_down(int index) {
209 if (!upper(data[index].box, data[index].prio)) return;
211 int box = findDown(data[index].box, data[index].prio);
215 /// \brief Find up the proper box for the item with the given prio.
216 int findDown(int start, int prio) {
217 while (upper(start, prio)) {
218 if (--start < 0) throw UnderFlowPriorityError();
223 /// \brief Find the first not empty box.
226 while (boxes[first].first == -1) ++first;
230 /// \brief Gives back the minimal prio of the box.
231 int minValue(int box) {
232 int min = data[boxes[box].first].prio;
233 for (int k = boxes[box].first; k != -1; k = data[k].next) {
234 if (data[k].prio < min) min = data[k].prio;
239 /// \brief Rearrange the items of the heap and makes the
240 /// first box not empty.
242 int box = findFirst();
243 if (box == 0) return;
244 int min = minValue(box);
245 for (int i = 0; i <= box; ++i) {
247 min += boxes[i].size;
249 int curr = boxes[box].first, next;
251 next = data[curr].next;
257 void relocate_last(int index) {
258 if (index != (int)data.size() - 1) {
259 data[index] = data.back();
260 if (data[index].prev != -1) {
261 data[data[index].prev].next = index;
263 boxes[data[index].box].first = index;
265 if (data[index].next != -1) {
266 data[data[index].next].prev = index;
268 iim[data[index].item] = index;
275 /// \brief Insert an item into the heap with the given heap.
277 /// Adds \c i to the heap with priority \c p.
278 /// \param i The item to insert.
279 /// \param p The priority of the item.
280 void push(const Item &i, const Prio &p) {
283 data.push_back(RadixItem(i, p));
284 while (lower(boxes.size() - 1, p)) {
287 int box = findDown(boxes.size() - 1, p);
291 /// \brief Returns the item with minimum priority.
293 /// This method returns the item with minimum priority.
294 /// \pre The heap must be nonempty.
296 const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
297 return data[boxes[0].first].item;
300 /// \brief Returns the minimum priority.
302 /// It returns the minimum priority.
303 /// \pre The heap must be nonempty.
305 const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
306 return data[boxes[0].first].prio;
309 /// \brief Deletes the item with minimum priority.
311 /// This method deletes the item with minimum priority.
312 /// \pre The heap must be non-empty.
315 int index = boxes[0].first;
316 iim[data[index].item] = POST_HEAP;
318 relocate_last(index);
321 /// \brief Deletes \c i from the heap.
323 /// This method deletes item \c i from the heap, if \c i was
324 /// already stored in the heap.
325 /// \param i The item to erase.
326 void erase(const Item &i) {
330 relocate_last(index);
333 /// \brief Returns the priority of \c i.
335 /// This function returns the priority of item \c i.
336 /// \pre \c i must be in the heap.
337 /// \param i The item.
338 Prio operator[](const Item &i) const {
340 return data[idx].prio;
343 /// \brief \c i gets to the heap with priority \c p independently
344 /// if \c i was already there.
346 /// This method calls \ref push(\c i, \c p) if \c i is not stored
347 /// in the heap and sets the priority of \c i to \c p otherwise.
348 /// It may throw an \e UnderFlowPriorityException.
349 /// \param i The item.
350 /// \param p The priority.
351 void set(const Item &i, const Prio &p) {
356 else if( p >= data[idx].prio ) {
366 /// \brief Decreases the priority of \c i to \c p.
368 /// This method decreases the priority of item \c i to \c p.
369 /// \pre \c i must be stored in the heap with priority at least \c p, and
370 /// \c should be greater then the last removed item's priority.
371 /// \param i The item.
372 /// \param p The priority.
373 void decrease(const Item &i, const Prio &p) {
379 /// \brief Increases the priority of \c i to \c p.
381 /// This method sets the priority of item \c i to \c p.
382 /// \pre \c i must be stored in the heap with priority at most \c
383 /// p relative to \c Compare.
384 /// \param i The item.
385 /// \param p The priority.
386 void increase(const Item &i, const Prio &p) {
392 /// \brief Returns if \c item is in, has already been in, or has
393 /// never been in the heap.
395 /// This method returns PRE_HEAP if \c item has never been in the
396 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
397 /// otherwise. In the latter case it is possible that \c item will
398 /// get back to the heap again.
399 /// \param i The item.
400 state_enum state(const Item &i) const {
403 return state_enum(s);
406 }; // class RadixHeap
413 #endif // LEMON_RADIX_HEAP_H