File: System\Collections\Immutable\ImmutableArray_1.Builder.cs
Web Access
Project: src\src\libraries\System.Collections.Immutable\src\System.Collections.Immutable.csproj (System.Collections.Immutable)
// 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.Runtime.CompilerServices;
 
namespace System.Collections.Immutable
{
    public partial struct ImmutableArray<T>
    {
        /// <summary>
        /// A writable array accessor that can be converted into an <see cref="ImmutableArray{T}"/>
        /// instance without allocating memory.
        /// </summary>
        [DebuggerDisplay("Count = {Count}")]
        [DebuggerTypeProxy(typeof(ImmutableArrayBuilderDebuggerProxy<>))]
        public sealed class Builder : IList<T>, IReadOnlyList<T>
        {
            /// <summary>
            /// The backing array for the builder.
            /// </summary>
            private T[] _elements;
 
            /// <summary>
            /// The number of initialized elements in the array.
            /// </summary>
            private int _count;
 
            /// <summary>
            /// Initializes a new instance of the <see cref="Builder"/> class.
            /// </summary>
            /// <param name="capacity">The initial capacity of the internal array.</param>
            internal Builder(int capacity)
            {
                Requires.Range(capacity >= 0, nameof(capacity));
                _elements = new T[capacity];
                _count = 0;
            }
 
            /// <summary>
            /// Initializes a new instance of the <see cref="Builder"/> class.
            /// </summary>
            internal Builder()
                : this(8)
            {
            }
 
            /// <summary>
            /// Get and sets the length of the internal array.  When set the internal array is
            /// reallocated to the given capacity if it is not already the specified length.
            /// </summary>
            public int Capacity
            {
                get { return _elements.Length; }
                set
                {
                    if (value < _count)
                    {
                        throw new ArgumentException(SR.CapacityMustBeGreaterThanOrEqualToCount, paramName: nameof(value));
                    }
 
                    if (value != _elements.Length)
                    {
                        if (value > 0)
                        {
                            var temp = new T[value];
                            if (_count > 0)
                            {
                                Array.Copy(_elements, temp, _count);
                            }
 
                            _elements = temp;
                        }
                        else
                        {
                            _elements = ImmutableArray<T>.Empty.array!;
                        }
                    }
                }
            }
 
            /// <summary>
            /// Gets or sets the length of the builder.
            /// </summary>
            /// <remarks>
            /// If the value is decreased, the array contents are truncated.
            /// If the value is increased, the added elements are initialized to the default value of type <typeparamref name="T"/>.
            /// </remarks>
            public int Count
            {
                get
                {
                    return _count;
                }
 
                set
                {
                    Requires.Range(value >= 0, nameof(value));
                    if (value < _count)
                    {
                        // truncation mode
                        // Clear the elements of the elements that are effectively removed.
 
                        // PERF: Array.Clear works well for big arrays,
                        //       but may have too much overhead with small ones (which is the common case here)
                        if (_count - value > 64)
                        {
                            Array.Clear(_elements, value, _count - value);
                        }
                        else
                        {
                            for (int i = value; i < this.Count; i++)
                            {
                                _elements[i] = default(T)!;
                            }
                        }
                    }
                    else if (value > _count)
                    {
                        // expansion
                        this.EnsureCapacity(value);
                    }
 
                    _count = value;
                }
            }
 
            private static void ThrowIndexOutOfRangeException() => throw new IndexOutOfRangeException();
 
            /// <summary>
            /// Gets or sets the element at the specified index.
            /// </summary>
            /// <param name="index">The index.</param>
            /// <returns></returns>
            /// <exception cref="IndexOutOfRangeException">
            /// </exception>
            public T this[int index]
            {
                get
                {
                    if (index >= this.Count)
                    {
                        ThrowIndexOutOfRangeException();
                    }
 
                    return _elements[index];
                }
 
                set
                {
                    if (index >= this.Count)
                    {
                        ThrowIndexOutOfRangeException();
                    }
 
                    _elements[index] = value;
                }
            }
 
            /// <summary>
            /// Gets a read-only reference to the element at the specified index.
            /// </summary>
            /// <param name="index">The index.</param>
            /// <returns></returns>
            /// <exception cref="IndexOutOfRangeException">
            /// </exception>
            public ref readonly T ItemRef(int index)
            {
                if (index >= this.Count)
                {
                    ThrowIndexOutOfRangeException();
                }
 
                return ref this._elements[index];
            }
 
            /// <summary>
            /// Gets a value indicating whether the <see cref="ICollection{T}"/> is read-only.
            /// </summary>
            /// <returns>true if the <see cref="ICollection{T}"/> is read-only; otherwise, false.
            ///   </returns>
            bool ICollection<T>.IsReadOnly
            {
                get { return false; }
            }
 
            /// <summary>
            /// Returns an immutable copy of the current contents of this collection.
            /// </summary>
            /// <returns>An immutable array.</returns>
            public ImmutableArray<T> ToImmutable()
            {
                return new ImmutableArray<T>(this.ToArray());
            }
 
            /// <summary>
            /// Extracts the internal array as an <see cref="ImmutableArray{T}"/> and replaces it
            /// with a zero length array.
            /// </summary>
            /// <exception cref="InvalidOperationException">When <see cref="ImmutableArray{T}.Builder.Count"/> doesn't
            /// equal <see cref="ImmutableArray{T}.Builder.Capacity"/>.</exception>
            public ImmutableArray<T> MoveToImmutable()
            {
                if (Capacity != Count)
                {
                    throw new InvalidOperationException(SR.CapacityMustEqualCountOnMove);
                }
 
                T[] temp = _elements;
                _elements = ImmutableArray<T>.Empty.array!;
                _count = 0;
                return new ImmutableArray<T>(temp);
            }
 
            /// <summary>
            /// Returns the current contents as an <see cref="ImmutableArray{T}"/> and sets the collection to a zero length array.
            /// </summary>
            /// <remarks>
            /// If <see cref="Capacity"/> equals <see cref="Count"/>, the internal array will be extracted
            /// as an <see cref="ImmutableArray{T}"/> without copying the contents. Otherwise, the contents
            /// will be copied into a new array. The collection will then be set to a zero length array.
            /// </remarks>
            /// <returns>An immutable array.</returns>
            public ImmutableArray<T> DrainToImmutable()
            {
                T[] result = _elements;
 
                if (result.Length != _count)
                {
                    result = ToArray();
                }
 
                _elements = ImmutableArray<T>.Empty.array!;
                _count = 0;
 
                return new ImmutableArray<T>(result);
            }
 
            /// <summary>
            /// Removes all items from the <see cref="ICollection{T}"/>.
            /// </summary>
            public void Clear()
            {
                this.Count = 0;
            }
 
            /// <summary>
            /// Inserts an item to the <see cref="IList{T}"/> at the specified index.
            /// </summary>
            /// <param name="index">The zero-based index at which <paramref name="item"/> should be inserted.</param>
            /// <param name="item">The object to insert into the <see cref="IList{T}"/>.</param>
            public void Insert(int index, T item)
            {
                Requires.Range(index >= 0 && index <= this.Count, nameof(index));
                this.EnsureCapacity(this.Count + 1);
 
                if (index < this.Count)
                {
                    Array.Copy(_elements, index, _elements, index + 1, this.Count - index);
                }
 
                _count++;
                _elements[index] = item;
            }
 
            /// <summary>
            /// Inserts the specified values at the specified index.
            /// </summary>
            /// <param name="index">The index at which to insert the value.</param>
            /// <param name="items">The elements to insert.</param>
            public void InsertRange(int index, IEnumerable<T> items)
            {
                Requires.Range(index >= 0 && index <= this.Count, nameof(index));
                Requires.NotNull(items, nameof(items));
 
                int count = ImmutableExtensions.GetCount(ref items);
                this.EnsureCapacity(this.Count + count);
 
                if (index != this.Count)
                {
                    Array.Copy(_elements, index, _elements, index + count, _count - index);
                }
 
                if (!items.TryCopyTo(_elements, index))
                {
                    foreach (T item in items)
                    {
                        _elements[index++] = item;
                    }
                }
 
                _count += count;
            }
 
            /// <summary>
            /// Inserts the specified values at the specified index.
            /// </summary>
            /// <param name="index">The index at which to insert the value.</param>
            /// <param name="items">The elements to insert.</param>
            public void InsertRange(int index, ImmutableArray<T> items)
            {
                Requires.Range(index >= 0 && index <= this.Count, nameof(index));
 
                if (items.IsEmpty)
                {
                    return;
                }
 
                this.EnsureCapacity(this.Count + items.Length);
 
                if (index != this.Count)
                {
                    Array.Copy(_elements, index, _elements, index + items.Length, _count - index);
                }
 
                Array.Copy(items.array!, 0, _elements, index, items.Length);
 
                _count += items.Length;
            }
 
            /// <summary>
            /// Adds an item to the <see cref="ICollection{T}"/>.
            /// </summary>
            /// <param name="item">The object to add to the <see cref="ICollection{T}"/>.</param>
            public void Add(T item)
            {
                int newCount = _count + 1;
                this.EnsureCapacity(newCount);
                _elements[_count] = item;
                _count = newCount;
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <param name="items">The items.</param>
            public void AddRange(IEnumerable<T> items)
            {
                Requires.NotNull(items, nameof(items));
 
                int count;
                if (items.TryGetCount(out count))
                {
                    this.EnsureCapacity(this.Count + count);
 
                    if (items.TryCopyTo(_elements, _count))
                    {
                        _count += count;
                        return;
                    }
                }
 
                foreach (T item in items)
                {
                    this.Add(item);
                }
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <param name="items">The items.</param>
            public void AddRange(params T[] items)
            {
                Requires.NotNull(items, nameof(items));
 
                int offset = this.Count;
                this.Count += items.Length;
 
                Array.Copy(items, 0, _elements, offset, items.Length);
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <typeparam name="TDerived">The type that derives from the type of item already in the array.</typeparam>
            /// <param name="items">The items.</param>
            public void AddRange<TDerived>(TDerived[] items) where TDerived : T
            {
                Requires.NotNull(items, nameof(items));
 
                int offset = this.Count;
                this.Count += items.Length;
 
                Array.Copy(items, 0, _elements, offset, items.Length);
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <param name="items">The items.</param>
            /// <param name="length">The number of elements from the source array to add.</param>
            public void AddRange(T[] items, int length)
            {
                Requires.NotNull(items, nameof(items));
                Requires.Range(length >= 0 && length <= items.Length, nameof(length));
 
                int offset = this.Count;
                this.Count += length;
 
                Array.Copy(items, 0, _elements, offset, length);
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <param name="items">The items.</param>
            public void AddRange(ImmutableArray<T> items)
            {
                this.AddRange(items, items.Length);
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <param name="items">The items.</param>
            /// <param name="length">The number of elements from the source array to add.</param>
            public void AddRange(ImmutableArray<T> items, int length)
            {
                Requires.Range(length >= 0, nameof(length));
 
                if (items.array != null)
                {
                    this.AddRange(items.array, length);
                }
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <param name="items">The items to add at the end of the array.</param>
            public void AddRange(params ReadOnlySpan<T> items)
            {
                int offset = this.Count;
                this.Count += items.Length;
 
                items.CopyTo(new Span<T>(_elements, offset, items.Length));
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <typeparam name="TDerived">The type that derives from the type of item already in the array.</typeparam>
            /// <param name="items">The items to add at the end of the array.</param>
            public void AddRange<TDerived>(params ReadOnlySpan<TDerived> items) where TDerived : T
            {
                int offset = this.Count;
                this.Count += items.Length;
 
                var elements = new Span<T>(_elements, offset, items.Length);
                for (int i = 0; i < items.Length; i++)
                {
                    elements[i] = items[i];
                }
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <typeparam name="TDerived">The type that derives from the type of item already in the array.</typeparam>
            /// <param name="items">The items to add at the end of the array.</param>
            public void AddRange<TDerived>(ImmutableArray<TDerived> items) where TDerived : T
            {
                if (items.array != null)
                {
                    this.AddRange(items.array);
                }
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <param name="items">The items to add at the end of the array.</param>
            public void AddRange(Builder items)
            {
                Requires.NotNull(items, nameof(items));
                this.AddRange(items._elements, items.Count);
            }
 
            /// <summary>
            /// Adds the specified items to the end of the array.
            /// </summary>
            /// <typeparam name="TDerived">The type that derives from the type of item already in the array.</typeparam>
            /// <param name="items">The items to add at the end of the array.</param>
            public void AddRange<TDerived>(ImmutableArray<TDerived>.Builder items) where TDerived : T
            {
                Requires.NotNull(items, nameof(items));
                this.AddRange(items._elements, items.Count);
            }
 
            /// <summary>
            /// Removes the first occurrence of the specified element from the builder.
            /// If no match is found, the builder remains unchanged.
            /// </summary>
            /// <param name="element">The element.</param>
            /// <returns>A value indicating whether the specified element was found and removed from the collection.</returns>
            public bool Remove(T element)
            {
                int index = this.IndexOf(element);
                if (index >= 0)
                {
                    this.RemoveAt(index);
                    return true;
                }
 
                return false;
            }
 
            /// <summary>
            /// Removes the first occurrence of the specified element from the builder.
            /// If no match is found, the builder remains unchanged.
            /// </summary>
            /// <param name="element">The element to remove.</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>A value indicating whether the specified element was found and removed from the collection.</returns>
            public bool Remove(T element, IEqualityComparer<T>? equalityComparer)
            {
                int index = this.IndexOf(element, 0, _count, equalityComparer);
 
                if (index >= 0)
                {
                    this.RemoveAt(index);
                    return true;
                }
 
                return false;
            }
 
            /// <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>
            public void RemoveAll(Predicate<T> match)
            {
                List<int>? removeIndices = null;
                for (int i = 0; i < _count; i++)
                {
                    if (match(_elements[i]))
                    {
                        removeIndices ??= new List<int>();
                        removeIndices.Add(i);
                    }
                }
 
                if (removeIndices != null)
                {
                    RemoveAtRange(removeIndices);
                }
            }
 
            /// <summary>
            /// Removes the <see cref="IList{T}"/> item at the specified index.
            /// </summary>
            /// <param name="index">The zero-based index of the item to remove.</param>
            public void RemoveAt(int index)
            {
                Requires.Range(index >= 0 && index < this.Count, nameof(index));
 
                if (index < this.Count - 1)
                {
                    Array.Copy(_elements, index + 1, _elements, index, this.Count - index - 1);
                }
 
                this.Count--;
            }
 
            /// <summary>
            /// Removes the specified values from this list.
            /// </summary>
            /// <param name="index">The 0-based index into the array for the element to omit from the returned array.</param>
            /// <param name="length">The number of elements to remove.</param>
            public void RemoveRange(int index, int length)
            {
                Requires.Range(index >= 0 && index <= _count, nameof(index));
                Requires.Range(length >= 0 && index <= _count - length, nameof(length));
 
                if (length == 0)
                {
                    return;
                }
 
                if (index + length < this._count)
                {
 
#if NET
                    if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
                    {
                        Array.Clear(_elements, index, length); // Clear the elements so that the gc can reclaim the references.
                    }
#endif
                    Array.Copy(_elements, index + length, _elements, index, this.Count - index - length);
                }
 
                this._count -= length;
            }
 
            /// <summary>
            /// Removes the specified values from this list.
            /// </summary>
            /// <param name="items">The items to remove if matches are found in this list.</param>
            public void RemoveRange(IEnumerable<T> items)
            {
                this.RemoveRange(items, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Removes the specified values from this list.
            /// </summary>
            /// <param name="items">The items to remove if matches are found in this list.</param>
            /// <param name="equalityComparer">
            /// The equality comparer to use in the search.
            /// If <c>null</c>, <see cref="EqualityComparer{T}.Default"/> is used.
            /// </param>
            public void RemoveRange(IEnumerable<T> items, IEqualityComparer<T>? equalityComparer)
            {
                Requires.NotNull(items, nameof(items));
 
                var indicesToRemove = new SortedSet<int>();
                foreach (T item in items)
                {
                    int index = this.IndexOf(item, 0, _count, equalityComparer);
                    while (index >= 0 && !indicesToRemove.Add(index) && index + 1 < _count)
                    {
                        index = this.IndexOf(item, index + 1, equalityComparer);
                    }
                }
 
                this.RemoveAtRange(indicesToRemove);
            }
 
            /// <summary>
            /// Replaces the first equal element in the list with the specified element.
            /// </summary>
            /// <param name="oldValue">The element to replace.</param>
            /// <param name="newValue">The element to replace the old element with.</param>
            public void Replace(T oldValue, T newValue)
            {
                this.Replace(oldValue, newValue, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Replaces the first equal element in the list with the specified element.
            /// </summary>
            /// <param name="oldValue">The element to replace.</param>
            /// <param name="newValue">The element to replace the old element with.</param>
            /// <param name="equalityComparer">
            /// The equality comparer to use in the search.
            /// If <c>null</c>, <see cref="EqualityComparer{T}.Default"/> is used.
            /// </param>
            public void Replace(T oldValue, T newValue, IEqualityComparer<T>? equalityComparer)
            {
                int index = this.IndexOf(oldValue, 0, _count, equalityComparer);
 
                if (index >= 0)
                {
                    _elements[index] = newValue;
                }
            }
 
            /// <summary>
            /// Determines whether the <see cref="ICollection{T}"/> contains a specific value.
            /// </summary>
            /// <param name="item">The object to locate in the <see cref="ICollection{T}"/>.</param>
            /// <returns>
            /// true if <paramref name="item"/> is found in the <see cref="ICollection{T}"/>; otherwise, false.
            /// </returns>
            public bool Contains(T item)
            {
                return this.IndexOf(item) >= 0;
            }
 
            /// <summary>
            /// Creates a new array with the current contents of this Builder.
            /// </summary>
            public T[] ToArray()
            {
                if (this.Count == 0)
                {
                    return Empty.array!;
                }
 
                T[] result = new T[this.Count];
                Array.Copy(_elements, result, this.Count);
                return result;
            }
 
            /// <summary>
            /// Copies the current contents to the specified array.
            /// </summary>
            /// <param name="array">The array to copy to.</param>
            /// <param name="index">The starting index of the target array.</param>
            public void CopyTo(T[] array, int index)
            {
                Requires.NotNull(array, nameof(array));
                Requires.Range(index >= 0 && index + this.Count <= array.Length, nameof(index));
                Array.Copy(_elements, 0, array, index, this.Count);
            }
 
            /// <summary>
            /// Copies the contents of this array to the specified array.
            /// </summary>
            /// <param name="destination">The array to copy to.</param>
            public void CopyTo(T[] destination)
            {
                Requires.NotNull(destination, nameof(destination));
                Array.Copy(_elements, 0, destination, 0, this.Count);
            }
 
            /// <summary>
            /// Copies the contents of this array to the specified array.
            /// </summary>
            /// <param name="sourceIndex">The index into this collection of the first element to copy.</param>
            /// <param name="destination">The array to copy to.</param>
            /// <param name="destinationIndex">The index into the destination array to which the first copied element is written.</param>
            /// <param name="length">The number of elements to copy.</param>
            public void CopyTo(int sourceIndex, T[] destination, int destinationIndex, int length)
            {
                Requires.NotNull(destination, nameof(destination));
                Requires.Range(length >= 0, nameof(length));
                Requires.Range(sourceIndex >= 0 && sourceIndex + length <= this.Count, nameof(sourceIndex));
                Requires.Range(destinationIndex >= 0 && destinationIndex + length <= destination.Length, nameof(destinationIndex));
                Array.Copy(_elements, sourceIndex, destination, destinationIndex, length);
            }
 
            /// <summary>
            /// Resizes the array to accommodate the specified capacity requirement.
            /// </summary>
            /// <param name="capacity">The required capacity.</param>
            private void EnsureCapacity(int capacity)
            {
                if (_elements.Length < capacity)
                {
                    int newCapacity = Math.Max(_elements.Length * 2, capacity);
                    Array.Resize(ref _elements, newCapacity);
                }
            }
 
            /// <summary>
            /// Determines the index of a specific item in the <see cref="IList{T}"/>.
            /// </summary>
            /// <param name="item">The object to locate in the <see cref="IList{T}"/>.</param>
            /// <returns>
            /// The index of <paramref name="item"/> if found in the list; otherwise, -1.
            /// </returns>
            public int IndexOf(T item)
            {
                return this.IndexOf(item, 0, _count, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Searches the array for the specified item.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <param name="startIndex">The index at which to begin the search.</param>
            /// <returns>The 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int IndexOf(T item, int startIndex)
            {
                return this.IndexOf(item, startIndex, this.Count - startIndex, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Searches the array for the specified item.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <param name="startIndex">The index at which to begin the search.</param>
            /// <param name="count">The number of elements to search.</param>
            /// <returns>The 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int IndexOf(T item, int startIndex, int count)
            {
                return this.IndexOf(item, startIndex, count, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Searches the array for the specified item.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <param name="startIndex">The index at which to begin the search.</param>
            /// <param name="count">The number of elements 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 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int IndexOf(T item, int startIndex, int count, IEqualityComparer<T>? equalityComparer)
            {
                if (count == 0 && startIndex == 0)
                {
                    return -1;
                }
 
                Requires.Range(startIndex >= 0 && startIndex < this.Count, nameof(startIndex));
                Requires.Range(count >= 0 && startIndex + count <= this.Count, nameof(count));
 
                equalityComparer ??= EqualityComparer<T>.Default;
                if (equalityComparer == EqualityComparer<T>.Default)
                {
                    return Array.IndexOf(_elements, item, startIndex, count);
                }
                else
                {
                    for (int i = startIndex; i < startIndex + count; i++)
                    {
                        if (equalityComparer.Equals(_elements[i], item))
                        {
                            return i;
                        }
                    }
 
                    return -1;
                }
            }
 
            /// <summary>
            /// Searches the array for the specified item.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <param name="startIndex">The index at which to begin the 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 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int IndexOf(T item, int startIndex, IEqualityComparer<T>? equalityComparer)
            {
                return this.IndexOf(item, startIndex, this.Count - startIndex, equalityComparer);
            }
 
            /// <summary>
            /// Searches the array for the specified item in reverse.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <returns>The 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int LastIndexOf(T item)
            {
                if (this.Count == 0)
                {
                    return -1;
                }
 
                return this.LastIndexOf(item, this.Count - 1, this.Count, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Searches the array for the specified item in reverse.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <param name="startIndex">The index at which to begin the search.</param>
            /// <returns>The 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int LastIndexOf(T item, int startIndex)
            {
                if (this.Count == 0 && startIndex == 0)
                {
                    return -1;
                }
 
                Requires.Range(startIndex >= 0 && startIndex < this.Count, nameof(startIndex));
 
                return this.LastIndexOf(item, startIndex, startIndex + 1, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Searches the array for the specified item in reverse.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <param name="startIndex">The index at which to begin the search.</param>
            /// <param name="count">The number of elements to search.</param>
            /// <returns>The 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int LastIndexOf(T item, int startIndex, int count)
            {
                return this.LastIndexOf(item, startIndex, count, EqualityComparer<T>.Default);
            }
 
            /// <summary>
            /// Searches the array for the specified item in reverse.
            /// </summary>
            /// <param name="item">The item to search for.</param>
            /// <param name="startIndex">The index at which to begin the search.</param>
            /// <param name="count">The number of elements to search.</param>
            /// <param name="equalityComparer">The equality comparer to use in the search.</param>
            /// <returns>The 0-based index into the array where the item was found; or -1 if it could not be found.</returns>
            public int LastIndexOf(T item, int startIndex, int count, IEqualityComparer<T>? equalityComparer)
            {
                if (count == 0 && startIndex == 0)
                {
                    return -1;
                }
 
                Requires.Range(startIndex >= 0 && startIndex < this.Count, nameof(startIndex));
                Requires.Range(count >= 0 && startIndex - count + 1 >= 0, nameof(count));
 
                equalityComparer ??= EqualityComparer<T>.Default;
                if (equalityComparer == EqualityComparer<T>.Default)
                {
                    return Array.LastIndexOf(_elements, item, startIndex, count);
                }
                else
                {
                    for (int i = startIndex; i >= startIndex - count + 1; i--)
                    {
                        if (equalityComparer.Equals(item, _elements[i]))
                        {
                            return i;
                        }
                    }
 
                    return -1;
                }
            }
 
            /// <summary>
            /// Reverses the order of elements in the collection.
            /// </summary>
            public void Reverse()
            {
#if NET || NETSTANDARD2_1_OR_GREATER
                Array.Reverse<T>(_elements, 0, _count);
#else
                // The non-generic Array.Reverse is not used because it does not perform
                // well for non-primitive value types.
                int i = 0;
                int j = _count - 1;
                T[] array = _elements;
                while (i < j)
                {
                    T temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    i++;
                    j--;
                }
#endif
            }
 
            /// <summary>
            /// Sorts the array.
            /// </summary>
            public void Sort()
            {
                if (Count > 1)
                {
                    Array.Sort(_elements, 0, this.Count, Comparer<T>.Default);
                }
            }
 
            /// <summary>
            /// Sorts the elements in the entire array using
            /// the specified <see cref="Comparison{T}"/>.
            /// </summary>
            /// <param name="comparison">
            /// The <see cref="Comparison{T}"/> to use when comparing elements.
            /// </param>
            /// <exception cref="ArgumentNullException"><paramref name="comparison"/> is null.</exception>
            public void Sort(Comparison<T> comparison)
            {
                Requires.NotNull(comparison, nameof(comparison));
 
                if (Count > 1)
                {
#if NET
                    // MemoryExtensions.Sort is not available in .NET Framework / Standard 2.0.
                    // But the overload with a Comparison argument doesn't allocate.
                    _elements.AsSpan(0, _count).Sort(comparison);
#else
                    // Array.Sort does not have an overload that takes both bounds and a Comparison.
                    // We could special case _count == _elements.Length in order to try to avoid
                    // the IComparer allocation, but the Array.Sort overload that takes a Comparison
                    // allocates such an IComparer internally, anyway.
                    Array.Sort(_elements, 0, _count, Comparer<T>.Create(comparison));
#endif
                }
            }
 
            /// <summary>
            /// Sorts the array.
            /// </summary>
            /// <param name="comparer">The comparer to use in sorting. If <c>null</c>, the default comparer is used.</param>
            public void Sort(IComparer<T>? comparer)
            {
                if (Count > 1)
                {
                    Array.Sort(_elements, 0, _count, comparer);
                }
            }
 
            /// <summary>
            /// Sorts the array.
            /// </summary>
            /// <param name="index">The index of the first element to consider in the sort.</param>
            /// <param name="count">The number of elements to include in the sort.</param>
            /// <param name="comparer">The comparer to use in sorting. If <c>null</c>, the default comparer is used.</param>
            public void Sort(int index, int count, IComparer<T>? comparer)
            {
                // Don't rely on Array.Sort's argument validation since our internal array may exceed
                // the bounds of the publicly addressable region.
                Requires.Range(index >= 0, nameof(index));
                Requires.Range(count >= 0 && index + count <= this.Count, nameof(count));
 
                if (count > 1)
                {
                    Array.Sort(_elements, index, count, comparer);
                }
            }
 
            /// <summary>
            /// Copies the current contents to the specified <see cref="Span{T}"/>.
            /// </summary>
            /// <param name="destination">The <see cref="Span{T}"/> to copy to.</param>
            public void CopyTo(Span<T> destination)
            {
                Requires.Range(this.Count <= destination.Length, nameof(destination));
                new ReadOnlySpan<T>(_elements, 0, this.Count).CopyTo(destination);
            }
 
            /// <summary>
            /// Returns an enumerator for the contents of the array.
            /// </summary>
            /// <returns>An enumerator.</returns>
            public IEnumerator<T> GetEnumerator()
            {
                for (int i = 0; i < this.Count; i++)
                {
                    yield return this[i];
                }
            }
 
            /// <summary>
            /// Returns an enumerator for the contents of the array.
            /// </summary>
            /// <returns>An enumerator.</returns>
            IEnumerator<T> IEnumerable<T>.GetEnumerator()
            {
                return this.GetEnumerator();
            }
 
            /// <summary>
            /// Returns an enumerator for the contents of the array.
            /// </summary>
            /// <returns>An enumerator.</returns>
            IEnumerator IEnumerable.GetEnumerator()
            {
                return this.GetEnumerator();
            }
 
            /// <summary>
            /// Adds items to this collection.
            /// </summary>
            /// <typeparam name="TDerived">The type of source elements.</typeparam>
            /// <param name="items">The source array.</param>
            /// <param name="length">The number of elements to add to this array.</param>
            private void AddRange<TDerived>(TDerived[] items, int length) where TDerived : T
            {
                this.EnsureCapacity(this.Count + length);
 
                int offset = this.Count;
                this.Count += length;
 
                T[] nodes = _elements;
                for (int i = 0; i < length; i++)
                {
                    nodes[offset + i] = items[i];
                }
            }
 
            private void RemoveAtRange(ICollection<int> indicesToRemove)
            {
                Requires.NotNull(indicesToRemove, nameof(indicesToRemove));
 
                if (indicesToRemove.Count == 0)
                {
                    return;
                }
 
                int copied = 0;
                int removed = 0;
                int lastIndexRemoved = -1;
                foreach (int indexToRemove in indicesToRemove)
                {
                    Debug.Assert(lastIndexRemoved < indexToRemove);
                    int copyLength = lastIndexRemoved == -1 ? indexToRemove : (indexToRemove - lastIndexRemoved - 1);
                    Array.Copy(_elements, copied + removed, _elements, copied, copyLength);
                    removed++;
                    copied += copyLength;
                    lastIndexRemoved = indexToRemove;
                }
 
                Array.Copy(_elements, copied + removed, _elements, copied, _elements.Length - (copied + removed));
 
                _count -= indicesToRemove.Count;
            }
        }
    }
}