// -*- C++ -*- //

 /*

 Union-Find structure

 * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen

 * minden szobajovo kulcs ertekre, -1 -es ertekkel!

 */

 #ifndef UNION_FIND_H

 #define UNION_FIND_H

 #include <vector>

 //#include <map>

 namespace lemon {

   template <typename KeyType, typename KeyIntMap>

     class UnionFind {

     KeyIntMap& pointmap;

     struct VectorElementType {

       int boss;

       int count;

       VectorElementType(int _boss, int _count){

 	boss = _boss;

 	count = _count;

       }

     };

     std::vector<VectorElementType> container;

     public:

     UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){

     } 

     //Give a component of one point to the structure

     int addPoint(KeyType u){

       int _index = container.size();

       VectorElementType buf(_index,1);

       container.push_back(buf);

       return _index;

     }

     //Finds the big boss of u

     int find(KeyType u){

       if (pointmap.get(u)==-1){

 	int whoami = addPoint(u);

 	pointmap.set(u, whoami);

 	return whoami;

       }

       else{

 	int emp = pointmap.get(u);

 	int boss = container[emp].boss;

 	while(emp != boss){

 	  emp = boss;

 	  boss = container[emp].boss;

 	}

 	return boss;

       }

     }

     //Finds u and v in the structures and merges the comopnents, if not equal

     bool findAndMerge(KeyType u,KeyType v){

       int bu = find(u);

       int bv = find(v);

       if (bu != bv){

 	unio(bu,bv);

 	return true;

       }

       else{

 	return false;

       }

     }

     //Merges a into b

     void mergeInto(int a, int b){

       container[a].boss = b;

       container[b].count +=  container[a].count;

     }

     //Makes the union

     void unio(int b1, int b2){

       if (container[b1].count>container[b2].count){

 	mergeInto(b2,b1);

       }

       else{

 	mergeInto(b1,b2);

       }

     }//unio

   };

 }//namespace lemon

 #endif