lemon/elevator.h
changeset 390 53c5277ba294
parent 382 61fbd77f0f44
child 440 88ed40ad0d4f
equal deleted inserted replaced
3:052089a90157 4:57611c56ba90
    25 ///
    25 ///
    26 ///Elevator class implements an efficient data structure
    26 ///Elevator class implements an efficient data structure
    27 ///for labeling items in push-relabel type algorithms.
    27 ///for labeling items in push-relabel type algorithms.
    28 ///
    28 ///
    29 
    29 
    30 #include <test/test_tools.h>
    30 #include <lemon/bits/traits.h>
       
    31 
    31 namespace lemon {
    32 namespace lemon {
    32 
    33 
    33   ///Class for handling "labels" in push-relabel type algorithms.
    34   ///Class for handling "labels" in push-relabel type algorithms.
    34 
    35 
    35   ///A class for handling "labels" in push-relabel type algorithms.
    36   ///A class for handling "labels" in push-relabel type algorithms.
    42   ///Each item is either \em active or not, and you can also choose a
    43   ///Each item is either \em active or not, and you can also choose a
    43   ///highest level active item.
    44   ///highest level active item.
    44   ///
    45   ///
    45   ///\sa LinkedElevator
    46   ///\sa LinkedElevator
    46   ///
    47   ///
    47   ///\param Graph the underlying graph type
    48   ///\param Graph Type of the underlying graph.
    48   ///\param Item Type of the items the data is assigned to (Graph::Node,
    49   ///\param Item Type of the items the data is assigned to (Graph::Node,
    49   ///Graph::Edge, Graph::UEdge)
    50   ///Graph::Arc, Graph::Edge).
    50   template<class Graph, class Item>
    51   template<class Graph, class Item>
    51   class Elevator
    52   class Elevator
    52   {
    53   {
    53   public:
    54   public:
    54 
    55 
    98 
    99 
    99     ///Constructor with given maximum level.
   100     ///Constructor with given maximum level.
   100 
   101 
   101     ///Constructor with given maximum level.
   102     ///Constructor with given maximum level.
   102     ///
   103     ///
   103     ///\param g The underlying graph
   104     ///\param graph The underlying graph.
   104     ///\param max_level Set the range of the possible labels to
   105     ///\param max_level The maximum allowed level.
   105     ///[0...\c max_level]
   106     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   106     Elevator(const Graph &g,int max_level) :
   107     Elevator(const Graph &graph,int max_level) :
   107       _g(g),
   108       _g(graph),
   108       _max_level(max_level),
   109       _max_level(max_level),
   109       _item_num(_max_level),
   110       _item_num(_max_level),
   110       _where(g),
   111       _where(graph),
   111       _level(g,0),
   112       _level(graph,0),
   112       _items(_max_level),
   113       _items(_max_level),
   113       _first(_max_level+2),
   114       _first(_max_level+2),
   114       _last_active(_max_level+2),
   115       _last_active(_max_level+2),
   115       _highest_active(-1) {}
   116       _highest_active(-1) {}
   116     ///Constructor.
   117     ///Constructor.
   117 
   118 
   118     ///Constructor.
   119     ///Constructor.
   119     ///
   120     ///
   120     ///\param g The underlying graph
   121     ///\param graph The underlying graph.
   121     ///The range of the possible labels is [0...\c max_level],
   122     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   122     ///where \c max_level is equal to the number of labeled items in the graph.
   123     ///where \c max_level is equal to the number of labeled items in the graph.
   123     Elevator(const Graph &g) :
   124     Elevator(const Graph &graph) :
   124       _g(g),
   125       _g(graph),
   125       _max_level(countItems<Graph, Item>(g)),
   126       _max_level(countItems<Graph, Item>(graph)),
   126       _item_num(_max_level),
   127       _item_num(_max_level),
   127       _where(g),
   128       _where(graph),
   128       _level(g,0),
   129       _level(graph,0),
   129       _items(_max_level),
   130       _items(_max_level),
   130       _first(_max_level+2),
   131       _first(_max_level+2),
   131       _last_active(_max_level+2),
   132       _last_active(_max_level+2),
   132       _highest_active(-1)
   133       _highest_active(-1)
   133     {
   134     {
   165     ///Return the number of items on level \c l.
   166     ///Return the number of items on level \c l.
   166     int onLevel(int l) const
   167     int onLevel(int l) const
   167     {
   168     {
   168       return _first[l+1]-_first[l];
   169       return _first[l+1]-_first[l];
   169     }
   170     }
   170     ///Return true if the level is empty.
   171     ///Return true if level \c l is empty.
   171     bool emptyLevel(int l) const
   172     bool emptyLevel(int l) const
   172     {
   173     {
   173       return _first[l+1]-_first[l]==0;
   174       return _first[l+1]-_first[l]==0;
   174     }
   175     }
   175     ///Return the number of items above level \c l.
   176     ///Return the number of items above level \c l.
   180     ///Return the number of active items on level \c l.
   181     ///Return the number of active items on level \c l.
   181     int activesOnLevel(int l) const
   182     int activesOnLevel(int l) const
   182     {
   183     {
   183       return _last_active[l]-_first[l]+1;
   184       return _last_active[l]-_first[l]+1;
   184     }
   185     }
   185     ///Return true if there is not active item on level \c l.
   186     ///Return true if there is no active item on level \c l.
   186     bool activeFree(int l) const
   187     bool activeFree(int l) const
   187     {
   188     {
   188       return _last_active[l]<_first[l];
   189       return _last_active[l]<_first[l];
   189     }
   190     }
   190     ///Return the maximum allowed level.
   191     ///Return the maximum allowed level.
   199 
   200 
   200     ///@{
   201     ///@{
   201 
   202 
   202     ///Return a highest level active item.
   203     ///Return a highest level active item.
   203 
   204 
   204     ///Return a highest level active item.
   205     ///Return a highest level active item or INVALID if there is no active
   205     ///
       
   206     ///\return the highest level active item or INVALID if there is no active
       
   207     ///item.
   206     ///item.
   208     Item highestActive() const
   207     Item highestActive() const
   209     {
   208     {
   210       return _highest_active>=0?*_last_active[_highest_active]:INVALID;
   209       return _highest_active>=0?*_last_active[_highest_active]:INVALID;
   211     }
   210     }
   212 
   211 
   213     ///Return a highest active level.
   212     ///Return the highest active level.
   214 
   213 
   215     ///Return a highest active level.
   214     ///Return the level of the highest active item or -1 if there is no active
   216     ///
       
   217     ///\return the level of the highest active item or -1 if there is no active
       
   218     ///item.
   215     ///item.
   219     int highestActiveLevel() const
   216     int highestActiveLevel() const
   220     {
   217     {
   221       return _highest_active;
   218       return _highest_active;
   222     }
   219     }
   231       _level.set(it,_level[it]+1);
   228       _level.set(it,_level[it]+1);
   232       swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
   229       swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
   233       --_first[++_highest_active];
   230       --_first[++_highest_active];
   234     }
   231     }
   235 
   232 
   236     ///Lift the highest active item.
   233     ///Lift the highest active item to the given level.
   237 
   234 
   238     ///Lift the item returned by highestActive() to level \c new_level.
   235     ///Lift the item returned by highestActive() to level \c new_level.
   239     ///
   236     ///
   240     ///\warning \c new_level must be strictly higher
   237     ///\warning \c new_level must be strictly higher
   241     ///than the current level.
   238     ///than the current level.
   253       copy(li,_first[new_level]);
   250       copy(li,_first[new_level]);
   254       _level.set(li,new_level);
   251       _level.set(li,new_level);
   255       _highest_active=new_level;
   252       _highest_active=new_level;
   256     }
   253     }
   257 
   254 
   258     ///Lift the highest active item.
   255     ///Lift the highest active item to the top level.
   259 
   256 
   260     ///Lift the item returned by highestActive() to the top level and
   257     ///Lift the item returned by highestActive() to the top level and
   261     ///deactivates it.
   258     ///deactivate it.
   262     ///
       
   263     ///\warning \c new_level must be strictly higher
       
   264     ///than the current level.
       
   265     ///
       
   266     void liftHighestActiveToTop()
   259     void liftHighestActiveToTop()
   267     {
   260     {
   268       const Item li = *_last_active[_highest_active];
   261       const Item li = *_last_active[_highest_active];
   269 
   262 
   270       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
   263       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
   287     ///\name Active Item on Certain Level
   280     ///\name Active Item on Certain Level
   288     ///Functions for working with the active items.
   281     ///Functions for working with the active items.
   289 
   282 
   290     ///@{
   283     ///@{
   291 
   284 
   292     ///Returns an active item on level \c l.
   285     ///Return an active item on level \c l.
   293 
   286 
   294     ///Returns an active item on level \c l.
   287     ///Return an active item on level \c l or \ref INVALID if there is no such
   295     ///
       
   296     ///Returns an active item on level \c l or \ref INVALID if there is no such
       
   297     ///an item. (\c l must be from the range [0...\c max_level].
   288     ///an item. (\c l must be from the range [0...\c max_level].
   298     Item activeOn(int l) const
   289     Item activeOn(int l) const
   299     {
   290     {
   300       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
   291       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
   301     }
   292     }
   302 
   293 
   303     ///Lifts the active item returned by \c activeOn() member function.
   294     ///Lift the active item returned by \c activeOn(level) by one.
   304 
   295 
   305     ///Lifts the active item returned by \c activeOn() member function
   296     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
   306     ///by one.
   297     ///by one.
   307     Item liftActiveOn(int level)
   298     Item liftActiveOn(int level)
   308     {
   299     {
   309       Item it =*_last_active[level];
   300       Item it =*_last_active[level];
   310       _level.set(it,_level[it]+1);
   301       _level.set(it,_level[it]+1);
   311       swap(_last_active[level]--, --_first[level+1]);
   302       swap(_last_active[level]--, --_first[level+1]);
   312       if (level+1>_highest_active) ++_highest_active;
   303       if (level+1>_highest_active) ++_highest_active;
   313     }
   304     }
   314 
   305 
   315     ///Lifts the active item returned by \c activeOn() member function.
   306     ///Lift the active item returned by \c activeOn(level) to the given level.
   316 
   307 
   317     ///Lifts the active item returned by \c activeOn() member function
   308     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
   318     ///to the given level.
   309     ///to the given level.
   319     void liftActiveOn(int level, int new_level)
   310     void liftActiveOn(int level, int new_level)
   320     {
   311     {
   321       const Item ai = *_last_active[level];
   312       const Item ai = *_last_active[level];
   322 
   313 
   329       copy(ai,_first[new_level]);
   320       copy(ai,_first[new_level]);
   330       _level.set(ai,new_level);
   321       _level.set(ai,new_level);
   331       if (new_level>_highest_active) _highest_active=new_level;
   322       if (new_level>_highest_active) _highest_active=new_level;
   332     }
   323     }
   333 
   324 
   334     ///Lifts the active item returned by \c activeOn() member function.
   325     ///Lift the active item returned by \c activeOn(level) to the top level.
   335 
   326 
   336     ///Lifts the active item returned by \c activeOn() member function
   327     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
   337     ///to the top level.
   328     ///to the top level and deactivate it.
   338     void liftActiveToTop(int level)
   329     void liftActiveToTop(int level)
   339     {
   330     {
   340       const Item ai = *_last_active[level];
   331       const Item ai = *_last_active[level];
   341 
   332 
   342       copy(--_first[level+1],_last_active[level]--);
   333       copy(--_first[level+1],_last_active[level]--);
   382       if(new_level>_highest_active) _highest_active=new_level;
   373       if(new_level>_highest_active) _highest_active=new_level;
   383     }
   374     }
   384 
   375 
   385     ///Move an inactive item to the top but one level (in a dirty way).
   376     ///Move an inactive item to the top but one level (in a dirty way).
   386 
   377 
   387     ///This function moves an inactive item to the top but one level.
   378     ///This function moves an inactive item from the top level to the top
   388     ///It makes the underlying datastructure corrupt, so use is only if
   379     ///but one level (in a dirty way).
   389     ///you really know what it is for.
   380     ///\warning It makes the underlying datastructure corrupt, so use it
       
   381     ///only if you really know what it is for.
   390     ///\pre The item is on the top level.
   382     ///\pre The item is on the top level.
   391     void dirtyTopButOne(Item i) {
   383     void dirtyTopButOne(Item i) {
   392       _level.set(i,_max_level - 1);
   384       _level.set(i,_max_level - 1);
   393     }
   385     }
   394 
   386 
   395     ///Lift all items on and above a level to the top (and deactivate them).
   387     ///Lift all items on and above the given level to the top level.
   396 
   388 
   397     ///This function lifts all items on and above level \c l to \c
   389     ///This function lifts all items on and above level \c l to the top
   398     ///maxLevel(), and also deactivates them.
   390     ///level and deactivates them.
   399     void liftToTop(int l)
   391     void liftToTop(int l)
   400     {
   392     {
   401       const Vit f=_first[l];
   393       const Vit f=_first[l];
   402       const Vit tl=_first[_max_level];
   394       const Vit tl=_first[_max_level];
   403       for(Vit i=f;i!=tl;++i)
   395       for(Vit i=f;i!=tl;++i)
   418     Vit _init_num;
   410     Vit _init_num;
   419 
   411 
   420   public:
   412   public:
   421 
   413 
   422     ///\name Initialization
   414     ///\name Initialization
   423     ///Using this function you can initialize the levels of the item.
   415     ///Using these functions you can initialize the levels of the items.
   424     ///\n
   416     ///\n
   425     ///This initializatios is started with calling \c initStart().
   417     ///The initialization must be started with calling \c initStart().
   426     ///Then the
   418     ///Then the items should be listed level by level starting with the
   427     ///items should be listed levels by levels statring with the lowest one
   419     ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
   428     ///(with level 0). This is done by using \c initAddItem()
   420     ///Finally \c initFinish() must be called.
   429     ///and \c initNewLevel(). Finally \c initFinish() must be called.
   421     ///The items not listed are put on the highest level.
   430     ///The items not listed will be put on the highest level.
       
   431     ///@{
   422     ///@{
   432 
   423 
   433     ///Start the initialization process.
   424     ///Start the initialization process.
   434 
       
   435     void initStart()
   425     void initStart()
   436     {
   426     {
   437       _init_lev=0;
   427       _init_lev=0;
   438       _init_num=&_items[0];
   428       _init_num=&_items[0];
   439       _first[0]=&_items[0];
   429       _first[0]=&_items[0];
   447           ++n;
   437           ++n;
   448         }
   438         }
   449     }
   439     }
   450 
   440 
   451     ///Add an item to the current level.
   441     ///Add an item to the current level.
   452 
       
   453     void initAddItem(Item i)
   442     void initAddItem(Item i)
   454     {
   443     {
   455       swap(_where[i],_init_num);
   444       swap(_where[i],_init_num);
   456       _level.set(i,_init_lev);
   445       _level.set(i,_init_lev);
   457       ++_init_num;
   446       ++_init_num;
   467       _first[_init_lev]=_init_num;
   456       _first[_init_lev]=_init_num;
   468       _last_active[_init_lev]=_init_num-1;
   457       _last_active[_init_lev]=_init_num-1;
   469     }
   458     }
   470 
   459 
   471     ///Finalize the initialization process.
   460     ///Finalize the initialization process.
   472 
       
   473     void initFinish()
   461     void initFinish()
   474     {
   462     {
   475       for(_init_lev++;_init_lev<=_max_level;_init_lev++)
   463       for(_init_lev++;_init_lev<=_max_level;_init_lev++)
   476         {
   464         {
   477           _first[_init_lev]=_init_num;
   465           _first[_init_lev]=_init_num;
   498   ///Each item is either \em active or not, and you can also choose a
   486   ///Each item is either \em active or not, and you can also choose a
   499   ///highest level active item.
   487   ///highest level active item.
   500   ///
   488   ///
   501   ///\sa Elevator
   489   ///\sa Elevator
   502   ///
   490   ///
   503   ///\param Graph the underlying graph type
   491   ///\param Graph Type of the underlying graph.
   504   ///\param Item Type of the items the data is assigned to (Graph::Node,
   492   ///\param Item Type of the items the data is assigned to (Graph::Node,
   505   ///Graph::Edge, Graph::UEdge)
   493   ///Graph::Arc, Graph::Edge).
   506   template <class Graph, class Item>
   494   template <class Graph, class Item>
   507   class LinkedElevator {
   495   class LinkedElevator {
   508   public:
   496   public:
   509 
   497 
   510     typedef Item Key;
   498     typedef Item Key;
   531   public:
   519   public:
   532     ///Constructor with given maximum level.
   520     ///Constructor with given maximum level.
   533 
   521 
   534     ///Constructor with given maximum level.
   522     ///Constructor with given maximum level.
   535     ///
   523     ///
   536     ///\param g The underlying graph
   524     ///\param graph The underlying graph.
   537     ///\param max_level Set the range of the possible labels to
   525     ///\param max_level The maximum allowed level.
   538     ///[0...\c max_level]
   526     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   539     LinkedElevator(const Graph& graph, int max_level)
   527     LinkedElevator(const Graph& graph, int max_level)
   540       : _graph(graph), _max_level(max_level), _item_num(_max_level),
   528       : _graph(graph), _max_level(max_level), _item_num(_max_level),
   541         _first(_max_level + 1), _last(_max_level + 1),
   529         _first(_max_level + 1), _last(_max_level + 1),
   542         _prev(graph), _next(graph),
   530         _prev(graph), _next(graph),
   543         _highest_active(-1), _level(graph), _active(graph) {}
   531         _highest_active(-1), _level(graph), _active(graph) {}
   544 
   532 
   545     ///Constructor.
   533     ///Constructor.
   546 
   534 
   547     ///Constructor.
   535     ///Constructor.
   548     ///
   536     ///
   549     ///\param g The underlying graph
   537     ///\param graph The underlying graph.
   550     ///The range of the possible labels is [0...\c max_level],
   538     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   551     ///where \c max_level is equal to the number of labeled items in the graph.
   539     ///where \c max_level is equal to the number of labeled items in the graph.
   552     LinkedElevator(const Graph& graph)
   540     LinkedElevator(const Graph& graph)
   553       : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
   541       : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
   554         _item_num(_max_level),
   542         _item_num(_max_level),
   555         _first(_max_level + 1), _last(_max_level + 1),
   543         _first(_max_level + 1), _last(_max_level + 1),
   655         n = _next[n];
   643         n = _next[n];
   656       }
   644       }
   657       return num;
   645       return num;
   658     }
   646     }
   659 
   647 
   660     ///Return true if there is not active item on level \c l.
   648     ///Return true if there is no active item on level \c l.
   661     bool activeFree(int l) const {
   649     bool activeFree(int l) const {
   662       return _first[l] == INVALID || !_active[_first[l]];
   650       return _first[l] == INVALID || !_active[_first[l]];
   663     }
   651     }
   664 
   652 
   665     ///Return the maximum allowed level.
   653     ///Return the maximum allowed level.
   673 
   661 
   674     ///@{
   662     ///@{
   675 
   663 
   676     ///Return a highest level active item.
   664     ///Return a highest level active item.
   677 
   665 
   678     ///Return a highest level active item.
   666     ///Return a highest level active item or INVALID if there is no active
   679     ///
   667     ///item.
   680     ///\return the highest level active item or INVALID if there is no
       
   681     ///active item.
       
   682     Item highestActive() const {
   668     Item highestActive() const {
   683       return _highest_active >= 0 ? _first[_highest_active] : INVALID;
   669       return _highest_active >= 0 ? _first[_highest_active] : INVALID;
   684     }
   670     }
   685 
   671 
   686     ///Return a highest active level.
   672     ///Return the highest active level.
   687 
   673 
   688     ///Return a highest active level.
   674     ///Return the level of the highest active item or -1 if there is no active
   689     ///
   675     ///item.
   690     ///\return the level of the highest active item or -1 if there is
       
   691     ///no active item.
       
   692     int highestActiveLevel() const {
   676     int highestActiveLevel() const {
   693       return _highest_active;
   677       return _highest_active;
   694     }
   678     }
   695 
   679 
   696     ///Lift the highest active item by one.
   680     ///Lift the highest active item by one.
   717         _next.set(i, _first[_highest_active]);
   701         _next.set(i, _first[_highest_active]);
   718         _first[_highest_active] = i;
   702         _first[_highest_active] = i;
   719       }
   703       }
   720     }
   704     }
   721 
   705 
   722     ///Lift the highest active item.
   706     ///Lift the highest active item to the given level.
   723 
   707 
   724     ///Lift the item returned by highestActive() to level \c new_level.
   708     ///Lift the item returned by highestActive() to level \c new_level.
   725     ///
   709     ///
   726     ///\warning \c new_level must be strictly higher
   710     ///\warning \c new_level must be strictly higher
   727     ///than the current level.
   711     ///than the current level.
   745         _next.set(i, _first[_highest_active]);
   729         _next.set(i, _first[_highest_active]);
   746         _first[_highest_active] = i;
   730         _first[_highest_active] = i;
   747       }
   731       }
   748     }
   732     }
   749 
   733 
   750     ///Lift the highest active to top.
   734     ///Lift the highest active item to the top level.
   751 
   735 
   752     ///Lift the item returned by highestActive() to the top level and
   736     ///Lift the item returned by highestActive() to the top level and
   753     ///deactivates the item.
   737     ///deactivate it.
   754     ///
       
   755     void liftHighestActiveToTop() {
   738     void liftHighestActiveToTop() {
   756       Item i = _first[_highest_active];
   739       Item i = _first[_highest_active];
   757       _level.set(i, _max_level);
   740       _level.set(i, _max_level);
   758       if (_next[i] != INVALID) {
   741       if (_next[i] != INVALID) {
   759         _prev.set(_next[i], INVALID);
   742         _prev.set(_next[i], INVALID);
   771     ///\name Active Item on Certain Level
   754     ///\name Active Item on Certain Level
   772     ///Functions for working with the active items.
   755     ///Functions for working with the active items.
   773 
   756 
   774     ///@{
   757     ///@{
   775 
   758 
   776     ///Returns an active item on level \c l.
   759     ///Return an active item on level \c l.
   777 
   760 
   778     ///Returns an active item on level \c l.
   761     ///Return an active item on level \c l or \ref INVALID if there is no such
   779     ///
       
   780     ///Returns an active item on level \c l or \ref INVALID if there is no such
       
   781     ///an item. (\c l must be from the range [0...\c max_level].
   762     ///an item. (\c l must be from the range [0...\c max_level].
   782     Item activeOn(int l) const
   763     Item activeOn(int l) const
   783     {
   764     {
   784       return _active[_first[l]] ? _first[l] : INVALID;
   765       return _active[_first[l]] ? _first[l] : INVALID;
   785     }
   766     }
   786 
   767 
   787     ///Lifts the active item returned by \c activeOn() member function.
   768     ///Lift the active item returned by \c activeOn(l) by one.
   788 
   769 
   789     ///Lifts the active item returned by \c activeOn() member function
   770     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
   790     ///by one.
   771     ///by one.
   791     Item liftActiveOn(int l)
   772     Item liftActiveOn(int l)
   792     {
   773     {
   793       Item i = _first[l];
   774       Item i = _first[l];
   794       if (_next[i] != INVALID) {
   775       if (_next[i] != INVALID) {
   811       if (_highest_active < l) {
   792       if (_highest_active < l) {
   812         _highest_active = l;
   793         _highest_active = l;
   813       }
   794       }
   814     }
   795     }
   815 
   796 
   816     /// \brief Lifts the active item returned by \c activeOn() member function.
   797     ///Lift the active item returned by \c activeOn(l) to the given level.
   817     ///
   798 
   818     /// Lifts the active item returned by \c activeOn() member function
   799     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
   819     /// to the given level.
   800     ///to the given level.
   820     void liftActiveOn(int l, int new_level)
   801     void liftActiveOn(int l, int new_level)
   821     {
   802     {
   822       Item i = _first[l];
   803       Item i = _first[l];
   823       if (_next[i] != INVALID) {
   804       if (_next[i] != INVALID) {
   824         _prev.set(_next[i], INVALID);
   805         _prev.set(_next[i], INVALID);
   840       if (_highest_active < l) {
   821       if (_highest_active < l) {
   841         _highest_active = l;
   822         _highest_active = l;
   842       }
   823       }
   843     }
   824     }
   844 
   825 
   845     ///Lifts the active item returned by \c activeOn() member function.
   826     ///Lift the active item returned by \c activeOn(l) to the top level.
   846 
   827 
   847     ///Lifts the active item returned by \c activeOn() member function
   828     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
   848     ///to the top level.
   829     ///to the top level and deactivate it.
   849     void liftActiveToTop(int l)
   830     void liftActiveToTop(int l)
   850     {
   831     {
   851       Item i = _first[l];
   832       Item i = _first[l];
   852       if (_next[i] != INVALID) {
   833       if (_next[i] != INVALID) {
   853         _prev.set(_next[i], INVALID);
   834         _prev.set(_next[i], INVALID);
   898       }
   879       }
   899     }
   880     }
   900 
   881 
   901     ///Move an inactive item to the top but one level (in a dirty way).
   882     ///Move an inactive item to the top but one level (in a dirty way).
   902 
   883 
   903     ///This function moves an inactive item to the top but one level.
   884     ///This function moves an inactive item from the top level to the top
   904     ///It makes the underlying datastructure corrupt, so use is only if
   885     ///but one level (in a dirty way).
   905     ///you really know what it is for.
   886     ///\warning It makes the underlying datastructure corrupt, so use it
       
   887     ///only if you really know what it is for.
   906     ///\pre The item is on the top level.
   888     ///\pre The item is on the top level.
   907     void dirtyTopButOne(Item i) {
   889     void dirtyTopButOne(Item i) {
   908       _level.set(i, _max_level - 1);
   890       _level.set(i, _max_level - 1);
   909     }
   891     }
   910 
   892 
   911     ///Lift all items on and above a level to the top (and deactivate them).
   893     ///Lift all items on and above the given level to the top level.
   912 
   894 
   913     ///This function lifts all items on and above level \c l to \c
   895     ///This function lifts all items on and above level \c l to the top
   914     ///maxLevel(), and also deactivates them.
   896     ///level and deactivates them.
   915     void liftToTop(int l)  {
   897     void liftToTop(int l)  {
   916       for (int i = l + 1; _first[i] != INVALID; ++i) {
   898       for (int i = l + 1; _first[i] != INVALID; ++i) {
   917         Item n = _first[i];
   899         Item n = _first[i];
   918         while (n != INVALID) {
   900         while (n != INVALID) {
   919           _level.set(n, _max_level);
   901           _level.set(n, _max_level);
   934     int _init_level;
   916     int _init_level;
   935 
   917 
   936   public:
   918   public:
   937 
   919 
   938     ///\name Initialization
   920     ///\name Initialization
   939     ///Using this function you can initialize the levels of the item.
   921     ///Using these functions you can initialize the levels of the items.
   940     ///\n
   922     ///\n
   941     ///This initializatios is started with calling \c initStart().
   923     ///The initialization must be started with calling \c initStart().
   942     ///Then the
   924     ///Then the items should be listed level by level starting with the
   943     ///items should be listed levels by levels statring with the lowest one
   925     ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
   944     ///(with level 0). This is done by using \c initAddItem()
   926     ///Finally \c initFinish() must be called.
   945     ///and \c initNewLevel(). Finally \c initFinish() must be called.
   927     ///The items not listed are put on the highest level.
   946     ///The items not listed will be put on the highest level.
       
   947     ///@{
   928     ///@{
   948 
   929 
   949     ///Start the initialization process.
   930     ///Start the initialization process.
   950 
       
   951     void initStart() {
   931     void initStart() {
   952 
   932 
   953       for (int i = 0; i <= _max_level; ++i) {
   933       for (int i = 0; i <= _max_level; ++i) {
   954         _first[i] = _last[i] = INVALID;
   934         _first[i] = _last[i] = INVALID;
   955       }
   935       }
   960         _active.set(i, false);
   940         _active.set(i, false);
   961       }
   941       }
   962     }
   942     }
   963 
   943 
   964     ///Add an item to the current level.
   944     ///Add an item to the current level.
   965 
       
   966     void initAddItem(Item i) {
   945     void initAddItem(Item i) {
   967       _level.set(i, _init_level);
   946       _level.set(i, _init_level);
   968       if (_last[_init_level] == INVALID) {
   947       if (_last[_init_level] == INVALID) {
   969         _first[_init_level] = i;
   948         _first[_init_level] = i;
   970         _last[_init_level] = i;
   949         _last[_init_level] = i;
   985     void initNewLevel() {
   964     void initNewLevel() {
   986       ++_init_level;
   965       ++_init_level;
   987     }
   966     }
   988 
   967 
   989     ///Finalize the initialization process.
   968     ///Finalize the initialization process.
   990 
       
   991     void initFinish() {
   969     void initFinish() {
   992       _highest_active = -1;
   970       _highest_active = -1;
   993     }
   971     }
   994 
   972 
   995     ///@}
   973     ///@}