source: lemon-0.x/lemon/elevator.h @ 2346:c06a956a92fa

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * 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 hangling "labels" in push-relabel type algorithms.
  
  ///A class for hangling "labels" in push-relabel type algorithms.
  ///
  ///\ingroup auxdat
  ///Using this class you can assign "labels" (nonnegativ 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.
  ///
  ///\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 typename std::vector<Item>::iterator Vit;
    typedef DefaultMap<Graph,Item,Vit> VitMap;
    typedef DefaultMap<Graph,Item,int> 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;
    }
    
    void checkDs() 
    {
      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
        {
          Vit w=_where[i];
          int l=_level[i];
          check(*w==i,"GEBASZ: CORRUPT DS");
          check(_first[l]<=w,"GEBASZ: CORRUPT DS");
          check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
        }
      check(_highest_active<0 ||
            _first[_highest_active]<=_last_active[_highest_active],
            "GEBASZ: CORRUPT DS");
    }

  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),
      _item_num(_max_level),
      _where(g),
      _level(g,0),
      _items(_max_level),
      _first(_max_level+2),
      _last_active(_max_level+2),
      _highest_active(-1) {}
    ///Constructor.

    ///Constructor.
    ///
    ///\param g The underlying graph
    ///The range of the possible labels is [0...\c max_level],
    ///where \c max_level is equal to the number of labeled items in the graph.
    Elevator(const Graph &g) :
      _g(g),
      _max_level(countItems<Graph, Item>(g)),
      _item_num(_max_level),
      _where(g),
      _level(g,0),
      _items(_max_level),
      _first(_max_level+2),
      _last_active(_max_level+2),
      _highest_active(-1)
    {
    }
  
    ///Activate item \c i.
    void activate(Item i)
    {
      const int l=_level[i];
      swap(_where[i],++_last_active[l]);
      if(l>_highest_active) _highest_active=l;
    }
  
    ///Deactivate item \c i.
    void deactivate(Item i)  
    {
      swap(_where[i],_last_active[_level[i]]--);
      _last_active[_level[i]]--;
      while(_highest_active>=0 &&
            _last_active[_highest_active]<_first[_highest_active])
        _highest_active--;
    }

    ///Query whether item \c i is active
    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
    
    ///Return the level of item \c i.
    int operator[](Item i) const { return _level[i]; }

    ///Returns an active item on level \c l.

    ///Returns an active item on level \c l.
    ///
    ///Returns an active item on level \c l or \ref INVALID if there is no such
    ///an item. (\c l must be from the range [0...\c max_level].
    Item operator[](int l) const
    { 
      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
    }

    ///Return the number of items on level \c l.
    int &onLevel(int l)
    {
      return _first[l+1]-_first[l];
    }
    ///Return the number of active items on level \c l.
    int &activesOnLevel(int l)
    {
      return _last_active[l]-_first[l]+1;
    }
    ///Return the maximum allowed level.
    int maxLevel() const 
    {
      return _max_level;
    }    

    ///\name Highest Active Item
    ///Functions for working with the highest level
    ///active item.

    ///@{

    ///Return a highest level active item.
  
    ///Return a highest level active item.
    ///
    ///\return the highest level active item or INVALID if there is no active
    ///item.
    Item highestActive() const 
    {
      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
    }

    ///Return a highest active level.

    ///Return a highest active level.
    ///
    ///\return the level of the highest active item or -1 if there is no active
    ///item.
    Item highestActiveLevel() const 
    {
      return _highest_active;
    }

    ///Lift the highest active item by one.

    ///Lift the item returned by highestActive() by one.
    ///
    void liftHighestActive() 
    {
      ++_level[*_last_active[_highest_active]];
      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
      --_first[++_highest_active];
    }

    ///Lift the highest active item.

    ///Lift the item returned by highestActive() to level \c new_level.
    ///
    ///
    void liftHighestActiveTo(int new_level) 
    {
      const Item li = *_last_active[_highest_active];
      
      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
      for(int l=_highest_active+1;l<new_level;l++)
        {
          copy(--_first[l+1],_first[l]);
          --_last_active[l];
        }
      copy(li,_first[new_level]);
      _level[li]=new_level;
          _highest_active=new_level;
    }
    
    ///@}
    
  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 listes will be put on the highest level.
    ///@{

    ///Starts the initialization process.

    void initStart() 
    {
      _init_lev=0;
      _init_num=_items.begin();
      _first[0]=_items.begin();
      _last_active[0]=_items.begin()-1;
      Vit n=_items.begin();
      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;
    }

    ///Finalizes 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;
        }
      _first[_max_level+1]=_items.begin()+_item_num;
      _last_active[_max_level+1]=_items.begin()+_item_num-1;
    }

    ///@}

  };

} //END OF NAMESPACE LEMON

#endif