ImmutableSortedSet_1.Builder.cs

// 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="ImmutableSortedSet{T}.Builder"/> class.
    /// </content>
    public sealed partial class ImmutableSortedSet<T>
    {
        /// <summary>
        /// A sorted set that mutates with little or no memory allocations,
        /// can produce and/or build on immutable sorted set instances very efficiently.
        /// </summary>
        /// <remarks>
        /// <para>
        /// While <see cref="M:ImmutableSortedSet{T}.Union"/> 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(ImmutableSortedSetBuilderDebuggerProxy<>))]
        public sealed class Builder : ISortKeyCollection<T>, IReadOnlyCollection<T>, ISet<T>, ICollection
        {
            /// <summary>
            /// The root of the binary tree that stores the collection.  Contents are typically not entirely frozen.
            /// </summary>
            private ImmutableSortedSet<T>.Node _root = ImmutableSortedSet<T>.Node.EmptyNode;

            /// <summary>
            /// The comparer to use for sorting the set.
            /// </summary>
            private IComparer<T> _comparer = Comparer<T>.Default;

            /// <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 ImmutableSortedSet<T>? _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="set">A set to act as the basis for a new set.</param>
            internal Builder(ImmutableSortedSet<T> set)
            {
                Requires.NotNull(set, nameof(set));
                _root = set._root;
                _comparer = set.KeyComparer;
                _immutable = set;
            }

            #region ISet<T> Properties

            /// <summary>
            /// Gets the number of elements in this set.
            /// </summary>
            public int Count
            {
                get { return this.Root.Count; }
            }

            /// <summary>
            /// Gets a value indicating whether this instance is read-only.
            /// </summary>
            /// <value>Always <c>false</c>.</value>
            bool ICollection<T>.IsReadOnly
            {
                get { return false; }
            }

            #endregion

            /// <summary>
            /// Gets the element of the set at the given index.
            /// </summary>
            /// <param name="index">The 0-based index of the element in the set to return.</param>
            /// <returns>The element at the given position.</returns>
            /// <remarks>
            /// No index setter is offered because the element being replaced may not sort
            /// to the same position in the sorted collection as the replacing element.
            /// </remarks>
            public T this[int index]
            {
                get { return _root.ItemRef(index); }
            }

            /// <summary>
            /// Gets a read-only reference to the element of the set at the given index.
            /// </summary>
            /// <param name="index">The 0-based index of the element in the set to return.</param>
            /// <returns>A read-only reference to the element at the given position.</returns>
            public ref readonly T ItemRef(int index)
            {
                return ref _root.ItemRef(index);
            }

            /// <summary>
            /// Gets the maximum value in the collection, as defined by the comparer.
            /// </summary>
            /// <value>The maximum value in the set.</value>
            public T? Max
            {
                get { return _root.Max; }
            }

            /// <summary>
            /// Gets the minimum value in the collection, as defined by the comparer.
            /// </summary>
            /// <value>The minimum value in the set.</value>
            public T? Min
            {
                get { return _root.Min; }
            }

            /// <summary>
            ///  Gets or sets the <see cref="IComparer{T}"/> object that is used to determine equality for the values in the <see cref="ImmutableSortedSet{T}"/>.
            /// </summary>
            /// <value>The comparer that is used to determine equality for the values in the set.</value>
            /// <remarks>
            /// When changing the comparer in such a way as would introduce collisions, the conflicting elements are dropped,
            /// leaving only one of each matching pair in the collection.
            /// </remarks>
            public IComparer<T> KeyComparer
            {
                get
                {
                    return _comparer;
                }

                set
                {
                    Requires.NotNull(value, nameof(value));

                    if (value != _comparer)
                    {
                        ImmutableSortedSet<T>.Node newRoot = Node.EmptyNode;
                        foreach (T item in this)
                        {
                            bool mutated;
                            newRoot = newRoot.Add(item, value, out mutated);
                        }

                        _immutable = null;
                        _comparer = value;
                        this.Root = newRoot;
                    }
                }
            }

            /// <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 ISet<T> Methods

            /// <summary>
            /// Adds an element to the current set and returns a value to indicate if the
            /// element was successfully added.
            /// </summary>
            /// <param name="item">The element to add to the set.</param>
            /// <returns>true if the element is added to the set; false if the element is already in the set.</returns>
            public bool Add(T item)
            {
                bool mutated;
                this.Root = this.Root.Add(item, _comparer, out mutated);
                return mutated;
            }

            /// <summary>
            /// Removes all elements in the specified collection from the current set.
            /// </summary>
            /// <param name="other">The collection of items to remove from the set.</param>
            public void ExceptWith(IEnumerable<T> other)
            {
                Requires.NotNull(other, nameof(other));

                foreach (T item in other)
                {
                    this.Root = this.Root.Remove(item, _comparer, out _);
                }
            }

            /// <summary>
            /// Modifies the current set so that it contains only elements that are also in a specified collection.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            public void IntersectWith(IEnumerable<T> other)
            {
                Requires.NotNull(other, nameof(other));

                ImmutableSortedSet<T>.Node result = ImmutableSortedSet<T>.Node.EmptyNode;
                foreach (T item in other)
                {
                    if (this.Contains(item))
                    {
                        bool mutated;
                        result = result.Add(item, _comparer, out mutated);
                    }
                }

                this.Root = result;
            }

            /// <summary>
            /// Determines whether the current set is a proper (strict) subset of a specified collection.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            /// <returns>true if the current set is a correct subset of other; otherwise, false.</returns>
            public bool IsProperSubsetOf(IEnumerable<T> other)
            {
                return this.ToImmutable().IsProperSubsetOf(other);
            }

            /// <summary>
            /// Determines whether the current set is a proper (strict) superset of a specified collection.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            /// <returns>true if the current set is a superset of other; otherwise, false.</returns>
            public bool IsProperSupersetOf(IEnumerable<T> other)
            {
                return this.ToImmutable().IsProperSupersetOf(other);
            }

            /// <summary>
            /// Determines whether the current set is a subset of a specified collection.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            /// <returns>true if the current set is a subset of other; otherwise, false.</returns>
            public bool IsSubsetOf(IEnumerable<T> other)
            {
                return this.ToImmutable().IsSubsetOf(other);
            }

            /// <summary>
            /// Determines whether the current set is a superset of a specified collection.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            /// <returns>true if the current set is a superset of other; otherwise, false.</returns>
            public bool IsSupersetOf(IEnumerable<T> other)
            {
                return this.ToImmutable().IsSupersetOf(other);
            }

            /// <summary>
            /// Determines whether the current set overlaps with the specified collection.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            /// <returns>true if the current set and other share at least one common element; otherwise, false.</returns>
            public bool Overlaps(IEnumerable<T> other)
            {
                return this.ToImmutable().Overlaps(other);
            }

            /// <summary>
            /// Determines whether the current set and the specified collection contain the same elements.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            /// <returns>true if the current set is equal to other; otherwise, false.</returns>
            public bool SetEquals(IEnumerable<T> other)
            {
                return this.ToImmutable().SetEquals(other);
            }

            /// <summary>
            /// Modifies the current set so that it contains only elements that are present either in the current set or in the specified collection, but not both.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            public void SymmetricExceptWith(IEnumerable<T> other)
            {
                this.Root = this.ToImmutable().SymmetricExcept(other)._root;
            }

            /// <summary>
            /// Modifies the current set so that it contains all elements that are present in both the current set and in the specified collection.
            /// </summary>
            /// <param name="other">The collection to compare to the current set.</param>
            public void UnionWith(IEnumerable<T> other)
            {
                Requires.NotNull(other, nameof(other));

                foreach (T item in other)
                {
                    this.Root = this.Root.Add(item, _comparer, out _);
                }
            }

            /// <summary>
            /// Adds an element to the current set and returns a value to indicate if the
            /// element was successfully added.
            /// </summary>
            /// <param name="item">The element to add to the set.</param>
            void ICollection<T>.Add(T item)
            {
                this.Add(item);
            }

            /// <summary>
            /// Removes all elements from this set.
            /// </summary>
            public void Clear()
            {
                this.Root = ImmutableSortedSet<T>.Node.EmptyNode;
            }

            /// <summary>
            /// Determines whether the set contains a specific value.
            /// </summary>
            /// <param name="item">The object to locate in the set.</param>
            /// <returns>true if item is found in the set; false otherwise.</returns>
            public bool Contains(T item)
            {
                return this.Root.Contains(item, _comparer);
            }

            /// <summary>
            /// See <see cref="ICollection{T}"/>
            /// </summary>
            void ICollection<T>.CopyTo(T[] array, int arrayIndex)
            {
                _root.CopyTo(array, arrayIndex);
            }

            /// <summary>
            ///  Removes the first occurrence of a specific object from the set.
            /// </summary>
            /// <param name="item">The object to remove from the set.</param>
            /// <returns><c>true</c> if the item was removed from the set; <c>false</c> if the item was not found in the set.</returns>
            public bool Remove(T item)
            {
                bool mutated;
                this.Root = this.Root.Remove(item, _comparer, out mutated);
                return mutated;
            }

            /// <summary>
            /// Returns an enumerator that iterates through the collection.
            /// </summary>
            /// <returns>A enumerator that can be used to iterate through the collection.</returns>
            public ImmutableSortedSet<T>.Enumerator GetEnumerator()
            {
                return this.Root.GetEnumerator(this);
            }

            /// <summary>
            /// Returns an enumerator that iterates through the collection.
            /// </summary>
            /// <returns>A enumerator that can be used to iterate through the collection.</returns>
            IEnumerator<T> IEnumerable<T>.GetEnumerator()
            {
                return this.Root.GetEnumerator();
            }

            /// <summary>
            /// Returns an enumerator that iterates through the collection.
            /// </summary>
            /// <returns>A enumerator that can be used to iterate through the collection.</returns>
            IEnumerator IEnumerable.GetEnumerator()
            {
                return this.GetEnumerator();
            }

            #endregion

            /// <summary>
            /// Searches for the first index within this set that the specified value is contained.
            /// </summary>
            /// <param name="item">The value to locate within the set.</param>
            /// <returns>
            /// The index of the specified <paramref name="item"/> in the sorted set,
            /// if <paramref name="item"/> is found.  If <paramref name="item"/> is not
            /// found and <paramref name="item"/> is less than one or more elements in this set,
            /// a negative number which is the bitwise complement of the index of the first
            /// element that is larger than value. If <paramref name="item"/> is not found
            /// and <paramref name="item"/> is greater than any of the elements in the set,
            /// a negative number which is the bitwise complement of (the index of the last
            /// element plus 1).
            /// </returns>
            public int IndexOf(T item)
            {
                return this.Root.IndexOf(item, _comparer);
            }

            /// <summary>
            /// Returns an <see cref="IEnumerable{T}"/> that iterates over this
            /// collection in reverse order.
            /// </summary>
            /// <returns>
            /// An enumerator that iterates over the <see cref="ImmutableSortedSet{T}.Builder"/>
            /// in reverse order.
            /// </returns>
            public IEnumerable<T> Reverse()
            {
                return new ReverseEnumerable(_root);
            }

            /// <summary>
            /// Creates an immutable sorted set based on the contents of this instance.
            /// </summary>
            /// <returns>An immutable set.</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 ImmutableSortedSet<T> ToImmutable()
            {
                // Creating an instance of ImmutableSortedSet<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 ??= ImmutableSortedSet<T>.Wrap(this.Root, _comparer);
            }

            /// <summary>
            /// Searches the set for a given value and returns the equal value it finds, if any.
            /// </summary>
            /// <param name="equalValue">The value for which to search.</param>
            /// <param name="actualValue">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>
            public bool TryGetValue(T equalValue, out T actualValue)
            {
                Node searchResult = _root.Search(equalValue, _comparer);
                if (!searchResult.IsEmpty)
                {
                    actualValue = searchResult.Key;
                    return true;
                }

                actualValue = equalValue;
                return false;
            }

            #region ICollection members

            /// <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)
            {
                this.Root.CopyTo(array, arrayIndex);
            }

            /// <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 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;
                }
            }
            #endregion
        }
    }
}