COIN-OR::LEMON - Graph Library

source: lemon/lemon/radix_heap.h @ 1298:a78e5b779b69

Last change on this file since 1298:a78e5b779b69 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
RevLine 
[728]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
[757]22///\ingroup heaps
[728]23///\file
[756]24///\brief Radix heap implementation.
[728]25
26#include <vector>
27#include <lemon/error.h>
28
29namespace lemon {
30
31
[757]32  /// \ingroup heaps
[728]33  ///
[756]34  /// \brief Radix heap data structure.
[728]35  ///
[756]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.
[728]41  ///
[756]42  /// \tparam IM A read-writable item map with \c int values, used
43  /// internally to handle the cross references.
[730]44  template <typename IM>
[728]45  class RadixHeap {
46
47  public:
[756]48
49    /// Type of the item-int map.
50    typedef IM ItemIntMap;
51    /// Type of the priorities.
[728]52    typedef int Prio;
[756]53    /// Type of the items stored in the heap.
54    typedef typename ItemIntMap::Key Item;
[728]55
56    /// \brief Exception thrown by RadixHeap.
57    ///
[756]58    /// This exception is thrown when an item is inserted into a
59    /// RadixHeap with a priority smaller than the last erased one.
[728]60    /// \see RadixHeap
[758]61    class PriorityUnderflowError : public Exception {
[728]62    public:
63      virtual const char* what() const throw() {
[758]64        return "lemon::RadixHeap::PriorityUnderflowError";
[728]65      }
66    };
67
[756]68    /// \brief Type to represent the states of the items.
[728]69    ///
[756]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
[728]72    /// heap's point of view, but may be useful to the user.
73    ///
[756]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.
[728]76    enum State {
[756]77      IN_HEAP = 0,    ///< = 0.
78      PRE_HEAP = -1,  ///< = -1.
79      POST_HEAP = -2  ///< = -2.
[728]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
[758]97    std::vector<RadixItem> _data;
98    std::vector<RadixBox> _boxes;
[728]99
[730]100    ItemIntMap &_iim;
[728]101
[756]102  public:
[728]103
[756]104    /// \brief Constructor.
[728]105    ///
[756]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    {
[758]115      _boxes.push_back(RadixBox(minimum, 1));
116      _boxes.push_back(RadixBox(minimum + 1, 1));
117      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
[728]118        extend();
119      }
120    }
121
[756]122    /// \brief The number of items stored in the heap.
[728]123    ///
[756]124    /// This function returns the number of items stored in the heap.
[758]125    int size() const { return _data.size(); }
[756]126
127    /// \brief Check if the heap is empty.
[728]128    ///
[756]129    /// This function returns \c true if the heap is empty.
[758]130    bool empty() const { return _data.empty(); }
[728]131
[756]132    /// \brief Make the heap empty.
[728]133    ///
[756]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) {
[758]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)) {
[728]146        extend();
147      }
148    }
149
150  private:
151
152    bool upper(int box, Prio pr) {
[758]153      return pr < _boxes[box].min;
[728]154    }
155
156    bool lower(int box, Prio pr) {
[758]157      return pr >= _boxes[box].min + _boxes[box].size;
[728]158    }
159
[756]160    // Remove item from the box list
[728]161    void remove(int index) {
[758]162      if (_data[index].prev >= 0) {
163        _data[_data[index].prev].next = _data[index].next;
[728]164      } else {
[758]165        _boxes[_data[index].box].first = _data[index].next;
[728]166      }
[758]167      if (_data[index].next >= 0) {
168        _data[_data[index].next].prev = _data[index].prev;
[728]169      }
170    }
171
[756]172    // Insert item into the box list
[728]173    void insert(int box, int index) {
[758]174      if (_boxes[box].first == -1) {
175        _boxes[box].first = index;
176        _data[index].next = _data[index].prev = -1;
[728]177      } else {
[758]178        _data[index].next = _boxes[box].first;
179        _data[_boxes[box].first].prev = index;
180        _data[index].prev = -1;
181        _boxes[box].first = index;
[728]182      }
[758]183      _data[index].box = box;
[728]184    }
185
[756]186    // Add a new box to the box list
[728]187    void extend() {
[758]188      int min = _boxes.back().min + _boxes.back().size;
189      int bs = 2 * _boxes.back().size;
190      _boxes.push_back(RadixBox(min, bs));
[728]191    }
192
[756]193    // Move an item up into the proper box.
[758]194    void bubbleUp(int index) {
195      if (!lower(_data[index].box, _data[index].prio)) return;
[728]196      remove(index);
[758]197      int box = findUp(_data[index].box, _data[index].prio);
[728]198      insert(box, index);
199    }
200
[756]201    // Find up the proper box for the item with the given priority
[728]202    int findUp(int start, int pr) {
203      while (lower(start, pr)) {
[758]204        if (++start == int(_boxes.size())) {
[728]205          extend();
206        }
207      }
208      return start;
209    }
210
[756]211    // Move an item down into the proper box
[758]212    void bubbleDown(int index) {
213      if (!upper(_data[index].box, _data[index].prio)) return;
[728]214      remove(index);
[758]215      int box = findDown(_data[index].box, _data[index].prio);
[728]216      insert(box, index);
217    }
218
[756]219    // Find down the proper box for the item with the given priority
[728]220    int findDown(int start, int pr) {
221      while (upper(start, pr)) {
[758]222        if (--start < 0) throw PriorityUnderflowError();
[728]223      }
224      return start;
225    }
226
[756]227    // Find the first non-empty box
[728]228    int findFirst() {
229      int first = 0;
[758]230      while (_boxes[first].first == -1) ++first;
[728]231      return first;
232    }
233
[756]234    // Gives back the minimum priority of the given box
[728]235    int minValue(int box) {
[758]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;
[728]239      }
240      return min;
241    }
242
[756]243    // Rearrange the items of the heap and make the first box non-empty
[728]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) {
[758]249        _boxes[i].min = min;
250        min += _boxes[i].size;
[728]251      }
[758]252      int curr = _boxes[box].first, next;
[728]253      while (curr != -1) {
[758]254        next = _data[curr].next;
255        bubbleDown(curr);
[728]256        curr = next;
257      }
258    }
259
[758]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;
[728]265        } else {
[758]266          _boxes[_data[index].box].first = index;
[728]267        }
[758]268        if (_data[index].next != -1) {
269          _data[_data[index].next].prev = index;
[728]270        }
[758]271        _iim[_data[index].item] = index;
[728]272      }
[758]273      _data.pop_back();
[728]274    }
275
276  public:
277
278    /// \brief Insert an item into the heap with the given priority.
279    ///
[756]280    /// This function inserts the given item into the heap with the
281    /// given priority.
[728]282    /// \param i The item to insert.
283    /// \param p The priority of the item.
[756]284    /// \pre \e i must not be stored in the heap.
285    /// \warning This method may throw an \c UnderFlowPriorityException.
[728]286    void push(const Item &i, const Prio &p) {
[758]287      int n = _data.size();
[730]288      _iim.set(i, n);
[758]289      _data.push_back(RadixItem(i, p));
290      while (lower(_boxes.size() - 1, p)) {
[728]291        extend();
292      }
[758]293      int box = findDown(_boxes.size() - 1, p);
[728]294      insert(box, n);
295    }
296
[756]297    /// \brief Return the item having minimum priority.
[728]298    ///
[756]299    /// This function returns the item having minimum priority.
300    /// \pre The heap must be non-empty.
[728]301    Item top() const {
302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
[758]303      return _data[_boxes[0].first].item;
[728]304    }
305
[756]306    /// \brief The minimum priority.
[728]307    ///
[756]308    /// This function returns the minimum priority.
309    /// \pre The heap must be non-empty.
[728]310    Prio prio() const {
311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
[758]312      return _data[_boxes[0].first].prio;
[728]313     }
314
[756]315    /// \brief Remove the item having minimum priority.
[728]316    ///
[756]317    /// This function removes the item having minimum priority.
[728]318    /// \pre The heap must be non-empty.
319    void pop() {
320      moveDown();
[758]321      int index = _boxes[0].first;
322      _iim[_data[index].item] = POST_HEAP;
[728]323      remove(index);
[758]324      relocateLast(index);
[728]325    }
326
[756]327    /// \brief Remove the given item from the heap.
[728]328    ///
[756]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.
[728]333    void erase(const Item &i) {
[730]334      int index = _iim[i];
335      _iim[i] = POST_HEAP;
[728]336      remove(index);
[758]337      relocateLast(index);
[728]338   }
339
[756]340    /// \brief The priority of the given item.
[728]341    ///
[756]342    /// This function returns the priority of the given item.
[728]343    /// \param i The item.
[756]344    /// \pre \e i must be in the heap.
[728]345    Prio operator[](const Item &i) const {
[730]346      int idx = _iim[i];
[758]347      return _data[idx].prio;
[728]348    }
349
[756]350    /// \brief Set the priority of an item or insert it, if it is
351    /// not stored in the heap.
[728]352    ///
[756]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.
[728]356    /// \param i The item.
357    /// \param p The priority.
[756]358    /// \pre \e i must be in the heap.
359    /// \warning This method may throw an \c UnderFlowPriorityException.
[728]360    void set(const Item &i, const Prio &p) {
[730]361      int idx = _iim[i];
[728]362      if( idx < 0 ) {
363        push(i, p);
364      }
[758]365      else if( p >= _data[idx].prio ) {
366        _data[idx].prio = p;
367        bubbleUp(idx);
[728]368      } else {
[758]369        _data[idx].prio = p;
370        bubbleDown(idx);
[728]371      }
372    }
373
[756]374    /// \brief Decrease the priority of an item to the given value.
[728]375    ///
[756]376    /// This function decreases the priority of an item to the given value.
[728]377    /// \param i The item.
378    /// \param p The priority.
[756]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.
[728]381    void decrease(const Item &i, const Prio &p) {
[730]382      int idx = _iim[i];
[758]383      _data[idx].prio = p;
384      bubbleDown(idx);
[728]385    }
386
[756]387    /// \brief Increase the priority of an item to the given value.
[728]388    ///
[756]389    /// This function increases the priority of an item to the given value.
[728]390    /// \param i The item.
391    /// \param p The priority.
[756]392    /// \pre \e i must be stored in the heap with priority at most \e p.
[728]393    void increase(const Item &i, const Prio &p) {
[730]394      int idx = _iim[i];
[758]395      _data[idx].prio = p;
396      bubbleUp(idx);
[728]397    }
398
[756]399    /// \brief Return the state of an item.
[728]400    ///
[756]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.
[728]406    /// \param i The item.
407    State state(const Item &i) const {
[730]408      int s = _iim[i];
[728]409      if( s >= 0 ) s = 0;
410      return State(s);
411    }
412
[756]413    /// \brief Set the state of an item in the heap.
[728]414    ///
[756]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.
[728]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        }
[730]427        _iim[i] = st;
[728]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.