/* -*- C++ -*-

  * lemon/unionfind.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 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_UNION_FIND_H

 #define LEMON_UNION_FIND_H

 //!\ingroup auxdat

 //!\file

 //!\brief Union-Find data structures.

 //!

 #include <vector>

 #include <list>

 #include <utility>

 #include <algorithm>

 #include <lemon/invalid.h>

 namespace lemon {

   //! \addtogroup auxdat

   //! @{

   /**

    * \brief A \e Union-Find data structure implementation

    *

    * The class implements the \e Union-Find data structure. 

    * The union operation uses rank heuristic, while

    * the find operation uses path compression.

    * This is a very simple but efficient implementation, providing 

    * only four methods: join (union), find, insert and size.

    * For more features see the \ref UnionFindEnum class.

    *

    * It is primarily used in Kruskal algorithm for finding minimal

    * cost spanning tree in a graph.

    * \sa kruskal()

    *

    * \pre The elements are automatically added only if the map 

    * given to the constructor was filled with -1's. Otherwise you

    * need to add all the elements by the \ref insert() method.

    * \bug It is not clear what the constructor parameter is used for.

    */

   template <typename T, typename TIntMap>

   class UnionFind {

   public:

     typedef T ElementType;

     typedef std::pair<int,int> PairType;

   private:

     std::vector<PairType> data;

     TIntMap& map;

   public:

     UnionFind(TIntMap& m) : map(m) {}

     /**

      * \brief Returns the index of the element's component.

      *

      * The method returns the index of the element's component.

      * This is an integer between zero and the number of inserted elements.

      */

     int find(T a)

     {

       int comp0 = map[a];

       if (comp0 < 0) {

 	return insert(a);

       }

       int comp = comp0;

       int next;

       while ( (next = data[comp].first) != comp) {

 	comp = next;

       }

       while ( (next = data[comp0].first) != comp) {

 	data[comp0].first = comp;

 	comp0 = next;

       }

       return comp;

     }

     /**

      * \brief Inserts a new element into the structure.

      *

      * This method inserts a new element into the data structure. 

      *

      * It is not required to use this method:

      * if the map given to the constructor was filled 

      * with -1's then it is called automatically

      * on the first \ref find or \ref join.

      *

      * The method returns the index of the new component.

      */

     int insert(T a)

     {

       int n = data.size();

       data.push_back(std::make_pair(n, 1));

       map.set(a,n);

       return n;

     }

     /**

      * \brief Joining the components of element \e a and element \e b.

      *

      * This is the \e union operation of the Union-Find structure. 

      * Joins the component of element \e a and component of

      * element \e b. If \e a and \e b are in the same component then

      * it returns false otherwise it returns true.

      */

     bool join(T a, T b)

     {

       int ca = find(a);

       int cb = find(b);

       if ( ca == cb ) 

 	return false;

       if ( data[ca].second > data[cb].second ) {

 	data[cb].first = ca;

 	data[ca].second += data[cb].second;

       }

       else {

 	data[ca].first = cb;

 	data[cb].second += data[ca].second;

       }

       return true;

     }

     /**

      * \brief Returns the size of the component of element \e a.

      *

      * Returns the size of the component of element \e a.

      */

     int size(T a)

     {

       int ca = find(a);

       return data[ca].second;

     }

   };

   /*******************************************************/

 #ifdef DEVELOPMENT_DOCS

   /**

    * \brief The auxiliary class for the \ref UnionFindEnum class.

    *

    * In the \ref UnionFindEnum class all components are represented as

    * a std::list. 

    * Items of these lists are UnionFindEnumItem structures.

    *

    * The class has four fields:

    *  - T me - the actual element 

    *  - IIter parent - the parent of the element in the union-find structure

    *  - int size - the size of the component of the element. 

    *            Only valid if the element

    *            is the leader of the component.

    *  - CIter my_class - pointer into the list of components 

    *            pointing to the component of the element.

    *            Only valid if the element is the leader of the component.

    */

 #endif

   template <typename T>

   struct UnionFindEnumItem {

     typedef std::list<UnionFindEnumItem> ItemList;

     typedef std::list<ItemList> ClassList;

     typedef typename ItemList::iterator IIter;

     typedef typename ClassList::iterator CIter;

     T me;

     IIter parent;

     int size;

     CIter my_class;

     UnionFindEnumItem() {}

     UnionFindEnumItem(const T &_me, CIter _my_class): 

       me(_me), size(1), my_class(_my_class) {}

   };

   /**

    * \brief A \e Union-Find data structure implementation which

    * is able to enumerate the components.

    *

    * The class implements a \e Union-Find data structure

    * which is able to enumerate the components and the items in

    * a component. If you don't need this feature then perhaps it's

    * better to use the \ref UnionFind class which is more efficient.

    *

    * The union operation uses rank heuristic, while

    * the find operation uses path compression.

    *

    * \pre You

    * need to add all the elements by the \ref insert() method.

    */

   template <typename T, template <typename Item> class Map>

   class UnionFindEnum {

     typedef std::list<UnionFindEnumItem<T> > ItemList;

     typedef std::list<ItemList> ClassList;

     typedef typename ItemList::iterator IIter;

     typedef typename ItemList::const_iterator IcIter;

     typedef typename ClassList::iterator CIter;

     typedef typename ClassList::const_iterator CcIter;

   public:

     typedef T ElementType;

     typedef UnionFindEnumItem<T> ItemType;

     typedef Map< IIter > MapType;

   private:

     MapType& m;

     ClassList classes;

     IIter _find(IIter a) const {

       IIter comp = a;

       IIter next;

       while( (next = comp->parent) != comp ) {

 	comp = next;

       }

       IIter comp1 = a;

       while( (next = comp1->parent) != comp ) {

 	comp1->parent = comp->parent;

 	comp1 = next;

       }

       return comp;

     }

   public:

     UnionFindEnum(MapType& _m) : m(_m) {}

     /**

      * \brief Inserts the given element into a new component.

      *

      * This method creates a new component consisting only of the

      * given element.

      */

     void insert(const T &a)

     {

       classes.push_back(ItemList());

       CIter aclass = classes.end();

       --aclass;

       ItemList &alist = *aclass;

       alist.push_back(ItemType(a, aclass));

       IIter ai = alist.begin();

       ai->parent = ai;

       m.set(a, ai);

     }

     /**

      * \brief Inserts the given element into the component of the others.

      *

      * This methods inserts the element \e a into the component of the

      * element \e comp. 

      */

     void insert(const T &a, const T &comp) {

       IIter clit = _find(m[comp]);

       ItemList &c = *clit->my_class;

       c.push_back(ItemType(a,0));

       IIter ai = c.end();

       --ai;

       ai->parent = clit;

       m.set(a, ai);

       ++clit->size;

     }

     /**

      * \brief Finds the leader of the component of the given element.

      *

      * The method returns the leader of the component of the given element.

      */

     T find(const T &a) const {

       return _find(m[a])->me;

     }

     /**

      * \brief Joining the component of element \e a and element \e b.

      *

      * This is the \e union operation of the Union-Find structure. 

      * Joins the component of element \e a and component of

      * element \e b. If \e a and \e b are in the same component then

      * returns false else returns true.

      */

     bool join(T a, T b) {

       IIter ca = _find(m[a]);

       IIter cb = _find(m[b]);

       if ( ca == cb ) {

 	return false;

       }

       if ( ca->size > cb->size ) {

 	cb->parent = ca->parent;

 	ca->size += cb->size;

 	ItemList &alist = *ca->my_class;

 	alist.splice(alist.end(),*cb->my_class);

 	classes.erase(cb->my_class);

 	cb->my_class = 0;

       }

       else {

 	ca->parent = cb->parent;

 	cb->size += ca->size;

 	ItemList &blist = *cb->my_class;

 	blist.splice(blist.end(),*ca->my_class);

 	classes.erase(ca->my_class);

 	ca->my_class = 0;

       }

       return true;

     }

     /**

      * \brief Returns the size of the component of element \e a.

      *

      * Returns the size of the component of element \e a.

      */

     int size(const T &a) const {

       return _find(m[a])->size;

     }

     /**

      * \brief Splits up the component of the element. 

      *

      * Splitting the component of the element into sigleton

      * components (component of size one).

      */

     void split(const T &a) {

       IIter ca = _find(m[a]);

       if ( ca->size == 1 )

 	return;

       CIter aclass = ca->my_class;

       for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {

 	classes.push_back(ItemList());

 	CIter nl = --classes.end();

 	nl->splice(nl->end(), *aclass, curr);

 	curr->size=1;

 	curr->parent=curr;

 	curr->my_class = nl;

       }

       ca->size=1;

       return;

     }

     /**

      * \brief Sets the given element to the leader element of its component.

      *

      * Sets the given element to the leader element of its component.

      */

     void makeRep(const T &a) {

       IIter ia = m[a];

       IIter la = _find(ia);

       if (la == ia) return;

       ia->my_class = la->my_class;

       la->my_class = 0;

       ia->size = la->size;

       CIter l = ia->my_class;

       l->splice(l->begin(),*l,ia);

       ia->parent = ia;

       la->parent = ia;

     }

     /**

      * \brief Moves the given element to an other component.

      *

      * This method moves the element \e a from its component

      * to the component of \e comp.

      * If \e a and \e comp are in the same component then

      * it returns false otherwise it returns true.

      */

     bool move(const T &a, const T &comp) {

       IIter ai = m[a];

       IIter lai = _find(ai);

       IIter clit = _find(m[comp]);

       if (lai == clit)

 	return false;

       ItemList &cl = *clit->my_class,

 	&al = *lai->my_class;

       bool is_leader = (lai == ai);

       bool singleton = false;

       if (is_leader) {

 	++lai;

       }

       cl.splice(cl.end(), al, ai);

       if (is_leader) {

 	if (ai->size == 1) {

 	  classes.erase(ai->my_class);

 	  singleton = true;

 	}

 	else {

 	  lai->size = ai->size; 

 	  lai->my_class = ai->my_class;	

 	}

       }

       if (!singleton) {

 	for (IIter i = lai; i != al.end(); ++i)

 	  i->parent = lai;

 	--lai->size;

       }

       ai->parent = clit;

       ai->my_class = 0;

       ++clit->size;

       return true;

     }

     /**

      * \brief Removes the given element from the structure.

      *

      * Removes the given element from the structure.

      *

      * Removes the element from its component and if the component becomes

      * empty then removes that component from the component list.

      */

     void erase(const T &a) {

       IIter ma = m[a];

       if (ma == 0) return;

       IIter la = _find(ma);

       if (la == ma) {

 	if (ma -> size == 1){

 	  classes.erase(ma->my_class);

 	  m.set(a,0);

 	  return;

 	}

 	++la;

 	la->size = ma->size; 

 	la->my_class = ma->my_class;	

       }

       for (IIter i = la; i != la->my_class->end(); ++i) {

 	i->parent = la;

       }

       la->size--;

       la->my_class->erase(ma);

       m.set(a,0);

     }

     /**

      * \brief Removes the component of the given element from the structure.

      *

      * Removes the component of the given element from the structure.

      */

     void eraseClass(const T &a) {

       IIter ma = m[a];

       if (ma == 0) return;

 #     ifdef DEBUG

       CIter c = _find(ma)->my_class;

       for (IIter i=c->begin(); i!=c->end(); ++i)

 	m.set(i->me, 0);

 #     endif

       classes.erase(_find(ma)->my_class);

     }

     class ClassIt {

       friend class UnionFindEnum;

       CcIter i;

     public:

       ClassIt(Invalid): i(0) {}

       ClassIt() {}

       operator const T& () const { 

 	ItemList const &ll = *i;

 	return (ll.begin())->me; }

       bool operator == (ClassIt it) const {

 	return (i == it.i);

       }

       bool operator != (ClassIt it) const {

 	return (i != it.i);

       }

       bool operator < (ClassIt it) const {

 	return (i < it.i);

       }

       bool valid() const { return i != 0; }

     private:

       void first(const ClassList &l) { i = l.begin(); validate(l); }

       void next(const ClassList &l) {

 	++i; 

 	validate(l);

       }

       void validate(const ClassList &l) {

 	if ( i == l.end() ) 

 	  i = 0;

       }

     };

     /**

      * \brief Sets the iterator to point to the first component.

      * 

      * Sets the iterator to point to the first component.

      *

      * With the \ref first, \ref valid and \ref next methods you can

      * iterate through the components. For example:

      * \code

      * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);

      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);

      * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;

      *  for (U.first(iter); U.valid(iter); U.next(iter)) {

      *    // iter is convertible to Graph::Node

      *    cout << iter << endl;

      *  }

      * \endcode

      */

     ClassIt& first(ClassIt& it) const {

       it.first(classes);

       return it;

     }

     /**

      * \brief Returns whether the iterator is valid.

      *

      * Returns whether the iterator is valid.

      *

      * With the \ref first, \ref valid and \ref next methods you can

      * iterate through the components. See the example here: \ref first.

      */

     bool valid(ClassIt const &it) const {

       return it.valid(); 

     }

     /**

      * \brief Steps the iterator to the next component. 

      *

      * Steps the iterator to the next component.

      *

      * With the \ref first, \ref valid and \ref next methods you can

      * iterate through the components. See the example here: \ref first.

      */

     ClassIt& next(ClassIt& it) const {

       it.next(classes);

       return it;

     }

     class ItemIt {

       friend class UnionFindEnum;

       IcIter i;

       const ItemList *l;

     public:

       ItemIt(Invalid): i(0) {}

       ItemIt() {}

       operator const T& () const { return i->me; }

       bool operator == (ItemIt it) const {

 	return (i == it.i);

       }

       bool operator != (ItemIt it) const {

 	return (i != it.i);

       }

       bool operator < (ItemIt it) const {

 	return (i < it.i);

       }

       bool valid() const { return i != 0; }

     private:

       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }

       void next() {

 	++i; 

 	validate();

       }

       void validate() {

 	if ( i == l->end() ) 

 	  i = 0;

       }

     };

     /**

      * \brief Sets the iterator to point to the first element of the component.

      * 

      * \anchor first2 

      * Sets the iterator to point to the first element of the component.

      *

      * With the \ref first2 "first", \ref valid2 "valid" 

      * and \ref next2 "next" methods you can

      * iterate through the elements of a component. For example

      * (iterating through the component of the node \e node):

      * \code

      * Graph::Node node = ...;

      * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);

      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);

      * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;

      *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {

      *     // iiter is convertible to Graph::Node

      *     cout << iiter << endl;

      *   }

      * \endcode

      */

     ItemIt& first(ItemIt& it, const T& a) const {

       it.first( * _find(m[a])->my_class );

       return it;

     }

     /**

      * \brief Returns whether the iterator is valid.

      *

      * \anchor valid2

      * Returns whether the iterator is valid.

      *

      * With the \ref first2 "first", \ref valid2 "valid" 

      * and \ref next2 "next" methods you can

      * iterate through the elements of a component.

      * See the example here: \ref first2 "first".

      */

     bool valid(ItemIt const &it) const {

       return it.valid(); 

     }

     /**

      * \brief Steps the iterator to the next component. 

      *

      * \anchor next2

      * Steps the iterator to the next component.

      *

      * With the \ref first2 "first", \ref valid2 "valid" 

      * and \ref next2 "next" methods you can

      * iterate through the elements of a component.

      * See the example here: \ref first2 "first".

      */

     ItemIt& next(ItemIt& it) const {

       it.next();

       return it;

     }

   };

   //! @}

 } //namespace lemon

 #endif //LEMON_UNION_FIND_H