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