|
// 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;
using System.Diagnostics.CodeAnalysis;
namespace System.Collections.Immutable
{
/// <content>
/// Contains the inner <see cref="ImmutableDictionary{TKey, TValue}.Builder"/> class.
/// </content>
public sealed partial class ImmutableDictionary<TKey, TValue>
{
/// <summary>
/// A dictionary that mutates with little or no memory allocations,
/// can produce and/or build on immutable dictionary instances very efficiently.
/// </summary>
/// <remarks>
/// <para>
/// While <see cref="ImmutableDictionary{TKey, TValue}.AddRange(IEnumerable{KeyValuePair{TKey, TValue}})"/>
/// and other bulk change methods already provide fast bulk change operations on the collection, this class allows
/// multiple combinations of changes to be made to a set with equal efficiency.
/// </para>
/// <para>
/// Instance members of this class are <em>not</em> thread-safe.
/// </para>
/// </remarks>
[DebuggerDisplay("Count = {Count}")]
[DebuggerTypeProxy(typeof(IDictionaryDebugView<,>))]
public sealed class Builder : IDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue>, IDictionary
{
/// <summary>
/// The root of the binary tree that stores the collection. Contents are typically not entirely frozen.
/// </summary>
private SortedInt32KeyNode<HashBucket> _root = SortedInt32KeyNode<HashBucket>.EmptyNode;
/// <summary>
/// The comparers.
/// </summary>
private Comparers _comparers;
/// <summary>
/// The number of elements in this collection.
/// </summary>
private int _count;
/// <summary>
/// Caches an immutable instance that represents the current state of the collection.
/// </summary>
/// <value>Null if no immutable view has been created for the current version.</value>
private ImmutableDictionary<TKey, TValue>? _immutable;
/// <summary>
/// A number that increments every time the builder changes its contents.
/// </summary>
private int _version;
/// <summary>
/// The object callers may use to synchronize access to this collection.
/// </summary>
private object? _syncRoot;
/// <summary>
/// Initializes a new instance of the <see cref="ImmutableDictionary{TKey, TValue}.Builder"/> class.
/// </summary>
/// <param name="map">The map that serves as the basis for this Builder.</param>
internal Builder(ImmutableDictionary<TKey, TValue> map)
{
Requires.NotNull(map, nameof(map));
_root = map._root;
_count = map._count;
_comparers = map._comparers;
_immutable = map;
}
/// <summary>
/// Gets or sets the key comparer.
/// </summary>
/// <value>
/// The key comparer.
/// </value>
public IEqualityComparer<TKey> KeyComparer
{
get
{
return _comparers.KeyComparer;
}
set
{
Requires.NotNull(value, nameof(value));
if (value != this.KeyComparer)
{
Comparers comparers = Comparers.Get(value, this.ValueComparer);
var input = new MutationInput(SortedInt32KeyNode<HashBucket>.EmptyNode, comparers);
ImmutableDictionary<TKey, TValue>.MutationResult result = ImmutableDictionary<TKey, TValue>.AddRange(this, input);
_immutable = null;
_comparers = comparers;
_count = result.CountAdjustment; // offset from 0
this.Root = result.Root;
}
}
}
/// <summary>
/// Gets or sets the value comparer.
/// </summary>
/// <value>
/// The value comparer.
/// </value>
public IEqualityComparer<TValue> ValueComparer
{
get
{
return _comparers.ValueComparer;
}
set
{
Requires.NotNull(value, nameof(value));
if (value != this.ValueComparer)
{
// When the key comparer is the same but the value comparer is different, we don't need a whole new tree
// because the structure of the tree does not depend on the value comparer.
// We just need a new root node to store the new value comparer.
_comparers = _comparers.WithValueComparer(value);
_immutable = null; // invalidate cached immutable
}
}
}
#region IDictionary<TKey, TValue> Properties
/// <summary>
/// Gets the number of elements contained in the <see cref="ICollection{T}"/>.
/// </summary>
/// <returns>The number of elements contained in the <see cref="ICollection{T}"/>.</returns>
public int Count
{
get { return _count; }
}
/// <summary>
/// Gets a value indicating whether the <see cref="ICollection{T}"/> is read-only.
/// </summary>
/// <returns>true if the <see cref="ICollection{T}"/> is read-only; otherwise, false.</returns>
bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
{
get { return false; }
}
/// <summary>
/// See <see cref="IReadOnlyDictionary{TKey, TValue}"/>
/// </summary>
public IEnumerable<TKey> Keys
{
get
{
foreach (KeyValuePair<TKey, TValue> item in this)
{
yield return item.Key;
}
}
}
/// <summary>
/// Gets an <see cref="ICollection{T}"/> containing the keys of the <see cref="IDictionary{TKey, TValue}"/>.
/// </summary>
/// <returns>An <see cref="ICollection{T}"/> containing the keys of the object that implements <see cref="IDictionary{TKey, TValue}"/>.</returns>
ICollection<TKey> IDictionary<TKey, TValue>.Keys
{
get { return this.Keys.ToArray(this.Count); }
}
/// <summary>
/// See <see cref="IReadOnlyDictionary{TKey, TValue}"/>
/// </summary>
public IEnumerable<TValue> Values
{
get
{
foreach (KeyValuePair<TKey, TValue> item in this)
{
yield return item.Value;
}
}
}
/// <summary>
/// Gets an <see cref="ICollection{T}"/> containing the values in the <see cref="IDictionary{TKey, TValue}"/>.
/// </summary>
/// <returns>An <see cref="ICollection{T}"/> containing the values in the object that implements <see cref="IDictionary{TKey, TValue}"/>.</returns>
ICollection<TValue> IDictionary<TKey, TValue>.Values
{
get { return this.Values.ToArray(this.Count); }
}
#endregion
#region IDictionary Properties
/// <summary>
/// Gets a value indicating whether the <see cref="IDictionary"/> object has a fixed size.
/// </summary>
/// <returns>true if the <see cref="IDictionary"/> object has a fixed size; otherwise, false.</returns>
bool IDictionary.IsFixedSize
{
get { return false; }
}
/// <summary>
/// Gets a value indicating whether the <see cref="ICollection{T}"/> is read-only.
/// </summary>
/// <returns>true if the <see cref="ICollection{T}"/> is read-only; otherwise, false.
/// </returns>
bool IDictionary.IsReadOnly
{
get { return false; }
}
/// <summary>
/// Gets an <see cref="ICollection{T}"/> containing the keys of the <see cref="IDictionary{TKey, TValue}"/>.
/// </summary>
/// <returns>
/// An <see cref="ICollection{T}"/> containing the keys of the object that implements <see cref="IDictionary{TKey, TValue}"/>.
/// </returns>
ICollection IDictionary.Keys
{
get { return this.Keys.ToArray(this.Count); }
}
/// <summary>
/// Gets an <see cref="ICollection{T}"/> containing the values in the <see cref="IDictionary{TKey, TValue}"/>.
/// </summary>
/// <returns>
/// An <see cref="ICollection{T}"/> containing the values in the object that implements <see cref="IDictionary{TKey, TValue}"/>.
/// </returns>
ICollection IDictionary.Values
{
get { return this.Values.ToArray(this.Count); }
}
#endregion
#region ICollection Properties
/// <summary>
/// Gets an object that can be used to synchronize access to the <see cref="ICollection"/>.
/// </summary>
/// <returns>An object that can be used to synchronize access to the <see cref="ICollection"/>.</returns>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
object ICollection.SyncRoot
{
get
{
if (_syncRoot == null)
{
Threading.Interlocked.CompareExchange<object?>(ref _syncRoot, new object(), null);
}
return _syncRoot;
}
}
/// <summary>
/// Gets a value indicating whether access to the <see cref="ICollection"/> is synchronized (thread safe).
/// </summary>
/// <returns>true if access to the <see cref="ICollection"/> is synchronized (thread safe); otherwise, false.</returns>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
bool ICollection.IsSynchronized
{
get { return false; }
}
#endregion
#region IDictionary Methods
/// <summary>
/// Adds an element with the provided key and value to the <see cref="IDictionary"/> object.
/// </summary>
/// <param name="key">The <see cref="object"/> to use as the key of the element to add.</param>
/// <param name="value">The <see cref="object"/> to use as the value of the element to add.</param>
void IDictionary.Add(object key, object? value)
{
this.Add((TKey)key, (TValue)value!);
}
/// <summary>
/// Determines whether the <see cref="IDictionary"/> object contains an element with the specified key.
/// </summary>
/// <param name="key">The key to locate in the <see cref="IDictionary"/> object.</param>
/// <returns>
/// true if the <see cref="IDictionary"/> contains an element with the key; otherwise, false.
/// </returns>
bool IDictionary.Contains(object key)
{
return this.ContainsKey((TKey)key);
}
/// <summary>
/// Returns an <see cref="IDictionaryEnumerator"/> object for the <see cref="IDictionary"/> object.
/// </summary>
/// <returns>
/// An <see cref="IDictionaryEnumerator"/> object for the <see cref="IDictionary"/> object.
/// </returns>
IDictionaryEnumerator IDictionary.GetEnumerator()
{
return new DictionaryEnumerator<TKey, TValue>(this.GetEnumerator());
}
/// <summary>
/// Removes the element with the specified key from the <see cref="IDictionary"/> object.
/// </summary>
/// <param name="key">The key of the element to remove.</param>
void IDictionary.Remove(object key)
{
this.Remove((TKey)key);
}
/// <summary>
/// Gets or sets the element with the specified key.
/// </summary>
/// <param name="key">The key.</param>
/// <returns></returns>
object? IDictionary.this[object key]
{
get { return this[(TKey)key]; }
set { this[(TKey)key] = (TValue)value!; }
}
#endregion
#region ICollection methods
/// <summary>
/// Copies the elements of the <see cref="ICollection"/> to an <see cref="Array"/>, starting at a particular <see cref="Array"/> index.
/// </summary>
/// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the elements copied from <see cref="ICollection"/>. The <see cref="Array"/> must have zero-based indexing.</param>
/// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param>
void ICollection.CopyTo(Array array, int arrayIndex)
{
Requires.NotNull(array, nameof(array));
Requires.Range(arrayIndex >= 0, nameof(arrayIndex));
Requires.Range(array.Length >= arrayIndex + this.Count, nameof(arrayIndex));
foreach (KeyValuePair<TKey, TValue> item in this)
{
array.SetValue(new DictionaryEntry(item.Key, item.Value), arrayIndex++);
}
}
#endregion
/// <summary>
/// Gets the current version of the contents of this builder.
/// </summary>
internal int Version
{
get { return _version; }
}
/// <summary>
/// Gets the initial data to pass to a query or mutation method.
/// </summary>
private MutationInput Origin
{
get { return new MutationInput(this.Root, _comparers); }
}
/// <summary>
/// Gets or sets the root of this data structure.
/// </summary>
private SortedInt32KeyNode<HashBucket> Root
{
get
{
return _root;
}
set
{
// We *always* increment the version number because some mutations
// may not create a new value of root, although the existing root
// instance may have mutated.
_version++;
if (_root != value)
{
_root = value;
// Clear any cached value for the immutable view since it is now invalidated.
_immutable = null;
}
}
}
/// <summary>
/// Gets or sets the element with the specified key.
/// </summary>
/// <returns>The element with the specified key.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is null.</exception>
/// <exception cref="KeyNotFoundException">The property is retrieved and <paramref name="key"/> is not found.</exception>
/// <exception cref="NotSupportedException">The property is set and the <see cref="IDictionary{TKey, TValue}"/> is read-only.</exception>
public TValue this[TKey key]
{
get
{
TValue value;
if (!this.TryGetValue(key, out value!))
{
ThrowHelper.ThrowKeyNotFoundException(key);
}
return value;
}
set
{
ImmutableDictionary<TKey, TValue>.MutationResult result = ImmutableDictionary<TKey, TValue>.Add(key, value, KeyCollisionBehavior.SetValue, this.Origin);
this.Apply(result);
}
}
#region Public Methods
/// <summary>
/// Adds a sequence of values to this collection.
/// </summary>
/// <param name="items">The items.</param>
public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> items)
{
ImmutableDictionary<TKey, TValue>.MutationResult result = ImmutableDictionary<TKey, TValue>.AddRange(items, this.Origin);
this.Apply(result);
}
/// <summary>
/// Removes any entries from the dictionaries with keys that match those found in the specified sequence.
/// </summary>
/// <param name="keys">The keys for entries to remove from the dictionary.</param>
public void RemoveRange(IEnumerable<TKey> keys)
{
Requires.NotNull(keys, nameof(keys));
foreach (TKey key in keys)
{
this.Remove(key);
}
}
/// <summary>
/// Returns an enumerator that iterates through the collection.
/// </summary>
/// <returns>
/// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection.
/// </returns>
public Enumerator GetEnumerator()
{
return new Enumerator(_root, this);
}
/// <summary>
/// Gets the value for a given key if a matching key exists in the dictionary.
/// </summary>
/// <param name="key">The key to search for.</param>
/// <returns>The value for the key, or the default value of type <typeparamref name="TValue"/> if no matching key was found.</returns>
public TValue? GetValueOrDefault(TKey key)
{
return this.GetValueOrDefault(key, default(TValue)!);
}
/// <summary>
/// Gets the value for a given key if a matching key exists in the dictionary.
/// </summary>
/// <param name="key">The key to search for.</param>
/// <param name="defaultValue">The default value to return if no matching key is found in the dictionary.</param>
/// <returns>
/// The value for the key, or <paramref name="defaultValue"/> if no matching key was found.
/// </returns>
public TValue GetValueOrDefault(TKey key, TValue defaultValue)
{
Requires.NotNullAllowStructs(key, nameof(key));
TValue value;
if (this.TryGetValue(key, out value!))
{
return value;
}
return defaultValue;
}
/// <summary>
/// Creates an immutable dictionary based on the contents of this instance.
/// </summary>
/// <returns>An immutable map.</returns>
/// <remarks>
/// This method is an O(n) operation, and approaches O(1) time as the number of
/// actual mutations to the set since the last call to this method approaches 0.
/// </remarks>
public ImmutableDictionary<TKey, TValue> ToImmutable()
{
// Creating an instance of ImmutableSortedMap<T> with our root node automatically freezes our tree,
// ensuring that the returned instance is immutable. Any further mutations made to this builder
// will clone (and unfreeze) the spine of modified nodes until the next time this method is invoked.
return _immutable ??= ImmutableDictionary<TKey, TValue>.Wrap(_root, _comparers, _count);
}
#endregion
#region IDictionary<TKey, TValue> Members
/// <summary>
/// Adds an element with the provided key and value to the <see cref="IDictionary{TKey, TValue}"/>.
/// </summary>
/// <param name="key">The object to use as the key of the element to add.</param>
/// <param name="value">The object to use as the value of the element to add.</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is null.</exception>
/// <exception cref="ArgumentException">An element with the same key already exists in the <see cref="IDictionary{TKey, TValue}"/>.</exception>
/// <exception cref="NotSupportedException">The <see cref="IDictionary{TKey, TValue}"/> is read-only.</exception>
public void Add(TKey key, TValue value)
{
ImmutableDictionary<TKey, TValue>.MutationResult result = ImmutableDictionary<TKey, TValue>.Add(key, value, KeyCollisionBehavior.ThrowIfValueDifferent, this.Origin);
this.Apply(result);
}
/// <summary>
/// Determines whether the <see cref="IDictionary{TKey, TValue}"/> contains an element with the specified key.
/// </summary>
/// <param name="key">The key to locate in the <see cref="IDictionary{TKey, TValue}"/>.</param>
/// <returns>
/// true if the <see cref="IDictionary{TKey, TValue}"/> contains an element with the key; otherwise, false.
/// </returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is null.</exception>
public bool ContainsKey(TKey key)
{
return ImmutableDictionary<TKey, TValue>.ContainsKey(key, this.Origin);
}
/// <summary>
/// Determines whether the <see cref="ImmutableDictionary{TKey, TValue}"/>
/// contains an element with the specified value.
/// </summary>
/// <param name="value">
/// The value to locate in the <see cref="ImmutableDictionary{TKey, TValue}"/>.
/// The value can be null for reference types.
/// </param>
/// <returns>
/// true if the <see cref="ImmutableDictionary{TKey, TValue}"/> contains
/// an element with the specified value; otherwise, false.
/// </returns>
public bool ContainsValue(TValue value)
{
foreach (KeyValuePair<TKey, TValue> item in this)
{
if (this.ValueComparer.Equals(value, item.Value))
{
return true;
}
}
return false;
}
/// <summary>
/// Removes the element with the specified key from the <see cref="IDictionary{TKey, TValue}"/>.
/// </summary>
/// <param name="key">The key of the element to remove.</param>
/// <returns>
/// true if the element is successfully removed; otherwise, false. This method also returns false if <paramref name="key"/> was not found in the original <see cref="IDictionary{TKey, TValue}"/>.
/// </returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is null.</exception>
///
/// <exception cref="NotSupportedException">The <see cref="IDictionary{TKey, TValue}"/> is read-only.</exception>
public bool Remove(TKey key)
{
ImmutableDictionary<TKey, TValue>.MutationResult result = ImmutableDictionary<TKey, TValue>.Remove(key, this.Origin);
return this.Apply(result);
}
/// <summary>
/// Gets the value associated with the specified key.
/// </summary>
/// <param name="key">The key whose value to get.</param>
/// <param name="value">When this method returns, the value associated with the specified key, if the key is found; otherwise, the default value of the type <typeparamref name="TValue"/>. This parameter is passed uninitialized.</param>
/// <returns>
/// true if the object that implements <see cref="IDictionary{TKey, TValue}"/> contains an element with the specified key; otherwise, false.
/// </returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is null.</exception>
public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
{
return ImmutableDictionary<TKey, TValue>.TryGetValue(key, this.Origin, out value!);
}
/// <summary>
/// See the <see cref="IImmutableDictionary{TKey, TValue}"/> interface.
/// </summary>
public bool TryGetKey(TKey equalKey, out TKey actualKey)
{
return ImmutableDictionary<TKey, TValue>.TryGetKey(equalKey, this.Origin, out actualKey);
}
/// <summary>
/// Adds an item to the <see cref="ICollection{T}"/>.
/// </summary>
/// <param name="item">The object to add to the <see cref="ICollection{T}"/>.</param>
/// <exception cref="NotSupportedException">The <see cref="ICollection{T}"/> is read-only.</exception>
public void Add(KeyValuePair<TKey, TValue> item)
{
this.Add(item.Key, item.Value);
}
/// <summary>
/// Removes all items from the <see cref="ICollection{T}"/>.
/// </summary>
/// <exception cref="NotSupportedException">The <see cref="ICollection{T}"/> is read-only. </exception>
public void Clear()
{
this.Root = SortedInt32KeyNode<HashBucket>.EmptyNode;
_count = 0;
}
/// <summary>
/// Determines whether the <see cref="ICollection{T}"/> contains a specific value.
/// </summary>
/// <param name="item">The object to locate in the <see cref="ICollection{T}"/>.</param>
/// <returns>
/// true if <paramref name="item"/> is found in the <see cref="ICollection{T}"/>; otherwise, false.
/// </returns>
public bool Contains(KeyValuePair<TKey, TValue> item)
{
return ImmutableDictionary<TKey, TValue>.Contains(item, this.Origin);
}
/// <summary>
/// See the <see cref="ICollection{T}"/> interface.
/// </summary>
void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
Requires.NotNull(array, nameof(array));
foreach (KeyValuePair<TKey, TValue> item in this)
{
array[arrayIndex++] = item;
}
}
#endregion
#region ICollection<KeyValuePair<TKey, TValue>> Members
/// <summary>
/// Removes the first occurrence of a specific object from the <see cref="ICollection{T}"/>.
/// </summary>
/// <param name="item">The object to remove from the <see cref="ICollection{T}"/>.</param>
/// <returns>
/// true if <paramref name="item"/> was successfully removed from the <see cref="ICollection{T}"/>; otherwise, false. This method also returns false if <paramref name="item"/> is not found in the original <see cref="ICollection{T}"/>.
/// </returns>
/// <exception cref="NotSupportedException">The <see cref="ICollection{T}"/> is read-only.</exception>
public bool Remove(KeyValuePair<TKey, TValue> item)
{
// Before removing based on the key, check that the key (if it exists) has the value given in the parameter as well.
if (this.Contains(item))
{
return this.Remove(item.Key);
}
return false;
}
#endregion
#region IEnumerator<T> methods
/// <summary>
/// Returns an enumerator that iterates through the collection.
/// </summary>
/// <returns>
/// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection.
/// </returns>
IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
{
return this.GetEnumerator();
}
/// <summary>
/// Returns an enumerator that iterates through a collection.
/// </summary>
/// <returns>
/// An <see cref="IEnumerator"/> object that can be used to iterate through the collection.
/// </returns>
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
/// <summary>
/// Applies the result of some mutation operation to this instance.
/// </summary>
/// <param name="result">The result.</param>
private bool Apply(MutationResult result)
{
this.Root = result.Root;
_count += result.CountAdjustment;
return result.CountAdjustment != 0;
}
}
}
}
|