Class StandardUnionFind<E>

  • Type Parameters:
    E - element type
    All Implemented Interfaces:
    UnionFind<E>, java.io.Serializable

    public class StandardUnionFind<E>
    extends java.lang.Object
    implements java.io.Serializable, UnionFind<E>
    A Union-Find implementation.

    This class implements Union-Find algorithm with rank and path compression.

    See algorithmist for more detail.

    See Also:
    Serialized Form
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(E e)
      Adds the given element to a new set if it is not already in a set.
      java.util.Collection<java.util.Set<E>> allEquivalenceClasses()
      Returns an immutable collection containing all equivalence classes.
      boolean areEquivalent​(E a, E b)
      Returns true if a and b belong to the same equivalence class.
      java.util.Set<E> elements()
      Returns an unmodifiable set of all elements added to the UnionFind.
      E find​(E e)
      Returns the representative of the equivalence class of e.
      java.util.Set<E> findAll​(E value)
      Returns the elements in the same equivalence class as value.
      E union​(E a, E b)
      Unions the equivalence classes of a and b and returns the representative of the resulting equivalence class.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • StandardUnionFind

        public StandardUnionFind()
        Creates an empty UnionFind structure.
      • StandardUnionFind

        public StandardUnionFind​(UnionFind<E> other)
        Creates an UnionFind structure being a copy of other structure. The created structure is optimal in a sense that the paths to the root from any element will have a length of at most 1.
        Parameters:
        other - structure to be copied
    • Method Detail

      • add

        public void add​(E e)
        Description copied from interface: UnionFind
        Adds the given element to a new set if it is not already in a set.
        Specified by:
        add in interface UnionFind<E>
      • union

        public E union​(E a,
                       E b)
        Description copied from interface: UnionFind
        Unions the equivalence classes of a and b and returns the representative of the resulting equivalence class. The elements will be added if they are not already present.
        Specified by:
        union in interface UnionFind<E>
      • find

        public E find​(E e)
        Description copied from interface: UnionFind
        Returns the representative of the equivalence class of e.
        Specified by:
        find in interface UnionFind<E>
      • areEquivalent

        public boolean areEquivalent​(E a,
                                     E b)
        Description copied from interface: UnionFind
        Returns true if a and b belong to the same equivalence class.
        Specified by:
        areEquivalent in interface UnionFind<E>
      • elements

        public java.util.Set<E> elements()
        Description copied from interface: UnionFind
        Returns an unmodifiable set of all elements added to the UnionFind.
        Specified by:
        elements in interface UnionFind<E>
      • allEquivalenceClasses

        public java.util.Collection<java.util.Set<E>> allEquivalenceClasses()
        Description copied from interface: UnionFind
        Returns an immutable collection containing all equivalence classes. The returned collection represents a snapshot of the current state and will not reflect changes made to the data structure.
        Specified by:
        allEquivalenceClasses in interface UnionFind<E>
      • findAll

        public java.util.Set<E> findAll​(E value)
        Description copied from interface: UnionFind
        Returns the elements in the same equivalence class as value.
        Specified by:
        findAll in interface UnionFind<E>
        Returns:
        an unmodifiable view. As equivalence classes are merged, this set will reflect those changes.