Changeset 2348:5ef61c97bf1b in lemon-0.x for lemon/elevator.h
- Timestamp:
- 01/22/07 11:22:14 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3140
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/elevator.h
r2347 r2348 87 87 } 88 88 89 void checkDs() 89 void checkDs() const 90 90 { 91 91 for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i) … … 96 96 check(_first[l]<=w,"GEBASZ: CORRUPT DS"); 97 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 105 check(_highest_active<0 || … … 152 158 { 153 159 swap(_where[i],_last_active[_level[i]]--); 154 _last_active[_level[i]]--;155 160 while(_highest_active>=0 && 156 161 _last_active[_highest_active]<_first[_highest_active]) … … 176 181 177 182 ///Return the number of items on level \c l. 178 int &onLevel(int l)183 int onLevel(int l) const 179 184 { 180 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 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 195 return _last_active[l]-_first[l]+1; … … 234 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 249 void liftHighestActiveTo(int new_level) … … 247 259 copy(li,_first[new_level]); 248 260 _level[li]=new_level; 249 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 328 private: … … 266 340 ///(with level 0). This is done by using \c initAddItem() 267 341 ///and \c initNewLevel(). Finally \c initFinish() must be called. 268 ///The items not liste swill be put on the highest level.342 ///The items not listed will be put on the highest level. 269 343 ///@{ 270 344 271 ///Start sthe initialization process.345 ///Start the initialization process. 272 346 273 347 void initStart() … … 307 381 } 308 382 309 ///Finalize sthe initialization process.383 ///Finalize the initialization process. 310 384 311 385 void initFinish()
Note: See TracChangeset
for help on using the changeset viewer.