// -*- 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 Key, 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(Key u){
      int _index = container.size();
      VectorElementType buf(_index,1);
      container.push_back(buf);
      return _index;
    }

    
    //Finds the big boss of u
    int find(Key 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(Key u,Key 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