alpar@394: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@394:  *
alpar@394:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@394:  *
alpar@463:  * Copyright (C) 2003-2009
alpar@394:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@394:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@394:  *
alpar@394:  * Permission to use, modify and distribute this software is granted
alpar@394:  * provided that this copyright notice appears in all copies. For
alpar@394:  * precise terms see the accompanying LICENSE file.
alpar@394:  *
alpar@394:  * This software is provided "AS IS" with no warranty of any kind,
alpar@394:  * express or implied, and with no claim as to its suitability for any
alpar@394:  * purpose.
alpar@394:  *
alpar@394:  */
alpar@394: 
alpar@394: #ifndef LEMON_ELEVATOR_H
alpar@394: #define LEMON_ELEVATOR_H
alpar@394: 
alpar@394: ///\ingroup auxdat
alpar@394: ///\file
alpar@394: ///\brief Elevator class
alpar@394: ///
alpar@394: ///Elevator class implements an efficient data structure
alpar@394: ///for labeling items in push-relabel type algorithms.
alpar@394: ///
alpar@394: 
deba@566: #include <lemon/core.h>
kpeter@398: #include <lemon/bits/traits.h>
kpeter@398: 
alpar@394: namespace lemon {
alpar@394: 
alpar@394:   ///Class for handling "labels" in push-relabel type algorithms.
alpar@394: 
alpar@394:   ///A class for handling "labels" in push-relabel type algorithms.
alpar@394:   ///
alpar@394:   ///\ingroup auxdat
alpar@394:   ///Using this class you can assign "labels" (nonnegative integer numbers)
alpar@394:   ///to the edges or nodes of a graph, manipulate and query them through
alpar@394:   ///operations typically arising in "push-relabel" type algorithms.
alpar@394:   ///
alpar@394:   ///Each item is either \em active or not, and you can also choose a
alpar@394:   ///highest level active item.
alpar@394:   ///
alpar@394:   ///\sa LinkedElevator
alpar@394:   ///
kpeter@606:   ///\param GR Type of the underlying graph.
kpeter@606:   ///\param Item Type of the items the data is assigned to (\c GR::Node,
kpeter@606:   ///\c GR::Arc or \c GR::Edge).
kpeter@606:   template<class GR, class Item>
alpar@394:   class Elevator
alpar@394:   {
alpar@394:   public:
alpar@394: 
alpar@394:     typedef Item Key;
alpar@394:     typedef int Value;
alpar@394: 
alpar@394:   private:
alpar@394: 
alpar@396:     typedef Item *Vit;
kpeter@606:     typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
kpeter@606:     typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
alpar@394: 
kpeter@606:     const GR &_g;
alpar@394:     int _max_level;
alpar@394:     int _item_num;
alpar@394:     VitMap _where;
alpar@394:     IntMap _level;
alpar@394:     std::vector<Item> _items;
alpar@394:     std::vector<Vit> _first;
alpar@394:     std::vector<Vit> _last_active;
alpar@394: 
alpar@394:     int _highest_active;
alpar@394: 
alpar@394:     void copy(Item i, Vit p)
alpar@394:     {
kpeter@628:       _where[*p=i] = p;
alpar@394:     }
alpar@394:     void copy(Vit s, Vit p)
alpar@394:     {
alpar@394:       if(s!=p)
alpar@394:         {
alpar@394:           Item i=*s;
alpar@394:           *p=i;
kpeter@628:           _where[i] = p;
alpar@394:         }
alpar@394:     }
alpar@394:     void swap(Vit i, Vit j)
alpar@394:     {
alpar@394:       Item ti=*i;
alpar@394:       Vit ct = _where[ti];
kpeter@628:       _where[ti] = _where[*i=*j];
kpeter@628:       _where[*j] = ct;
alpar@394:       *j=ti;
alpar@394:     }
alpar@394: 
alpar@394:   public:
alpar@394: 
alpar@394:     ///Constructor with given maximum level.
alpar@394: 
alpar@394:     ///Constructor with given maximum level.
alpar@394:     ///
kpeter@398:     ///\param graph The underlying graph.
kpeter@398:     ///\param max_level The maximum allowed level.
kpeter@398:     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
kpeter@606:     Elevator(const GR &graph,int max_level) :
kpeter@398:       _g(graph),
alpar@394:       _max_level(max_level),
alpar@394:       _item_num(_max_level),
kpeter@398:       _where(graph),
kpeter@398:       _level(graph,0),
alpar@394:       _items(_max_level),
alpar@394:       _first(_max_level+2),
alpar@394:       _last_active(_max_level+2),
alpar@394:       _highest_active(-1) {}
alpar@394:     ///Constructor.
alpar@394: 
alpar@394:     ///Constructor.
alpar@394:     ///
kpeter@398:     ///\param graph The underlying graph.
kpeter@398:     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
alpar@394:     ///where \c max_level is equal to the number of labeled items in the graph.
kpeter@606:     Elevator(const GR &graph) :
kpeter@398:       _g(graph),
kpeter@606:       _max_level(countItems<GR, Item>(graph)),
alpar@394:       _item_num(_max_level),
kpeter@398:       _where(graph),
kpeter@398:       _level(graph,0),
alpar@394:       _items(_max_level),
alpar@394:       _first(_max_level+2),
alpar@394:       _last_active(_max_level+2),
alpar@394:       _highest_active(-1)
alpar@394:     {
alpar@394:     }
alpar@394: 
alpar@394:     ///Activate item \c i.
alpar@394: 
alpar@394:     ///Activate item \c i.
alpar@394:     ///\pre Item \c i shouldn't be active before.
alpar@394:     void activate(Item i)
alpar@394:     {
alpar@394:       const int l=_level[i];
alpar@394:       swap(_where[i],++_last_active[l]);
alpar@394:       if(l>_highest_active) _highest_active=l;
alpar@394:     }
alpar@394: 
alpar@394:     ///Deactivate item \c i.
alpar@394: 
alpar@394:     ///Deactivate item \c i.
alpar@394:     ///\pre Item \c i must be active before.
alpar@394:     void deactivate(Item i)
alpar@394:     {
alpar@394:       swap(_where[i],_last_active[_level[i]]--);
alpar@394:       while(_highest_active>=0 &&
alpar@394:             _last_active[_highest_active]<_first[_highest_active])
alpar@394:         _highest_active--;
alpar@394:     }
alpar@394: 
alpar@394:     ///Query whether item \c i is active
alpar@394:     bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
alpar@394: 
alpar@394:     ///Return the level of item \c i.
alpar@394:     int operator[](Item i) const { return _level[i]; }
alpar@394: 
alpar@394:     ///Return the number of items on level \c l.
alpar@394:     int onLevel(int l) const
alpar@394:     {
alpar@1328:       return static_cast<int>(_first[l+1]-_first[l]);
alpar@394:     }
kpeter@398:     ///Return true if level \c l is empty.
alpar@394:     bool emptyLevel(int l) const
alpar@394:     {
alpar@394:       return _first[l+1]-_first[l]==0;
alpar@394:     }
alpar@394:     ///Return the number of items above level \c l.
alpar@394:     int aboveLevel(int l) const
alpar@394:     {
alpar@1328:       return static_cast<int>(_first[_max_level+1]-_first[l+1]);
alpar@394:     }
alpar@394:     ///Return the number of active items on level \c l.
alpar@394:     int activesOnLevel(int l) const
alpar@394:     {
alpar@1328:       return static_cast<int>(_last_active[l]-_first[l]+1);
alpar@394:     }
kpeter@398:     ///Return true if there is no active item on level \c l.
alpar@394:     bool activeFree(int l) const
alpar@394:     {
alpar@394:       return _last_active[l]<_first[l];
alpar@394:     }
alpar@394:     ///Return the maximum allowed level.
alpar@394:     int maxLevel() const
alpar@394:     {
alpar@394:       return _max_level;
alpar@394:     }
alpar@394: 
alpar@394:     ///\name Highest Active Item
alpar@394:     ///Functions for working with the highest level
alpar@394:     ///active item.
alpar@394: 
alpar@394:     ///@{
alpar@394: 
alpar@394:     ///Return a highest level active item.
alpar@394: 
kpeter@398:     ///Return a highest level active item or INVALID if there is no active
alpar@394:     ///item.
alpar@394:     Item highestActive() const
alpar@394:     {
alpar@394:       return _highest_active>=0?*_last_active[_highest_active]:INVALID;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Return the highest active level.
alpar@394: 
kpeter@398:     ///Return the level of the highest active item or -1 if there is no active
alpar@394:     ///item.
alpar@394:     int highestActiveLevel() const
alpar@394:     {
alpar@394:       return _highest_active;
alpar@394:     }
alpar@394: 
alpar@394:     ///Lift the highest active item by one.
alpar@394: 
alpar@394:     ///Lift the item returned by highestActive() by one.
alpar@394:     ///
alpar@394:     void liftHighestActive()
alpar@394:     {
alpar@397:       Item it = *_last_active[_highest_active];
kpeter@628:       ++_level[it];
alpar@394:       swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
alpar@394:       --_first[++_highest_active];
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the highest active item to the given level.
alpar@394: 
alpar@394:     ///Lift the item returned by highestActive() to level \c new_level.
alpar@394:     ///
alpar@394:     ///\warning \c new_level must be strictly higher
alpar@394:     ///than the current level.
alpar@394:     ///
alpar@394:     void liftHighestActive(int new_level)
alpar@394:     {
alpar@394:       const Item li = *_last_active[_highest_active];
alpar@394: 
alpar@394:       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
alpar@394:       for(int l=_highest_active+1;l<new_level;l++)
alpar@394:         {
alpar@394:           copy(--_first[l+1],_first[l]);
alpar@394:           --_last_active[l];
alpar@394:         }
alpar@394:       copy(li,_first[new_level]);
kpeter@628:       _level[li] = new_level;
alpar@394:       _highest_active=new_level;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the highest active item to the top level.
alpar@394: 
alpar@394:     ///Lift the item returned by highestActive() to the top level and
kpeter@398:     ///deactivate it.
alpar@394:     void liftHighestActiveToTop()
alpar@394:     {
alpar@394:       const Item li = *_last_active[_highest_active];
alpar@394: 
alpar@394:       copy(--_first[_highest_active+1],_last_active[_highest_active]--);
alpar@394:       for(int l=_highest_active+1;l<_max_level;l++)
alpar@394:         {
alpar@394:           copy(--_first[l+1],_first[l]);
alpar@394:           --_last_active[l];
alpar@394:         }
alpar@394:       copy(li,_first[_max_level]);
alpar@394:       --_last_active[_max_level];
kpeter@628:       _level[li] = _max_level;
alpar@394: 
alpar@394:       while(_highest_active>=0 &&
alpar@394:             _last_active[_highest_active]<_first[_highest_active])
alpar@394:         _highest_active--;
alpar@394:     }
alpar@394: 
alpar@394:     ///@}
alpar@394: 
alpar@394:     ///\name Active Item on Certain Level
alpar@394:     ///Functions for working with the active items.
alpar@394: 
alpar@394:     ///@{
alpar@394: 
kpeter@398:     ///Return an active item on level \c l.
alpar@394: 
kpeter@398:     ///Return an active item on level \c l or \ref INVALID if there is no such
alpar@394:     ///an item. (\c l must be from the range [0...\c max_level].
alpar@394:     Item activeOn(int l) const
alpar@394:     {
alpar@394:       return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the active item returned by \c activeOn(level) by one.
alpar@394: 
kpeter@398:     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
alpar@394:     ///by one.
alpar@394:     Item liftActiveOn(int level)
alpar@394:     {
alpar@397:       Item it =*_last_active[level];
kpeter@628:       ++_level[it];
alpar@394:       swap(_last_active[level]--, --_first[level+1]);
alpar@394:       if (level+1>_highest_active) ++_highest_active;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the active item returned by \c activeOn(level) to the given level.
alpar@394: 
kpeter@398:     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
alpar@394:     ///to the given level.
alpar@394:     void liftActiveOn(int level, int new_level)
alpar@394:     {
alpar@394:       const Item ai = *_last_active[level];
alpar@394: 
alpar@394:       copy(--_first[level+1], _last_active[level]--);
alpar@394:       for(int l=level+1;l<new_level;l++)
alpar@394:         {
alpar@394:           copy(_last_active[l],_first[l]);
alpar@394:           copy(--_first[l+1], _last_active[l]--);
alpar@394:         }
alpar@394:       copy(ai,_first[new_level]);
kpeter@628:       _level[ai] = new_level;
alpar@394:       if (new_level>_highest_active) _highest_active=new_level;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the active item returned by \c activeOn(level) to the top level.
alpar@394: 
kpeter@398:     ///Lift the active item returned by \ref activeOn() "activeOn(level)"
kpeter@398:     ///to the top level and deactivate it.
alpar@394:     void liftActiveToTop(int level)
alpar@394:     {
alpar@394:       const Item ai = *_last_active[level];
alpar@394: 
alpar@394:       copy(--_first[level+1],_last_active[level]--);
alpar@394:       for(int l=level+1;l<_max_level;l++)
alpar@394:         {
alpar@394:           copy(_last_active[l],_first[l]);
alpar@394:           copy(--_first[l+1], _last_active[l]--);
alpar@394:         }
alpar@394:       copy(ai,_first[_max_level]);
alpar@394:       --_last_active[_max_level];
kpeter@628:       _level[ai] = _max_level;
alpar@394: 
alpar@394:       if (_highest_active==level) {
alpar@394:         while(_highest_active>=0 &&
alpar@394:               _last_active[_highest_active]<_first[_highest_active])
alpar@394:           _highest_active--;
alpar@394:       }
alpar@394:     }
alpar@394: 
alpar@394:     ///@}
alpar@394: 
alpar@394:     ///Lift an active item to a higher level.
alpar@394: 
alpar@394:     ///Lift an active item to a higher level.
alpar@394:     ///\param i The item to be lifted. It must be active.
alpar@394:     ///\param new_level The new level of \c i. It must be strictly higher
alpar@394:     ///than the current level.
alpar@394:     ///
alpar@394:     void lift(Item i, int new_level)
alpar@394:     {
alpar@394:       const int lo = _level[i];
alpar@394:       const Vit w = _where[i];
alpar@394: 
alpar@394:       copy(_last_active[lo],w);
alpar@394:       copy(--_first[lo+1],_last_active[lo]--);
alpar@394:       for(int l=lo+1;l<new_level;l++)
alpar@394:         {
alpar@394:           copy(_last_active[l],_first[l]);
alpar@394:           copy(--_first[l+1],_last_active[l]--);
alpar@394:         }
alpar@394:       copy(i,_first[new_level]);
kpeter@628:       _level[i] = new_level;
alpar@394:       if(new_level>_highest_active) _highest_active=new_level;
alpar@394:     }
alpar@394: 
alpar@395:     ///Move an inactive item to the top but one level (in a dirty way).
alpar@394: 
kpeter@398:     ///This function moves an inactive item from the top level to the top
kpeter@398:     ///but one level (in a dirty way).
kpeter@398:     ///\warning It makes the underlying datastructure corrupt, so use it
kpeter@398:     ///only if you really know what it is for.
alpar@395:     ///\pre The item is on the top level.
alpar@395:     void dirtyTopButOne(Item i) {
kpeter@628:       _level[i] = _max_level - 1;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift all items on and above the given level to the top level.
alpar@394: 
kpeter@398:     ///This function lifts all items on and above level \c l to the top
kpeter@398:     ///level and deactivates them.
alpar@394:     void liftToTop(int l)
alpar@394:     {
alpar@394:       const Vit f=_first[l];
alpar@394:       const Vit tl=_first[_max_level];
alpar@394:       for(Vit i=f;i!=tl;++i)
kpeter@628:         _level[*i] = _max_level;
alpar@394:       for(int i=l;i<=_max_level;i++)
alpar@394:         {
alpar@394:           _first[i]=f;
alpar@394:           _last_active[i]=f-1;
alpar@394:         }
alpar@394:       for(_highest_active=l-1;
alpar@394:           _highest_active>=0 &&
alpar@394:             _last_active[_highest_active]<_first[_highest_active];
alpar@394:           _highest_active--) ;
alpar@394:     }
alpar@394: 
alpar@394:   private:
alpar@394:     int _init_lev;
alpar@394:     Vit _init_num;
alpar@394: 
alpar@394:   public:
alpar@394: 
alpar@394:     ///\name Initialization
kpeter@398:     ///Using these functions you can initialize the levels of the items.
alpar@394:     ///\n
kpeter@398:     ///The initialization must be started with calling \c initStart().
kpeter@398:     ///Then the items should be listed level by level starting with the
kpeter@398:     ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
kpeter@398:     ///Finally \c initFinish() must be called.
kpeter@398:     ///The items not listed are put on the highest level.
alpar@394:     ///@{
alpar@394: 
alpar@394:     ///Start the initialization process.
alpar@394:     void initStart()
alpar@394:     {
alpar@394:       _init_lev=0;
alpar@396:       _init_num=&_items[0];
alpar@396:       _first[0]=&_items[0];
alpar@396:       _last_active[0]=&_items[0]-1;
alpar@396:       Vit n=&_items[0];
kpeter@606:       for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
alpar@394:         {
alpar@394:           *n=i;
kpeter@628:           _where[i] = n;
kpeter@628:           _level[i] = _max_level;
alpar@394:           ++n;
alpar@394:         }
alpar@394:     }
alpar@394: 
alpar@394:     ///Add an item to the current level.
alpar@394:     void initAddItem(Item i)
alpar@394:     {
alpar@397:       swap(_where[i],_init_num);
kpeter@628:       _level[i] = _init_lev;
alpar@394:       ++_init_num;
alpar@394:     }
alpar@394: 
alpar@394:     ///Start a new level.
alpar@394: 
alpar@394:     ///Start a new level.
alpar@394:     ///It shouldn't be used before the items on level 0 are listed.
alpar@394:     void initNewLevel()
alpar@394:     {
alpar@394:       _init_lev++;
alpar@394:       _first[_init_lev]=_init_num;
alpar@394:       _last_active[_init_lev]=_init_num-1;
alpar@394:     }
alpar@394: 
alpar@394:     ///Finalize the initialization process.
alpar@394:     void initFinish()
alpar@394:     {
alpar@394:       for(_init_lev++;_init_lev<=_max_level;_init_lev++)
alpar@394:         {
alpar@394:           _first[_init_lev]=_init_num;
alpar@394:           _last_active[_init_lev]=_init_num-1;
alpar@394:         }
alpar@396:       _first[_max_level+1]=&_items[0]+_item_num;
alpar@396:       _last_active[_max_level+1]=&_items[0]+_item_num-1;
alpar@394:       _highest_active = -1;
alpar@394:     }
alpar@394: 
alpar@394:     ///@}
alpar@394: 
alpar@394:   };
alpar@394: 
alpar@394:   ///Class for handling "labels" in push-relabel type algorithms.
alpar@394: 
alpar@394:   ///A class for handling "labels" in push-relabel type algorithms.
alpar@394:   ///
alpar@394:   ///\ingroup auxdat
alpar@394:   ///Using this class you can assign "labels" (nonnegative integer numbers)
alpar@394:   ///to the edges or nodes of a graph, manipulate and query them through
alpar@394:   ///operations typically arising in "push-relabel" type algorithms.
alpar@394:   ///
alpar@394:   ///Each item is either \em active or not, and you can also choose a
alpar@394:   ///highest level active item.
alpar@394:   ///
alpar@394:   ///\sa Elevator
alpar@394:   ///
kpeter@606:   ///\param GR Type of the underlying graph.
kpeter@606:   ///\param Item Type of the items the data is assigned to (\c GR::Node,
kpeter@606:   ///\c GR::Arc or \c GR::Edge).
kpeter@606:   template <class GR, class Item>
alpar@394:   class LinkedElevator {
alpar@394:   public:
alpar@394: 
alpar@394:     typedef Item Key;
alpar@394:     typedef int Value;
alpar@394: 
alpar@394:   private:
alpar@394: 
kpeter@606:     typedef typename ItemSetTraits<GR,Item>::
alpar@394:     template Map<Item>::Type ItemMap;
kpeter@606:     typedef typename ItemSetTraits<GR,Item>::
alpar@394:     template Map<int>::Type IntMap;
kpeter@606:     typedef typename ItemSetTraits<GR,Item>::
alpar@394:     template Map<bool>::Type BoolMap;
alpar@394: 
kpeter@606:     const GR &_graph;
alpar@394:     int _max_level;
alpar@394:     int _item_num;
alpar@394:     std::vector<Item> _first, _last;
alpar@394:     ItemMap _prev, _next;
alpar@394:     int _highest_active;
alpar@394:     IntMap _level;
alpar@394:     BoolMap _active;
alpar@394: 
alpar@394:   public:
alpar@394:     ///Constructor with given maximum level.
alpar@394: 
alpar@394:     ///Constructor with given maximum level.
alpar@394:     ///
kpeter@398:     ///\param graph The underlying graph.
kpeter@398:     ///\param max_level The maximum allowed level.
kpeter@398:     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
kpeter@606:     LinkedElevator(const GR& graph, int max_level)
alpar@394:       : _graph(graph), _max_level(max_level), _item_num(_max_level),
alpar@394:         _first(_max_level + 1), _last(_max_level + 1),
alpar@394:         _prev(graph), _next(graph),
alpar@394:         _highest_active(-1), _level(graph), _active(graph) {}
alpar@394: 
alpar@394:     ///Constructor.
alpar@394: 
alpar@394:     ///Constructor.
alpar@394:     ///
kpeter@398:     ///\param graph The underlying graph.
kpeter@398:     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
alpar@394:     ///where \c max_level is equal to the number of labeled items in the graph.
kpeter@606:     LinkedElevator(const GR& graph)
kpeter@606:       : _graph(graph), _max_level(countItems<GR, Item>(graph)),
alpar@394:         _item_num(_max_level),
alpar@394:         _first(_max_level + 1), _last(_max_level + 1),
alpar@394:         _prev(graph, INVALID), _next(graph, INVALID),
alpar@394:         _highest_active(-1), _level(graph), _active(graph) {}
alpar@394: 
alpar@394: 
alpar@394:     ///Activate item \c i.
alpar@394: 
alpar@394:     ///Activate item \c i.
alpar@394:     ///\pre Item \c i shouldn't be active before.
alpar@394:     void activate(Item i) {
kpeter@628:       _active[i] = true;
alpar@394: 
alpar@394:       int level = _level[i];
alpar@394:       if (level > _highest_active) {
alpar@394:         _highest_active = level;
alpar@394:       }
alpar@394: 
alpar@394:       if (_prev[i] == INVALID || _active[_prev[i]]) return;
alpar@394:       //unlace
kpeter@628:       _next[_prev[i]] = _next[i];
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = _prev[i];
alpar@394:       } else {
alpar@394:         _last[level] = _prev[i];
alpar@394:       }
alpar@394:       //lace
kpeter@628:       _next[i] = _first[level];
kpeter@628:       _prev[_first[level]] = i;
kpeter@628:       _prev[i] = INVALID;
alpar@394:       _first[level] = i;
alpar@394: 
alpar@394:     }
alpar@394: 
alpar@394:     ///Deactivate item \c i.
alpar@394: 
alpar@394:     ///Deactivate item \c i.
alpar@394:     ///\pre Item \c i must be active before.
alpar@394:     void deactivate(Item i) {
kpeter@628:       _active[i] = false;
alpar@394:       int level = _level[i];
alpar@394: 
alpar@394:       if (_next[i] == INVALID || !_active[_next[i]])
alpar@394:         goto find_highest_level;
alpar@394: 
alpar@394:       //unlace
kpeter@628:       _prev[_next[i]] = _prev[i];
alpar@394:       if (_prev[i] != INVALID) {
kpeter@628:         _next[_prev[i]] = _next[i];
alpar@394:       } else {
alpar@394:         _first[_level[i]] = _next[i];
alpar@394:       }
alpar@394:       //lace
kpeter@628:       _prev[i] = _last[level];
kpeter@628:       _next[_last[level]] = i;
kpeter@628:       _next[i] = INVALID;
alpar@394:       _last[level] = i;
alpar@394: 
alpar@394:     find_highest_level:
alpar@394:       if (level == _highest_active) {
alpar@394:         while (_highest_active >= 0 && activeFree(_highest_active))
alpar@394:           --_highest_active;
alpar@394:       }
alpar@394:     }
alpar@394: 
alpar@394:     ///Query whether item \c i is active
alpar@394:     bool active(Item i) const { return _active[i]; }
alpar@394: 
alpar@394:     ///Return the level of item \c i.
alpar@394:     int operator[](Item i) const { return _level[i]; }
alpar@394: 
alpar@394:     ///Return the number of items on level \c l.
alpar@394:     int onLevel(int l) const {
alpar@394:       int num = 0;
alpar@394:       Item n = _first[l];
alpar@394:       while (n != INVALID) {
alpar@394:         ++num;
alpar@394:         n = _next[n];
alpar@394:       }
alpar@394:       return num;
alpar@394:     }
alpar@394: 
alpar@394:     ///Return true if the level is empty.
alpar@394:     bool emptyLevel(int l) const {
alpar@394:       return _first[l] == INVALID;
alpar@394:     }
alpar@394: 
alpar@394:     ///Return the number of items above level \c l.
alpar@394:     int aboveLevel(int l) const {
alpar@394:       int num = 0;
alpar@394:       for (int level = l + 1; level < _max_level; ++level)
alpar@394:         num += onLevel(level);
alpar@394:       return num;
alpar@394:     }
alpar@394: 
alpar@394:     ///Return the number of active items on level \c l.
alpar@394:     int activesOnLevel(int l) const {
alpar@394:       int num = 0;
alpar@394:       Item n = _first[l];
alpar@394:       while (n != INVALID && _active[n]) {
alpar@394:         ++num;
alpar@394:         n = _next[n];
alpar@394:       }
alpar@394:       return num;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Return true if there is no active item on level \c l.
alpar@394:     bool activeFree(int l) const {
alpar@394:       return _first[l] == INVALID || !_active[_first[l]];
alpar@394:     }
alpar@394: 
alpar@394:     ///Return the maximum allowed level.
alpar@394:     int maxLevel() const {
alpar@394:       return _max_level;
alpar@394:     }
alpar@394: 
alpar@394:     ///\name Highest Active Item
alpar@394:     ///Functions for working with the highest level
alpar@394:     ///active item.
alpar@394: 
alpar@394:     ///@{
alpar@394: 
alpar@394:     ///Return a highest level active item.
alpar@394: 
kpeter@398:     ///Return a highest level active item or INVALID if there is no active
kpeter@398:     ///item.
alpar@394:     Item highestActive() const {
alpar@394:       return _highest_active >= 0 ? _first[_highest_active] : INVALID;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Return the highest active level.
alpar@394: 
kpeter@398:     ///Return the level of the highest active item or -1 if there is no active
kpeter@398:     ///item.
alpar@394:     int highestActiveLevel() const {
alpar@394:       return _highest_active;
alpar@394:     }
alpar@394: 
alpar@394:     ///Lift the highest active item by one.
alpar@394: 
alpar@394:     ///Lift the item returned by highestActive() by one.
alpar@394:     ///
alpar@394:     void liftHighestActive() {
alpar@394:       Item i = _first[_highest_active];
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = INVALID;
alpar@394:         _first[_highest_active] = _next[i];
alpar@394:       } else {
alpar@394:         _first[_highest_active] = INVALID;
alpar@394:         _last[_highest_active] = INVALID;
alpar@394:       }
kpeter@628:       _level[i] = ++_highest_active;
alpar@394:       if (_first[_highest_active] == INVALID) {
alpar@394:         _first[_highest_active] = i;
alpar@394:         _last[_highest_active] = i;
kpeter@628:         _prev[i] = INVALID;
kpeter@628:         _next[i] = INVALID;
alpar@394:       } else {
kpeter@628:         _prev[_first[_highest_active]] = i;
kpeter@628:         _next[i] = _first[_highest_active];
alpar@394:         _first[_highest_active] = i;
alpar@394:       }
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the highest active item to the given level.
alpar@394: 
alpar@394:     ///Lift the item returned by highestActive() to level \c new_level.
alpar@394:     ///
alpar@394:     ///\warning \c new_level must be strictly higher
alpar@394:     ///than the current level.
alpar@394:     ///
alpar@394:     void liftHighestActive(int new_level) {
alpar@394:       Item i = _first[_highest_active];
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = INVALID;
alpar@394:         _first[_highest_active] = _next[i];
alpar@394:       } else {
alpar@394:         _first[_highest_active] = INVALID;
alpar@394:         _last[_highest_active] = INVALID;
alpar@394:       }
kpeter@628:       _level[i] = _highest_active = new_level;
alpar@394:       if (_first[_highest_active] == INVALID) {
alpar@394:         _first[_highest_active] = _last[_highest_active] = i;
kpeter@628:         _prev[i] = INVALID;
kpeter@628:         _next[i] = INVALID;
alpar@394:       } else {
kpeter@628:         _prev[_first[_highest_active]] = i;
kpeter@628:         _next[i] = _first[_highest_active];
alpar@394:         _first[_highest_active] = i;
alpar@394:       }
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the highest active item to the top level.
alpar@394: 
alpar@394:     ///Lift the item returned by highestActive() to the top level and
kpeter@398:     ///deactivate it.
alpar@394:     void liftHighestActiveToTop() {
alpar@394:       Item i = _first[_highest_active];
kpeter@628:       _level[i] = _max_level;
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = INVALID;
alpar@394:         _first[_highest_active] = _next[i];
alpar@394:       } else {
alpar@394:         _first[_highest_active] = INVALID;
alpar@394:         _last[_highest_active] = INVALID;
alpar@394:       }
alpar@394:       while (_highest_active >= 0 && activeFree(_highest_active))
alpar@394:         --_highest_active;
alpar@394:     }
alpar@394: 
alpar@394:     ///@}
alpar@394: 
alpar@394:     ///\name Active Item on Certain Level
alpar@394:     ///Functions for working with the active items.
alpar@394: 
alpar@394:     ///@{
alpar@394: 
kpeter@398:     ///Return an active item on level \c l.
alpar@394: 
kpeter@398:     ///Return an active item on level \c l or \ref INVALID if there is no such
alpar@394:     ///an item. (\c l must be from the range [0...\c max_level].
alpar@394:     Item activeOn(int l) const
alpar@394:     {
alpar@394:       return _active[_first[l]] ? _first[l] : INVALID;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the active item returned by \c activeOn(l) by one.
alpar@394: 
kpeter@398:     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
alpar@394:     ///by one.
alpar@394:     Item liftActiveOn(int l)
alpar@394:     {
alpar@394:       Item i = _first[l];
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = INVALID;
alpar@394:         _first[l] = _next[i];
alpar@394:       } else {
alpar@394:         _first[l] = INVALID;
alpar@394:         _last[l] = INVALID;
alpar@394:       }
kpeter@628:       _level[i] = ++l;
alpar@394:       if (_first[l] == INVALID) {
alpar@394:         _first[l] = _last[l] = i;
kpeter@628:         _prev[i] = INVALID;
kpeter@628:         _next[i] = INVALID;
alpar@394:       } else {
kpeter@628:         _prev[_first[l]] = i;
kpeter@628:         _next[i] = _first[l];
alpar@394:         _first[l] = i;
alpar@394:       }
alpar@394:       if (_highest_active < l) {
alpar@394:         _highest_active = l;
alpar@394:       }
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the active item returned by \c activeOn(l) to the given level.
kpeter@398: 
kpeter@398:     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
kpeter@398:     ///to the given level.
alpar@394:     void liftActiveOn(int l, int new_level)
alpar@394:     {
alpar@394:       Item i = _first[l];
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = INVALID;
alpar@394:         _first[l] = _next[i];
alpar@394:       } else {
alpar@394:         _first[l] = INVALID;
alpar@394:         _last[l] = INVALID;
alpar@394:       }
kpeter@628:       _level[i] = l = new_level;
alpar@394:       if (_first[l] == INVALID) {
alpar@394:         _first[l] = _last[l] = i;
kpeter@628:         _prev[i] = INVALID;
kpeter@628:         _next[i] = INVALID;
alpar@394:       } else {
kpeter@628:         _prev[_first[l]] = i;
kpeter@628:         _next[i] = _first[l];
alpar@394:         _first[l] = i;
alpar@394:       }
alpar@394:       if (_highest_active < l) {
alpar@394:         _highest_active = l;
alpar@394:       }
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift the active item returned by \c activeOn(l) to the top level.
alpar@394: 
kpeter@398:     ///Lift the active item returned by \ref activeOn() "activeOn(l)"
kpeter@398:     ///to the top level and deactivate it.
alpar@394:     void liftActiveToTop(int l)
alpar@394:     {
alpar@394:       Item i = _first[l];
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = INVALID;
alpar@394:         _first[l] = _next[i];
alpar@394:       } else {
alpar@394:         _first[l] = INVALID;
alpar@394:         _last[l] = INVALID;
alpar@394:       }
kpeter@628:       _level[i] = _max_level;
alpar@394:       if (l == _highest_active) {
alpar@394:         while (_highest_active >= 0 && activeFree(_highest_active))
alpar@394:           --_highest_active;
alpar@394:       }
alpar@394:     }
alpar@394: 
alpar@394:     ///@}
alpar@394: 
alpar@394:     /// \brief Lift an active item to a higher level.
alpar@394:     ///
alpar@394:     /// Lift an active item to a higher level.
alpar@394:     /// \param i The item to be lifted. It must be active.
alpar@394:     /// \param new_level The new level of \c i. It must be strictly higher
alpar@394:     /// than the current level.
alpar@394:     ///
alpar@394:     void lift(Item i, int new_level) {
alpar@394:       if (_next[i] != INVALID) {
kpeter@628:         _prev[_next[i]] = _prev[i];
alpar@394:       } else {
alpar@394:         _last[new_level] = _prev[i];
alpar@394:       }
alpar@394:       if (_prev[i] != INVALID) {
kpeter@628:         _next[_prev[i]] = _next[i];
alpar@394:       } else {
alpar@394:         _first[new_level] = _next[i];
alpar@394:       }
kpeter@628:       _level[i] = new_level;
alpar@394:       if (_first[new_level] == INVALID) {
alpar@394:         _first[new_level] = _last[new_level] = i;
kpeter@628:         _prev[i] = INVALID;
kpeter@628:         _next[i] = INVALID;
alpar@394:       } else {
kpeter@628:         _prev[_first[new_level]] = i;
kpeter@628:         _next[i] = _first[new_level];
alpar@394:         _first[new_level] = i;
alpar@394:       }
alpar@394:       if (_highest_active < new_level) {
alpar@394:         _highest_active = new_level;
alpar@394:       }
alpar@394:     }
alpar@394: 
alpar@395:     ///Move an inactive item to the top but one level (in a dirty way).
alpar@394: 
kpeter@398:     ///This function moves an inactive item from the top level to the top
kpeter@398:     ///but one level (in a dirty way).
kpeter@398:     ///\warning It makes the underlying datastructure corrupt, so use it
kpeter@398:     ///only if you really know what it is for.
alpar@395:     ///\pre The item is on the top level.
alpar@395:     void dirtyTopButOne(Item i) {
kpeter@628:       _level[i] = _max_level - 1;
alpar@394:     }
alpar@394: 
kpeter@398:     ///Lift all items on and above the given level to the top level.
alpar@394: 
kpeter@398:     ///This function lifts all items on and above level \c l to the top
kpeter@398:     ///level and deactivates them.
alpar@394:     void liftToTop(int l)  {
alpar@394:       for (int i = l + 1; _first[i] != INVALID; ++i) {
alpar@394:         Item n = _first[i];
alpar@394:         while (n != INVALID) {
kpeter@628:           _level[n] = _max_level;
alpar@394:           n = _next[n];
alpar@394:         }
alpar@394:         _first[i] = INVALID;
alpar@394:         _last[i] = INVALID;
alpar@394:       }
alpar@394:       if (_highest_active > l - 1) {
alpar@394:         _highest_active = l - 1;
alpar@394:         while (_highest_active >= 0 && activeFree(_highest_active))
alpar@394:           --_highest_active;
alpar@394:       }
alpar@394:     }
alpar@394: 
alpar@394:   private:
alpar@394: 
alpar@394:     int _init_level;
alpar@394: 
alpar@394:   public:
alpar@394: 
alpar@394:     ///\name Initialization
kpeter@398:     ///Using these functions you can initialize the levels of the items.
alpar@394:     ///\n
kpeter@398:     ///The initialization must be started with calling \c initStart().
kpeter@398:     ///Then the items should be listed level by level starting with the
kpeter@398:     ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
kpeter@398:     ///Finally \c initFinish() must be called.
kpeter@398:     ///The items not listed are put on the highest level.
alpar@394:     ///@{
alpar@394: 
alpar@394:     ///Start the initialization process.
alpar@394:     void initStart() {
alpar@394: 
alpar@394:       for (int i = 0; i <= _max_level; ++i) {
alpar@394:         _first[i] = _last[i] = INVALID;
alpar@394:       }
alpar@394:       _init_level = 0;
kpeter@606:       for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
alpar@394:           i != INVALID; ++i) {
kpeter@628:         _level[i] = _max_level;
kpeter@628:         _active[i] = false;
alpar@394:       }
alpar@394:     }
alpar@394: 
alpar@394:     ///Add an item to the current level.
alpar@394:     void initAddItem(Item i) {
kpeter@628:       _level[i] = _init_level;
alpar@394:       if (_last[_init_level] == INVALID) {
alpar@394:         _first[_init_level] = i;
alpar@394:         _last[_init_level] = i;
kpeter@628:         _prev[i] = INVALID;
kpeter@628:         _next[i] = INVALID;
alpar@394:       } else {
kpeter@628:         _prev[i] = _last[_init_level];
kpeter@628:         _next[i] = INVALID;
kpeter@628:         _next[_last[_init_level]] = i;
alpar@394:         _last[_init_level] = i;
alpar@394:       }
alpar@394:     }
alpar@394: 
alpar@394:     ///Start a new level.
alpar@394: 
alpar@394:     ///Start a new level.
alpar@394:     ///It shouldn't be used before the items on level 0 are listed.
alpar@394:     void initNewLevel() {
alpar@394:       ++_init_level;
alpar@394:     }
alpar@394: 
alpar@394:     ///Finalize the initialization process.
alpar@394:     void initFinish() {
alpar@394:       _highest_active = -1;
alpar@394:     }
alpar@394: 
alpar@394:     ///@}
alpar@394: 
alpar@394:   };
alpar@394: 
alpar@394: 
alpar@394: } //END OF NAMESPACE LEMON
alpar@394: 
alpar@394: #endif
alpar@394: