COIN-OR::LEMON - Graph Library

Changeset 2348:5ef61c97bf1b in lemon-0.x


Ignore:
Timestamp:
01/22/07 11:22:14 (17 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3140
Message:
  • Some bugfixes
  • Better doc
  • liftToTop(), liftTo() added
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/elevator.h

    r2347 r2348  
    8787    }
    8888   
    89     void checkDs()
     89    void checkDs() const
    9090    {
    9191      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
     
    9696          check(_first[l]<=w,"GEBASZ: CORRUPT DS");
    9797          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");
    98104        }
    99105      check(_highest_active<0 ||
     
    152158    {
    153159      swap(_where[i],_last_active[_level[i]]--);
    154       _last_active[_level[i]]--;
    155160      while(_highest_active>=0 &&
    156161            _last_active[_highest_active]<_first[_highest_active])
     
    176181
    177182    ///Return the number of items on level \c l.
    178     int &onLevel(int l)
     183    int onLevel(int l) const
    179184    {
    180185      return _first[l+1]-_first[l];
    181186    }
     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    }
    182192    ///Return the number of active items on level \c l.
    183     int &activesOnLevel(int l)
     193    int activesOnLevel(int l) const
    184194    {
    185195      return _last_active[l]-_first[l]+1;
     
    234244    ///Lift the item returned by highestActive() to level \c new_level.
    235245    ///
     246    ///\warning \c new_level must be strictly higher
     247    ///than the current level.
    236248    ///
    237249    void liftHighestActiveTo(int new_level)
     
    247259      copy(li,_first[new_level]);
    248260      _level[li]=new_level;
    249           _highest_active=new_level;
     261      _highest_active=new_level;
    250262    }
    251263   
    252264    ///@}
     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    }
    253327   
    254328  private:
     
    266340    ///(with level 0). This is done by using \c initAddItem()
    267341    ///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.
    269343    ///@{
    270344
    271     ///Starts the initialization process.
     345    ///Start the initialization process.
    272346
    273347    void initStart()
     
    307381    }
    308382
    309     ///Finalizes the initialization process.
     383    ///Finalize the initialization process.
    310384
    311385    void initFinish()
Note: See TracChangeset for help on using the changeset viewer.