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