Package org.plumelib.util

Class UnionFind<E>

java.lang.Object
org.plumelib.util.UnionFind<E>
Type Parameters:
E - the type of the elements
public class UnionFind<E> extends Object
A union-find (disjoint-set) data structure. Elements must not be null. Elements are used as hash keys, so an element's equals and hashCode must not change while it is in the structure. This class is not thread-safe.

The structure partitions its elements into disjoint sets. Each set has a distinguished element, its representative. Two elements are in the same set if and only if they have the same representative. The two fundamental operations are:

  • find(E): return the representative of the set containing an element.
  • union(E, E): merge the two sets containing two elements into a single set.

Both operations run in nearly constant amortized time, using union by rank and path compression.

In addition to the usual union-find operations, this implementation supports:

Predicates. A client may supply, to the constructor, a unary predicate and/or a binary predicate. Functions test(Object) and test(Object, Object) lift them to predicates over sets:

  • test(S) is true if p(x) is true for some element x of S.
  • test(S1, S2) is true if q(x, y) is true for some x in S1 and some y in S2.

Querying through any member of a set gives the same answer as through any other member.

The lifted predicates are existential ("there exists") properties, so they are monotonic: as a set grows, the predicate can only change from false to true, never the reverse. Therefore unioning preserves them:

  • If p(a) is true, then after z = union(a, e), p(z) is true.
  • If q(a, b) is true, then:
    • after x = union(a, c), q(x, b) is true, and
    • after y = union(b, d), q(a, y) is true.

Lazy evaluation and caching. A lifted predicate's value for a set (or ordered pair of sets) is computed on demand, cached, and incrementally maintained. The binary-predicate cache can hold an entry per ordered pair of sets, so it may use space quadratic in the number of sets, and each union(E, E) scans the cached pairs to maintain them. Clients that query many cross-pairs among many small sets pay for this in time and space.

  • Constructor Summary

    Constructors
    Constructor
    Description
    UnionFind()
    Creates a new, empty union-find structure with no predicates.
    UnionFind(@Nullable Predicate<? super E> unaryPredicate, @Nullable BiPredicate<? super E,? super E> binaryPredicate)
    Creates a new, empty union-find structure with the given predicates.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(E e)
    Adds an element as a new singleton set.
    boolean
    addAll(Collection<? extends E> es)
    Adds each element as a new singleton set.
    Collection<List<E>>
    allSets()
    Returns all the sets, each as a list of its elements.
    boolean
    contains(E e)
    Returns true if the element is present in this structure.
    List<E>
    elementsInSameSetAs(E e)
    Returns all the elements in the same set as the given element.
    E
    find(E e)
    Returns the representative of the set containing the given element.
    int
    numberOfSets()
    Returns the number of disjoint sets.
    boolean
    sameSet(E a, E b)
    Returns true if the two elements are in the same set.
    int
    size()
    Returns the number of elements in this structure.
    boolean
    test(E e)
    Returns true if the unary predicate holds of the set containing the given element; that is, if the client's unary predicate is true of some element of that set.
    boolean
    test(E a, E b)
    Returns true if the binary predicate holds of the ordered pair of sets containing the given elements; that is, if the client's binary predicate is true of some ordered pair of an element of a's set and an element of b's set.
    String
    toString()
     
    E
    union(E a, E b)
    Merges the set containing a and the set containing b into a single set, and returns the representative of the merged set.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • UnionFind

      public UnionFind()
      Creates a new, empty union-find structure with no predicates.

    • UnionFind

      public UnionFind(@Nullable Predicate<? super E> unaryPredicate, @Nullable BiPredicate<? super E,? super E> binaryPredicate)
      Creates a new, empty union-find structure with the given predicates.
      Parameters:
      unaryPredicate - the unary predicate to lift to sets, or null for none
      binaryPredicate - the binary predicate to lift to ordered pairs of sets, or null for none

  • Method Details

    • add

      public boolean add(E e)
      Adds an element as a new singleton set. Does nothing if the element is already present.
      Parameters:
      e - the element to add
      Returns:
      true if the element was added, false if it was already present

    • addAll

      public boolean addAll(Collection<? extends E> es)
      Adds each element as a new singleton set. Elements that are already present are left unchanged.
      Parameters:
      es - the elements to add
      Returns:
      true if this structure changed as a result of the call

    • contains

      public boolean contains(E e)
      Returns true if the element is present in this structure.
      Parameters:
      e - the element to test
      Returns:
      true if the element has been added

    • size

      public int size()
      Returns the number of elements in this structure.
      Returns:
      the number of elements

    • numberOfSets

      public int numberOfSets()
      Returns the number of disjoint sets.
      Returns:
      the number of sets

    • find

      public E find(E e)
      Returns the representative of the set containing the given element. Two elements are in the same set if and only if this method returns the same representative for both.
      Parameters:
      e - the element whose representative to return
      Returns:
      the representative of the set containing e
      Throws:
      NoSuchElementException - if e is not present

    • union

      public E union(E a, E b)
      Merges the set containing a and the set containing b into a single set, and returns the representative of the merged set. Adds a or b as a new singleton set if it is not already present.

      Cached predicate values are preserved. A true value stays true. A false value is maintained incrementally: the client's predicate is evaluated on the newly-formed elements or pairs, and the value becomes true if any of them satisfies it.

      Parameters:
      a - an element
      b - an element
      Returns:
      the representative of the set that contains both a and b

    • sameSet

      public boolean sameSet(E a, E b)
      Returns true if the two elements are in the same set. Adds neither element.
      Parameters:
      a - an element
      b - an element
      Returns:
      true if a and b are in the same set
      Throws:
      NoSuchElementException - if a or b is not present

    • elementsInSameSetAs

      public List<E> elementsInSameSetAs(E e)
      Returns all the elements in the same set as the given element. The returned list is an unmodifiable snapshot; it is not affected by subsequent operations.
      Parameters:
      e - an element
      Returns:
      all elements in the same set as e, including e itself
      Throws:
      NoSuchElementException - if e is not present

    • allSets

      @SideEffectFree public Collection<List<E>> allSets()
      Returns all the sets, each as a list of its elements. The returned collection and its lists are unmodifiable snapshots.
      Returns:
      all the sets

    • toString

      @SideEffectFree public String toString()
      Overrides:
      toString in class Object

    • test

      public boolean test(E e)
      Returns true if the unary predicate holds of the set containing the given element; that is, if the client's unary predicate is true of some element of that set.
      Parameters:
      e - an element of the set
      Returns:
      true if the unary predicate holds of e's set
      Throws:
      IllegalStateException - if no unary predicate was supplied to the constructor
      NoSuchElementException - if e is not present

    • test

      public boolean test(E a, E b)
      Returns true if the binary predicate holds of the ordered pair of sets containing the given elements; that is, if the client's binary predicate is true of some ordered pair of an element of a's set and an element of b's set.
      Parameters:
      a - an element of the first set
      b - an element of the second set
      Returns:
      true if the binary predicate holds of the ordered pair (a's set, b's set)
      Throws:
      IllegalStateException - if no binary predicate was supplied to the constructor
      NoSuchElementException - if a or b is not present