Changeset 2263:9273fe7d850c in lemon-0.x for lemon/bin_heap.h
- Timestamp:
- 10/26/06 16:20:17 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3021
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bin_heap.h
r2258 r2263 40 40 ///one can change the priority of an item, add or erase an item, etc. 41 41 /// 42 ///\param Item Type of the items to be stored.43 42 ///\param Prio Type of the priority of the items. 44 43 ///\param ItemIntMap A read and writable Item int map, used internally … … 49 48 ///\sa FibHeap 50 49 ///\sa Dijkstra 51 template <typename Item, typenamePrio, typename ItemIntMap,50 template <typename Prio, typename ItemIntMap, 52 51 typename Compare = std::less<Prio> > 53 52 class BinHeap { 54 53 55 54 public: 56 typedef ItemItemType;55 typedef typename ItemIntMap::Key ItemType; 57 56 typedef Prio PrioType; 58 57 typedef std::pair<ItemType,PrioType> PairType; … … 162 161 /// \param i The item to insert. 163 162 /// \param p The priority of the item. 164 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }163 void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); } 165 164 166 165 /// \brief Returns the item with minimum priority relative to \c Compare. … … 169 168 /// Compare. 170 169 /// \pre The heap must be nonempty. 171 Item top() const {170 ItemType top() const { 172 171 return data[0].first; 173 172 } … … 195 194 /// already stored in the heap. 196 195 /// \param i The item to erase. 197 void erase(const Item &i) {196 void erase(const ItemType &i) { 198 197 rmidx(iim[i]); 199 198 } … … 205 204 /// \pre \c i must be in the heap. 206 205 /// \param i The item. 207 Prio operator[](const Item &i) const {206 Prio operator[](const ItemType &i) const { 208 207 int idx = iim[i]; 209 208 return data[idx].second; … … 217 216 /// \param i The item. 218 217 /// \param p The priority. 219 void set(const Item &i, const Prio &p) {218 void set(const ItemType &i, const Prio &p) { 220 219 int idx = iim[i]; 221 220 if( idx < 0 ) { … … 237 236 /// \param i The item. 238 237 /// \param p The priority. 239 void decrease(const Item &i, const Prio &p) {238 void decrease(const ItemType &i, const Prio &p) { 240 239 int idx = iim[i]; 241 240 bubble_up(idx, PairType(i,p)); … … 249 248 /// \param i The item. 250 249 /// \param p The priority. 251 void increase(const Item &i, const Prio &p) {250 void increase(const ItemType &i, const Prio &p) { 252 251 int idx = iim[i]; 253 252 bubble_down(idx, PairType(i,p), data.size()); … … 262 261 /// get back to the heap again. 263 262 /// \param i The item. 264 state_enum state(const Item &i) const {263 state_enum state(const ItemType &i) const { 265 264 int s = iim[i]; 266 265 if( s>=0 ) … … 276 275 /// \param i The item. 277 276 /// \param st The state. It should not be \c IN_HEAP. 278 void state(const Item & i, state_enum st) {277 void state(const ItemType& i, state_enum st) { 279 278 switch (st) { 280 279 case POST_HEAP: … … 293 292 294 293 295 template <typename K, typenameV, typename M, typename C>296 int BinHeap< K,V,M,C>::bubble_up(int hole, PairType p) {294 template <typename V, typename M, typename C> 295 int BinHeap<V,M,C>::bubble_up(int hole, PairType p) { 297 296 int par = parent(hole); 298 297 while( hole>0 && less(p,data[par]) ) { … … 305 304 } 306 305 307 template <typename K, typenameV, typename M, typename C>308 int BinHeap< K,V,M,C>::bubble_down(int hole, PairType p, int length) {306 template <typename V, typename M, typename C> 307 int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) { 309 308 int child = second_child(hole); 310 309 while(child < length) {
Note: See TracChangeset
for help on using the changeset viewer.