COIN-OR::LEMON - Graph Library

Changeset 1717:75fe24093ded in lemon-0.x for lemon/fib_heap.h


Ignore:
Timestamp:
10/14/05 12:40:00 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2244
Message:

Added clear function to heaps and concept

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/fib_heap.h

    r1435 r1717  
    8989    };
    9090   
    91     ///The constructor
    92 
    93     /**
    94        \c _iimap should be given to the constructor, since it is
    95        used internally to handle the cross references.
    96     */
     91    /// \brief The constructor
     92    ///
     93    /// \c _iimap should be given to the constructor, since it is
     94    ///   used internally to handle the cross references.
    9795    explicit FibHeap(ItemIntMap &_iimap)
    9896      : minimum(0), iimap(_iimap), num_items() {}
    9997 
    100     ///The constructor
    101 
    102     /**
    103        \c _iimap should be given to the constructor, since it is used
    104        internally to handle the cross references. \c _comp is an
    105        object for ordering of the priorities.
    106     */
     98    /// \brief The constructor
     99    ///
     100    /// \c _iimap should be given to the constructor, since it is used
     101    /// internally to handle the cross references. \c _comp is an
     102    /// object for ordering of the priorities.
    107103    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
    108104                  iimap(_iimap), comp(_comp), num_items() {}
    109105   
    110     ///The number of items stored in the heap.
    111 
    112     /**
    113        Returns the number of items stored in the heap.
    114     */
     106    /// \brief The number of items stored in the heap.
     107    ///
     108    /// Returns the number of items stored in the heap.
    115109    int size() const { return num_items; }
    116110
    117     ///Checks if the heap stores no items.
    118    
    119     /**
    120        Returns \c true if and only if the heap stores no items.
    121     */
     111    /// \brief Checks if the heap stores no items.
     112    ///
     113    ///   Returns \c true if and only if the heap stores no items.
    122114    bool empty() const { return num_items==0; }
    123115
    124     ///\c item gets to the heap with priority \c value independently if \c item was already there.
    125 
    126     /**
    127        This method calls \ref push(\c item, \c value) if \c item is not
    128        stored in the heap and it calls \ref decrease(\c item, \c value) or
    129        \ref increase(\c item, \c value) otherwise.
    130     */
     116    /// \brief Make empty this heap.
     117    ///
     118    /// Make empty this heap.
     119    void clear() {
     120      for (int i = 0; i < (int)container.size(); ++i) {
     121        iimap[container[i].name] = -2;
     122      }
     123      container.clear(); minimum = 0; num_items = 0;
     124    }
     125
     126    /// \brief \c item gets to the heap with priority \c value independently
     127    /// if \c item was already there.
     128    ///
     129    /// This method calls \ref push(\c item, \c value) if \c item is not
     130    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
     131    /// \ref increase(\c item, \c value) otherwise.
    131132    void set (Item const item, PrioType const value);
    132133   
    133     ///Adds \c item to the heap with priority \c value.
    134    
    135     /**
    136        Adds \c item to the heap with priority \c value.
    137        \pre \c item must not be stored in the heap.
    138     */
     134    /// \brief Adds \c item to the heap with priority \c value.
     135    ///   
     136    /// Adds \c item to the heap with priority \c value.
     137    /// \pre \c item must not be stored in the heap.
    139138    void push (Item const item, PrioType const value);
    140139   
    141     ///Returns the item with minimum priority relative to \c Compare.
    142    
    143     /**
    144        This method returns the item with minimum priority relative to \c
    145        Compare. 
    146        \pre The heap must be nonempty. 
    147     */
     140    /// \brief Returns the item with minimum priority relative to \c Compare.
     141    ///
     142    /// This method returns the item with minimum priority relative to \c
     143    /// Compare. 
     144    /// \pre The heap must be nonempty. 
    148145    Item top() const { return container[minimum].name; }
    149146
    150     ///Returns the minimum priority relative to \c Compare.
    151 
    152     /**
    153        It returns the minimum priority relative to \c Compare.
    154        \pre The heap must be nonempty.
    155     */
     147    /// \brief Returns the minimum priority relative to \c Compare.
     148    ///
     149    /// It returns the minimum priority relative to \c Compare.
     150    /// \pre The heap must be nonempty.
    156151    PrioType prio() const { return container[minimum].prio; }
    157152   
    158     ///Returns the priority of \c item.
    159 
    160     /**
    161        This function returns the priority of \c item.
    162        \pre \c item must be in the heap.
    163     */
     153    /// \brief Returns the priority of \c item.
     154    ///
     155    /// This function returns the priority of \c item.
     156    /// \pre \c item must be in the heap.
    164157    PrioType& operator[](const Item& item) {
    165158      return container[iimap[item]].prio;
    166159    }
    167160   
    168     ///Returns the priority of \c item.
    169    
    170     /**
    171        It returns the priority of \c item.
    172        \pre \c item must be in the heap.
    173     */
     161    /// \brief Returns the priority of \c item.
     162    ///
     163    /// It returns the priority of \c item.
     164    /// \pre \c item must be in the heap.
    174165    const PrioType& operator[](const Item& item) const {
    175166      return container[iimap[item]].prio;
     
    177168
    178169
    179     ///Deletes the item with minimum priority relative to \c Compare.
    180 
    181     /**
    182     This method deletes the item with minimum priority relative to \c
    183     Compare from the heap. 
    184     \pre The heap must be non-empty. 
    185     */
     170    /// \brief Deletes the item with minimum priority relative to \c Compare.
     171    ///
     172    /// This method deletes the item with minimum priority relative to \c
     173    /// Compare from the heap. 
     174    /// \pre The heap must be non-empty. 
    186175    void pop();
    187176
    188     ///Deletes \c item from the heap.
    189 
    190     /**
    191        This method deletes \c item from the heap, if \c item was already
    192        stored in the heap. It is quite inefficient in Fibonacci heaps.
    193     */
     177    /// \brief Deletes \c item from the heap.
     178    ///
     179    /// This method deletes \c item from the heap, if \c item was already
     180    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
    194181    void erase (const Item& item);
    195182
    196     ///Decreases the priority of \c item to \c value.
    197 
    198     /**
    199        This method decreases the priority of \c item to \c value.
    200        \pre \c item must be stored in the heap with priority at least \c
    201        value relative to \c Compare.
    202     */
     183    /// \brief Decreases the priority of \c item to \c value.
     184    ///
     185    /// This method decreases the priority of \c item to \c value.
     186    /// \pre \c item must be stored in the heap with priority at least \c
     187    ///   value relative to \c Compare.
    203188    void decrease (Item item, PrioType const value);
    204189
    205     ///Increases the priority of \c item to \c value.
    206 
    207     /**
    208        This method sets the priority of \c item to \c value. Though
    209        there is no precondition on the priority of \c item, this
    210        method should be used only if it is indeed necessary to increase
    211        (relative to \c Compare) the priority of \c item, because this
    212        method is inefficient.
    213     */
     190    /// \brief Increases the priority of \c item to \c value.
     191    ///
     192    /// This method sets the priority of \c item to \c value. Though
     193    /// there is no precondition on the priority of \c item, this
     194    /// method should be used only if it is indeed necessary to increase
     195    /// (relative to \c Compare) the priority of \c item, because this
     196    /// method is inefficient.
    214197    void increase (Item item, PrioType const value) {
    215198      erase(item);
     
    218201
    219202
    220     ///Returns if \c item is in, has already been in, or has never been in the heap.
    221 
    222     /**
    223        This method returns PRE_HEAP if \c item has never been in the
    224        heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    225        otherwise. In the latter case it is possible that \c item will
    226        get back to the heap again.
    227     */
     203    /// \brief Returns if \c item is in, has already been in, or has never
     204    /// been in the heap.
     205    ///
     206    /// This method returns PRE_HEAP if \c item has never been in the
     207    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     208    /// otherwise. In the latter case it is possible that \c item will
     209    /// get back to the heap again.
    228210    state_enum state(const Item &item) const {
    229211      int i=iimap[item];
Note: See TracChangeset for help on using the changeset viewer.