1.1 --- a/lemon/elevator.h	Fri Jan 19 17:27:22 2007 +0000
     1.2 +++ b/lemon/elevator.h	Mon Jan 22 10:22:14 2007 +0000
     1.3 @@ -86,7 +86,7 @@
     1.4        *j=ti;
     1.5      }
     1.6      
     1.7 -    void checkDs() 
     1.8 +    void checkDs() const
     1.9      {
    1.10        for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
    1.11  	{
    1.12 @@ -96,6 +96,12 @@
    1.13  	  check(_first[l]<=w,"GEBASZ: CORRUPT DS");
    1.14  	  check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
    1.15  	}
    1.16 +      for(int l=0;l<=_max_level;++l) 
    1.17 +	{
    1.18 +	  check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS");
    1.19 +	  check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS");
    1.20 +	  check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS");
    1.21 +	}
    1.22        check(_highest_active<0 ||
    1.23  	    _first[_highest_active]<=_last_active[_highest_active],
    1.24  	    "GEBASZ: CORRUPT DS");
    1.25 @@ -151,7 +157,6 @@
    1.26      void deactivate(Item i)  
    1.27      {
    1.28        swap(_where[i],_last_active[_level[i]]--);
    1.29 -      _last_active[_level[i]]--;
    1.30        while(_highest_active>=0 &&
    1.31  	    _last_active[_highest_active]<_first[_highest_active])
    1.32  	_highest_active--;
    1.33 @@ -175,12 +180,17 @@
    1.34      }
    1.35  
    1.36      ///Return the number of items on level \c l.
    1.37 -    int &onLevel(int l)
    1.38 +    int onLevel(int l) const
    1.39      {
    1.40        return _first[l+1]-_first[l];
    1.41      }
    1.42 +    ///Return the number of items above level \c l.
    1.43 +    int aboveLevel(int l) const
    1.44 +    {
    1.45 +      return _first[_max_level+1]-_first[l+1];
    1.46 +    }
    1.47      ///Return the number of active items on level \c l.
    1.48 -    int &activesOnLevel(int l)
    1.49 +    int activesOnLevel(int l) const
    1.50      {
    1.51        return _last_active[l]-_first[l]+1;
    1.52      }
    1.53 @@ -233,6 +243,8 @@
    1.54  
    1.55      ///Lift the item returned by highestActive() to level \c new_level.
    1.56      ///
    1.57 +    ///\warning \c new_level must be strictly higher
    1.58 +    ///than the current level.
    1.59      ///
    1.60      void liftHighestActiveTo(int new_level) 
    1.61      {
    1.62 @@ -246,11 +258,73 @@
    1.63  	}
    1.64        copy(li,_first[new_level]);
    1.65        _level[li]=new_level;
    1.66 -	  _highest_active=new_level;
    1.67 +      _highest_active=new_level;
    1.68      }
    1.69      
    1.70      ///@}
    1.71      
    1.72 +    ///Lift an active item to a higher level.
    1.73 +
    1.74 +    ///Lift an active item to a higher level.
    1.75 +    ///\params i The item to be lifted. It must be active.
    1.76 +    ///\params new_level The new level of \c i. It must be strictly higher
    1.77 +    ///than the current level.
    1.78 +    ///
    1.79 +    void liftTo(Item i, int new_level) 
    1.80 +    {
    1.81 +      const int lo = _level[i];
    1.82 +      const Vit w = _where[i];
    1.83 +
    1.84 +      copy(_last_active[lo],w);
    1.85 +      copy(--_first[lo+1],_last_active[lo]--);
    1.86 +      for(int l=lo+1;l<new_level;l++)
    1.87 +	{
    1.88 +	  copy(_last_active[l],_first[l]);
    1.89 +	  copy(--_first[l+1],_last_active[l]--);
    1.90 +	}
    1.91 +      copy(i,_first[new_level]);
    1.92 +      _level[i]=new_level;
    1.93 +      if(new_level>_highest_active) _highest_active=new_level;
    1.94 +    }
    1.95 +
    1.96 +//     void liftToTop(int l) 
    1.97 +//     {
    1.98 +//       const Vit f=_first[l];
    1.99 +//       for(int i=l;i<=_max_level;i++)
   1.100 +// 	{
   1.101 +// 	  _first[i]=f;
   1.102 +// 	  _last_active[i]=f-1;
   1.103 +// 	}
   1.104 +//       for(Vit i=f;i!=_items.end();++i)
   1.105 +// 	_level[*i]=_max_level;
   1.106 +//       for(_highest_active=l-1;
   1.107 +// 	  _highest_active>=0 &&
   1.108 +// 	    _last_active[_highest_active]<_first[_highest_active];
   1.109 +// 	  _highest_active--) ;
   1.110 +//     }
   1.111 +    
   1.112 +    ///Lift all nodes on and above a level to the top (and deactivate them).
   1.113 +
   1.114 +    ///This function lifts all nodes on and above level \c l to \c maxLevel(),
   1.115 +    ///and
   1.116 +    ///also deactivates them.
   1.117 +    void liftToTop(int l) 
   1.118 +    {
   1.119 +      const Vit f=_first[l];
   1.120 +      const Vit tl=_first[_max_level];
   1.121 +      for(Vit i=f;i!=tl;++i)
   1.122 +	_level[*i]=_max_level;
   1.123 +      for(int i=l;i<=_max_level;i++)
   1.124 +	{
   1.125 +	  _first[i]=f;
   1.126 +	  _last_active[i]=f-1;
   1.127 +	}
   1.128 +      for(_highest_active=l-1;
   1.129 +	  _highest_active>=0 &&
   1.130 +	    _last_active[_highest_active]<_first[_highest_active];
   1.131 +	  _highest_active--) ;
   1.132 +    }
   1.133 +    
   1.134    private:
   1.135      int _init_lev;
   1.136      Vit _init_num;
   1.137 @@ -265,10 +339,10 @@
   1.138      ///items should be listed levels by levels statring with the lowest one
   1.139      ///(with level 0). This is done by using \c initAddItem()
   1.140      ///and \c initNewLevel(). Finally \c initFinish() must be called.
   1.141 -    ///The items not listes will be put on the highest level.
   1.142 +    ///The items not listed will be put on the highest level.
   1.143      ///@{
   1.144  
   1.145 -    ///Starts the initialization process.
   1.146 +    ///Start the initialization process.
   1.147  
   1.148      void initStart() 
   1.149      {
   1.150 @@ -306,7 +380,7 @@
   1.151        _last_active[_init_lev]=_init_num-1;
   1.152      }
   1.153  
   1.154 -    ///Finalizes the initialization process.
   1.155 +    ///Finalize the initialization process.
   1.156  
   1.157      void initFinish()
   1.158      {