RhodeCode

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_ELEVATOR_H

#define LEMON_ELEVATOR_H

///\ingroup auxdat

///\file

///\brief Elevator class

///

///Elevator class implements an efficient data structure

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

///

#include <test/test_tools.h>

namespace lemon {

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

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

  ///

  ///\ingroup auxdat

  ///Using this class you can assign "labels" (nonnegative integer numbers)

  ///to the edges or nodes of a graph, manipulate and query them through

  ///operations typically arising 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 Graph the underlying graph type

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

  ///Graph::Edge, Graph::UEdge)

  template<class Graph, class Item>

  class Elevator

  {

  public:

    typedef Item Key;

    typedef int Value;

  private:

    typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;

    typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;

    const Graph &_g;

    int _max_level;

    int _item_num;

    VitMap _where;

    IntMap _level;

    std::vector<Item> _items;

    std::vector<Vit> _first;

    std::vector<Vit> _last_active;

    int _highest_active;

    void copy(Item i, Vit p)

    {

      _where[*p=i]=p;

    }

    void copy(Vit s, Vit p)

    {

      if(s!=p)

        {

          Item i=*s;

          *p=i;

          _where[i]=p;

        }

    }

    void swap(Vit i, Vit j)

    {

      Item ti=*i;

      Vit ct = _where[ti];

      _where[ti]=_where[*i=*j];

      _where[*j]=ct;

      *j=ti;

    }

  public:

    ///Constructor with given maximum level.

    ///Constructor with given maximum level.

    ///

    ///\param g The underlying graph

    ///\param max_level Set the range of the possible labels to

    ///[0...\c max_level]

    Elevator(const Graph &g,int max_level) :

      _g(g),

      _max_level(max_level),

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

    void dirtyTopButOne(Item i) {

      _level[i] = _max_level - 1;

    }

    ///Lift all items on and above a level to the top (and deactivate them).

    ///This function lifts all items on and above level \c l to \c

    ///maxLevel(), and also deactivates them.

    void liftToTop(int l)

    {

      const Vit f=_first[l];

      const Vit tl=_first[_max_level];

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

        _level[*i]=_max_level;

      for(int i=l;i<=_max_level;i++)

        {

          _first[i]=f;

          _last_active[i]=f-1;

        }

      for(_highest_active=l-1;

          _highest_active>=0 &&

            _last_active[_highest_active]<_first[_highest_active];

          _highest_active--) ;

    }

  private:

    int _init_lev;

    Vit _init_num;

  public:

    ///\name Initialization

    ///Using this function you can initialize the levels of the item.

    ///\n

    ///This initializatios is started with calling \c initStart().

    ///Then the

    ///items should be listed levels by levels statring with the lowest one

    ///(with level 0). This is done by using \c initAddItem()

    ///and \c initNewLevel(). Finally \c initFinish() must be called.

    ///The items not listed will be put on the highest level.

    ///@{

    ///Start the initialization process.

    void initStart()

    {

      _init_lev=0;

      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)

        {

          *n=i;

          _where[i]=n;

          _level[i]=_max_level;

          ++n;

        }

    }

    ///Add an item to the current level.

    void initAddItem(Item i)

    {

     swap(_where[i],_init_num);

      _level[i]=_init_lev;

      ++_init_num;

    }

    ///Start a new level.

    ///Start a new level.

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

    void initNewLevel()

    {

      _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;

        }

      _highest_active = -1;

    }

    ///@}

  };

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

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

  ///

  ///\ingroup auxdat

  ///Using this class you can assign "labels" (nonnegative integer numbers)

  ///to the edges or nodes of a graph, manipulate and query them through

  ///operations typically arising in "push-relabel" type algorithms.

  ///

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

  ///highest level active item.

  ///

  ///\sa Elevator

  ///

  ///\param Graph the underlying graph type

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

  ///Graph::Edge, Graph::UEdge)

  template <class Graph, class Item>

  class LinkedElevator {

  public:

    typedef Item Key;

    typedef int Value;

  private:

    typedef typename ItemSetTraits<Graph,Item>::

    template Map<Item>::Type ItemMap;

    typedef typename ItemSetTraits<Graph,Item>::

    template Map<int>::Type IntMap;

    typedef typename ItemSetTraits<Graph,Item>::

    template Map<bool>::Type BoolMap;

    const Graph &_graph;

    int _max_level;

    int _item_num;

    std::vector<Item> _first, _last;

    ItemMap _prev, _next;

    int _highest_active;

    IntMap _level;

    BoolMap _active;