Changeset 1270:806451fd084b in lemon-0.x for src/lemon/bin_heap.h

Timestamp:

03/29/05 09:35:09 (19 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1698

Message:

bugfixes in doc

File:

• src/lemon/bin_heap.h (modified) (8 diffs)

src/lemon/bin_heap.h

@@ -21 +21 @@
 ///\file
 ///\brief Binary Heap implementation.
-///\todo It should be documented.
 
 #include <vector>
@@ -32 +31 @@
   /// @{
 
-   /// A Binary Heap implementation.
+  /// A Binary Heap implementation.
   
-  ///\todo Please document...
+  ///This class implements the \e binary \e heap data structure. A \e heap
+  ///is a data structure for storing items with specified values called \e
+  ///priorities in such a way that finding the item with minimum priority is
+  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
+  ///one can change the priority of an item, add or erase an item, etc.
+  ///
+  ///\param Item Type of the items to be stored.  
+  ///\param Prio Type of the priority of the items.
+  ///\param ItemIntMap A read and writable Item int map, used internally
+  ///to handle the cross references.
+  ///\param Compare A class for the ordering of the priorities. The
+  ///default is \c std::less<Prio>.
   ///
   ///\sa FibHeap
@@ -73 +83 @@
 
   public:
-    ///\e
+    ///The constructor
+
+    /**
+       \c _iim should be given to the constructor, since it is used
+       internally to handle the cross references.
+    */
     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
-    ///\e
+    
+    ///The constructor
+
+    /**
+       \c _iim 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.
+    */
     BinHeap(ItemIntMap &_iim, const Compare &_comp) 
       : iim(_iim), comp(_comp) {}
 
 
-    ///\e
+    ///The number of items stored in the heap.
+
+    /**
+       Returns the number of items stored in the heap.
+    */
     int size() const { return data.size(); }
-    ///\e
+    
+    ///Checks if the heap stores no items.
+    
+    /**
+       Returns \c true if and only if the heap stores no items.
+    */
     bool empty() const { return data.empty(); }
 
@@ -112 +143 @@
 
   public:
-    ///\e
+    ///Adds \c p.first to the heap with priority \c p.second.
+    
+    /**
+       Adds \c p.first to the heap with priority \c p.second.
+       \c p.first must not be stored in the heap. 
+    */
     void push(const PairType &p) {
       int n = data.size();
@@ -118 +154 @@
       bubble_up(n, p);
     }
-    ///\e
+
+    ///Adds \c i to the heap with priority \c p. 
+    
+    /**
+       Adds \c i to the heap with priority \c p. 
+       \pre \c i must not be stored in the heap. 
+    */
     void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
 
-    ///\e
+    ///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 data[0].first;
     }
-    /// Returns the prio of the top element of the heap.
+
+    ///Returns the minimum priority relative to \c Compare.
+
+    /**
+       It returns the minimum priority relative to \c Compare.
+       \pre The heap must be nonempty.
+    */
     Prio prio() const {
       return data[0].second;
     }
 
-    ///\e
+    ///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() {
       rmidx(0);
     }
 
-    ///\e
+    ///Deletes \c i from the heap.
+
+    /**
+       This method deletes item \c i from the heap, if \c i was
+       already stored in the heap. 
+    */
     void erase(const Item &i) {
       rmidx(iim[i]);
     }
 
-    ///\e
+    
+    ///Returns the priority of \c i.
+
+    /**
+       This function returns the priority of item \c i.  
+       \pre \c i must be in the heap.
+    */
     Prio operator[](const Item &i) const {
       int idx = iim[i];
@@ -146 +217 @@
     }
 
-    ///\e
+    ///\c i gets to the heap with priority \c p independently if \c i was already there.
+
+    /**
+       This method calls \ref push(\c i, \c p) if \c i is not stored
+       in the heap and sets the priority of \c i to \c p otherwise.
+    */
     void set(const Item &i, const Prio &p) {
       int idx = iim[i];
@@ -160 +236 @@
     }
 
-    ///\e
+    ///Decreases the priority of \c i to \c p.
+
+    /**
+       This method decreases the priority of item \c i to \c p.
+       \pre \c i must be stored in the heap with priority at least \c
+       p relative to \c Compare.
+    */
     void decrease(const Item &i, const Prio &p) {
       int idx = iim[i];
       bubble_up(idx, PairType(i,p));
     }
-    ///\e
+    
+    ///Increases the priority of \c i to \c p.
+
+    /**
+       This method sets the priority of item \c i to \c p. 
+       \pre \c i must be stored in the heap with priority at most \c
+       p relative to \c Compare.
+    */
     void increase(const Item &i, const Prio &p) {
       int idx = iim[i];
@@ -171 +260 @@
     }
 
-    ///\e
+    ///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 &i) const {
       int s = iim[i];