Class UnionFind

java.lang.Object
org.ek9lang.compiler.phase5.UnionFind
class UnionFind extends Object
Union-Find (Disjoint Set Union) data structure for O(n * alpha(n)) connected components. Used by LCOM4 cohesion calculation to find groups of methods that share field access.

Uses path compression and union by rank for near-constant time operations. Alpha(n) is the inverse Ackermann function - effectively constant for practical inputs.

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

  • Constructor Details

    • UnionFind

      UnionFind()

  • Method Details

    • add

      void add(String element)
      Add an element to the union-find structure. Initially, each element is in its own set (parent is itself).
      Parameters:
      element - the element to add

    • find

      String find(String element)
      Find the root of the set containing the element. Uses path compression to flatten the tree structure.
      Parameters:
      element - the element to find
      Returns:
      the root of the set, or the element if not found

    • union

      void union(String a, String b)
      Union two elements into the same set. Uses union by rank to keep trees balanced.
      Parameters:
      a - first element
      b - second element

    • countComponents

      int countComponents()
      Count the number of distinct connected components (sets).
      Returns:
      the number of distinct roots