1.1 --- a/lemon/radix_heap.h	Fri Oct 07 11:05:35 2005 +0000
     1.2 +++ b/lemon/radix_heap.h	Fri Oct 14 10:40:00 2005 +0000
     1.3 @@ -26,9 +26,6 @@
     1.4  
     1.5  namespace lemon {
     1.6  
     1.7 -  /// \addtogroup auxdat
     1.8 -  /// @{
     1.9 -
    1.10    /// \brief Exception thrown by RadixHeap.
    1.11    ///  
    1.12    /// This Exception is thrown when a smaller priority
    1.13 @@ -43,6 +40,8 @@
    1.14      }  
    1.15    };
    1.16  
    1.17 +  /// \ingroup auxdata
    1.18 +  ///
    1.19    /// \brief A Radix Heap implementation.
    1.20    ///
    1.21    /// This class implements the \e radix \e heap data structure. A \e heap
    1.22 @@ -108,27 +107,18 @@
    1.23      /// \brief The constructor.
    1.24      ///
    1.25      /// The constructor.
    1.26 -    /// \param _iim should be given to the constructor, since it is used
    1.27 -    /// internally to handle the cross references. The value of the map
    1.28 -    /// should be PRE_HEAP (-1) for each element.
    1.29 -    explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
    1.30 -      boxes.push_back(RadixBox(0, 1));
    1.31 -      boxes.push_back(RadixBox(1, 1));
    1.32 -    }
    1.33 -
    1.34 -    /// \brief The constructor.
    1.35 -    ///
    1.36 -    /// The constructor.
    1.37      ///
    1.38      /// \param _iim It should be given to the constructor, since it is used
    1.39      /// internally to handle the cross references. The value of the map
    1.40      /// should be PRE_HEAP (-1) for each element.
    1.41      ///
    1.42 +    /// \param minimal The initial minimal value of the heap.
    1.43      /// \param capacity It determines the initial capacity of the heap. 
    1.44 -    RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
    1.45 -      boxes.push_back(RadixBox(0, 1));
    1.46 -      boxes.push_back(RadixBox(1, 1));
    1.47 -      while (upper(boxes.back(), capacity)) {
    1.48 +    RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0) 
    1.49 +      : iim(_iim) {
    1.50 +      boxes.push_back(RadixBox(minimal, 1));
    1.51 +      boxes.push_back(RadixBox(minimal + 1, 1));
    1.52 +      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
    1.53  	extend();
    1.54        }
    1.55      }
    1.56 @@ -142,6 +132,21 @@
    1.57      /// Returns \c true if and only if the heap stores no items.
    1.58      bool empty() const { return data.empty(); }
    1.59  
    1.60 +    /// \brief Make empty this heap.
    1.61 +    /// 
    1.62 +    /// Make empty this heap.
    1.63 +    void clear(int minimal = 0, int capacity = 0) { 
    1.64 +      for (int i = 0; i < (int)data.size(); ++i) {
    1.65 +	iim[data[i].item] = -2;
    1.66 +      }
    1.67 +      data.clear(); boxes.clear(); 
    1.68 +      boxes.push_back(RadixBox(minimal, 1));
    1.69 +      boxes.push_back(RadixBox(minimal + 1, 1));
    1.70 +      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
    1.71 +	extend();
    1.72 +      }
    1.73 +    }
    1.74 +
    1.75    private:
    1.76  
    1.77      bool upper(int box, Prio prio) {
    1.78 @@ -271,7 +276,7 @@
    1.79  
    1.80    public:
    1.81  
    1.82 -    /// \brief Insert an item into the heap with the given heap.
    1.83 +    /// \brief Insert an item into the heap with the given priority.
    1.84      ///    
    1.85      /// Adds \c i to the heap with priority \c p. 
    1.86      /// \param i The item to insert.
    1.87 @@ -292,7 +297,7 @@
    1.88      /// This method returns the item with minimum priority.  
    1.89      /// \pre The heap must be nonempty.  
    1.90      Item top() const {
    1.91 -      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
    1.92 +      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
    1.93        return data[boxes[0].first].item;
    1.94      }
    1.95  
    1.96 @@ -301,7 +306,7 @@
    1.97      /// It returns the minimum priority.
    1.98      /// \pre The heap must be nonempty.
    1.99      Prio prio() const {
   1.100 -      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
   1.101 +      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
   1.102        return data[boxes[0].first].prio;
   1.103       }
   1.104