COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/radix_heap.h @ 902:79fab87ee483

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