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