Changeset 373:259ea2d741a2 in lemon0.x for src/include/fib_heap.h
 Timestamp:
 04/22/04 16:50:24 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@503
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/include/fib_heap.h
r255 r373 1 1 // * C++ * 2 /* 3 *template <typename Item, 4 * typename Prio, 5 * typename ItemIntMap, 6 * typename Compare = std::less<Prio> > 7 * 8 *constructors: 9 * 10 *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare) 11 * 12 *Member functions: 13 * 14 *int size() : returns the number of elements in the heap 15 * 16 *bool empty() : true iff size()=0 17 * 18 *void set(Item, Prio) : calls push(Item, Prio) if Item is not 19 * in the heap, and calls decrease/increase(Item, Prio) otherwise 20 * 21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item 22 * mustn't be in the heap. 23 * 24 *Item top() : returns the Item with least Prio. 25 * Must be called only if heap is nonempty. 26 * 27 *Prio prio() : returns the least Prio 28 * Must be called only if heap is nonempty. 29 * 30 *Prio get(Item) : returns Prio of Item 31 * Must be called only if Item is in heap. 32 * 33 *void pop() : deletes the Item with least Prio 34 * 35 *void erase(Item) : deletes Item from the heap if it was already there 36 * 37 *void decrease(Item, P) : decreases prio of Item to P. 38 * Item must be in the heap with prio at least P. 39 * 40 *void increase(Item, P) : sets prio of Item to P. 41 * 42 *state_enum state(Item) : returns PRE_HEAP if Item has not been in the 43 * heap until now, IN_HEAP if it is in the heap at the moment, and 44 * POST_HEAP otherwise. In the latter case it is possible that Item 45 * will get back to the heap again. 46 * 47 *In Fibonacci heaps, increase and erase are not efficient, in case of 48 *many calls to these operations, it is better to use bin_heap. 49 */ 50 51 #ifndef FIB_HEAP_H 52 #define FIB_HEAP_H 2 3 #ifndef HUGO_FIB_HEAP_H 4 #define HUGO_FIB_HEAP_H 53 5 54 6 ///\file … … 61 13 namespace hugo { 62 14 63 /// A Fibonacci Heap implementation. 64 template <typename Item, typename Prio, typename ItemIntMap, 15 /// An implementation of the Fibonacci Heap. 16 17 /** 18 This class implements the \e Fibonacci \e heap data structure. A \e 19 heap is a data structure for storing items with specified priorities, 20 such that finding the item with minimum priority is efficient. In a 21 heap one can change the priority of an item, and to add or erase an 22 item. 23 24 The methods \ref increase and \ref erase are not efficient, in 25 case of many calls to these operations, it is better to use 26 a binary heap. 27 28 /param Item The type of the items to be stored. 29 /param Prio The type of the priority of the items. 30 /param ItemIntMap A read and writable Item int map, for the usage of 31 the heap. 32 /param Compare A class for the comparison of the priorities. The 33 default is \c std::less<Prio>. 34 35 */ 36 37 #ifdef DOXYGEN 38 template <typename Item, 39 typename Prio, 40 typename ItemIntMap, 41 typename Compare> 42 #else 43 template <typename Item, 44 typename Prio, 45 typename ItemIntMap, 65 46 typename Compare = std::less<Prio> > 47 #endif 66 48 class FibHeap { 67 49 public: 68 50 typedef Prio PrioType; 69 51 52 private: 70 53 class store; 71 54 … … 75 58 Compare comp; 76 59 int num_items; 77 60 78 61 ///\todo It is use nowhere 79 62 ///\todo It doesn't conform to the naming conventions. … … 87 70 public : 88 71 89 FibHeap(ItemIntMap &_iimap) : minimum( ), iimap(_iimap), num_items() {}90 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum( ),72 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 73 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 91 74 iimap(_iimap), comp(_comp), num_items() {} 92 75 93 94 int size() const { 95 return num_items; 96 } 97 98 76 ///The number of items stored in the heap. 77 78 /** 79 Returns the number of items stored in the heap. 80 */ 81 int size() const { return num_items; } 82 83 ///Checks if the heap stores no items. 84 85 /** 86 Returns true iff the heap stores no items. 87 */ 99 88 bool empty() const { return num_items==0; } 100 89 90 ///Item \c item gets to the heap with priority \c value independently if \c item was already there. 91 92 /** 93 This method calls \ref push(item, value) if \c item is not 94 stored in the heap, and it calls \ref decrease(it, \c value) or 95 \ref increase(it, \c value) otherwise. 96 */ 97 void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van 98 99 ///Adds \c item to the heap with priority \c value. 100 101 /** 102 Adds \c item to the heap with priority \c value. 103 \pre \c item must not be stored in the heap. 104 */ 105 void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/ 106 107 108 ///Returns the item having the minimum priority w.r.t. Compare. 109 110 /** 111 This method returns the item having the minimum priority w.r.t. Compare. 112 \pre The heap must be nonempty. 113 */ 114 Item top() const { return container[minimum].name; } 115 116 117 ///Returns the minimum priority w.r.t. Compare. 118 119 /** 120 It returns the minimum priority w.r.t. Compare. 121 \pre The heap must be nonempty. 122 */ 123 PrioType prio() const { return container[minimum].prio; } 124 125 126 ///Returns the priority of \c item. 127 128 /** 129 It returns the priority of \c item. 130 \pre \c item must be in the heap. 131 */ 132 PrioType& operator[](const Item& it) { return container[iimap[it]].prio; } 133 134 ///Returns the priority of \c item. 135 136 /** 137 It returns the priority of \c item. 138 \pre \c item must be in the heap. 139 */ 140 const PrioType& operator[](const Item& it) const { 141 return container[iimap[it]].prio; 142 } 143 144 145 ///Deletes the item with minimum priority w.r.t. Compare. 146 147 /** 148 This method deletes the item with minimum priority w.r.t. 149 Compare from the heap. 150 \pre The heap must be nonempty. 151 */ 152 void pop(); 153 154 ///Deletes \c item from the heap. 155 156 /** 157 This method deletes \c item from the heap, if \c item was already 158 stored in the heap. It is quite inefficient in Fibonacci heaps. 159 */ 160 void erase (const Item& item); /*vigyazat: az implementacioban it van*/ 161 162 ///Decreases the priority of \c item to \c value. 163 164 /** 165 This method decreases the priority of \c item to \c value. 166 \pre \c item must be stored in the heap with priority at least \c 167 value w.r.t. Compare. 168 */ 169 void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/ 170 171 172 ///Increases the priority of \c item to \c value. 173 174 /** 175 This method sets the priority of \c item to \c value. Though 176 there is no precondition on the priority of \c item, this 177 method should be used only if one wants to \e increase 178 (w.r.t. Compare) the priority of \c item, because this 179 method is inefficient. 180 */ 181 void increase (Item it, PrioType const value) { 182 erase(it); 183 push(it, value); 184 } 185 186 187 ///Tells if \c item is in, was in, or has not been in the heap. 188 189 /** 190 This method returns PRE_HEAP if \c item has never been in the 191 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 192 otherwise. In the latter case it is possible that \c item will 193 get back to the heap again. 194 */ 195 state_enum state(const Item &it); /*vigyazat: az implementacioban it van*/ 196 197 198 199 // ********************************************************************** 200 // IMPLEMENTATIONS 201 // ********************************************************************** 202 101 203 102 204 void set (Item const it, PrioType const value) { … … 139 241 } 140 242 141 142 Item top() const {143 return container[minimum].name;144 }145 146 147 PrioType prio() const {148 return container[minimum].prio;149 }150 151 152 153 154 PrioType& operator[](const Item& it) {155 return container[iimap[it]].prio;156 }157 158 const PrioType& operator[](const Item& it) const {159 return container[iimap[it]].prio;160 }161 162 // const PrioType get(const Item& it) const {163 // return container[iimap[it]].prio;164 // }165 243 166 244 void pop() { … … 224 302 225 303 226 void increase (Item it, PrioType const value) {227 erase(it);228 push(it, value);229 }230 231 232 304 state_enum state(const Item &it) const { 233 305 int i=iimap[it];
Note: See TracChangeset
for help on using the changeset viewer.