COIN-OR::LEMON - Graph Library

source: lemon/lemon/bucket_heap.h @ 757:f1fe0ddad6f7

Last change on this file since 757:f1fe0ddad6f7 was 757:f1fe0ddad6f7, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Move the heaps to a separate group (#299)

File size: 17.3 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_BUCKET_HEAP_H
20#define LEMON_BUCKET_HEAP_H
21
[757]22///\ingroup heaps
[728]23///\file
[756]24///\brief Bucket heap implementation.
[728]25
26#include <vector>
27#include <utility>
28#include <functional>
29
30namespace lemon {
31
[729]32  namespace _bucket_heap_bits {
33
[730]34    template <bool MIN>
[729]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
[757]56  /// \ingroup heaps
[728]57  ///
[756]58  /// \brief Bucket heap data structure.
[728]59  ///
[756]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.
[728]63  ///
[756]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
[730]78  template <typename IM, bool MIN = true>
[728]79  class BucketHeap {
80
81  public:
[756]82
83    /// Type of the item-int map.
84    typedef IM ItemIntMap;
85    /// Type of the priorities.
[728]86    typedef int Prio;
[756]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;
[728]91
[729]92  private:
93
[730]94    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
[729]95
96  public:
97
[756]98    /// \brief Type to represent the states of the items.
[728]99    ///
[756]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
[728]102    /// heap's point of view, but may be useful to the user.
103    ///
[730]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.
[728]106    enum State {
[730]107      IN_HEAP = 0,    ///< = 0.
108      PRE_HEAP = -1,  ///< = -1.
109      POST_HEAP = -2  ///< = -2.
[728]110    };
111
112  public:
[756]113
114    /// \brief Constructor.
[728]115    ///
[756]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.
[730]120    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
[728]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.
[730]125    int size() const { return _data.size(); }
[728]126
[756]127    /// \brief Check if the heap is empty.
[728]128    ///
[756]129    /// This function returns \c true if the heap is empty.
[730]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.
[728]139    void clear() {
[730]140      _data.clear(); _first.clear(); _minimum = 0;
[728]141    }
142
143  private:
144
145    void relocate_last(int idx) {
[730]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;
[728]150        } else {
[730]151          _first[_data[idx].value] = idx;
[728]152        }
[730]153        if (_data[idx].next != -1) {
154          _data[_data[idx].next].prev = idx;
[728]155        }
[730]156        _iim[_data[idx].item] = idx;
[728]157      }
[730]158      _data.pop_back();
[728]159    }
160
161    void unlace(int idx) {
[730]162      if (_data[idx].prev != -1) {
163        _data[_data[idx].prev].next = _data[idx].next;
[728]164      } else {
[730]165        _first[_data[idx].value] = _data[idx].next;
[728]166      }
[730]167      if (_data[idx].next != -1) {
168        _data[_data[idx].next].prev = _data[idx].prev;
[728]169      }
170    }
171
172    void lace(int idx) {
[730]173      if (int(_first.size()) <= _data[idx].value) {
174        _first.resize(_data[idx].value + 1, -1);
[728]175      }
[730]176      _data[idx].next = _first[_data[idx].value];
177      if (_data[idx].next != -1) {
178        _data[_data[idx].next].prev = idx;
[728]179      }
[730]180      _first[_data[idx].value] = idx;
181      _data[idx].prev = -1;
[728]182    }
183
184  public:
[756]185
[728]186    /// \brief Insert a pair of item and priority into the heap.
187    ///
[756]188    /// This function inserts \c p.first to the heap with priority
189    /// \c p.second.
[728]190    /// \param p The pair to insert.
[756]191    /// \pre \c p.first must not be stored in the heap.
[728]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    ///
[756]198    /// This function inserts the given item into the heap with the
199    /// given priority.
[728]200    /// \param i The item to insert.
201    /// \param p The priority of the item.
[756]202    /// \pre \e i must not be stored in the heap.
[728]203    void push(const Item &i, const Prio &p) {
[730]204      int idx = _data.size();
205      _iim[i] = idx;
206      _data.push_back(BucketItem(i, p));
[728]207      lace(idx);
[730]208      if (Direction::less(p, _minimum)) {
209        _minimum = p;
[728]210      }
211    }
212
[756]213    /// \brief Return the item having minimum priority.
[728]214    ///
[756]215    /// This function returns the item having minimum priority.
216    /// \pre The heap must be non-empty.
[728]217    Item top() const {
[730]218      while (_first[_minimum] == -1) {
219        Direction::increase(_minimum);
[728]220      }
[730]221      return _data[_first[_minimum]].item;
[728]222    }
223
[756]224    /// \brief The minimum priority.
[728]225    ///
[756]226    /// This function returns the minimum priority.
227    /// \pre The heap must be non-empty.
[728]228    Prio prio() const {
[730]229      while (_first[_minimum] == -1) {
230        Direction::increase(_minimum);
[728]231      }
[730]232      return _minimum;
[728]233    }
234
[756]235    /// \brief Remove the item having minimum priority.
[728]236    ///
[756]237    /// This function removes the item having minimum priority.
[728]238    /// \pre The heap must be non-empty.
239    void pop() {
[730]240      while (_first[_minimum] == -1) {
241        Direction::increase(_minimum);
[728]242      }
[730]243      int idx = _first[_minimum];
244      _iim[_data[idx].item] = -2;
[728]245      unlace(idx);
246      relocate_last(idx);
247    }
248
[756]249    /// \brief Remove the given item from the heap.
[728]250    ///
[756]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.
[728]255    void erase(const Item &i) {
[730]256      int idx = _iim[i];
257      _iim[_data[idx].item] = -2;
[728]258      unlace(idx);
259      relocate_last(idx);
260    }
261
[756]262    /// \brief The priority of the given item.
[728]263    ///
[756]264    /// This function returns the priority of the given item.
[728]265    /// \param i The item.
[756]266    /// \pre \e i must be in the heap.
[728]267    Prio operator[](const Item &i) const {
[730]268      int idx = _iim[i];
269      return _data[idx].value;
[728]270    }
271
[756]272    /// \brief Set the priority of an item or insert it, if it is
273    /// not stored in the heap.
[728]274    ///
[756]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.
[728]278    /// \param i The item.
279    /// \param p The priority.
280    void set(const Item &i, const Prio &p) {
[730]281      int idx = _iim[i];
[728]282      if (idx < 0) {
[729]283        push(i, p);
[730]284      } else if (Direction::less(p, _data[idx].value)) {
[729]285        decrease(i, p);
286      } else {
[728]287        increase(i, p);
288      }
289    }
290
[756]291    /// \brief Decrease the priority of an item to the given value.
[728]292    ///
[756]293    /// This function decreases the priority of an item to the given value.
[728]294    /// \param i The item.
295    /// \param p The priority.
[756]296    /// \pre \e i must be stored in the heap with priority at least \e p.
[728]297    void decrease(const Item &i, const Prio &p) {
[730]298      int idx = _iim[i];
[728]299      unlace(idx);
[730]300      _data[idx].value = p;
301      if (Direction::less(p, _minimum)) {
302        _minimum = p;
[728]303      }
304      lace(idx);
305    }
306
[756]307    /// \brief Increase the priority of an item to the given value.
[728]308    ///
[756]309    /// This function increases the priority of an item to the given value.
[728]310    /// \param i The item.
311    /// \param p The priority.
[756]312    /// \pre \e i must be stored in the heap with priority at most \e p.
[728]313    void increase(const Item &i, const Prio &p) {
[730]314      int idx = _iim[i];
[728]315      unlace(idx);
[730]316      _data[idx].value = p;
[728]317      lace(idx);
318    }
319
[756]320    /// \brief Return the state of an item.
[728]321    ///
[756]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.
[728]327    /// \param i The item.
328    State state(const Item &i) const {
[730]329      int idx = _iim[i];
[728]330      if (idx >= 0) idx = 0;
331      return State(idx);
332    }
333
[756]334    /// \brief Set the state of an item in the heap.
[728]335    ///
[756]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.
[728]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        }
[730]348        _iim[i] = st;
[728]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
[730]367    ItemIntMap& _iim;
368    std::vector<int> _first;
369    std::vector<BucketItem> _data;
370    mutable int _minimum;
[728]371
372  }; // class BucketHeap
373
[757]374  /// \ingroup heaps
[728]375  ///
[756]376  /// \brief Simplified bucket heap data structure.
[728]377  ///
378  /// This class implements a simplified \e bucket \e heap data
[756]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.
[728]385  ///
[756]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.
[728]397  ///
398  /// \sa BucketHeap
[730]399  template <typename IM, bool MIN = true >
[728]400  class SimpleBucketHeap {
401
402  public:
[756]403
404    /// Type of the item-int map.
405    typedef IM ItemIntMap;
406    /// Type of the priorities.
[728]407    typedef int Prio;
[756]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;
[728]412
[729]413  private:
414
[730]415    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
[729]416
417  public:
418
[756]419    /// \brief Type to represent the states of the items.
[728]420    ///
[756]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
[728]423    /// heap's point of view, but may be useful to the user.
424    ///
[730]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.
[728]427    enum State {
[730]428      IN_HEAP = 0,    ///< = 0.
429      PRE_HEAP = -1,  ///< = -1.
430      POST_HEAP = -2  ///< = -2.
[728]431    };
432
433  public:
434
[756]435    /// \brief Constructor.
[728]436    ///
[756]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.
[730]441    explicit SimpleBucketHeap(ItemIntMap &map)
442      : _iim(map), _free(-1), _num(0), _minimum(0) {}
[728]443
[756]444    /// \brief The number of items stored in the heap.
[728]445    ///
[756]446    /// This function returns the number of items stored in the heap.
[730]447    int size() const { return _num; }
[728]448
[756]449    /// \brief Check if the heap is empty.
[728]450    ///
[756]451    /// This function returns \c true if the heap is empty.
[730]452    bool empty() const { return _num == 0; }
[728]453
[756]454    /// \brief Make the heap empty.
[728]455    ///
[756]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.
[728]461    void clear() {
[730]462      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
[728]463    }
464
465    /// \brief Insert a pair of item and priority into the heap.
466    ///
[756]467    /// This function inserts \c p.first to the heap with priority
468    /// \c p.second.
[728]469    /// \param p The pair to insert.
[756]470    /// \pre \c p.first must not be stored in the heap.
[728]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    ///
[756]477    /// This function inserts the given item into the heap with the
478    /// given priority.
[728]479    /// \param i The item to insert.
480    /// \param p The priority of the item.
[756]481    /// \pre \e i must not be stored in the heap.
[728]482    void push(const Item &i, const Prio &p) {
483      int idx;
[730]484      if (_free == -1) {
485        idx = _data.size();
486        _data.push_back(BucketItem(i));
[728]487      } else {
[730]488        idx = _free;
489        _free = _data[idx].next;
490        _data[idx].item = i;
[728]491      }
[730]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;
[728]498      }
[730]499      ++_num;
[728]500    }
501
[756]502    /// \brief Return the item having minimum priority.
[728]503    ///
[756]504    /// This function returns the item having minimum priority.
505    /// \pre The heap must be non-empty.
[728]506    Item top() const {
[730]507      while (_first[_minimum] == -1) {
508        Direction::increase(_minimum);
[728]509      }
[730]510      return _data[_first[_minimum]].item;
[728]511    }
512
[756]513    /// \brief The minimum priority.
[728]514    ///
[756]515    /// This function returns the minimum priority.
516    /// \pre The heap must be non-empty.
[728]517    Prio prio() const {
[730]518      while (_first[_minimum] == -1) {
519        Direction::increase(_minimum);
[728]520      }
[730]521      return _minimum;
[728]522    }
523
[756]524    /// \brief Remove the item having minimum priority.
[728]525    ///
[756]526    /// This function removes the item having minimum priority.
[728]527    /// \pre The heap must be non-empty.
528    void pop() {
[730]529      while (_first[_minimum] == -1) {
530        Direction::increase(_minimum);
[728]531      }
[730]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;
[728]538    }
539
[756]540    /// \brief The priority of the given item.
[728]541    ///
[756]542    /// This function returns the priority of the given item.
[728]543    /// \param i The item.
[756]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.
[728]547    Prio operator[](const Item &i) const {
[756]548      for (int k = 0; k < int(_first.size()); ++k) {
[730]549        int idx = _first[k];
[728]550        while (idx != -1) {
[730]551          if (_data[idx].item == i) {
[728]552            return k;
553          }
[730]554          idx = _data[idx].next;
[728]555        }
556      }
557      return -1;
558    }
559
[756]560    /// \brief Return the state of an item.
[728]561    ///
[756]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.
[728]567    /// \param i The item.
568    State state(const Item &i) const {
[730]569      int idx = _iim[i];
[728]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
[730]584    ItemIntMap& _iim;
585    std::vector<int> _first;
586    std::vector<BucketItem> _data;
587    int _free, _num;
588    mutable int _minimum;
[728]589
590  }; // class SimpleBucketHeap
591
592}
593
594#endif
Note: See TracBrowser for help on using the repository browser.