|
// 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="ImmutableSortedDictionary{TKey, TValue}.Builder"/> class.
/// </content>
public sealed partial class ImmutableSortedDictionary<TKey, TValue> where TKey : notnull
{
/// <summary>
/// A sorted dictionary that mutates with little or no memory allocations,
/// can produce and/or build on immutable sorted dictionary instances very efficiently.
/// </summary>
/// <remarks>
/// <para>
/// 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 binary tree used to store the contents of the map. Contents are typically not entirely frozen.
/// </summary>
private Node _root = Node.EmptyNode;
/// <summary>
/// The key comparer.
/// </summary>
private IComparer<TKey> _keyComparer = Comparer<TKey>.Default;
/// <summary>
/// The value comparer.
/// </summary>
private IEqualityComparer<TValue> _valueComparer = EqualityComparer<TValue>.Default;
/// <summary>
/// The number of entries in the map.
/// </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 ImmutableSortedDictionary<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="Builder"/> class.
/// </summary>
/// <param name="map">A map to act as the basis for a new map.</param>
internal Builder(ImmutableSortedDictionary<TKey, TValue> map)
{
Requires.NotNull(map, nameof(map));
_root = map._root;
_keyComparer = map.KeyComparer;
_valueComparer = map.ValueComparer;
_count = map.Count;
_immutable = map;
}
#region IDictionary<TKey, TValue> Properties and Indexer
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
ICollection<TKey> IDictionary<TKey, TValue>.Keys
{
get { return this.Root.Keys.ToArray(this.Count); }
}
/// <summary>
/// See <see cref="IReadOnlyDictionary{TKey, TValue}"/>
/// </summary>
public IEnumerable<TKey> Keys
{
get { return this.Root.Keys; }
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
ICollection<TValue> IDictionary<TKey, TValue>.Values
{
get { return this.Root.Values.ToArray(this.Count); }
}
/// <summary>
/// See <see cref="IReadOnlyDictionary{TKey, TValue}"/>
/// </summary>
public IEnumerable<TValue> Values
{
get { return this.Root.Values; }
}
/// <summary>
/// Gets the number of elements in this map.
/// </summary>
public int Count
{
get { return _count; }
}
/// <summary>
/// Gets a value indicating whether this instance is read-only.
/// </summary>
/// <value>Always <c>false</c>.</value>
bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
{
get { return false; }
}
#endregion
/// <summary>
/// Gets the current version of the contents of this builder.
/// </summary>
internal int Version
{
get { return _version; }
}
/// <summary>
/// Gets or sets the root node that represents the data in this collection.
/// </summary>
private Node 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;
}
}
}
#region IDictionary<TKey, TValue> Indexer
/// <summary>
/// Gets or sets the value for a given key.
/// </summary>
/// <param name="key">The key.</param>
/// <returns>The value associated with the given key.</returns>
public TValue this[TKey key]
{
get
{
TValue value;
if (!this.TryGetValue(key, out value!))
{
ThrowHelper.ThrowKeyNotFoundException(key);
}
return value;
}
set
{
bool replacedExistingValue, mutated;
this.Root = _root.SetItem(key, value, _keyComparer, _valueComparer, out replacedExistingValue, out mutated);
if (mutated && !replacedExistingValue)
{
_count++;
}
}
}
/// <summary>
/// Returns a read-only reference to the value associated with the provided key.
/// </summary>
/// <exception cref="KeyNotFoundException">If the key is not present.</exception>
public ref readonly TValue ValueRef(TKey key)
{
Requires.NotNullAllowStructs(key, nameof(key));
return ref _root.ValueRef(key, _keyComparer);
}
#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; }
}
/// <summary>
/// Gets or sets the key comparer.
/// </summary>
/// <value>
/// The key comparer.
/// </value>
public IComparer<TKey> KeyComparer
{
get
{
return _keyComparer;
}
set
{
Requires.NotNull(value, nameof(value));
if (value != _keyComparer)
{
ImmutableSortedDictionary<TKey, TValue>.Node newRoot = Node.EmptyNode;
int count = 0;
foreach (KeyValuePair<TKey, TValue> item in this)
{
bool mutated;
newRoot = newRoot.Add(item.Key, item.Value, value, _valueComparer, out mutated);
if (mutated)
{
count++;
}
}
_keyComparer = value;
this.Root = newRoot;
_count = count;
}
}
}
/// <summary>
/// Gets or sets the value comparer.
/// </summary>
/// <value>
/// The value comparer.
/// </value>
public IEqualityComparer<TValue> ValueComparer
{
get
{
return _valueComparer;
}
set
{
Requires.NotNull(value, nameof(value));
if (value != _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.
_valueComparer = value;
_immutable = null; // invalidate cached immutable
}
}
}
#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="index">The zero-based index in <paramref name="array"/> at which copying begins.</param>
void ICollection.CopyTo(Array array, int index)
{
this.Root.CopyTo(array, index, this.Count);
}
#endregion
#region IDictionary<TKey, TValue> Methods
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public void Add(TKey key, TValue value)
{
bool mutated;
this.Root = this.Root.Add(key, value, _keyComparer, _valueComparer, out mutated);
if (mutated)
{
_count++;
}
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public bool ContainsKey(TKey key)
{
return this.Root.ContainsKey(key, _keyComparer);
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public bool Remove(TKey key)
{
bool mutated;
this.Root = this.Root.Remove(key, _keyComparer, out mutated);
if (mutated)
{
_count--;
}
return mutated;
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
{
return this.Root.TryGetValue(key, _keyComparer, out value!);
}
/// <summary>
/// See the <see cref="IImmutableDictionary{TKey, TValue}"/> interface.
/// </summary>
public bool TryGetKey(TKey equalKey, out TKey actualKey)
{
Requires.NotNullAllowStructs(equalKey, nameof(equalKey));
return this.Root.TryGetKey(equalKey, _keyComparer, out actualKey);
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public void Add(KeyValuePair<TKey, TValue> item)
{
this.Add(item.Key, item.Value);
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public void Clear()
{
this.Root = ImmutableSortedDictionary<TKey, TValue>.Node.EmptyNode;
_count = 0;
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public bool Contains(KeyValuePair<TKey, TValue> item)
{
return this.Root.Contains(item, _keyComparer, _valueComparer);
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
this.Root.CopyTo(array, arrayIndex, this.Count);
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public bool Remove(KeyValuePair<TKey, TValue> item)
{
if (this.Contains(item))
{
return this.Remove(item.Key);
}
return false;
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
public ImmutableSortedDictionary<TKey, TValue>.Enumerator GetEnumerator()
{
return this.Root.GetEnumerator(this);
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
{
return this.GetEnumerator();
}
/// <summary>
/// See <see cref="IDictionary{TKey, TValue}"/>
/// </summary>
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
#region Public methods
/// <summary>
/// Determines whether the <see cref="ImmutableSortedDictionary{TKey, TValue}"/>
/// contains an element with the specified value.
/// </summary>
/// <param name="value">
/// The value to locate in the <see cref="ImmutableSortedDictionary{TKey, TValue}"/>.
/// The value can be null for reference types.
/// </param>
/// <returns>
/// true if the <see cref="ImmutableSortedDictionary{TKey, TValue}"/> contains
/// an element with the specified value; otherwise, false.
/// </returns>
public bool ContainsValue(TValue value)
{
return _root.ContainsValue(value, _valueComparer);
}
/// <summary>
/// Removes any entries from the dictionaries with keys that match those found in the specified sequence.
/// </summary>
/// <param name="items">The keys for entries to remove from the dictionary.</param>
public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> items)
{
Requires.NotNull(items, nameof(items));
foreach (KeyValuePair<TKey, TValue> pair in items)
{
this.Add(pair);
}
}
/// <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>
/// 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 for 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 sorted 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 ImmutableSortedDictionary<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 ??= Wrap(this.Root, _count, _keyComparer, _valueComparer);
}
#endregion
}
}
}
|