Class UnionFind<T>

java.lang.Object
org.ek9lang.compiler.support.UnionFind<T>
Type Parameters:
T - the element type; needs a sound equals/hashCode.
public final class UnionFind<T> extends Object
THE Union-Find (Disjoint Set Union) - use this for "which things are connected", never hand-roll parent arrays. Used by LCOM4 and module cohesion (groups of methods or constructs that touch one another), by the data clump check (groups of signatures that share a clump) and by the MCP module cohesion extractor.

Uses path compression and union by rank: near-constant time per operation (alpha(n), the inverse Ackermann function). On equal ranks the second argument's root goes under the first's, so results (the root chosen) are stable for a given sequence of operations. For cycles in a directed graph use StronglyConnectedComponents instead - this is for undirected connectivity.

Algorithm: Tarjan, R.E. (1975) "Efficiency of a Good But Not Linear Set Union Algorithm"

  • Constructor Summary

    Constructors
    Constructor
    Description
    UnionFind()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(T element)
    Add an element; initially each element is in its own set.
    int
    countComponents()
    Count the distinct sets among the added elements.
    T
    find(T element)
    Find the root of the set containing the element, compressing the path.
    void
    union(T a, T b)
    Union the sets of two elements, by rank.

    Methods inherited from class Object

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

  • Constructor Details

    • UnionFind

      public UnionFind()

  • Method Details

    • add

      public void add(T element)
      Add an element; initially each element is in its own set. Adding twice is harmless.
      Parameters:
      element - the element to add.

    • find

      public T find(T element)
      Find the root of the set containing the element, compressing the path.
      Parameters:
      element - the element to find.
      Returns:
      the root of its set, or the element itself if it was never added.

    • union

      public void union(T a, T b)
      Union the sets of two elements, by rank.
      Parameters:
      a - first element.
      b - second element.

    • countComponents

      public int countComponents()
      Count the distinct sets among the added elements.
      Returns:
      the number of distinct roots.