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

Class DisjointIntegerSetForest

java.lang.Object
org.cicirello.ds.DisjointIntegerSetForest
All Implemented Interfaces:
Copyable<DisjointIntegerSetForest>
public final class DisjointIntegerSetForest extends Object implements Copyable<DisjointIntegerSetForest>
Disjoint sets of integers from [0, n) implemented with a disjoint set forest. An instance of this class represents a set of disjoint sets of the n integers: {0, 1, ..., n-1}. Initially each integer is in a set by itself, and the class provides methods for combining sets and checking if elements are in the same 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 objects, see the DisjointSetForest class.

  • Constructor Summary

    Constructors
    Constructor
    Description
    DisjointIntegerSetForest(int n)
    Initializes a disjoint set forest containing the integers from 0 through n-1, each initially in a set by itself.

  • Method Summary

    Modifier and Type
    Method
    Description
    DisjointIntegerSetForest
    copy()
    Creates an identical copy of this object.
    boolean
    equals(Object other)
    Checks if this DisjointIntegerSetForest is equal to another.
    int
    findSet(int element)
    Finds the id of the set currently containing the element.
    int
    hashCode()
    Computes a hashCode for the DisjointIntegerSetForest.
    boolean
    sameSet(int element1, int element2)
    Checks whether or not two elements are in the same set.
    int
    size()
    Gets the size of the DisjointIntegerSetForest in total number of elements.
    void
    union(int element1, int 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, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • DisjointIntegerSetForest

      public DisjointIntegerSetForest(int n)
      Initializes a disjoint set forest containing the integers from 0 through n-1, each initially in a set by itself.
      Parameters:
      n - The number of integers in the disjoint set forest.

  • Method Details

    • copy

      public DisjointIntegerSetForest copy()
      Description copied from interface: Copyable
      Creates an identical copy of this object.
      Specified by:
      copy in interface Copyable<DisjointIntegerSetForest>
      Returns:
      an identical copy of this object.

    • equals

      public boolean equals(Object other)
      Checks if this DisjointIntegerSetForest is equal to another. This test of equality is true if and only if the two DisjointIntegerSetForest are structurally the same (i.e., not just same set of disjoint sets, but also exact same internal structure).
      Overrides:
      equals in class Object
      Parameters:
      other - The other DisjointIntegerSetForest.
      Returns:
      true if and only if two DisjointIntegerSetForest instances are structurally identical.

    • hashCode

      public int hashCode()
      Computes a hashCode for the DisjointIntegerSetForest.
      Overrides:
      hashCode in class Object
      Returns:
      a hashCode

    • findSet

      public int findSet(int 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, which must be in [0,n).
      Returns:
      the id of the set that currently contains the element, where the id is a representative member of that set.
      Throws:
      ArrayIndexOutOfBoundsException - if element is less than 0 or if element is greater than or equal to n.

    • sameSet

      public boolean sameSet(int element1, int element2)
      Checks whether or not two elements are in the same set.
      Parameters:
      element1 - The first element, which must be in [0,n).
      element2 - The second element, which must be in [0,n).
      Returns:
      true if and only if element1 and element2 are elements in the same set of the disjoint set forest.
      Throws:
      ArrayIndexOutOfBoundsException - if element1 or element2 is less than 0 or if element1 or element2 is greater than or equal to n.

    • size

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

    • union

      public void union(int element1, int 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, which must be in [0,n).
      element2 - A representative member of the other set, which must be in [0,n).
      Throws:
      ArrayIndexOutOfBoundsException - if either element1 or element2 is less than 0 or if element1 ot element2 is greater than or equal to n.