#include "DisjSets.h"


void DisjSets::unionSets( int root1, int root2 )
{
	if(!initialized)
	{
		cout << "DisjSets is not initialized... Exiting..." << endl;
		system("pause");
		exit(-1);
	}

	if ( s[root2] < s[root1] ) //// root2 is deeper
	{
		//make root2 new root
		s[root1] = root2;
	}
	else////root1
	{
		if ( s[root1] == s[root2] )
			s[root1]--;		//Update height if same else the height is the larger root's height
		s[root2] = root1;
	}
}

int DisjSets::Find( int x )
{
	if(!initialized)
	{
		cout << "DisjSets is not initialized... Exiting..." << endl;
		system("pause");
		exit(-1);
	}

	if (s[x] < 0)
	{
		return x;
	}else
	{
		//Find the parent recursivly and on way back set to root
		return s[x] = Find( s[x] );
	}

}

void DisjSets::Union( int x, int y )
{
	if(!initialized)
	{
		cout << "DisjSets is not initialized... Exiting..." << endl;
		system("pause");
		exit(-1);
	}

	int r1, r2;
	r1 = Find(x);
	r2 = Find(y);
	if (r1 != r2)
		unionSets( Find(x), Find (y) );
}

void DisjSets::Init( int numElements )
{
	s.resize(numElements);
	for (unsigned int i = 0; i < s.size(); i++)
		s[i] = -1;
	
	this->initialized = true;
}

DisjSets::DisjSets( int numElements ) : s(numElements)
{
	for (unsigned int i = 0; i < s.size(); i++)
		s[i] = -1;
	this->initialized = true;
}


DisjSets::DisjSets(void)
{
	this->initialized = false;
}