COIN-OR::LEMON - Graph Library

Changeset 756:0747f332c478 in lemon


Ignore:
Timestamp:
07/08/09 17:21:30 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Improve and unify the documentation of heaps (#299)
and avoid a warning in SimpleBucketHeap::operator[].

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r730 r756  
    2222///\ingroup auxdat 
    2323///\file 
    24 ///\brief Binary Heap implementation. 
     24///\brief Binary heap implementation. 
    2525 
    2626#include <vector> 
     
    3030namespace lemon { 
    3131 
    32   ///\ingroup auxdat 
     32  /// \ingroup auxdat 
    3333  /// 
    34   ///\brief A Binary Heap implementation. 
     34  /// \brief Binary heap data structure. 
    3535  /// 
    36   ///This class implements the \e binary \e heap data structure. 
     36  /// This class implements the \e binary \e heap data structure. 
     37  /// It fully conforms to the \ref concepts::Heap "heap concept". 
    3738  /// 
    38   ///A \e heap is a data structure for storing items with specified values 
    39   ///called \e priorities in such a way that finding the item with minimum 
    40   ///priority is efficient. \c CMP specifies the ordering of the priorities. 
    41   ///In a heap one can change the priority of an item, add or erase an 
    42   ///item, etc. 
    43   /// 
    44   ///\tparam PR Type of the priority of the items. 
    45   ///\tparam IM A read and writable item map with int values, used internally 
    46   ///to handle the cross references. 
    47   ///\tparam CMP A functor class for the ordering of the priorities. 
    48   ///The default is \c std::less<PR>. 
    49   /// 
    50   ///\sa FibHeap 
    51   ///\sa Dijkstra 
     39  /// \tparam PR Type of the priorities of the items. 
     40  /// \tparam IM A read-writable item map with \c int values, used 
     41  /// internally to handle the cross references. 
     42  /// \tparam CMP A functor class for comparing the priorities. 
     43  /// The default is \c std::less<PR>. 
     44#ifdef DOXYGEN 
     45  template <typename PR, typename IM, typename CMP> 
     46#else 
    5247  template <typename PR, typename IM, typename CMP = std::less<PR> > 
     48#endif 
    5349  class BinHeap { 
    54  
    5550  public: 
    56     ///\e 
     51 
     52    /// Type of the item-int map. 
    5753    typedef IM ItemIntMap; 
    58     ///\e 
     54    /// Type of the priorities. 
    5955    typedef PR Prio; 
    60     ///\e 
     56    /// Type of the items stored in the heap. 
    6157    typedef typename ItemIntMap::Key Item; 
    62     ///\e 
     58    /// Type of the item-priority pairs. 
    6359    typedef std::pair<Item,Prio> Pair; 
    64     ///\e 
     60    /// Functor type for comparing the priorities. 
    6561    typedef CMP Compare; 
    6662 
    67     /// \brief Type to represent the items states. 
    68     /// 
    69     /// Each Item element have a state associated to it. It may be "in heap", 
    70     /// "pre heap" or "post heap". The latter two are indifferent from the 
     63    /// \brief Type to represent the states of the items. 
     64    /// 
     65    /// Each item has a state associated to it. It can be "in heap", 
     66    /// "pre-heap" or "post-heap". The latter two are indifferent from the 
    7167    /// heap's point of view, but may be useful to the user. 
    7268    /// 
     
    8581 
    8682  public: 
    87     /// \brief The constructor. 
    88     /// 
    89     /// The constructor. 
    90     /// \param map should be given to the constructor, since it is used 
    91     /// internally to handle the cross references. The value of the map 
    92     /// must be \c PRE_HEAP (<tt>-1</tt>) for every item. 
     83 
     84    /// \brief Constructor. 
     85    /// 
     86    /// Constructor. 
     87    /// \param map A map that assigns \c int values to the items. 
     88    /// It is used internally to handle the cross references. 
     89    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
    9390    explicit BinHeap(ItemIntMap &map) : _iim(map) {} 
    9491 
    95     /// \brief The constructor. 
    96     /// 
    97     /// The constructor. 
    98     /// \param map should be given to the constructor, since it is used 
    99     /// internally to handle the cross references. The value of the map 
    100     /// should be PRE_HEAP (-1) for each element. 
    101     /// 
    102     /// \param comp The comparator function object. 
     92    /// \brief Constructor. 
     93    /// 
     94    /// Constructor. 
     95    /// \param map A map that assigns \c int values to the items. 
     96    /// It is used internally to handle the cross references. 
     97    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     98    /// \param comp The function object used for comparing the priorities. 
    10399    BinHeap(ItemIntMap &map, const Compare &comp) 
    104100      : _iim(map), _comp(comp) {} 
    105101 
    106102 
    107     /// The number of items stored in the heap. 
    108     /// 
    109     /// \brief Returns the number of items stored in the heap. 
     103    /// \brief The number of items stored in the heap. 
     104    /// 
     105    /// This function returns the number of items stored in the heap. 
    110106    int size() const { return _data.size(); } 
    111107 
    112     /// \brief Checks if the heap stores no items. 
    113     /// 
    114     /// Returns \c true if and only if the heap stores no items. 
     108    /// \brief Check if the heap is empty. 
     109    /// 
     110    /// This function returns \c true if the heap is empty. 
    115111    bool empty() const { return _data.empty(); } 
    116112 
    117     /// \brief Make empty this heap. 
    118     /// 
    119     /// Make empty this heap. It does not change the cross reference map. 
    120     /// If you want to reuse what is not surely empty you should first clear 
    121     /// the heap and after that you should set the cross reference map for 
    122     /// each item to \c PRE_HEAP. 
     113    /// \brief Make the heap empty. 
     114    /// 
     115    /// This functon makes the heap empty. 
     116    /// It does not change the cross reference map. If you want to reuse 
     117    /// a heap that is not surely empty, you should first clear it and 
     118    /// then you should set the cross reference map to \c PRE_HEAP 
     119    /// for each item. 
    123120    void clear() { 
    124121      _data.clear(); 
     
    172169 
    173170  public: 
     171 
    174172    /// \brief Insert a pair of item and priority into the heap. 
    175173    /// 
    176     /// Adds \c p.first to the heap with priority \c p.second. 
     174    /// This function inserts \c p.first to the heap with priority 
     175    /// \c p.second. 
    177176    /// \param p The pair to insert. 
     177    /// \pre \c p.first must not be stored in the heap. 
    178178    void push(const Pair &p) { 
    179179      int n = _data.size(); 
     
    182182    } 
    183183 
    184     /// \brief Insert an item into the heap with the given heap. 
    185     /// 
    186     /// Adds \c i to the heap with priority \c p. 
     184    /// \brief Insert an item into the heap with the given priority. 
     185    /// 
     186    /// This function inserts the given item into the heap with the 
     187    /// given priority. 
    187188    /// \param i The item to insert. 
    188189    /// \param p The priority of the item. 
     190    /// \pre \e i must not be stored in the heap. 
    189191    void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 
    190192 
    191     /// \brief Returns the item with minimum priority relative to \c Compare. 
    192     /// 
    193     /// This method returns the item with minimum priority relative to \c 
    194     /// Compare. 
    195     /// \pre The heap must be nonempty. 
     193    /// \brief Return the item having minimum priority. 
     194    /// 
     195    /// This function returns the item having minimum priority. 
     196    /// \pre The heap must be non-empty. 
    196197    Item top() const { 
    197198      return _data[0].first; 
    198199    } 
    199200 
    200     /// \brief Returns the minimum priority relative to \c Compare. 
    201     /// 
    202     /// It returns the minimum priority relative to \c Compare. 
    203     /// \pre The heap must be nonempty. 
     201    /// \brief The minimum priority. 
     202    /// 
     203    /// This function returns the minimum priority. 
     204    /// \pre The heap must be non-empty. 
    204205    Prio prio() const { 
    205206      return _data[0].second; 
    206207    } 
    207208 
    208     /// \brief Deletes the item with minimum priority relative to \c Compare. 
    209     /// 
    210     /// This method deletes the item with minimum priority relative to \c 
    211     /// Compare from the heap. 
     209    /// \brief Remove the item having minimum priority. 
     210    /// 
     211    /// This function removes the item having minimum priority. 
    212212    /// \pre The heap must be non-empty. 
    213213    void pop() { 
     
    220220    } 
    221221 
    222     /// \brief Deletes \c i from the heap. 
    223     /// 
    224     /// This method deletes item \c i from the heap. 
    225     /// \param i The item to erase. 
    226     /// \pre The item should be in the heap. 
     222    /// \brief Remove the given item from the heap. 
     223    /// 
     224    /// This function removes the given item from the heap if it is 
     225    /// already stored. 
     226    /// \param i The item to delete. 
     227    /// \pre \e i must be in the heap. 
    227228    void erase(const Item &i) { 
    228229      int h = _iim[i]; 
     
    237238    } 
    238239 
    239  
    240     /// \brief Returns the priority of \c i. 
    241     /// 
    242     /// This function returns the priority of item \c i. 
    243     /// \param i The item. 
    244     /// \pre \c i must be in the heap. 
     240    /// \brief The priority of the given item. 
     241    /// 
     242    /// This function returns the priority of the given item. 
     243    /// \param i The item. 
     244    /// \pre \e i must be in the heap. 
    245245    Prio operator[](const Item &i) const { 
    246246      int idx = _iim[i]; 
     
    248248    } 
    249249 
    250     /// \brief \c i gets to the heap with priority \c p independently 
    251     /// if \c i was already there. 
    252     /// 
    253     /// This method calls \ref push(\c i, \c p) if \c i is not stored 
    254     /// in the heap and sets the priority of \c i to \c p otherwise. 
     250    /// \brief Set the priority of an item or insert it, if it is 
     251    /// not stored in the heap. 
     252    /// 
     253    /// This method sets the priority of the given item if it is 
     254    /// already stored in the heap. Otherwise it inserts the given 
     255    /// item into the heap with the given priority. 
    255256    /// \param i The item. 
    256257    /// \param p The priority. 
     
    268269    } 
    269270 
    270     /// \brief Decreases the priority of \c i to \c p. 
    271     /// 
    272     /// This method decreases the priority of item \c i to \c p. 
     271    /// \brief Decrease the priority of an item to the given value. 
     272    /// 
     273    /// This function decreases the priority of an item to the given value. 
    273274    /// \param i The item. 
    274275    /// \param p The priority. 
    275     /// \pre \c i must be stored in the heap with priority at least \c 
    276     /// p relative to \c Compare. 
     276    /// \pre \e i must be stored in the heap with priority at least \e p. 
    277277    void decrease(const Item &i, const Prio &p) { 
    278278      int idx = _iim[i]; 
     
    280280    } 
    281281 
    282     /// \brief Increases the priority of \c i to \c p. 
    283     /// 
    284     /// This method sets the priority of item \c i to \c p. 
     282    /// \brief Increase the priority of an item to the given value. 
     283    /// 
     284    /// This function increases the priority of an item to the given value. 
    285285    /// \param i The item. 
    286286    /// \param p The priority. 
    287     /// \pre \c i must be stored in the heap with priority at most \c 
    288     /// p relative to \c Compare. 
     287    /// \pre \e i must be stored in the heap with priority at most \e p. 
    289288    void increase(const Item &i, const Prio &p) { 
    290289      int idx = _iim[i]; 
     
    292291    } 
    293292 
    294     /// \brief Returns if \c item is in, has already been in, or has 
    295     /// never been in the heap. 
    296     /// 
    297     /// This method returns PRE_HEAP if \c item has never been in the 
    298     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    299     /// otherwise. In the latter case it is possible that \c item will 
    300     /// get back to the heap again. 
     293    /// \brief Return the state of an item. 
     294    /// 
     295    /// This method returns \c PRE_HEAP if the given item has never 
     296    /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 
     297    /// and \c POST_HEAP otherwise. 
     298    /// In the latter case it is possible that the item will get back 
     299    /// to the heap again. 
    301300    /// \param i The item. 
    302301    State state(const Item &i) const { 
     
    307306    } 
    308307 
    309     /// \brief Sets the state of the \c item in the heap. 
    310     /// 
    311     /// Sets the state of the \c item in the heap. It can be used to 
    312     /// manually clear the heap when it is important to achive the 
    313     /// better time complexity. 
     308    /// \brief Set the state of an item in the heap. 
     309    /// 
     310    /// This function sets the state of the given item in the heap. 
     311    /// It can be used to manually clear the heap when it is important 
     312    /// to achive better time complexity. 
    314313    /// \param i The item. 
    315314    /// \param st The state. It should not be \c IN_HEAP. 
     
    328327    } 
    329328 
    330     /// \brief Replaces an item in the heap. 
    331     /// 
    332     /// The \c i item is replaced with \c j item. The \c i item should 
    333     /// be in the heap, while the \c j should be out of the heap. The 
    334     /// \c i item will out of the heap and \c j will be in the heap 
    335     /// with the same prioriority as prevoiusly the \c i item. 
     329    /// \brief Replace an item in the heap. 
     330    /// 
     331    /// This function replaces item \c i with item \c j. 
     332    /// Item \c i must be in the heap, while \c j must be out of the heap. 
     333    /// After calling this method, item \c i will be out of the 
     334    /// heap and \c j will be in the heap with the same prioriority 
     335    /// as item \c i had before. 
    336336    void replace(const Item& i, const Item& j) { 
    337337      int idx = _iim[i]; 
  • lemon/bucket_heap.h

    r730 r756  
    2222///\ingroup auxdat 
    2323///\file 
    24 ///\brief Bucket Heap implementation. 
     24///\brief Bucket heap implementation. 
    2525 
    2626#include <vector> 
     
    5656  /// \ingroup auxdat 
    5757  /// 
    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 IM A read and write Item int map, used internally 
    69   /// to handle the cross references. 
    70   /// \param MIN If the given parameter is false then instead of the 
    71   /// minimum value the maximum can be retrivied with the top() and 
    72   /// prio() member functions. 
     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 
    7378  template <typename IM, bool MIN = true> 
    7479  class BucketHeap { 
    7580 
    7681  public: 
    77     /// \e 
    78     typedef typename IM::Key Item; 
    79     /// \e 
     82 
     83    /// Type of the item-int map. 
     84    typedef IM ItemIntMap; 
     85    /// Type of the priorities. 
    8086    typedef int Prio; 
    81     /// \e 
    82     typedef std::pair<Item, Prio> Pair; 
    83     /// \e 
    84     typedef IM ItemIntMap; 
     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; 
    8591 
    8692  private: 
     
    9096  public: 
    9197 
    92     /// \brief Type to represent the items states. 
    93     /// 
    94     /// Each Item element have a state associated to it. It may be "in heap", 
    95     /// "pre heap" or "post heap". The latter two are indifferent from the 
     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 
    96102    /// heap's point of view, but may be useful to the user. 
    97103    /// 
     
    105111 
    106112  public: 
    107     /// \brief The constructor. 
    108     /// 
    109     /// The constructor. 
    110     /// \param map should be given to the constructor, since it is used 
    111     /// internally to handle the cross references. The value of the map 
    112     /// should be PRE_HEAP (-1) for each element. 
     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. 
    113120    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} 
    114121 
    115     /// The number of items stored in the heap. 
    116     /// 
    117     /// \brief Returns the number of items stored in the heap. 
     122    /// \brief The number of items stored in the heap. 
     123    /// 
     124    /// This function returns the number of items stored in the heap. 
    118125    int size() const { return _data.size(); } 
    119126 
    120     /// \brief Checks if the heap stores no items. 
    121     /// 
    122     /// Returns \c true if and only if the heap stores no items. 
     127    /// \brief Check if the heap is empty. 
     128    /// 
     129    /// This function returns \c true if the heap is empty. 
    123130    bool empty() const { return _data.empty(); } 
    124131 
    125     /// \brief Make empty this heap. 
    126     /// 
    127     /// Make empty this heap. It does not change the cross reference 
    128     /// map.  If you want to reuse a heap what is not surely empty you 
    129     /// should first clear the heap and after that you should set the 
    130     /// cross reference map for each item to \c PRE_HEAP. 
     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. 
    131139    void clear() { 
    132140      _data.clear(); _first.clear(); _minimum = 0; 
     
    175183 
    176184  public: 
     185 
    177186    /// \brief Insert a pair of item and priority into the heap. 
    178187    /// 
    179     /// Adds \c p.first to the heap with priority \c p.second. 
     188    /// This function inserts \c p.first to the heap with priority 
     189    /// \c p.second. 
    180190    /// \param p The pair to insert. 
     191    /// \pre \c p.first must not be stored in the heap. 
    181192    void push(const Pair& p) { 
    182193      push(p.first, p.second); 
     
    185196    /// \brief Insert an item into the heap with the given priority. 
    186197    /// 
    187     /// Adds \c i to the heap with priority \c p. 
     198    /// This function inserts the given item into the heap with the 
     199    /// given priority. 
    188200    /// \param i The item to insert. 
    189201    /// \param p The priority of the item. 
     202    /// \pre \e i must not be stored in the heap. 
    190203    void push(const Item &i, const Prio &p) { 
    191204      int idx = _data.size(); 
     
    198211    } 
    199212 
    200     /// \brief Returns the item with minimum priority. 
    201     /// 
    202     /// This method returns the item with minimum priority. 
    203     /// \pre The heap must be nonempty. 
     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. 
    204217    Item top() const { 
    205218      while (_first[_minimum] == -1) { 
     
    209222    } 
    210223 
    211     /// \brief Returns the minimum priority. 
    212     /// 
    213     /// It returns the minimum priority. 
    214     /// \pre The heap must be nonempty. 
     224    /// \brief The minimum priority. 
     225    /// 
     226    /// This function returns the minimum priority. 
     227    /// \pre The heap must be non-empty. 
    215228    Prio prio() const { 
    216229      while (_first[_minimum] == -1) { 
     
    220233    } 
    221234 
    222     /// \brief Deletes the item with minimum priority. 
    223     /// 
    224     /// This method deletes the item with minimum priority from the heap. 
     235    /// \brief Remove the item having minimum priority. 
     236    /// 
     237    /// This function removes the item having minimum priority. 
    225238    /// \pre The heap must be non-empty. 
    226239    void pop() { 
     
    234247    } 
    235248 
    236     /// \brief Deletes \c i from the heap. 
    237     /// 
    238     /// This method deletes item \c i from the heap, if \c i was 
    239     /// already stored in the heap. 
    240     /// \param i The item to erase. 
     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. 
    241255    void erase(const Item &i) { 
    242256      int idx = _iim[i]; 
     
    246260    } 
    247261 
    248  
    249     /// \brief Returns the priority of \c i. 
    250     /// 
    251     /// This function returns the priority of item \c i. 
    252     /// \pre \c i must be in the heap. 
    253     /// \param i The item. 
     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. 
    254267    Prio operator[](const Item &i) const { 
    255268      int idx = _iim[i]; 
     
    257270    } 
    258271 
    259     /// \brief \c i gets to the heap with priority \c p independently 
    260     /// if \c i was already there. 
    261     /// 
    262     /// This method calls \ref push(\c i, \c p) if \c i is not stored 
    263     /// in the heap and sets the priority of \c i to \c p otherwise. 
     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. 
    264278    /// \param i The item. 
    265279    /// \param p The priority. 
     
    275289    } 
    276290 
    277     /// \brief Decreases the priority of \c i to \c p. 
    278     /// 
    279     /// This method decreases the priority of item \c i to \c p. 
    280     /// \pre \c i must be stored in the heap with priority at least \c 
    281     /// p relative to \c Compare. 
     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. 
    282294    /// \param i The item. 
    283295    /// \param p The priority. 
     296    /// \pre \e i must be stored in the heap with priority at least \e p. 
    284297    void decrease(const Item &i, const Prio &p) { 
    285298      int idx = _iim[i]; 
     
    292305    } 
    293306 
    294     /// \brief Increases the priority of \c i to \c p. 
    295     /// 
    296     /// This method sets the priority of item \c i to \c p. 
    297     /// \pre \c i must be stored in the heap with priority at most \c 
    298     /// p relative to \c Compare. 
     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. 
    299310    /// \param i The item. 
    300311    /// \param p The priority. 
     312    /// \pre \e i must be stored in the heap with priority at most \e p. 
    301313    void increase(const Item &i, const Prio &p) { 
    302314      int idx = _iim[i]; 
     
    306318    } 
    307319 
    308     /// \brief Returns if \c item is in, has already been in, or has 
    309     /// never been in the heap. 
    310     /// 
    311     /// This method returns PRE_HEAP if \c item has never been in the 
    312     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    313     /// otherwise. In the latter case it is possible that \c item will 
    314     /// get back to the heap again. 
     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. 
    315327    /// \param i The item. 
    316328    State state(const Item &i) const { 
     
    320332    } 
    321333 
    322     /// \brief Sets the state of the \c item in the heap. 
    323     /// 
    324     /// Sets the state of the \c item in the heap. It can be used to 
    325     /// manually clear the heap when it is important to achive the 
    326     /// better time complexity. 
     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. 
    327339    /// \param i The item. 
    328340    /// \param st The state. It should not be \c IN_HEAP. 
     
    362374  /// \ingroup auxdat 
    363375  /// 
    364   /// \brief A Simplified Bucket Heap implementation. 
     376  /// \brief Simplified bucket heap data structure. 
    365377  /// 
    366378  /// This class implements a simplified \e bucket \e heap data 
    367   /// structure.  It does not provide some functionality but it faster 
    368   /// and simplier data structure than the BucketHeap. The main 
    369   /// difference is that the BucketHeap stores for every key a double 
    370   /// linked list while this class stores just simple lists. In the 
    371   /// other way it does not support erasing each elements just the 
    372   /// minimal and it does not supports key increasing, decreasing. 
    373   /// 
    374   /// \param IM A read and write Item int map, used internally 
    375   /// to handle the cross references. 
    376   /// \param MIN If the given parameter is false then instead of the 
    377   /// minimum value the maximum can be retrivied with the top() and 
    378   /// prio() member functions. 
     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. 
    379397  /// 
    380398  /// \sa BucketHeap 
     
    383401 
    384402  public: 
    385     typedef typename IM::Key Item; 
     403 
     404    /// Type of the item-int map. 
     405    typedef IM ItemIntMap; 
     406    /// Type of the priorities. 
    386407    typedef int Prio; 
    387     typedef std::pair<Item, Prio> Pair; 
    388     typedef IM ItemIntMap; 
     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; 
    389412 
    390413  private: 
     
    394417  public: 
    395418 
    396     /// \brief Type to represent the items states. 
    397     /// 
    398     /// Each Item element have a state associated to it. It may be "in heap", 
    399     /// "pre heap" or "post heap". The latter two are indifferent from the 
     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 
    400423    /// heap's point of view, but may be useful to the user. 
    401424    /// 
     
    410433  public: 
    411434 
    412     /// \brief The constructor. 
    413     /// 
    414     /// The constructor. 
    415     /// \param map should be given to the constructor, since it is used 
    416     /// internally to handle the cross references. The value of the map 
    417     /// should be PRE_HEAP (-1) for each element. 
     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. 
    418441    explicit SimpleBucketHeap(ItemIntMap &map) 
    419442      : _iim(map), _free(-1), _num(0), _minimum(0) {} 
    420443 
    421     /// \brief Returns the number of items stored in the heap. 
    422     /// 
    423     /// The number of items stored in the heap. 
     444    /// \brief The number of items stored in the heap. 
     445    /// 
     446    /// This function returns the number of items stored in the heap. 
    424447    int size() const { return _num; } 
    425448 
    426     /// \brief Checks if the heap stores no items. 
    427     /// 
    428     /// Returns \c true if and only if the heap stores no items. 
     449    /// \brief Check if the heap is empty. 
     450    /// 
     451    /// This function returns \c true if the heap is empty. 
    429452    bool empty() const { return _num == 0; } 
    430453 
    431     /// \brief Make empty this heap. 
    432     /// 
    433     /// Make empty this heap. It does not change the cross reference 
    434     /// map.  If you want to reuse a heap what is not surely empty you 
    435     /// should first clear the heap and after that you should set the 
    436     /// cross reference map for each item to \c PRE_HEAP. 
     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. 
    437461    void clear() { 
    438462      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; 
     
    441465    /// \brief Insert a pair of item and priority into the heap. 
    442466    /// 
    443     /// Adds \c p.first to the heap with priority \c p.second. 
     467    /// This function inserts \c p.first to the heap with priority 
     468    /// \c p.second. 
    444469    /// \param p The pair to insert. 
     470    /// \pre \c p.first must not be stored in the heap. 
    445471    void push(const Pair& p) { 
    446472      push(p.first, p.second); 
     
    449475    /// \brief Insert an item into the heap with the given priority. 
    450476    /// 
    451     /// Adds \c i to the heap with priority \c p. 
     477    /// This function inserts the given item into the heap with the 
     478    /// given priority. 
    452479    /// \param i The item to insert. 
    453480    /// \param p The priority of the item. 
     481    /// \pre \e i must not be stored in the heap. 
    454482    void push(const Item &i, const Prio &p) { 
    455483      int idx; 
     
    472500    } 
    473501 
    474     /// \brief Returns the item with minimum priority. 
    475     /// 
    476     /// This method returns the item with minimum priority. 
    477     /// \pre The heap must be nonempty. 
     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. 
    478506    Item top() const { 
    479507      while (_first[_minimum] == -1) { 
     
    483511    } 
    484512 
    485     /// \brief Returns the minimum priority. 
    486     /// 
    487     /// It returns the minimum priority. 
    488     /// \pre The heap must be nonempty. 
     513    /// \brief The minimum priority. 
     514    /// 
     515    /// This function returns the minimum priority. 
     516    /// \pre The heap must be non-empty. 
    489517    Prio prio() const { 
    490518      while (_first[_minimum] == -1) { 
     
    494522    } 
    495523 
    496     /// \brief Deletes the item with minimum priority. 
    497     /// 
    498     /// This method deletes the item with minimum priority from the heap. 
     524    /// \brief Remove the item having minimum priority. 
     525    /// 
     526    /// This function removes the item having minimum priority. 
    499527    /// \pre The heap must be non-empty. 
    500528    void pop() { 
     
    510538    } 
    511539 
    512     /// \brief Returns the priority of \c i. 
    513     /// 
    514     /// This function returns the priority of item \c i. 
    515     /// \warning This operator is not a constant time function 
    516     /// because it scans the whole data structure to find the proper 
    517     /// value. 
    518     /// \pre \c i must be in the heap. 
    519     /// \param i The item. 
     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. 
    520547    Prio operator[](const Item &i) const { 
    521       for (int k = 0; k < _first.size(); ++k) { 
     548      for (int k = 0; k < int(_first.size()); ++k) { 
    522549        int idx = _first[k]; 
    523550        while (idx != -1) { 
     
    531558    } 
    532559 
    533     /// \brief Returns if \c item is in, has already been in, or has 
    534     /// never been in the heap. 
    535     /// 
    536     /// This method returns PRE_HEAP if \c item has never been in the 
    537     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    538     /// otherwise. In the latter case it is possible that \c item will 
    539     /// get back to the heap again. 
     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. 
    540567    /// \param i The item. 
    541568    State state(const Item &i) const { 
  • lemon/concepts/heap.h

    r631 r756  
    1717 */ 
    1818 
     19#ifndef LEMON_CONCEPTS_HEAP_H 
     20#define LEMON_CONCEPTS_HEAP_H 
     21 
    1922///\ingroup concept 
    2023///\file 
    2124///\brief The concept of heaps. 
    2225 
    23 #ifndef LEMON_CONCEPTS_HEAP_H 
    24 #define LEMON_CONCEPTS_HEAP_H 
    25  
    2626#include <lemon/core.h> 
    2727#include <lemon/concept_check.h> 
     
    3636    /// \brief The heap concept. 
    3737    /// 
    38     /// Concept class describing the main interface of heaps. A \e heap 
    39     /// is a data structure for storing items with specified values called 
    40     /// \e priorities in such a way that finding the item with minimum 
    41     /// priority is efficient. In a heap one can change the priority of an 
    42     /// item, add or erase an item, etc. 
     38    /// This concept class describes the main interface of heaps. 
     39    /// The various heap structures are efficient 
     40    /// implementations of the abstract data type \e priority \e queue. 
     41    /// They store items with specified values called \e priorities 
     42    /// in such a way that finding and removing the item with minimum 
     43    /// priority are efficient. The basic operations are adding and 
     44    /// erasing items, changing the priority of an item, etc. 
    4345    /// 
    44     /// \tparam PR Type of the priority of the items. 
    45     /// \tparam IM A read and writable item map with int values, used 
     46    /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. 
     47    /// Any class that conforms to this concept can be used easily in such 
     48    /// algorithms. 
     49    /// 
     50    /// \tparam PR Type of the priorities of the items. 
     51    /// \tparam IM A read-writable item map with \c int values, used 
    4652    /// internally to handle the cross references. 
    47     /// \tparam Comp A functor class for the ordering of the priorities. 
     53    /// \tparam CMP A functor class for comparing the priorities. 
    4854    /// The default is \c std::less<PR>. 
    4955#ifdef DOXYGEN 
    50     template <typename PR, typename IM, typename Comp = std::less<PR> > 
     56    template <typename PR, typename IM, typename CMP> 
    5157#else 
    52     template <typename PR, typename IM> 
     58    template <typename PR, typename IM, typename CMP = std::less<PR> > 
    5359#endif 
    5460    class Heap { 
     
    6571      /// 
    6672      /// Each item has a state associated to it. It can be "in heap", 
    67       /// "pre heap" or "post heap". The later two are indifferent 
    68       /// from the point of view of the heap, but may be useful for 
    69       /// the user. 
     73      /// "pre-heap" or "post-heap". The latter two are indifferent from the 
     74      /// heap's point of view, but may be useful to the user. 
    7075      /// 
    7176      /// The item-int map must be initialized in such way that it assigns 
     
    7378      enum State { 
    7479        IN_HEAP = 0,    ///< = 0. The "in heap" state constant. 
    75         PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant. 
    76         POST_HEAP = -2  ///< = -2. The "post heap" state constant. 
     80        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant. 
     81        POST_HEAP = -2  ///< = -2. The "post-heap" state constant. 
    7782      }; 
    7883 
    79       /// \brief The constructor. 
    80       /// 
    81       /// The constructor. 
     84      /// \brief Constructor. 
     85      /// 
     86      /// Constructor. 
    8287      /// \param map A map that assigns \c int values to keys of type 
    8388      /// \c Item. It is used internally by the heap implementations to 
    8489      /// handle the cross references. The assigned value must be 
    85       /// \c PRE_HEAP (<tt>-1</tt>) for every item. 
     90      /// \c PRE_HEAP (<tt>-1</tt>) for each item. 
    8691      explicit Heap(ItemIntMap &map) {} 
    8792 
     93      /// \brief Constructor. 
     94      /// 
     95      /// Constructor. 
     96      /// \param map A map that assigns \c int values to keys of type 
     97      /// \c Item. It is used internally by the heap implementations to 
     98      /// handle the cross references. The assigned value must be 
     99      /// \c PRE_HEAP (<tt>-1</tt>) for each item. 
     100      /// \param comp The function object used for comparing the priorities. 
     101      explicit Heap(ItemIntMap &map, const CMP &comp) {} 
     102 
    88103      /// \brief The number of items stored in the heap. 
    89104      /// 
    90       /// Returns the number of items stored in the heap. 
     105      /// This function returns the number of items stored in the heap. 
    91106      int size() const { return 0; } 
    92107 
    93       /// \brief Checks if the heap is empty. 
    94       /// 
    95       /// Returns \c true if the heap is empty. 
     108      /// \brief Check if the heap is empty. 
     109      /// 
     110      /// This function returns \c true if the heap is empty. 
    96111      bool empty() const { return false; } 
    97112 
    98       /// \brief Makes the heap empty. 
    99       /// 
    100       /// Makes the heap empty. 
    101       void clear(); 
    102  
    103       /// \brief Inserts an item into the heap with the given priority. 
    104       /// 
    105       /// Inserts the given item into the heap with the given priority. 
     113      /// \brief Make the heap empty. 
     114      /// 
     115      /// This functon makes the heap empty. 
     116      /// It does not change the cross reference map. If you want to reuse 
     117      /// a heap that is not surely empty, you should first clear it and 
     118      /// then you should set the cross reference map to \c PRE_HEAP 
     119      /// for each item. 
     120      void clear() {} 
     121 
     122      /// \brief Insert an item into the heap with the given priority. 
     123      /// 
     124      /// This function inserts the given item into the heap with the 
     125      /// given priority. 
    106126      /// \param i The item to insert. 
    107127      /// \param p The priority of the item. 
     128      /// \pre \e i must not be stored in the heap. 
    108129      void push(const Item &i, const Prio &p) {} 
    109130 
    110       /// \brief Returns the item having minimum priority. 
    111       /// 
    112       /// Returns the item having minimum priority. 
     131      /// \brief Return the item having minimum priority. 
     132      /// 
     133      /// This function returns the item having minimum priority. 
    113134      /// \pre The heap must be non-empty. 
    114135      Item top() const {} 
     
    116137      /// \brief The minimum priority. 
    117138      /// 
    118       /// Returns the minimum priority. 
     139      /// This function returns the minimum priority. 
    119140      /// \pre The heap must be non-empty. 
    120141      Prio prio() const {} 
    121142 
    122       /// \brief Removes the item having minimum priority. 
    123       /// 
    124       /// Removes the item having minimum priority. 
     143      /// \brief Remove the item having minimum priority. 
     144      /// 
     145      /// This function removes the item having minimum priority. 
    125146      /// \pre The heap must be non-empty. 
    126147      void pop() {} 
    127148 
    128       /// \brief Removes an item from the heap. 
    129       /// 
    130       /// Removes the given item from the heap if it is already stored. 
     149      /// \brief Remove the given item from the heap. 
     150      /// 
     151      /// This function removes the given item from the heap if it is 
     152      /// already stored. 
    131153      /// \param i The item to delete. 
     154      /// \pre \e i must be in the heap. 
    132155      void erase(const Item &i) {} 
    133156 
    134       /// \brief The priority of an item. 
    135       /// 
    136       /// Returns the priority of the given item. 
    137       /// \param i The item. 
    138       /// \pre \c i must be in the heap. 
     157      /// \brief The priority of the given item. 
     158      /// 
     159      /// This function returns the priority of the given item. 
     160      /// \param i The item. 
     161      /// \pre \e i must be in the heap. 
    139162      Prio operator[](const Item &i) const {} 
    140163 
    141       /// \brief Sets the priority of an item or inserts it, if it is 
     164      /// \brief Set the priority of an item or insert it, if it is 
    142165      /// not stored in the heap. 
    143166      /// 
    144167      /// This method sets the priority of the given item if it is 
    145       /// already stored in the heap. 
    146       /// Otherwise it inserts the given item with the given priority. 
     168      /// already stored in the heap. Otherwise it inserts the given 
     169      /// item into the heap with the given priority. 
    147170      /// 
    148171      /// \param i The item. 
     
    150173      void set(const Item &i, const Prio &p) {} 
    151174 
    152       /// \brief Decreases the priority of an item to the given value. 
    153       /// 
    154       /// Decreases the priority of an item to the given value. 
     175      /// \brief Decrease the priority of an item to the given value. 
     176      /// 
     177      /// This function decreases the priority of an item to the given value. 
    155178      /// \param i The item. 
    156179      /// \param p The priority. 
    157       /// \pre \c i must be stored in the heap with priority at least \c p. 
     180      /// \pre \e i must be stored in the heap with priority at least \e p. 
    158181      void decrease(const Item &i, const Prio &p) {} 
    159182 
    160       /// \brief Increases the priority of an item to the given value. 
    161       /// 
    162       /// Increases the priority of an item to the given value. 
     183      /// \brief Increase the priority of an item to the given value. 
     184      /// 
     185      /// This function increases the priority of an item to the given value. 
    163186      /// \param i The item. 
    164187      /// \param p The priority. 
    165       /// \pre \c i must be stored in the heap with priority at most \c p. 
     188      /// \pre \e i must be stored in the heap with priority at most \e p. 
    166189      void increase(const Item &i, const Prio &p) {} 
    167190 
    168       /// \brief Returns if an item is in, has already been in, or has 
    169       /// never been in the heap. 
     191      /// \brief Return the state of an item. 
    170192      /// 
    171193      /// This method returns \c PRE_HEAP if the given item has never 
     
    177199      State state(const Item &i) const {} 
    178200 
    179       /// \brief Sets the state of an item in the heap. 
    180       /// 
    181       /// Sets the state of the given item in the heap. It can be used 
    182       /// to manually clear the heap when it is important to achive the 
    183       /// better time complexity. 
     201      /// \brief Set the state of an item in the heap. 
     202      /// 
     203      /// This function sets the state of the given item in the heap. 
     204      /// It can be used to manually clear the heap when it is important 
     205      /// to achive better time complexity. 
    184206      /// \param i The item. 
    185207      /// \param st The state. It should not be \c IN_HEAP. 
  • lemon/fib_heap.h

    r730 r756  
    2222///\file 
    2323///\ingroup auxdat 
    24 ///\brief Fibonacci Heap implementation. 
     24///\brief Fibonacci heap implementation. 
    2525 
    2626#include <vector> 
     27#include <utility> 
    2728#include <functional> 
    2829#include <lemon/math.h> 
     
    3233  /// \ingroup auxdat 
    3334  /// 
    34   ///\brief Fibonacci Heap. 
     35  /// \brief Fibonacci heap data structure. 
    3536  /// 
    36   ///This class implements the \e Fibonacci \e heap data structure. A \e heap 
    37   ///is a data structure for storing items with specified values called \e 
    38   ///priorities in such a way that finding the item with minimum priority is 
    39   ///efficient. \c CMP specifies the ordering of the priorities. In a heap 
    40   ///one can change the priority of an item, add or erase an item, etc. 
     37  /// This class implements the \e Fibonacci \e heap data structure. 
     38  /// It fully conforms to the \ref concepts::Heap "heap concept". 
    4139  /// 
    42   ///The methods \ref increase and \ref erase are not efficient in a Fibonacci 
    43   ///heap. In case of many calls to these operations, it is better to use a 
    44   ///\ref BinHeap "binary heap". 
     40  /// The methods \ref increase() and \ref erase() are not efficient in a 
     41  /// Fibonacci heap. In case of many calls of these operations, it is 
     42  /// better to use other heap structure, e.g. \ref BinHeap "binary heap". 
    4543  /// 
    46   ///\param PRIO Type of the priority of the items. 
    47   ///\param IM A read and writable Item int map, used internally 
    48   ///to handle the cross references. 
    49   ///\param CMP A class for the ordering of the priorities. The 
    50   ///default is \c std::less<PRIO>. 
    51   /// 
    52   ///\sa BinHeap 
    53   ///\sa Dijkstra 
     44  /// \tparam PR Type of the priorities of the items. 
     45  /// \tparam IM A read-writable item map with \c int values, used 
     46  /// internally to handle the cross references. 
     47  /// \tparam CMP A functor class for comparing the priorities. 
     48  /// The default is \c std::less<PR>. 
    5449#ifdef DOXYGEN 
    55   template <typename PRIO, typename IM, typename CMP> 
     50  template <typename PR, typename IM, typename CMP> 
    5651#else 
    57   template <typename PRIO, typename IM, typename CMP = std::less<PRIO> > 
     52  template <typename PR, typename IM, typename CMP = std::less<PR> > 
    5853#endif 
    5954  class FibHeap { 
    6055  public: 
    61     ///\e 
     56 
     57    /// Type of the item-int map. 
    6258    typedef IM ItemIntMap; 
    63     ///\e 
    64     typedef PRIO Prio; 
    65     ///\e 
     59    /// Type of the priorities. 
     60    typedef PR Prio; 
     61    /// Type of the items stored in the heap. 
    6662    typedef typename ItemIntMap::Key Item; 
    67     ///\e 
     63    /// Type of the item-priority pairs. 
    6864    typedef std::pair<Item,Prio> Pair; 
    69     ///\e 
     65    /// Functor type for comparing the priorities. 
    7066    typedef CMP Compare; 
    7167 
     
    8177  public: 
    8278 
    83     /// \brief Type to represent the items states. 
    84     /// 
    85     /// Each Item element have a state associated to it. It may be "in heap", 
    86     /// "pre heap" or "post heap". The latter two are indifferent from the 
     79    /// \brief Type to represent the states of the items. 
     80    /// 
     81    /// Each item has a state associated to it. It can be "in heap", 
     82    /// "pre-heap" or "post-heap". The latter two are indifferent from the 
    8783    /// heap's point of view, but may be useful to the user. 
    8884    /// 
     
    9591    }; 
    9692 
    97     /// \brief The constructor 
    98     /// 
    99     /// \c map should be given to the constructor, since it is 
    100     ///   used internally to handle the cross references. 
     93    /// \brief Constructor. 
     94    /// 
     95    /// Constructor. 
     96    /// \param map A map that assigns \c int values to the items. 
     97    /// It is used internally to handle the cross references. 
     98    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
    10199    explicit FibHeap(ItemIntMap &map) 
    102100      : _minimum(0), _iim(map), _num() {} 
    103101 
    104     /// \brief The constructor 
    105     /// 
    106     /// \c map should be given to the constructor, since it is used 
    107     /// internally to handle the cross references. \c comp is an 
    108     /// object for ordering of the priorities. 
     102    /// \brief Constructor. 
     103    /// 
     104    /// Constructor. 
     105    /// \param map A map that assigns \c int values to the items. 
     106    /// It is used internally to handle the cross references. 
     107    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     108    /// \param comp The function object used for comparing the priorities. 
    109109    FibHeap(ItemIntMap &map, const Compare &comp) 
    110110      : _minimum(0), _iim(map), _comp(comp), _num() {} 
     
    112112    /// \brief The number of items stored in the heap. 
    113113    /// 
    114     /// Returns the number of items stored in the heap. 
     114    /// This function returns the number of items stored in the heap. 
    115115    int size() const { return _num; } 
    116116 
    117     /// \brief Checks if the heap stores no items. 
    118     /// 
    119     ///   Returns \c true if and only if the heap stores no items. 
     117    /// \brief Check if the heap is empty. 
     118    /// 
     119    /// This function returns \c true if the heap is empty. 
    120120    bool empty() const { return _num==0; } 
    121121 
    122     /// \brief Make empty this heap. 
    123     /// 
    124     /// Make empty this heap. It does not change the cross reference 
    125     /// map.  If you want to reuse a heap what is not surely empty you 
    126     /// should first clear the heap and after that you should set the 
    127     /// cross reference map for each item to \c PRE_HEAP. 
     122    /// \brief Make the heap empty. 
     123    /// 
     124    /// This functon makes the heap empty. 
     125    /// It does not change the cross reference map. If you want to reuse 
     126    /// a heap that is not surely empty, you should first clear it and 
     127    /// then you should set the cross reference map to \c PRE_HEAP 
     128    /// for each item. 
    128129    void clear() { 
    129130      _data.clear(); _minimum = 0; _num = 0; 
    130131    } 
    131132 
    132     /// \brief \c item gets to the heap with priority \c value independently 
    133     /// if \c item was already there. 
    134     /// 
    135     /// This method calls \ref push(\c item, \c value) if \c item is not 
    136     /// stored in the heap and it calls \ref decrease(\c item, \c value) or 
    137     /// \ref increase(\c item, \c value) otherwise. 
    138     void set (const Item& item, const Prio& value) { 
    139       int i=_iim[item]; 
    140       if ( i >= 0 && _data[i].in ) { 
    141         if ( _comp(value, _data[i].prio) ) decrease(item, value); 
    142         if ( _comp(_data[i].prio, value) ) increase(item, value); 
    143       } else push(item, value); 
    144     } 
    145  
    146     /// \brief Adds \c item to the heap with priority \c value. 
    147     /// 
    148     /// Adds \c item to the heap with priority \c value. 
    149     /// \pre \c item must not be stored in the heap. 
    150     void push (const Item& item, const Prio& value) { 
     133    /// \brief Insert an item into the heap with the given priority. 
     134    /// 
     135    /// This function inserts the given item into the heap with the 
     136    /// given priority. 
     137    /// \param item The item to insert. 
     138    /// \param prio The priority of the item. 
     139    /// \pre \e item must not be stored in the heap. 
     140    void push (const Item& item, const Prio& prio) { 
    151141      int i=_iim[item]; 
    152142      if ( i < 0 ) { 
     
    169159        _data[_minimum].right_neighbor=i; 
    170160        _data[i].left_neighbor=_minimum; 
    171         if ( _comp( value, _data[_minimum].prio) ) _minimum=i; 
     161        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; 
    172162      } else { 
    173163        _data[i].right_neighbor=_data[i].left_neighbor=i; 
    174164        _minimum=i; 
    175165      } 
    176       _data[i].prio=value; 
     166      _data[i].prio=prio; 
    177167      ++_num; 
    178168    } 
    179169 
    180     /// \brief Returns the item with minimum priority relative to \c Compare. 
    181     /// 
    182     /// This method returns the item with minimum priority relative to \c 
    183     /// Compare. 
    184     /// \pre The heap must be nonempty. 
     170    /// \brief Return the item having minimum priority. 
     171    /// 
     172    /// This function returns the item having minimum priority. 
     173    /// \pre The heap must be non-empty. 
    185174    Item top() const { return _data[_minimum].name; } 
    186175 
    187     /// \brief Returns the minimum priority relative to \c Compare. 
    188     /// 
    189     /// It returns the minimum priority relative to \c Compare. 
    190     /// \pre The heap must be nonempty. 
    191     const Prio& prio() const { return _data[_minimum].prio; } 
    192  
    193     /// \brief Returns the priority of \c item. 
    194     /// 
    195     /// It returns the priority of \c item. 
    196     /// \pre \c item must be in the heap. 
    197     const Prio& operator[](const Item& item) const { 
    198       return _data[_iim[item]].prio; 
    199     } 
    200  
    201     /// \brief Deletes the item with minimum priority relative to \c Compare. 
    202     /// 
    203     /// This method deletes the item with minimum priority relative to \c 
    204     /// Compare from the heap. 
     176    /// \brief The minimum priority. 
     177    /// 
     178    /// This function returns the minimum priority. 
     179    /// \pre The heap must be non-empty. 
     180    Prio prio() const { return _data[_minimum].prio; } 
     181 
     182    /// \brief Remove the item having minimum priority. 
     183    /// 
     184    /// This function removes the item having minimum priority. 
    205185    /// \pre The heap must be non-empty. 
    206186    void pop() { 
     
    235215    } 
    236216 
    237     /// \brief Deletes \c item from the heap. 
    238     /// 
    239     /// This method deletes \c item from the heap, if \c item was already 
    240     /// stored in the heap. It is quite inefficient in Fibonacci heaps. 
     217    /// \brief Remove the given item from the heap. 
     218    /// 
     219    /// This function removes the given item from the heap if it is 
     220    /// already stored. 
     221    /// \param item The item to delete. 
     222    /// \pre \e item must be in the heap. 
    241223    void erase (const Item& item) { 
    242224      int i=_iim[item]; 
     
    253235    } 
    254236 
    255     /// \brief Decreases the priority of \c item to \c value. 
    256     /// 
    257     /// This method decreases the priority of \c item to \c value. 
    258     /// \pre \c item must be stored in the heap with priority at least \c 
    259     ///   value relative to \c Compare. 
    260     void decrease (Item item, const Prio& value) { 
     237    /// \brief The priority of the given item. 
     238    /// 
     239    /// This function returns the priority of the given item. 
     240    /// \param item The item. 
     241    /// \pre \e item must be in the heap. 
     242    Prio operator[](const Item& item) const { 
     243      return _data[_iim[item]].prio; 
     244    } 
     245 
     246    /// \brief Set the priority of an item or insert it, if it is 
     247    /// not stored in the heap. 
     248    /// 
     249    /// This method sets the priority of the given item if it is 
     250    /// already stored in the heap. Otherwise it inserts the given 
     251    /// item into the heap with the given priority. 
     252    /// \param item The item. 
     253    /// \param prio The priority. 
     254    void set (const Item& item, const Prio& prio) { 
    261255      int i=_iim[item]; 
    262       _data[i].prio=value; 
     256      if ( i >= 0 && _data[i].in ) { 
     257        if ( _comp(prio, _data[i].prio) ) decrease(item, prio); 
     258        if ( _comp(_data[i].prio, prio) ) increase(item, prio); 
     259      } else push(item, prio); 
     260    } 
     261 
     262    /// \brief Decrease the priority of an item to the given value. 
     263    /// 
     264    /// This function decreases the priority of an item to the given value. 
     265    /// \param item The item. 
     266    /// \param prio The priority. 
     267    /// \pre \e item must be stored in the heap with priority at least \e prio. 
     268    void decrease (const Item& item, const Prio& prio) { 
     269      int i=_iim[item]; 
     270      _data[i].prio=prio; 
    263271      int p=_data[i].parent; 
    264272 
    265       if ( p!=-1 && _comp(value, _data[p].prio) ) { 
     273      if ( p!=-1 && _comp(prio, _data[p].prio) ) { 
    266274        cut(i,p); 
    267275        cascade(p); 
    268276      } 
    269       if ( _comp(value, _data[_minimum].prio) ) _minimum=i; 
    270     } 
    271  
    272     /// \brief Increases the priority of \c item to \c value. 
    273     /// 
    274     /// This method sets the priority of \c item to \c value. Though 
    275     /// there is no precondition on the priority of \c item, this 
    276     /// method should be used only if it is indeed necessary to increase 
    277     /// (relative to \c Compare) the priority of \c item, because this 
    278     /// method is inefficient. 
    279     void increase (Item item, const Prio& value) { 
     277      if ( _comp(prio, _data[_minimum].prio) ) _minimum=i; 
     278    } 
     279 
     280    /// \brief Increase the priority of an item to the given value. 
     281    /// 
     282    /// This function increases the priority of an item to the given value. 
     283    /// \param item The item. 
     284    /// \param prio The priority. 
     285    /// \pre \e item must be stored in the heap with priority at most \e prio. 
     286    void increase (const Item& item, const Prio& prio) { 
    280287      erase(item); 
    281       push(item, value); 
    282     } 
    283  
    284  
    285     /// \brief Returns if \c item is in, has already been in, or has never 
    286     /// been in the heap. 
    287     /// 
    288     /// This method returns PRE_HEAP if \c item has never been in the 
    289     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    290     /// otherwise. In the latter case it is possible that \c item will 
    291     /// get back to the heap again. 
     288      push(item, prio); 
     289    } 
     290 
     291    /// \brief Return the state of an item. 
     292    /// 
     293    /// This method returns \c PRE_HEAP if the given item has never 
     294    /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 
     295    /// and \c POST_HEAP otherwise. 
     296    /// In the latter case it is possible that the item will get back 
     297    /// to the heap again. 
     298    /// \param item The item. 
    292299    State state(const Item &item) const { 
    293300      int i=_iim[item]; 
     
    299306    } 
    300307 
    301     /// \brief Sets the state of the \c item in the heap. 
    302     /// 
    303     /// Sets the state of the \c item in the heap. It can be used to 
    304     /// manually clear the heap when it is important to achive the 
    305     /// better time _complexity. 
     308    /// \brief Set the state of an item in the heap. 
     309    /// 
     310    /// This function sets the state of the given item in the heap. 
     311    /// It can be used to manually clear the heap when it is important 
     312    /// to achive better time complexity. 
    306313    /// \param i The item. 
    307314    /// \param st The state. It should not be \c IN_HEAP. 
  • lemon/radix_heap.h

    r730 r756  
    2222///\ingroup auxdat 
    2323///\file 
    24 ///\brief Radix Heap implementation. 
     24///\brief Radix heap implementation. 
    2525 
    2626#include <vector> 
     
    3030 
    3131 
    32   /// \ingroup auxdata 
     32  /// \ingroup auxdat 
    3333  /// 
    34   /// \brief A Radix Heap implementation. 
     34  /// \brief Radix heap data structure. 
    3535  /// 
    36   /// This class implements the \e radix \e heap data structure. A \e heap 
    37   /// is a data structure for storing items with specified values called \e 
    38   /// priorities in such a way that finding the item with minimum priority is 
    39   /// efficient. This heap type can store only items with \e int priority. 
    40   /// In a heap one can change the priority of an item, add or erase an 
    41   /// item, but the priority cannot be decreased under the last removed 
    42   /// item's priority. 
     36  /// This class implements the \e radix \e heap data structure. 
     37  /// It practically conforms to the \ref concepts::Heap "heap concept", 
     38  /// but it has some limitations due its special implementation. 
     39  /// The type of the priorities must be \c int and the priority of an 
     40  /// item cannot be decreased under the priority of the last removed item. 
    4341  /// 
    44   /// \param IM A read and writable Item int map, used internally 
    45   /// to handle the cross references. 
    46   /// 
    47   /// \see BinHeap 
    48   /// \see Dijkstra 
     42  /// \tparam IM A read-writable item map with \c int values, used 
     43  /// internally to handle the cross references. 
    4944  template <typename IM> 
    5045  class RadixHeap { 
    5146 
    5247  public: 
    53     typedef typename IM::Key Item; 
     48 
     49    /// Type of the item-int map. 
     50    typedef IM ItemIntMap; 
     51    /// Type of the priorities. 
    5452    typedef int Prio; 
    55     typedef IM ItemIntMap; 
     53    /// Type of the items stored in the heap. 
     54    typedef typename ItemIntMap::Key Item; 
    5655 
    5756    /// \brief Exception thrown by RadixHeap. 
    5857    /// 
    59     /// This Exception is thrown when a smaller priority 
    60     /// is inserted into the \e RadixHeap then the last time erased. 
     58    /// This exception is thrown when an item is inserted into a 
     59    /// RadixHeap with a priority smaller than the last erased one. 
    6160    /// \see RadixHeap 
    62  
    6361    class UnderFlowPriorityError : public Exception { 
    6462    public: 
     
    6866    }; 
    6967 
    70     /// \brief Type to represent the items states. 
    71     /// 
    72     /// Each Item element have a state associated to it. It may be "in heap", 
    73     /// "pre heap" or "post heap". The latter two are indifferent from the 
     68    /// \brief Type to represent the states of the items. 
     69    /// 
     70    /// Each item has a state associated to it. It can be "in heap", 
     71    /// "pre-heap" or "post-heap". The latter two are indifferent from the 
    7472    /// heap's point of view, but may be useful to the user. 
    7573    /// 
    76     /// The ItemIntMap \e should be initialized in such way that it maps 
    77     /// PRE_HEAP (-1) to any element to be put in the heap... 
     74    /// The item-int map must be initialized in such way that it assigns 
     75    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 
    7876    enum State { 
    79       IN_HEAP = 0, 
    80       PRE_HEAP = -1, 
    81       POST_HEAP = -2 
     77      IN_HEAP = 0,    ///< = 0. 
     78      PRE_HEAP = -1,  ///< = -1. 
     79      POST_HEAP = -2  ///< = -2. 
    8280    }; 
    8381 
     
    102100    ItemIntMap &_iim; 
    103101 
    104  
    105102  public: 
    106     /// \brief The constructor. 
    107     /// 
    108     /// The constructor. 
    109     /// 
    110     /// \param map It should be given to the constructor, since it is used 
    111     /// internally to handle the cross references. The value of the map 
    112     /// should be PRE_HEAP (-1) for each element. 
    113     /// 
    114     /// \param minimal The initial minimal value of the heap. 
    115     /// \param capacity It determines the initial capacity of the heap. 
    116     RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0) 
    117       : _iim(map) { 
    118       boxes.push_back(RadixBox(minimal, 1)); 
    119       boxes.push_back(RadixBox(minimal + 1, 1)); 
    120       while (lower(boxes.size() - 1, capacity + minimal - 1)) { 
     103 
     104    /// \brief Constructor. 
     105    /// 
     106    /// Constructor. 
     107    /// \param map A map that assigns \c int values to the items. 
     108    /// It is used internally to handle the cross references. 
     109    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     110    /// \param minimum The initial minimum value of the heap. 
     111    /// \param capacity The initial capacity of the heap. 
     112    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0) 
     113      : _iim(map) 
     114    { 
     115      boxes.push_back(RadixBox(minimum, 1)); 
     116      boxes.push_back(RadixBox(minimum + 1, 1)); 
     117      while (lower(boxes.size() - 1, capacity + minimum - 1)) { 
    121118        extend(); 
    122119      } 
    123120    } 
    124121 
    125     /// The number of items stored in the heap. 
    126     /// 
    127     /// \brief Returns the number of items stored in the heap. 
     122    /// \brief The number of items stored in the heap. 
     123    /// 
     124    /// This function returns the number of items stored in the heap. 
    128125    int size() const { return data.size(); } 
    129     /// \brief Checks if the heap stores no items. 
    130     /// 
    131     /// Returns \c true if and only if the heap stores no items. 
     126 
     127    /// \brief Check if the heap is empty. 
     128    /// 
     129    /// This function returns \c true if the heap is empty. 
    132130    bool empty() const { return data.empty(); } 
    133131 
    134     /// \brief Make empty this heap. 
    135     /// 
    136     /// Make empty this heap. It does not change the cross reference 
    137     /// map.  If you want to reuse a heap what is not surely empty you 
    138     /// should first clear the heap and after that you should set the 
    139     /// cross reference map for each item to \c PRE_HEAP. 
    140     void clear(int minimal = 0, int capacity = 0) { 
     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    /// \param minimum The minimum value of the heap. 
     140    /// \param capacity The capacity of the heap. 
     141    void clear(int minimum = 0, int capacity = 0) { 
    141142      data.clear(); boxes.clear(); 
    142       boxes.push_back(RadixBox(minimal, 1)); 
    143       boxes.push_back(RadixBox(minimal + 1, 1)); 
    144       while (lower(boxes.size() - 1, capacity + minimal - 1)) { 
     143      boxes.push_back(RadixBox(minimum, 1)); 
     144      boxes.push_back(RadixBox(minimum + 1, 1)); 
     145      while (lower(boxes.size() - 1, capacity + minimum - 1)) { 
    145146        extend(); 
    146147      } 
     
    157158    } 
    158159 
    159     /// \brief Remove item from the box list. 
     160    // Remove item from the box list 
    160161    void remove(int index) { 
    161162      if (data[index].prev >= 0) { 
     
    169170    } 
    170171 
    171     /// \brief Insert item into the box list. 
     172    // Insert item into the box list 
    172173    void insert(int box, int index) { 
    173174      if (boxes[box].first == -1) { 
     
    183184    } 
    184185 
    185     /// \brief Add a new box to the box list. 
     186    // Add a new box to the box list 
    186187    void extend() { 
    187188      int min = boxes.back().min + boxes.back().size; 
     
    190191    } 
    191192 
    192     /// \brief Move an item up into the proper box. 
     193    // Move an item up into the proper box. 
    193194    void bubble_up(int index) { 
    194195      if (!lower(data[index].box, data[index].prio)) return; 
     
    198199    } 
    199200 
    200     /// \brief Find up the proper box for the item with the given prio. 
     201    // Find up the proper box for the item with the given priority 
    201202    int findUp(int start, int pr) { 
    202203      while (lower(start, pr)) { 
     
    208209    } 
    209210 
    210     /// \brief Move an item down into the proper box. 
     211    // Move an item down into the proper box 
    211212    void bubble_down(int index) { 
    212213      if (!upper(data[index].box, data[index].prio)) return; 
     
    216217    } 
    217218 
    218     /// \brief Find up the proper box for the item with the given prio. 
     219    // Find down the proper box for the item with the given priority 
    219220    int findDown(int start, int pr) { 
    220221      while (upper(start, pr)) { 
     
    224225    } 
    225226 
    226     /// \brief Find the first not empty box. 
     227    // Find the first non-empty box 
    227228    int findFirst() { 
    228229      int first = 0; 
     
    231232    } 
    232233 
    233     /// \brief Gives back the minimal prio of the box. 
     234    // Gives back the minimum priority of the given box 
    234235    int minValue(int box) { 
    235236      int min = data[boxes[box].first].prio; 
     
    240241    } 
    241242 
    242     /// \brief Rearrange the items of the heap and makes the 
    243     /// first box not empty. 
     243    // Rearrange the items of the heap and make the first box non-empty 
    244244    void moveDown() { 
    245245      int box = findFirst(); 
     
    278278    /// \brief Insert an item into the heap with the given priority. 
    279279    /// 
    280     /// Adds \c i to the heap with priority \c p. 
     280    /// This function inserts the given item into the heap with the 
     281    /// given priority. 
    281282    /// \param i The item to insert. 
    282283    /// \param p The priority of the item. 
     284    /// \pre \e i must not be stored in the heap. 
     285    /// \warning This method may throw an \c UnderFlowPriorityException. 
    283286    void push(const Item &i, const Prio &p) { 
    284287      int n = data.size(); 
     
    292295    } 
    293296 
    294     /// \brief Returns the item with minimum priority. 
    295     /// 
    296     /// This method returns the item with minimum priority. 
    297     /// \pre The heap must be nonempty. 
     297    /// \brief Return the item having minimum priority. 
     298    /// 
     299    /// This function returns the item having minimum priority. 
     300    /// \pre The heap must be non-empty. 
    298301    Item top() const { 
    299302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 
     
    301304    } 
    302305 
    303     /// \brief Returns the minimum priority. 
    304     /// 
    305     /// It returns the minimum priority. 
    306     /// \pre The heap must be nonempty. 
     306    /// \brief The minimum priority. 
     307    /// 
     308    /// This function returns the minimum priority. 
     309    /// \pre The heap must be non-empty. 
    307310    Prio prio() const { 
    308311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 
     
    310313     } 
    311314 
    312     /// \brief Deletes the item with minimum priority. 
    313     /// 
    314     /// This method deletes the item with minimum priority. 
     315    /// \brief Remove the item having minimum priority. 
     316    /// 
     317    /// This function removes the item having minimum priority. 
    315318    /// \pre The heap must be non-empty. 
    316319    void pop() { 
     
    322325    } 
    323326 
    324     /// \brief Deletes \c i from the heap. 
    325     /// 
    326     /// This method deletes item \c i from the heap, if \c i was 
    327     /// already stored in the heap. 
    328     /// \param i The item to erase. 
     327    /// \brief Remove the given item from the heap. 
     328    /// 
     329    /// This function removes the given item from the heap if it is 
     330    /// already stored. 
     331    /// \param i The item to delete. 
     332    /// \pre \e i must be in the heap. 
    329333    void erase(const Item &i) { 
    330334      int index = _iim[i]; 
     
    334338   } 
    335339 
    336     /// \brief Returns the priority of \c i. 
    337     /// 
    338     /// This function returns the priority of item \c i. 
    339     /// \pre \c i must be in the heap. 
    340     /// \param i The item. 
     340    /// \brief The priority of the given item. 
     341    /// 
     342    /// This function returns the priority of the given item. 
     343    /// \param i The item. 
     344    /// \pre \e i must be in the heap. 
    341345    Prio operator[](const Item &i) const { 
    342346      int idx = _iim[i]; 
     
    344348    } 
    345349 
    346     /// \brief \c i gets to the heap with priority \c p independently 
    347     /// if \c i was already there. 
    348     /// 
    349     /// This method calls \ref push(\c i, \c p) if \c i is not stored 
    350     /// in the heap and sets the priority of \c i to \c p otherwise. 
    351     /// It may throw an \e UnderFlowPriorityException. 
     350    /// \brief Set the priority of an item or insert it, if it is 
     351    /// not stored in the heap. 
     352    /// 
     353    /// This method sets the priority of the given item if it is 
     354    /// already stored in the heap. Otherwise it inserts the given 
     355    /// item into the heap with the given priority. 
    352356    /// \param i The item. 
    353357    /// \param p The priority. 
     358    /// \pre \e i must be in the heap. 
     359    /// \warning This method may throw an \c UnderFlowPriorityException. 
    354360    void set(const Item &i, const Prio &p) { 
    355361      int idx = _iim[i]; 
     
    366372    } 
    367373 
    368  
    369     /// \brief Decreases the priority of \c i to \c p. 
    370     /// 
    371     /// This method decreases the priority of item \c i to \c p. 
    372     /// \pre \c i must be stored in the heap with priority at least \c p, and 
    373     /// \c should be greater or equal to the last removed item's priority. 
     374    /// \brief Decrease the priority of an item to the given value. 
     375    /// 
     376    /// This function decreases the priority of an item to the given value. 
    374377    /// \param i The item. 
    375378    /// \param p The priority. 
     379    /// \pre \e i must be stored in the heap with priority at least \e p. 
     380    /// \warning This method may throw an \c UnderFlowPriorityException. 
    376381    void decrease(const Item &i, const Prio &p) { 
    377382      int idx = _iim[i]; 
     
    380385    } 
    381386 
    382     /// \brief Increases the priority of \c i to \c p. 
    383     /// 
    384     /// This method sets the priority of item \c i to \c p. 
    385     /// \pre \c i must be stored in the heap with priority at most \c p 
     387    /// \brief Increase the priority of an item to the given value. 
     388    /// 
     389    /// This function increases the priority of an item to the given value. 
    386390    /// \param i The item. 
    387391    /// \param p The priority. 
     392    /// \pre \e i must be stored in the heap with priority at most \e p. 
    388393    void increase(const Item &i, const Prio &p) { 
    389394      int idx = _iim[i]; 
     
    392397    } 
    393398 
    394     /// \brief Returns if \c item is in, has already been in, or has 
    395     /// never been in the heap. 
    396     /// 
    397     /// This method returns PRE_HEAP if \c item has never been in the 
    398     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    399     /// otherwise. In the latter case it is possible that \c item will 
    400     /// get back to the heap again. 
     399    /// \brief Return the state of an item. 
     400    /// 
     401    /// This method returns \c PRE_HEAP if the given item has never 
     402    /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 
     403    /// and \c POST_HEAP otherwise. 
     404    /// In the latter case it is possible that the item will get back 
     405    /// to the heap again. 
    401406    /// \param i The item. 
    402407    State state(const Item &i) const { 
     
    406411    } 
    407412 
    408     /// \brief Sets the state of the \c item in the heap. 
    409     /// 
    410     /// Sets the state of the \c item in the heap. It can be used to 
    411     /// manually clear the heap when it is important to achive the 
    412     /// better time complexity. 
     413    /// \brief Set the state of an item in the heap. 
     414    /// 
     415    /// This function sets the state of the given item in the heap. 
     416    /// It can be used to manually clear the heap when it is important 
     417    /// to achive better time complexity. 
    413418    /// \param i The item. 
    414419    /// \param st The state. It should not be \c IN_HEAP. 
Note: See TracChangeset for help on using the changeset viewer.