DisjointSet.java

packagecom.jwetherell.algorithms.data_structures;

/**
 * In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of 
 * elements partitioned into a number of disjoint (non-overlapping) subsets. 
 * <p>
 * It supports two useful operations:<br>
 * Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its "representative"; by comparing the 
 * result of two Find operations, one can determine whether two elements are in the same subset.<br>
 * Union: Join two subsets into a single subset.<br>
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint Set (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
@SuppressWarnings("unchecked")
publicclassDisjointSet<TextendsObject> {

privateDisjointSet() { }

/**
 * Creates a set of one element.
 * 
 * @param v Value to use when creating the set
 * @return Item representing the value
 */
publicstaticfinal <TextendsObject> Item<T> makeSet(Tv) {
finalItem<T> item = newItem<T>(null,v);
item.parent = item;
returnitem;
 }

/**
 * Determine which subset a particular element is in. Find returns an item from this set that serves as its "representative"; by comparing the result 
 * of two Find operations, one can determine whether two elements are in the same subset. This method uses path compression which is a way of flattening 
 * the structure of the tree whenever Find is used on it.
 * 
 * @param x Find the "representative" of this Item
 * @return "Representative" of this Item
 */
publicstaticfinal <TextendsObject> Item<T> find(Item<T> x) {
if (x == null)
returnnull;

if ((x.parent!=null) && !(x.parent.equals(x)))
returnx.parent = find(x.parent);
returnx.parent;
 }

/**
 * Join two subsets into a single subset. This method uses 'union by rank' which always attaches the smaller tree to the root of the larger tree. 
 * 
 * @param x Subset 1 to join
 * @param y Subset 2 to join
 * @return Resulting Set of joining Subset 1 and Subset 2 
 */
publicstaticfinal <TextendsObject> Item<T> union(Item<T> x, Item<T> y) {
finalItem<T> xRoot = find(x);
finalItem<T> yRoot = find(y);
if (xRoot==null && yRoot==null)
returnnull;
if (xRoot==null && yRoot!=null)
returnyRoot;
if (yRoot==null && xRoot!=null)
returnxRoot;

// x and y are in the same set
if (xRoot.equals(yRoot))
returnxRoot;

if (xRoot.rank < yRoot.rank) {
xRoot.parent = yRoot;
returnyRoot;
 } elseif (xRoot.rank > yRoot.rank) {
yRoot.parent = xRoot;
returnxRoot;
 }
// else
yRoot.parent = xRoot;
xRoot.rank = xRoot.rank + 1;
returnxRoot;
 }

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
return"Nothing here to see, yet.";
 }

publicstaticfinalclassItem<T> {

privateItem<T> parent;
privateTvalue;
/** Rank is not the actual depth of the tree rather it is an upper bound. As such, on a find operation, the rank is allowed to get out of sync with the depth. **/
privatelongrank;

publicItem(Item<T> parent, Tvalue) {
this.parent = parent;
this.value = value;
this.rank = 0;
 }

publicTgetValue() {
returnvalue;
 }
publiclonggetRank() {
returnrank;
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanequals(Objecto) {
if (!(oinstanceofItem))
returnfalse;

finalItem<T> i = (Item<T>) o;
if ((i.parent!=null && parent!=null) && !(i.parent.value.equals(parent.value)))
returnfalse;
if ((i.value!=null && value!=null) && !(i.value.equals(value)))
returnfalse;
returntrue;
 }

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
return"parent="+(parent!=null?parent.value:null)+" "+
 (rank>0?"rank="+rank +" " : "") +
"value="+(value!=null?value:null);
 }
 }
}