COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bucket_heap.h @ 711:28cfac049a6a

Last change on this file since 711:28cfac049a6a 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: 17.3 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_BUCKET_HEAP_H
20#define LEMON_BUCKET_HEAP_H
21
[710]22///\ingroup heaps
[681]23///\file
[709]24///\brief Bucket heap implementation.
[681]25
26#include <vector>
27#include <utility>
28#include <functional>
29
30namespace lemon {
31
[682]32  namespace _bucket_heap_bits {
33
[683]34    template <bool MIN>
[682]35    struct DirectionTraits {
36      static bool less(int left, int right) {
37        return left < right;
38      }
39      static void increase(int& value) {
40        ++value;
41      }
42    };
43
44    template <>
45    struct DirectionTraits<false> {
46      static bool less(int left, int right) {
47        return left > right;
48      }
49      static void increase(int& value) {
50        --value;
51      }
52    };
53
54  }
55
[710]56  /// \ingroup heaps
[681]57  ///
[709]58  /// \brief Bucket heap data structure.
[681]59  ///
[709]60  /// This class implements the \e bucket \e heap data structure.
61  /// It practically conforms to the \ref concepts::Heap "heap concept",
62  /// but it has some limitations.
[681]63  ///
[709]64  /// The bucket heap is a very simple structure. It can store only
65  /// \c int priorities and it maintains a list of items for each priority
66  /// in the range <tt>[0..C)</tt>. So it should only be used when the
67  /// priorities are small. It is not intended to use as a Dijkstra heap.
68  ///
69  /// \tparam IM A read-writable item map with \c int values, used
70  /// internally to handle the cross references.
71  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
72  /// The default is \e min-heap. If this parameter is set to \c false,
73  /// then the comparison is reversed, so the top(), prio() and pop()
74  /// functions deal with the item having maximum priority instead of the
75  /// minimum.
76  ///
77  /// \sa SimpleBucketHeap
[683]78  template <typename IM, bool MIN = true>
[681]79  class BucketHeap {
80
81  public:
[709]82
83    /// Type of the item-int map.
84    typedef IM ItemIntMap;
85    /// Type of the priorities.
[681]86    typedef int Prio;
[709]87    /// Type of the items stored in the heap.
88    typedef typename ItemIntMap::Key Item;
89    /// Type of the item-priority pairs.
90    typedef std::pair<Item,Prio> Pair;
[681]91
[682]92  private:
93
[683]94    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
[682]95
96  public:
97
[709]98    /// \brief Type to represent the states of the items.
[681]99    ///
[709]100    /// Each item has a state associated to it. It can be "in heap",
101    /// "pre-heap" or "post-heap". The latter two are indifferent from the
[681]102    /// heap's point of view, but may be useful to the user.
103    ///
[683]104    /// The item-int map must be initialized in such way that it assigns
105    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
[681]106    enum State {
[683]107      IN_HEAP = 0,    ///< = 0.
108      PRE_HEAP = -1,  ///< = -1.
109      POST_HEAP = -2  ///< = -2.
[681]110    };
111
112  public:
[709]113
114    /// \brief Constructor.
[681]115    ///
[709]116    /// Constructor.
117    /// \param map A map that assigns \c int values to the items.
118    /// It is used internally to handle the cross references.
119    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
[683]120    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
[681]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.
[683]125    int size() const { return _data.size(); }
[681]126
[709]127    /// \brief Check if the heap is empty.
[681]128    ///
[709]129    /// This function returns \c true if the heap is empty.
[683]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.
[681]139    void clear() {
[683]140      _data.clear(); _first.clear(); _minimum = 0;
[681]141    }
142
143  private:
144
[711]145    void relocateLast(int idx) {
[683]146      if (idx + 1 < int(_data.size())) {
147        _data[idx] = _data.back();
148        if (_data[idx].prev != -1) {
149          _data[_data[idx].prev].next = idx;
[681]150        } else {
[683]151          _first[_data[idx].value] = idx;
[681]152        }
[683]153        if (_data[idx].next != -1) {
154          _data[_data[idx].next].prev = idx;
[681]155        }
[683]156        _iim[_data[idx].item] = idx;
[681]157      }
[683]158      _data.pop_back();
[681]159    }
160
161    void unlace(int idx) {
[683]162      if (_data[idx].prev != -1) {
163        _data[_data[idx].prev].next = _data[idx].next;
[681]164      } else {
[683]165        _first[_data[idx].value] = _data[idx].next;
[681]166      }
[683]167      if (_data[idx].next != -1) {
168        _data[_data[idx].next].prev = _data[idx].prev;
[681]169      }
170    }
171
172    void lace(int idx) {
[683]173      if (int(_first.size()) <= _data[idx].value) {
174        _first.resize(_data[idx].value + 1, -1);
[681]175      }
[683]176      _data[idx].next = _first[_data[idx].value];
177      if (_data[idx].next != -1) {
178        _data[_data[idx].next].prev = idx;
[681]179      }
[683]180      _first[_data[idx].value] = idx;
181      _data[idx].prev = -1;
[681]182    }
183
184  public:
[709]185
[681]186    /// \brief Insert a pair of item and priority into the heap.
187    ///
[709]188    /// This function inserts \c p.first to the heap with priority
189    /// \c p.second.
[681]190    /// \param p The pair to insert.
[709]191    /// \pre \c p.first must not be stored in the heap.
[681]192    void push(const Pair& p) {
193      push(p.first, p.second);
194    }
195
196    /// \brief Insert an item into the heap with the given priority.
197    ///
[709]198    /// This function inserts the given item into the heap with the
199    /// given priority.
[681]200    /// \param i The item to insert.
201    /// \param p The priority of the item.
[709]202    /// \pre \e i must not be stored in the heap.
[681]203    void push(const Item &i, const Prio &p) {
[683]204      int idx = _data.size();
205      _iim[i] = idx;
206      _data.push_back(BucketItem(i, p));
[681]207      lace(idx);
[683]208      if (Direction::less(p, _minimum)) {
209        _minimum = p;
[681]210      }
211    }
212
[709]213    /// \brief Return the item having minimum priority.
[681]214    ///
[709]215    /// This function returns the item having minimum priority.
216    /// \pre The heap must be non-empty.
[681]217    Item top() const {
[683]218      while (_first[_minimum] == -1) {
219        Direction::increase(_minimum);
[681]220      }
[683]221      return _data[_first[_minimum]].item;
[681]222    }
223
[709]224    /// \brief The minimum priority.
[681]225    ///
[709]226    /// This function returns the minimum priority.
227    /// \pre The heap must be non-empty.
[681]228    Prio prio() const {
[683]229      while (_first[_minimum] == -1) {
230        Direction::increase(_minimum);
[681]231      }
[683]232      return _minimum;
[681]233    }
234
[709]235    /// \brief Remove the item having minimum priority.
[681]236    ///
[709]237    /// This function removes the item having minimum priority.
[681]238    /// \pre The heap must be non-empty.
239    void pop() {
[683]240      while (_first[_minimum] == -1) {
241        Direction::increase(_minimum);
[681]242      }
[683]243      int idx = _first[_minimum];
244      _iim[_data[idx].item] = -2;
[681]245      unlace(idx);
[711]246      relocateLast(idx);
[681]247    }
248
[709]249    /// \brief Remove the given item from the heap.
[681]250    ///
[709]251    /// This function removes the given item from the heap if it is
252    /// already stored.
253    /// \param i The item to delete.
254    /// \pre \e i must be in the heap.
[681]255    void erase(const Item &i) {
[683]256      int idx = _iim[i];
257      _iim[_data[idx].item] = -2;
[681]258      unlace(idx);
[711]259      relocateLast(idx);
[681]260    }
261
[709]262    /// \brief The priority of the given item.
[681]263    ///
[709]264    /// This function returns the priority of the given item.
[681]265    /// \param i The item.
[709]266    /// \pre \e i must be in the heap.
[681]267    Prio operator[](const Item &i) const {
[683]268      int idx = _iim[i];
269      return _data[idx].value;
[681]270    }
271
[709]272    /// \brief Set the priority of an item or insert it, if it is
273    /// not stored in the heap.
[681]274    ///
[709]275    /// This method sets the priority of the given item if it is
276    /// already stored in the heap. Otherwise it inserts the given
277    /// item into the heap with the given priority.
[681]278    /// \param i The item.
279    /// \param p The priority.
280    void set(const Item &i, const Prio &p) {
[683]281      int idx = _iim[i];
[681]282      if (idx < 0) {
[682]283        push(i, p);
[683]284      } else if (Direction::less(p, _data[idx].value)) {
[682]285        decrease(i, p);
286      } else {
[681]287        increase(i, p);
288      }
289    }
290
[709]291    /// \brief Decrease the priority of an item to the given value.
[681]292    ///
[709]293    /// This function decreases the priority of an item to the given value.
[681]294    /// \param i The item.
295    /// \param p The priority.
[709]296    /// \pre \e i must be stored in the heap with priority at least \e p.
[681]297    void decrease(const Item &i, const Prio &p) {
[683]298      int idx = _iim[i];
[681]299      unlace(idx);
[683]300      _data[idx].value = p;
301      if (Direction::less(p, _minimum)) {
302        _minimum = p;
[681]303      }
304      lace(idx);
305    }
306
[709]307    /// \brief Increase the priority of an item to the given value.
[681]308    ///
[709]309    /// This function increases the priority of an item to the given value.
[681]310    /// \param i The item.
311    /// \param p The priority.
[709]312    /// \pre \e i must be stored in the heap with priority at most \e p.
[681]313    void increase(const Item &i, const Prio &p) {
[683]314      int idx = _iim[i];
[681]315      unlace(idx);
[683]316      _data[idx].value = p;
[681]317      lace(idx);
318    }
319
[709]320    /// \brief Return the state of an item.
[681]321    ///
[709]322    /// This method returns \c PRE_HEAP if the given item has never
323    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
324    /// and \c POST_HEAP otherwise.
325    /// In the latter case it is possible that the item will get back
326    /// to the heap again.
[681]327    /// \param i The item.
328    State state(const Item &i) const {
[683]329      int idx = _iim[i];
[681]330      if (idx >= 0) idx = 0;
331      return State(idx);
332    }
333
[709]334    /// \brief Set the state of an item in the heap.
[681]335    ///
[709]336    /// This function sets the state of the given item in the heap.
337    /// It can be used to manually clear the heap when it is important
338    /// to achive better time complexity.
[681]339    /// \param i The item.
340    /// \param st The state. It should not be \c IN_HEAP.
341    void state(const Item& i, State st) {
342      switch (st) {
343      case POST_HEAP:
344      case PRE_HEAP:
345        if (state(i) == IN_HEAP) {
346          erase(i);
347        }
[683]348        _iim[i] = st;
[681]349        break;
350      case IN_HEAP:
351        break;
352      }
353    }
354
355  private:
356
357    struct BucketItem {
358      BucketItem(const Item& _item, int _value)
359        : item(_item), value(_value) {}
360
361      Item item;
362      int value;
363
364      int prev, next;
365    };
366
[683]367    ItemIntMap& _iim;
368    std::vector<int> _first;
369    std::vector<BucketItem> _data;
370    mutable int _minimum;
[681]371
372  }; // class BucketHeap
373
[710]374  /// \ingroup heaps
[681]375  ///
[709]376  /// \brief Simplified bucket heap data structure.
[681]377  ///
378  /// This class implements a simplified \e bucket \e heap data
[709]379  /// structure. It does not provide some functionality, but it is
380  /// faster and simpler than BucketHeap. The main difference is
381  /// that BucketHeap stores a doubly-linked list for each key while
382  /// this class stores only simply-linked lists. It supports erasing
383  /// only for the item having minimum priority and it does not support
384  /// key increasing and decreasing.
[681]385  ///
[709]386  /// Note that this implementation does not conform to the
387  /// \ref concepts::Heap "heap concept" due to the lack of some
388  /// functionality.
389  ///
390  /// \tparam IM A read-writable item map with \c int values, used
391  /// internally to handle the cross references.
392  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
393  /// The default is \e min-heap. If this parameter is set to \c false,
394  /// then the comparison is reversed, so the top(), prio() and pop()
395  /// functions deal with the item having maximum priority instead of the
396  /// minimum.
[681]397  ///
398  /// \sa BucketHeap
[683]399  template <typename IM, bool MIN = true >
[681]400  class SimpleBucketHeap {
401
402  public:
[709]403
404    /// Type of the item-int map.
405    typedef IM ItemIntMap;
406    /// Type of the priorities.
[681]407    typedef int Prio;
[709]408    /// Type of the items stored in the heap.
409    typedef typename ItemIntMap::Key Item;
410    /// Type of the item-priority pairs.
411    typedef std::pair<Item,Prio> Pair;
[681]412
[682]413  private:
414
[683]415    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
[682]416
417  public:
418
[709]419    /// \brief Type to represent the states of the items.
[681]420    ///
[709]421    /// Each item has a state associated to it. It can be "in heap",
422    /// "pre-heap" or "post-heap". The latter two are indifferent from the
[681]423    /// heap's point of view, but may be useful to the user.
424    ///
[683]425    /// The item-int map must be initialized in such way that it assigns
426    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
[681]427    enum State {
[683]428      IN_HEAP = 0,    ///< = 0.
429      PRE_HEAP = -1,  ///< = -1.
430      POST_HEAP = -2  ///< = -2.
[681]431    };
432
433  public:
434
[709]435    /// \brief Constructor.
[681]436    ///
[709]437    /// Constructor.
438    /// \param map A map that assigns \c int values to the items.
439    /// It is used internally to handle the cross references.
440    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
[683]441    explicit SimpleBucketHeap(ItemIntMap &map)
442      : _iim(map), _free(-1), _num(0), _minimum(0) {}
[681]443
[709]444    /// \brief The number of items stored in the heap.
[681]445    ///
[709]446    /// This function returns the number of items stored in the heap.
[683]447    int size() const { return _num; }
[681]448
[709]449    /// \brief Check if the heap is empty.
[681]450    ///
[709]451    /// This function returns \c true if the heap is empty.
[683]452    bool empty() const { return _num == 0; }
[681]453
[709]454    /// \brief Make the heap empty.
[681]455    ///
[709]456    /// This functon makes the heap empty.
457    /// It does not change the cross reference map. If you want to reuse
458    /// a heap that is not surely empty, you should first clear it and
459    /// then you should set the cross reference map to \c PRE_HEAP
460    /// for each item.
[681]461    void clear() {
[683]462      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
[681]463    }
464
465    /// \brief Insert a pair of item and priority into the heap.
466    ///
[709]467    /// This function inserts \c p.first to the heap with priority
468    /// \c p.second.
[681]469    /// \param p The pair to insert.
[709]470    /// \pre \c p.first must not be stored in the heap.
[681]471    void push(const Pair& p) {
472      push(p.first, p.second);
473    }
474
475    /// \brief Insert an item into the heap with the given priority.
476    ///
[709]477    /// This function inserts the given item into the heap with the
478    /// given priority.
[681]479    /// \param i The item to insert.
480    /// \param p The priority of the item.
[709]481    /// \pre \e i must not be stored in the heap.
[681]482    void push(const Item &i, const Prio &p) {
483      int idx;
[683]484      if (_free == -1) {
485        idx = _data.size();
486        _data.push_back(BucketItem(i));
[681]487      } else {
[683]488        idx = _free;
489        _free = _data[idx].next;
490        _data[idx].item = i;
[681]491      }
[683]492      _iim[i] = idx;
493      if (p >= int(_first.size())) _first.resize(p + 1, -1);
494      _data[idx].next = _first[p];
495      _first[p] = idx;
496      if (Direction::less(p, _minimum)) {
497        _minimum = p;
[681]498      }
[683]499      ++_num;
[681]500    }
501
[709]502    /// \brief Return the item having minimum priority.
[681]503    ///
[709]504    /// This function returns the item having minimum priority.
505    /// \pre The heap must be non-empty.
[681]506    Item top() const {
[683]507      while (_first[_minimum] == -1) {
508        Direction::increase(_minimum);
[681]509      }
[683]510      return _data[_first[_minimum]].item;
[681]511    }
512
[709]513    /// \brief The minimum priority.
[681]514    ///
[709]515    /// This function returns the minimum priority.
516    /// \pre The heap must be non-empty.
[681]517    Prio prio() const {
[683]518      while (_first[_minimum] == -1) {
519        Direction::increase(_minimum);
[681]520      }
[683]521      return _minimum;
[681]522    }
523
[709]524    /// \brief Remove the item having minimum priority.
[681]525    ///
[709]526    /// This function removes the item having minimum priority.
[681]527    /// \pre The heap must be non-empty.
528    void pop() {
[683]529      while (_first[_minimum] == -1) {
530        Direction::increase(_minimum);
[681]531      }
[683]532      int idx = _first[_minimum];
533      _iim[_data[idx].item] = -2;
534      _first[_minimum] = _data[idx].next;
535      _data[idx].next = _free;
536      _free = idx;
537      --_num;
[681]538    }
539
[709]540    /// \brief The priority of the given item.
[681]541    ///
[709]542    /// This function returns the priority of the given item.
[681]543    /// \param i The item.
[709]544    /// \pre \e i must be in the heap.
545    /// \warning This operator is not a constant time function because
546    /// it scans the whole data structure to find the proper value.
[681]547    Prio operator[](const Item &i) const {
[709]548      for (int k = 0; k < int(_first.size()); ++k) {
[683]549        int idx = _first[k];
[681]550        while (idx != -1) {
[683]551          if (_data[idx].item == i) {
[681]552            return k;
553          }
[683]554          idx = _data[idx].next;
[681]555        }
556      }
557      return -1;
558    }
559
[709]560    /// \brief Return the state of an item.
[681]561    ///
[709]562    /// This method returns \c PRE_HEAP if the given item has never
563    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
564    /// and \c POST_HEAP otherwise.
565    /// In the latter case it is possible that the item will get back
566    /// to the heap again.
[681]567    /// \param i The item.
568    State state(const Item &i) const {
[683]569      int idx = _iim[i];
[681]570      if (idx >= 0) idx = 0;
571      return State(idx);
572    }
573
574  private:
575
576    struct BucketItem {
577      BucketItem(const Item& _item)
578        : item(_item) {}
579
580      Item item;
581      int next;
582    };
583
[683]584    ItemIntMap& _iim;
585    std::vector<int> _first;
586    std::vector<BucketItem> _data;
587    int _free, _num;
588    mutable int _minimum;
[681]589
590  }; // class SimpleBucketHeap
591
592}
593
594#endif
Note: See TracBrowser for help on using the repository browser.