Changeset 373:259ea2d741a2 in lemon-0.x for src/include/fib_heap.h

Timestamp:

04/22/04 16:50:24 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

Changes in the documentation.

File:

• src/include/fib_heap.h (modified) (6 diffs)

src/include/fib_heap.h

@@ -1 +1 @@
 // -*- C++ -*-
-/*
- *template <typename Item, 
- *          typename Prio, 
- *          typename ItemIntMap, 
- *          typename Compare = std::less<Prio> >
- * 
- *constructors:
- *
- *FibHeap(ItemIntMap),   FibHeap(ItemIntMap, Compare)
- *
- *Member functions:
- *
- *int size() : returns the number of elements in the heap
- *
- *bool empty() : true iff size()=0
- *
- *void set(Item, Prio) : calls push(Item, Prio) if Item is not
- *     in the heap, and calls decrease/increase(Item, Prio) otherwise
- *
- *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
- *     mustn't be in the heap.
- *
- *Item top() : returns the Item with least Prio. 
- *     Must be called only if heap is nonempty.
- *
- *Prio prio() : returns the least Prio
- *     Must be called only if heap is nonempty.
- *
- *Prio get(Item) : returns Prio of Item
- *     Must be called only if Item is in heap.
- *
- *void pop() : deletes the Item with least Prio
- *
- *void erase(Item) : deletes Item from the heap if it was already there
- *
- *void decrease(Item, P) : decreases prio of Item to P. 
- *     Item must be in the heap with prio at least P.
- *
- *void increase(Item, P) : sets prio of Item to P. 
- *
- *state_enum state(Item) : returns PRE_HEAP if Item has not been in the 
- *     heap until now, IN_HEAP if it is in the heap at the moment, and 
- *     POST_HEAP otherwise. In the latter case it is possible that Item
- *     will get back to the heap again. 
- *
- *In Fibonacci heaps, increase and erase are not efficient, in case of
- *many calls to these operations, it is better to use bin_heap.
- */
-
-#ifndef FIB_HEAP_H
-#define FIB_HEAP_H
+
+#ifndef HUGO_FIB_HEAP_H
+#define HUGO_FIB_HEAP_H
 
 ///\file
@@ -61 +13 @@
 namespace hugo {
   
-  /// A Fibonacci Heap implementation.
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  /// An implementation of the Fibonacci Heap.
+
+  /**
+     This class implements the \e Fibonacci \e heap data structure. A \e
+     heap is a data structure for storing items with specified priorities,
+     such that finding the item with minimum priority is efficient. In a
+     heap one can change the priority of an item, and to add or erase an
+     item.
+
+     The methods \ref increase and \ref erase are not efficient, in
+     case of many calls to these operations, it is better to use
+     a binary heap.
+     
+     /param Item The type of the items to be stored.  
+     /param Prio The type of the priority of the items.
+     /param ItemIntMap A read and writable Item int map, for the usage of
+     the heap.
+     /param Compare A class for the comparison of the priorities. The
+     default is \c std::less<Prio>.
+
+  */
+
+#ifdef DOXYGEN
+  template <typename Item, 
+            typename Prio, 
+            typename ItemIntMap, 
+            typename Compare>
+#else
+  template <typename Item, 
+            typename Prio, 
+            typename ItemIntMap, 
             typename Compare = std::less<Prio> >
+#endif
   class FibHeap {
-    
+  public: 
     typedef Prio PrioType;
     
+  private:
     class store;
     
@@ -75 +58 @@
     Compare comp;
     int num_items;
-
+    
     ///\todo It is use nowhere
     ///\todo It doesn't conform to the naming conventions.
@@ -87 +70 @@
   public :
     
-    FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} 
-    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), 
+    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 
+    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
       iimap(_iimap), comp(_comp), num_items() {}
     
-    
-    int size() const {
-      return num_items; 
-    }
-
-
+    ///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 true iff the heap stores no items.
+    */
     bool empty() const { return num_items==0; }
 
+    ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
+
+    /**
+       This method calls \ref push(item, value) if \c item is not
+       stored in the heap, and it calls \ref decrease(it, \c value) or
+       \ref increase(it, \c value) otherwise.
+    */
+    void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
+    
+    ///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 it, PrioType const value); /*vigyazat: az implementacioban it van*/
+    
+    
+    ///Returns the item having the minimum priority w.r.t.  Compare.
+    
+    /**
+       This method returns the item having the minimum priority w.r.t.  Compare. 
+       \pre The heap must be nonempty.
+    */
+    Item top() const { return container[minimum].name; }
+    
+
+    ///Returns the minimum priority w.r.t.  Compare.
+
+    /**
+       It returns the minimum priority w.r.t.  Compare.
+       \pre The heap must be nonempty.
+    */
+    PrioType prio() const { return container[minimum].prio; }
+    
+
+    ///Returns the priority of \c item.
+
+    /**
+       It returns the priority of \c item.
+       \pre \c item must be in the heap.
+    */
+    PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
+    
+    ///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& it) const { 
+      return container[iimap[it]].prio; 
+    }
+
+
+    ///Deletes the item with minimum priority w.r.t.  Compare.
+
+    /**
+    This method deletes the item with minimum priority w.r.t. 
+    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.
+    */
+    void erase (const Item& item); /*vigyazat: az implementacioban it van*/
+
+    ///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 w.r.t.  Compare.
+    */
+    void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
+
+
+    ///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 one wants to \e increase
+       (w.r.t.  Compare) the priority of \c item, because this
+       method is inefficient.
+    */
+    void increase (Item it, PrioType const value) {
+      erase(it);
+      push(it, value);
+    }
+
+
+    ///Tells if \c item is in, was in, or has not 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 &it);  /*vigyazat: az implementacioban it van*/
+
+
+
+    // **********************************************************************
+    //  IMPLEMENTATIONS
+    // **********************************************************************
+    
 
     void set (Item const it, PrioType const value) {
@@ -139 +241 @@
     }
     
-
-    Item top() const {
-      return container[minimum].name;
-    }
-    
-    
-    PrioType prio() const {
-      return container[minimum].prio;
-    }
-    
-
-
-
-    PrioType& operator[](const Item& it) {
-      return container[iimap[it]].prio;
-    }
-    
-    const PrioType& operator[](const Item& it) const {
-      return container[iimap[it]].prio;
-    }
-
-//     const PrioType get(const Item& it) const {
-//       return container[iimap[it]].prio;
-//     }
 
     void pop() {
@@ -224 +302 @@
    
 
-    void increase (Item it, PrioType const value) {
-      erase(it);
-      push(it, value);
-    }
-
-
     state_enum state(const Item &it) const {
       int i=iimap[it];