Packages

trait DisjointSetUnion[V] extends IterableOnce[V]

Disjoint-Set Data Structure (a.k.a. Union-Find)

Manages a collection of disjoint sets. Each set contains no duplicate members. Like an array, an index identifies each member.

Provides some operations on almost constant time:

  • Determines whether the two members are in the same group
  • Finds a value of the representative member of the group containing the given members
  • Merges two sets into a single group containing the given members

If two sets are merged into a new single set, the representative member's value of the new set is calculated from the representative members' values of the two sets to merge. For this calculation, cats.kernel.CommutativeSemigroup must be available.

Expects that the semigroup-combine calculation will complete in a constant time, but not required. Suppose the calculation completes in O(K). The time complexity of almost operation are multiplied by such time O(K).

V

Type of the members in the sets

Linear Supertypes
IterableOnce[V], AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. DisjointSetUnion
  2. IterableOnce
  3. AnyRef
  4. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Abstract Value Members

  1. abstract def apply(v: Int): V

    Alias of find

  2. abstract def find(v: Int): V

    Finds a value of the representative of the group containing the given member index

    Finds a value of the representative of the group containing the given member index

    Exceptions thrown

    java.lang.IndexOutOfBoundsException if the index is out of bounds

    Note

    Time Complexity: O(a(N)) amortized

  3. abstract def groupCount: Int

    Returns the number of groups

    Returns the number of groups

    Note

    Time Complexity: O(1)

  4. abstract def groups: Set[Set[Int]]

    Return groups containing its member indices

    Return groups containing its member indices

    Note

    Time Complexity: ~= O(a(N) N)

  5. abstract def isSame(u: Int, v: Int): Boolean

    Returns true if the same group contains the given member indices

    Returns true if the same group contains the given member indices

    Exceptions thrown

    java.lang.IndexOutOfBoundsException if the index is out of bounds

    Note

    Time Complexity: O(a(N)) amortized

  6. abstract def iterator: Iterator[V]
    Definition Classes
    IterableOnce
  7. abstract def size: Int

    Returns the number of members

    Returns the number of members

    Note

    Time Complexity: O(1)

  8. abstract def unite(u: Int, v: Int): DisjointSetUnion.this.type

    Merge two groups into a single group containing the given member indices

    Merge two groups into a single group containing the given member indices

    Exceptions thrown

    java.lang.IndexOutOfBoundsException if the index is out of bounds

    Note

    Time Complexity: O(a(N)) amortized

Concrete Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @native() @HotSpotIntrinsicCandidate()
  6. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  7. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  8. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  9. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  10. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  11. def knownSize: Int
    Definition Classes
    IterableOnce
  12. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  13. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  14. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  15. def stepper[S <: Stepper[_]](implicit shape: StepperShape[V, S]): S
    Definition Classes
    IterableOnce
  16. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  17. def toString(): String
    Definition Classes
    AnyRef → Any
  18. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  19. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  20. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable]) @Deprecated
    Deprecated

Inherited from IterableOnce[V]

Inherited from AnyRef

Inherited from Any

Ungrouped