equal
deleted
inserted
replaced
92 |
92 |
93 bool empty() const { return num_items==0; } |
93 bool empty() const { return num_items==0; } |
94 |
94 |
95 |
95 |
96 void set (Item const it, PrioType const value) { |
96 void set (Item const it, PrioType const value) { |
97 int i=iimap.get(it); |
97 int i=iimap[it]; |
98 if ( i >= 0 && container[i].in ) { |
98 if ( i >= 0 && container[i].in ) { |
99 if ( comp(value, container[i].prio) ) decrease(it, value); |
99 if ( comp(value, container[i].prio) ) decrease(it, value); |
100 if ( comp(container[i].prio, value) ) increase(it, value); |
100 if ( comp(container[i].prio, value) ) increase(it, value); |
101 } else push(it, value); |
101 } else push(it, value); |
102 } |
102 } |
103 |
103 |
104 |
104 |
105 void push (Item const it, PrioType const value) { |
105 void push (Item const it, PrioType const value) { |
106 int i=iimap.get(it); |
106 int i=iimap[it]; |
107 if ( i < 0 ) { |
107 if ( i < 0 ) { |
108 int s=container.size(); |
108 int s=container.size(); |
109 iimap.set( it, s ); |
109 iimap.set( it, s ); |
110 store st; |
110 store st; |
111 st.name=it; |
111 st.name=it; |
143 } |
143 } |
144 |
144 |
145 |
145 |
146 |
146 |
147 |
147 |
148 PrioType& operator[](const Item& it) const { |
148 PrioType& operator[](const Item& it) { |
149 return container[iimap.get(it)].prio; |
149 return container[iimap[it]].prio; |
150 } |
150 } |
151 |
151 |
152 const PrioType& operator[](const Item& it) const { |
152 const PrioType& operator[](const Item& it) const { |
153 return container[iimap.get(it)].prio; |
153 return container[iimap[it]].prio; |
154 } |
154 } |
155 |
155 |
156 const PrioType get(const Item& it) const { |
156 // const PrioType get(const Item& it) const { |
157 return container[iimap.get(it)].prio; |
157 // return container[iimap[it]].prio; |
158 } |
158 // } |
159 |
|
160 |
|
161 |
159 |
162 void pop() { |
160 void pop() { |
163 /*The first case is that there are only one root.*/ |
161 /*The first case is that there are only one root.*/ |
164 if ( container[minimum].left_neighbor==minimum ) { |
162 if ( container[minimum].left_neighbor==minimum ) { |
165 container[minimum].in=false; |
163 container[minimum].in=false; |
190 --num_items; |
188 --num_items; |
191 } |
189 } |
192 |
190 |
193 |
191 |
194 void erase (const Item& it) { |
192 void erase (const Item& it) { |
195 int i=iimap.get(it); |
193 int i=iimap[it]; |
196 |
194 |
197 if ( i >= 0 && container[i].in ) { |
195 if ( i >= 0 && container[i].in ) { |
198 if ( container[i].parent!=-1 ) { |
196 if ( container[i].parent!=-1 ) { |
199 int p=container[i].parent; |
197 int p=container[i].parent; |
200 cut(i,p); |
198 cut(i,p); |
205 } |
203 } |
206 } |
204 } |
207 |
205 |
208 |
206 |
209 void decrease (Item it, PrioType const value) { |
207 void decrease (Item it, PrioType const value) { |
210 int i=iimap.get(it); |
208 int i=iimap[it]; |
211 container[i].prio=value; |
209 container[i].prio=value; |
212 int p=container[i].parent; |
210 int p=container[i].parent; |
213 |
211 |
214 if ( p!=-1 && comp(value, container[p].prio) ) { |
212 if ( p!=-1 && comp(value, container[p].prio) ) { |
215 cut(i,p); |
213 cut(i,p); |
224 push(it, value); |
222 push(it, value); |
225 } |
223 } |
226 |
224 |
227 |
225 |
228 state_enum state(const Item &it) const { |
226 state_enum state(const Item &it) const { |
229 int i=iimap.get(it); |
227 int i=iimap[it]; |
230 if( i>=0 ) { |
228 if( i>=0 ) { |
231 if ( container[i].in ) i=0; |
229 if ( container[i].in ) i=0; |
232 else i=-2; |
230 else i=-2; |
233 } |
231 } |
234 return state_enum(i); |
232 return state_enum(i); |