Module org.cicirello.core
Package org.cicirello.ds

Class DisjointSetForest<T>

java.lang.Object
org.cicirello.ds.DisjointSetForest<T>
Type Parameters:
T - The type of object contained in the DisjointSetForest.
public final class DisjointSetForest<T> extends Object
Represents disjoint sets of objects with a disjoint set forest. This class assumes that the objects in the sets are of a class that has appropriately implemented the Object.equals(java.lang.Object) and Object.hashCode() methods. If you rely on the default implementations of those methods from the Object class, then the disjoint set forest will treat two different objects containing same data as different objects (i.e., the default behavior of equals and hashCode when not overridden). Each object when first added to the DisjointSetForest is initially in a set by itself. The class provides methods for combining sets and checking if elements are in the same set, or in any set. It does not support splitting a set. It is implemented as Disjoint Set Forests are described by Cormen, Leiserson, Rivest, and Stein describe in Introduction to Algorithms, including the use of the union by rank heuristic and path compression.

For disjoint sets of integers, see the DisjointIntegerSetForest class.

  • Constructor Summary

    Constructors
    Constructor
    Description
    DisjointSetForest()
    Initializes an empty DisjointSetForest.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    contains(T element)
    Checks if an element is in the disjoint set forest.
    int
    findSet(T element)
    Finds the id of the set currently containing the element.
    void
    makeSet(T element)
    Adds a new set to the disjoint set forest containing only the new element.
    boolean
    sameSet(T element1, T element2)
    Checks whether or not two elements are in the same set.
    int
    size()
    Gets the size of the DisjointSetForest.
    void
    union(T element1, T element2)
    Merges two sets into one, where the sets are chosen by specifying a representative member of each.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • DisjointSetForest

      public DisjointSetForest()
      Initializes an empty DisjointSetForest.

  • Method Details

    • contains

      public boolean contains(T element)
      Checks if an element is in the disjoint set forest.
      Parameters:
      element - The element to check
      Returns:
      true if and only if element is in the disjoint set forest.

    • findSet

      public int findSet(T element)
      Finds the id of the set currently containing the element. Calls to this method also apply path compression to make subsequent calls faster.
      Parameters:
      element - The element whose set is sought.
      Returns:
      the id of the set that currently contains the element.
      Throws:
      IllegalArgumentException - if element is not in the DisjointSetForest.

    • makeSet

      public void makeSet(T element)
      Adds a new set to the disjoint set forest containing only the new element.
      Parameters:
      element - The new element to add to the disjoint set forest, which must not already exist within the DisjointSetForest.
      Throws:
      IllegalArgumentException - if element already exists in the DisjointSetForest.

    • sameSet

      public boolean sameSet(T element1, T element2)
      Checks whether or not two elements are in the same set.
      Parameters:
      element1 - The first element.
      element2 - The second element.
      Returns:
      true if and only if element1 and element2 are elements in the same set of the disjoint set forest.

    • size

      public int size()
      Gets the size of the DisjointSetForest.
      Returns:
      the number of elements in the DisjointSetForest.

    • union

      public void union(T element1, T element2)
      Merges two sets into one, where the sets are chosen by specifying a representative member of each. If the two elements are already in the same set, then no merger takes place. Calls to this method also apply path compression while finding the sets containing each of the elements, and the union itself uses the union by rank heuristic. The combination of these two should improve cost of subsequent operations.
      Parameters:
      element1 - A representative member of one of the sets.
      element2 - A representative member of the other set.
      Throws:
      IllegalArgumentException - if either of the elements doesn't exist in the DisjointSetForest.