COIN-OR::LEMON - Graph Library

Changeset 1331:7e93d3f0406d in lemon-0.x for src/lemon/bin_heap.h


Ignore:
Timestamp:
04/09/05 21:30:49 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1770
Message:

Documentation improvments.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bin_heap.h

    r1270 r1331  
    6060    typedef Compare                          PrioCompare;
    6161
    62     /**
    63      * Each Item element have a state associated to it. It may be "in heap",
    64      * "pre heap" or "post heap". The later two are indifferent from the
    65      * heap's point of view, but may be useful to the user.
    66      *
    67      * The ItemIntMap _should_ be initialized in such way, that it maps
    68      * PRE_HEAP (-1) to any element to be put in the heap...
    69      */
    70     ///\todo it is used nowhere
    71     ///
     62    /// \brief Type to represent the items states.
     63    ///
     64    /// Each Item element have a state associated to it. It may be "in heap",
     65    /// "pre heap" or "post heap". The later two are indifferent from the
     66    /// heap's point of view, but may be useful to the user.
     67    ///
     68    /// The ItemIntMap _should_ be initialized in such way, that it maps
     69    /// PRE_HEAP (-1) to any element to be put in the heap...
    7270    enum state_enum {
    7371      IN_HEAP = 0,
     
    7977    std::vector<PairType> data;
    8078    Compare comp;
    81     // FIXME: jo ez igy???
    8279    ItemIntMap &iim;
    8380
    8481  public:
    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     */
     82    /// \brief The constructor.
     83    ///
     84    /// The constructor.
     85    /// \param _iim should be given to the constructor, since it is used
     86    /// internally to handle the cross references. The value of the map
     87    /// should be PRE_HEAP (-1) for each element.
    9188    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    9289   
    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     */
     90    /// \brief The constructor.
     91    ///
     92    /// The constructor.
     93    /// \param _iim should be given to the constructor, since it is used
     94    /// internally to handle the cross references. The value of the map
     95    /// should be PRE_HEAP (-1) for each element.
     96    ///
     97    /// \param _comp The comparator function object.
    10098    BinHeap(ItemIntMap &_iim, const Compare &_comp)
    10199      : iim(_iim), comp(_comp) {}
    102100
    103101
    104     ///The number of items stored in the heap.
    105 
    106     /**
    107        Returns the number of items stored in the heap.
    108     */
     102    /// The number of items stored in the heap.
     103    ///
     104    /// \brief Returns the number of items stored in the heap.
    109105    int size() const { return data.size(); }
    110106   
    111     ///Checks if the heap stores no items.
    112    
    113     /**
    114        Returns \c true if and only if the heap stores no items.
    115     */
     107    /// \brief Checks if the heap stores no items.
     108    ///
     109    /// Returns \c true if and only if the heap stores no items.
    116110    bool empty() const { return data.empty(); }
    117111
     
    143137
    144138  public:
    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     */
     139    /// \brief Insert a pair of item and priority into the heap.
     140    ///
     141    /// Adds \c p.first to the heap with priority \c p.second.
     142    /// \param p The pair to insert.
    151143    void push(const PairType &p) {
    152144      int n = data.size();
     
    155147    }
    156148
    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     */
     149    /// \brief Insert an item into the heap with the given heap.
     150    ///   
     151    /// Adds \c i to the heap with priority \c p.
     152    /// \param i The item to insert.
     153    /// \param p The priority of the item.
    163154    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
    164155
    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     */
     156    /// \brief Returns the item with minimum priority relative to \c Compare.
     157    ///
     158    /// This method returns the item with minimum priority relative to \c
     159    /// Compare. 
     160    /// \pre The heap must be nonempty. 
    172161    Item top() const {
    173162      return data[0].first;
    174163    }
    175164
    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     */
     165    /// \brief Returns the minimum priority relative to \c Compare.
     166    ///
     167    /// It returns the minimum priority relative to \c Compare.
     168    /// \pre The heap must be nonempty.
    182169    Prio prio() const {
    183170      return data[0].second;
    184171    }
    185172
    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     */
     173    /// \brief Deletes the item with minimum priority relative to \c Compare.
     174    ///
     175    /// This method deletes the item with minimum priority relative to \c
     176    /// Compare from the heap. 
     177    /// \pre The heap must be non-empty. 
    193178    void pop() {
    194179      rmidx(0);
    195180    }
    196181
    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     */
     182    /// \brief Deletes \c i from the heap.
     183    ///
     184    /// This method deletes item \c i from the heap, if \c i was
     185    /// already stored in the heap.
     186    /// \param i The item to erase.
    203187    void erase(const Item &i) {
    204188      rmidx(iim[i]);
     
    206190
    207191   
    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     */
     192    /// \brief Returns the priority of \c i.
     193    ///
     194    /// This function returns the priority of item \c i. 
     195    /// \pre \c i must be in the heap.
     196    /// \param i The item.
    214197    Prio operator[](const Item &i) const {
    215198      int idx = iim[i];
     
    217200    }
    218201
    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     */
     202    /// \brief \c i gets to the heap with priority \c p independently
     203    /// if \c i was already there.
     204    ///
     205    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     206    /// in the heap and sets the priority of \c i to \c p otherwise.
     207    /// \param i The item.
     208    /// \param p The priority.
    225209    void set(const Item &i, const Prio &p) {
    226210      int idx = iim[i];
     
    236220    }
    237221
    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     */
     222    /// \brief Decreases the priority of \c i to \c p.
     223
     224    /// This method decreases the priority of item \c i to \c p.
     225    /// \pre \c i must be stored in the heap with priority at least \c
     226    /// p relative to \c Compare.
     227    /// \param i The item.
     228    /// \param p The priority.
    245229    void decrease(const Item &i, const Prio &p) {
    246230      int idx = iim[i];
     
    248232    }
    249233   
    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     */
     234    /// \brief Increases the priority of \c i to \c p.
     235    ///
     236    /// This method sets the priority of item \c i to \c p.
     237    /// \pre \c i must be stored in the heap with priority at most \c
     238    /// p relative to \c Compare.
     239    /// \param i The item.
     240    /// \param p The priority.
    257241    void increase(const Item &i, const Prio &p) {
    258242      int idx = iim[i];
     
    260244    }
    261245
    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     */
     246    /// \brief Returns if \c item is in, has already been in, or has
     247    /// never been in the heap.
     248    ///
     249    /// This method returns PRE_HEAP if \c item has never been in the
     250    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     251    /// otherwise. In the latter case it is possible that \c item will
     252    /// get back to the heap again.
     253    /// \param i The item.
    270254    state_enum state(const Item &i) const {
    271255      int s = iim[i];
Note: See TracChangeset for help on using the changeset viewer.