COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1717:75fe24093ded in lemon-0.x


Ignore:
Timestamp:
10/14/05 12:40:00 (17 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

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • lemon/bin_heap.h

    r1435 r1717  
    110110    bool empty() const { return data.empty(); }
    111111
     112    /// \brief Make empty this heap.
     113    ///
     114    /// Make empty this heap.
     115    void clear() {
     116      for (int i = 0; i < (int)data.size(); ++i) {
     117        iim.set(data[i].first, POST_HEAP);
     118      }
     119      data.clear();
     120    }
     121
    112122  private:
    113123    static int parent(int i) { return (i-1)/2; }

  • lemon/concept/heap.h

    r1494 r1717  
    6262      explicit Heap(ItemIntMap &_iim) {}
    6363
    64       /// The number of items stored in the heap.
    65       ///
    66       /// \brief Returns the number of items stored in the heap.
     64      /// \brief The number of items stored in the heap.
     65      ///
     66      /// Returns the number of items stored in the heap.
    6767      int size() const { return 0; }
     68
    6869      /// \brief Checks if the heap stores no items.
    6970      ///
    7071      /// Returns \c true if and only if the heap stores no items.
    7172      bool empty() const { return false; }
     73
     74      /// \brief Makes empty this heap.
     75      ///
     76      /// Makes this heap empty.
     77      void clear();
    7278
    7379      /// \brief Insert an item into the heap with the given heap.
    … …  
    190196          state = _Heap::IN_HEAP;
    191197          state = _Heap::POST_HEAP;
     198
     199          heap.clear();
    192200        }
    193201   

  • 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];

  • lemon/radix_heap.h

    r1435 r1717  
    2727namespace lemon {
    2828
    29   /// \addtogroup auxdat
    30   /// @{
    31 
    3229  /// \brief Exception thrown by RadixHeap.
    3330  /// 
    … …  
    4441  };
    4542
     43  /// \ingroup auxdata
     44  ///
    4645  /// \brief A Radix Heap implementation.
    4746  ///
    … …  
    109108    ///
    110109    /// The constructor.
    111     /// \param _iim should be given to the constructor, since it is used
    112     /// internally to handle the cross references. The value of the map
    113     /// should be PRE_HEAP (-1) for each element.
    114     explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
    115       boxes.push_back(RadixBox(0, 1));
    116       boxes.push_back(RadixBox(1, 1));
    117     }
    118 
    119     /// \brief The constructor.
    120     ///
    121     /// The constructor.
    122110    ///
    123111    /// \param _iim It should be given to the constructor, since it is used
    … …  
    125113    /// should be PRE_HEAP (-1) for each element.
    126114    ///
     115    /// \param minimal The initial minimal value of the heap.
    127116    /// \param capacity It determines the initial capacity of the heap.
    128     RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
    129       boxes.push_back(RadixBox(0, 1));
    130       boxes.push_back(RadixBox(1, 1));
    131       while (upper(boxes.back(), capacity)) {
     117    RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
     118      : iim(_iim) {
     119      boxes.push_back(RadixBox(minimal, 1));
     120      boxes.push_back(RadixBox(minimal + 1, 1));
     121      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
    132122        extend();
    133123      }
    … …  
    142132    /// Returns \c true if and only if the heap stores no items.
    143133    bool empty() const { return data.empty(); }
     134
     135    /// \brief Make empty this heap.
     136    ///
     137    /// Make empty this heap.
     138    void clear(int minimal = 0, int capacity = 0) {
     139      for (int i = 0; i < (int)data.size(); ++i) {
     140        iim[data[i].item] = -2;
     141      }
     142      data.clear(); boxes.clear();
     143      boxes.push_back(RadixBox(minimal, 1));
     144      boxes.push_back(RadixBox(minimal + 1, 1));
     145      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
     146        extend();
     147      }
     148    }
    144149
    145150  private:
    … …  
    272277  public:
    273278
    274     /// \brief Insert an item into the heap with the given heap.
     279    /// \brief Insert an item into the heap with the given priority.
    275280    ///   
    276281    /// Adds \c i to the heap with priority \c p.
    … …  
    293298    /// \pre The heap must be nonempty. 
    294299    Item top() const {
    295       const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
     300      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
    296301      return data[boxes[0].first].item;
    297302    }
    … …  
    302307    /// \pre The heap must be nonempty.
    303308    Prio prio() const {
    304       const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
     309      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
    305310      return data[boxes[0].first].prio;
    306311     }
Note: See TracChangeset for help on using the changeset viewer.