//#####################################################################
// Copyright 2003, Geoffrey Irving
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class UNION_FIND
//#####################################################################
#ifndef __UNION_FIND__
#define __UNION_FIND__

#include "../Arrays/LIST_ARRAY.h"
namespace PhysBAM
{

class UNION_FIND
{
public:
	LIST_ARRAY<int> parents;

	explicit UNION_FIND (const int entries = 0)
	{
		parents.Resize_Array (entries);
	}

	void Initialize (const int entries)
	{
		parents.Remove_All_Entries();
		parents.Resize_Array (entries);
	}

	int Add_Entry()
	{
		parents.Append_Element (0);
		return parents.m;
	}

	bool Is_Root (const int i)
	{
		return !parents (i);
	}

	int Find (const int i)
	{
		int root = Find_Without_Path_Compression (i);
		Path_Compress (i, root);
		return root;
	}

	int Union (const int i, const int j)
	{
		int root_i = Find (i), root_j = Find_Without_Path_Compression (j);
		Path_Compress (j, root_i);

		if (root_i != root_j) parents (root_j) = root_i;

		return root_i;
	}

	void Compress_All()
	{
		for (int i = 1; i <= parents.m; i++) Path_Compress (i, Find_Without_Path_Compression (i));
	}

private:
	int Find_Without_Path_Compression (const int i) const
	{
		int j = i, k;

		while ( (k = parents (j))) j = k;

		return j;
	}

	void Path_Compress (const int i, const int root)
	{
		int j = i, k;

		while ( (k = parents (j)))
		{
			parents (j) = root;
			j = k;
		}
	}

//#####################################################################
};
}
#endif