| | | 1 | | namespace MoreStructures.DisjointSets; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// An <see cref="IDisjointSet"/> implementation based on a simple <see cref="List{T}"/> to store set ids of each of |
| | | 5 | | /// the values stored in the Disjoint Set. |
| | | 6 | | /// </summary> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// - This implementation optimizes <see cref="Find(int)"/> and <see cref="AreConnected(int, int)"/> runtime, making |
| | | 9 | | /// them constant-time operations, at the cost of <see cref="Union(int, int)"/>, which requires a full scan of the |
| | | 10 | | /// underlying list and hence is a O(n) operation. |
| | | 11 | | /// <br/> |
| | | 12 | | /// - Check <see cref="QuickUnionDisjointSet"/> for an alternative implementation of <see cref="IDisjointSet"/> which |
| | | 13 | | /// does the opposite, in terms of optimization. |
| | | 14 | | /// </remarks> |
| | | 15 | | public class QuickFindDisjointSet : IDisjointSet |
| | | 16 | | { |
| | 474 | 17 | | private int[] SetIds { get; } |
| | | 18 | | |
| | | 19 | | /// <summary> |
| | | 20 | | /// Builds a Disjoint Set structure containing <paramref name="valuesCount"/> disjoint values, each one into its |
| | | 21 | | /// own singleton set. |
| | | 22 | | /// </summary> |
| | | 23 | | /// <param name="valuesCount"><inheritdoc cref="ValuesCount" path="/summary"/></param> |
| | | 24 | | /// <remarks> |
| | | 25 | | /// Requires initializing all the <paramref name="valuesCount"/> items of the underlying list. |
| | | 26 | | /// <br/> |
| | | 27 | | /// Time and Space Complexity are O(n). |
| | | 28 | | /// </remarks> |
| | 22 | 29 | | public QuickFindDisjointSet(int valuesCount) |
| | 22 | 30 | | { |
| | 22 | 31 | | ValuesCount = valuesCount >= 0 |
| | 22 | 32 | | ? valuesCount |
| | 22 | 33 | | : throw new ArgumentException("Must be non-negative.", nameof(valuesCount)); |
| | 20 | 34 | | SetIds = new int[valuesCount]; |
| | | 35 | | |
| | 356 | 36 | | for (var i = 0; i < ValuesCount; i++) |
| | 158 | 37 | | SetIds[i] = i; |
| | 20 | 38 | | } |
| | | 39 | | |
| | | 40 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 41 | | /// <remarks> |
| | | 42 | | /// Set at construction time, based on the constructor parameter. |
| | | 43 | | /// <br/> |
| | | 44 | | /// Time and Space Complexity are O(1). |
| | | 45 | | /// </remarks> |
| | 611 | 46 | | public int ValuesCount { get; } |
| | | 47 | | |
| | | 48 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 49 | | /// <remarks> |
| | | 50 | | /// Obtained as the number of distinct values in the underlying list, which is scanned linearly. |
| | | 51 | | /// <br/> |
| | | 52 | | /// Time Complexity is O(n) and Space Complexity is O(1), where n is <see cref="ValuesCount"/>. |
| | | 53 | | /// </remarks> |
| | 8 | 54 | | public int SetsCount => SetIds.Distinct().Count(); |
| | | 55 | | |
| | | 56 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 57 | | /// <remarks> |
| | | 58 | | /// Calculated in constant-time by comparing the set id of the first value with the set id of the second value. |
| | | 59 | | /// <br/> |
| | | 60 | | /// Time and Space Complexity are O(1). |
| | | 61 | | /// </remarks> |
| | | 62 | | public bool AreConnected(int first, int second) |
| | 25 | 63 | | { |
| | 25 | 64 | | if (ValuesCount == 0) |
| | 1 | 65 | | throw new InvalidOperationException( |
| | 1 | 66 | | $"{nameof(AreConnected)} cannot be invoked on an empty queue."); |
| | 24 | 67 | | if (first < 0 || first >= ValuesCount) |
| | 2 | 68 | | throw new ArgumentException( |
| | 2 | 69 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(first)); |
| | 22 | 70 | | if (second < 0 || second >= ValuesCount) |
| | 2 | 71 | | throw new ArgumentException( |
| | 2 | 72 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(second)); |
| | | 73 | | |
| | 20 | 74 | | return SetIds[first] == SetIds[second]; |
| | 20 | 75 | | } |
| | | 76 | | |
| | | 77 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 78 | | /// <remarks> |
| | | 79 | | /// Calculated in constant-time by retrieving the set id at index <paramref name="value"/> in the underlying list. |
| | | 80 | | /// </remarks> |
| | | 81 | | public int Find(int value) |
| | 85 | 82 | | { |
| | 85 | 83 | | if (ValuesCount == 0) |
| | 2 | 84 | | throw new InvalidOperationException( |
| | 2 | 85 | | $"{nameof(AreConnected)} cannot be invoked on an empty queue."); |
| | 83 | 86 | | if (value < 0 || value >= ValuesCount) |
| | 7 | 87 | | throw new ArgumentException( |
| | 7 | 88 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(value)); |
| | | 89 | | |
| | 76 | 90 | | return SetIds[value]; |
| | 76 | 91 | | } |
| | | 92 | | |
| | | 93 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 94 | | /// <remarks> |
| | | 95 | | /// Retrieves the set id A of <paramref name="first"/> and B of <paramref name="second"/>, via <see cref="Find"/>. |
| | | 96 | | /// <br/> |
| | | 97 | | /// Then replaces all occurrences of B with A, in the underlying list. |
| | | 98 | | /// <br/> |
| | | 99 | | /// Time Complexity is O(n) and Space Complexity is O(1). |
| | | 100 | | /// </remarks> |
| | | 101 | | public void Union(int first, int second) |
| | 28 | 102 | | { |
| | 28 | 103 | | var firstSetId = Find(first); |
| | 25 | 104 | | var secondSetId = Find(second); |
| | | 105 | | |
| | 23 | 106 | | if (firstSetId == secondSetId) |
| | 6 | 107 | | return; |
| | | 108 | | |
| | 374 | 109 | | for (var i = 0; i < ValuesCount; i++) |
| | 170 | 110 | | if (SetIds[i] == secondSetId) |
| | 22 | 111 | | SetIds[i] = firstSetId; |
| | 23 | 112 | | } |
| | | 113 | | } |