COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/radix_heap.h @ 1331:7e93d3f0406d

Last change on this file since 1331:7e93d3f0406d was 1331:7e93d3f0406d, checked in by Balazs Dezso, 15 years ago

Documentation improvments.

File size: 11.6 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/radix_heap.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_RADIX_HEAP_H
18#define LEMON_RADIX_HEAP_H
19
20///\ingroup auxdat
21///\file
22///\brief Radix Heap implementation.
23///\todo It should be documented.
24
25#include <vector>
26#include <lemon/error.h>
27
28namespace lemon {
29
30  /// \addtogroup auxdat
31  /// @{
32
33  /// \brief Exception thrown by RadixHeap.
34  /// 
35  /// This Exception is thrown when a smaller priority
36  /// is inserted into the \e RadixHeap then the last time erased.
37  /// \see RadixHeap
38  /// \author Balazs Dezso
39
40  class UnderFlowPriorityError : public RuntimeError {
41  public:
42    virtual const char* exceptionName() const {
43      return "lemon::UnderFlowPriorityError";
44    } 
45  };
46
47  /// \brief A Radix Heap implementation.
48  ///
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
55  /// item's priority.
56  ///
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.
60  ///
61  /// \see BinHeap
62  /// \see Dijkstra
63  /// \author Balazs Dezso
64
65  template <typename _Item, typename _ItemIntMap>
66  class RadixHeap {
67
68  public:
69    typedef _Item Item;
70    typedef int Prio;
71    typedef _ItemIntMap ItemIntMap;
72
73    /// \brief Type to represent the items states.
74    ///
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.
78    ///
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...
81    enum state_enum {
82      IN_HEAP = 0,
83      PRE_HEAP = -1,
84      POST_HEAP = -2
85    };
86
87  private:
88   
89    struct RadixItem {
90      int prev, next, box;
91      Item item;
92      int prio;
93      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
94    };
95
96    struct RadixBox {
97      int first;
98      int min, size;
99      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
100    };
101
102    std::vector<RadixItem> data;
103    std::vector<RadixBox> boxes;
104
105    ItemIntMap &iim;
106
107
108  public:
109    /// \brief The constructor.
110    ///
111    /// 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));
118    }
119
120    /// \brief The constructor.
121    ///
122    /// The constructor.
123    ///
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.
127    ///
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)) {
133        extend();
134      }
135    }
136
137    /// The number of items stored in the heap.
138    ///
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.
142    ///
143    /// Returns \c true if and only if the heap stores no items.
144    bool empty() const { return data.empty(); }
145
146  private:
147
148    bool upper(int box, Prio prio) {
149      return prio < boxes[box].min;
150    }
151
152    bool lower(int box, Prio prio) {
153      return prio >= boxes[box].min + boxes[box].size;
154    }
155
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;
160      } else {
161        boxes[data[index].box].first = data[index].next;
162      }
163      if (data[index].next >= 0) {
164        data[data[index].next].prev = data[index].prev;
165      }
166    }
167
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;
173      } else {
174        data[index].next = boxes[box].first;
175        data[boxes[box].first].prev = index;
176        data[index].prev = -1;
177        boxes[box].first = index;
178      }
179      data[index].box = box;
180    }
181
182    /// \brief Add a new box to the box list.
183    void extend() {
184      int min = boxes.back().min + boxes.back().size;
185      int size = 2 * boxes.back().size;
186      boxes.push_back(RadixBox(min, size));
187    }
188
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;
192      remove(index);
193      int box = findUp(data[index].box, data[index].prio);
194      insert(box, index);     
195    }
196
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()) {
201          extend();
202        }
203      }
204      return start;
205    }
206
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;
210      remove(index);
211      int box = findDown(data[index].box, data[index].prio);
212      insert(box, index);
213    }
214
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();
219      }
220      return start;
221    }
222
223    /// \brief Find the first not empty box.
224    int findFirst() {
225      int first = 0;
226      while (boxes[first].first == -1) ++first;
227      return first;
228    }
229
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;
235      }
236      return min;
237    }
238
239    /// \brief Rearrange the items of the heap and makes the
240    /// first box not empty.
241    void moveDown() {
242      int box = findFirst();
243      if (box == 0) return;
244      int min = minValue(box);
245      for (int i = 0; i <= box; ++i) {
246        boxes[i].min = min;
247        min += boxes[i].size;
248      }
249      int curr = boxes[box].first, next;
250      while (curr != -1) {
251        next = data[curr].next;
252        bubble_down(curr);
253        curr = next;
254      }     
255    }
256
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;
262        } else {
263          boxes[data[index].box].first = index;
264        }
265        if (data[index].next != -1) {
266          data[data[index].next].prev = index;
267        }
268        iim[data[index].item] = index;
269      }
270      data.pop_back();
271    }
272
273  public:
274
275    /// \brief Insert an item into the heap with the given heap.
276    ///   
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) {
281      int n = data.size();
282      iim.set(i, n);
283      data.push_back(RadixItem(i, p));
284      while (lower(boxes.size() - 1, p)) {
285        extend();
286      }
287      int box = findDown(boxes.size() - 1, p);
288      insert(box, n);
289    }
290
291    /// \brief Returns the item with minimum priority.
292    ///
293    /// This method returns the item with minimum priority. 
294    /// \pre The heap must be nonempty. 
295    Item top() const {
296      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
297      return data[boxes[0].first].item;
298    }
299
300    /// \brief Returns the minimum priority.
301    ///
302    /// It returns the minimum priority.
303    /// \pre The heap must be nonempty.
304    Prio prio() const {
305      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
306      return data[boxes[0].first].prio;
307     }
308
309    /// \brief Deletes the item with minimum priority.
310    ///
311    /// This method deletes the item with minimum priority.
312    /// \pre The heap must be non-empty. 
313    void pop() {
314      moveDown();
315      int index = boxes[0].first;
316      iim[data[index].item] = POST_HEAP;
317      remove(index);
318      relocate_last(index);
319    }
320
321    /// \brief Deletes \c i from the heap.
322    ///
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) {
327      int index = iim[i];
328      iim[i] = POST_HEAP;
329      remove(index);
330      relocate_last(index);
331   }
332
333    /// \brief Returns the priority of \c i.
334    ///
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 {
339      int idx = iim[i];
340      return data[idx].prio;
341    }
342
343    /// \brief \c i gets to the heap with priority \c p independently
344    /// if \c i was already there.
345    ///
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) {
352      int idx = iim[i];
353      if( idx < 0 ) {
354        push(i, p);
355      }
356      else if( p >= data[idx].prio ) {
357        data[idx].prio = p;
358        bubble_up(idx);
359      } else {
360        data[idx].prio = p;
361        bubble_down(idx);
362      }
363    }
364
365
366    /// \brief Decreases the priority of \c i to \c p.
367    ///
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) {
374      int idx = iim[i];
375      data[idx].prio = p;
376      bubble_down(idx);
377    }
378
379    /// \brief Increases the priority of \c i to \c p.
380    ///
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) {
387      int idx = iim[i];
388      data[idx].prio = p;
389      bubble_up(idx);
390    }
391
392    /// \brief Returns if \c item is in, has already been in, or has
393    /// never been in the heap.
394    ///
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 {
401      int s = iim[i];
402      if( s >= 0 ) s = 0;
403      return state_enum(s);
404    }
405
406  }; // class RadixHeap
407
408
409  ///@}
410
411} // namespace lemon
412
413#endif // LEMON_RADIX_HEAP_H
Note: See TracBrowser for help on using the repository browser.