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

 1 edited
Legend:
 Unmodified
 Added
 Removed

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.