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.
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 SourceDisjointSet(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 SourceCount
Number of distinct sets.
Declaration
public int Count { get; }
Property Value
Type | Description |
---|---|
int |
Methods
View SourceAsReadOnly()
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. |
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. |
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. |
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. |
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.
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 SourceSetsJoined
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>> |