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