Changeset 1331:7e93d3f0406d in lemon-0.x for src/lemon/radix_heap.h

Timestamp:

04/09/05 21:30:49 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Documentation improvments.

File:

• src/lemon/radix_heap.h (modified) (17 diffs)

src/lemon/radix_heap.h

@@ -1 +1 @@
 /* -*- 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
@@ -31 +31 @@
   /// @{
 
-  /// A Radix Heap implementation.
-  
-  ///\todo Please document...
-  ///
-  ///\sa BinHeap
-  ///\sa Dijkstra
-
-  class UnderFlowPriorityException : public RuntimeError {
+  /// \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 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 {
@@ -50 +68 @@
   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,
@@ -92 +107 @@
 
   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));
@@ -98 +118 @@
     }
 
-    ///\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));
@@ -107 +135 @@
     }
 
-    ///\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(); }
 
@@ -184 +216 @@
     int findDown(int start, int prio) {
       while (upper(start, prio)) {
-        if (--start < 0) throw UnderFlowPriorityException();
+        if (--start < 0) throw UnderFlowPriorityError();
       }
       return start;
@@ -208 +240 @@
     /// first box not empty.
     void moveDown() {
-      //      print(); printf("moveDown\n"); fflush(stdout);       
       int box = findFirst();
       if (box == 0) return;
@@ -242 +273 @@
   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);
@@ -253 +287 @@
       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;
@@ -280 +317 @@
       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];
@@ -292 +331 @@
    }
 
-    ///\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];
@@ -298 +341 @@
     }
 
-    ///\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];
@@ -313 +363 @@
     }
 
-    ///\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;
@@ -321 +377 @@
     }
 
-    ///\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];
@@ -328 +390 @@
     }
 
-    ///\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];
@@ -335 +404 @@
     }
 
-//     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