Package edu.claflin.finder.struct

# Class DisjointSet<T extends Comparable<T>>

java.lang.Object
edu.claflin.finder.struct.DisjointSet<T>

public class DisjointSet<T extends Comparable<T>> extends Object
A LinkedList-based Disjoint Set data structure. Three operations combined O(m * + n* log(n)).

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `private int`
  `length`
  `private LinkedList<T>[]`
  `list`
  `private int`
  `size`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `DisjointSet(int size)`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `private boolean`
  `contains(T a)`
  Whether the given object is in the disjoint sets.
  `boolean`
  `disjointElements(T a, T b)`
  Whether two given elements are not in the same set
  `private T`
  `find(T x)`
  Get the representative of the set the given object is in.
  `void`
  `makeSet(T n)`
  Create a new disjoint set with the given element.
  `void`
  `merge(T a, T b)`
  Merge the disjoint sets two elements are in
  `int`
  `size()`
  Get the number of disjoint sets.
  `String`
  `toString()`

  ### Methods inherited from class java.lang.Object

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

- ## Field Details

  - ### list

    private LinkedList<T extends Comparable<T>>[] list

  - ### size

    private int size

  - ### length

    private int length

- ## Constructor Details

  - ### DisjointSet

    public DisjointSet(int size)

- ## Method Details

  - ### size

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

  - ### contains

    private boolean contains(T a)
    Whether the given object is in the disjoint sets.
    Parameters:
      `a` - the object to determined whether it is in the disjoint sets
    Returns:
      true if the object is in the disjoint set, false otherwise

  - ### makeSet

    public void makeSet(T n)
    Create a new disjoint set with the given element.
    Parameters:
      `n` - the new element

  - ### find

    private T find(T x)
    Get the representative of the set the given object is in.
    Parameters:
      `x` - the object to find the representative of
    Returns:
      the representative

  - ### disjointElements

    public boolean disjointElements(T a, T b)
    Whether two given elements are not in the same set
    Parameters:
      `a` - the first element
      `b` - the second element
    Returns:
      whether the elements are not in the same set

  - ### merge

    public void merge(T a, T b)
    Merge the disjoint sets two elements are in
    Parameters:
      `a` - the first element
      `b` - the second element

  - ### toString

    public String toString()
    Overrides:
      `toString` in class `Object`