lemon/elevator.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 02 Dec 2008 10:31:20 +0000
changeset 408 69f33ef03334
parent 382 61fbd77f0f44
child 440 88ed40ad0d4f
permissions -rw-r--r--
Merge
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_ELEVATOR_H
    20 #define LEMON_ELEVATOR_H
    21 
    22 ///\ingroup auxdat
    23 ///\file
    24 ///\brief Elevator class
    25 ///
    26 ///Elevator class implements an efficient data structure
    27 ///for labeling items in push-relabel type algorithms.
    28 ///
    29 
    30 #include <lemon/bits/traits.h>
    31 
    32 namespace lemon {
    33 
    34   ///Class for handling "labels" in push-relabel type algorithms.
    35 
    36   ///A class for handling "labels" in push-relabel type algorithms.
    37   ///
    38   ///\ingroup auxdat
    39   ///Using this class you can assign "labels" (nonnegative integer numbers)
    40   ///to the edges or nodes of a graph, manipulate and query them through
    41   ///operations typically arising in "push-relabel" type algorithms.
    42   ///
    43   ///Each item is either \em active or not, and you can also choose a
    44   ///highest level active item.
    45   ///
    46   ///\sa LinkedElevator
    47   ///
    48   ///\param Graph Type of the underlying graph.
    49   ///\param Item Type of the items the data is assigned to (Graph::Node,
    50   ///Graph::Arc, Graph::Edge).
    51   template<class Graph, class Item>
    52   class Elevator
    53   {
    54   public:
    55 
    56     typedef Item Key;
    57     typedef int Value;
    58 
    59   private:
    60 
    61     typedef Item *Vit;
    62     typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
    63     typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
    64 
    65     const Graph &_g;
    66     int _max_level;
    67     int _item_num;
    68     VitMap _where;
    69     IntMap _level;
    70     std::vector<Item> _items;
    71     std::vector<Vit> _first;
    72     std::vector<Vit> _last_active;
    73 
    74     int _highest_active;
    75 
    76     void copy(Item i, Vit p)
    77     {
    78       _where.set(*p=i,p);
    79     }
    80     void copy(Vit s, Vit p)
    81     {
    82       if(s!=p)
    83         {
    84           Item i=*s;
    85           *p=i;
    86           _where.set(i,p);
    87         }
    88     }
    89     void swap(Vit i, Vit j)
    90     {
    91       Item ti=*i;
    92       Vit ct = _where[ti];
    93       _where.set(ti,_where[*i=*j]);
    94       _where.set(*j,ct);
    95       *j=ti;
    96     }
    97 
    98   public:
    99 
   100     ///Constructor with given maximum level.
   101 
   102     ///Constructor with given maximum level.
   103     ///
   104     ///\param graph The underlying graph.
   105     ///\param max_level The maximum allowed level.
   106     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   107     Elevator(const Graph &graph,int max_level) :
   108       _g(graph),
   109       _max_level(max_level),
   110       _item_num(_max_level),
   111       _where(graph),
   112       _level(graph,0),
   113       _items(_max_level),
   114       _first(_max_level+2),
   115       _last_active(_max_level+2),
   116       _highest_active(-1) {}
   117     ///Constructor.
   118 
   119     ///Constructor.
   120     ///
   121     ///\param graph The underlying graph.
   122     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   123     ///where \c max_level is equal to the number of labeled items in the graph.
   124     Elevator(const Graph &graph) :
   125       _g(graph),
   126       _max_level(countItems<Graph, Item>(graph)),
   127       _item_num(_max_level),
   128       _where(graph),
   129       _level(graph,0),
   130       _items(_max_level),
   131       _first(_max_level+2),
   132       _last_active(_max_level+2),
   133       _highest_active(-1)
   134     {
   135     }
   136 
   137     ///Activate item \c i.
   138 
   139     ///Activate item \c i.
   140     ///\pre Item \c i shouldn't be active before.
   141     void activate(Item i)
   142     {
   143       const int l=_level[i];
   144       swap(_where[i],++_last_active[l]);
   145       if(l>_highest_active) _highest_active=l;
   146     }
   147 
   148     ///Deactivate item \c i.
   149 
   150     ///Deactivate item \c i.
   151     ///\pre Item \c i must be active before.
   152     void deactivate(Item i)
   153     {
   154       swap(_where[i],_last_active[_level[i]]--);
   155       while(_highest_active>=0 &&
   156             _last_active[_highest_active]<_first[_highest_active])
   157         _highest_active--;
   158     }
   159 
   160     ///Query whether item \c i is active
   161     bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
   162 
   163     ///Return the level of item \c i.
   164     int operator[](Item i) const { return _level[i]; }
   165 
   166     ///Return the number of items on level \c l.
   167     int onLevel(int l) const
   168     {
   169       return _first[l+1]-_first[l];
   170     }
   171     ///Return true if level \c l is empty.
   172     bool emptyLevel(int l) const
   173     {
   174       return _first[l+1]-_first[l]==0;
   175     }
   176     ///Return the number of items above level \c l.
   177     int aboveLevel(int l) const
   178     {
   179       return _first[_max_level+1]-_first[l+1];
   180     }
   181     ///Return the number of active items on level \c l.
   182     int activesOnLevel(int l) const
   183     {
   184       return _last_active[l]-_first[l]+1;
   185     }
   186     ///Return true if there is no active item on level \c l.
   187     bool activeFree(int l) const
   188     {
   189       return _last_active[l]<_first[l];
   190     }
   191     ///Return the maximum allowed level.
   192     int maxLevel() const
   193     {
   194       return _max_level;
   195     }
   196 
   197     ///\name Highest Active Item
   198     ///Functions for working with the highest level
   199     ///active item.
   200 
   201     ///@{
   202 
   203     ///Return a highest level active item.
   204 
   205     ///Return a highest level active item or INVALID if there is no active
   206     ///item.
   207     Item highestActive() const
   208     {
   209       return _highest_active>=0?*_last_active[_highest_active]:INVALID;
   210     }
   211 
   212     ///Return the highest active level.
   213 
   214     ///Return the level of the highest active item or -1 if there is no active
   215     ///item.
   216     int highestActiveLevel() const
   217     {
   218       return _highest_active;
   219     }
   220 
   221     ///Lift the highest active item by one.
   222 
   223     ///Lift the item returned by highestActive() by one.
   224     ///
   225     void liftHighestActive()
   226     {
   227       Item it = *_last_active[_highest_active];
   228       _level.set(it,_level[it]+1);
   229       swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
   230       --_first[++_highest_active];
   231     }
   232 
   233     ///Lift the highest active item to the given level.
   234 
   235     ///Lift the item returned by highestActive() to level \c new_level.
   236     ///
   237     ///\warning \c new_level must be strictly higher
   238     ///than the current level.
   239     ///
   240     void liftHighestActive(int new_level)
   241     {
   242       const Item li = *_last_active[_highest_active];
   243 
   244       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
   245       for(int l=_highest_active+1;l<new_level;l++)
   246         {
   247           copy(--_first[l+1],_first[l]);
   248           --_last_active[l];
   249         }
   250       copy(li,_first[new_level]);
   251       _level.set(li,new_level);
   252       _highest_active=new_level;
   253     }
   254 
   255     ///Lift the highest active item to the top level.
   256 
   257     ///Lift the item returned by highestActive() to the top level and
   258     ///deactivate it.
   259     void liftHighestActiveToTop()
   260     {
   261       const Item li = *_last_active[_highest_active];
   262 
   263       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
   264       for(int l=_highest_active+1;l<_max_level;l++)
   265         {
   266           copy(--_first[l+1],_first[l]);
   267           --_last_active[l];
   268         }
   269       copy(li,_first[_max_level]);
   270       --_last_active[_max_level];
   271       _level.set(li,_max_level);
   272 
   273       while(_highest_active>=0 &&
   274             _last_active[_highest_active]<_first[_highest_active])
   275         _highest_active--;
   276     }
   277 
   278     ///@}
   279 
   280     ///\name Active Item on Certain Level
   281     ///Functions for working with the active items.
   282 
   283     ///@{
   284 
   285     ///Return an active item on level \c l.
   286 
   287     ///Return an active item on level \c l or \ref INVALID if there is no such
   288     ///an item. (\c l must be from the range [0...\c max_level].
   289     Item activeOn(int l) const
   290     {
   291       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
   292     }
   293 
   294     ///Lift the active item returned by \c activeOn(level) by one.
   295 
   296     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
   297     ///by one.
   298     Item liftActiveOn(int level)
   299     {
   300       Item it =*_last_active[level];
   301       _level.set(it,_level[it]+1);
   302       swap(_last_active[level]--, --_first[level+1]);
   303       if (level+1>_highest_active) ++_highest_active;
   304     }
   305 
   306     ///Lift the active item returned by \c activeOn(level) to the given level.
   307 
   308     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
   309     ///to the given level.
   310     void liftActiveOn(int level, int new_level)
   311     {
   312       const Item ai = *_last_active[level];
   313 
   314       copy(--_first[level+1], _last_active[level]--);
   315       for(int l=level+1;l<new_level;l++)
   316         {
   317           copy(_last_active[l],_first[l]);
   318           copy(--_first[l+1], _last_active[l]--);
   319         }
   320       copy(ai,_first[new_level]);
   321       _level.set(ai,new_level);
   322       if (new_level>_highest_active) _highest_active=new_level;
   323     }
   324 
   325     ///Lift the active item returned by \c activeOn(level) to the top level.
   326 
   327     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
   328     ///to the top level and deactivate it.
   329     void liftActiveToTop(int level)
   330     {
   331       const Item ai = *_last_active[level];
   332 
   333       copy(--_first[level+1],_last_active[level]--);
   334       for(int l=level+1;l<_max_level;l++)
   335         {
   336           copy(_last_active[l],_first[l]);
   337           copy(--_first[l+1], _last_active[l]--);
   338         }
   339       copy(ai,_first[_max_level]);
   340       --_last_active[_max_level];
   341       _level.set(ai,_max_level);
   342 
   343       if (_highest_active==level) {
   344         while(_highest_active>=0 &&
   345               _last_active[_highest_active]<_first[_highest_active])
   346           _highest_active--;
   347       }
   348     }
   349 
   350     ///@}
   351 
   352     ///Lift an active item to a higher level.
   353 
   354     ///Lift an active item to a higher level.
   355     ///\param i The item to be lifted. It must be active.
   356     ///\param new_level The new level of \c i. It must be strictly higher
   357     ///than the current level.
   358     ///
   359     void lift(Item i, int new_level)
   360     {
   361       const int lo = _level[i];
   362       const Vit w = _where[i];
   363 
   364       copy(_last_active[lo],w);
   365       copy(--_first[lo+1],_last_active[lo]--);
   366       for(int l=lo+1;l<new_level;l++)
   367         {
   368           copy(_last_active[l],_first[l]);
   369           copy(--_first[l+1],_last_active[l]--);
   370         }
   371       copy(i,_first[new_level]);
   372       _level.set(i,new_level);
   373       if(new_level>_highest_active) _highest_active=new_level;
   374     }
   375 
   376     ///Move an inactive item to the top but one level (in a dirty way).
   377 
   378     ///This function moves an inactive item from the top level to the top
   379     ///but one level (in a dirty way).
   380     ///\warning It makes the underlying datastructure corrupt, so use it
   381     ///only if you really know what it is for.
   382     ///\pre The item is on the top level.
   383     void dirtyTopButOne(Item i) {
   384       _level.set(i,_max_level - 1);
   385     }
   386 
   387     ///Lift all items on and above the given level to the top level.
   388 
   389     ///This function lifts all items on and above level \c l to the top
   390     ///level and deactivates them.
   391     void liftToTop(int l)
   392     {
   393       const Vit f=_first[l];
   394       const Vit tl=_first[_max_level];
   395       for(Vit i=f;i!=tl;++i)
   396         _level.set(*i,_max_level);
   397       for(int i=l;i<=_max_level;i++)
   398         {
   399           _first[i]=f;
   400           _last_active[i]=f-1;
   401         }
   402       for(_highest_active=l-1;
   403           _highest_active>=0 &&
   404             _last_active[_highest_active]<_first[_highest_active];
   405           _highest_active--) ;
   406     }
   407 
   408   private:
   409     int _init_lev;
   410     Vit _init_num;
   411 
   412   public:
   413 
   414     ///\name Initialization
   415     ///Using these functions you can initialize the levels of the items.
   416     ///\n
   417     ///The initialization must be started with calling \c initStart().
   418     ///Then the items should be listed level by level starting with the
   419     ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
   420     ///Finally \c initFinish() must be called.
   421     ///The items not listed are put on the highest level.
   422     ///@{
   423 
   424     ///Start the initialization process.
   425     void initStart()
   426     {
   427       _init_lev=0;
   428       _init_num=&_items[0];
   429       _first[0]=&_items[0];
   430       _last_active[0]=&_items[0]-1;
   431       Vit n=&_items[0];
   432       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
   433         {
   434           *n=i;
   435           _where.set(i,n);
   436           _level.set(i,_max_level);
   437           ++n;
   438         }
   439     }
   440 
   441     ///Add an item to the current level.
   442     void initAddItem(Item i)
   443     {
   444       swap(_where[i],_init_num);
   445       _level.set(i,_init_lev);
   446       ++_init_num;
   447     }
   448 
   449     ///Start a new level.
   450 
   451     ///Start a new level.
   452     ///It shouldn't be used before the items on level 0 are listed.
   453     void initNewLevel()
   454     {
   455       _init_lev++;
   456       _first[_init_lev]=_init_num;
   457       _last_active[_init_lev]=_init_num-1;
   458     }
   459 
   460     ///Finalize the initialization process.
   461     void initFinish()
   462     {
   463       for(_init_lev++;_init_lev<=_max_level;_init_lev++)
   464         {
   465           _first[_init_lev]=_init_num;
   466           _last_active[_init_lev]=_init_num-1;
   467         }
   468       _first[_max_level+1]=&_items[0]+_item_num;
   469       _last_active[_max_level+1]=&_items[0]+_item_num-1;
   470       _highest_active = -1;
   471     }
   472 
   473     ///@}
   474 
   475   };
   476 
   477   ///Class for handling "labels" in push-relabel type algorithms.
   478 
   479   ///A class for handling "labels" in push-relabel type algorithms.
   480   ///
   481   ///\ingroup auxdat
   482   ///Using this class you can assign "labels" (nonnegative integer numbers)
   483   ///to the edges or nodes of a graph, manipulate and query them through
   484   ///operations typically arising in "push-relabel" type algorithms.
   485   ///
   486   ///Each item is either \em active or not, and you can also choose a
   487   ///highest level active item.
   488   ///
   489   ///\sa Elevator
   490   ///
   491   ///\param Graph Type of the underlying graph.
   492   ///\param Item Type of the items the data is assigned to (Graph::Node,
   493   ///Graph::Arc, Graph::Edge).
   494   template <class Graph, class Item>
   495   class LinkedElevator {
   496   public:
   497 
   498     typedef Item Key;
   499     typedef int Value;
   500 
   501   private:
   502 
   503     typedef typename ItemSetTraits<Graph,Item>::
   504     template Map<Item>::Type ItemMap;
   505     typedef typename ItemSetTraits<Graph,Item>::
   506     template Map<int>::Type IntMap;
   507     typedef typename ItemSetTraits<Graph,Item>::
   508     template Map<bool>::Type BoolMap;
   509 
   510     const Graph &_graph;
   511     int _max_level;
   512     int _item_num;
   513     std::vector<Item> _first, _last;
   514     ItemMap _prev, _next;
   515     int _highest_active;
   516     IntMap _level;
   517     BoolMap _active;
   518 
   519   public:
   520     ///Constructor with given maximum level.
   521 
   522     ///Constructor with given maximum level.
   523     ///
   524     ///\param graph The underlying graph.
   525     ///\param max_level The maximum allowed level.
   526     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   527     LinkedElevator(const Graph& graph, int max_level)
   528       : _graph(graph), _max_level(max_level), _item_num(_max_level),
   529         _first(_max_level + 1), _last(_max_level + 1),
   530         _prev(graph), _next(graph),
   531         _highest_active(-1), _level(graph), _active(graph) {}
   532 
   533     ///Constructor.
   534 
   535     ///Constructor.
   536     ///
   537     ///\param graph The underlying graph.
   538     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   539     ///where \c max_level is equal to the number of labeled items in the graph.
   540     LinkedElevator(const Graph& graph)
   541       : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
   542         _item_num(_max_level),
   543         _first(_max_level + 1), _last(_max_level + 1),
   544         _prev(graph, INVALID), _next(graph, INVALID),
   545         _highest_active(-1), _level(graph), _active(graph) {}
   546 
   547 
   548     ///Activate item \c i.
   549 
   550     ///Activate item \c i.
   551     ///\pre Item \c i shouldn't be active before.
   552     void activate(Item i) {
   553       _active.set(i, true);
   554 
   555       int level = _level[i];
   556       if (level > _highest_active) {
   557         _highest_active = level;
   558       }
   559 
   560       if (_prev[i] == INVALID || _active[_prev[i]]) return;
   561       //unlace
   562       _next.set(_prev[i], _next[i]);
   563       if (_next[i] != INVALID) {
   564         _prev.set(_next[i], _prev[i]);
   565       } else {
   566         _last[level] = _prev[i];
   567       }
   568       //lace
   569       _next.set(i, _first[level]);
   570       _prev.set(_first[level], i);
   571       _prev.set(i, INVALID);
   572       _first[level] = i;
   573 
   574     }
   575 
   576     ///Deactivate item \c i.
   577 
   578     ///Deactivate item \c i.
   579     ///\pre Item \c i must be active before.
   580     void deactivate(Item i) {
   581       _active.set(i, false);
   582       int level = _level[i];
   583 
   584       if (_next[i] == INVALID || !_active[_next[i]])
   585         goto find_highest_level;
   586 
   587       //unlace
   588       _prev.set(_next[i], _prev[i]);
   589       if (_prev[i] != INVALID) {
   590         _next.set(_prev[i], _next[i]);
   591       } else {
   592         _first[_level[i]] = _next[i];
   593       }
   594       //lace
   595       _prev.set(i, _last[level]);
   596       _next.set(_last[level], i);
   597       _next.set(i, INVALID);
   598       _last[level] = i;
   599 
   600     find_highest_level:
   601       if (level == _highest_active) {
   602         while (_highest_active >= 0 && activeFree(_highest_active))
   603           --_highest_active;
   604       }
   605     }
   606 
   607     ///Query whether item \c i is active
   608     bool active(Item i) const { return _active[i]; }
   609 
   610     ///Return the level of item \c i.
   611     int operator[](Item i) const { return _level[i]; }
   612 
   613     ///Return the number of items on level \c l.
   614     int onLevel(int l) const {
   615       int num = 0;
   616       Item n = _first[l];
   617       while (n != INVALID) {
   618         ++num;
   619         n = _next[n];
   620       }
   621       return num;
   622     }
   623 
   624     ///Return true if the level is empty.
   625     bool emptyLevel(int l) const {
   626       return _first[l] == INVALID;
   627     }
   628 
   629     ///Return the number of items above level \c l.
   630     int aboveLevel(int l) const {
   631       int num = 0;
   632       for (int level = l + 1; level < _max_level; ++level)
   633         num += onLevel(level);
   634       return num;
   635     }
   636 
   637     ///Return the number of active items on level \c l.
   638     int activesOnLevel(int l) const {
   639       int num = 0;
   640       Item n = _first[l];
   641       while (n != INVALID && _active[n]) {
   642         ++num;
   643         n = _next[n];
   644       }
   645       return num;
   646     }
   647 
   648     ///Return true if there is no active item on level \c l.
   649     bool activeFree(int l) const {
   650       return _first[l] == INVALID || !_active[_first[l]];
   651     }
   652 
   653     ///Return the maximum allowed level.
   654     int maxLevel() const {
   655       return _max_level;
   656     }
   657 
   658     ///\name Highest Active Item
   659     ///Functions for working with the highest level
   660     ///active item.
   661 
   662     ///@{
   663 
   664     ///Return a highest level active item.
   665 
   666     ///Return a highest level active item or INVALID if there is no active
   667     ///item.
   668     Item highestActive() const {
   669       return _highest_active >= 0 ? _first[_highest_active] : INVALID;
   670     }
   671 
   672     ///Return the highest active level.
   673 
   674     ///Return the level of the highest active item or -1 if there is no active
   675     ///item.
   676     int highestActiveLevel() const {
   677       return _highest_active;
   678     }
   679 
   680     ///Lift the highest active item by one.
   681 
   682     ///Lift the item returned by highestActive() by one.
   683     ///
   684     void liftHighestActive() {
   685       Item i = _first[_highest_active];
   686       if (_next[i] != INVALID) {
   687         _prev.set(_next[i], INVALID);
   688         _first[_highest_active] = _next[i];
   689       } else {
   690         _first[_highest_active] = INVALID;
   691         _last[_highest_active] = INVALID;
   692       }
   693       _level.set(i, ++_highest_active);
   694       if (_first[_highest_active] == INVALID) {
   695         _first[_highest_active] = i;
   696         _last[_highest_active] = i;
   697         _prev.set(i, INVALID);
   698         _next.set(i, INVALID);
   699       } else {
   700         _prev.set(_first[_highest_active], i);
   701         _next.set(i, _first[_highest_active]);
   702         _first[_highest_active] = i;
   703       }
   704     }
   705 
   706     ///Lift the highest active item to the given level.
   707 
   708     ///Lift the item returned by highestActive() to level \c new_level.
   709     ///
   710     ///\warning \c new_level must be strictly higher
   711     ///than the current level.
   712     ///
   713     void liftHighestActive(int new_level) {
   714       Item i = _first[_highest_active];
   715       if (_next[i] != INVALID) {
   716         _prev.set(_next[i], INVALID);
   717         _first[_highest_active] = _next[i];
   718       } else {
   719         _first[_highest_active] = INVALID;
   720         _last[_highest_active] = INVALID;
   721       }
   722       _level.set(i, _highest_active = new_level);
   723       if (_first[_highest_active] == INVALID) {
   724         _first[_highest_active] = _last[_highest_active] = i;
   725         _prev.set(i, INVALID);
   726         _next.set(i, INVALID);
   727       } else {
   728         _prev.set(_first[_highest_active], i);
   729         _next.set(i, _first[_highest_active]);
   730         _first[_highest_active] = i;
   731       }
   732     }
   733 
   734     ///Lift the highest active item to the top level.
   735 
   736     ///Lift the item returned by highestActive() to the top level and
   737     ///deactivate it.
   738     void liftHighestActiveToTop() {
   739       Item i = _first[_highest_active];
   740       _level.set(i, _max_level);
   741       if (_next[i] != INVALID) {
   742         _prev.set(_next[i], INVALID);
   743         _first[_highest_active] = _next[i];
   744       } else {
   745         _first[_highest_active] = INVALID;
   746         _last[_highest_active] = INVALID;
   747       }
   748       while (_highest_active >= 0 && activeFree(_highest_active))
   749         --_highest_active;
   750     }
   751 
   752     ///@}
   753 
   754     ///\name Active Item on Certain Level
   755     ///Functions for working with the active items.
   756 
   757     ///@{
   758 
   759     ///Return an active item on level \c l.
   760 
   761     ///Return an active item on level \c l or \ref INVALID if there is no such
   762     ///an item. (\c l must be from the range [0...\c max_level].
   763     Item activeOn(int l) const
   764     {
   765       return _active[_first[l]] ? _first[l] : INVALID;
   766     }
   767 
   768     ///Lift the active item returned by \c activeOn(l) by one.
   769 
   770     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
   771     ///by one.
   772     Item liftActiveOn(int l)
   773     {
   774       Item i = _first[l];
   775       if (_next[i] != INVALID) {
   776         _prev.set(_next[i], INVALID);
   777         _first[l] = _next[i];
   778       } else {
   779         _first[l] = INVALID;
   780         _last[l] = INVALID;
   781       }
   782       _level.set(i, ++l);
   783       if (_first[l] == INVALID) {
   784         _first[l] = _last[l] = i;
   785         _prev.set(i, INVALID);
   786         _next.set(i, INVALID);
   787       } else {
   788         _prev.set(_first[l], i);
   789         _next.set(i, _first[l]);
   790         _first[l] = i;
   791       }
   792       if (_highest_active < l) {
   793         _highest_active = l;
   794       }
   795     }
   796 
   797     ///Lift the active item returned by \c activeOn(l) to the given level.
   798 
   799     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
   800     ///to the given level.
   801     void liftActiveOn(int l, int new_level)
   802     {
   803       Item i = _first[l];
   804       if (_next[i] != INVALID) {
   805         _prev.set(_next[i], INVALID);
   806         _first[l] = _next[i];
   807       } else {
   808         _first[l] = INVALID;
   809         _last[l] = INVALID;
   810       }
   811       _level.set(i, l = new_level);
   812       if (_first[l] == INVALID) {
   813         _first[l] = _last[l] = i;
   814         _prev.set(i, INVALID);
   815         _next.set(i, INVALID);
   816       } else {
   817         _prev.set(_first[l], i);
   818         _next.set(i, _first[l]);
   819         _first[l] = i;
   820       }
   821       if (_highest_active < l) {
   822         _highest_active = l;
   823       }
   824     }
   825 
   826     ///Lift the active item returned by \c activeOn(l) to the top level.
   827 
   828     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
   829     ///to the top level and deactivate it.
   830     void liftActiveToTop(int l)
   831     {
   832       Item i = _first[l];
   833       if (_next[i] != INVALID) {
   834         _prev.set(_next[i], INVALID);
   835         _first[l] = _next[i];
   836       } else {
   837         _first[l] = INVALID;
   838         _last[l] = INVALID;
   839       }
   840       _level.set(i, _max_level);
   841       if (l == _highest_active) {
   842         while (_highest_active >= 0 && activeFree(_highest_active))
   843           --_highest_active;
   844       }
   845     }
   846 
   847     ///@}
   848 
   849     /// \brief Lift an active item to a higher level.
   850     ///
   851     /// Lift an active item to a higher level.
   852     /// \param i The item to be lifted. It must be active.
   853     /// \param new_level The new level of \c i. It must be strictly higher
   854     /// than the current level.
   855     ///
   856     void lift(Item i, int new_level) {
   857       if (_next[i] != INVALID) {
   858         _prev.set(_next[i], _prev[i]);
   859       } else {
   860         _last[new_level] = _prev[i];
   861       }
   862       if (_prev[i] != INVALID) {
   863         _next.set(_prev[i], _next[i]);
   864       } else {
   865         _first[new_level] = _next[i];
   866       }
   867       _level.set(i, new_level);
   868       if (_first[new_level] == INVALID) {
   869         _first[new_level] = _last[new_level] = i;
   870         _prev.set(i, INVALID);
   871         _next.set(i, INVALID);
   872       } else {
   873         _prev.set(_first[new_level], i);
   874         _next.set(i, _first[new_level]);
   875         _first[new_level] = i;
   876       }
   877       if (_highest_active < new_level) {
   878         _highest_active = new_level;
   879       }
   880     }
   881 
   882     ///Move an inactive item to the top but one level (in a dirty way).
   883 
   884     ///This function moves an inactive item from the top level to the top
   885     ///but one level (in a dirty way).
   886     ///\warning It makes the underlying datastructure corrupt, so use it
   887     ///only if you really know what it is for.
   888     ///\pre The item is on the top level.
   889     void dirtyTopButOne(Item i) {
   890       _level.set(i, _max_level - 1);
   891     }
   892 
   893     ///Lift all items on and above the given level to the top level.
   894 
   895     ///This function lifts all items on and above level \c l to the top
   896     ///level and deactivates them.
   897     void liftToTop(int l)  {
   898       for (int i = l + 1; _first[i] != INVALID; ++i) {
   899         Item n = _first[i];
   900         while (n != INVALID) {
   901           _level.set(n, _max_level);
   902           n = _next[n];
   903         }
   904         _first[i] = INVALID;
   905         _last[i] = INVALID;
   906       }
   907       if (_highest_active > l - 1) {
   908         _highest_active = l - 1;
   909         while (_highest_active >= 0 && activeFree(_highest_active))
   910           --_highest_active;
   911       }
   912     }
   913 
   914   private:
   915 
   916     int _init_level;
   917 
   918   public:
   919 
   920     ///\name Initialization
   921     ///Using these functions you can initialize the levels of the items.
   922     ///\n
   923     ///The initialization must be started with calling \c initStart().
   924     ///Then the items should be listed level by level starting with the
   925     ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
   926     ///Finally \c initFinish() must be called.
   927     ///The items not listed are put on the highest level.
   928     ///@{
   929 
   930     ///Start the initialization process.
   931     void initStart() {
   932 
   933       for (int i = 0; i <= _max_level; ++i) {
   934         _first[i] = _last[i] = INVALID;
   935       }
   936       _init_level = 0;
   937       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
   938           i != INVALID; ++i) {
   939         _level.set(i, _max_level);
   940         _active.set(i, false);
   941       }
   942     }
   943 
   944     ///Add an item to the current level.
   945     void initAddItem(Item i) {
   946       _level.set(i, _init_level);
   947       if (_last[_init_level] == INVALID) {
   948         _first[_init_level] = i;
   949         _last[_init_level] = i;
   950         _prev.set(i, INVALID);
   951         _next.set(i, INVALID);
   952       } else {
   953         _prev.set(i, _last[_init_level]);
   954         _next.set(i, INVALID);
   955         _next.set(_last[_init_level], i);
   956         _last[_init_level] = i;
   957       }
   958     }
   959 
   960     ///Start a new level.
   961 
   962     ///Start a new level.
   963     ///It shouldn't be used before the items on level 0 are listed.
   964     void initNewLevel() {
   965       ++_init_level;
   966     }
   967 
   968     ///Finalize the initialization process.
   969     void initFinish() {
   970       _highest_active = -1;
   971     }
   972 
   973     ///@}
   974 
   975   };
   976 
   977 
   978 } //END OF NAMESPACE LEMON
   979 
   980 #endif
   981