RhodeCode

///\brief Elevator class

///

///Elevator class implements an efficient data structure

///for labeling items in push-relabel type algorithms.

///

namespace lemon {

  ///Class for handling "labels" in push-relabel type algorithms.

  ///A class for handling "labels" in push-relabel type algorithms.

  ///

  ///

  ///Each item is either \em active or not, and you can also choose a

  ///highest level active item.

  ///

  ///\sa LinkedElevator

  ///

  ///\param Item Type of the items the data is assigned to (Graph::Node,

  template<class Graph, class Item>

  class Elevator

  {

  public:

    typedef Item Key;

  public:

    ///Constructor with given maximum level.

    ///Constructor with given maximum level.

    ///

      _max_level(max_level),

      _item_num(_max_level),

      _items(_max_level),

      _first(_max_level+2),

      _last_active(_max_level+2),

      _highest_active(-1) {}

    ///Constructor.

    ///Constructor.

    ///

    ///where \c max_level is equal to the number of labeled items in the graph.

      _item_num(_max_level),

      _items(_max_level),

      _first(_max_level+2),

      _last_active(_max_level+2),

      _highest_active(-1)

    {

    }

    ///Return the number of items on level \c l.

    int onLevel(int l) const

    {

      return _first[l+1]-_first[l];

    }

    bool emptyLevel(int l) const

    {

      return _first[l+1]-_first[l]==0;

    }

    ///Return the number of items above level \c l.

    int aboveLevel(int l) const

    }

    ///Return the number of active items on level \c l.

    int activesOnLevel(int l) const

    {

      return _last_active[l]-_first[l]+1;

    }

    bool activeFree(int l) const

    {

      return _last_active[l]<_first[l];

    }

    ///Return the maximum allowed level.

    int maxLevel() const

    ///active item.

    ///@{

    ///Return a highest level active item.

    ///item.

    Item highestActive() const

    {

      return _highest_active>=0?*_last_active[_highest_active]:INVALID;

    }

    ///item.

    int highestActiveLevel() const

    {

      return _highest_active;

    }

      Item it = *_last_active[_highest_active];

      _level.set(it,_level[it]+1);

      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);

      --_first[++_highest_active];

    }

    ///Lift the item returned by highestActive() to level \c new_level.

    ///

    ///\warning \c new_level must be strictly higher

    ///than the current level.

    ///

        }

      copy(li,_first[new_level]);

      _level.set(li,new_level);

      _highest_active=new_level;

    }

    ///Lift the item returned by highestActive() to the top level and

    void liftHighestActiveToTop()

    {

      const Item li = *_last_active[_highest_active];

      copy(--_first[_highest_active+1],_last_active[_highest_active]--);

      for(int l=_highest_active+1;l<_max_level;l++)

    ///\name Active Item on Certain Level

    ///Functions for working with the active items.

    ///@{

    ///an item. (\c l must be from the range [0...\c max_level].

    Item activeOn(int l) const

    {

      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;

    }

    ///by one.

    Item liftActiveOn(int level)

    {

      Item it =*_last_active[level];

      _level.set(it,_level[it]+1);

      swap(_last_active[level]--, --_first[level+1]);

      if (level+1>_highest_active) ++_highest_active;

    }

    ///to the given level.

    void liftActiveOn(int level, int new_level)

    {

      const Item ai = *_last_active[level];

      copy(--_first[level+1], _last_active[level]--);

        }

      copy(ai,_first[new_level]);

      _level.set(ai,new_level);

      if (new_level>_highest_active) _highest_active=new_level;

    }

    void liftActiveToTop(int level)

    {

      const Item ai = *_last_active[level];

      copy(--_first[level+1],_last_active[level]--);

      for(int l=level+1;l<_max_level;l++)

      _level.set(i,new_level);

      if(new_level>_highest_active) _highest_active=new_level;

    }

    ///Move an inactive item to the top but one level (in a dirty way).

    ///\pre The item is on the top level.

    void dirtyTopButOne(Item i) {

      _level.set(i,_max_level - 1);

    }

    void liftToTop(int l)

    {

      const Vit f=_first[l];

      const Vit tl=_first[_max_level];

      for(Vit i=f;i!=tl;++i)

        _level.set(*i,_max_level);

    int _init_lev;

    Vit _init_num;

  public:

    ///\name Initialization

    ///\n

    ///@{

    ///Start the initialization process.

    void initStart()

    {

      _init_lev=0;

      _init_num=&_items[0];

      _first[0]=&_items[0];

      _last_active[0]=&_items[0]-1;

          _level.set(i,_max_level);

          ++n;

        }

    }

    ///Add an item to the current level.

    void initAddItem(Item i)

    {

      swap(_where[i],_init_num);

      _level.set(i,_init_lev);

      ++_init_num;

    }

      _init_lev++;

      _first[_init_lev]=_init_num;

      _last_active[_init_lev]=_init_num-1;

    }

    ///Finalize the initialization process.

    void initFinish()

    {

      for(_init_lev++;_init_lev<=_max_level;_init_lev++)

        {

          _first[_init_lev]=_init_num;

          _last_active[_init_lev]=_init_num-1;

  ///

  ///Each item is either \em active or not, and you can also choose a

  ///highest level active item.

  ///

  ///\sa Elevator

  ///

  ///\param Item Type of the items the data is assigned to (Graph::Node,

  template <class Graph, class Item>

  class LinkedElevator {

  public:

    typedef Item Key;

    typedef int Value;

  public:

    ///Constructor with given maximum level.

    ///Constructor with given maximum level.

    ///

    LinkedElevator(const Graph& graph, int max_level)

      : _graph(graph), _max_level(max_level), _item_num(_max_level),

        _first(_max_level + 1), _last(_max_level + 1),

        _prev(graph), _next(graph),

        _highest_active(-1), _level(graph), _active(graph) {}

    ///Constructor.

    ///Constructor.

    ///

    ///where \c max_level is equal to the number of labeled items in the graph.

    LinkedElevator(const Graph& graph)

      : _graph(graph), _max_level(countItems<Graph, Item>(graph)),

        _item_num(_max_level),

        _first(_max_level + 1), _last(_max_level + 1),

        _prev(graph, INVALID), _next(graph, INVALID),

        ++num;

        n = _next[n];

      }

      return num;

    }

    bool activeFree(int l) const {

      return _first[l] == INVALID || !_active[_first[l]];

    }

    ///Return the maximum allowed level.

    int maxLevel() const {

    ///active item.

    ///@{

    ///Return a highest level active item.

    Item highestActive() const {

      return _highest_active >= 0 ? _first[_highest_active] : INVALID;

    }

    int highestActiveLevel() const {

      return _highest_active;

    }

    ///Lift the highest active item by one.

        _prev.set(_first[_highest_active], i);

        _next.set(i, _first[_highest_active]);

        _first[_highest_active] = i;

      }

    }

    ///Lift the item returned by highestActive() to level \c new_level.

    ///

    ///\warning \c new_level must be strictly higher

    ///than the current level.

    ///

        _prev.set(_first[_highest_active], i);

        _next.set(i, _first[_highest_active]);

        _first[_highest_active] = i;

      }

    }

    ///Lift the item returned by highestActive() to the top level and

    void liftHighestActiveToTop() {

      Item i = _first[_highest_active];

      _level.set(i, _max_level);

      if (_next[i] != INVALID) {

        _prev.set(_next[i], INVALID);

        _first[_highest_active] = _next[i];

    ///\name Active Item on Certain Level

    ///Functions for working with the active items.

    ///@{

    ///an item. (\c l must be from the range [0...\c max_level].

    Item activeOn(int l) const

    {

      return _active[_first[l]] ? _first[l] : INVALID;

    }

    ///by one.

    Item liftActiveOn(int l)

    {

      Item i = _first[l];

      if (_next[i] != INVALID) {

        _prev.set(_next[i], INVALID);

      }

      if (_highest_active < l) {

        _highest_active = l;

      }

    }

    void liftActiveOn(int l, int new_level)

    {

      Item i = _first[l];

      if (_next[i] != INVALID) {

        _prev.set(_next[i], INVALID);

        _first[l] = _next[i];

      }

      if (_highest_active < l) {

        _highest_active = l;

      }

    }

    void liftActiveToTop(int l)

    {

      Item i = _first[l];

      if (_next[i] != INVALID) {

        _prev.set(_next[i], INVALID);

        _first[l] = _next[i];

        _highest_active = new_level;

      }

    }

    ///Move an inactive item to the top but one level (in a dirty way).

    ///\pre The item is on the top level.

    void dirtyTopButOne(Item i) {

      _level.set(i, _max_level - 1);

    }

    void liftToTop(int l)  {

      for (int i = l + 1; _first[i] != INVALID; ++i) {

        Item n = _first[i];

        while (n != INVALID) {

          _level.set(n, _max_level);

          n = _next[n];

    int _init_level;

  public:

    ///\name Initialization

    ///\n

    ///@{

    ///Start the initialization process.

    void initStart() {

      for (int i = 0; i <= _max_level; ++i) {

        _first[i] = _last[i] = INVALID;

      }

      _init_level = 0;

        _level.set(i, _max_level);

        _active.set(i, false);

      }

    }

    ///Add an item to the current level.

    void initAddItem(Item i) {

      _level.set(i, _init_level);

      if (_last[_init_level] == INVALID) {

        _first[_init_level] = i;

        _last[_init_level] = i;

        _prev.set(i, INVALID);

    ///It shouldn't be used before the items on level 0 are listed.

    void initNewLevel() {

      ++_init_level;

    }

    ///Finalize the initialization process.

    void initFinish() {

      _highest_active = -1;

    }

    ///@}