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

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:

• lemon/fib_heap.h (modified) (3 diffs)

lemon/fib_heap.h

@@ -89 +89 @@
     };
     
-    ///The constructor
-
-    /**
-       \c _iimap should be given to the constructor, since it is
-       used internally to handle the cross references.
-    */
+    /// \brief The constructor
+    ///
+    /// \c _iimap should be given to the constructor, since it is
+    ///   used internally to handle the cross references.
     explicit FibHeap(ItemIntMap &_iimap) 
       : minimum(0), iimap(_iimap), num_items() {} 
  
-    ///The constructor
-
-    /**
-       \c _iimap should be given to the constructor, since it is used
-       internally to handle the cross references. \c _comp is an
-       object for ordering of the priorities. 
-    */
+    /// \brief The constructor
+    ///
+    /// \c _iimap should be given to the constructor, since it is used
+    /// internally to handle the cross references. \c _comp is an
+    /// object for ordering of the priorities. 
     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
                   iimap(_iimap), comp(_comp), num_items() {}
     
-    ///The number of items stored in the heap.
-
-    /**
-       Returns the number of items stored in the heap.
-    */
+    /// \brief The number of items stored in the heap.
+    ///
+    /// Returns the number of items stored in the heap.
     int size() const { return num_items; }
 
-    ///Checks if the heap stores no items.
-    
-    /**
-       Returns \c true if and only if the heap stores no items.
-    */
+    /// \brief Checks if the heap stores no items.
+    ///
+    ///   Returns \c true if and only if the heap stores no items.
     bool empty() const { return num_items==0; }
 
-    ///\c item gets to the heap with priority \c value independently if \c item was already there.
-
-    /**
-       This method calls \ref push(\c item, \c value) if \c item is not
-       stored in the heap and it calls \ref decrease(\c item, \c value) or
-       \ref increase(\c item, \c value) otherwise.
-    */
+    /// \brief Make empty this heap.
+    /// 
+    /// Make empty this heap.
+    void clear() { 
+      for (int i = 0; i < (int)container.size(); ++i) {
+        iimap[container[i].name] = -2;
+      }
+      container.clear(); minimum = 0; num_items = 0;
+    }
+
+    /// \brief \c item gets to the heap with priority \c value independently 
+    /// if \c item was already there.
+    ///
+    /// This method calls \ref push(\c item, \c value) if \c item is not
+    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
+    /// \ref increase(\c item, \c value) otherwise.
     void set (Item const item, PrioType const value); 
     
-    ///Adds \c item to the heap with priority \c value. 
-    
-    /**
-       Adds \c item to the heap with priority \c value. 
-       \pre \c item must not be stored in the heap. 
-    */
+    /// \brief Adds \c item to the heap with priority \c value. 
+    ///    
+    /// Adds \c item to the heap with priority \c value. 
+    /// \pre \c item must not be stored in the heap. 
     void push (Item const item, PrioType const value);
     
-    ///Returns the item with minimum priority relative to \c Compare.
-    
-    /**
-       This method returns the item with minimum priority relative to \c
-       Compare.  
-       \pre The heap must be nonempty.  
-    */
+    /// \brief Returns the item with minimum priority relative to \c Compare.
+    ///
+    /// This method returns the item with minimum priority relative to \c
+    /// Compare.  
+    /// \pre The heap must be nonempty.  
     Item top() const { return container[minimum].name; }
 
-    ///Returns the minimum priority relative to \c Compare.
-
-    /**
-       It returns the minimum priority relative to \c Compare.
-       \pre The heap must be nonempty.
-    */
+    /// \brief Returns the minimum priority relative to \c Compare.
+    ///
+    /// It returns the minimum priority relative to \c Compare.
+    /// \pre The heap must be nonempty.
     PrioType prio() const { return container[minimum].prio; }
     
-    ///Returns the priority of \c item.
-
-    /**
-       This function returns the priority of \c item.
-       \pre \c item must be in the heap.
-    */
+    /// \brief Returns the priority of \c item.
+    ///
+    /// This function returns the priority of \c item.
+    /// \pre \c item must be in the heap.
     PrioType& operator[](const Item& item) { 
       return container[iimap[item]].prio; 
     }
     
-    ///Returns the priority of \c item.
-    
-    /**
-       It returns the priority of \c item.
-       \pre \c item must be in the heap.
-    */
+    /// \brief Returns the priority of \c item.
+    ///
+    /// It returns the priority of \c item.
+    /// \pre \c item must be in the heap.
     const PrioType& operator[](const Item& item) const { 
       return container[iimap[item]].prio; 
@@ -177 +168 @@
 
 
-    ///Deletes the item with minimum priority relative to \c Compare.
-
-    /**
-    This method deletes the item with minimum priority relative to \c
-    Compare from the heap.  
-    \pre The heap must be non-empty.  
-    */
+    /// \brief Deletes the item with minimum priority relative to \c Compare.
+    ///
+    /// This method deletes the item with minimum priority relative to \c
+    /// Compare from the heap.  
+    /// \pre The heap must be non-empty.  
     void pop();
 
-    ///Deletes \c item from the heap.
-
-    /**
-       This method deletes \c item from the heap, if \c item was already
-       stored in the heap. It is quite inefficient in Fibonacci heaps.
-    */
+    /// \brief Deletes \c item from the heap.
+    ///
+    /// This method deletes \c item from the heap, if \c item was already
+    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
     void erase (const Item& item); 
 
-    ///Decreases the priority of \c item to \c value.
-
-    /**
-       This method decreases the priority of \c item to \c value.
-       \pre \c item must be stored in the heap with priority at least \c
-       value relative to \c Compare.
-    */
+    /// \brief Decreases the priority of \c item to \c value.
+    ///
+    /// This method decreases the priority of \c item to \c value.
+    /// \pre \c item must be stored in the heap with priority at least \c
+    ///   value relative to \c Compare.
     void decrease (Item item, PrioType const value); 
 
-    ///Increases the priority of \c item to \c value.
-
-    /**
-       This method sets the priority of \c item to \c value. Though
-       there is no precondition on the priority of \c item, this
-       method should be used only if it is indeed necessary to increase
-       (relative to \c Compare) the priority of \c item, because this
-       method is inefficient.
-    */
+    /// \brief Increases the priority of \c item to \c value.
+    ///
+    /// This method sets the priority of \c item to \c value. Though
+    /// there is no precondition on the priority of \c item, this
+    /// method should be used only if it is indeed necessary to increase
+    /// (relative to \c Compare) the priority of \c item, because this
+    /// method is inefficient.
     void increase (Item item, PrioType const value) {
       erase(item);
@@ -218 +201 @@
 
 
-    ///Returns if \c item is in, has already been in, or has never been in the heap.
-
-    /**
-       This method returns PRE_HEAP if \c item has never been in the
-       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
-       otherwise. In the latter case it is possible that \c item will
-       get back to the heap again.
-    */
+    /// \brief Returns if \c item is in, has already been in, or has never 
+    /// been in the heap.
+    ///
+    /// This method returns PRE_HEAP if \c item has never been in the
+    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+    /// otherwise. In the latter case it is possible that \c item will
+    /// get back to the heap again.
     state_enum state(const Item &item) const {
       int i=iimap[item];