COIN-OR::LEMON - Graph Library

source: lemon/lemon/radix_heap.h @ 758:28cfac049a6a

Last change on this file since 758:28cfac049a6a was 758:28cfac049a6a, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Unify member names in heaps (#299)

The following renamings are made.

Public members:

Private members:

  • bubble_up() -> bubbleUp()
  • bubble_down() -> bubbleDown()
  • second_child() -> secondChild()
  • makeroot() -> makeRoot()
  • relocate_last() -> relocateLast()
  • data -> _data
  • boxes -> _boxes
File size: 12.9 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 heaps
23///\file
24///\brief Radix heap implementation.
25
26#include <vector>
27#include <lemon/error.h>
28
29namespace lemon {
30
31
32  /// \ingroup heaps
33  ///
34  /// \brief Radix heap data structure.
35  ///
36  /// This class implements the \e radix \e heap data structure.
37  /// It practically conforms to the \ref concepts::Heap "heap concept",
38  /// but it has some limitations due its special implementation.
39  /// The type of the priorities must be \c int and the priority of an
40  /// item cannot be decreased under the priority of the last removed item.
41  ///
42  /// \tparam IM A read-writable item map with \c int values, used
43  /// internally to handle the cross references.
44  template <typename IM>
45  class RadixHeap {
46
47  public:
48
49    /// Type of the item-int map.
50    typedef IM ItemIntMap;
51    /// Type of the priorities.
52    typedef int Prio;
53    /// Type of the items stored in the heap.
54    typedef typename ItemIntMap::Key Item;
55
56    /// \brief Exception thrown by RadixHeap.
57    ///
58    /// This exception is thrown when an item is inserted into a
59    /// RadixHeap with a priority smaller than the last erased one.
60    /// \see RadixHeap
61    class PriorityUnderflowError : public Exception {
62    public:
63      virtual const char* what() const throw() {
64        return "lemon::RadixHeap::PriorityUnderflowError";
65      }
66    };
67
68    /// \brief Type to represent the states of the items.
69    ///
70    /// Each item has a state associated to it. It can be "in heap",
71    /// "pre-heap" or "post-heap". The latter two are indifferent from the
72    /// heap's point of view, but may be useful to the user.
73    ///
74    /// The item-int map must be initialized in such way that it assigns
75    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
76    enum State {
77      IN_HEAP = 0,    ///< = 0.
78      PRE_HEAP = -1,  ///< = -1.
79      POST_HEAP = -2  ///< = -2.
80    };
81
82  private:
83
84    struct RadixItem {
85      int prev, next, box;
86      Item item;
87      int prio;
88      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
89    };
90
91    struct RadixBox {
92      int first;
93      int min, size;
94      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
95    };
96
97    std::vector<RadixItem> _data;
98    std::vector<RadixBox> _boxes;
99
100    ItemIntMap &_iim;
101
102  public:
103
104    /// \brief Constructor.
105    ///
106    /// Constructor.
107    /// \param map A map that assigns \c int values to the items.
108    /// It is used internally to handle the cross references.
109    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
110    /// \param minimum The initial minimum value of the heap.
111    /// \param capacity The initial capacity of the heap.
112    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
113      : _iim(map)
114    {
115      _boxes.push_back(RadixBox(minimum, 1));
116      _boxes.push_back(RadixBox(minimum + 1, 1));
117      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
118        extend();
119      }
120    }
121
122    /// \brief The number of items stored in the heap.
123    ///
124    /// This function returns the number of items stored in the heap.
125    int size() const { return _data.size(); }
126
127    /// \brief Check if the heap is empty.
128    ///
129    /// This function returns \c true if the heap is empty.
130    bool empty() const { return _data.empty(); }
131
132    /// \brief Make the heap empty.
133    ///
134    /// This functon makes the heap empty.
135    /// It does not change the cross reference map. If you want to reuse
136    /// a heap that is not surely empty, you should first clear it and
137    /// then you should set the cross reference map to \c PRE_HEAP
138    /// for each item.
139    /// \param minimum The minimum value of the heap.
140    /// \param capacity The capacity of the heap.
141    void clear(int minimum = 0, int capacity = 0) {
142      _data.clear(); _boxes.clear();
143      _boxes.push_back(RadixBox(minimum, 1));
144      _boxes.push_back(RadixBox(minimum + 1, 1));
145      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
146        extend();
147      }
148    }
149
150  private:
151
152    bool upper(int box, Prio pr) {
153      return pr < _boxes[box].min;
154    }
155
156    bool lower(int box, Prio pr) {
157      return pr >= _boxes[box].min + _boxes[box].size;
158    }
159
160    // Remove item from the box list
161    void remove(int index) {
162      if (_data[index].prev >= 0) {
163        _data[_data[index].prev].next = _data[index].next;
164      } else {
165        _boxes[_data[index].box].first = _data[index].next;
166      }
167      if (_data[index].next >= 0) {
168        _data[_data[index].next].prev = _data[index].prev;
169      }
170    }
171
172    // Insert item into the box list
173    void insert(int box, int index) {
174      if (_boxes[box].first == -1) {
175        _boxes[box].first = index;
176        _data[index].next = _data[index].prev = -1;
177      } else {
178        _data[index].next = _boxes[box].first;
179        _data[_boxes[box].first].prev = index;
180        _data[index].prev = -1;
181        _boxes[box].first = index;
182      }
183      _data[index].box = box;
184    }
185
186    // Add a new box to the box list
187    void extend() {
188      int min = _boxes.back().min + _boxes.back().size;
189      int bs = 2 * _boxes.back().size;
190      _boxes.push_back(RadixBox(min, bs));
191    }
192
193    // Move an item up into the proper box.
194    void bubbleUp(int index) {
195      if (!lower(_data[index].box, _data[index].prio)) return;
196      remove(index);
197      int box = findUp(_data[index].box, _data[index].prio);
198      insert(box, index);
199    }
200
201    // Find up the proper box for the item with the given priority
202    int findUp(int start, int pr) {
203      while (lower(start, pr)) {
204        if (++start == int(_boxes.size())) {
205          extend();
206        }
207      }
208      return start;
209    }
210
211    // Move an item down into the proper box
212    void bubbleDown(int index) {
213      if (!upper(_data[index].box, _data[index].prio)) return;
214      remove(index);
215      int box = findDown(_data[index].box, _data[index].prio);
216      insert(box, index);
217    }
218
219    // Find down the proper box for the item with the given priority
220    int findDown(int start, int pr) {
221      while (upper(start, pr)) {
222        if (--start < 0) throw PriorityUnderflowError();
223      }
224      return start;
225    }
226
227    // Find the first non-empty box
228    int findFirst() {
229      int first = 0;
230      while (_boxes[first].first == -1) ++first;
231      return first;
232    }
233
234    // Gives back the minimum priority of the given box
235    int minValue(int box) {
236      int min = _data[_boxes[box].first].prio;
237      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
238        if (_data[k].prio < min) min = _data[k].prio;
239      }
240      return min;
241    }
242
243    // Rearrange the items of the heap and make the first box non-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        bubbleDown(curr);
256        curr = next;
257      }
258    }
259
260    void relocateLast(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    /// This function inserts the given item into the heap with the
281    /// given priority.
282    /// \param i The item to insert.
283    /// \param p The priority of the item.
284    /// \pre \e i must not be stored in the heap.
285    /// \warning This method may throw an \c UnderFlowPriorityException.
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 Return the item having minimum priority.
298    ///
299    /// This function returns the item having minimum priority.
300    /// \pre The heap must be non-empty.
301    Item top() const {
302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
303      return _data[_boxes[0].first].item;
304    }
305
306    /// \brief The minimum priority.
307    ///
308    /// This function returns the minimum priority.
309    /// \pre The heap must be non-empty.
310    Prio prio() const {
311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
312      return _data[_boxes[0].first].prio;
313     }
314
315    /// \brief Remove the item having minimum priority.
316    ///
317    /// This function removes the item having 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      relocateLast(index);
325    }
326
327    /// \brief Remove the given item from the heap.
328    ///
329    /// This function removes the given item from the heap if it is
330    /// already stored.
331    /// \param i The item to delete.
332    /// \pre \e i must be in the heap.
333    void erase(const Item &i) {
334      int index = _iim[i];
335      _iim[i] = POST_HEAP;
336      remove(index);
337      relocateLast(index);
338   }
339
340    /// \brief The priority of the given item.
341    ///
342    /// This function returns the priority of the given item.
343    /// \param i The item.
344    /// \pre \e i must be in the heap.
345    Prio operator[](const Item &i) const {
346      int idx = _iim[i];
347      return _data[idx].prio;
348    }
349
350    /// \brief Set the priority of an item or insert it, if it is
351    /// not stored in the heap.
352    ///
353    /// This method sets the priority of the given item if it is
354    /// already stored in the heap. Otherwise it inserts the given
355    /// item into the heap with the given priority.
356    /// \param i The item.
357    /// \param p The priority.
358    /// \pre \e i must be in the heap.
359    /// \warning This method may throw an \c UnderFlowPriorityException.
360    void set(const Item &i, const Prio &p) {
361      int idx = _iim[i];
362      if( idx < 0 ) {
363        push(i, p);
364      }
365      else if( p >= _data[idx].prio ) {
366        _data[idx].prio = p;
367        bubbleUp(idx);
368      } else {
369        _data[idx].prio = p;
370        bubbleDown(idx);
371      }
372    }
373
374    /// \brief Decrease the priority of an item to the given value.
375    ///
376    /// This function decreases the priority of an item to the given value.
377    /// \param i The item.
378    /// \param p The priority.
379    /// \pre \e i must be stored in the heap with priority at least \e p.
380    /// \warning This method may throw an \c UnderFlowPriorityException.
381    void decrease(const Item &i, const Prio &p) {
382      int idx = _iim[i];
383      _data[idx].prio = p;
384      bubbleDown(idx);
385    }
386
387    /// \brief Increase the priority of an item to the given value.
388    ///
389    /// This function increases the priority of an item to the given value.
390    /// \param i The item.
391    /// \param p The priority.
392    /// \pre \e i must be stored in the heap with priority at most \e p.
393    void increase(const Item &i, const Prio &p) {
394      int idx = _iim[i];
395      _data[idx].prio = p;
396      bubbleUp(idx);
397    }
398
399    /// \brief Return the state of an item.
400    ///
401    /// This method returns \c PRE_HEAP if the given item has never
402    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
403    /// and \c POST_HEAP otherwise.
404    /// In the latter case it is possible that the item will get back
405    /// to the heap again.
406    /// \param i The item.
407    State state(const Item &i) const {
408      int s = _iim[i];
409      if( s >= 0 ) s = 0;
410      return State(s);
411    }
412
413    /// \brief Set the state of an item in the heap.
414    ///
415    /// This function sets the state of the given item in the heap.
416    /// It can be used to manually clear the heap when it is important
417    /// to achive better time complexity.
418    /// \param i The item.
419    /// \param st The state. It should not be \c IN_HEAP.
420    void state(const Item& i, State st) {
421      switch (st) {
422      case POST_HEAP:
423      case PRE_HEAP:
424        if (state(i) == IN_HEAP) {
425          erase(i);
426        }
427        _iim[i] = st;
428        break;
429      case IN_HEAP:
430        break;
431      }
432    }
433
434  }; // class RadixHeap
435
436} // namespace lemon
437
438#endif // LEMON_RADIX_HEAP_H
Note: See TracBrowser for help on using the repository browser.