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