Changeset 161:743fa50c442e in lemon-0.x for src/work
- Timestamp:
- 03/09/04 19:42:14 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@228
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/fib_heap.h
r159 r161 16 16 *bool empty() : true iff size()=0 17 17 * 18 *void push(Item, Prio) : pushes Item to the heap with priority Prio. If 19 * Item was already in the heap, it calls decrease(Item, Prio) 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. 20 23 * 21 24 *Item top() : returns the Item with least Prio … … 29 32 *void erase(Item) : deletes Item from the heap if it was already there 30 33 * 31 *void decrease(Item, P) : If Item was not in the heap, then it calls 32 * push(Item, P). If item is in the heap with Prio more than P 33 * then sets its Prio to P. 34 * 35 *void increase(Item, P) : If Item was not in the heap, then it calls 36 * push(Item, P). If item is in the heap with Prio less than P 37 * then sets its Prio to P. 34 *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap 35 * with prio at least P. 36 * 37 *void increase(Item, P) : sets prio of Item to P. 38 38 * 39 39 * … … 81 81 82 82 83 bool empty() const { return blank; } 84 85 86 void push (Item const it, PrioType const value) 87 { 88 89 int i=iimap.get(it); 90 91 if ( i >= 0 && container[i].in ) decrease(it, value); 92 else { 93 if ( i < 0 ) { 94 int s=container.size(); 95 iimap.set( it, s ); 96 store st; 97 st.name=it; 98 container.push_back(st); 99 i=s; 100 } 101 102 if ( !blank ) { 103 container[container[minimum].right_neighbor].left_neighbor=i; 104 container[i].right_neighbor=container[minimum].right_neighbor; 105 container[minimum].right_neighbor=i; 106 container[i].left_neighbor=minimum; 107 if ( !comp( container[minimum].prio, value) ) minimum=i; 108 109 110 111 } else { 112 container[i].right_neighbor=container[i].left_neighbor=i; 113 minimum=i; 114 blank=false; 115 } 116 container[i].prio=value; 117 } 118 } 83 bool empty() const { return blank; } 84 85 86 void set (Item const it, PrioType const value) { 87 int i=iimap.get(it); 88 if ( i >= 0 && container[i].in ) { 89 if ( !comp(container[i].prio, value) ) decrease(it, value); 90 if ( comp(container[i].prio, value) ) increase(it, value); 91 } else push(it, value); 92 } 93 94 95 void push (Item const it, PrioType const value) { 96 int i=iimap.get(it); 97 if ( i < 0 ) { 98 int s=container.size(); 99 iimap.set( it, s ); 100 store st; 101 st.name=it; 102 container.push_back(st); 103 i=s; 104 } 105 106 if ( !blank ) { 107 container[container[minimum].right_neighbor].left_neighbor=i; 108 container[i].right_neighbor=container[minimum].right_neighbor; 109 container[minimum].right_neighbor=i; 110 container[i].left_neighbor=minimum; 111 if ( !comp( container[minimum].prio, value) ) minimum=i; 112 113 } else { 114 container[i].right_neighbor=container[i].left_neighbor=i; 115 minimum=i; 116 blank=false; 117 } 118 container[i].prio=value; 119 } 120 119 121 120 122 … … 200 202 201 203 202 void decrease (Item it, PrioType const value) { 203 int i=iimap.get(it); 204 if ( i >= 0 && container[i].in ) { 205 206 if ( comp(value, container[i].prio) ) { 207 container[i].prio=value; 208 209 if ( container[i].parent!=-1 ) { 210 int p=container[i].parent; 211 212 if ( !comp(container[p].prio, value) ) { 213 cut(i,p); 214 cascade(p); 215 if ( comp(value, container[minimum].prio) ) minimum=i; 216 } 217 } 218 } 219 } else push(it, value); 220 } 204 void decrease (Item it, PrioType const value) { 205 int i=iimap.get(it); 206 container[i].prio=value; 207 int p=container[i].parent; 208 209 if ( p!=-1 && comp(value, container[p].prio) ) { 210 cut(i,p); 211 cascade(p); 212 if ( comp(value, container[minimum].prio) ) minimum=i; 213 } 214 } 221 215 222 216 223 217 void increase (Item it, PrioType const value) { 224 int i=iimap.get(it); 225 226 if ( i >= 0 && container[i].in ) { 227 if ( comp(container[i].prio, value) ) { 228 erase(it); 229 push(it, value); 230 } 231 } else push(it, value); 218 erase(it); 219 push(it, value); 232 220 } 233 221
Note: See TracChangeset
for help on using the changeset viewer.