72 |
72 |
73 int _highest_active; |
73 int _highest_active; |
74 |
74 |
75 void copy(Item i, Vit p) |
75 void copy(Item i, Vit p) |
76 { |
76 { |
77 _where[*p=i]=p; |
77 _where.set(*p=i,p); |
78 } |
78 } |
79 void copy(Vit s, Vit p) |
79 void copy(Vit s, Vit p) |
80 { |
80 { |
81 if(s!=p) |
81 if(s!=p) |
82 { |
82 { |
83 Item i=*s; |
83 Item i=*s; |
84 *p=i; |
84 *p=i; |
85 _where[i]=p; |
85 _where.set(i,p); |
86 } |
86 } |
87 } |
87 } |
88 void swap(Vit i, Vit j) |
88 void swap(Vit i, Vit j) |
89 { |
89 { |
90 Item ti=*i; |
90 Item ti=*i; |
91 Vit ct = _where[ti]; |
91 Vit ct = _where[ti]; |
92 _where[ti]=_where[*i=*j]; |
92 _where.set(ti,_where[*i=*j]); |
93 _where[*j]=ct; |
93 _where.set(*j,ct); |
94 *j=ti; |
94 *j=ti; |
95 } |
95 } |
96 |
96 |
97 public: |
97 public: |
98 |
98 |
225 |
225 |
226 ///Lift the item returned by highestActive() by one. |
226 ///Lift the item returned by highestActive() by one. |
227 /// |
227 /// |
228 void liftHighestActive() |
228 void liftHighestActive() |
229 { |
229 { |
230 ++_level[*_last_active[_highest_active]]; |
230 Item it = *_last_active[_highest_active]; |
|
231 _level.set(it,_level[it]+1); |
231 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]); |
232 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]); |
232 --_first[++_highest_active]; |
233 --_first[++_highest_active]; |
233 } |
234 } |
234 |
235 |
235 ///Lift the highest active item. |
236 ///Lift the highest active item. |
248 { |
249 { |
249 copy(--_first[l+1],_first[l]); |
250 copy(--_first[l+1],_first[l]); |
250 --_last_active[l]; |
251 --_last_active[l]; |
251 } |
252 } |
252 copy(li,_first[new_level]); |
253 copy(li,_first[new_level]); |
253 _level[li]=new_level; |
254 _level.set(li,new_level); |
254 _highest_active=new_level; |
255 _highest_active=new_level; |
255 } |
256 } |
256 |
257 |
257 ///Lift the highest active item. |
258 ///Lift the highest active item. |
258 |
259 |
272 copy(--_first[l+1],_first[l]); |
273 copy(--_first[l+1],_first[l]); |
273 --_last_active[l]; |
274 --_last_active[l]; |
274 } |
275 } |
275 copy(li,_first[_max_level]); |
276 copy(li,_first[_max_level]); |
276 --_last_active[_max_level]; |
277 --_last_active[_max_level]; |
277 _level[li]=_max_level; |
278 _level.set(li,_max_level); |
278 |
279 |
279 while(_highest_active>=0 && |
280 while(_highest_active>=0 && |
280 _last_active[_highest_active]<_first[_highest_active]) |
281 _last_active[_highest_active]<_first[_highest_active]) |
281 _highest_active--; |
282 _highest_active--; |
282 } |
283 } |
303 |
304 |
304 ///Lifts the active item returned by \c activeOn() member function |
305 ///Lifts the active item returned by \c activeOn() member function |
305 ///by one. |
306 ///by one. |
306 Item liftActiveOn(int level) |
307 Item liftActiveOn(int level) |
307 { |
308 { |
308 ++_level[*_last_active[level]]; |
309 Item it =*_last_active[level]; |
|
310 _level.set(it,_level[it]+1); |
309 swap(_last_active[level]--, --_first[level+1]); |
311 swap(_last_active[level]--, --_first[level+1]); |
310 if (level+1>_highest_active) ++_highest_active; |
312 if (level+1>_highest_active) ++_highest_active; |
311 } |
313 } |
312 |
314 |
313 ///Lifts the active item returned by \c activeOn() member function. |
315 ///Lifts the active item returned by \c activeOn() member function. |
323 { |
325 { |
324 copy(_last_active[l],_first[l]); |
326 copy(_last_active[l],_first[l]); |
325 copy(--_first[l+1], _last_active[l]--); |
327 copy(--_first[l+1], _last_active[l]--); |
326 } |
328 } |
327 copy(ai,_first[new_level]); |
329 copy(ai,_first[new_level]); |
328 _level[ai]=new_level; |
330 _level.set(ai,new_level); |
329 if (new_level>_highest_active) _highest_active=new_level; |
331 if (new_level>_highest_active) _highest_active=new_level; |
330 } |
332 } |
331 |
333 |
332 ///Lifts the active item returned by \c activeOn() member function. |
334 ///Lifts the active item returned by \c activeOn() member function. |
333 |
335 |
343 copy(_last_active[l],_first[l]); |
345 copy(_last_active[l],_first[l]); |
344 copy(--_first[l+1], _last_active[l]--); |
346 copy(--_first[l+1], _last_active[l]--); |
345 } |
347 } |
346 copy(ai,_first[_max_level]); |
348 copy(ai,_first[_max_level]); |
347 --_last_active[_max_level]; |
349 --_last_active[_max_level]; |
348 _level[ai]=_max_level; |
350 _level.set(ai,_max_level); |
349 |
351 |
350 if (_highest_active==level) { |
352 if (_highest_active==level) { |
351 while(_highest_active>=0 && |
353 while(_highest_active>=0 && |
352 _last_active[_highest_active]<_first[_highest_active]) |
354 _last_active[_highest_active]<_first[_highest_active]) |
353 _highest_active--; |
355 _highest_active--; |
374 { |
376 { |
375 copy(_last_active[l],_first[l]); |
377 copy(_last_active[l],_first[l]); |
376 copy(--_first[l+1],_last_active[l]--); |
378 copy(--_first[l+1],_last_active[l]--); |
377 } |
379 } |
378 copy(i,_first[new_level]); |
380 copy(i,_first[new_level]); |
379 _level[i]=new_level; |
381 _level.set(i,new_level); |
380 if(new_level>_highest_active) _highest_active=new_level; |
382 if(new_level>_highest_active) _highest_active=new_level; |
381 } |
383 } |
382 |
384 |
383 ///Move an inactive item to the top but one level (in a dirty way). |
385 ///Move an inactive item to the top but one level (in a dirty way). |
384 |
386 |
385 ///This function moves an inactive item to the top but one level. |
387 ///This function moves an inactive item to the top but one level. |
386 ///It makes the underlying datastructure corrupt, so use is only if |
388 ///It makes the underlying datastructure corrupt, so use is only if |
387 ///you really know what it is for. |
389 ///you really know what it is for. |
388 ///\pre The item is on the top level. |
390 ///\pre The item is on the top level. |
389 void dirtyTopButOne(Item i) { |
391 void dirtyTopButOne(Item i) { |
390 _level[i] = _max_level - 1; |
392 _level.set(i,_max_level - 1); |
391 } |
393 } |
392 |
394 |
393 ///Lift all items on and above a level to the top (and deactivate them). |
395 ///Lift all items on and above a level to the top (and deactivate them). |
394 |
396 |
395 ///This function lifts all items on and above level \c l to \c |
397 ///This function lifts all items on and above level \c l to \c |
397 void liftToTop(int l) |
399 void liftToTop(int l) |
398 { |
400 { |
399 const Vit f=_first[l]; |
401 const Vit f=_first[l]; |
400 const Vit tl=_first[_max_level]; |
402 const Vit tl=_first[_max_level]; |
401 for(Vit i=f;i!=tl;++i) |
403 for(Vit i=f;i!=tl;++i) |
402 _level[*i]=_max_level; |
404 _level.set(*i,_max_level); |
403 for(int i=l;i<=_max_level;i++) |
405 for(int i=l;i<=_max_level;i++) |
404 { |
406 { |
405 _first[i]=f; |
407 _first[i]=f; |
406 _last_active[i]=f-1; |
408 _last_active[i]=f-1; |
407 } |
409 } |
438 _last_active[0]=&_items[0]-1; |
440 _last_active[0]=&_items[0]-1; |
439 Vit n=&_items[0]; |
441 Vit n=&_items[0]; |
440 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) |
442 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) |
441 { |
443 { |
442 *n=i; |
444 *n=i; |
443 _where[i]=n; |
445 _where.set(i,n); |
444 _level[i]=_max_level; |
446 _level.set(i,_max_level); |
445 ++n; |
447 ++n; |
446 } |
448 } |
447 } |
449 } |
448 |
450 |
449 ///Add an item to the current level. |
451 ///Add an item to the current level. |
450 |
452 |
451 void initAddItem(Item i) |
453 void initAddItem(Item i) |
452 { |
454 { |
453 swap(_where[i],_init_num); |
455 swap(_where[i],_init_num); |
454 _level[i]=_init_lev; |
456 _level.set(i,_init_lev); |
455 ++_init_num; |
457 ++_init_num; |
456 } |
458 } |
457 |
459 |
458 ///Start a new level. |
460 ///Start a new level. |
459 |
461 |