package edu.stanford.nlp.util;import java.util.*;/** *  Fast Disjoint Set * *  Disjoint forest with path compression and union-by-rank.  The set *  is unmodifiable except by unions. * *  @author Dan Klein *  @version 4/17/01 */public class FastDisjointSet implements DisjointSet {  class Element {    Element parent;    int rank;    Object object;    Element(Object o) {      object = o;      rank = 0;      parent = this;    }  }  Map objectToElement;  private void linkElements(Element e, Element f) {    if (e.rank > f.rank) {      f.parent = e;    } else {      e.parent = f;      if (e.rank == f.rank)	f.rank++;    }  }  private Element findElement(Element e) {    if (e.parent == e)      return e;    Element rep = findElement(e.parent);    e.parent = rep;    return rep;  }  public Object find(Object o) {    Element e = (Element)objectToElement.get(o);    if (e == null)      return null;    Element element = findElement(e);    return element.object;  }  public void union(Object a, Object b) {    Element e = (Element)objectToElement.get(a);    Element f = (Element)objectToElement.get(b);    if (e == null || f == null)      return;    if (e == f)      return;    linkElements(findElement(e), findElement(f));  }  public FastDisjointSet(Set objectSet) {    objectToElement = new HashMap();    for (Iterator i = objectSet.iterator(); i.hasNext();) {      // create an element      Object o = i.next();      Element e = new Element(o);      objectToElement.put(o, e);    }  }}