package edu.claflin.finder.struct;

import java.util.LinkedList;

/**
 * A LinkedList-based Disjoint Set data structure.
 * Three operations combined O(m * + n* log(n)).
 */
public class DisjointSet<T extends Comparable<T>>
{
	private LinkedList<T>[] list;
	private int size;
	private int length;

	public DisjointSet(int size)
	{
		this.size = size;
		list = new LinkedList[this.size];
		length = 0;

		for (int i = 0; i < size; i++)
		{
			list[i] = new LinkedList<T>();
		}
	}

	/**
	 * Get the number of disjoint sets.
	 * @return the number of disjoint sets
	 */	
	public int size()
	{
		return length;
	}

	/**
	 * Whether the given object
	 * is in the disjoint sets.
	 * 
	 * @param a the object to determined whether it is in the disjoint sets
	 * @return true if the object is in the disjoint set, false otherwise
	 */
	private boolean contains(T a)
	{
		return find(a) != null;
	}

	/**
	 * Create a new disjoint set with the given element.
	 * @param n the new element
	 */
	public void makeSet(T n)
	{
		if (find(n) == null) // not already in the disjoint sets?			
		{
			list[length].add(n);
			length++;
		}
	}

	/**
	 * Get the representative of the set the given object is in.
	 * @param x the object to find the representative of
	 * @return the representative
	 */
	private T find(T x)
	{
		T representative = null;

		for (int i = 0; i < length; i++)
		{
			if (list[i].contains(x))
			{
				representative = list[i].get(0);
			}
		}
		return representative;
	}

	/**
	 * Whether two given elements are not in the same set
	 * @param a the first element
	 * @param b the second element
	 * @return whether the elements are not in the same set
	 */
	public boolean disjointElements(T a, T b)
	{
		return !find(a).equals(find(b));
	}

	/**
	 * Merge the disjoint sets two elements are in
	 * @param a the first element
	 * @param b the second element
	 */
	public void merge(T a, T b)
	{
		// get the representatives
		T ra = find(a);
		T rb = find(b);

		// objects in the disjoint sets and not in the same disjoint sets
		if (ra != null && rb != null && !ra.equals(rb))
		{
			int rai = -1; // stores the index of the linked list of element 1
			int rbi = -1; // stores the index of the linked list of element 2

			for (int i = 0; i < length; i++) // locate linked lists
			{
				if (list[i].get(0).equals(ra))
				{
					rai = i;
				}
				else if (list[i].get(0).equals(rb))
				{
					rbi = i;
				}
			}

			if (rai != -1 && rbi != -1 && rai != rbi) // lists located and not the same?
			{
				list[rai].addAll(list[rbi]); // merge b into a
				
				// delete b by moving last linked list to b's position and decrease lists count
				list[rbi] = list[length - 1];
				length--;
			}
		}
	}

	@Override
	public String toString()
	{
		String result = "";
		for (int i = 0; i < length; i++)
		{
			result += list[i].toString() + "\n";
		}
		return result;
	}

}
