COIN-OR::LEMON - Graph Library

Changeset 1270:806451fd084b in lemon-0.x for src/lemon/bin_heap.h


Ignore:
Timestamp:
03/29/05 09:35:09 (15 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1698
Message:

bugfixes in doc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bin_heap.h

    r1191 r1270  
    2121///\file
    2222///\brief Binary Heap implementation.
    23 ///\todo It should be documented.
    2423
    2524#include <vector>
     
    3231  /// @{
    3332
    34    /// A Binary Heap implementation.
     33  /// A Binary Heap implementation.
    3534 
    36   ///\todo Please document...
     35  ///This class implements the \e binary \e heap data structure. A \e heap
     36  ///is a data structure for storing items with specified values called \e
     37  ///priorities in such a way that finding the item with minimum priority is
     38  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
     39  ///one can change the priority of an item, add or erase an item, etc.
     40  ///
     41  ///\param Item Type of the items to be stored. 
     42  ///\param Prio Type of the priority of the items.
     43  ///\param ItemIntMap A read and writable Item int map, used internally
     44  ///to handle the cross references.
     45  ///\param Compare A class for the ordering of the priorities. The
     46  ///default is \c std::less<Prio>.
    3747  ///
    3848  ///\sa FibHeap
     
    7383
    7484  public:
    75     ///\e
     85    ///The constructor
     86
     87    /**
     88       \c _iim should be given to the constructor, since it is used
     89       internally to handle the cross references.
     90    */
    7691    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    77     ///\e
     92   
     93    ///The constructor
     94
     95    /**
     96       \c _iim should be given to the constructor, since it is used
     97       internally to handle the cross references. \c _comp is an
     98       object for ordering of the priorities.
     99    */
    78100    BinHeap(ItemIntMap &_iim, const Compare &_comp)
    79101      : iim(_iim), comp(_comp) {}
    80102
    81103
    82     ///\e
     104    ///The number of items stored in the heap.
     105
     106    /**
     107       Returns the number of items stored in the heap.
     108    */
    83109    int size() const { return data.size(); }
    84     ///\e
     110   
     111    ///Checks if the heap stores no items.
     112   
     113    /**
     114       Returns \c true if and only if the heap stores no items.
     115    */
    85116    bool empty() const { return data.empty(); }
    86117
     
    112143
    113144  public:
    114     ///\e
     145    ///Adds \c p.first to the heap with priority \c p.second.
     146   
     147    /**
     148       Adds \c p.first to the heap with priority \c p.second.
     149       \c p.first must not be stored in the heap.
     150    */
    115151    void push(const PairType &p) {
    116152      int n = data.size();
     
    118154      bubble_up(n, p);
    119155    }
    120     ///\e
     156
     157    ///Adds \c i to the heap with priority \c p.
     158   
     159    /**
     160       Adds \c i to the heap with priority \c p.
     161       \pre \c i must not be stored in the heap.
     162    */
    121163    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
    122164
    123     ///\e
     165    ///Returns the item with minimum priority relative to \c Compare.
     166   
     167    /**
     168       This method returns the item with minimum priority relative to \c
     169       Compare. 
     170       \pre The heap must be nonempty. 
     171    */
    124172    Item top() const {
    125173      return data[0].first;
    126174    }
    127     /// Returns the prio of the top element of the heap.
     175
     176    ///Returns the minimum priority relative to \c Compare.
     177
     178    /**
     179       It returns the minimum priority relative to \c Compare.
     180       \pre The heap must be nonempty.
     181    */
    128182    Prio prio() const {
    129183      return data[0].second;
    130184    }
    131185
    132     ///\e
     186    ///Deletes the item with minimum priority relative to \c Compare.
     187
     188    /**
     189    This method deletes the item with minimum priority relative to \c
     190    Compare from the heap. 
     191    \pre The heap must be non-empty. 
     192    */
    133193    void pop() {
    134194      rmidx(0);
    135195    }
    136196
    137     ///\e
     197    ///Deletes \c i from the heap.
     198
     199    /**
     200       This method deletes item \c i from the heap, if \c i was
     201       already stored in the heap.
     202    */
    138203    void erase(const Item &i) {
    139204      rmidx(iim[i]);
    140205    }
    141206
    142     ///\e
     207   
     208    ///Returns the priority of \c i.
     209
     210    /**
     211       This function returns the priority of item \c i. 
     212       \pre \c i must be in the heap.
     213    */
    143214    Prio operator[](const Item &i) const {
    144215      int idx = iim[i];
     
    146217    }
    147218
    148     ///\e
     219    ///\c i gets to the heap with priority \c p independently if \c i was already there.
     220
     221    /**
     222       This method calls \ref push(\c i, \c p) if \c i is not stored
     223       in the heap and sets the priority of \c i to \c p otherwise.
     224    */
    149225    void set(const Item &i, const Prio &p) {
    150226      int idx = iim[i];
     
    160236    }
    161237
    162     ///\e
     238    ///Decreases the priority of \c i to \c p.
     239
     240    /**
     241       This method decreases the priority of item \c i to \c p.
     242       \pre \c i must be stored in the heap with priority at least \c
     243       p relative to \c Compare.
     244    */
    163245    void decrease(const Item &i, const Prio &p) {
    164246      int idx = iim[i];
    165247      bubble_up(idx, PairType(i,p));
    166248    }
    167     ///\e
     249   
     250    ///Increases the priority of \c i to \c p.
     251
     252    /**
     253       This method sets the priority of item \c i to \c p.
     254       \pre \c i must be stored in the heap with priority at most \c
     255       p relative to \c Compare.
     256    */
    168257    void increase(const Item &i, const Prio &p) {
    169258      int idx = iim[i];
     
    171260    }
    172261
    173     ///\e
     262    ///Returns if \c item is in, has already been in, or has never been in the heap.
     263
     264    /**
     265       This method returns PRE_HEAP if \c item has never been in the
     266       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     267       otherwise. In the latter case it is possible that \c item will
     268       get back to the heap again.
     269    */
    174270    state_enum state(const Item &i) const {
    175271      int s = iim[i];
Note: See TracChangeset for help on using the changeset viewer.