COIN-OR::LEMON - Graph Library

source: lemon/lemon/radix_heap.h @ 810:93cd93e82f9b

Last change on this file since 810:93cd93e82f9b was 730:9f529abcaebf, checked in by Balazs Dezso <deba@…>, 16 years ago

Unification of names in heaps (#50)

File size: 12.5 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_RADIX_HEAP_H
20#define LEMON_RADIX_HEAP_H
21
22///\ingroup auxdat
23///\file
24///\brief Radix Heap implementation.
25
26#include <vector>
27#include <lemon/error.h>
28
29namespace lemon {
30
31
32  /// \ingroup auxdata
33  ///
34  /// \brief A Radix Heap implementation.
35  ///
36  /// This class implements the \e radix \e heap data structure. A \e heap
37  /// is a data structure for storing items with specified values called \e
38  /// priorities in such a way that finding the item with minimum priority is
39  /// efficient. This heap type can store only items with \e int priority.
40  /// In a heap one can change the priority of an item, add or erase an
41  /// item, but the priority cannot be decreased under the last removed
42  /// item's priority.
43  ///
44  /// \param IM A read and writable Item int map, used internally
45  /// to handle the cross references.
46  ///
47  /// \see BinHeap
48  /// \see Dijkstra
49  template <typename IM>
50  class RadixHeap {
51
52  public:
53    typedef typename IM::Key Item;
54    typedef int Prio;
55    typedef IM ItemIntMap;
56
57    /// \brief Exception thrown by RadixHeap.
58    ///
59    /// This Exception is thrown when a smaller priority
60    /// is inserted into the \e RadixHeap then the last time erased.
61    /// \see RadixHeap
62
63    class UnderFlowPriorityError : public Exception {
64    public:
65      virtual const char* what() const throw() {
66        return "lemon::RadixHeap::UnderFlowPriorityError";
67      }
68    };
69
70    /// \brief Type to represent the items states.
71    ///
72    /// Each Item element have a state associated to it. It may be "in heap",
73    /// "pre heap" or "post heap". The latter two are indifferent from the
74    /// heap's point of view, but may be useful to the user.
75    ///
76    /// The ItemIntMap \e should be initialized in such way that it maps
77    /// PRE_HEAP (-1) to any element to be put in the heap...
78    enum State {
79      IN_HEAP = 0,
80      PRE_HEAP = -1,
81      POST_HEAP = -2
82    };
83
84  private:
85
86    struct RadixItem {
87      int prev, next, box;
88      Item item;
89      int prio;
90      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
91    };
92
93    struct RadixBox {
94      int first;
95      int min, size;
96      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
97    };
98
99    std::vector<RadixItem> data;
100    std::vector<RadixBox> boxes;
101
102    ItemIntMap &_iim;
103
104
105  public:
106    /// \brief The constructor.
107    ///
108    /// The constructor.
109    ///
110    /// \param map It should be given to the constructor, since it is used
111    /// internally to handle the cross references. The value of the map
112    /// should be PRE_HEAP (-1) for each element.
113    ///
114    /// \param minimal The initial minimal value of the heap.
115    /// \param capacity It determines the initial capacity of the heap.
116    RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
117      : _iim(map) {
118      boxes.push_back(RadixBox(minimal, 1));
119      boxes.push_back(RadixBox(minimal + 1, 1));
120      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
121        extend();
122      }
123    }
124
125    /// The number of items stored in the heap.
126    ///
127    /// \brief Returns the number of items stored in the heap.
128    int size() const { return data.size(); }
129    /// \brief Checks if the heap stores no items.
130    ///
131    /// Returns \c true if and only if the heap stores no items.
132    bool empty() const { return data.empty(); }
133
134    /// \brief Make empty this heap.
135    ///
136    /// Make empty this heap. It does not change the cross reference
137    /// map.  If you want to reuse a heap what is not surely empty you
138    /// should first clear the heap and after that you should set the
139    /// cross reference map for each item to \c PRE_HEAP.
140    void clear(int minimal = 0, int capacity = 0) {
141      data.clear(); boxes.clear();
142      boxes.push_back(RadixBox(minimal, 1));
143      boxes.push_back(RadixBox(minimal + 1, 1));
144      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
145        extend();
146      }
147    }
148
149  private:
150
151    bool upper(int box, Prio pr) {
152      return pr < boxes[box].min;
153    }
154
155    bool lower(int box, Prio pr) {
156      return pr >= boxes[box].min + boxes[box].size;
157    }
158
159    /// \brief Remove item from the box list.
160    void remove(int index) {
161      if (data[index].prev >= 0) {
162        data[data[index].prev].next = data[index].next;
163      } else {
164        boxes[data[index].box].first = data[index].next;
165      }
166      if (data[index].next >= 0) {
167        data[data[index].next].prev = data[index].prev;
168      }
169    }
170
171    /// \brief Insert item into the box list.
172    void insert(int box, int index) {
173      if (boxes[box].first == -1) {
174        boxes[box].first = index;
175        data[index].next = data[index].prev = -1;
176      } else {
177        data[index].next = boxes[box].first;
178        data[boxes[box].first].prev = index;
179        data[index].prev = -1;
180        boxes[box].first = index;
181      }
182      data[index].box = box;
183    }
184
185    /// \brief Add a new box to the box list.
186    void extend() {
187      int min = boxes.back().min + boxes.back().size;
188      int bs = 2 * boxes.back().size;
189      boxes.push_back(RadixBox(min, bs));
190    }
191
192    /// \brief Move an item up into the proper box.
193    void bubble_up(int index) {
194      if (!lower(data[index].box, data[index].prio)) return;
195      remove(index);
196      int box = findUp(data[index].box, data[index].prio);
197      insert(box, index);
198    }
199
200    /// \brief Find up the proper box for the item with the given prio.
201    int findUp(int start, int pr) {
202      while (lower(start, pr)) {
203        if (++start == int(boxes.size())) {
204          extend();
205        }
206      }
207      return start;
208    }
209
210    /// \brief Move an item down into the proper box.
211    void bubble_down(int index) {
212      if (!upper(data[index].box, data[index].prio)) return;
213      remove(index);
214      int box = findDown(data[index].box, data[index].prio);
215      insert(box, index);
216    }
217
218    /// \brief Find up the proper box for the item with the given prio.
219    int findDown(int start, int pr) {
220      while (upper(start, pr)) {
221        if (--start < 0) throw UnderFlowPriorityError();
222      }
223      return start;
224    }
225
226    /// \brief Find the first not empty box.
227    int findFirst() {
228      int first = 0;
229      while (boxes[first].first == -1) ++first;
230      return first;
231    }
232
233    /// \brief Gives back the minimal prio of the box.
234    int minValue(int box) {
235      int min = data[boxes[box].first].prio;
236      for (int k = boxes[box].first; k != -1; k = data[k].next) {
237        if (data[k].prio < min) min = data[k].prio;
238      }
239      return min;
240    }
241
242    /// \brief Rearrange the items of the heap and makes the
243    /// first box not empty.
244    void moveDown() {
245      int box = findFirst();
246      if (box == 0) return;
247      int min = minValue(box);
248      for (int i = 0; i <= box; ++i) {
249        boxes[i].min = min;
250        min += boxes[i].size;
251      }
252      int curr = boxes[box].first, next;
253      while (curr != -1) {
254        next = data[curr].next;
255        bubble_down(curr);
256        curr = next;
257      }
258    }
259
260    void relocate_last(int index) {
261      if (index != int(data.size()) - 1) {
262        data[index] = data.back();
263        if (data[index].prev != -1) {
264          data[data[index].prev].next = index;
265        } else {
266          boxes[data[index].box].first = index;
267        }
268        if (data[index].next != -1) {
269          data[data[index].next].prev = index;
270        }
271        _iim[data[index].item] = index;
272      }
273      data.pop_back();
274    }
275
276  public:
277
278    /// \brief Insert an item into the heap with the given priority.
279    ///
280    /// Adds \c i to the heap with priority \c p.
281    /// \param i The item to insert.
282    /// \param p The priority of the item.
283    void push(const Item &i, const Prio &p) {
284      int n = data.size();
285      _iim.set(i, n);
286      data.push_back(RadixItem(i, p));
287      while (lower(boxes.size() - 1, p)) {
288        extend();
289      }
290      int box = findDown(boxes.size() - 1, p);
291      insert(box, n);
292    }
293
294    /// \brief Returns the item with minimum priority.
295    ///
296    /// This method returns the item with minimum priority.
297    /// \pre The heap must be nonempty.
298    Item top() const {
299      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
300      return data[boxes[0].first].item;
301    }
302
303    /// \brief Returns the minimum priority.
304    ///
305    /// It returns the minimum priority.
306    /// \pre The heap must be nonempty.
307    Prio prio() const {
308      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
309      return data[boxes[0].first].prio;
310     }
311
312    /// \brief Deletes the item with minimum priority.
313    ///
314    /// This method deletes the item with minimum priority.
315    /// \pre The heap must be non-empty.
316    void pop() {
317      moveDown();
318      int index = boxes[0].first;
319      _iim[data[index].item] = POST_HEAP;
320      remove(index);
321      relocate_last(index);
322    }
323
324    /// \brief Deletes \c i from the heap.
325    ///
326    /// This method deletes item \c i from the heap, if \c i was
327    /// already stored in the heap.
328    /// \param i The item to erase.
329    void erase(const Item &i) {
330      int index = _iim[i];
331      _iim[i] = POST_HEAP;
332      remove(index);
333      relocate_last(index);
334   }
335
336    /// \brief Returns the priority of \c i.
337    ///
338    /// This function returns the priority of item \c i.
339    /// \pre \c i must be in the heap.
340    /// \param i The item.
341    Prio operator[](const Item &i) const {
342      int idx = _iim[i];
343      return data[idx].prio;
344    }
345
346    /// \brief \c i gets to the heap with priority \c p independently
347    /// if \c i was already there.
348    ///
349    /// This method calls \ref push(\c i, \c p) if \c i is not stored
350    /// in the heap and sets the priority of \c i to \c p otherwise.
351    /// It may throw an \e UnderFlowPriorityException.
352    /// \param i The item.
353    /// \param p The priority.
354    void set(const Item &i, const Prio &p) {
355      int idx = _iim[i];
356      if( idx < 0 ) {
357        push(i, p);
358      }
359      else if( p >= data[idx].prio ) {
360        data[idx].prio = p;
361        bubble_up(idx);
362      } else {
363        data[idx].prio = p;
364        bubble_down(idx);
365      }
366    }
367
368
369    /// \brief Decreases the priority of \c i to \c p.
370    ///
371    /// This method decreases the priority of item \c i to \c p.
372    /// \pre \c i must be stored in the heap with priority at least \c p, and
373    /// \c should be greater or equal to the last removed item's priority.
374    /// \param i The item.
375    /// \param p The priority.
376    void decrease(const Item &i, const Prio &p) {
377      int idx = _iim[i];
378      data[idx].prio = p;
379      bubble_down(idx);
380    }
381
382    /// \brief Increases the priority of \c i to \c p.
383    ///
384    /// This method sets the priority of item \c i to \c p.
385    /// \pre \c i must be stored in the heap with priority at most \c p
386    /// \param i The item.
387    /// \param p The priority.
388    void increase(const Item &i, const Prio &p) {
389      int idx = _iim[i];
390      data[idx].prio = p;
391      bubble_up(idx);
392    }
393
394    /// \brief Returns if \c item is in, has already been in, or has
395    /// never been in the heap.
396    ///
397    /// This method returns PRE_HEAP if \c item has never been in the
398    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
399    /// otherwise. In the latter case it is possible that \c item will
400    /// get back to the heap again.
401    /// \param i The item.
402    State state(const Item &i) const {
403      int s = _iim[i];
404      if( s >= 0 ) s = 0;
405      return State(s);
406    }
407
408    /// \brief Sets the state of the \c item in the heap.
409    ///
410    /// Sets the state of the \c item in the heap. It can be used to
411    /// manually clear the heap when it is important to achive the
412    /// better time complexity.
413    /// \param i The item.
414    /// \param st The state. It should not be \c IN_HEAP.
415    void state(const Item& i, State st) {
416      switch (st) {
417      case POST_HEAP:
418      case PRE_HEAP:
419        if (state(i) == IN_HEAP) {
420          erase(i);
421        }
422        _iim[i] = st;
423        break;
424      case IN_HEAP:
425        break;
426      }
427    }
428
429  }; // class RadixHeap
430
431} // namespace lemon
432
433#endif // LEMON_RADIX_HEAP_H
Note: See TracBrowser for help on using the repository browser.