athos@250: // -*- C++ -*- //
athos@250: /*
athos@250: Union-Find structure
athos@250: 
athos@250: * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
athos@250: * minden szobajovo kulcs ertekre, -1 -es ertekkel!
athos@250:  
athos@250: */
athos@250: #ifndef UNION_FIND_H
athos@250: #define UNION_FIND_H
athos@250: 
athos@250: #include <vector>
athos@250: //#include <map>
athos@250: 
athos@250: 
athos@250: namespace hugo {
athos@250:   
athos@250:   template <typename KeyType, typename KeyIntMap>
athos@250:     class UnionFind {
athos@250:     KeyIntMap& pointmap;
athos@250:     struct VectorElementType {
athos@250:       int boss;
athos@250:       int count;
athos@250:       VectorElementType(int _boss, int _count){
athos@250: 	boss = _boss;
athos@250: 	count = _count;
athos@250:       }
athos@250:     };
athos@250:     std::vector<VectorElementType> container;
athos@250:     public:
athos@250:       
athos@250:     UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){
athos@250:       
athos@250:     } 
athos@250:     
athos@250:     //Give a component of one point to the structure
athos@250:     int addPoint(KeyType u){
athos@250:       int _index = container.size();
athos@250:       VectorElementType buf(_index,1);
athos@250:       container.push_back(buf);
athos@250:       return _index;
athos@250:     }
athos@250: 
athos@250:     
athos@250:     //Finds the big boss of u
athos@250:     int find(KeyType u){
athos@250:       if (pointmap.get(u)==-1){
athos@250: 	int whoami = addPoint(u);
athos@250: 	pointmap.set(u, whoami);
athos@250: 	return whoami;
athos@250:       }
athos@250:       else{
athos@250: 	int emp = pointmap.get(u);
athos@250: 	int boss = container[emp].boss;
athos@250: 	while(emp != boss){
athos@250: 	  emp = boss;
athos@250: 	  boss = container[emp].boss;
athos@250: 	}
athos@250: 	return boss;
athos@250:       }
athos@250:     }
athos@250: 
athos@250:     //Finds u and v in the structures and merges the comopnents, if not equal
athos@250:     bool findAndMerge(KeyType u,KeyType v){
athos@250:       int bu = find(u);
athos@250:       int bv = find(v);
athos@250:       if (bu != bv){
athos@250: 	unio(bu,bv);
athos@250: 	return true;
athos@250:       }
athos@250:       else{
athos@250: 	return false;
athos@250:       }
athos@250:     }
athos@250: 
athos@250:     //Merges a into b
athos@250:     void mergeInto(int a, int b){
athos@250:       container[a].boss = b;
athos@250:       container[b].count +=  container[a].count;
athos@250:     }
athos@250:     
athos@250:     //Makes the union
athos@250:     void unio(int b1, int b2){
athos@250:       if (container[b1].count>container[b2].count){
athos@250: 	mergeInto(b2,b1);
athos@250:       }
athos@250:       else{
athos@250: 	mergeInto(b1,b2);
athos@250:       }
athos@250:     }//unio
athos@250:   };
athos@250:   
athos@250: }//namespace hugo
athos@250: #endif