# HG changeset patch
# User deba
# Date 1113075049 0
# Node ID 7e93d3f0406df511895846525919acc12da212b0
# Parent  52ef02524468c0f942cd668bf134ff7a7b9b5798
Documentation improvments.

diff -r 52ef02524468 -r 7e93d3f0406d src/lemon/bin_heap.h
--- a/src/lemon/bin_heap.h	Sat Apr 09 19:27:48 2005 +0000
+++ b/src/lemon/bin_heap.h	Sat Apr 09 19:30:49 2005 +0000
@@ -59,16 +59,14 @@
     typedef ItemIntMap                       ItemIntMapType;
     typedef Compare                          PrioCompare;
 
-    /**
-     * Each Item element have a state associated to it. It may be "in heap",
-     * "pre heap" or "post heap". The later two are indifferent from the
-     * heap's point of view, but may be useful to the user.
-     *
-     * The ItemIntMap _should_ be initialized in such way, that it maps
-     * PRE_HEAP (-1) to any element to be put in the heap...
-     */
-    ///\todo it is used nowhere
+    /// \brief Type to represent the items states.
     ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The later two are indifferent from the
+    /// heap's point of view, but may be useful to the user.
+    ///
+    /// The ItemIntMap _should_ be initialized in such way, that it maps
+    /// PRE_HEAP (-1) to any element to be put in the heap...
     enum state_enum {
       IN_HEAP = 0,
       PRE_HEAP = -1,
@@ -78,41 +76,37 @@
   private:
     std::vector<PairType> data;
     Compare comp;
-    // FIXME: jo ez igy???
     ItemIntMap &iim;
 
   public:
-    ///The constructor
-
-    /**
-       \c _iim should be given to the constructor, since it is used
-       internally to handle the cross references.
-    */
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param _iim should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
     
-    ///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.
-    */
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param _iim should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
+    ///
+    /// \param _comp The comparator function object.
     BinHeap(ItemIntMap &_iim, const Compare &_comp) 
       : iim(_iim), comp(_comp) {}
 
 
-    ///The number of items stored in the heap.
-
-    /**
-       Returns the number of items stored in the heap.
-    */
+    /// The number of items stored in the heap.
+    ///
+    /// \brief Returns the number of items stored in the heap.
     int size() const { return data.size(); }
     
-    ///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 data.empty(); }
 
   private:
@@ -142,86 +136,76 @@
     }
 
   public:
-    ///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. 
-    */
+    /// \brief Insert a pair of item and priority into the heap.
+    ///
+    /// Adds \c p.first to the heap with priority \c p.second.
+    /// \param p The pair to insert.
     void push(const PairType &p) {
       int n = data.size();
       data.resize(n+1);
       bubble_up(n, p);
     }
 
-    ///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. 
-    */
+    /// \brief Insert an item into the heap with the given heap.
+    ///    
+    /// Adds \c i to the heap with priority \c p. 
+    /// \param i The item to insert.
+    /// \param p The priority of the item.
     void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
 
-    ///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 data[0].first;
     }
 
-    ///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.
     Prio prio() const {
       return data[0].second;
     }
 
-    ///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() {
       rmidx(0);
     }
 
-    ///Deletes \c i from the heap.
-
-    /**
-       This method deletes item \c i from the heap, if \c i was
-       already stored in the heap. 
-    */
+    /// \brief Deletes \c i from the heap.
+    ///
+    /// This method deletes item \c i from the heap, if \c i was
+    /// already stored in the heap.
+    /// \param i The item to erase. 
     void erase(const Item &i) {
       rmidx(iim[i]);
     }
 
     
-    ///Returns the priority of \c i.
-
-    /**
-       This function returns the priority of item \c i.  
-       \pre \c i must be in the heap.
-    */
+    /// \brief Returns the priority of \c i.
+    ///
+    /// This function returns the priority of item \c i.  
+    /// \pre \c i must be in the heap.
+    /// \param i The item.
     Prio operator[](const Item &i) const {
       int idx = iim[i];
       return data[idx].second;
     }
 
-    ///\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.
-    */
+    /// \brief \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.
+    /// \param i The item.
+    /// \param p The priority.
     void set(const Item &i, const Prio &p) {
       int idx = iim[i];
       if( idx < 0 ) {
@@ -235,38 +219,38 @@
       }
     }
 
-    ///Decreases the priority of \c i to \c p.
+    /// \brief 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.
-    */
+    /// 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.
+    /// \param i The item.
+    /// \param p The priority.
     void decrease(const Item &i, const Prio &p) {
       int idx = iim[i];
       bubble_up(idx, PairType(i,p));
     }
     
-    ///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.
-    */
+    /// \brief 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.
+    /// \param i The item.
+    /// \param p The priority.
     void increase(const Item &i, const Prio &p) {
       int idx = iim[i];
       bubble_down(idx, PairType(i,p), data.size());
     }
 
-    ///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.
+    /// \param i The item.
     state_enum state(const Item &i) const {
       int s = iim[i];
       if( s>=0 )
diff -r 52ef02524468 -r 7e93d3f0406d src/lemon/radix_heap.h
--- a/src/lemon/radix_heap.h	Sat Apr 09 19:27:48 2005 +0000
+++ b/src/lemon/radix_heap.h	Sat Apr 09 19:30:49 2005 +0000
@@ -1,5 +1,5 @@
 /* -*- C++ -*-
- * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
+ * src/lemon/radix_heap.h - Part of LEMON, a generic C++ optimization library
  *
  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Combinatorial Optimization Research Group, EGRES).
@@ -30,39 +30,54 @@
   /// \addtogroup auxdat
   /// @{
 
-  /// A Radix Heap implementation.
-  
-  ///\todo Please document...
-  ///
-  ///\sa BinHeap
-  ///\sa Dijkstra
+  /// \brief Exception thrown by RadixHeap.
+  ///  
+  /// This Exception is thrown when a smaller priority
+  /// is inserted into the \e RadixHeap then the last time erased.
+  /// \see RadixHeap
+  /// \author Balazs Dezso
 
-  class UnderFlowPriorityException : public RuntimeError {
+  class UnderFlowPriorityError : public RuntimeError {
   public:
     virtual const char* exceptionName() const {
-      return "lemon::UnderFlowPriorityException";
+      return "lemon::UnderFlowPriorityError";
     }  
   };
 
+  /// \brief A Radix Heap implementation.
+  ///
+  /// This class implements the \e radix \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. This heap type can store only items with \e int priority.
+  /// In a heap one can change the priority of an item, add or erase an 
+  /// item, but the priority cannot be decreased under the last removed 
+  /// item's priority.
+  ///
+  /// \param _Item Type of the items to be stored.  
+  /// \param _ItemIntMap A read and writable Item int map, used internally
+  /// to handle the cross references.
+  ///
+  /// \see BinHeap
+  /// \see Dijkstra
+  /// \author Balazs Dezso
+
   template <typename _Item, typename _ItemIntMap>
   class RadixHeap {
 
   public:
     typedef _Item Item;
-    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
     typedef int Prio;
     typedef _ItemIntMap ItemIntMap;
 
-    /**
-     * Each Item element have a state associated to it. It may be "in heap",
-     * "pre heap" or "post heap". The later two are indifferent from the
-     * heap's point of view, but may be useful to the user.
-     *
-     * The ItemIntMap _should_ be initialized in such way, that it maps
-     * PRE_HEAP (-1) to any element to be put in the heap...
-     */
-    ///\todo it is used nowhere
+    /// \brief Type to represent the items states.
     ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The later two are indifferent from the
+    /// heap's point of view, but may be useful to the user.
+    ///
+    /// The ItemIntMap _should_ be initialized in such way, that it maps
+    /// PRE_HEAP (-1) to any element to be put in the heap...
     enum state_enum {
       IN_HEAP = 0,
       PRE_HEAP = -1,
@@ -91,13 +106,26 @@
 
 
   public:
-    ///\e
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param _iim should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
     explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
       boxes.push_back(RadixBox(0, 1));
       boxes.push_back(RadixBox(1, 1));
     }
 
-    ///\e
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    ///
+    /// \param _iim It should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
+    ///
+    /// \param capacity It determines the initial capacity of the heap. 
     RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
       boxes.push_back(RadixBox(0, 1));
       boxes.push_back(RadixBox(1, 1));
@@ -106,9 +134,13 @@
       }
     }
 
-    ///\e
+    /// The number of items stored in the heap.
+    ///
+    /// \brief Returns the number of items stored in the heap.
     int size() const { return data.size(); }
-    ///\e
+    /// \brief 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(); }
 
   private:
@@ -183,7 +215,7 @@
     /// \brief Find up the proper box for the item with the given prio.
     int findDown(int start, int prio) {
       while (upper(start, prio)) {
-	if (--start < 0) throw UnderFlowPriorityException();
+	if (--start < 0) throw UnderFlowPriorityError();
       }
       return start;
     }
@@ -207,7 +239,6 @@
     /// \brief Rearrange the items of the heap and makes the 
     /// first box not empty.
     void moveDown() {
-      //      print(); printf("moveDown\n"); fflush(stdout);       
       int box = findFirst();
       if (box == 0) return;
       int min = minValue(box);
@@ -241,9 +272,12 @@
 
   public:
 
-    ///\e
+    /// \brief Insert an item into the heap with the given heap.
+    ///    
+    /// Adds \c i to the heap with priority \c p. 
+    /// \param i The item to insert.
+    /// \param p The priority of the item.
     void push(const Item &i, const Prio &p) {
-      fflush(stdout);
       int n = data.size();
       iim.set(i, n);
       data.push_back(RadixItem(i, p));
@@ -252,38 +286,43 @@
       }
       int box = findDown(boxes.size() - 1, p);
       insert(box, n);
-      //      printf("Push %d\n", p);
-      //print();
     }
 
-    ///\e
+    /// \brief Returns the item with minimum priority.
+    ///
+    /// This method returns the item with minimum priority.  
+    /// \pre The heap must be nonempty.  
     Item top() const {
-      //      print(); printf("top\n");  fflush(stdout);
       const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
       return data[boxes[0].first].item;
-      //      print(); printf("top_end\n");  fflush(stdout);
     }
 
-    /// Returns the prio of the top element of the heap.
+    /// \brief Returns the minimum priority.
+    ///
+    /// It returns the minimum priority.
+    /// \pre The heap must be nonempty.
     Prio prio() const {
-      //      print(); printf("prio\n"); fflush(stdout);
       const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
       return data[boxes[0].first].prio;
      }
 
-    ///\e
+    /// \brief Deletes the item with minimum priority.
+    ///
+    /// This method deletes the item with minimum priority.
+    /// \pre The heap must be non-empty.  
     void pop() {
-      //      print(); printf("pop\n"); fflush(stdout);
       moveDown();
       int index = boxes[0].first;
       iim[data[index].item] = POST_HEAP;
       remove(index);
       relocate_last(index);
-      //      printf("Pop \n");
-      //print();
     }
 
-    ///\e
+    /// \brief Deletes \c i from the heap.
+    ///
+    /// This method deletes item \c i from the heap, if \c i was
+    /// already stored in the heap.
+    /// \param i The item to erase. 
     void erase(const Item &i) {
       int index = iim[i];
       iim[i] = POST_HEAP;
@@ -291,13 +330,24 @@
       relocate_last(index);
    }
 
-    ///\e
+    /// \brief Returns the priority of \c i.
+    ///
+    /// This function returns the priority of item \c i.  
+    /// \pre \c i must be in the heap.
+    /// \param i The item.
     Prio operator[](const Item &i) const {
       int idx = iim[i];
       return data[idx].prio;
     }
 
-    ///\e
+    /// \brief \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.
+    /// It may throw an \e UnderFlowPriorityException. 
+    /// \param i The item.
+    /// \param p The priority.
     void set(const Item &i, const Prio &p) {
       int idx = iim[i];
       if( idx < 0 ) {
@@ -312,39 +362,47 @@
       }
     }
 
-    ///\e
+
+    /// \brief 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, and
+    /// \c should be greater then the last removed item's priority.
+    /// \param i The item.
+    /// \param p The priority.
     void decrease(const Item &i, const Prio &p) {
-      //      print(); printf("decrease\n"); fflush(stdout);
       int idx = iim[i];
       data[idx].prio = p;
       bubble_down(idx);
     }
 
-    ///\e
+    /// \brief 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.
+    /// \param i The item.
+    /// \param p The priority.
     void increase(const Item &i, const Prio &p) {
       int idx = iim[i];
       data[idx].prio = p;
       bubble_up(idx);
     }
 
-    ///\e
+    /// \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.
+    /// \param i The item.
     state_enum state(const Item &i) const {
       int s = iim[i];
       if( s >= 0 ) s = 0;
       return state_enum(s);
     }
 
-//     void print() const {
-//       for (int i = 0; i < boxes.size(); ++i) {
-// 	printf("(%d, %d) ", boxes[i].min, boxes[i].size);
-// 	for (int k = boxes[i].first; k != -1; k = data[k].next) {
-// 	  printf("%d ", data[k].prio);
-// 	}
-// 	printf("\n");
-//       }
-//       fflush(stdout);
-//     }
-
   }; // class RadixHeap