lemon/bucket_heap.h
changeset 803 1b89e29c9fc7
parent 710 f1fe0ddad6f7
child 877 141f9c0db4a3
     1.1 --- a/lemon/bucket_heap.h	Thu Dec 10 17:05:35 2009 +0100
     1.2 +++ b/lemon/bucket_heap.h	Thu Dec 10 17:18:25 2009 +0100
     1.3 @@ -19,9 +19,9 @@
     1.4  #ifndef LEMON_BUCKET_HEAP_H
     1.5  #define LEMON_BUCKET_HEAP_H
     1.6  
     1.7 -///\ingroup auxdat
     1.8 +///\ingroup heaps
     1.9  ///\file
    1.10 -///\brief Bucket Heap implementation.
    1.11 +///\brief Bucket heap implementation.
    1.12  
    1.13  #include <vector>
    1.14  #include <utility>
    1.15 @@ -53,35 +53,41 @@
    1.16  
    1.17    }
    1.18  
    1.19 -  /// \ingroup auxdat
    1.20 +  /// \ingroup heaps
    1.21    ///
    1.22 -  /// \brief A Bucket Heap implementation.
    1.23 +  /// \brief Bucket heap data structure.
    1.24    ///
    1.25 -  /// This class implements the \e bucket \e heap data structure. A \e heap
    1.26 -  /// is a data structure for storing items with specified values called \e
    1.27 -  /// priorities in such a way that finding the item with minimum priority is
    1.28 -  /// efficient. The bucket heap is very simple implementation, it can store
    1.29 -  /// only integer priorities and it stores for each priority in the
    1.30 -  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
    1.31 -  /// the priorities are small. It is not intended to use as dijkstra heap.
    1.32 +  /// This class implements the \e bucket \e heap data structure.
    1.33 +  /// It practically conforms to the \ref concepts::Heap "heap concept",
    1.34 +  /// but it has some limitations.
    1.35    ///
    1.36 -  /// \param IM A read and write Item int map, used internally
    1.37 -  /// to handle the cross references.
    1.38 -  /// \param MIN If the given parameter is false then instead of the
    1.39 -  /// minimum value the maximum can be retrivied with the top() and
    1.40 -  /// prio() member functions.
    1.41 +  /// The bucket heap is a very simple structure. It can store only
    1.42 +  /// \c int priorities and it maintains a list of items for each priority
    1.43 +  /// in the range <tt>[0..C)</tt>. So it should only be used when the
    1.44 +  /// priorities are small. It is not intended to use as a Dijkstra heap.
    1.45 +  ///
    1.46 +  /// \tparam IM A read-writable item map with \c int values, used
    1.47 +  /// internally to handle the cross references.
    1.48 +  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    1.49 +  /// The default is \e min-heap. If this parameter is set to \c false,
    1.50 +  /// then the comparison is reversed, so the top(), prio() and pop()
    1.51 +  /// functions deal with the item having maximum priority instead of the
    1.52 +  /// minimum.
    1.53 +  ///
    1.54 +  /// \sa SimpleBucketHeap
    1.55    template <typename IM, bool MIN = true>
    1.56    class BucketHeap {
    1.57  
    1.58    public:
    1.59 -    /// \e
    1.60 -    typedef typename IM::Key Item;
    1.61 -    /// \e
    1.62 +
    1.63 +    /// Type of the item-int map.
    1.64 +    typedef IM ItemIntMap;
    1.65 +    /// Type of the priorities.
    1.66      typedef int Prio;
    1.67 -    /// \e
    1.68 -    typedef std::pair<Item, Prio> Pair;
    1.69 -    /// \e
    1.70 -    typedef IM ItemIntMap;
    1.71 +    /// Type of the items stored in the heap.
    1.72 +    typedef typename ItemIntMap::Key Item;
    1.73 +    /// Type of the item-priority pairs.
    1.74 +    typedef std::pair<Item,Prio> Pair;
    1.75  
    1.76    private:
    1.77  
    1.78 @@ -89,10 +95,10 @@
    1.79  
    1.80    public:
    1.81  
    1.82 -    /// \brief Type to represent the items states.
    1.83 +    /// \brief Type to represent the states of the items.
    1.84      ///
    1.85 -    /// Each Item element have a state associated to it. It may be "in heap",
    1.86 -    /// "pre heap" or "post heap". The latter two are indifferent from the
    1.87 +    /// Each item has a state associated to it. It can be "in heap",
    1.88 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    1.89      /// heap's point of view, but may be useful to the user.
    1.90      ///
    1.91      /// The item-int map must be initialized in such way that it assigns
    1.92 @@ -104,37 +110,39 @@
    1.93      };
    1.94  
    1.95    public:
    1.96 -    /// \brief The constructor.
    1.97 +
    1.98 +    /// \brief Constructor.
    1.99      ///
   1.100 -    /// The constructor.
   1.101 -    /// \param map should be given to the constructor, since it is used
   1.102 -    /// internally to handle the cross references. The value of the map
   1.103 -    /// should be PRE_HEAP (-1) for each element.
   1.104 +    /// Constructor.
   1.105 +    /// \param map A map that assigns \c int values to the items.
   1.106 +    /// It is used internally to handle the cross references.
   1.107 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   1.108      explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
   1.109  
   1.110 -    /// The number of items stored in the heap.
   1.111 +    /// \brief The number of items stored in the heap.
   1.112      ///
   1.113 -    /// \brief Returns the number of items stored in the heap.
   1.114 +    /// This function returns the number of items stored in the heap.
   1.115      int size() const { return _data.size(); }
   1.116  
   1.117 -    /// \brief Checks if the heap stores no items.
   1.118 +    /// \brief Check if the heap is empty.
   1.119      ///
   1.120 -    /// Returns \c true if and only if the heap stores no items.
   1.121 +    /// This function returns \c true if the heap is empty.
   1.122      bool empty() const { return _data.empty(); }
   1.123  
   1.124 -    /// \brief Make empty this heap.
   1.125 +    /// \brief Make the heap empty.
   1.126      ///
   1.127 -    /// Make empty this heap. It does not change the cross reference
   1.128 -    /// map.  If you want to reuse a heap what is not surely empty you
   1.129 -    /// should first clear the heap and after that you should set the
   1.130 -    /// cross reference map for each item to \c PRE_HEAP.
   1.131 +    /// This functon makes the heap empty.
   1.132 +    /// It does not change the cross reference map. If you want to reuse
   1.133 +    /// a heap that is not surely empty, you should first clear it and
   1.134 +    /// then you should set the cross reference map to \c PRE_HEAP
   1.135 +    /// for each item.
   1.136      void clear() {
   1.137        _data.clear(); _first.clear(); _minimum = 0;
   1.138      }
   1.139  
   1.140    private:
   1.141  
   1.142 -    void relocate_last(int idx) {
   1.143 +    void relocateLast(int idx) {
   1.144        if (idx + 1 < int(_data.size())) {
   1.145          _data[idx] = _data.back();
   1.146          if (_data[idx].prev != -1) {
   1.147 @@ -174,19 +182,24 @@
   1.148      }
   1.149  
   1.150    public:
   1.151 +
   1.152      /// \brief Insert a pair of item and priority into the heap.
   1.153      ///
   1.154 -    /// Adds \c p.first to the heap with priority \c p.second.
   1.155 +    /// This function inserts \c p.first to the heap with priority
   1.156 +    /// \c p.second.
   1.157      /// \param p The pair to insert.
   1.158 +    /// \pre \c p.first must not be stored in the heap.
   1.159      void push(const Pair& p) {
   1.160        push(p.first, p.second);
   1.161      }
   1.162  
   1.163      /// \brief Insert an item into the heap with the given priority.
   1.164      ///
   1.165 -    /// Adds \c i to the heap with priority \c p.
   1.166 +    /// This function inserts the given item into the heap with the
   1.167 +    /// given priority.
   1.168      /// \param i The item to insert.
   1.169      /// \param p The priority of the item.
   1.170 +    /// \pre \e i must not be stored in the heap.
   1.171      void push(const Item &i, const Prio &p) {
   1.172        int idx = _data.size();
   1.173        _iim[i] = idx;
   1.174 @@ -197,10 +210,10 @@
   1.175        }
   1.176      }
   1.177  
   1.178 -    /// \brief Returns the item with minimum priority.
   1.179 +    /// \brief Return the item having minimum priority.
   1.180      ///
   1.181 -    /// This method returns the item with minimum priority.
   1.182 -    /// \pre The heap must be nonempty.
   1.183 +    /// This function returns the item having minimum priority.
   1.184 +    /// \pre The heap must be non-empty.
   1.185      Item top() const {
   1.186        while (_first[_minimum] == -1) {
   1.187          Direction::increase(_minimum);
   1.188 @@ -208,10 +221,10 @@
   1.189        return _data[_first[_minimum]].item;
   1.190      }
   1.191  
   1.192 -    /// \brief Returns the minimum priority.
   1.193 +    /// \brief The minimum priority.
   1.194      ///
   1.195 -    /// It returns the minimum priority.
   1.196 -    /// \pre The heap must be nonempty.
   1.197 +    /// This function returns the minimum priority.
   1.198 +    /// \pre The heap must be non-empty.
   1.199      Prio prio() const {
   1.200        while (_first[_minimum] == -1) {
   1.201          Direction::increase(_minimum);
   1.202 @@ -219,9 +232,9 @@
   1.203        return _minimum;
   1.204      }
   1.205  
   1.206 -    /// \brief Deletes the item with minimum priority.
   1.207 +    /// \brief Remove the item having minimum priority.
   1.208      ///
   1.209 -    /// This method deletes the item with minimum priority from the heap.
   1.210 +    /// This function removes the item having minimum priority.
   1.211      /// \pre The heap must be non-empty.
   1.212      void pop() {
   1.213        while (_first[_minimum] == -1) {
   1.214 @@ -230,37 +243,38 @@
   1.215        int idx = _first[_minimum];
   1.216        _iim[_data[idx].item] = -2;
   1.217        unlace(idx);
   1.218 -      relocate_last(idx);
   1.219 +      relocateLast(idx);
   1.220      }
   1.221  
   1.222 -    /// \brief Deletes \c i from the heap.
   1.223 +    /// \brief Remove the given item from the heap.
   1.224      ///
   1.225 -    /// This method deletes item \c i from the heap, if \c i was
   1.226 -    /// already stored in the heap.
   1.227 -    /// \param i The item to erase.
   1.228 +    /// This function removes the given item from the heap if it is
   1.229 +    /// already stored.
   1.230 +    /// \param i The item to delete.
   1.231 +    /// \pre \e i must be in the heap.
   1.232      void erase(const Item &i) {
   1.233        int idx = _iim[i];
   1.234        _iim[_data[idx].item] = -2;
   1.235        unlace(idx);
   1.236 -      relocate_last(idx);
   1.237 +      relocateLast(idx);
   1.238      }
   1.239  
   1.240 -
   1.241 -    /// \brief Returns the priority of \c i.
   1.242 +    /// \brief The priority of the given item.
   1.243      ///
   1.244 -    /// This function returns the priority of item \c i.
   1.245 -    /// \pre \c i must be in the heap.
   1.246 +    /// This function returns the priority of the given item.
   1.247      /// \param i The item.
   1.248 +    /// \pre \e i must be in the heap.
   1.249      Prio operator[](const Item &i) const {
   1.250        int idx = _iim[i];
   1.251        return _data[idx].value;
   1.252      }
   1.253  
   1.254 -    /// \brief \c i gets to the heap with priority \c p independently
   1.255 -    /// if \c i was already there.
   1.256 +    /// \brief Set the priority of an item or insert it, if it is
   1.257 +    /// not stored in the heap.
   1.258      ///
   1.259 -    /// This method calls \ref push(\c i, \c p) if \c i is not stored
   1.260 -    /// in the heap and sets the priority of \c i to \c p otherwise.
   1.261 +    /// This method sets the priority of the given item if it is
   1.262 +    /// already stored in the heap. Otherwise it inserts the given
   1.263 +    /// item into the heap with the given priority.
   1.264      /// \param i The item.
   1.265      /// \param p The priority.
   1.266      void set(const Item &i, const Prio &p) {
   1.267 @@ -274,13 +288,12 @@
   1.268        }
   1.269      }
   1.270  
   1.271 -    /// \brief Decreases the priority of \c i to \c p.
   1.272 +    /// \brief Decrease the priority of an item to the given value.
   1.273      ///
   1.274 -    /// This method decreases the priority of item \c i to \c p.
   1.275 -    /// \pre \c i must be stored in the heap with priority at least \c
   1.276 -    /// p relative to \c Compare.
   1.277 +    /// This function decreases the priority of an item to the given value.
   1.278      /// \param i The item.
   1.279      /// \param p The priority.
   1.280 +    /// \pre \e i must be stored in the heap with priority at least \e p.
   1.281      void decrease(const Item &i, const Prio &p) {
   1.282        int idx = _iim[i];
   1.283        unlace(idx);
   1.284 @@ -291,13 +304,12 @@
   1.285        lace(idx);
   1.286      }
   1.287  
   1.288 -    /// \brief Increases the priority of \c i to \c p.
   1.289 +    /// \brief Increase the priority of an item to the given value.
   1.290      ///
   1.291 -    /// This method sets the priority of item \c i to \c p.
   1.292 -    /// \pre \c i must be stored in the heap with priority at most \c
   1.293 -    /// p relative to \c Compare.
   1.294 +    /// This function increases the priority of an item to the given value.
   1.295      /// \param i The item.
   1.296      /// \param p The priority.
   1.297 +    /// \pre \e i must be stored in the heap with priority at most \e p.
   1.298      void increase(const Item &i, const Prio &p) {
   1.299        int idx = _iim[i];
   1.300        unlace(idx);
   1.301 @@ -305,13 +317,13 @@
   1.302        lace(idx);
   1.303      }
   1.304  
   1.305 -    /// \brief Returns if \c item is in, has already been in, or has
   1.306 -    /// never been in the heap.
   1.307 +    /// \brief Return the state of an item.
   1.308      ///
   1.309 -    /// This method returns PRE_HEAP if \c item has never been in the
   1.310 -    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   1.311 -    /// otherwise. In the latter case it is possible that \c item will
   1.312 -    /// get back to the heap again.
   1.313 +    /// This method returns \c PRE_HEAP if the given item has never
   1.314 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   1.315 +    /// and \c POST_HEAP otherwise.
   1.316 +    /// In the latter case it is possible that the item will get back
   1.317 +    /// to the heap again.
   1.318      /// \param i The item.
   1.319      State state(const Item &i) const {
   1.320        int idx = _iim[i];
   1.321 @@ -319,11 +331,11 @@
   1.322        return State(idx);
   1.323      }
   1.324  
   1.325 -    /// \brief Sets the state of the \c item in the heap.
   1.326 +    /// \brief Set the state of an item in the heap.
   1.327      ///
   1.328 -    /// Sets the state of the \c item in the heap. It can be used to
   1.329 -    /// manually clear the heap when it is important to achive the
   1.330 -    /// better time complexity.
   1.331 +    /// This function sets the state of the given item in the heap.
   1.332 +    /// It can be used to manually clear the heap when it is important
   1.333 +    /// to achive better time complexity.
   1.334      /// \param i The item.
   1.335      /// \param st The state. It should not be \c IN_HEAP.
   1.336      void state(const Item& i, State st) {
   1.337 @@ -359,33 +371,44 @@
   1.338  
   1.339    }; // class BucketHeap
   1.340  
   1.341 -  /// \ingroup auxdat
   1.342 +  /// \ingroup heaps
   1.343    ///
   1.344 -  /// \brief A Simplified Bucket Heap implementation.
   1.345 +  /// \brief Simplified bucket heap data structure.
   1.346    ///
   1.347    /// This class implements a simplified \e bucket \e heap data
   1.348 -  /// structure.  It does not provide some functionality but it faster
   1.349 -  /// and simplier data structure than the BucketHeap. The main
   1.350 -  /// difference is that the BucketHeap stores for every key a double
   1.351 -  /// linked list while this class stores just simple lists. In the
   1.352 -  /// other way it does not support erasing each elements just the
   1.353 -  /// minimal and it does not supports key increasing, decreasing.
   1.354 +  /// structure. It does not provide some functionality, but it is
   1.355 +  /// faster and simpler than BucketHeap. The main difference is
   1.356 +  /// that BucketHeap stores a doubly-linked list for each key while
   1.357 +  /// this class stores only simply-linked lists. It supports erasing
   1.358 +  /// only for the item having minimum priority and it does not support
   1.359 +  /// key increasing and decreasing.
   1.360    ///
   1.361 -  /// \param IM A read and write Item int map, used internally
   1.362 -  /// to handle the cross references.
   1.363 -  /// \param MIN If the given parameter is false then instead of the
   1.364 -  /// minimum value the maximum can be retrivied with the top() and
   1.365 -  /// prio() member functions.
   1.366 +  /// Note that this implementation does not conform to the
   1.367 +  /// \ref concepts::Heap "heap concept" due to the lack of some 
   1.368 +  /// functionality.
   1.369 +  ///
   1.370 +  /// \tparam IM A read-writable item map with \c int values, used
   1.371 +  /// internally to handle the cross references.
   1.372 +  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
   1.373 +  /// The default is \e min-heap. If this parameter is set to \c false,
   1.374 +  /// then the comparison is reversed, so the top(), prio() and pop()
   1.375 +  /// functions deal with the item having maximum priority instead of the
   1.376 +  /// minimum.
   1.377    ///
   1.378    /// \sa BucketHeap
   1.379    template <typename IM, bool MIN = true >
   1.380    class SimpleBucketHeap {
   1.381  
   1.382    public:
   1.383 -    typedef typename IM::Key Item;
   1.384 +
   1.385 +    /// Type of the item-int map.
   1.386 +    typedef IM ItemIntMap;
   1.387 +    /// Type of the priorities.
   1.388      typedef int Prio;
   1.389 -    typedef std::pair<Item, Prio> Pair;
   1.390 -    typedef IM ItemIntMap;
   1.391 +    /// Type of the items stored in the heap.
   1.392 +    typedef typename ItemIntMap::Key Item;
   1.393 +    /// Type of the item-priority pairs.
   1.394 +    typedef std::pair<Item,Prio> Pair;
   1.395  
   1.396    private:
   1.397  
   1.398 @@ -393,10 +416,10 @@
   1.399  
   1.400    public:
   1.401  
   1.402 -    /// \brief Type to represent the items states.
   1.403 +    /// \brief Type to represent the states of the items.
   1.404      ///
   1.405 -    /// Each Item element have a state associated to it. It may be "in heap",
   1.406 -    /// "pre heap" or "post heap". The latter two are indifferent from the
   1.407 +    /// Each item has a state associated to it. It can be "in heap",
   1.408 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
   1.409      /// heap's point of view, but may be useful to the user.
   1.410      ///
   1.411      /// The item-int map must be initialized in such way that it assigns
   1.412 @@ -409,48 +432,53 @@
   1.413  
   1.414    public:
   1.415  
   1.416 -    /// \brief The constructor.
   1.417 +    /// \brief Constructor.
   1.418      ///
   1.419 -    /// The constructor.
   1.420 -    /// \param map should be given to the constructor, since it is used
   1.421 -    /// internally to handle the cross references. The value of the map
   1.422 -    /// should be PRE_HEAP (-1) for each element.
   1.423 +    /// Constructor.
   1.424 +    /// \param map A map that assigns \c int values to the items.
   1.425 +    /// It is used internally to handle the cross references.
   1.426 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   1.427      explicit SimpleBucketHeap(ItemIntMap &map)
   1.428        : _iim(map), _free(-1), _num(0), _minimum(0) {}
   1.429  
   1.430 -    /// \brief Returns the number of items stored in the heap.
   1.431 +    /// \brief The number of items stored in the heap.
   1.432      ///
   1.433 -    /// The number of items stored in the heap.
   1.434 +    /// This function returns the number of items stored in the heap.
   1.435      int size() const { return _num; }
   1.436  
   1.437 -    /// \brief Checks if the heap stores no items.
   1.438 +    /// \brief Check if the heap is empty.
   1.439      ///
   1.440 -    /// Returns \c true if and only if the heap stores no items.
   1.441 +    /// This function returns \c true if the heap is empty.
   1.442      bool empty() const { return _num == 0; }
   1.443  
   1.444 -    /// \brief Make empty this heap.
   1.445 +    /// \brief Make the heap empty.
   1.446      ///
   1.447 -    /// Make empty this heap. It does not change the cross reference
   1.448 -    /// map.  If you want to reuse a heap what is not surely empty you
   1.449 -    /// should first clear the heap and after that you should set the
   1.450 -    /// cross reference map for each item to \c PRE_HEAP.
   1.451 +    /// This functon makes the heap empty.
   1.452 +    /// It does not change the cross reference map. If you want to reuse
   1.453 +    /// a heap that is not surely empty, you should first clear it and
   1.454 +    /// then you should set the cross reference map to \c PRE_HEAP
   1.455 +    /// for each item.
   1.456      void clear() {
   1.457        _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
   1.458      }
   1.459  
   1.460      /// \brief Insert a pair of item and priority into the heap.
   1.461      ///
   1.462 -    /// Adds \c p.first to the heap with priority \c p.second.
   1.463 +    /// This function inserts \c p.first to the heap with priority
   1.464 +    /// \c p.second.
   1.465      /// \param p The pair to insert.
   1.466 +    /// \pre \c p.first must not be stored in the heap.
   1.467      void push(const Pair& p) {
   1.468        push(p.first, p.second);
   1.469      }
   1.470  
   1.471      /// \brief Insert an item into the heap with the given priority.
   1.472      ///
   1.473 -    /// Adds \c i to the heap with priority \c p.
   1.474 +    /// This function inserts the given item into the heap with the
   1.475 +    /// given priority.
   1.476      /// \param i The item to insert.
   1.477      /// \param p The priority of the item.
   1.478 +    /// \pre \e i must not be stored in the heap.
   1.479      void push(const Item &i, const Prio &p) {
   1.480        int idx;
   1.481        if (_free == -1) {
   1.482 @@ -471,10 +499,10 @@
   1.483        ++_num;
   1.484      }
   1.485  
   1.486 -    /// \brief Returns the item with minimum priority.
   1.487 +    /// \brief Return the item having minimum priority.
   1.488      ///
   1.489 -    /// This method returns the item with minimum priority.
   1.490 -    /// \pre The heap must be nonempty.
   1.491 +    /// This function returns the item having minimum priority.
   1.492 +    /// \pre The heap must be non-empty.
   1.493      Item top() const {
   1.494        while (_first[_minimum] == -1) {
   1.495          Direction::increase(_minimum);
   1.496 @@ -482,10 +510,10 @@
   1.497        return _data[_first[_minimum]].item;
   1.498      }
   1.499  
   1.500 -    /// \brief Returns the minimum priority.
   1.501 +    /// \brief The minimum priority.
   1.502      ///
   1.503 -    /// It returns the minimum priority.
   1.504 -    /// \pre The heap must be nonempty.
   1.505 +    /// This function returns the minimum priority.
   1.506 +    /// \pre The heap must be non-empty.
   1.507      Prio prio() const {
   1.508        while (_first[_minimum] == -1) {
   1.509          Direction::increase(_minimum);
   1.510 @@ -493,9 +521,9 @@
   1.511        return _minimum;
   1.512      }
   1.513  
   1.514 -    /// \brief Deletes the item with minimum priority.
   1.515 +    /// \brief Remove the item having minimum priority.
   1.516      ///
   1.517 -    /// This method deletes the item with minimum priority from the heap.
   1.518 +    /// This function removes the item having minimum priority.
   1.519      /// \pre The heap must be non-empty.
   1.520      void pop() {
   1.521        while (_first[_minimum] == -1) {
   1.522 @@ -509,16 +537,15 @@
   1.523        --_num;
   1.524      }
   1.525  
   1.526 -    /// \brief Returns the priority of \c i.
   1.527 +    /// \brief The priority of the given item.
   1.528      ///
   1.529 -    /// This function returns the priority of item \c i.
   1.530 -    /// \warning This operator is not a constant time function
   1.531 -    /// because it scans the whole data structure to find the proper
   1.532 -    /// value.
   1.533 -    /// \pre \c i must be in the heap.
   1.534 +    /// This function returns the priority of the given item.
   1.535      /// \param i The item.
   1.536 +    /// \pre \e i must be in the heap.
   1.537 +    /// \warning This operator is not a constant time function because
   1.538 +    /// it scans the whole data structure to find the proper value.
   1.539      Prio operator[](const Item &i) const {
   1.540 -      for (int k = 0; k < _first.size(); ++k) {
   1.541 +      for (int k = 0; k < int(_first.size()); ++k) {
   1.542          int idx = _first[k];
   1.543          while (idx != -1) {
   1.544            if (_data[idx].item == i) {
   1.545 @@ -530,13 +557,13 @@
   1.546        return -1;
   1.547      }
   1.548  
   1.549 -    /// \brief Returns if \c item is in, has already been in, or has
   1.550 -    /// never been in the heap.
   1.551 +    /// \brief Return the state of an item.
   1.552      ///
   1.553 -    /// This method returns PRE_HEAP if \c item has never been in the
   1.554 -    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   1.555 -    /// otherwise. In the latter case it is possible that \c item will
   1.556 -    /// get back to the heap again.
   1.557 +    /// This method returns \c PRE_HEAP if the given item has never
   1.558 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   1.559 +    /// and \c POST_HEAP otherwise.
   1.560 +    /// In the latter case it is possible that the item will get back
   1.561 +    /// to the heap again.
   1.562      /// \param i The item.
   1.563      State state(const Item &i) const {
   1.564        int idx = _iim[i];