Class DisjointSet<T>

An easier-to-use (but less efficient) variant of DisjointSet. This version takes actual objects of type T, and manages IDs for you automatically.

Inheritance
object
DisjointSet<T>
Implements
Inherited Members
Namespace: GoRogue
Assembly: GoRogue.dll
Syntax
public class DisjointSet<T> : IReadOnlyDisjointSet<T> where T : notnull
Type Parameters
Name Description
T

Type of elements in the set.
Remarks

This set structure is effectively exactly like DisjointSet, however it takes type T instead of IDs. For the sake of efficiency, it still requires the number of elements to be known when the set is created.

Constructors

View Source

DisjointSet(IEnumerable<T>, IEqualityComparer<T>?)

Creates a new disjoint set that is composed of the given items. Each item will be its own unique set.

Declaration
public DisjointSet(IEnumerable<T> items, IEqualityComparer<T>? comparer = null)
Parameters
Type Name Description
IEnumerable<T> items

Items to place in the disjoint set.
IEqualityComparer<T> comparer

Optional comparer to use when hashing items.
Remarks

The items will be mapped to IDs in the range [0, items.Length - 1] via a Dictionary, where the keys are hashed using the comparer specified, or the default hash function if no comparer is specified.

Properties

View Source

Count

Number of distinct sets.

Declaration
public int Count { get; }
Property Value
Type Description
int

Methods

View Source

AsReadOnly()

Returns a read-only representation of the disjoint set.

Declaration
public IReadOnlyDisjointSet<T> AsReadOnly()
Returns
Type Description
IReadOnlyDisjointSet<T>

A read-only representation of the disjoint set.
View Source

ExtendToString(Func<T, string>)

Returns a string representation of the DisjointSet, showing parents and all elements in their set. The given function is used to produce the string for each element.

Declaration
public string ExtendToString(Func<T, string> elementStringifier)
Parameters
Type Name Description
Func<T, string> elementStringifier
Returns
Type Description
string

A string representation of the DisjointSet.
View Source

Find(T)

Returns the parent of the set containing item, performing path compression as search is completed.

Declaration
public T Find(T item)
Parameters
Type Name Description
T item

Object to search for.
Returns
Type Description
T

The parent of the object given.
View Source

InSameSet(T, T)

Returns true if the two objects specified are in the same set.

Declaration
public bool InSameSet(T item1, T item2)
Parameters
Type Name Description
T item1
T item2
Returns
Type Description
bool

True if the two objects are in the same set, false otherwise.
View Source

MakeUnion(T, T)

Performs a union of the sets containing the two objects specified. After this operation, every element in the sets containing the two objects specified will be part of one larger set.

Declaration
public void MakeUnion(T item1, T item2)
Parameters
Type Name Description
T item1
T item2
Remarks

If the two elements are already in the same set, nothing is done.

View Source

ToString()

Returns a string representation of the DisjointSet, parents and all elements in their set. The element's default ToString method is used to produce the string.

Declaration
public override string ToString()
Returns
Type Description
string

A string representation of the DisjointSet.
Overrides

Events

View Source

SetsJoined

Fired when two sets are joined into one. The arguments give the two sets that were joined.

Declaration
public event EventHandler<JoinedEventArgs<T>>? SetsJoined
Event Type
Type Description
EventHandler<JoinedEventArgs<T>>

Implements

Extension Methods