Changeset 1717:75fe24093ded in lemon0.x for lemon/fib_heap.h
 Timestamp:
 10/14/05 12:40:00 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2244
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/fib_heap.h
r1435 r1717 89 89 }; 90 90 91 ///The constructor 92 93 /** 94 \c _iimap should be given to the constructor, since it is 95 used internally to handle the cross references. 96 */ 91 /// \brief The constructor 92 /// 93 /// \c _iimap should be given to the constructor, since it is 94 /// used internally to handle the cross references. 97 95 explicit FibHeap(ItemIntMap &_iimap) 98 96 : minimum(0), iimap(_iimap), num_items() {} 99 97 100 ///The constructor 101 102 /** 103 \c _iimap should be given to the constructor, since it is used 104 internally to handle the cross references. \c _comp is an 105 object for ordering of the priorities. 106 */ 98 /// \brief The constructor 99 /// 100 /// \c _iimap should be given to the constructor, since it is used 101 /// internally to handle the cross references. \c _comp is an 102 /// object for ordering of the priorities. 107 103 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 108 104 iimap(_iimap), comp(_comp), num_items() {} 109 105 110 ///The number of items stored in the heap. 111 112 /** 113 Returns the number of items stored in the heap. 114 */ 106 /// \brief The number of items stored in the heap. 107 /// 108 /// Returns the number of items stored in the heap. 115 109 int size() const { return num_items; } 116 110 117 ///Checks if the heap stores no items. 118 119 /** 120 Returns \c true if and only if the heap stores no items. 121 */ 111 /// \brief Checks if the heap stores no items. 112 /// 113 /// Returns \c true if and only if the heap stores no items. 122 114 bool empty() const { return num_items==0; } 123 115 124 ///\c item gets to the heap with priority \c value independently if \c item was already there. 125 126 /** 127 This method calls \ref push(\c item, \c value) if \c item is not 128 stored in the heap and it calls \ref decrease(\c item, \c value) or 129 \ref increase(\c item, \c value) otherwise. 130 */ 116 /// \brief Make empty this heap. 117 /// 118 /// Make empty this heap. 119 void clear() { 120 for (int i = 0; i < (int)container.size(); ++i) { 121 iimap[container[i].name] = 2; 122 } 123 container.clear(); minimum = 0; num_items = 0; 124 } 125 126 /// \brief \c item gets to the heap with priority \c value independently 127 /// if \c item was already there. 128 /// 129 /// This method calls \ref push(\c item, \c value) if \c item is not 130 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 131 /// \ref increase(\c item, \c value) otherwise. 131 132 void set (Item const item, PrioType const value); 132 133 133 ///Adds \c item to the heap with priority \c value. 134 135 /** 136 Adds \c item to the heap with priority \c value. 137 \pre \c item must not be stored in the heap. 138 */ 134 /// \brief Adds \c item to the heap with priority \c value. 135 /// 136 /// Adds \c item to the heap with priority \c value. 137 /// \pre \c item must not be stored in the heap. 139 138 void push (Item const item, PrioType const value); 140 139 141 ///Returns the item with minimum priority relative to \c Compare. 142 143 /** 144 This method returns the item with minimum priority relative to \c 145 Compare. 146 \pre The heap must be nonempty. 147 */ 140 /// \brief Returns the item with minimum priority relative to \c Compare. 141 /// 142 /// This method returns the item with minimum priority relative to \c 143 /// Compare. 144 /// \pre The heap must be nonempty. 148 145 Item top() const { return container[minimum].name; } 149 146 150 ///Returns the minimum priority relative to \c Compare. 151 152 /** 153 It returns the minimum priority relative to \c Compare. 154 \pre The heap must be nonempty. 155 */ 147 /// \brief Returns the minimum priority relative to \c Compare. 148 /// 149 /// It returns the minimum priority relative to \c Compare. 150 /// \pre The heap must be nonempty. 156 151 PrioType prio() const { return container[minimum].prio; } 157 152 158 ///Returns the priority of \c item. 159 160 /** 161 This function returns the priority of \c item. 162 \pre \c item must be in the heap. 163 */ 153 /// \brief Returns the priority of \c item. 154 /// 155 /// This function returns the priority of \c item. 156 /// \pre \c item must be in the heap. 164 157 PrioType& operator[](const Item& item) { 165 158 return container[iimap[item]].prio; 166 159 } 167 160 168 ///Returns the priority of \c item. 169 170 /** 171 It returns the priority of \c item. 172 \pre \c item must be in the heap. 173 */ 161 /// \brief Returns the priority of \c item. 162 /// 163 /// It returns the priority of \c item. 164 /// \pre \c item must be in the heap. 174 165 const PrioType& operator[](const Item& item) const { 175 166 return container[iimap[item]].prio; … … 177 168 178 169 179 ///Deletes the item with minimum priority relative to \c Compare. 180 181 /** 182 This method deletes the item with minimum priority relative to \c 183 Compare from the heap. 184 \pre The heap must be nonempty. 185 */ 170 /// \brief Deletes the item with minimum priority relative to \c Compare. 171 /// 172 /// This method deletes the item with minimum priority relative to \c 173 /// Compare from the heap. 174 /// \pre The heap must be nonempty. 186 175 void pop(); 187 176 188 ///Deletes \c item from the heap. 189 190 /** 191 This method deletes \c item from the heap, if \c item was already 192 stored in the heap. It is quite inefficient in Fibonacci heaps. 193 */ 177 /// \brief Deletes \c item from the heap. 178 /// 179 /// This method deletes \c item from the heap, if \c item was already 180 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 194 181 void erase (const Item& item); 195 182 196 ///Decreases the priority of \c item to \c value. 197 198 /** 199 This method decreases the priority of \c item to \c value. 200 \pre \c item must be stored in the heap with priority at least \c 201 value relative to \c Compare. 202 */ 183 /// \brief Decreases the priority of \c item to \c value. 184 /// 185 /// This method decreases the priority of \c item to \c value. 186 /// \pre \c item must be stored in the heap with priority at least \c 187 /// value relative to \c Compare. 203 188 void decrease (Item item, PrioType const value); 204 189 205 ///Increases the priority of \c item to \c value. 206 207 /** 208 This method sets the priority of \c item to \c value. Though 209 there is no precondition on the priority of \c item, this 210 method should be used only if it is indeed necessary to increase 211 (relative to \c Compare) the priority of \c item, because this 212 method is inefficient. 213 */ 190 /// \brief Increases the priority of \c item to \c value. 191 /// 192 /// This method sets the priority of \c item to \c value. Though 193 /// there is no precondition on the priority of \c item, this 194 /// method should be used only if it is indeed necessary to increase 195 /// (relative to \c Compare) the priority of \c item, because this 196 /// method is inefficient. 214 197 void increase (Item item, PrioType const value) { 215 198 erase(item); … … 218 201 219 202 220 ///Returns if \c item is in, has already been in, or has never been in the heap. 221 222 /** 223 This method returns PRE_HEAP if \c item has never been in the 224 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 225 otherwise. In the latter case it is possible that \c item will 226 get back to the heap again. 227 */ 203 /// \brief Returns if \c item is in, has already been in, or has never 204 /// been in the heap. 205 /// 206 /// This method returns PRE_HEAP if \c item has never been in the 207 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 208 /// otherwise. In the latter case it is possible that \c item will 209 /// get back to the heap again. 228 210 state_enum state(const Item &item) const { 229 211 int i=iimap[item];
Note: See TracChangeset
for help on using the changeset viewer.