Class DisjointSet
Basic representation of a disjoint set data structure.
Implements
Inherited Members
Namespace: GoRogue
Assembly: GoRogue.dll
Syntax
public class DisjointSet : IReadOnlyDisjointSet
Remarks
For reasons pertaining to optimization, this disjoint set implementation does not use generics, and instead holds integer values, which will be exactly all integer values in range [0, num_items_in_set - 1]. Thus, you will need to assign appropriate IDs to objects you intend to add and map them appropriately.
Constructors
View SourceDisjointSet(int)
Constructor. The disjoint set will contain all values in range [0, size
- 1].
Declaration
public DisjointSet(int size)
Parameters
Type | Name | Description |
---|---|---|
int | size | (Max) size of the disjoint set. |
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 AsReadOnly()
Returns
Type | Description |
---|---|
IReadOnlyDisjointSet | A read-only representation of the disjoint set. |
ExtendToString(Func<int, 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<int, string> elementStringifier)
Parameters
Type | Name | Description |
---|---|---|
Func<int, string> | elementStringifier |
Returns
Type | Description |
---|---|
string | A string representation of the DisjointSet. |
Find(int)
Returns the ID for the parent of the set containing the set with ID objectID
,
performing path compression as search is completed.
Declaration
public int Find(int obj)
Parameters
Type | Name | Description |
---|---|---|
int | obj |
Returns
Type | Description |
---|---|
int | The ID for the parent of the object given. |
InSameSet(int, int)
Returns true if the objects specified by the given IDs are in the same set.
Declaration
public bool InSameSet(int obj1, int obj2)
Parameters
Type | Name | Description |
---|---|---|
int | obj1 | |
int | obj2 |
Returns
Type | Description |
---|---|
bool | True if the the objects specified by the given IDs are in the same set, false otherwise. |
MakeUnion(int, int)
Performs a union of the sets containing the objects specified by the two IDs. After this operation, every element in the sets containing the two objects specified will be part of one larger set.
Declaration
public void MakeUnion(int obj1, int obj2)
Parameters
Type | Name | Description |
---|---|---|
int | obj1 | |
int | obj2 |
Remarks
If the two elements are already in the same set, nothing is done.
ToString()
Returns a string representation of the DisjointSet, showing IDs of parents and all elements in their set.
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 IDs of the two sets that were joined.
Declaration
public event EventHandler<JoinedEventArgs>? SetsJoined
Event Type
Type | Description |
---|---|
EventHandler<JoinedEventArgs> |