System.Collections.Immutable by Microsoft

<PackageReference Include="System.Collections.Immutable" Version="5.0.0-preview.1.20120.5" />

.NET API 189,816 bytes

 SortedInt32KeyNode<TValue>

sealed class SortedInt32KeyNode<TValue> : IBinaryTree
using System.Collections.Generic; using System.ComponentModel; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Runtime.CompilerServices; namespace System.Collections.Immutable { [System.Runtime.CompilerServices.NullableContext(1)] [System.Runtime.CompilerServices.Nullable(0)] [DebuggerDisplay("{_key} = {_value}")] internal sealed class SortedInt32KeyNode<[System.Runtime.CompilerServices.Nullable(2)] TValue> : IBinaryTree { [System.Runtime.CompilerServices.NullableContext(0)] [EditorBrowsable(EditorBrowsableState.Advanced)] public struct Enumerator : IEnumerator<KeyValuePair<int, TValue>>, IEnumerator, IDisposable, ISecurePooledObjectUser { private static readonly SecureObjectPool<Stack<RefAsValueType<SortedInt32KeyNode<TValue>>>, Enumerator> s_enumeratingStacks = new SecureObjectPool<Stack<RefAsValueType<SortedInt32KeyNode<TValue>>>, Enumerator>(); private readonly int _poolUserId; private SortedInt32KeyNode<TValue> _root; private SecurePooledObject<Stack<RefAsValueType<SortedInt32KeyNode<TValue>>>> _stack; private SortedInt32KeyNode<TValue> _current; [System.Runtime.CompilerServices.Nullable(new byte[] { 0, 1 })] public KeyValuePair<int, TValue> Current { [return: System.Runtime.CompilerServices.Nullable(new byte[] { 0, 1 })] get { ThrowIfDisposed(); if (_current != null) return _current.Value; throw new InvalidOperationException(); } } int ISecurePooledObjectUser.PoolUserId { get { return _poolUserId; } } [System.Runtime.CompilerServices.Nullable(1)] object IEnumerator.Current { get { return Current; } } [System.Runtime.CompilerServices.NullableContext(1)] internal Enumerator(SortedInt32KeyNode<TValue> root) { Requires.NotNull<SortedInt32KeyNode<TValue>>(root, "root"); _root = root; _current = null; _poolUserId = SecureObjectPool.NewId(); _stack = null; if (!_root.IsEmpty) { if (!s_enumeratingStacks.TryTake(this, out _stack)) _stack = s_enumeratingStacks.PrepNew(this, new Stack<RefAsValueType<SortedInt32KeyNode<TValue>>>(root.Height)); PushLeft(_root); } } public void Dispose() { _root = null; _current = null; if (_stack != null && _stack.TryUse(ref this, out Stack<RefAsValueType<SortedInt32KeyNode<TValue>>> value)) { ImmutableExtensions.ClearFastWhenEmpty<RefAsValueType<SortedInt32KeyNode<TValue>>>(value); s_enumeratingStacks.TryAdd(this, _stack); } _stack = null; } public bool MoveNext() { ThrowIfDisposed(); if (_stack != null) { Stack<RefAsValueType<SortedInt32KeyNode<TValue>>> stack = _stack.Use(ref this); if (stack.Count > 0) { PushLeft((_current = stack.Pop().Value).Right); return true; } } _current = null; return false; } public void Reset() { ThrowIfDisposed(); _current = null; if (_stack != null) { Stack<RefAsValueType<SortedInt32KeyNode<TValue>>> stack = _stack.Use(ref this); ImmutableExtensions.ClearFastWhenEmpty<RefAsValueType<SortedInt32KeyNode<TValue>>>(stack); PushLeft(_root); } } internal void ThrowIfDisposed() { if (_root == null || (_stack != null && !_stack.IsOwned(ref this))) Requires.FailObjectDisposed<Enumerator>(this); } private void PushLeft(SortedInt32KeyNode<TValue> node) { Requires.NotNull<SortedInt32KeyNode<TValue>>(node, "node"); Stack<RefAsValueType<SortedInt32KeyNode<TValue>>> stack = _stack.Use(ref this); while (!node.IsEmpty) { stack.Push(new RefAsValueType<SortedInt32KeyNode<TValue>>(node)); node = node.Left; } } } internal static readonly SortedInt32KeyNode<TValue> EmptyNode = new SortedInt32KeyNode<TValue>(); private readonly int _key; [System.Diagnostics.CodeAnalysis.MaybeNull] private readonly TValue _value; private bool _frozen; private byte _height; private SortedInt32KeyNode<TValue> _left; private SortedInt32KeyNode<TValue> _right; public bool IsEmpty => _left == null; public int Height => _height; [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1 })] public SortedInt32KeyNode<TValue> Left { [return: System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1 })] get { return _left; } } [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1 })] public SortedInt32KeyNode<TValue> Right { [return: System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1 })] get { return _right; } } [System.Runtime.CompilerServices.Nullable(2)] IBinaryTree IBinaryTree.Left { get { return _left; } } [System.Runtime.CompilerServices.Nullable(2)] IBinaryTree IBinaryTree.Right { get { return _right; } } int IBinaryTree.Count { get { throw new NotSupportedException(); } } [System.Runtime.CompilerServices.Nullable(new byte[] { 0, 1 })] public KeyValuePair<int, TValue> Value { [return: System.Runtime.CompilerServices.Nullable(new byte[] { 0, 1 })] get { return new KeyValuePair<int, TValue>(_key, _value); } } internal IEnumerable<TValue> Values { get { Enumerator enumerator = this.GetEnumerator(); try { while (enumerator.MoveNext()) { yield return enumerator.Current.Value; } } finally { ((IDisposable)enumerator).Dispose(); } enumerator = default(Enumerator); } } private SortedInt32KeyNode() { _frozen = true; } private SortedInt32KeyNode(int key, TValue value, SortedInt32KeyNode<TValue> left, SortedInt32KeyNode<TValue> right, bool frozen = false) { Requires.NotNull<SortedInt32KeyNode<TValue>>(left, "left"); Requires.NotNull<SortedInt32KeyNode<TValue>>(right, "right"); _key = key; _value = value; _left = left; _right = right; _frozen = frozen; checked { _height = (byte)(1 + unchecked((int)Math.Max(left._height, right._height))); } } [System.Runtime.CompilerServices.NullableContext(0)] public Enumerator GetEnumerator() { return new Enumerator(this); } internal SortedInt32KeyNode<TValue> SetItem(int key, TValue value, IEqualityComparer<TValue> valueComparer, out bool replacedExistingValue, out bool mutated) { Requires.NotNull<IEqualityComparer<TValue>>(valueComparer, "valueComparer"); return SetOrAdd(key, value, valueComparer, true, out replacedExistingValue, out mutated); } internal SortedInt32KeyNode<TValue> Remove(int key, out bool mutated) { return RemoveRecursive(key, out mutated); } [return: System.Diagnostics.CodeAnalysis.MaybeNull] internal TValue GetValueOrDefault(int key) { SortedInt32KeyNode<TValue> sortedInt32KeyNode = this; while (true) { if (sortedInt32KeyNode.IsEmpty) return default(TValue); if (key == sortedInt32KeyNode._key) break; sortedInt32KeyNode = ((key <= sortedInt32KeyNode._key) ? sortedInt32KeyNode._left : sortedInt32KeyNode._right); } return sortedInt32KeyNode._value; } internal bool TryGetValue(int key, [System.Diagnostics.CodeAnalysis.MaybeNullWhen(false)] out TValue value) { SortedInt32KeyNode<TValue> sortedInt32KeyNode = this; while (true) { if (sortedInt32KeyNode.IsEmpty) { value = default(TValue); return false; } if (key == sortedInt32KeyNode._key) break; sortedInt32KeyNode = ((key <= sortedInt32KeyNode._key) ? sortedInt32KeyNode._left : sortedInt32KeyNode._right); } value = sortedInt32KeyNode._value; return true; } internal void Freeze([System.Runtime.CompilerServices.Nullable(new byte[] { 2, 0, 1 })] Action<KeyValuePair<int, TValue>> freezeAction = null) { if (!_frozen) { freezeAction?.Invoke(new KeyValuePair<int, TValue>(_key, _value)); _left.Freeze(freezeAction); _right.Freeze(freezeAction); _frozen = true; } } private static SortedInt32KeyNode<TValue> RotateLeft(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); if (tree._right.IsEmpty) return tree; SortedInt32KeyNode<TValue> right = tree._right; return right.Mutate(tree.Mutate(null, right._left), null); } private static SortedInt32KeyNode<TValue> RotateRight(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); if (tree._left.IsEmpty) return tree; SortedInt32KeyNode<TValue> left = tree._left; return left.Mutate(null, tree.Mutate(left._right, null)); } private static SortedInt32KeyNode<TValue> DoubleLeft(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); if (tree._right.IsEmpty) return tree; SortedInt32KeyNode<TValue> tree2 = tree.Mutate(null, RotateRight(tree._right)); return RotateLeft(tree2); } private static SortedInt32KeyNode<TValue> DoubleRight(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); if (tree._left.IsEmpty) return tree; SortedInt32KeyNode<TValue> tree2 = tree.Mutate(RotateLeft(tree._left), null); return RotateRight(tree2); } private static int Balance(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); return tree._right._height - tree._left._height; } private static bool IsRightHeavy(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); return Balance(tree) >= 2; } private static bool IsLeftHeavy(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); return Balance(tree) <= -2; } private static SortedInt32KeyNode<TValue> MakeBalanced(SortedInt32KeyNode<TValue> tree) { Requires.NotNull<SortedInt32KeyNode<TValue>>(tree, "tree"); if (IsRightHeavy(tree)) { if (Balance(tree._right) >= 0) return RotateLeft(tree); return DoubleLeft(tree); } if (IsLeftHeavy(tree)) { if (Balance(tree._left) <= 0) return RotateRight(tree); return DoubleRight(tree); } return tree; } private SortedInt32KeyNode<TValue> SetOrAdd(int key, TValue value, IEqualityComparer<TValue> valueComparer, bool overwriteExistingValue, out bool replacedExistingValue, out bool mutated) { replacedExistingValue = false; if (IsEmpty) { mutated = true; return new SortedInt32KeyNode<TValue>(key, value, this, this, false); } SortedInt32KeyNode<TValue> sortedInt32KeyNode = this; if (key > _key) { SortedInt32KeyNode<TValue> right = _right.SetOrAdd(key, value, valueComparer, overwriteExistingValue, out replacedExistingValue, out mutated); if (mutated) sortedInt32KeyNode = Mutate(null, right); } else if (key < _key) { SortedInt32KeyNode<TValue> left = _left.SetOrAdd(key, value, valueComparer, overwriteExistingValue, out replacedExistingValue, out mutated); if (mutated) sortedInt32KeyNode = Mutate(left, null); } else { if (valueComparer.Equals(_value, value)) { mutated = false; return this; } if (!overwriteExistingValue) throw new ArgumentException(System.SR.Format(System.SR.DuplicateKey, key)); mutated = true; replacedExistingValue = true; sortedInt32KeyNode = new SortedInt32KeyNode<TValue>(key, value, _left, _right, false); } if (!mutated) return sortedInt32KeyNode; return MakeBalanced(sortedInt32KeyNode); } private SortedInt32KeyNode<TValue> RemoveRecursive(int key, out bool mutated) { if (IsEmpty) { mutated = false; return this; } SortedInt32KeyNode<TValue> sortedInt32KeyNode = this; if (key == _key) { mutated = true; if (_right.IsEmpty && _left.IsEmpty) sortedInt32KeyNode = EmptyNode; else if (_right.IsEmpty && !_left.IsEmpty) { sortedInt32KeyNode = _left; } else if (!_right.IsEmpty && _left.IsEmpty) { sortedInt32KeyNode = _right; } else { SortedInt32KeyNode<TValue> sortedInt32KeyNode2 = _right; while (!sortedInt32KeyNode2._left.IsEmpty) { sortedInt32KeyNode2 = sortedInt32KeyNode2._left; } bool mutated2; SortedInt32KeyNode<TValue> right = _right.Remove(sortedInt32KeyNode2._key, out mutated2); sortedInt32KeyNode = sortedInt32KeyNode2.Mutate(_left, right); } } else if (key < _key) { SortedInt32KeyNode<TValue> left = _left.Remove(key, out mutated); if (mutated) sortedInt32KeyNode = Mutate(left, null); } else { SortedInt32KeyNode<TValue> right2 = _right.Remove(key, out mutated); if (mutated) sortedInt32KeyNode = Mutate(null, right2); } if (!sortedInt32KeyNode.IsEmpty) return MakeBalanced(sortedInt32KeyNode); return sortedInt32KeyNode; } private SortedInt32KeyNode<TValue> Mutate(SortedInt32KeyNode<TValue> left = null, SortedInt32KeyNode<TValue> right = null) { if (_frozen) return new SortedInt32KeyNode<TValue>(_key, _value, left ?? _left, right ?? _right, false); if (left != null) _left = left; if (right != null) _right = right; checked { _height = (byte)(1 + unchecked((int)Math.Max(_left._height, _right._height))); return this; } } } }