|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Collections.Generic;
using System.Diagnostics;
namespace System.Collections.Immutable
{
/// <content>
/// Contains the inner <see cref="ImmutableHashSet{T}.HashBucket"/> struct.
/// </content>
public partial class ImmutableHashSet<T>
{
/// <summary>
/// The result of a mutation operation.
/// </summary>
internal enum OperationResult
{
/// <summary>
/// The change required element(s) to be added or removed from the collection.
/// </summary>
SizeChanged,
/// <summary>
/// No change was required (the operation ended in a no-op).
/// </summary>
NoChangeRequired,
}
/// <summary>
/// Contains all the keys in the collection that hash to the same value.
/// </summary>
#pragma warning disable CA1066 // Implement IEquatable when overriding Object.Equals
internal readonly struct HashBucket
#pragma warning restore CA1066
{
/// <summary>
/// One of the values in this bucket.
/// </summary>
private readonly T _firstValue;
/// <summary>
/// Any other elements that hash to the same value.
/// </summary>
/// <value>
/// This is null if and only if the entire bucket is empty (including <see cref="_firstValue"/>).
/// It's empty if <see cref="_firstValue"/> has an element but no additional elements.
/// </value>
private readonly ImmutableList<T>.Node _additionalElements;
/// <summary>
/// Initializes a new instance of the <see cref="HashBucket"/> struct.
/// </summary>
/// <param name="firstElement">The first element.</param>
/// <param name="additionalElements">The additional elements.</param>
private HashBucket(T firstElement, ImmutableList<T>.Node? additionalElements = null)
{
_firstValue = firstElement;
_additionalElements = additionalElements ?? ImmutableList<T>.Node.EmptyNode;
}
/// <summary>
/// Gets a value indicating whether this instance is empty.
/// </summary>
/// <value>
/// <c>true</c> if this instance is empty; otherwise, <c>false</c>.
/// </value>
internal bool IsEmpty
{
get { return _additionalElements == null; }
}
/// <summary>
/// Returns an enumerator that iterates through the collection.
/// </summary>
public Enumerator GetEnumerator()
{
return new Enumerator(this);
}
/// <summary>
/// Throws an exception to catch any errors in comparing <see cref="HashBucket"/> instances.
/// </summary>
public override bool Equals(object? obj)
{
// This should never be called, as hash buckets don't know how to equate themselves.
throw new NotSupportedException();
}
/// <summary>
/// Throws an exception to catch any errors in comparing <see cref="HashBucket"/> instances.
/// </summary>
public override int GetHashCode()
{
// This should never be called, as hash buckets don't know how to hash themselves.
throw new NotSupportedException();
}
/// <summary>
/// Checks whether this <see cref="HashBucket"/> is exactly like another one,
/// comparing by reference. For use when type parameter T is an object.
/// </summary>
/// <param name="other">The other bucket.</param>
/// <returns><c>true</c> if the two <see cref="HashBucket"/> structs have precisely the same values.</returns>
internal bool EqualsByRef(HashBucket other)
{
return object.ReferenceEquals(_firstValue, other._firstValue)
&& object.ReferenceEquals(_additionalElements, other._additionalElements);
}
/// <summary>
/// Checks whether this <see cref="HashBucket"/> is exactly like another one,
/// comparing by value. For use when type parameter T is a struct.
/// </summary>
/// <param name="other">The other bucket.</param>
/// <param name="valueComparer">The comparer to use for the first value in the bucket.</param>
/// <returns><c>true</c> if the two <see cref="HashBucket"/> structs have precisely the same values.</returns>
internal bool EqualsByValue(HashBucket other, IEqualityComparer<T> valueComparer)
{
return valueComparer.Equals(_firstValue, other._firstValue)
&& object.ReferenceEquals(_additionalElements, other._additionalElements);
}
/// <summary>
/// Adds the specified value.
/// </summary>
/// <param name="value">The value.</param>
/// <param name="valueComparer">The value comparer.</param>
/// <param name="result">A description of the effect was on adding an element to this <see cref="HashBucket"/>.</param>
/// <returns>A new <see cref="HashBucket"/> that contains the added value and any values already held by this <see cref="HashBucket"/>.</returns>
internal HashBucket Add(T value, IEqualityComparer<T> valueComparer, out OperationResult result)
{
if (this.IsEmpty)
{
result = OperationResult.SizeChanged;
return new HashBucket(value);
}
if (valueComparer.Equals(value, _firstValue) || _additionalElements.IndexOf(value, valueComparer) >= 0)
{
result = OperationResult.NoChangeRequired;
return this;
}
result = OperationResult.SizeChanged;
return new HashBucket(_firstValue, _additionalElements.Add(value));
}
/// <summary>
/// Determines whether the <see cref="HashBucket"/> contains the specified value.
/// </summary>
/// <param name="value">The value.</param>
/// <param name="valueComparer">The value comparer.</param>
internal bool Contains(T value, IEqualityComparer<T> valueComparer)
{
if (this.IsEmpty)
{
return false;
}
return valueComparer.Equals(value, _firstValue) || _additionalElements.IndexOf(value, valueComparer) >= 0;
}
/// <summary>
/// Searches the set for a given value and returns the equal value it finds, if any.
/// </summary>
/// <param name="value">The value to search for.</param>
/// <param name="valueComparer">The value comparer.</param>
/// <param name="existingValue">The value from the set that the search found, or the original value if the search yielded no match.</param>
/// <returns>
/// A value indicating whether the search was successful.
/// </returns>
internal bool TryExchange(T value, IEqualityComparer<T> valueComparer, out T existingValue)
{
if (!this.IsEmpty)
{
if (valueComparer.Equals(value, _firstValue))
{
existingValue = _firstValue;
return true;
}
int index = _additionalElements.IndexOf(value, valueComparer);
if (index >= 0)
{
existingValue = _additionalElements.ItemRef(index);
return true;
}
}
existingValue = value;
return false;
}
/// <summary>
/// Removes the specified value if it exists in the collection.
/// </summary>
/// <param name="value">The value.</param>
/// <param name="equalityComparer">The equality comparer.</param>
/// <param name="result">A description of the effect was on adding an element to this <see cref="HashBucket"/>.</param>
/// <returns>A new <see cref="HashBucket"/> that does not contain the removed value and any values already held by this <see cref="HashBucket"/>.</returns>
internal HashBucket Remove(T value, IEqualityComparer<T> equalityComparer, out OperationResult result)
{
if (this.IsEmpty)
{
result = OperationResult.NoChangeRequired;
return this;
}
if (equalityComparer.Equals(_firstValue, value))
{
if (_additionalElements.IsEmpty)
{
result = OperationResult.SizeChanged;
return default;
}
else
{
// We can promote any element from the list into the first position, but it's most efficient
// to remove the root node in the binary tree that implements the list.
int indexOfRootNode = _additionalElements.Left!.Count;
result = OperationResult.SizeChanged;
return new HashBucket(_additionalElements.Key, _additionalElements.RemoveAt(indexOfRootNode));
}
}
int index = _additionalElements.IndexOf(value, equalityComparer);
if (index < 0)
{
result = OperationResult.NoChangeRequired;
return this;
}
else
{
result = OperationResult.SizeChanged;
return new HashBucket(_firstValue, _additionalElements.RemoveAt(index));
}
}
/// <summary>
/// Freezes this instance so that any further mutations require new memory allocations.
/// </summary>
internal void Freeze()
{
_additionalElements?.Freeze();
}
/// <summary>
/// Enumerates all the elements in this instance.
/// </summary>
internal struct Enumerator : IEnumerator<T>, IDisposable
{
/// <summary>
/// The bucket being enumerated.
/// </summary>
private readonly HashBucket _bucket;
/// <summary>
/// A value indicating whether this enumerator has been disposed.
/// </summary>
private bool _disposed;
/// <summary>
/// The current position of this enumerator.
/// </summary>
private Position _currentPosition;
/// <summary>
/// The enumerator that represents the current position over the <see cref="_additionalElements"/> of the <see cref="HashBucket"/>.
/// </summary>
private ImmutableList<T>.Enumerator _additionalEnumerator;
/// <summary>
/// Initializes a new instance of the <see cref="ImmutableHashSet{T}.HashBucket.Enumerator"/> struct.
/// </summary>
/// <param name="bucket">The bucket.</param>
internal Enumerator(HashBucket bucket)
{
_disposed = false;
_bucket = bucket;
_currentPosition = Position.BeforeFirst;
_additionalEnumerator = default(ImmutableList<T>.Enumerator);
}
/// <summary>
/// Describes the positions the enumerator state machine may be in.
/// </summary>
private enum Position
{
/// <summary>
/// The first element has not yet been moved to.
/// </summary>
BeforeFirst,
/// <summary>
/// We're at the <see cref="_firstValue"/> of the containing bucket.
/// </summary>
First,
/// <summary>
/// We're enumerating the <see cref="_additionalElements"/> in the bucket.
/// </summary>
Additional,
/// <summary>
/// The end of enumeration has been reached.
/// </summary>
End,
}
/// <summary>
/// Gets the current element.
/// </summary>
object? IEnumerator.Current
{
get { return this.Current; }
}
/// <summary>
/// Gets the current element.
/// </summary>
public T Current
{
get
{
this.ThrowIfDisposed();
return _currentPosition switch
{
Position.First => _bucket._firstValue,
Position.Additional => _additionalEnumerator.Current,
_ => throw new InvalidOperationException(),
};
}
}
/// <summary>
/// Advances the enumerator to the next element of the collection.
/// </summary>
/// <returns>
/// true if the enumerator was successfully advanced to the next element; false if the enumerator has passed the end of the collection.
/// </returns>
/// <exception cref="InvalidOperationException">The collection was modified after the enumerator was created. </exception>
public bool MoveNext()
{
this.ThrowIfDisposed();
if (_bucket.IsEmpty)
{
_currentPosition = Position.End;
return false;
}
switch (_currentPosition)
{
case Position.BeforeFirst:
_currentPosition = Position.First;
return true;
case Position.First:
if (_bucket._additionalElements.IsEmpty)
{
_currentPosition = Position.End;
return false;
}
_currentPosition = Position.Additional;
_additionalEnumerator = new ImmutableList<T>.Enumerator(_bucket._additionalElements);
return _additionalEnumerator.MoveNext();
case Position.Additional:
return _additionalEnumerator.MoveNext();
case Position.End:
return false;
default:
throw new InvalidOperationException();
}
}
/// <summary>
/// Sets the enumerator to its initial position, which is before the first element in the collection.
/// </summary>
/// <exception cref="InvalidOperationException">The collection was modified after the enumerator was created. </exception>
public void Reset()
{
this.ThrowIfDisposed();
_additionalEnumerator.Dispose();
_currentPosition = Position.BeforeFirst;
}
/// <summary>
/// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
/// </summary>
public void Dispose()
{
_disposed = true;
_additionalEnumerator.Dispose();
}
/// <summary>
/// Throws an <see cref="ObjectDisposedException"/> if this enumerator has been disposed.
/// </summary>
private void ThrowIfDisposed()
{
if (_disposed)
{
Requires.FailObjectDisposed(this);
}
}
}
}
}
}
|