COIN-OR::LEMON - Graph Library

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


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