COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_heap.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 12.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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 _ItemIntMap A read and writable Item int map, used internally
45  /// to handle the cross references.
46  ///
47  /// \see BinHeap
48  /// \see Dijkstra
49  /// \author Balazs Dezso
50
51  template <typename _ItemIntMap>
52  class RadixHeap {
53
54  public:
55    typedef typename _ItemIntMap::Key Item;
56    typedef int Prio;
57    typedef _ItemIntMap ItemIntMap;
58
59    /// \brief Exception thrown by RadixHeap.
60    /// 
61    /// This Exception is thrown when a smaller priority
62    /// is inserted into the \e RadixHeap then the last time erased.
63    /// \see RadixHeap
64    /// \author Balazs Dezso
65   
66    class UnderFlowPriorityError : public RuntimeError {
67    public:
68      virtual const char* what() const throw() {
69        return "lemon::RadixHeap::UnderFlowPriorityError";
70      } 
71    };
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 latter two are indifferent from the
77    /// heap's point of view, but may be useful to the user.
78    ///
79    /// The ItemIntMap \e 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 {
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    ///
113    /// \param _iim It should be given to the constructor, since it is used
114    /// internally to handle the cross references. The value of the map
115    /// should be PRE_HEAP (-1) for each element.
116    ///
117    /// \param minimal The initial minimal value of the heap.
118    /// \param capacity It determines the initial capacity of the heap.
119    RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
120      : iim(_iim) {
121      boxes.push_back(RadixBox(minimal, 1));
122      boxes.push_back(RadixBox(minimal + 1, 1));
123      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
124        extend();
125      }
126    }
127
128    /// The number of items stored in the heap.
129    ///
130    /// \brief Returns the number of items stored in the heap.
131    int size() const { return data.size(); }
132    /// \brief Checks if the heap stores no items.
133    ///
134    /// Returns \c true if and only if the heap stores no items.
135    bool empty() const { return data.empty(); }
136
137    /// \brief Make empty this heap.
138    ///
139    /// Make empty this heap. It does not change the cross reference
140    /// map.  If you want to reuse a heap what is not surely empty you
141    /// should first clear the heap and after that you should set the
142    /// cross reference map for each item to \c PRE_HEAP.
143    void clear(int minimal = 0, int capacity = 0) {
144      data.clear(); boxes.clear();
145      boxes.push_back(RadixBox(minimal, 1));
146      boxes.push_back(RadixBox(minimal + 1, 1));
147      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
148        extend();
149      }
150    }
151
152  private:
153
154    bool upper(int box, Prio pr) {
155      return pr < boxes[box].min;
156    }
157
158    bool lower(int box, Prio pr) {
159      return pr >= boxes[box].min + boxes[box].size;
160    }
161
162    /// \brief Remove item from the box list.
163    void remove(int index) {
164      if (data[index].prev >= 0) {
165        data[data[index].prev].next = data[index].next;
166      } else {
167        boxes[data[index].box].first = data[index].next;
168      }
169      if (data[index].next >= 0) {
170        data[data[index].next].prev = data[index].prev;
171      }
172    }
173
174    /// \brief Insert item into the box list.
175    void insert(int box, int index) {
176      if (boxes[box].first == -1) {
177        boxes[box].first = index;
178        data[index].next = data[index].prev = -1;
179      } else {
180        data[index].next = boxes[box].first;
181        data[boxes[box].first].prev = index;
182        data[index].prev = -1;
183        boxes[box].first = index;
184      }
185      data[index].box = box;
186    }
187
188    /// \brief Add a new box to the box list.
189    void extend() {
190      int min = boxes.back().min + boxes.back().size;
191      int bs = 2 * boxes.back().size;
192      boxes.push_back(RadixBox(min, bs));
193    }
194
195    /// \brief Move an item up into the proper box.
196    void bubble_up(int index) {
197      if (!lower(data[index].box, data[index].prio)) return;
198      remove(index);
199      int box = findUp(data[index].box, data[index].prio);
200      insert(box, index);     
201    }
202
203    /// \brief Find up the proper box for the item with the given prio.
204    int findUp(int start, int pr) {
205      while (lower(start, pr)) {
206        if (++start == int(boxes.size())) {
207          extend();
208        }
209      }
210      return start;
211    }
212
213    /// \brief Move an item down into the proper box.
214    void bubble_down(int index) {
215      if (!upper(data[index].box, data[index].prio)) return;
216      remove(index);
217      int box = findDown(data[index].box, data[index].prio);
218      insert(box, index);
219    }
220
221    /// \brief Find up the proper box for the item with the given prio.
222    int findDown(int start, int pr) {
223      while (upper(start, pr)) {
224        if (--start < 0) throw UnderFlowPriorityError();
225      }
226      return start;
227    }
228
229    /// \brief Find the first not empty box.
230    int findFirst() {
231      int first = 0;
232      while (boxes[first].first == -1) ++first;
233      return first;
234    }
235
236    /// \brief Gives back the minimal prio of the box.
237    int minValue(int box) {
238      int min = data[boxes[box].first].prio;
239      for (int k = boxes[box].first; k != -1; k = data[k].next) {
240        if (data[k].prio < min) min = data[k].prio;
241      }
242      return min;
243    }
244
245    /// \brief Rearrange the items of the heap and makes the
246    /// first box not empty.
247    void moveDown() {
248      int box = findFirst();
249      if (box == 0) return;
250      int min = minValue(box);
251      for (int i = 0; i <= box; ++i) {
252        boxes[i].min = min;
253        min += boxes[i].size;
254      }
255      int curr = boxes[box].first, next;
256      while (curr != -1) {
257        next = data[curr].next;
258        bubble_down(curr);
259        curr = next;
260      }     
261    }
262
263    void relocate_last(int index) {
264      if (index != int(data.size()) - 1) {
265        data[index] = data.back();
266        if (data[index].prev != -1) {
267          data[data[index].prev].next = index;
268        } else {
269          boxes[data[index].box].first = index;
270        }
271        if (data[index].next != -1) {
272          data[data[index].next].prev = index;
273        }
274        iim[data[index].item] = index;
275      }
276      data.pop_back();
277    }
278
279  public:
280
281    /// \brief Insert an item into the heap with the given priority.
282    ///   
283    /// Adds \c i to the heap with priority \c p.
284    /// \param i The item to insert.
285    /// \param p The priority of the item.
286    void push(const Item &i, const Prio &p) {
287      int n = data.size();
288      iim.set(i, n);
289      data.push_back(RadixItem(i, p));
290      while (lower(boxes.size() - 1, p)) {
291        extend();
292      }
293      int box = findDown(boxes.size() - 1, p);
294      insert(box, n);
295    }
296
297    /// \brief Returns the item with minimum priority.
298    ///
299    /// This method returns the item with minimum priority. 
300    /// \pre The heap must be nonempty. 
301    Item top() const {
302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
303      return data[boxes[0].first].item;
304    }
305
306    /// \brief Returns the minimum priority.
307    ///
308    /// It returns the minimum priority.
309    /// \pre The heap must be nonempty.
310    Prio prio() const {
311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
312      return data[boxes[0].first].prio;
313     }
314
315    /// \brief Deletes the item with minimum priority.
316    ///
317    /// This method deletes the item with minimum priority.
318    /// \pre The heap must be non-empty. 
319    void pop() {
320      moveDown();
321      int index = boxes[0].first;
322      iim[data[index].item] = POST_HEAP;
323      remove(index);
324      relocate_last(index);
325    }
326
327    /// \brief Deletes \c i from the heap.
328    ///
329    /// This method deletes item \c i from the heap, if \c i was
330    /// already stored in the heap.
331    /// \param i The item to erase.
332    void erase(const Item &i) {
333      int index = iim[i];
334      iim[i] = POST_HEAP;
335      remove(index);
336      relocate_last(index);
337   }
338
339    /// \brief Returns the priority of \c i.
340    ///
341    /// This function returns the priority of item \c i. 
342    /// \pre \c i must be in the heap.
343    /// \param i The item.
344    Prio operator[](const Item &i) const {
345      int idx = iim[i];
346      return data[idx].prio;
347    }
348
349    /// \brief \c i gets to the heap with priority \c p independently
350    /// if \c i was already there.
351    ///
352    /// This method calls \ref push(\c i, \c p) if \c i is not stored
353    /// in the heap and sets the priority of \c i to \c p otherwise.
354    /// It may throw an \e UnderFlowPriorityException.
355    /// \param i The item.
356    /// \param p The priority.
357    void set(const Item &i, const Prio &p) {
358      int idx = iim[i];
359      if( idx < 0 ) {
360        push(i, p);
361      }
362      else if( p >= data[idx].prio ) {
363        data[idx].prio = p;
364        bubble_up(idx);
365      } else {
366        data[idx].prio = p;
367        bubble_down(idx);
368      }
369    }
370
371
372    /// \brief Decreases the priority of \c i to \c p.
373    ///
374    /// This method decreases the priority of item \c i to \c p.
375    /// \pre \c i must be stored in the heap with priority at least \c p, and
376    /// \c should be greater or equal to the last removed item's priority.
377    /// \param i The item.
378    /// \param p The priority.
379    void decrease(const Item &i, const Prio &p) {
380      int idx = iim[i];
381      data[idx].prio = p;
382      bubble_down(idx);
383    }
384
385    /// \brief Increases the priority of \c i to \c p.
386    ///
387    /// This method sets the priority of item \c i to \c p.
388    /// \pre \c i must be stored in the heap with priority at most \c p
389    /// \param i The item.
390    /// \param p The priority.
391    void increase(const Item &i, const Prio &p) {
392      int idx = iim[i];
393      data[idx].prio = p;
394      bubble_up(idx);
395    }
396
397    /// \brief Returns if \c item is in, has already been in, or has
398    /// never been in the heap.
399    ///
400    /// This method returns PRE_HEAP if \c item has never been in the
401    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
402    /// otherwise. In the latter case it is possible that \c item will
403    /// get back to the heap again.
404    /// \param i The item.
405    State state(const Item &i) const {
406      int s = iim[i];
407      if( s >= 0 ) s = 0;
408      return State(s);
409    }
410
411    /// \brief Sets the state of the \c item in the heap.
412    ///
413    /// Sets the state of the \c item in the heap. It can be used to
414    /// manually clear the heap when it is important to achive the
415    /// better time complexity.
416    /// \param i The item.
417    /// \param st The state. It should not be \c IN_HEAP.
418    void state(const Item& i, State st) {
419      switch (st) {
420      case POST_HEAP:
421      case PRE_HEAP:
422        if (state(i) == IN_HEAP) {
423          erase(i);
424        }
425        iim[i] = st;
426        break;
427      case IN_HEAP:
428        break;
429      }
430    }
431
432  }; // class RadixHeap
433
434} // namespace lemon
435
436#endif // LEMON_RADIX_HEAP_H
Note: See TracBrowser for help on using the repository browser.