84 _where[ti]=_where[*i=*j]; |
84 _where[ti]=_where[*i=*j]; |
85 _where[*j]=ct; |
85 _where[*j]=ct; |
86 *j=ti; |
86 *j=ti; |
87 } |
87 } |
88 |
88 |
89 void checkDs() |
89 void checkDs() const |
90 { |
90 { |
91 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) |
91 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) |
92 { |
92 { |
93 Vit w=_where[i]; |
93 Vit w=_where[i]; |
94 int l=_level[i]; |
94 int l=_level[i]; |
95 check(*w==i,"GEBASZ: CORRUPT DS"); |
95 check(*w==i,"GEBASZ: CORRUPT DS"); |
96 check(_first[l]<=w,"GEBASZ: CORRUPT DS"); |
96 check(_first[l]<=w,"GEBASZ: CORRUPT DS"); |
97 check(_first[l+1]>w,"GEBASZ: CORRUPT DS"); |
97 check(_first[l+1]>w,"GEBASZ: CORRUPT DS"); |
|
98 } |
|
99 for(int l=0;l<=_max_level;++l) |
|
100 { |
|
101 check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS"); |
|
102 check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS"); |
|
103 check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS"); |
98 } |
104 } |
99 check(_highest_active<0 || |
105 check(_highest_active<0 || |
100 _first[_highest_active]<=_last_active[_highest_active], |
106 _first[_highest_active]<=_last_active[_highest_active], |
101 "GEBASZ: CORRUPT DS"); |
107 "GEBASZ: CORRUPT DS"); |
102 } |
108 } |
149 |
155 |
150 ///Deactivate item \c i. |
156 ///Deactivate item \c i. |
151 void deactivate(Item i) |
157 void deactivate(Item i) |
152 { |
158 { |
153 swap(_where[i],_last_active[_level[i]]--); |
159 swap(_where[i],_last_active[_level[i]]--); |
154 _last_active[_level[i]]--; |
|
155 while(_highest_active>=0 && |
160 while(_highest_active>=0 && |
156 _last_active[_highest_active]<_first[_highest_active]) |
161 _last_active[_highest_active]<_first[_highest_active]) |
157 _highest_active--; |
162 _highest_active--; |
158 } |
163 } |
159 |
164 |
173 { |
178 { |
174 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID; |
179 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID; |
175 } |
180 } |
176 |
181 |
177 ///Return the number of items on level \c l. |
182 ///Return the number of items on level \c l. |
178 int &onLevel(int l) |
183 int onLevel(int l) const |
179 { |
184 { |
180 return _first[l+1]-_first[l]; |
185 return _first[l+1]-_first[l]; |
181 } |
186 } |
|
187 ///Return the number of items above level \c l. |
|
188 int aboveLevel(int l) const |
|
189 { |
|
190 return _first[_max_level+1]-_first[l+1]; |
|
191 } |
182 ///Return the number of active items on level \c l. |
192 ///Return the number of active items on level \c l. |
183 int &activesOnLevel(int l) |
193 int activesOnLevel(int l) const |
184 { |
194 { |
185 return _last_active[l]-_first[l]+1; |
195 return _last_active[l]-_first[l]+1; |
186 } |
196 } |
187 ///Return the maximum allowed level. |
197 ///Return the maximum allowed level. |
188 int maxLevel() const |
198 int maxLevel() const |
231 |
241 |
232 ///Lift the highest active item. |
242 ///Lift the highest active item. |
233 |
243 |
234 ///Lift the item returned by highestActive() to level \c new_level. |
244 ///Lift the item returned by highestActive() to level \c new_level. |
235 /// |
245 /// |
|
246 ///\warning \c new_level must be strictly higher |
|
247 ///than the current level. |
236 /// |
248 /// |
237 void liftHighestActiveTo(int new_level) |
249 void liftHighestActiveTo(int new_level) |
238 { |
250 { |
239 const Item li = *_last_active[_highest_active]; |
251 const Item li = *_last_active[_highest_active]; |
240 |
252 |
244 copy(--_first[l+1],_first[l]); |
256 copy(--_first[l+1],_first[l]); |
245 --_last_active[l]; |
257 --_last_active[l]; |
246 } |
258 } |
247 copy(li,_first[new_level]); |
259 copy(li,_first[new_level]); |
248 _level[li]=new_level; |
260 _level[li]=new_level; |
249 _highest_active=new_level; |
261 _highest_active=new_level; |
250 } |
262 } |
251 |
263 |
252 ///@} |
264 ///@} |
|
265 |
|
266 ///Lift an active item to a higher level. |
|
267 |
|
268 ///Lift an active item to a higher level. |
|
269 ///\params i The item to be lifted. It must be active. |
|
270 ///\params new_level The new level of \c i. It must be strictly higher |
|
271 ///than the current level. |
|
272 /// |
|
273 void liftTo(Item i, int new_level) |
|
274 { |
|
275 const int lo = _level[i]; |
|
276 const Vit w = _where[i]; |
|
277 |
|
278 copy(_last_active[lo],w); |
|
279 copy(--_first[lo+1],_last_active[lo]--); |
|
280 for(int l=lo+1;l<new_level;l++) |
|
281 { |
|
282 copy(_last_active[l],_first[l]); |
|
283 copy(--_first[l+1],_last_active[l]--); |
|
284 } |
|
285 copy(i,_first[new_level]); |
|
286 _level[i]=new_level; |
|
287 if(new_level>_highest_active) _highest_active=new_level; |
|
288 } |
|
289 |
|
290 // void liftToTop(int l) |
|
291 // { |
|
292 // const Vit f=_first[l]; |
|
293 // for(int i=l;i<=_max_level;i++) |
|
294 // { |
|
295 // _first[i]=f; |
|
296 // _last_active[i]=f-1; |
|
297 // } |
|
298 // for(Vit i=f;i!=_items.end();++i) |
|
299 // _level[*i]=_max_level; |
|
300 // for(_highest_active=l-1; |
|
301 // _highest_active>=0 && |
|
302 // _last_active[_highest_active]<_first[_highest_active]; |
|
303 // _highest_active--) ; |
|
304 // } |
|
305 |
|
306 ///Lift all nodes on and above a level to the top (and deactivate them). |
|
307 |
|
308 ///This function lifts all nodes on and above level \c l to \c maxLevel(), |
|
309 ///and |
|
310 ///also deactivates them. |
|
311 void liftToTop(int l) |
|
312 { |
|
313 const Vit f=_first[l]; |
|
314 const Vit tl=_first[_max_level]; |
|
315 for(Vit i=f;i!=tl;++i) |
|
316 _level[*i]=_max_level; |
|
317 for(int i=l;i<=_max_level;i++) |
|
318 { |
|
319 _first[i]=f; |
|
320 _last_active[i]=f-1; |
|
321 } |
|
322 for(_highest_active=l-1; |
|
323 _highest_active>=0 && |
|
324 _last_active[_highest_active]<_first[_highest_active]; |
|
325 _highest_active--) ; |
|
326 } |
253 |
327 |
254 private: |
328 private: |
255 int _init_lev; |
329 int _init_lev; |
256 Vit _init_num; |
330 Vit _init_num; |
257 |
331 |
263 ///This initializatios is started with calling \c initStart(). |
337 ///This initializatios is started with calling \c initStart(). |
264 ///Then the |
338 ///Then the |
265 ///items should be listed levels by levels statring with the lowest one |
339 ///items should be listed levels by levels statring with the lowest one |
266 ///(with level 0). This is done by using \c initAddItem() |
340 ///(with level 0). This is done by using \c initAddItem() |
267 ///and \c initNewLevel(). Finally \c initFinish() must be called. |
341 ///and \c initNewLevel(). Finally \c initFinish() must be called. |
268 ///The items not listes will be put on the highest level. |
342 ///The items not listed will be put on the highest level. |
269 ///@{ |
343 ///@{ |
270 |
344 |
271 ///Starts the initialization process. |
345 ///Start the initialization process. |
272 |
346 |
273 void initStart() |
347 void initStart() |
274 { |
348 { |
275 _init_lev=0; |
349 _init_lev=0; |
276 _init_num=_items.begin(); |
350 _init_num=_items.begin(); |