lemon/bucket_heap.h
author Balazs Dezso <deba@inf.elte.hu>
Thu, 11 Jun 2009 22:16:11 +0200
changeset 682 bb8c4cd57900
parent 681 532697c9fa53
child 683 9f529abcaebf
permissions -rw-r--r--
Simplified implementation of bucket heaps (#50)
     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 
    22 ///\ingroup auxdat
    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 minimize>
    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 auxdat
    57   ///
    58   /// \brief A Bucket Heap implementation.
    59   ///
    60   /// This class implements the \e bucket \e heap data structure. A \e heap
    61   /// is a data structure for storing items with specified values called \e
    62   /// priorities in such a way that finding the item with minimum priority is
    63   /// efficient. The bucket heap is very simple implementation, it can store
    64   /// only integer priorities and it stores for each priority in the
    65   /// \f$ [0..C) \f$ range a list of items. So it should be used only when
    66   /// the priorities are small. It is not intended to use as dijkstra heap.
    67   ///
    68   /// \param _ItemIntMap A read and writable Item int map, used internally
    69   /// to handle the cross references.
    70   /// \param minimize If the given parameter is true then the heap gives back
    71   /// the lowest priority.
    72   template <typename _ItemIntMap, bool minimize = true>
    73   class BucketHeap {
    74 
    75   public:
    76     /// \e
    77     typedef typename _ItemIntMap::Key Item;
    78     /// \e
    79     typedef int Prio;
    80     /// \e
    81     typedef std::pair<Item, Prio> Pair;
    82     /// \e
    83     typedef _ItemIntMap ItemIntMap;
    84 
    85   private:
    86 
    87     typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
    88 
    89   public:
    90 
    91     /// \brief Type to represent the items states.
    92     ///
    93     /// Each Item element have a state associated to it. It may be "in heap",
    94     /// "pre heap" or "post heap". The latter two are indifferent from the
    95     /// heap's point of view, but may be useful to the user.
    96     ///
    97     /// The ItemIntMap \e should be initialized in such way that it maps
    98     /// PRE_HEAP (-1) to any element to be put in the heap...
    99     enum State {
   100       IN_HEAP = 0,
   101       PRE_HEAP = -1,
   102       POST_HEAP = -2
   103     };
   104 
   105   public:
   106     /// \brief The constructor.
   107     ///
   108     /// The constructor.
   109     /// \param _index should be given to the constructor, since it is used
   110     /// internally to handle the cross references. The value of the map
   111     /// should be PRE_HEAP (-1) for each element.
   112     explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
   113 
   114     /// The number of items stored in the heap.
   115     ///
   116     /// \brief Returns the number of items stored in the heap.
   117     int size() const { return data.size(); }
   118 
   119     /// \brief Checks if the heap stores no items.
   120     ///
   121     /// Returns \c true if and only if the heap stores no items.
   122     bool empty() const { return data.empty(); }
   123 
   124     /// \brief Make empty this heap.
   125     ///
   126     /// Make empty this heap. It does not change the cross reference
   127     /// map.  If you want to reuse a heap what is not surely empty you
   128     /// should first clear the heap and after that you should set the
   129     /// cross reference map for each item to \c PRE_HEAP.
   130     void clear() {
   131       data.clear(); first.clear(); minimal = 0;
   132     }
   133 
   134   private:
   135 
   136     void relocate_last(int idx) {
   137       if (idx + 1 < int(data.size())) {
   138         data[idx] = data.back();
   139         if (data[idx].prev != -1) {
   140           data[data[idx].prev].next = idx;
   141         } else {
   142           first[data[idx].value] = idx;
   143         }
   144         if (data[idx].next != -1) {
   145           data[data[idx].next].prev = idx;
   146         }
   147         index[data[idx].item] = idx;
   148       }
   149       data.pop_back();
   150     }
   151 
   152     void unlace(int idx) {
   153       if (data[idx].prev != -1) {
   154         data[data[idx].prev].next = data[idx].next;
   155       } else {
   156         first[data[idx].value] = data[idx].next;
   157       }
   158       if (data[idx].next != -1) {
   159         data[data[idx].next].prev = data[idx].prev;
   160       }
   161     }
   162 
   163     void lace(int idx) {
   164       if (int(first.size()) <= data[idx].value) {
   165         first.resize(data[idx].value + 1, -1);
   166       }
   167       data[idx].next = first[data[idx].value];
   168       if (data[idx].next != -1) {
   169         data[data[idx].next].prev = idx;
   170       }
   171       first[data[idx].value] = idx;
   172       data[idx].prev = -1;
   173     }
   174 
   175   public:
   176     /// \brief Insert a pair of item and priority into the heap.
   177     ///
   178     /// Adds \c p.first to the heap with priority \c p.second.
   179     /// \param p The pair to insert.
   180     void push(const Pair& p) {
   181       push(p.first, p.second);
   182     }
   183 
   184     /// \brief Insert an item into the heap with the given priority.
   185     ///
   186     /// Adds \c i to the heap with priority \c p.
   187     /// \param i The item to insert.
   188     /// \param p The priority of the item.
   189     void push(const Item &i, const Prio &p) {
   190       int idx = data.size();
   191       index[i] = idx;
   192       data.push_back(BucketItem(i, p));
   193       lace(idx);
   194       if (Direction::less(p, minimal)) {
   195         minimal = p;
   196       }
   197     }
   198 
   199     /// \brief Returns the item with minimum priority.
   200     ///
   201     /// This method returns the item with minimum priority.
   202     /// \pre The heap must be nonempty.
   203     Item top() const {
   204       while (first[minimal] == -1) {
   205         Direction::increase(minimal);
   206       }
   207       return data[first[minimal]].item;
   208     }
   209 
   210     /// \brief Returns the minimum priority.
   211     ///
   212     /// It returns the minimum priority.
   213     /// \pre The heap must be nonempty.
   214     Prio prio() const {
   215       while (first[minimal] == -1) {
   216         Direction::increase(minimal);
   217       }
   218       return minimal;
   219     }
   220 
   221     /// \brief Deletes the item with minimum priority.
   222     ///
   223     /// This method deletes the item with minimum priority from the heap.
   224     /// \pre The heap must be non-empty.
   225     void pop() {
   226       while (first[minimal] == -1) {
   227         Direction::increase(minimal);
   228       }
   229       int idx = first[minimal];
   230       index[data[idx].item] = -2;
   231       unlace(idx);
   232       relocate_last(idx);
   233     }
   234 
   235     /// \brief Deletes \c i from the heap.
   236     ///
   237     /// This method deletes item \c i from the heap, if \c i was
   238     /// already stored in the heap.
   239     /// \param i The item to erase.
   240     void erase(const Item &i) {
   241       int idx = index[i];
   242       index[data[idx].item] = -2;
   243       unlace(idx);
   244       relocate_last(idx);
   245     }
   246 
   247 
   248     /// \brief Returns the priority of \c i.
   249     ///
   250     /// This function returns the priority of item \c i.
   251     /// \pre \c i must be in the heap.
   252     /// \param i The item.
   253     Prio operator[](const Item &i) const {
   254       int idx = index[i];
   255       return data[idx].value;
   256     }
   257 
   258     /// \brief \c i gets to the heap with priority \c p independently
   259     /// if \c i was already there.
   260     ///
   261     /// This method calls \ref push(\c i, \c p) if \c i is not stored
   262     /// in the heap and sets the priority of \c i to \c p otherwise.
   263     /// \param i The item.
   264     /// \param p The priority.
   265     void set(const Item &i, const Prio &p) {
   266       int idx = index[i];
   267       if (idx < 0) {
   268         push(i, p);
   269       } else if (Direction::less(p, data[idx].value)) {
   270         decrease(i, p);
   271       } else {
   272         increase(i, p);
   273       }
   274     }
   275 
   276     /// \brief Decreases the priority of \c i to \c p.
   277     ///
   278     /// This method decreases the priority of item \c i to \c p.
   279     /// \pre \c i must be stored in the heap with priority at least \c
   280     /// p relative to \c Compare.
   281     /// \param i The item.
   282     /// \param p The priority.
   283     void decrease(const Item &i, const Prio &p) {
   284       int idx = index[i];
   285       unlace(idx);
   286       data[idx].value = p;
   287       if (Direction::less(p, minimal)) {
   288         minimal = p;
   289       }
   290       lace(idx);
   291     }
   292 
   293     /// \brief Increases the priority of \c i to \c p.
   294     ///
   295     /// This method sets the priority of item \c i to \c p.
   296     /// \pre \c i must be stored in the heap with priority at most \c
   297     /// p relative to \c Compare.
   298     /// \param i The item.
   299     /// \param p The priority.
   300     void increase(const Item &i, const Prio &p) {
   301       int idx = index[i];
   302       unlace(idx);
   303       data[idx].value = p;
   304       lace(idx);
   305     }
   306 
   307     /// \brief Returns if \c item is in, has already been in, or has
   308     /// never been in the heap.
   309     ///
   310     /// This method returns PRE_HEAP if \c item has never been in the
   311     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   312     /// otherwise. In the latter case it is possible that \c item will
   313     /// get back to the heap again.
   314     /// \param i The item.
   315     State state(const Item &i) const {
   316       int idx = index[i];
   317       if (idx >= 0) idx = 0;
   318       return State(idx);
   319     }
   320 
   321     /// \brief Sets the state of the \c item in the heap.
   322     ///
   323     /// Sets the state of the \c item in the heap. It can be used to
   324     /// manually clear the heap when it is important to achive the
   325     /// better time complexity.
   326     /// \param i The item.
   327     /// \param st The state. It should not be \c IN_HEAP.
   328     void state(const Item& i, State st) {
   329       switch (st) {
   330       case POST_HEAP:
   331       case PRE_HEAP:
   332         if (state(i) == IN_HEAP) {
   333           erase(i);
   334         }
   335         index[i] = st;
   336         break;
   337       case IN_HEAP:
   338         break;
   339       }
   340     }
   341 
   342   private:
   343 
   344     struct BucketItem {
   345       BucketItem(const Item& _item, int _value)
   346         : item(_item), value(_value) {}
   347 
   348       Item item;
   349       int value;
   350 
   351       int prev, next;
   352     };
   353 
   354     ItemIntMap& index;
   355     std::vector<int> first;
   356     std::vector<BucketItem> data;
   357     mutable int minimal;
   358 
   359   }; // class BucketHeap
   360 
   361   /// \ingroup auxdat
   362   ///
   363   /// \brief A Simplified Bucket Heap implementation.
   364   ///
   365   /// This class implements a simplified \e bucket \e heap data
   366   /// structure.  It does not provide some functionality but it faster
   367   /// and simplier data structure than the BucketHeap. The main
   368   /// difference is that the BucketHeap stores for every key a double
   369   /// linked list while this class stores just simple lists. In the
   370   /// other way it does not support erasing each elements just the
   371   /// minimal and it does not supports key increasing, decreasing.
   372   ///
   373   /// \param _ItemIntMap A read and writable Item int map, used internally
   374   /// to handle the cross references.
   375   /// \param minimize If the given parameter is true then the heap gives back
   376   /// the lowest priority.
   377   ///
   378   /// \sa BucketHeap
   379   template <typename _ItemIntMap, bool minimize = true >
   380   class SimpleBucketHeap {
   381 
   382   public:
   383     typedef typename _ItemIntMap::Key Item;
   384     typedef int Prio;
   385     typedef std::pair<Item, Prio> Pair;
   386     typedef _ItemIntMap ItemIntMap;
   387 
   388   private:
   389 
   390     typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
   391 
   392   public:
   393 
   394     /// \brief Type to represent the items states.
   395     ///
   396     /// Each Item element have a state associated to it. It may be "in heap",
   397     /// "pre heap" or "post heap". The latter two are indifferent from the
   398     /// heap's point of view, but may be useful to the user.
   399     ///
   400     /// The ItemIntMap \e should be initialized in such way that it maps
   401     /// PRE_HEAP (-1) to any element to be put in the heap...
   402     enum State {
   403       IN_HEAP = 0,
   404       PRE_HEAP = -1,
   405       POST_HEAP = -2
   406     };
   407 
   408   public:
   409 
   410     /// \brief The constructor.
   411     ///
   412     /// The constructor.
   413     /// \param _index should be given to the constructor, since it is used
   414     /// internally to handle the cross references. The value of the map
   415     /// should be PRE_HEAP (-1) for each element.
   416     explicit SimpleBucketHeap(ItemIntMap &_index)
   417       : index(_index), free(-1), num(0), minimal(0) {}
   418 
   419     /// \brief Returns the number of items stored in the heap.
   420     ///
   421     /// The number of items stored in the heap.
   422     int size() const { return num; }
   423 
   424     /// \brief Checks if the heap stores no items.
   425     ///
   426     /// Returns \c true if and only if the heap stores no items.
   427     bool empty() const { return num == 0; }
   428 
   429     /// \brief Make empty this heap.
   430     ///
   431     /// Make empty this heap. It does not change the cross reference
   432     /// map.  If you want to reuse a heap what is not surely empty you
   433     /// should first clear the heap and after that you should set the
   434     /// cross reference map for each item to \c PRE_HEAP.
   435     void clear() {
   436       data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
   437     }
   438 
   439     /// \brief Insert a pair of item and priority into the heap.
   440     ///
   441     /// Adds \c p.first to the heap with priority \c p.second.
   442     /// \param p The pair to insert.
   443     void push(const Pair& p) {
   444       push(p.first, p.second);
   445     }
   446 
   447     /// \brief Insert an item into the heap with the given priority.
   448     ///
   449     /// Adds \c i to the heap with priority \c p.
   450     /// \param i The item to insert.
   451     /// \param p The priority of the item.
   452     void push(const Item &i, const Prio &p) {
   453       int idx;
   454       if (free == -1) {
   455         idx = data.size();
   456         data.push_back(BucketItem(i));
   457       } else {
   458         idx = free;
   459         free = data[idx].next;
   460         data[idx].item = i;
   461       }
   462       index[i] = idx;
   463       if (p >= int(first.size())) first.resize(p + 1, -1);
   464       data[idx].next = first[p];
   465       first[p] = idx;
   466       if (Direction::less(p, minimal)) {
   467         minimal = p;
   468       }
   469       ++num;
   470     }
   471 
   472     /// \brief Returns the item with minimum priority.
   473     ///
   474     /// This method returns the item with minimum priority.
   475     /// \pre The heap must be nonempty.
   476     Item top() const {
   477       while (first[minimal] == -1) {
   478         Direction::increase(minimal);
   479       }
   480       return data[first[minimal]].item;
   481     }
   482 
   483     /// \brief Returns the minimum priority.
   484     ///
   485     /// It returns the minimum priority.
   486     /// \pre The heap must be nonempty.
   487     Prio prio() const {
   488       while (first[minimal] == -1) {
   489         Direction::increase(minimal);
   490       }
   491       return minimal;
   492     }
   493 
   494     /// \brief Deletes the item with minimum priority.
   495     ///
   496     /// This method deletes the item with minimum priority from the heap.
   497     /// \pre The heap must be non-empty.
   498     void pop() {
   499       while (first[minimal] == -1) {
   500         Direction::increase(minimal);
   501       }
   502       int idx = first[minimal];
   503       index[data[idx].item] = -2;
   504       first[minimal] = data[idx].next;
   505       data[idx].next = free;
   506       free = idx;
   507       --num;
   508     }
   509 
   510     /// \brief Returns the priority of \c i.
   511     ///
   512     /// This function returns the priority of item \c i.
   513     /// \warning This operator is not a constant time function
   514     /// because it scans the whole data structure to find the proper
   515     /// value.
   516     /// \pre \c i must be in the heap.
   517     /// \param i The item.
   518     Prio operator[](const Item &i) const {
   519       for (int k = 0; k < first.size(); ++k) {
   520         int idx = first[k];
   521         while (idx != -1) {
   522           if (data[idx].item == i) {
   523             return k;
   524           }
   525           idx = data[idx].next;
   526         }
   527       }
   528       return -1;
   529     }
   530 
   531     /// \brief Returns if \c item is in, has already been in, or has
   532     /// never been in the heap.
   533     ///
   534     /// This method returns PRE_HEAP if \c item has never been in the
   535     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   536     /// otherwise. In the latter case it is possible that \c item will
   537     /// get back to the heap again.
   538     /// \param i The item.
   539     State state(const Item &i) const {
   540       int idx = index[i];
   541       if (idx >= 0) idx = 0;
   542       return State(idx);
   543     }
   544 
   545   private:
   546 
   547     struct BucketItem {
   548       BucketItem(const Item& _item)
   549         : item(_item) {}
   550 
   551       Item item;
   552       int next;
   553     };
   554 
   555     ItemIntMap& index;
   556     std::vector<int> first;
   557     std::vector<BucketItem> data;
   558     int free, num;
   559     mutable int minimal;
   560 
   561   }; // class SimpleBucketHeap
   562 
   563 }
   564 
   565 #endif