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

     ItemIntMap& index;

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

     // is root item and it has ~(items[it].parent) component id.  Else

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

     //

     // The \c next and \c prev provides the double-linked

     // cyclic list of one component's items.

     struct ItemT {

       int parent;

       Item item;

       int next, prev;

     };

     std::vector<ItemT> items;

     int firstFreeItem;

     struct ClassT {

       int size;

       int firstItem;

       int next, prev;

     };

     std::vector<ClassT> classes;

     int firstClass, firstFreeClass;

     int newClass() {

       if (firstFreeClass == -1) {

 	int cdx = classes.size();

 	classes.push_back(ClassT());

 	return cdx;

       } else {

 	int cdx = firstFreeClass;

 	firstFreeClass = classes[firstFreeClass].next;

 	return cdx;

       }

     }

     int newItem() {

       if (firstFreeItem == -1) {

 	int idx = items.size();

 	items.push_back(ItemT());

 	return idx;

       } else {

 	int idx = firstFreeItem;

 	firstFreeItem = items[firstFreeItem].next;

 	return idx;

       }

     }

     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;

     }

     int classIndex(int idx) const {

       return ~(items[repIndex(idx)].parent);

     }

     void singletonItem(int idx) {

       items[idx].next = idx;

       items[idx].prev = idx;

     }

     void laceItem(int idx, int rdx) {

       items[idx].prev = rdx;

       items[idx].next = items[rdx].next;

       items[items[rdx].next].prev = idx;

       items[rdx].next = idx;

     }

     void unlaceItem(int idx) {

       items[items[idx].prev].next = items[idx].next;

       items[items[idx].next].prev = items[idx].prev;

       items[idx].next = firstFreeItem;

       firstFreeItem = idx;

     }

     void spliceItems(int ak, int bk) {

       items[items[ak].prev].next = bk;

       items[items[bk].prev].next = ak;

       int tmp = items[ak].prev;

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

       items[bk].prev = tmp;

     }

     void laceClass(int cls) {

       if (firstClass != -1) {

         classes[firstClass].prev = cls;

       }

       classes[cls].next = firstClass;

       classes[cls].prev = -1;

       firstClass = cls;

     } 

     void unlaceClass(int cls) {

       if (classes[cls].prev != -1) {

         classes[classes[cls].prev].next = classes[cls].next;

       } else {

         firstClass = classes[cls].next;

       }

       if (classes[cls].next != -1) {

         classes[classes[cls].next].prev = classes[cls].prev;

       }

       classes[cls].next = firstFreeClass;

       firstFreeClass = cls;

     } 

   public:

     UnionFindEnum(ItemIntMap& _index) 

       : index(_index), items(), firstFreeItem(-1), 

 	firstClass(-1), firstFreeClass(-1) {}

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

     ///

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

     /// given element.

     ///

     int insert(const Item& item) {

       int idx = newItem();

       index.set(item, idx);

       singletonItem(idx);

       items[idx].item = item;

       int cdx = newClass();

       items[idx].parent = ~cdx;

       laceClass(cdx);

       classes[cdx].size = 1;

       classes[cdx].firstItem = idx;

       firstClass = cdx;

       return cdx;

     }

     /// \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, int cls) {

       int rdx = classes[cls].firstItem;

       int idx = newItem();

       index.set(item, idx);

       laceItem(idx, rdx);

       items[idx].item = item;

       items[idx].parent = rdx;

       ++classes[~(items[rdx].parent)].size;

     }

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

     ///

     /// Erase each item from the data structure.

     void clear() {

       items.clear();

       firstClass = -1;

       firstFreeItem = -1;

     }

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

     ///

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

     int find(const Item &item) const {

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

     }

     /// \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 -1 else returns the remaining class.

     int join(const Item& a, const Item& b) {

       int ak = repIndex(index[a]);

       int bk = repIndex(index[b]);

       if (ak == bk) {

 	return -1;

       }

       int acx = ~(items[ak].parent);

       int bcx = ~(items[bk].parent);

       int rcx;

       if (classes[acx].size > classes[bcx].size) {

 	classes[acx].size += classes[bcx].size;

 	items[bk].parent = ak;

         unlaceClass(bcx);

 	rcx = acx;

       } else {

 	classes[bcx].size += classes[acx].size;

 	items[ak].parent = bk;

         unlaceClass(acx);

 	rcx = bcx;

       }

       spliceItems(ak, bk);

       return rcx;

     }

     /// \brief Returns the size of the class.

     ///

     /// Returns the size of the class.

     int size(int cls) const {

       return classes[cls].size;

     }

     /// \brief Splits up the component. 

     ///

     /// Splitting the component into singleton components (component

     /// of size one).

     void split(int cls) {

       int fdx = classes[cls].firstItem;

       int idx = items[fdx].next;

       while (idx != fdx) {

         int next = items[idx].next;

 	singletonItem(idx);

 	int cdx = newClass();        

         items[idx].parent = ~cdx;

 	laceClass(cdx);

 	classes[cdx].size = 1;

 	classes[cdx].firstItem = idx;

         idx = next;

       }

       items[idx].prev = idx;

       items[idx].next = idx;

       classes[~(items[idx].parent)].size = 1;

     }

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

     /// \warning This running time of this operation is proportional to the

     /// number of the items in this class.

     void erase(const Item& item) {

       int idx = index[item];

       int fdx = items[idx].next;

       int cdx = classIndex(idx);

       if (idx == fdx) {

 	unlaceClass(cdx);

 	items[idx].next = firstFreeItem;

 	firstFreeItem = idx;

 	return;

       } else {

 	classes[cdx].firstItem = fdx;

 	--classes[cdx].size;

 	items[fdx].parent = ~cdx;

 	unlaceItem(idx);

 	idx = items[fdx].next;

 	while (idx != fdx) {

 	  items[idx].parent = fdx;

 	  idx = items[idx].next;

 	}

       }

     }

     /// \brief Gives back a representant item of the component.

     ///

     /// Gives back a representant item of the component.

     Item item(int cls) const {

       return items[classes[cls].firstItem].item;

     }

     /// \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(int cls) {

       int fdx = classes[cls].firstItem;

       unlaceClass(cls);

       items[items[fdx].prev].next = firstFreeItem;

       firstFreeItem = fdx;

     }

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

     ///

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

     /// on the ids of the classes.

     class ClassIt {

     public:

       /// \brief Constructor of the iterator

       ///

       /// Constructor of the iterator

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

         cdx = unionFind->firstClass;

       }

       /// \brief Constructor to get invalid iterator

       ///

       /// Constructor to get invalid iterator

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

       /// \brief Increment operator

       ///

       /// It steps to the next representant item.

       ClassIt& operator++() {

         cdx = unionFind->classes[cdx].next;

         return *this;

       }

       /// \brief Conversion operator

       ///

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

       operator int() const {

         return cdx;

       }

       /// \brief Equality operator

       ///

       /// Equality operator

       bool operator==(const ClassIt& i) { 

         return i.cdx == cdx;

       }

       /// \brief Inequality operator

       ///

       /// Inequality operator

       bool operator!=(const ClassIt& i) { 

         return i.cdx != cdx;

       }

     private:

       const UnionFindEnum* unionFind;

       int cdx;

     };

     /// \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, int cls) : unionFind(&ufe) {

         fdx = idx = unionFind->classes[cls].firstItem;

       }

       /// \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].next;

         if (idx == fdx) 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, fdx;

     };

   };

   /// \ingroup auxdat

   ///

   /// \brief A \e Extend-Find data structure implementation which

   /// is able to enumerate the components.

   ///

   /// The class implements an \e Extend-Find data structure which is

   /// able to enumerate the components and the items in a

   /// component. The data structure is a simplification of the

   /// Union-Find structure, and it does not allow to merge two components.

   ///

   /// \pre You need to add all the elements by the \ref insert()

   /// method.

   template <typename _ItemIntMap>

   class ExtendFindEnum {

   public:

     typedef _ItemIntMap ItemIntMap;

     typedef typename ItemIntMap::Key Item;

   private:

     ItemIntMap& index;

     struct ItemT {

       int cls;

       Item item;

       int next, prev;

     };

     std::vector<ItemT> items;

     int firstFreeItem;

     struct ClassT {

       int firstItem;

       int next, prev;

     };

     std::vector<ClassT> classes;

     int firstClass, firstFreeClass;

     int newClass() {

       if (firstFreeClass != -1) {

 	int cdx = firstFreeClass;

 	firstFreeClass = classes[cdx].next;

 	return cdx;

       } else {

 	classes.push_back(ClassT());

 	return classes.size() - 1;

       }

     }

     int newItem() {

       if (firstFreeItem != -1) {

 	int idx = firstFreeItem;

 	firstFreeItem = items[idx].next;

 	return idx;

       } else {

 	items.push_back(ItemT());

 	return items.size() - 1;

       }

     }

   public:

     /// \brief Constructor

     ExtendFindEnum(ItemIntMap& _index) 

       : index(_index), items(), firstFreeItem(-1), 

 	classes(), firstClass(-1), firstFreeClass(-1) {}

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

     ///

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

     /// given element.

     int insert(const Item& item) {

       int cdx = newClass();

       classes[cdx].prev = -1;

       classes[cdx].next = firstClass;

       firstClass = cdx;

       int idx = newItem();

       items[idx].item = item;

       items[idx].cls = cdx;

       items[idx].prev = idx;

       items[idx].next = idx;

       classes[cdx].firstItem = idx;

       index.set(item, idx);

       return cdx;

     }

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

     ///

     /// This methods inserts the element \e item a into the \e cls class.

     void insert(const Item& item, int cls) {

       int idx = newItem();

       int rdx = classes[cls].firstItem;

       items[idx].item = item;

       items[idx].cls = cls;

       items[idx].prev = rdx;

       items[idx].next = items[rdx].next;

       items[items[rdx].next].prev = idx;

       items[rdx].next = idx;

       index.set(item, idx);

     }

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

     ///

     /// Erase each item from the data structure.

     void clear() {

       items.clear();

       classes.clear;

       firstClass = firstFreeClass = firstFreeItem = -1;

     }

     /// \brief Gives back the class of the \e item.

     ///

     /// Gives back the class of the \e item.

     int find(const Item &item) const {

       return items[index[item]].cls;

     }

     /// \brief Gives back a representant item of the component.

     ///

     /// Gives back a representant item of the component.

     Item item(int cls) const {

       return items[classes[cls].firstItem].item;

     }

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

       int cdx = items[idx].cls;

       if (idx == items[idx].next) {

 	if (classes[cdx].prev != -1) {

 	  classes[classes[cdx].prev].next = classes[cdx].next; 

 	} else {

 	  firstClass = classes[cdx].next;

 	}

 	if (classes[cdx].next != -1) {

 	  classes[classes[cdx].next].prev = classes[cdx].prev; 

 	}

 	classes[cdx].next = firstFreeClass;

 	firstFreeClass = cdx;

       } else {

 	classes[cdx].firstItem = items[idx].next;

 	items[items[idx].next].prev = items[idx].prev;

 	items[items[idx].prev].next = items[idx].next;

       }

       items[idx].next = firstFreeItem;

       firstFreeItem = idx;

     }    

     /// \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(int cdx) {

       int idx = classes[cdx].firstItem;

       items[items[idx].prev].next = firstFreeItem;

       firstFreeItem = idx;

       if (classes[cdx].prev != -1) {

 	classes[classes[cdx].prev].next = classes[cdx].next; 

       } else {

 	firstClass = classes[cdx].next;

       }

       if (classes[cdx].next != -1) {

 	classes[classes[cdx].next].prev = classes[cdx].prev; 

       }

       classes[cdx].next = firstFreeClass;

       firstFreeClass = cdx;

     }

     /// \brief Lemon style iterator for the classes.

     ///

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

     /// on the ids of classes.

     class ClassIt {

     public:

       /// \brief Constructor of the iterator

       ///

       /// Constructor of the iterator

       ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {

         cdx = extendFind->firstClass;

       }

       /// \brief Constructor to get invalid iterator

       ///

       /// Constructor to get invalid iterator

       ClassIt(Invalid) : extendFind(0), cdx(-1) {}

       /// \brief Increment operator

       ///

       /// It steps to the next representant item.

       ClassIt& operator++() {

         cdx = extendFind->classes[cdx].next;

         return *this;

       }

       /// \brief Conversion operator

       ///

       /// It converts the iterator to the current class id.

       operator int() const {

         return cdx;

       }

       /// \brief Equality operator

       ///

       /// Equality operator

       bool operator==(const ClassIt& i) { 

         return i.cdx == cdx;

       }

       /// \brief Inequality operator

       ///

       /// Inequality operator

       bool operator!=(const ClassIt& i) { 

         return i.cdx != cdx;

       }

     private:

       const ExtendFindEnum* extendFind;

       int cdx;

     };

     /// \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 ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {

         fdx = idx = extendFind->classes[cls].firstItem;

       }

       /// \brief Constructor to get invalid iterator

       ///

       /// Constructor to get invalid iterator

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

       /// \brief Increment operator

       ///

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

       ItemIt& operator++() {

         idx = extendFind->items[idx].next;

 	if (fdx == idx) idx = -1;

         return *this;

       }

       /// \brief Conversion operator

       ///

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

       operator const Item&() const {

         return extendFind->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 ExtendFindEnum* extendFind;

       int idx, fdx;

     };

   };

   //! @}

 } //namespace lemon

 #endif //LEMON_UNION_FIND_H