/* -*- C++ -*-

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

 *

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