ImmutableList_1.Node.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;
using System.Runtime.CompilerServices;

namespace System.Collections.Immutable
{
    public sealed partial class ImmutableList<T>
    {
        /// <summary>
        /// A node in the AVL tree storing this set.
        /// </summary>
        [DebuggerDisplay("{_key}")]
        internal sealed class Node : IBinaryTree<T>, IEnumerable<T>
        {
            /// <summary>
            /// The default empty node.
            /// </summary>
            internal static readonly Node EmptyNode = new Node();

            /// <summary>
            /// The key associated with this node.
            /// </summary>
            private T _key = default!; // Defaulting for EmptyNode, shouldn't be null for non empty nodes so didn't annotated with [MaybeNull]

            /// <summary>
            /// A value indicating whether this node has been frozen (made immutable).
            /// </summary>
            /// <remarks>
            /// Nodes must be frozen before ever being observed by a wrapping collection type
            /// to protect collections from further mutations.
            /// </remarks>
            private bool _frozen;

            /// <summary>
            /// The depth of the tree beneath this node.
            /// </summary>
            private byte _height; // AVL tree max height <= ~1.44 * log2(maxNodes + 2)

            /// <summary>
            /// The number of elements contained by this subtree starting at this node.
            /// </summary>
            /// <remarks>
            /// If this node would benefit from saving 4 bytes, we could have only a few nodes
            /// scattered throughout the graph actually record the count of nodes beneath them.
            /// Those without the count could query their descendants, which would often short-circuit
            /// when they hit a node that *does* include a count field.
            /// </remarks>
            private int _count;

            /// <summary>
            /// The left tree.
            /// </summary>
            private Node? _left;

            /// <summary>
            /// The right tree.
            /// </summary>
            private Node? _right;

            /// <summary>
            /// Initializes a new instance of the <see cref="ImmutableList{T}.Node"/> class
            /// that is pre-frozen.
            /// </summary>
            private Node()
            {
                _frozen = true; // the empty node is *always* frozen.
                Debug.Assert(this.IsEmpty);
            }

            /// <summary>
            /// Initializes a new instance of the <see cref="ImmutableList{T}.Node"/> class
            /// that is not yet frozen.
            /// </summary>
            /// <param name="key">The value stored by this node.</param>
            /// <param name="left">The left branch.</param>
            /// <param name="right">The right branch.</param>
            /// <param name="frozen">Whether this node is prefrozen.</param>
            private Node(T key, Node left, Node right, bool frozen = false)
            {
                Requires.NotNull(left, nameof(left));
                Requires.NotNull(right, nameof(right));
                Debug.Assert(!frozen || (left._frozen && right._frozen));

                _key = key;
                _left = left;
                _right = right;
                _height = ParentHeight(left, right);
                _count = ParentCount(left, right);
                _frozen = frozen;

                Debug.Assert(!this.IsEmpty);
            }

            /// <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>
            public bool IsEmpty
            {
                get
                {
                    Debug.Assert(!(_left == null ^ _right == null));
                    return _left == null;
                }
            }

            /// <summary>
            /// Gets the height of the tree beneath this node.
            /// </summary>
            public int Height => _height;

            /// <summary>
            /// Gets the left branch of this node.
            /// </summary>
            public Node? Left => _left;

            /// <summary>
            /// Gets the left branch of this node.
            /// </summary>
            IBinaryTree? IBinaryTree.Left => _left;

            /// <summary>
            /// Gets the right branch of this node.
            /// </summary>
            public Node? Right => _right;

            /// <summary>
            /// Gets the right branch of this node.
            /// </summary>
            IBinaryTree? IBinaryTree.Right => _right;

            /// <summary>
            /// Gets the left branch of this node.
            /// </summary>
            IBinaryTree<T>? IBinaryTree<T>.Left => _left;

            /// <summary>
            /// Gets the right branch of this node.
            /// </summary>
            IBinaryTree<T>? IBinaryTree<T>.Right => _right;

            /// <summary>
            /// Gets the value represented by the current node.
            /// </summary>
            public T Value => _key;

            /// <summary>
            /// Gets the number of elements contained by this subtree starting at this node.
            /// </summary>
            public int Count => _count;

            /// <summary>
            /// Gets the key.
            /// </summary>
            internal T Key => _key;

            /// <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>
            internal T this[int index]
            {
                get
                {
                    Requires.Range(index >= 0 && index < this.Count, nameof(index));
                    Debug.Assert(_left != null && _right != null);

                    if (index < _left._count)
                    {
                        return _left[index];
                    }

                    if (index > _left._count)
                    {
                        return _right[index - _left._count - 1];
                    }

                    return _key;
                }
            }

            /// <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>
            internal ref readonly T ItemRef(int index)
            {
                Requires.Range(index >= 0 && index < this.Count, nameof(index));

                return ref ItemRefUnchecked(index);
            }

            private ref readonly T ItemRefUnchecked(int index)
            {
                Debug.Assert(_left != null && _right != null);
                if (index < _left._count)
                {
                    return ref _left.ItemRefUnchecked(index);
                }

                if (index > _left._count)
                {
                    return ref _right.ItemRefUnchecked(index - _left._count - 1);
                }

                return ref _key;
            }

            #region IEnumerable<T> Members

            /// <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() => new Enumerator(this);

            /// <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>
            [ExcludeFromCodeCoverage] // internal, never called, but here for interface implementation
            IEnumerator<T> IEnumerable<T>.GetEnumerator() => this.GetEnumerator();

            /// <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>
            [ExcludeFromCodeCoverage] // internal, never called, but here for interface implementation
            IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator();

            #endregion

            /// <summary>
            /// Returns an enumerator that iterates through the collection.
            /// </summary>
            /// <param name="builder">The builder, if applicable.</param>
            /// <returns>
            /// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection.
            /// </returns>
            internal Enumerator GetEnumerator(Builder builder) => new Enumerator(this, builder);

            /// <summary>
            /// Creates a node tree that contains the contents of a list.
            /// </summary>
            /// <param name="items">An indexable list with the contents that the new node tree should contain.</param>
            /// <param name="start">The starting index within <paramref name="items"/> that should be captured by the node tree.</param>
            /// <param name="length">The number of elements from <paramref name="items"/> that should be captured by the node tree.</param>
            /// <returns>The root of the created node tree.</returns>
            internal static Node NodeTreeFromList(IOrderedCollection<T> items, int start, int length)
            {
                Requires.NotNull(items, nameof(items));
                Requires.Range(start >= 0, nameof(start));
                Requires.Range(length >= 0, nameof(length));

                if (length == 0)
                {
                    return EmptyNode;
                }

                int rightCount = (length - 1) / 2;
                int leftCount = (length - 1) - rightCount;
                Node left = NodeTreeFromList(items, start, leftCount);
                Node right = NodeTreeFromList(items, start + leftCount + 1, rightCount);
                return new Node(items[start + leftCount], left, right, true);
            }

            /// <summary>
            /// Creates a node tree that contains the contents of a span.
            /// </summary>
            /// <param name="items">A span with the contents that the new node tree should contain.</param>
            /// <returns>The root of the created node tree.</returns>
            internal static Node NodeTreeFromList(ReadOnlySpan<T> items)
            {
                if (items.IsEmpty)
                {
                    return EmptyNode;
                }

                int rightCount = (items.Length - 1) / 2;
                int leftCount = (items.Length - 1) - rightCount;
                Node left = NodeTreeFromList(items.Slice(0, leftCount));
                Node right = NodeTreeFromList(items.Slice(leftCount + 1));
                return new Node(items[leftCount], left, right, frozen: true);
            }

            /// <summary>
            /// Adds the specified key to the tree.
            /// </summary>
            /// <param name="key">The key.</param>
            /// <returns>The new tree.</returns>
            internal Node Add(T key)
            {
                if (this.IsEmpty)
                {
                    return CreateLeaf(key);
                }

                Node newRight = _right!.Add(key);
                Node result = this.MutateRight(newRight);
                return result.IsBalanced ? result : result.BalanceRight();
            }

            /// <summary>
            /// Adds a value at a given index to this node.
            /// </summary>
            /// <param name="index">The location for the new value.</param>
            /// <param name="key">The value to add.</param>
            /// <returns>The new tree.</returns>
            internal Node Insert(int index, T key)
            {
                Requires.Range(index >= 0 && index <= this.Count, nameof(index));

                if (this.IsEmpty)
                {
                    return CreateLeaf(key);
                }

                if (index <= _left!._count)
                {
                    Node newLeft = _left.Insert(index, key);
                    Node result = this.MutateLeft(newLeft);
                    return result.IsBalanced ? result : result.BalanceLeft();
                }
                else
                {
                    Node newRight = _right!.Insert(index - _left._count - 1, key);
                    Node result = this.MutateRight(newRight);
                    return result.IsBalanced ? result : result.BalanceRight();
                }
            }

            /// <summary>
            /// Adds the specified keys to this tree.
            /// </summary>
            /// <param name="keys">The keys.</param>
            /// <returns>The new tree.</returns>
            internal Node AddRange(IEnumerable<T> keys)
            {
                Requires.NotNull(keys, nameof(keys));

                if (this.IsEmpty)
                {
                    return CreateRange(keys);
                }

                Node newRight = _right!.AddRange(keys);
                Node result = this.MutateRight(newRight);
                return result.BalanceMany();
            }

            /// <summary>
            /// Adds the specified keys to this tree.
            /// </summary>
            /// <param name="keys">The keys.</param>
            /// <returns>The new tree.</returns>
            internal Node AddRange(ReadOnlySpan<T> keys)
            {
                if (this.IsEmpty)
                {
                    return NodeTreeFromList(keys);
                }

                Node newRight = _right!.AddRange(keys);
                Node result = this.MutateRight(newRight);
                return result.BalanceMany();
            }

            /// <summary>
            /// Adds the specified keys at a given index to this tree.
            /// </summary>
            /// <param name="index">The location for the new keys.</param>
            /// <param name="keys">The keys.</param>
            /// <returns>The new tree.</returns>
            internal Node InsertRange(int index, IEnumerable<T> keys)
            {
                Requires.Range(index >= 0 && index <= this.Count, nameof(index));
                Requires.NotNull(keys, nameof(keys));

                if (this.IsEmpty)
                {
                    return CreateRange(keys);
                }

                Node result;
                if (index <= _left!._count)
                {
                    Node newLeft = _left.InsertRange(index, keys);
                    result = this.MutateLeft(newLeft);
                }
                else
                {
                    Node newRight = _right!.InsertRange(index - _left._count - 1, keys);
                    result = this.MutateRight(newRight);
                }

                return result.BalanceMany();
            }

            /// <summary>
            /// Removes a value at a given index to this node.
            /// </summary>
            /// <param name="index">The location for the new value.</param>
            /// <returns>The new tree.</returns>
            internal Node RemoveAt(int index)
            {
                Requires.Range(index >= 0 && index < this.Count, nameof(index));
                Debug.Assert(_left != null && _right != null);

                Node result;
                if (index == _left._count)
                {
                    // We have a match. If this is a leaf, just remove it
                    // by returning Empty.  If we have only one child,
                    // replace the node with the child.
                    if (_right.IsEmpty && _left.IsEmpty)
                    {
                        result = EmptyNode;
                    }
                    else if (_right.IsEmpty && !_left.IsEmpty)
                    {
                        result = _left;
                    }
                    else if (!_right.IsEmpty && _left.IsEmpty)
                    {
                        result = _right;
                    }
                    else
                    {
                        // We have two children. Remove the next-highest node and replace
                        // this node with it.
                        ImmutableList<T>.Node successor = _right;
                        while (!successor._left!.IsEmpty)
                        {
                            successor = successor._left;
                        }

                        ImmutableList<T>.Node newRight = _right.RemoveAt(0);
                        result = successor.MutateBoth(left: _left, right: newRight);
                    }
                }
                else if (index < _left._count)
                {
                    ImmutableList<T>.Node newLeft = _left.RemoveAt(index);
                    result = this.MutateLeft(newLeft);
                }
                else
                {
                    ImmutableList<T>.Node newRight = _right.RemoveAt(index - _left._count - 1);
                    result = this.MutateRight(newRight);
                }

                return result.IsEmpty || result.IsBalanced ? result : result.Balance();
            }

            /// <summary>
            /// Removes all the elements that match the conditions defined by the specified
            /// predicate.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the elements
            /// to remove.
            /// </param>
            /// <returns>
            /// The new node tree.
            /// </returns>
            internal Node RemoveAll(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                ImmutableList<T>.Node result = this;
                var enumerator = new Enumerator(result);
                try
                {
                    int startIndex = 0;
                    while (enumerator.MoveNext())
                    {
                        if (match(enumerator.Current))
                        {
                            result = result.RemoveAt(startIndex);
                            enumerator.Dispose();
                            enumerator = new Enumerator(result, startIndex: startIndex);
                        }
                        else
                        {
                            startIndex++;
                        }
                    }
                }
                finally
                {
                    enumerator.Dispose();
                }

                Debug.Assert(result != null);
                return result;
            }

            /// <summary>
            /// Replaces a value at a given index.
            /// </summary>
            /// <param name="index">The location for the new value.</param>
            /// <param name="value">The new value for the node.</param>
            /// <returns>The new tree.</returns>
            internal Node ReplaceAt(int index, T value)
            {
                Requires.Range(index >= 0 && index < this.Count, nameof(index));
                Debug.Assert(!this.IsEmpty);

                Node result;
                if (index == _left!._count)
                {
                    // We have a match.
                    result = this.MutateKey(value);
                }
                else if (index < _left._count)
                {
                    ImmutableList<T>.Node newLeft = _left.ReplaceAt(index, value);
                    result = this.MutateLeft(newLeft);
                }
                else
                {
                    ImmutableList<T>.Node newRight = _right!.ReplaceAt(index - _left._count - 1, value);
                    result = this.MutateRight(newRight);
                }

                return result;
            }

            /// <summary>
            /// Reverses the order of the elements in the entire <see cref="ImmutableList{T}"/>.
            /// </summary>
            /// <returns>The reversed list.</returns>
            internal Node Reverse() => this.Reverse(0, this.Count);

            /// <summary>
            /// Reverses the order of the elements in the specified range.
            /// </summary>
            /// <param name="index">The zero-based starting index of the range to reverse.</param>
            /// <param name="count">The number of elements in the range to reverse.</param>
            /// <returns>The reversed list.</returns>
            internal Node Reverse(int index, int count)
            {
                Requires.Range(index >= 0, nameof(index));
                Requires.Range(count >= 0, nameof(count));
                Requires.Range(index + count <= this.Count, nameof(index));

                Node result = this;
                int start = index;
                int end = index + count - 1;
                while (start < end)
                {
                    T a = result.ItemRef(start);
                    T b = result.ItemRef(end);
                    result = result
                        .ReplaceAt(end, a)
                        .ReplaceAt(start, b);
                    start++;
                    end--;
                }

                return result;
            }

            /// <summary>
            /// Sorts the elements in the entire <see cref="ImmutableList{T}"/> using
            /// the default comparer.
            /// </summary>
            internal Node Sort() => this.Sort(Comparer<T>.Default);

            /// <summary>
            /// Sorts the elements in the entire <see cref="ImmutableList{T}"/> using
            /// the specified <see cref="Comparison{T}"/>.
            /// </summary>
            /// <param name="comparison">
            /// The <see cref="Comparison{T}"/> to use when comparing elements.
            /// </param>
            /// <returns>The sorted list.</returns>
            internal Node Sort(Comparison<T> comparison)
            {
                Requires.NotNull(comparison, nameof(comparison));

                // PERF: Eventually this might be reimplemented in a way that does not require allocating an array.
                var array = new T[this.Count];
                this.CopyTo(array);
                Array.Sort(array, comparison);
                return NodeTreeFromList(array.AsOrderedCollection(), 0, this.Count);
            }

            /// <summary>
            /// Sorts the elements in the entire <see cref="ImmutableList{T}"/> using
            /// the specified comparer.
            /// </summary>
            /// <param name="comparer">
            /// The <see cref="IComparer{T}"/> implementation to use when comparing
            /// elements, or null to use the default comparer <see cref="Comparer{T}.Default"/>.
            /// </param>
            /// <returns>The sorted list.</returns>
            internal Node Sort(IComparer<T>? comparer) => this.Sort(0, this.Count, comparer);

            /// <summary>
            /// Sorts the elements in a range of elements in <see cref="ImmutableList{T}"/>
            /// using the specified comparer.
            /// </summary>
            /// <param name="index">
            /// The zero-based starting index of the range to sort.
            /// </param>
            /// <param name="count">
            /// The length of the range to sort.
            /// </param>
            /// <param name="comparer">
            /// The <see cref="IComparer{T}"/> implementation to use when comparing
            /// elements, or null to use the default comparer <see cref="Comparer{T}.Default"/>.
            /// </param>
            /// <returns>The sorted list.</returns>
            internal Node Sort(int index, int count, IComparer<T>? comparer)
            {
                Requires.Range(index >= 0, nameof(index));
                Requires.Range(count >= 0, nameof(count));
                Requires.Argument(index + count <= this.Count);

                // PERF: Eventually this might be reimplemented in a way that does not require allocating an array.
                var array = new T[this.Count];
                this.CopyTo(array);
                Array.Sort(array, index, count, comparer);
                return NodeTreeFromList(array.AsOrderedCollection(), 0, this.Count);
            }

            /// <summary>
            /// Searches a range of elements in the sorted <see cref="ImmutableList{T}"/>
            /// for an element using the specified comparer and returns the zero-based index
            /// of the element.
            /// </summary>
            /// <param name="index">The zero-based starting index of the range to search.</param>
            /// <param name="count"> The length of the range to search.</param>
            /// <param name="item">The object to locate. The value can be null for reference types.</param>
            /// <param name="comparer">
            /// The <see cref="IComparer{T}"/> implementation to use when comparing
            /// elements, or null to use the default comparer <see cref="Comparer{T}.Default"/>.
            /// </param>
            /// <returns>
            /// The zero-based index of item in the sorted <see cref="ImmutableList{T}"/>,
            /// if item is found; otherwise, a negative number that is the bitwise complement
            /// of the index of the next element that is larger than item or, if there is
            /// no larger element, the bitwise complement of <see cref="ImmutableList{T}.Count"/>.
            /// </returns>
            /// <exception cref="ArgumentOutOfRangeException">
            /// <paramref name="index"/> is less than 0.-or-<paramref name="count"/> is less than 0.
            /// </exception>
            /// <exception cref="ArgumentException">
            /// <paramref name="index"/> and <paramref name="count"/> do not denote a valid range in the <see cref="ImmutableList{T}"/>.
            /// </exception>
            /// <exception cref="InvalidOperationException">
            /// <paramref name="comparer"/> is null, and the default comparer <see cref="Comparer{T}.Default"/>
            /// cannot find an implementation of the <see cref="IComparable{T}"/> generic interface
            /// or the <see cref="IComparable"/> interface for type <typeparamref name="T"/>.
            /// </exception>
            internal int BinarySearch(int index, int count, T item, IComparer<T>? comparer)
            {
                Requires.Range(index >= 0, nameof(index));
                Requires.Range(count >= 0, nameof(count));
                comparer ??= Comparer<T>.Default;

                if (this.IsEmpty || count <= 0)
                {
                    return ~index;
                }

                // If this node is not within range, defer to either branch as appropriate.
                int thisNodeIndex = _left!.Count; // this is only the index within the AVL tree, treating this node as root rather than a member of a larger tree.
                if (index + count <= thisNodeIndex)
                {
                    return _left.BinarySearch(index, count, item, comparer);
                }
                else if (index > thisNodeIndex)
                {
                    int result = _right!.BinarySearch(index - thisNodeIndex - 1, count, item, comparer);
                    int offset = thisNodeIndex + 1;
                    return result < 0 ? result - offset : result + offset;
                }

                // We're definitely in the caller's designated range now.
                // Any possible match will be a descendant of this node (or this immediate one).
                // Some descendants may not be in range, but if we hit any it means no match was found,
                // and a negative response would come back from the above code to the below code.
                int compare = comparer.Compare(item, _key);
                if (compare == 0)
                {
                    return thisNodeIndex;
                }
                else if (compare > 0)
                {
                    int adjustedCount = count - (thisNodeIndex - index) - 1;
                    int result = adjustedCount < 0 ? -1 : _right!.BinarySearch(0, adjustedCount, item, comparer);
                    int offset = thisNodeIndex + 1;
                    return result < 0 ? result - offset : result + offset;
                }
                else
                {
                    if (index == thisNodeIndex)
                    {
                        // We can't go any further left.
                        return ~index;
                    }

                    int result = _left.BinarySearch(index, count, item, comparer);
                    return result;
                }
            }

            /// <summary>
            /// Searches for the specified object and returns the zero-based index of the
            /// first occurrence within the range of elements in the <see cref="ImmutableList{T}"/>
            /// that starts at the specified index and contains the specified number of elements.
            /// </summary>
            /// <param name="item">
            /// The object to locate in the <see cref="ImmutableList{T}"/>. The value
            /// can be null for reference types.
            /// </param>
            /// <param name="equalityComparer">The equality comparer to use for testing the match of two elements.</param>
            /// <returns>
            /// The zero-based index of the first occurrence of <paramref name="item"/> within the entire
            /// <see cref="ImmutableList{T}"/>, if found; otherwise, -1.
            /// </returns>
            internal int IndexOf(T item, IEqualityComparer<T>? equalityComparer) => this.IndexOf(item, 0, this.Count, equalityComparer);

            /// <summary>
            /// Searches for the specified object and returns <c>true</c> if it is found, <c>false</c> otherwise.
            /// </summary>
            /// <param name="item">
            /// The object to locate in the <see cref="ImmutableList{T}"/>. The value
            /// can be null for reference types.
            /// </param>
            /// <param name="equalityComparer">
            /// The equality comparer to use for testing the match of two elements.
            /// </param>
            /// <returns>
            /// <c>true</c> if it is found, <c>false</c> otherwise.
            /// </returns>
            internal bool Contains(T item, IEqualityComparer<T> equalityComparer) => Contains(this, item, equalityComparer);

            /// <summary>
            /// Searches for the specified object and returns the zero-based index of the
            /// first occurrence within the range of elements in the <see cref="ImmutableList{T}"/>
            /// that starts at the specified index and contains the specified number of elements.
            /// </summary>
            /// <param name="item">
            /// The object to locate in the <see cref="ImmutableList{T}"/>. The value
            /// can be null for reference types.
            /// </param>
            /// <param name="index">
            /// The zero-based starting index of the search. 0 (zero) is valid in an empty
            /// list.
            /// </param>
            /// <param name="count">
            /// The number of elements in the section to search.
            /// </param>
            /// <param name="equalityComparer">
            /// The equality comparer to use in the search.
            /// If <c>null</c>, <see cref="EqualityComparer{T}.Default"/> is used.
            /// </param>
            /// <returns>
            /// The zero-based index of the first occurrence of <paramref name="item"/> within the range of
            /// elements in the <see cref="ImmutableList{T}"/> that starts at <paramref name="index"/> and
            /// contains <paramref name="count"/> number of elements, if found; otherwise, -1.
            /// </returns>
            internal int IndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer)
            {
                Requires.Range(index >= 0, nameof(index));
                Requires.Range(count >= 0, nameof(count));
                Requires.Range(count <= this.Count, nameof(count));
                Requires.Range(index + count <= this.Count, nameof(count));

                equalityComparer ??= EqualityComparer<T>.Default;
                using (var enumerator = new Enumerator(this, startIndex: index, count: count))
                {
                    while (enumerator.MoveNext())
                    {
                        if (equalityComparer.Equals(item, enumerator.Current))
                        {
                            return index;
                        }

                        index++;
                    }
                }

                return -1;
            }

            /// <summary>
            /// Searches for the specified object and returns the zero-based index of the
            /// last occurrence within the range of elements in the <see cref="ImmutableList{T}"/>
            /// that contains the specified number of elements and ends at the specified
            /// index.
            /// </summary>
            /// <param name="item">
            /// The object to locate in the <see cref="ImmutableList{T}"/>. The value
            /// can be null for reference types.
            /// </param>
            /// <param name="index">The zero-based starting index of the backward search.</param>
            /// <param name="count">The number of elements in the section to search.</param>
            /// <param name="equalityComparer">The equality comparer to use for testing the match of two elements.</param>
            /// <returns>
            /// The zero-based index of the last occurrence of <paramref name="item"/> within the range of elements
            /// in the <see cref="ImmutableList{T}"/> that contains <paramref name="count"/> number of elements
            /// and ends at <paramref name="index"/>, if found; otherwise, -1.
            /// </returns>
            internal int LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer)
            {
                Requires.Range(index >= 0, nameof(index));
                Requires.Range(count >= 0 && count <= this.Count, nameof(count));
                Requires.Argument(index - count + 1 >= 0);

                equalityComparer ??= EqualityComparer<T>.Default;
                using (var enumerator = new Enumerator(this, startIndex: index, count: count, reversed: true))
                {
                    while (enumerator.MoveNext())
                    {
                        if (equalityComparer.Equals(item, enumerator.Current))
                        {
                            return index;
                        }

                        index--;
                    }
                }

                return -1;
            }

            /// <summary>
            /// Copies the entire <see cref="ImmutableList{T}"/> to a compatible one-dimensional
            /// array, starting at the beginning of the target array.
            /// </summary>
            /// <param name="array">
            /// The one-dimensional <see cref="Array"/> that is the destination of the elements
            /// copied from <see cref="ImmutableList{T}"/>. The <see cref="Array"/> must have
            /// zero-based indexing.
            /// </param>
            internal void CopyTo(T[] array)
            {
                Requires.NotNull(array, nameof(array));
                Requires.Range(array.Length >= this.Count, nameof(array));

                int index = 0;
                foreach (T element in this)
                {
                    array[index++] = element;
                }
            }

            /// <summary>
            /// Copies the entire <see cref="ImmutableList{T}"/> to a compatible one-dimensional
            /// array, starting at the specified index of the target array.
            /// </summary>
            /// <param name="array">
            /// The one-dimensional <see cref="Array"/> that is the destination of the elements
            /// copied from <see cref="ImmutableList{T}"/>. 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>
            internal void CopyTo(T[] array, int arrayIndex)
            {
                Requires.NotNull(array, nameof(array));
                Requires.Range(arrayIndex >= 0, nameof(arrayIndex));
                Requires.Range(array.Length >= arrayIndex + this.Count, nameof(arrayIndex));

                foreach (T element in this)
                {
                    array[arrayIndex++] = element;
                }
            }

            /// <summary>
            /// Copies a range of elements from the <see cref="ImmutableList{T}"/> to
            /// a compatible one-dimensional array, starting at the specified index of the
            /// target array.
            /// </summary>
            /// <param name="index">
            /// The zero-based index in the source <see cref="ImmutableList{T}"/> at
            /// which copying begins.
            /// </param>
            /// <param name="array">
            /// The one-dimensional <see cref="Array"/> that is the destination of the elements
            /// copied from <see cref="ImmutableList{T}"/>. 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>
            /// <param name="count">The number of elements to copy.</param>
            internal void CopyTo(int index, T[] array, int arrayIndex, int count)
            {
                Requires.NotNull(array, nameof(array));
                Requires.Range(index >= 0, nameof(index));
                Requires.Range(count >= 0, nameof(count));
                Requires.Range(index + count <= this.Count, nameof(count));
                Requires.Range(arrayIndex >= 0, nameof(arrayIndex));
                Requires.Range(arrayIndex + count <= array.Length, nameof(arrayIndex));

                using (var enumerator = new Enumerator(this, startIndex: index, count: count))
                {
                    while (enumerator.MoveNext())
                    {
                        array[arrayIndex++] = enumerator.Current;
                    }
                }
            }

            /// <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>
            internal void 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 (T element in this)
                {
                    array.SetValue(element, arrayIndex++);
                }
            }

            /// <summary>
            /// Converts the elements in the current <see cref="ImmutableList{T}"/> to
            /// another type, and returns a list containing the converted elements.
            /// </summary>
            /// <param name="converter">
            /// A <see cref="Func{T, TResult}"/> delegate that converts each element from
            /// one type to another type.
            /// </param>
            /// <typeparam name="TOutput">
            /// The type of the elements of the target array.
            /// </typeparam>
            /// <returns>
            /// A node tree with the transformed list.
            /// </returns>
            internal ImmutableList<TOutput>.Node ConvertAll<TOutput>(Func<T, TOutput> converter)
            {
                ImmutableList<TOutput>.Node root = ImmutableList<TOutput>.Node.EmptyNode;

                if (this.IsEmpty)
                {
                    return root;
                }

                return root.AddRange(Linq.Enumerable.Select(this, converter));
            }

            /// <summary>
            /// Determines whether every element in the <see cref="ImmutableList{T}"/>
            /// matches the conditions defined by the specified predicate.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions to check against
            /// the elements.
            /// </param>
            /// <returns>
            /// true if every element in the <see cref="ImmutableList{T}"/> matches the
            /// conditions defined by the specified predicate; otherwise, false. If the list
            /// has no elements, the return value is true.
            /// </returns>
            internal bool TrueForAll(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                foreach (T item in this)
                {
                    if (!match(item))
                    {
                        return false;
                    }
                }

                return true;
            }

            /// <summary>
            /// Determines whether the <see cref="ImmutableList{T}"/> contains elements
            /// that match the conditions defined by the specified predicate.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the elements
            /// to search for.
            /// </param>
            /// <returns>
            /// true if the <see cref="ImmutableList{T}"/> contains one or more elements
            /// that match the conditions defined by the specified predicate; otherwise,
            /// false.
            /// </returns>
            internal bool Exists(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                foreach (T item in this)
                {
                    if (match(item))
                    {
                        return true;
                    }
                }

                return false;
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the first occurrence within the entire <see cref="ImmutableList{T}"/>.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element
            /// to search for.
            /// </param>
            /// <returns>
            /// The first element that matches the conditions defined by the specified predicate,
            /// if found; otherwise, the default value for type <typeparamref name="T"/>.
            /// </returns>
            internal T? Find(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                foreach (T item in this)
                {
                    if (match(item))
                    {
                        return item;
                    }
                }

                return default;
            }

            /// <summary>
            /// Retrieves all the elements that match the conditions defined by the specified
            /// predicate.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the elements
            /// to search for.
            /// </param>
            /// <returns>
            /// A <see cref="ImmutableList{T}"/> containing all the elements that match
            /// the conditions defined by the specified predicate, if found; otherwise, an
            /// empty <see cref="ImmutableList{T}"/>.
            /// </returns>
            internal ImmutableList<T> FindAll(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                if (this.IsEmpty)
                {
                    return ImmutableList<T>.Empty;
                }

                List<T>? list = null;
                foreach (T item in this)
                {
                    if (match(item))
                    {
                        list ??= new List<T>();

                        list.Add(item);
                    }
                }

                return list != null ?
                    ImmutableList.CreateRange(list) :
                    ImmutableList<T>.Empty;
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the zero-based index of the first occurrence within
            /// the entire <see cref="ImmutableList{T}"/>.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element
            /// to search for.
            /// </param>
            /// <returns>
            /// The zero-based index of the first occurrence of an element that matches the
            /// conditions defined by <paramref name="match"/>, if found; otherwise, -1.
            /// </returns>
            internal int FindIndex(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                return this.FindIndex(0, _count, match);
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the zero-based index of the first occurrence within
            /// the range of elements in the <see cref="ImmutableList{T}"/> that extends
            /// from the specified index to the last element.
            /// </summary>
            /// <param name="startIndex">The zero-based starting index of the search.</param>
            /// <param name="match">The <see cref="Predicate{T}"/> delegate that defines the conditions of the element to search for.</param>
            /// <returns>
            /// The zero-based index of the first occurrence of an element that matches the
            /// conditions defined by <paramref name="match"/>, if found; otherwise, -1.
            /// </returns>
            internal int FindIndex(int startIndex, Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));
                Requires.Range(startIndex >= 0 && startIndex <= this.Count, nameof(startIndex));

                return this.FindIndex(startIndex, this.Count - startIndex, match);
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the zero-based index of the first occurrence within
            /// the range of elements in the <see cref="ImmutableList{T}"/> that starts
            /// at the specified index and contains the specified number of elements.
            /// </summary>
            /// <param name="startIndex">The zero-based starting index of the search.</param>
            /// <param name="count">The number of elements in the section to search.</param>
            /// <param name="match">The <see cref="Predicate{T}"/> delegate that defines the conditions of the element to search for.</param>
            /// <returns>
            /// The zero-based index of the first occurrence of an element that matches the
            /// conditions defined by <paramref name="match"/>, if found; otherwise, -1.
            /// </returns>
            internal int FindIndex(int startIndex, int count, Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));
                Requires.Range(startIndex >= 0, nameof(startIndex));
                Requires.Range(count >= 0, nameof(count));
                Requires.Range(startIndex + count <= this.Count, nameof(count));

                using (var enumerator = new Enumerator(this, startIndex: startIndex, count: count))
                {
                    int index = startIndex;
                    while (enumerator.MoveNext())
                    {
                        if (match(enumerator.Current))
                        {
                            return index;
                        }

                        index++;
                    }
                }

                return -1;
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the last occurrence within the entire <see cref="ImmutableList{T}"/>.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element
            /// to search for.
            /// </param>
            /// <returns>
            /// The last element that matches the conditions defined by the specified predicate,
            /// if found; otherwise, the default value for type <typeparamref name="T"/>.
            /// </returns>
            internal T? FindLast(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                using (var enumerator = new Enumerator(this, reversed: true))
                {
                    while (enumerator.MoveNext())
                    {
                        if (match(enumerator.Current))
                        {
                            return enumerator.Current;
                        }
                    }
                }

                return default;
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the zero-based index of the last occurrence within
            /// the entire <see cref="ImmutableList{T}"/>.
            /// </summary>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element
            /// to search for.
            /// </param>
            /// <returns>
            /// The zero-based index of the last occurrence of an element that matches the
            /// conditions defined by <paramref name="match"/>, if found; otherwise, -1.
            /// </returns>
            internal int FindLastIndex(Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));

                return this.IsEmpty ? -1 : this.FindLastIndex(this.Count - 1, this.Count, match);
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the zero-based index of the last occurrence within
            /// the range of elements in the <see cref="ImmutableList{T}"/> that extends
            /// from the first element to the specified index.
            /// </summary>
            /// <param name="startIndex">The zero-based starting index of the backward search.</param>
            /// <param name="match">The <see cref="Predicate{T}"/> delegate that defines the conditions of the element
            /// to search for.</param>
            /// <returns>
            /// The zero-based index of the last occurrence of an element that matches the
            /// conditions defined by <paramref name="match"/>, if found; otherwise, -1.
            /// </returns>
            internal int FindLastIndex(int startIndex, Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));
                Requires.Range(startIndex >= 0, nameof(startIndex));
                Requires.Range(startIndex == 0 || startIndex < this.Count, nameof(startIndex));

                return this.IsEmpty ? -1 : this.FindLastIndex(startIndex, startIndex + 1, match);
            }

            /// <summary>
            /// Searches for an element that matches the conditions defined by the specified
            /// predicate, and returns the zero-based index of the last occurrence within
            /// the range of elements in the <see cref="ImmutableList{T}"/> that contains
            /// the specified number of elements and ends at the specified index.
            /// </summary>
            /// <param name="startIndex">The zero-based starting index of the backward search.</param>
            /// <param name="count">The number of elements in the section to search.</param>
            /// <param name="match">
            /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element
            /// to search for.
            /// </param>
            /// <returns>
            /// The zero-based index of the last occurrence of an element that matches the
            /// conditions defined by <paramref name="match"/>, if found; otherwise, -1.
            /// </returns>
            internal int FindLastIndex(int startIndex, int count, Predicate<T> match)
            {
                Requires.NotNull(match, nameof(match));
                Requires.Range(startIndex >= 0, nameof(startIndex));
                Requires.Range(count <= this.Count, nameof(count));
                Requires.Range(startIndex - count + 1 >= 0, nameof(startIndex));

                using (var enumerator = new Enumerator(this, startIndex: startIndex, count: count, reversed: true))
                {
                    int index = startIndex;
                    while (enumerator.MoveNext())
                    {
                        if (match(enumerator.Current))
                        {
                            return index;
                        }

                        index--;
                    }
                }

                return -1;
            }

            /// <summary>
            /// Freezes this node and all descendant nodes so that any mutations require a new instance of the nodes.
            /// </summary>
            internal void Freeze()
            {
                // If this node is frozen, all its descendants must already be frozen.
                if (!_frozen)
                {
                    _left!.Freeze();
                    _right!.Freeze();
                    _frozen = true;
                }
            }

            #region Tree balancing methods

            /// <summary>
            /// AVL rotate left operation.
            /// </summary>
            /// <returns>The rotated tree.</returns>
            private Node RotateLeft()
            {
                Debug.Assert(!this.IsEmpty);
                Debug.Assert(!_right!.IsEmpty);

                return _right.MutateLeft(this.MutateRight(_right._left!));
            }

            /// <summary>
            /// AVL rotate right operation.
            /// </summary>
            /// <returns>The rotated tree.</returns>
            private Node RotateRight()
            {
                Debug.Assert(!this.IsEmpty);
                Debug.Assert(!_left!.IsEmpty);

                return _left.MutateRight(this.MutateLeft(_left._right!));
            }

            /// <summary>
            /// AVL rotate double-left operation.
            /// </summary>
            /// <returns>The rotated tree.</returns>
            private Node DoubleLeft()
            {
                Debug.Assert(!this.IsEmpty);
                Debug.Assert(!_right!.IsEmpty);
                Debug.Assert(!_right!._left!.IsEmpty);

                // The following is an optimized version of rotating the right child right, then rotating the parent left.
                Node right = _right;
                Node rightLeft = right._left;
                return rightLeft.MutateBoth(
                    left: this.MutateRight(rightLeft._left!),
                    right: right.MutateLeft(rightLeft._right!));
            }

            /// <summary>
            /// AVL rotate double-right operation.
            /// </summary>
            /// <returns>The rotated tree.</returns>
            private Node DoubleRight()
            {
                Debug.Assert(!this.IsEmpty);
                Debug.Assert(!_left!.IsEmpty);
                Debug.Assert(!_left._right!.IsEmpty);

                // The following is an optimized version of rotating the left child left, then rotating the parent right.
                Node left = _left;
                Node leftRight = left._right;
                return leftRight.MutateBoth(
                    left: left.MutateRight(leftRight._left!),
                    right: this.MutateLeft(leftRight._right!));
            }

            /// <summary>
            /// Gets a value indicating whether this tree is in balance.
            /// </summary>
            /// <returns>
            /// 0 if the heights of both sides are the same, a positive integer if the right side is taller, or a negative integer if the left side is taller.
            /// </returns>
            private int BalanceFactor
            {
                get
                {
                    Debug.Assert(!this.IsEmpty);
                    return _right!._height - _left!._height;
                }
            }

            /// <summary>
            /// Determines whether this tree is right heavy.
            /// </summary>
            /// <returns>
            /// <c>true</c> if this tree is right heavy; otherwise, <c>false</c>.
            /// </returns>
            private bool IsRightHeavy => this.BalanceFactor >= 2;

            /// <summary>
            /// Determines whether this tree is left heavy.
            /// </summary>
            /// <returns>
            /// <c>true</c> if this tree is left heavy; otherwise, <c>false</c>.
            /// </returns>
            private bool IsLeftHeavy => this.BalanceFactor <= -2;

            /// <summary>
            /// Determines whether this tree has a balance factor of -1, 0, or 1.
            /// </summary>
            /// <returns>
            /// <c>true</c> if this tree is balanced; otherwise, <c>false</c>.
            /// </returns>
            private bool IsBalanced => unchecked((uint)(this.BalanceFactor + 1)) <= 2;

            /// <summary>
            /// Balances this tree.
            /// </summary>
            /// <returns>A balanced tree.</returns>
            private Node Balance() => this.IsLeftHeavy ? this.BalanceLeft() : this.BalanceRight();

            /// <summary>
            /// Balances the left side of this tree by rotating this tree rightwards.
            /// </summary>
            /// <returns>A balanced tree.</returns>
            private Node BalanceLeft()
            {
                Debug.Assert(!this.IsEmpty);
                Debug.Assert(this.IsLeftHeavy);

                return _left!.BalanceFactor > 0 ? this.DoubleRight() : this.RotateRight();
            }

            /// <summary>
            /// Balances the right side of this tree by rotating this tree leftwards.
            /// </summary>
            /// <returns>A balanced tree.</returns>
            private Node BalanceRight()
            {
                Debug.Assert(!this.IsEmpty);
                Debug.Assert(this.IsRightHeavy);

                return _right!.BalanceFactor < 0 ? this.DoubleLeft() : this.RotateLeft();
            }

            /// <summary>
            /// Balances this tree.  Allows for a large imbalance between left and
            /// right nodes, but assumes left and right nodes are individually balanced.
            /// </summary>
            /// <returns>A balanced tree.</returns>
            /// <remarks>
            /// If this tree is already balanced, this method does nothing.
            /// </remarks>
            private Node BalanceMany()
            {
                Node tree = this;
                Debug.Assert(tree._left != null && tree._right != null);
                while (!tree.IsBalanced)
                {
                    if (tree.IsRightHeavy)
                    {
                        tree = tree.BalanceRight();
                        Debug.Assert(tree._left != null);
                        tree.MutateLeft(tree._left.BalanceMany());
                    }
                    else
                    {
                        tree = tree.BalanceLeft();
                        Debug.Assert(tree._right != null);
                        tree.MutateRight(tree._right.BalanceMany());
                    }
                }

                return tree;
            }

            #endregion

            /// <summary>
            /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node
            /// with the described changes.
            /// </summary>
            /// <param name="left">The left branch of the mutated node.</param>
            /// <param name="right">The right branch of the mutated node.</param>
            /// <returns>The mutated (or created) node.</returns>
            private Node MutateBoth(Node left, Node right)
            {
                Requires.NotNull(left, nameof(left));
                Requires.NotNull(right, nameof(right));
                Debug.Assert(!this.IsEmpty);

                if (_frozen)
                {
                    return new Node(_key, left, right);
                }
                else
                {
                    _left = left;
                    _right = right;
                    _height = ParentHeight(left, right);
                    _count = ParentCount(left, right);
                    return this;
                }
            }

            /// <summary>
            /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node
            /// with the described changes.
            /// </summary>
            /// <param name="left">The left branch of the mutated node.</param>
            /// <returns>The mutated (or created) node.</returns>
            private Node MutateLeft(Node left)
            {
                Requires.NotNull(left, nameof(left));
                Debug.Assert(!this.IsEmpty);

                if (_frozen)
                {
                    return new Node(_key, left, _right!);
                }
                else
                {
                    _left = left;
                    _height = ParentHeight(left, _right!);
                    _count = ParentCount(left, _right!);
                    return this;
                }
            }

            /// <summary>
            /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node
            /// with the described changes.
            /// </summary>
            /// <param name="right">The right branch of the mutated node.</param>
            /// <returns>The mutated (or created) node.</returns>
            private Node MutateRight(Node right)
            {
                Requires.NotNull(right, nameof(right));
                Debug.Assert(!this.IsEmpty);

                if (_frozen)
                {
                    return new Node(_key, _left!, right);
                }
                else
                {
                    _right = right;
                    _height = ParentHeight(_left!, right);
                    _count = ParentCount(_left!, right);
                    return this;
                }
            }

            /// <summary>
            /// Calculates the height of the parent node from its children.
            /// </summary>
            /// <param name="left">The left child.</param>
            /// <param name="right">The right child.</param>
            /// <returns>The height of the parent node.</returns>
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            private static byte ParentHeight(Node left, Node right) => checked((byte)(1 + Math.Max(left._height, right._height)));

            /// <summary>
            /// Calculates the number of elements in the parent node from its children.
            /// </summary>
            /// <param name="left">The left child.</param>
            /// <param name="right">The right child.</param>
            /// <returns>The number of elements in the parent node.</returns>
            private static int ParentCount(Node left, Node right) => 1 + left._count + right._count;

            /// <summary>
            /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node
            /// with the described changes.
            /// </summary>
            /// <param name="key">The new key for this node.</param>
            /// <returns>The mutated (or created) node.</returns>
            private Node MutateKey(T key)
            {
                Debug.Assert(!this.IsEmpty);

                if (_frozen)
                {
                    return new Node(key, _left!, _right!);
                }
                else
                {
                    _key = key;
                    return this;
                }
            }

            /// <summary>
            /// Creates a node from the specified keys.
            /// </summary>
            /// <param name="keys">The keys.</param>
            /// <returns>The root of the created node tree.</returns>
            private static Node CreateRange(IEnumerable<T> keys)
            {
                ImmutableList<T>? other;
                if (TryCastToImmutableList(keys, out other))
                {
                    return other._root;
                }

                IOrderedCollection<T> list = keys.AsOrderedCollection();
                return NodeTreeFromList(list, 0, list.Count);
            }

            /// <summary>
            /// Creates a leaf node.
            /// </summary>
            /// <param name="key">The leaf node's key.</param>
            /// <returns>The leaf node.</returns>
            private static Node CreateLeaf(T key) => new Node(key, left: EmptyNode, right: EmptyNode);

            /// <summary>
            /// Traverses the node tree looking for a node with the provided value. The provided node will be checked
            /// then we will recursively check it's left and right nodes.
            /// </summary>
            /// <param name="node">
            /// The node to check.
            /// </param>
            /// <param name="value">
            /// The value to check for.
            /// </param>
            /// <param name="equalityComparer">
            /// The equality comparer to use for testing the node and value.
            /// </param>
            /// <returns></returns>
            private static bool Contains(Node node, T value, IEqualityComparer<T> equalityComparer) => !node.IsEmpty && (equalityComparer.Equals(value, node._key) || Contains(node._left!, value, equalityComparer) || Contains(node._right!, value, equalityComparer));
        }
    }
}