Changeset 1331:7e93d3f0406d in lemon0.x for src/lemon/bin_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/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];
Note: See TracChangeset
for help on using the changeset viewer.