/* -*- 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_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/bits/invalid.h>

 namespace lemon {

   /// \ingroup 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 You need to add all the elements by the \ref insert()

   /// method.  

   template <typename _ItemIntMap>

   class UnionFind {

   public:

     typedef _ItemIntMap ItemIntMap;

     typedef typename ItemIntMap::Key Item;

   private:

     // If the items vector stores negative value for an item then

     // that item is root item and it has -items[it] component size.

     // Else the items[it] contains the index of the parent.

     std::vector<int> items;

     ItemIntMap& index;

     bool rep(int idx) const {

       return items[idx] < 0;

     }

     int repIndex(int idx) const {

       int k = idx;

       while (!rep(k)) {

         k = items[k] ;

       }

       while (idx != k) {

         int next = items[idx];

         const_cast<int&>(items[idx]) = k;

         idx = next;

       }

       return k;

     }

   public:

     /// \brief Constructor

     ///

     /// Constructor of the UnionFind class. You should give an item to

     /// integer map which will be used from the data structure. If you

     /// modify directly this map that may cause segmentation fault,

     /// invalid data structure, or infinite loop when you use again

     /// the union-find.

     UnionFind(ItemIntMap& m) : index(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(const Item& a) {

       return repIndex(index[a]);

     }

     /// \brief Clears the union-find data structure

     ///

     /// Erase each item from the data structure.

     void clear() {

       items.clear();

     }

     /// \brief Inserts a new element into the structure.

     ///

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

     ///

     /// The method returns the index of the new component.

     int insert(const Item& a) {

       int n = items.size();

       items.push_back(-1);

       index.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(const Item& a, const Item& b) {

       int ka = repIndex(index[a]);

       int kb = repIndex(index[b]);

       if ( ka == kb ) 

 	return false;

       if (items[ka] < items[kb]) {

 	items[ka] += items[kb];

 	items[kb] = ka;

       } else {

 	items[kb] += items[ka];

 	items[ka] = kb;

       }

       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 Item& a) {

       int k = repIndex(index[a]);

       return - items[k];

     }

   };

   /// \ingroup auxdat

   ///

   /// \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 _ItemIntMap>

   class UnionFindEnum {

   public:

     typedef _ItemIntMap ItemIntMap;

     typedef typename ItemIntMap::Key Item;

   private:

     // If the parent stores negative value for an item then that item

     // is root item and it has -items[it].parent component size.  Else

     // the items[it].parent contains the index of the parent.

     //

     // The \c nextItem and \c prevItem provides the double-linked

     // cyclic list of one component's items. The \c prevClass and

     // \c nextClass gives the double linked list of the representant

     // items. 

     struct ItemT {

       int parent;

       Item item;

       int nextItem, prevItem;

       int nextClass, prevClass;

     };

     std::vector<ItemT> items;

     ItemIntMap& index;

     int firstClass;

     bool rep(int idx) const {

       return items[idx].parent < 0;

     }

     int repIndex(int idx) const {

       int k = idx;

       while (!rep(k)) {

         k = items[k].parent;

       }

       while (idx != k) {

         int next = items[idx].parent;

         const_cast<int&>(items[idx].parent) = k;

         idx = next;

       }

       return k;

     }

     void unlaceClass(int k) {

       if (items[k].prevClass != -1) {

         items[items[k].prevClass].nextClass = items[k].nextClass;

       } else {

         firstClass = items[k].nextClass;

       }

       if (items[k].nextClass != -1) {

         items[items[k].nextClass].prevClass = items[k].prevClass;

       }

     } 

     void spliceItems(int ak, int bk) {

       items[items[ak].prevItem].nextItem = bk;

       items[items[bk].prevItem].nextItem = ak;

       int tmp = items[ak].prevItem;

       items[ak].prevItem = items[bk].prevItem;

       items[bk].prevItem = tmp;

     }

   public:

     UnionFindEnum(ItemIntMap& _index) 

       : items(), index(_index), firstClass(-1) {}

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

     ///

     /// This method creates a new component consisting only of the

     /// given element.

     ///

     void insert(const Item& item) {

       ItemT t;

       int idx = items.size();

       index.set(item, idx);

       t.nextItem = idx;

       t.prevItem = idx;

       t.item = item;

       t.parent = -1;

       t.nextClass = firstClass;

       if (firstClass != -1) {

         items[firstClass].prevClass = idx;

       }

       t.prevClass = -1;

       firstClass = idx;

       items.push_back(t);

     }

     /// \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 Item& item, const Item& comp) {

       int k = repIndex(index[comp]);

       ItemT t;

       int idx = items.size();

       index.set(item, idx);

       t.prevItem = k;

       t.nextItem = items[k].nextItem;

       items[items[k].nextItem].prevItem = idx;

       items[k].nextItem = idx;

       t.item = item;

       t.parent = k;

       --items[k].parent;

       items.push_back(t);

     }

     /// \brief Clears the union-find data structure

     ///

     /// Erase each item from the data structure.

     void clear() {

       items.clear();

       firstClass = -1;

     }

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

     ///

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

     const Item& find(const Item &item) const {

       return items[repIndex(index[item])].item;

     }

     /// \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(const Item& a, const Item& b) {

       int ak = repIndex(index[a]);

       int bk = repIndex(index[b]);

       if (ak == bk) {

 	return false;

       }

       if ( items[ak].parent < items[bk].parent ) {

         unlaceClass(bk);

         items[ak].parent += items[bk].parent;

 	items[bk].parent = ak;

       } else {

         unlaceClass(ak);

         items[bk].parent += items[ak].parent;

 	items[ak].parent = bk;

       }

       spliceItems(ak, bk);

       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 Item &item) const {

       return - items[repIndex(index[item])].parent;

     }

     /// \brief Splits up the component of the element. 

     ///

     /// Splitting the component of the element into sigleton

     /// components (component of size one).

     void split(const Item &item) {

       int k = repIndex(index[item]);

       int idx = items[k].nextItem;

       while (idx != k) {

         int next = items[idx].nextItem;

         items[idx].parent = -1;

         items[idx].prevItem = idx;

         items[idx].nextItem = idx;

         items[idx].nextClass = firstClass;

         items[firstClass].prevClass = idx;

         firstClass = idx;

         idx = next;

       }

       items[idx].parent = -1;

       items[idx].prevItem = idx;

       items[idx].nextItem = idx;

       items[firstClass].prevClass = -1;

     }

     /// \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 Item &item) {

       int nk = index[item];

       int k = repIndex(nk);

       if (nk == k) return;

       if (items[k].prevClass != -1) {

         items[items[k].prevClass].nextClass = nk;

       } else {

         firstClass = nk;

       }

       if (items[k].nextClass != -1) {

         items[items[k].nextClass].prevClass = nk;

       }

       int idx = items[k].nextItem;

       while (idx != k) {

         items[idx].parent = nk;

         idx = items[idx].nextItem;

       }

       items[nk].parent = items[k].parent;

       items[k].parent = nk;

     }

     /// \brief 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.

     ///

     /// \warning It is an error to remove an element which is not in

     /// the structure.

     void erase(const Item &item) {

       int idx = index[item];

       if (rep(idx)) {

         int k = idx;

         if (items[k].parent == -1) {

           unlaceClass(idx);

           return;

         } else {

           int nk = items[k].nextItem;

           if (items[k].prevClass != -1) {

             items[items[k].prevClass].nextClass = nk;

           } else {

             firstClass = nk;

           }

           if (items[k].nextClass != -1) {

             items[items[k].nextClass].prevClass = nk;

           }

           int l = items[k].nextItem;

           while (l != k) {

             items[l].parent = nk;

             l = items[l].nextItem;

           }

           items[nk].parent = items[k].parent + 1;

         }

       } else {

         int k = repIndex(idx);

         idx = items[k].nextItem;

         while (idx != k) {

           items[idx].parent = k;

           idx = items[idx].nextItem;

         }

         ++items[k].parent;

       }

       idx = index[item];      

       items[items[idx].prevItem].nextItem = items[idx].nextItem;

       items[items[idx].nextItem].prevItem = items[idx].prevItem;

     }    

     /// \brief Moves the given element to another 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 Item &item, const Item &comp) {

       if (repIndex(index[item]) == repIndex(index[comp])) return false;

       erase(item);

       insert(item, comp);

       return true;

     }

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

     ///

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

     ///

     /// \warning It is an error to give an element which is not in the

     /// structure.

     void eraseClass(const Item &item) {

       unlaceClass(repIndex(index[item]));

     }

     /// \brief Lemon style iterator for the representant items.

     ///

     /// ClassIt is a lemon style iterator for the components. It iterates

     /// on the representant items of the classes.

     class ClassIt {

     public:

       /// \brief Constructor of the iterator

       ///

       /// Constructor of the iterator

       ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {

         idx = unionFind->firstClass;

       }

       /// \brief Constructor to get invalid iterator

       ///

       /// Constructor to get invalid iterator

       ClassIt(Invalid) : unionFind(0), idx(-1) {}

       /// \brief Increment operator

       ///

       /// It steps to the next representant item.

       ClassIt& operator++() {

         idx = unionFind->items[idx].nextClass;

         return *this;

       }

       /// \brief Conversion operator

       ///

       /// It converts the iterator to the current representant item.

       operator const Item&() const {

         return unionFind->items[idx].item;

       }

       /// \brief Equality operator

       ///

       /// Equality operator

       bool operator==(const ClassIt& i) { 

         return i.idx == idx;

       }

       /// \brief Inequality operator

       ///

       /// Inequality operator

       bool operator!=(const ClassIt& i) { 

         return i.idx != idx;

       }

     private:

       const UnionFindEnum* unionFind;

       int idx;

     };

     /// \brief Lemon style iterator for the items of a component.

     ///

     /// ClassIt is a lemon style iterator for the components. It iterates

     /// on the items of a class. By example if you want to iterate on

     /// each items of each classes then you may write the next code.

     ///\code

     /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {

     ///   std::cout << "Class: ";

     ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {

     ///     std::cout << toString(iit) << ' ' << std::endl;

     ///   }

     ///   std::cout << std::endl;

     /// }

     ///\endcode

     class ItemIt {

     public:

       /// \brief Constructor of the iterator

       ///

       /// Constructor of the iterator. The iterator iterates

       /// on the class of the \c item.

       ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {

         idx = unionFind->repIndex(unionFind->index[item]);

       }

       /// \brief Constructor to get invalid iterator

       ///

       /// Constructor to get invalid iterator

       ItemIt(Invalid) : unionFind(0), idx(-1) {}

       /// \brief Increment operator

       ///

       /// It steps to the next item in the class.

       ItemIt& operator++() {

         idx = unionFind->items[idx].nextItem;

         if (unionFind->rep(idx)) idx = -1;

         return *this;

       }

       /// \brief Conversion operator

       ///

       /// It converts the iterator to the current item.

       operator const Item&() const {

         return unionFind->items[idx].item;

       }

       /// \brief Equality operator

       ///

       /// Equality operator

       bool operator==(const ItemIt& i) { 

         return i.idx == idx;

       }

       /// \brief Inequality operator

       ///

       /// Inequality operator

       bool operator!=(const ItemIt& i) { 

         return i.idx != idx;

       }

     private:

       const UnionFindEnum* unionFind;

       int idx;

     };

   };

   //! @}

 } //namespace lemon

 #endif //LEMON_UNION_FIND_H