/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2007

 * 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 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.

  ///

  ///\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() const

    {

      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");

	}

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

	{

	  check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS");

	  check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS");

	  check(_first[l]<=_first[l+1],"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.

    ///Activate item \c i.

    ///\pre Item \c i shouldn't be active before.

    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.

    ///Deactivate item \c i.

    ///\pre Item \c i must be active before.

    void deactivate(Item i)  

    {

      swap(_where[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) const

    {

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

    }

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

    int aboveLevel(int l) const

    {

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

    }

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

    int activesOnLevel(int l) const

    {

      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.

    int 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.

    ///

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

    ///than the current 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;

    }

    ///@}

    ///Lift an active item to a higher level.

    ///Lift an active item to a higher level.

    ///\param i The item to be lifted. It must be active.

    ///\param new_level The new level of \c i. It must be strictly higher

    ///than the current level.

    ///

    void liftTo(Item i, int new_level) 

    {

      const int lo = _level[i];

      const Vit w = _where[i];

      copy(_last_active[lo],w);

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

      for(int l=lo+1;l<new_level;l++)

	{

	  copy(_last_active[l],_first[l]);

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

	}

      copy(i,_first[new_level]);

      _level[i]=new_level;

      if(new_level>_highest_active) _highest_active=new_level;

    }

//     void liftToTop(int l) 

//     {

//       const Vit f=_first[l];

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

// 	{

// 	  _first[i]=f;

// 	  _last_active[i]=f-1;

// 	}

//       for(Vit i=f;i!=_items.end();++i)

// 	_level[*i]=_max_level;

//       for(_highest_active=l-1;

// 	  _highest_active>=0 &&

// 	    _last_active[_highest_active]<_first[_highest_active];

// 	  _highest_active--) ;

//     }

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

    ///This function lifts all nodes 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;

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

    }

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

	}

      _first[_max_level+1]=_items.begin()+_item_num;

      _last_active[_max_level+1]=_items.begin()+_item_num-1;

    }

    ///@}

  };

} //END OF NAMESPACE LEMON

#endif