1.1 --- a/lemon/fib_heap.h Fri Oct 07 11:05:35 2005 +0000
1.2 +++ b/lemon/fib_heap.h Fri Oct 14 10:40:00 2005 +0000
1.3 @@ -88,143 +88,125 @@
1.4 POST_HEAP = -2
1.5 };
1.6
1.7 - ///The constructor
1.8 -
1.9 - /**
1.10 - \c _iimap should be given to the constructor, since it is
1.11 - used internally to handle the cross references.
1.12 - */
1.13 + /// \brief The constructor
1.14 + ///
1.15 + /// \c _iimap should be given to the constructor, since it is
1.16 + /// used internally to handle the cross references.
1.17 explicit FibHeap(ItemIntMap &_iimap)
1.18 : minimum(0), iimap(_iimap), num_items() {}
1.19
1.20 - ///The constructor
1.21 -
1.22 - /**
1.23 - \c _iimap should be given to the constructor, since it is used
1.24 - internally to handle the cross references. \c _comp is an
1.25 - object for ordering of the priorities.
1.26 - */
1.27 + /// \brief The constructor
1.28 + ///
1.29 + /// \c _iimap should be given to the constructor, since it is used
1.30 + /// internally to handle the cross references. \c _comp is an
1.31 + /// object for ordering of the priorities.
1.32 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
1.33 iimap(_iimap), comp(_comp), num_items() {}
1.34
1.35 - ///The number of items stored in the heap.
1.36 -
1.37 - /**
1.38 - Returns the number of items stored in the heap.
1.39 - */
1.40 + /// \brief The number of items stored in the heap.
1.41 + ///
1.42 + /// Returns the number of items stored in the heap.
1.43 int size() const { return num_items; }
1.44
1.45 - ///Checks if the heap stores no items.
1.46 -
1.47 - /**
1.48 - Returns \c true if and only if the heap stores no items.
1.49 - */
1.50 + /// \brief Checks if the heap stores no items.
1.51 + ///
1.52 + /// Returns \c true if and only if the heap stores no items.
1.53 bool empty() const { return num_items==0; }
1.54
1.55 - ///\c item gets to the heap with priority \c value independently if \c item was already there.
1.56 + /// \brief Make empty this heap.
1.57 + ///
1.58 + /// Make empty this heap.
1.59 + void clear() {
1.60 + for (int i = 0; i < (int)container.size(); ++i) {
1.61 + iimap[container[i].name] = -2;
1.62 + }
1.63 + container.clear(); minimum = 0; num_items = 0;
1.64 + }
1.65
1.66 - /**
1.67 - This method calls \ref push(\c item, \c value) if \c item is not
1.68 - stored in the heap and it calls \ref decrease(\c item, \c value) or
1.69 - \ref increase(\c item, \c value) otherwise.
1.70 - */
1.71 + /// \brief \c item gets to the heap with priority \c value independently
1.72 + /// if \c item was already there.
1.73 + ///
1.74 + /// This method calls \ref push(\c item, \c value) if \c item is not
1.75 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
1.76 + /// \ref increase(\c item, \c value) otherwise.
1.77 void set (Item const item, PrioType const value);
1.78
1.79 - ///Adds \c item to the heap with priority \c value.
1.80 -
1.81 - /**
1.82 - Adds \c item to the heap with priority \c value.
1.83 - \pre \c item must not be stored in the heap.
1.84 - */
1.85 + /// \brief Adds \c item to the heap with priority \c value.
1.86 + ///
1.87 + /// Adds \c item to the heap with priority \c value.
1.88 + /// \pre \c item must not be stored in the heap.
1.89 void push (Item const item, PrioType const value);
1.90
1.91 - ///Returns the item with minimum priority relative to \c Compare.
1.92 -
1.93 - /**
1.94 - This method returns the item with minimum priority relative to \c
1.95 - Compare.
1.96 - \pre The heap must be nonempty.
1.97 - */
1.98 + /// \brief Returns the item with minimum priority relative to \c Compare.
1.99 + ///
1.100 + /// This method returns the item with minimum priority relative to \c
1.101 + /// Compare.
1.102 + /// \pre The heap must be nonempty.
1.103 Item top() const { return container[minimum].name; }
1.104
1.105 - ///Returns the minimum priority relative to \c Compare.
1.106 -
1.107 - /**
1.108 - It returns the minimum priority relative to \c Compare.
1.109 - \pre The heap must be nonempty.
1.110 - */
1.111 + /// \brief Returns the minimum priority relative to \c Compare.
1.112 + ///
1.113 + /// It returns the minimum priority relative to \c Compare.
1.114 + /// \pre The heap must be nonempty.
1.115 PrioType prio() const { return container[minimum].prio; }
1.116
1.117 - ///Returns the priority of \c item.
1.118 -
1.119 - /**
1.120 - This function returns the priority of \c item.
1.121 - \pre \c item must be in the heap.
1.122 - */
1.123 + /// \brief Returns the priority of \c item.
1.124 + ///
1.125 + /// This function returns the priority of \c item.
1.126 + /// \pre \c item must be in the heap.
1.127 PrioType& operator[](const Item& item) {
1.128 return container[iimap[item]].prio;
1.129 }
1.130
1.131 - ///Returns the priority of \c item.
1.132 -
1.133 - /**
1.134 - It returns the priority of \c item.
1.135 - \pre \c item must be in the heap.
1.136 - */
1.137 + /// \brief Returns the priority of \c item.
1.138 + ///
1.139 + /// It returns the priority of \c item.
1.140 + /// \pre \c item must be in the heap.
1.141 const PrioType& operator[](const Item& item) const {
1.142 return container[iimap[item]].prio;
1.143 }
1.144
1.145
1.146 - ///Deletes the item with minimum priority relative to \c Compare.
1.147 -
1.148 - /**
1.149 - This method deletes the item with minimum priority relative to \c
1.150 - Compare from the heap.
1.151 - \pre The heap must be non-empty.
1.152 - */
1.153 + /// \brief Deletes the item with minimum priority relative to \c Compare.
1.154 + ///
1.155 + /// This method deletes the item with minimum priority relative to \c
1.156 + /// Compare from the heap.
1.157 + /// \pre The heap must be non-empty.
1.158 void pop();
1.159
1.160 - ///Deletes \c item from the heap.
1.161 -
1.162 - /**
1.163 - This method deletes \c item from the heap, if \c item was already
1.164 - stored in the heap. It is quite inefficient in Fibonacci heaps.
1.165 - */
1.166 + /// \brief Deletes \c item from the heap.
1.167 + ///
1.168 + /// This method deletes \c item from the heap, if \c item was already
1.169 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
1.170 void erase (const Item& item);
1.171
1.172 - ///Decreases the priority of \c item to \c value.
1.173 -
1.174 - /**
1.175 - This method decreases the priority of \c item to \c value.
1.176 - \pre \c item must be stored in the heap with priority at least \c
1.177 - value relative to \c Compare.
1.178 - */
1.179 + /// \brief Decreases the priority of \c item to \c value.
1.180 + ///
1.181 + /// This method decreases the priority of \c item to \c value.
1.182 + /// \pre \c item must be stored in the heap with priority at least \c
1.183 + /// value relative to \c Compare.
1.184 void decrease (Item item, PrioType const value);
1.185
1.186 - ///Increases the priority of \c item to \c value.
1.187 -
1.188 - /**
1.189 - This method sets the priority of \c item to \c value. Though
1.190 - there is no precondition on the priority of \c item, this
1.191 - method should be used only if it is indeed necessary to increase
1.192 - (relative to \c Compare) the priority of \c item, because this
1.193 - method is inefficient.
1.194 - */
1.195 + /// \brief Increases the priority of \c item to \c value.
1.196 + ///
1.197 + /// This method sets the priority of \c item to \c value. Though
1.198 + /// there is no precondition on the priority of \c item, this
1.199 + /// method should be used only if it is indeed necessary to increase
1.200 + /// (relative to \c Compare) the priority of \c item, because this
1.201 + /// method is inefficient.
1.202 void increase (Item item, PrioType const value) {
1.203 erase(item);
1.204 push(item, value);
1.205 }
1.206
1.207
1.208 - ///Returns if \c item is in, has already been in, or has never been in the heap.
1.209 -
1.210 - /**
1.211 - This method returns PRE_HEAP if \c item has never been in the
1.212 - heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.213 - otherwise. In the latter case it is possible that \c item will
1.214 - get back to the heap again.
1.215 - */
1.216 + /// \brief Returns if \c item is in, has already been in, or has never
1.217 + /// been in the heap.
1.218 + ///
1.219 + /// This method returns PRE_HEAP if \c item has never been in the
1.220 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.221 + /// otherwise. In the latter case it is possible that \c item will
1.222 + /// get back to the heap again.
1.223 state_enum state(const Item &item) const {
1.224 int i=iimap[item];
1.225 if( i>=0 ) {