Package tools.refinery.interpreter.matchers.algorithms

Class UnionFind<V>

java.lang.Object
tools.refinery.interpreter.matchers.algorithms.UnionFind<V>
Type Parameters:
V - the type parameter of the element's stored in the union-find data structure
public class UnionFind<V> extends Object
Union-find data structure implementation. Note that the implementation relies on the correct implementation of the equals method of the type parameter's class.

  • Constructor Summary

    Constructors
    Constructor
    Description
    UnionFind()
    Instantiate a new union-find data structure.
    UnionFind(Iterable<V> elements)
    Instantiate a new union-find data structure with the given elements as separate sets.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    deleteSet(V root)
    Delete the set whose root is the given node.
    V
    find(V node)
    Find method with path compression.
    Set<V>
    getPartition(V element)
    Returns the partition in which the given element can be found, or null otherwise.
    Set<V>
    getPartitionHeads()
     
    Collection<Set<V>>
    getPartitions()
    Returns all partitions.
    boolean
    isSameUnion(Set<V> elements)
    Returns if all given elements are in the same partition.
    V
    makeSet(Collection<V> nodes)
    Creates a new union set from a collection of elements.
    V
    makeSet(V node)
    This method creates a single set containing the given node.
    V
    union(V x, V y)
    Union by rank implementation of the two sets which contain x and y; x and/or y can be a single element from the universe.
    void
    unite(Set<V> elements)
    Places the given elements in to the same partition.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • UnionFind

      public UnionFind()
      Instantiate a new union-find data structure.

    • UnionFind

      public UnionFind(Iterable<V> elements)
      Instantiate a new union-find data structure with the given elements as separate sets.

  • Method Details

    • makeSet

      public V makeSet(Collection<V> nodes)
      Creates a new union set from a collection of elements.
      Parameters:
      nodes - the collection of elements
      Returns:
      the root element

    • makeSet

      public V makeSet(V node)
      This method creates a single set containing the given node.
      Parameters:
      node - the root node of the set
      Returns:
      the root element

    • find

      public V find(V node)
      Find method with path compression.
      Parameters:
      node - the node to find
      Returns:
      the root node of the set in which the given node can be found

    • union

      public V union(V x, V y)
      Union by rank implementation of the two sets which contain x and y; x and/or y can be a single element from the universe.
      Parameters:
      x - set or single element of the universe
      y - set or single element of the universe
      Returns:
      the new root of the two sets

    • unite

      public void unite(Set<V> elements)
      Places the given elements in to the same partition.

    • deleteSet

      public void deleteSet(V root)
      Delete the set whose root is the given node.
      Parameters:
      root - the root node

    • isSameUnion

      public boolean isSameUnion(Set<V> elements)
      Returns if all given elements are in the same partition.

    • getPartition

      public Set<V> getPartition(V element)
      Returns the partition in which the given element can be found, or null otherwise.

    • getPartitions

      public Collection<Set<V>> getPartitions()
      Returns all partitions.

    • getPartitionHeads

      public Set<V> getPartitionHeads()