1.1 --- a/src/hugo/fib_heap.h Wed Sep 15 12:20:21 2004 +0000
1.2 +++ b/src/hugo/fib_heap.h Wed Sep 15 14:04:57 2004 +0000
1.3 @@ -3,8 +3,8 @@
1.4 #ifndef HUGO_FIB_HEAP_H
1.5 #define HUGO_FIB_HEAP_H
1.6
1.7 +///\file
1.8 ///\ingroup auxdat
1.9 -///\file
1.10 ///\brief Fibonacci Heap implementation.
1.11
1.12 #include <vector>
1.13 @@ -16,28 +16,27 @@
1.14 /// \addtogroup auxdat
1.15 /// @{
1.16
1.17 - /// An implementation of the Fibonacci Heap.
1.18 + /// Fibonacci Heap.
1.19
1.20 - /**
1.21 - This class implements the \e Fibonacci \e heap data structure. A \e heap
1.22 - is a data structure for storing items with specified values called \e
1.23 - priorities, such that finding the item with minimum priority with respect
1.24 - to \e Compare is efficient. In a heap one can change the priority of an
1.25 - item, add or erase an item, etc.
1.26 -
1.27 - The methods \ref increase and \ref erase are not efficient in a Fibonacci
1.28 - heap. In case of many calls to these operations, it is better to use a
1.29 - \e binary \e heap.
1.30 -
1.31 - \param Item The type of the items to be stored.
1.32 - \param Prio The type of the priority of the items.
1.33 - \param ItemIntMap A read and writable Item int map, for the usage of
1.34 - the heap.
1.35 - \param Compare A class for the comparison of the priorities. The
1.36 - default is \c std::less<Prio>.
1.37 -
1.38 - */
1.39 -
1.40 + ///This class implements the \e Fibonacci \e heap data structure. A \e heap
1.41 + ///is a data structure for storing items with specified values called \e
1.42 + ///priorities in such a way that finding the item with minimum priority is
1.43 + ///efficient. \ref Compare specifies the ordering of the priorities. In a heap
1.44 + ///one can change the priority of an item, add or erase an item, etc.
1.45 + ///
1.46 + ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
1.47 + ///heap. In case of many calls to these operations, it is better to use a
1.48 + ///\e binary \e heap.
1.49 + ///
1.50 + ///\param Item Type of the items to be stored.
1.51 + ///\param Prio Type of the priority of the items.
1.52 + ///\param ItemIntMap A read and writable Item int map, for the usage of
1.53 + ///the heap.
1.54 + ///\param Compare A class for the ordering of the priorities. The
1.55 + ///default is \c std::less<Prio>.
1.56 + ///
1.57 + ///\author Jacint Szabo
1.58 +
1.59 #ifdef DOXYGEN
1.60 template <typename Item,
1.61 typename Prio,
1.62 @@ -83,7 +82,7 @@
1.63 ///Checks if the heap stores no items.
1.64
1.65 /**
1.66 - Returns \c true iff the heap stores no items.
1.67 + Returns \c true if and only if the heap stores no items.
1.68 */
1.69 bool empty() const { return num_items==0; }
1.70
1.71 @@ -104,29 +103,27 @@
1.72 */
1.73 void push (Item const item, PrioType const value);
1.74
1.75 -
1.76 - ///Returns the item having the minimum priority w.r.t. Compare.
1.77 + ///Returns the item with minimum priority relative to \ref Compare.
1.78
1.79 /**
1.80 - This method returns the item having the minimum priority w.r.t. Compare.
1.81 - \pre The heap must be nonempty.
1.82 + This method returns the item with minimum priority relative to \ref
1.83 + Compare.
1.84 + \pre The heap must be nonempty.
1.85 */
1.86 Item top() const { return container[minimum].name; }
1.87 -
1.88
1.89 - ///Returns the minimum priority w.r.t. Compare.
1.90 + ///Returns the minimum priority relative to \ref Compare.
1.91
1.92 /**
1.93 - It returns the minimum priority w.r.t. Compare.
1.94 + It returns the minimum priority relative to \ref Compare.
1.95 \pre The heap must be nonempty.
1.96 */
1.97 PrioType prio() const { return container[minimum].prio; }
1.98
1.99 -
1.100 ///Returns the priority of \c item.
1.101
1.102 /**
1.103 - It returns the priority of \c item.
1.104 + This function returns the priority of \c item.
1.105 \pre \c item must be in the heap.
1.106 */
1.107 PrioType& operator[](const Item& item) {
1.108 @@ -144,12 +141,12 @@
1.109 }
1.110
1.111
1.112 - ///Deletes the item with minimum priority w.r.t. Compare.
1.113 + ///Deletes the item with minimum priority relative to \ref Compare.
1.114
1.115 /**
1.116 - This method deletes the item with minimum priority w.r.t.
1.117 - Compare from the heap.
1.118 - \pre The heap must be non-empty.
1.119 + This method deletes the item with minimum priority relative to \ref
1.120 + Compare from the heap.
1.121 + \pre The heap must be non-empty.
1.122 */
1.123 void pop();
1.124
1.125 @@ -166,18 +163,17 @@
1.126 /**
1.127 This method decreases the priority of \c item to \c value.
1.128 \pre \c item must be stored in the heap with priority at least \c
1.129 - value w.r.t. Compare.
1.130 + value relative to \ref Compare.
1.131 */
1.132 void decrease (Item item, PrioType const value);
1.133
1.134 -
1.135 ///Increases the priority of \c item to \c value.
1.136
1.137 /**
1.138 This method sets the priority of \c item to \c value. Though
1.139 there is no precondition on the priority of \c item, this
1.140 - method should be used only if there is a need to really \e increase
1.141 - (w.r.t. Compare) the priority of \c item, because this
1.142 + method should be used only if it is indeed necessary to increase
1.143 + (relative to \ref Compare) the priority of \c item, because this
1.144 method is inefficient.
1.145 */
1.146 void increase (Item item, PrioType const value) {
1.147 @@ -186,7 +182,7 @@
1.148 }
1.149
1.150
1.151 - ///Tells if \c item is in, was already in, or has never been in the heap.
1.152 + ///Returns if \c item is in, has already been in, or has never been in the heap.
1.153
1.154 /**
1.155 This method returns PRE_HEAP if \c item has never been in the