Changeset 1331:7e93d3f0406d in lemon0.x
 Timestamp:
 04/09/05 21:30:49 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1770
 Location:
 src/lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/bin_heap.h
r1270 r1331 60 60 typedef Compare PrioCompare; 61 61 62 /** 63 * Each Item element have a state associated to it. It may be "in heap", 64 * "pre heap" or "post heap". The later two are indifferent from the 65 * heap's point of view, but may be useful to the user. 66 * 67 * The ItemIntMap _should_ be initialized in such way, that it maps 68 * PRE_HEAP (1) to any element to be put in the heap... 69 */ 70 ///\todo it is used nowhere 71 /// 62 /// \brief Type to represent the items states. 63 /// 64 /// Each Item element have a state associated to it. It may be "in heap", 65 /// "pre heap" or "post heap". The later two are indifferent from the 66 /// heap's point of view, but may be useful to the user. 67 /// 68 /// The ItemIntMap _should_ be initialized in such way, that it maps 69 /// PRE_HEAP (1) to any element to be put in the heap... 72 70 enum state_enum { 73 71 IN_HEAP = 0, … … 79 77 std::vector<PairType> data; 80 78 Compare comp; 81 // FIXME: jo ez igy???82 79 ItemIntMap &iim; 83 80 84 81 public: 85 /// The constructor86 87 / **88 \c_iim should be given to the constructor, since it is used89 internally to handle the cross references.90 */82 /// \brief The constructor. 83 /// 84 /// The constructor. 85 /// \param _iim should be given to the constructor, since it is used 86 /// internally to handle the cross references. The value of the map 87 /// should be PRE_HEAP (1) for each element. 91 88 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} 92 89 93 ///The constructor 94 95 /** 96 \c _iim should be given to the constructor, since it is used 97 internally to handle the cross references. \c _comp is an 98 object for ordering of the priorities. 99 */ 90 /// \brief The constructor. 91 /// 92 /// The constructor. 93 /// \param _iim should be given to the constructor, since it is used 94 /// internally to handle the cross references. The value of the map 95 /// should be PRE_HEAP (1) for each element. 96 /// 97 /// \param _comp The comparator function object. 100 98 BinHeap(ItemIntMap &_iim, const Compare &_comp) 101 99 : iim(_iim), comp(_comp) {} 102 100 103 101 104 ///The number of items stored in the heap. 105 106 /** 107 Returns the number of items stored in the heap. 108 */ 102 /// The number of items stored in the heap. 103 /// 104 /// \brief Returns the number of items stored in the heap. 109 105 int size() const { return data.size(); } 110 106 111 ///Checks if the heap stores no items. 112 113 /** 114 Returns \c true if and only if the heap stores no items. 115 */ 107 /// \brief Checks if the heap stores no items. 108 /// 109 /// Returns \c true if and only if the heap stores no items. 116 110 bool empty() const { return data.empty(); } 117 111 … … 143 137 144 138 public: 145 ///Adds \c p.first to the heap with priority \c p.second. 146 147 /** 148 Adds \c p.first to the heap with priority \c p.second. 149 \c p.first must not be stored in the heap. 150 */ 139 /// \brief Insert a pair of item and priority into the heap. 140 /// 141 /// Adds \c p.first to the heap with priority \c p.second. 142 /// \param p The pair to insert. 151 143 void push(const PairType &p) { 152 144 int n = data.size(); … … 155 147 } 156 148 157 ///Adds \c i to the heap with priority \c p. 158 159 /** 160 Adds \c i to the heap with priority \c p. 161 \pre \c i must not be stored in the heap. 162 */ 149 /// \brief Insert an item into the heap with the given heap. 150 /// 151 /// Adds \c i to the heap with priority \c p. 152 /// \param i The item to insert. 153 /// \param p The priority of the item. 163 154 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } 164 155 165 ///Returns the item with minimum priority relative to \c Compare. 166 167 /** 168 This method returns the item with minimum priority relative to \c 169 Compare. 170 \pre The heap must be nonempty. 171 */ 156 /// \brief Returns the item with minimum priority relative to \c Compare. 157 /// 158 /// This method returns the item with minimum priority relative to \c 159 /// Compare. 160 /// \pre The heap must be nonempty. 172 161 Item top() const { 173 162 return data[0].first; 174 163 } 175 164 176 ///Returns the minimum priority relative to \c Compare. 177 178 /** 179 It returns the minimum priority relative to \c Compare. 180 \pre The heap must be nonempty. 181 */ 165 /// \brief Returns the minimum priority relative to \c Compare. 166 /// 167 /// It returns the minimum priority relative to \c Compare. 168 /// \pre The heap must be nonempty. 182 169 Prio prio() const { 183 170 return data[0].second; 184 171 } 185 172 186 ///Deletes the item with minimum priority relative to \c Compare. 187 188 /** 189 This method deletes the item with minimum priority relative to \c 190 Compare from the heap. 191 \pre The heap must be nonempty. 192 */ 173 /// \brief Deletes the item with minimum priority relative to \c Compare. 174 /// 175 /// This method deletes the item with minimum priority relative to \c 176 /// Compare from the heap. 177 /// \pre The heap must be nonempty. 193 178 void pop() { 194 179 rmidx(0); 195 180 } 196 181 197 ///Deletes \c i from the heap. 198 199 /** 200 This method deletes item \c i from the heap, if \c i was 201 already stored in the heap. 202 */ 182 /// \brief Deletes \c i from the heap. 183 /// 184 /// This method deletes item \c i from the heap, if \c i was 185 /// already stored in the heap. 186 /// \param i The item to erase. 203 187 void erase(const Item &i) { 204 188 rmidx(iim[i]); … … 206 190 207 191 208 ///Returns the priority of \c i. 209 210 /** 211 This function returns the priority of item \c i. 212 \pre \c i must be in the heap. 213 */ 192 /// \brief Returns the priority of \c i. 193 /// 194 /// This function returns the priority of item \c i. 195 /// \pre \c i must be in the heap. 196 /// \param i The item. 214 197 Prio operator[](const Item &i) const { 215 198 int idx = iim[i]; … … 217 200 } 218 201 219 ///\c i gets to the heap with priority \c p independently if \c i was already there. 220 221 /** 222 This method calls \ref push(\c i, \c p) if \c i is not stored 223 in the heap and sets the priority of \c i to \c p otherwise. 224 */ 202 /// \brief \c i gets to the heap with priority \c p independently 203 /// if \c i was already there. 204 /// 205 /// This method calls \ref push(\c i, \c p) if \c i is not stored 206 /// in the heap and sets the priority of \c i to \c p otherwise. 207 /// \param i The item. 208 /// \param p The priority. 225 209 void set(const Item &i, const Prio &p) { 226 210 int idx = iim[i]; … … 236 220 } 237 221 238 /// Decreases the priority of \c i to \c p.239 240 / **241 This method decreases the priority of item \c i to \c p.242 \pre \c i must be stored in the heap with priority at least \c243 p relative to \c Compare.244 */222 /// \brief Decreases the priority of \c i to \c p. 223 224 /// This method decreases the priority of item \c i to \c p. 225 /// \pre \c i must be stored in the heap with priority at least \c 226 /// p relative to \c Compare. 227 /// \param i The item. 228 /// \param p The priority. 245 229 void decrease(const Item &i, const Prio &p) { 246 230 int idx = iim[i]; … … 248 232 } 249 233 250 /// Increases the priority of \c i to \c p.251 252 / **253 This method sets the priority of item \c i to \c p.254 \pre \c i must be stored in the heap with priority at most \c255 p relative to \c Compare.256 */234 /// \brief Increases the priority of \c i to \c p. 235 /// 236 /// This method sets the priority of item \c i to \c p. 237 /// \pre \c i must be stored in the heap with priority at most \c 238 /// p relative to \c Compare. 239 /// \param i The item. 240 /// \param p The priority. 257 241 void increase(const Item &i, const Prio &p) { 258 242 int idx = iim[i]; … … 260 244 } 261 245 262 /// Returns if \c item is in, has already been in, or has never been in the heap.263 264 / **265 266 267 268 269 */246 /// \brief Returns if \c item is in, has already been in, or has 247 /// never been in the heap. 248 /// 249 /// This method returns PRE_HEAP if \c item has never been in the 250 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 251 /// otherwise. In the latter case it is possible that \c item will 252 /// get back to the heap again. 253 /// \param i The item. 270 254 state_enum state(const Item &i) const { 271 255 int s = iim[i]; 
src/lemon/radix_heap.h
r1205 r1331 1 1 /* * C++ * 2 * src/lemon/ bin_heap.h  Part of LEMON, a generic C++ optimization library2 * src/lemon/radix_heap.h  Part of LEMON, a generic C++ optimization library 3 3 * 4 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport … … 31 31 /// @{ 32 32 33 /// A Radix Heap implementation.34 35 /// \todo Please document...36 /// 37 /// \sa BinHeap38 /// \sa Dijkstra39 40 class UnderFlowPriorityE xception: public RuntimeError {33 /// \brief Exception thrown by RadixHeap. 34 /// 35 /// This Exception is thrown when a smaller priority 36 /// is inserted into the \e RadixHeap then the last time erased. 37 /// \see RadixHeap 38 /// \author Balazs Dezso 39 40 class UnderFlowPriorityError : public RuntimeError { 41 41 public: 42 42 virtual const char* exceptionName() const { 43 return "lemon::UnderFlowPriorityE xception";43 return "lemon::UnderFlowPriorityError"; 44 44 } 45 45 }; 46 46 47 /// \brief A Radix Heap implementation. 48 /// 49 /// This class implements the \e radix \e heap data structure. A \e heap 50 /// is a data structure for storing items with specified values called \e 51 /// priorities in such a way that finding the item with minimum priority is 52 /// efficient. This heap type can store only items with \e int priority. 53 /// In a heap one can change the priority of an item, add or erase an 54 /// item, but the priority cannot be decreased under the last removed 55 /// item's priority. 56 /// 57 /// \param _Item Type of the items to be stored. 58 /// \param _ItemIntMap A read and writable Item int map, used internally 59 /// to handle the cross references. 60 /// 61 /// \see BinHeap 62 /// \see Dijkstra 63 /// \author Balazs Dezso 64 47 65 template <typename _Item, typename _ItemIntMap> 48 66 class RadixHeap { … … 50 68 public: 51 69 typedef _Item Item; 52 // FIXME: stlben nem ezt hivjak value_type nak, hanem a kovetkezot...53 70 typedef int Prio; 54 71 typedef _ItemIntMap ItemIntMap; 55 72 56 /** 57 * Each Item element have a state associated to it. It may be "in heap", 58 * "pre heap" or "post heap". The later two are indifferent from the 59 * heap's point of view, but may be useful to the user. 60 * 61 * The ItemIntMap _should_ be initialized in such way, that it maps 62 * PRE_HEAP (1) to any element to be put in the heap... 63 */ 64 ///\todo it is used nowhere 65 /// 73 /// \brief Type to represent the items states. 74 /// 75 /// Each Item element have a state associated to it. It may be "in heap", 76 /// "pre heap" or "post heap". The later two are indifferent from the 77 /// heap's point of view, but may be useful to the user. 78 /// 79 /// The ItemIntMap _should_ be initialized in such way, that it maps 80 /// PRE_HEAP (1) to any element to be put in the heap... 66 81 enum state_enum { 67 82 IN_HEAP = 0, … … 92 107 93 108 public: 94 ///\e 109 /// \brief The constructor. 110 /// 111 /// The constructor. 112 /// \param _iim should be given to the constructor, since it is used 113 /// internally to handle the cross references. The value of the map 114 /// should be PRE_HEAP (1) for each element. 95 115 explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) { 96 116 boxes.push_back(RadixBox(0, 1)); … … 98 118 } 99 119 100 ///\e 120 /// \brief The constructor. 121 /// 122 /// The constructor. 123 /// 124 /// \param _iim It should be given to the constructor, since it is used 125 /// internally to handle the cross references. The value of the map 126 /// should be PRE_HEAP (1) for each element. 127 /// 128 /// \param capacity It determines the initial capacity of the heap. 101 129 RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) { 102 130 boxes.push_back(RadixBox(0, 1)); … … 107 135 } 108 136 109 ///\e 137 /// The number of items stored in the heap. 138 /// 139 /// \brief Returns the number of items stored in the heap. 110 140 int size() const { return data.size(); } 111 ///\e 141 /// \brief Checks if the heap stores no items. 142 /// 143 /// Returns \c true if and only if the heap stores no items. 112 144 bool empty() const { return data.empty(); } 113 145 … … 184 216 int findDown(int start, int prio) { 185 217 while (upper(start, prio)) { 186 if (start < 0) throw UnderFlowPriorityE xception();218 if (start < 0) throw UnderFlowPriorityError(); 187 219 } 188 220 return start; … … 208 240 /// first box not empty. 209 241 void moveDown() { 210 // print(); printf("moveDown\n"); fflush(stdout);211 242 int box = findFirst(); 212 243 if (box == 0) return; … … 242 273 public: 243 274 244 ///\e 275 /// \brief Insert an item into the heap with the given heap. 276 /// 277 /// Adds \c i to the heap with priority \c p. 278 /// \param i The item to insert. 279 /// \param p The priority of the item. 245 280 void push(const Item &i, const Prio &p) { 246 fflush(stdout);247 281 int n = data.size(); 248 282 iim.set(i, n); … … 253 287 int box = findDown(boxes.size()  1, p); 254 288 insert(box, n); 255 // printf("Push %d\n", p); 256 //print(); 257 } 258 259 ///\e 289 } 290 291 /// \brief Returns the item with minimum priority. 292 /// 293 /// This method returns the item with minimum priority. 294 /// \pre The heap must be nonempty. 260 295 Item top() const { 261 // print(); printf("top\n"); fflush(stdout);262 296 const_cast<RadixHeap<Item, ItemIntMap>*>(this)>moveDown(); 263 297 return data[boxes[0].first].item; 264 // print(); printf("top_end\n"); fflush(stdout); 265 } 266 267 /// Returns the prio of the top element of the heap. 298 } 299 300 /// \brief Returns the minimum priority. 301 /// 302 /// It returns the minimum priority. 303 /// \pre The heap must be nonempty. 268 304 Prio prio() const { 269 // print(); printf("prio\n"); fflush(stdout);270 305 const_cast<RadixHeap<Item, ItemIntMap>*>(this)>moveDown(); 271 306 return data[boxes[0].first].prio; 272 307 } 273 308 274 ///\e 309 /// \brief Deletes the item with minimum priority. 310 /// 311 /// This method deletes the item with minimum priority. 312 /// \pre The heap must be nonempty. 275 313 void pop() { 276 // print(); printf("pop\n"); fflush(stdout);277 314 moveDown(); 278 315 int index = boxes[0].first; … … 280 317 remove(index); 281 318 relocate_last(index); 282 // printf("Pop \n"); 283 //print(); 284 } 285 286 ///\e 319 } 320 321 /// \brief Deletes \c i from the heap. 322 /// 323 /// This method deletes item \c i from the heap, if \c i was 324 /// already stored in the heap. 325 /// \param i The item to erase. 287 326 void erase(const Item &i) { 288 327 int index = iim[i]; … … 292 331 } 293 332 294 ///\e 333 /// \brief Returns the priority of \c i. 334 /// 335 /// This function returns the priority of item \c i. 336 /// \pre \c i must be in the heap. 337 /// \param i The item. 295 338 Prio operator[](const Item &i) const { 296 339 int idx = iim[i]; … … 298 341 } 299 342 300 ///\e 343 /// \brief \c i gets to the heap with priority \c p independently 344 /// if \c i was already there. 345 /// 346 /// This method calls \ref push(\c i, \c p) if \c i is not stored 347 /// in the heap and sets the priority of \c i to \c p otherwise. 348 /// It may throw an \e UnderFlowPriorityException. 349 /// \param i The item. 350 /// \param p The priority. 301 351 void set(const Item &i, const Prio &p) { 302 352 int idx = iim[i]; … … 313 363 } 314 364 315 ///\e 365 366 /// \brief Decreases the priority of \c i to \c p. 367 /// 368 /// This method decreases the priority of item \c i to \c p. 369 /// \pre \c i must be stored in the heap with priority at least \c p, and 370 /// \c should be greater then the last removed item's priority. 371 /// \param i The item. 372 /// \param p The priority. 316 373 void decrease(const Item &i, const Prio &p) { 317 // print(); printf("decrease\n"); fflush(stdout);318 374 int idx = iim[i]; 319 375 data[idx].prio = p; … … 321 377 } 322 378 323 ///\e 379 /// \brief Increases the priority of \c i to \c p. 380 /// 381 /// This method sets the priority of item \c i to \c p. 382 /// \pre \c i must be stored in the heap with priority at most \c 383 /// p relative to \c Compare. 384 /// \param i The item. 385 /// \param p The priority. 324 386 void increase(const Item &i, const Prio &p) { 325 387 int idx = iim[i]; … … 328 390 } 329 391 330 ///\e 392 /// \brief Returns if \c item is in, has already been in, or has 393 /// never been in the heap. 394 /// 395 /// This method returns PRE_HEAP if \c item has never been in the 396 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 397 /// otherwise. In the latter case it is possible that \c item will 398 /// get back to the heap again. 399 /// \param i The item. 331 400 state_enum state(const Item &i) const { 332 401 int s = iim[i]; … … 335 404 } 336 405 337 // void print() const {338 // for (int i = 0; i < boxes.size(); ++i) {339 // printf("(%d, %d) ", boxes[i].min, boxes[i].size);340 // for (int k = boxes[i].first; k != 1; k = data[k].next) {341 // printf("%d ", data[k].prio);342 // }343 // printf("\n");344 // }345 // fflush(stdout);346 // }347 348 406 }; // class RadixHeap 349 407
Note: See TracChangeset
for help on using the changeset viewer.