ImmutableArray.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.Linq;

namespace System.Collections.Immutable
{
    /// <summary>
    /// A set of initialization methods for instances of <see cref="ImmutableArray{T}"/>.
    /// </summary>
    public static class ImmutableArray
    {
        /// <summary>
        /// A two element array useful for throwing exceptions the way LINQ does.
        /// </summary>
        internal static readonly byte[] TwoElementArray = new byte[2];

        /// <summary>
        /// Creates an empty <see cref="ImmutableArray{T}"/>.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <returns>An empty array.</returns>
        public static ImmutableArray<T> Create<T>()
        {
            return ImmutableArray<T>.Empty;
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> with the specified element as its only member.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="item">The element to store in the array.</param>
        /// <returns>A 1-element immutable array containing the specified item.</returns>
        public static ImmutableArray<T> Create<T>(T item)
        {
            T[] array = new[] { item };
            return new ImmutableArray<T>(array);
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> with the specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="item1">The first element to store in the array.</param>
        /// <param name="item2">The second element to store in the array.</param>
        /// <returns>A 2-element immutable array containing the specified items.</returns>
        public static ImmutableArray<T> Create<T>(T item1, T item2)
        {
            T[] array = new[] { item1, item2 };
            return new ImmutableArray<T>(array);
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> with the specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="item1">The first element to store in the array.</param>
        /// <param name="item2">The second element to store in the array.</param>
        /// <param name="item3">The third element to store in the array.</param>
        /// <returns>A 3-element immutable array containing the specified items.</returns>
        public static ImmutableArray<T> Create<T>(T item1, T item2, T item3)
        {
            T[] array = new[] { item1, item2, item3 };
            return new ImmutableArray<T>(array);
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> with the specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="item1">The first element to store in the array.</param>
        /// <param name="item2">The second element to store in the array.</param>
        /// <param name="item3">The third element to store in the array.</param>
        /// <param name="item4">The fourth element to store in the array.</param>
        /// <returns>A 4-element immutable array containing the specified items.</returns>
        public static ImmutableArray<T> Create<T>(T item1, T item2, T item3, T item4)
        {
            T[] array = new[] { item1, item2, item3, item4 };
            return new ImmutableArray<T>(array);
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> with the specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="items">The elements to store in the array.</param>
        /// <returns>An immutable array containing the specified items.</returns>
        public static ImmutableArray<T> Create<T>(ReadOnlySpan<T> items)
        {
            if (items.IsEmpty)
            {
                return ImmutableArray<T>.Empty;
            }

            T[] array = items.ToArray();
            return new ImmutableArray<T>(array);
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> with the specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="items">The elements to store in the array.</param>
        /// <returns>An immutable array containing the specified items.</returns>
        public static ImmutableArray<T> Create<T>(Span<T> items)
        {
            return Create((ReadOnlySpan<T>)items);
        }

        /// <summary>
        /// Produce an immutable array of contents from specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element in the list.</typeparam>
        /// <param name="items">The elements to store in the array.</param>
        /// <returns>An immutable array containing the specified items.</returns>
        public static ImmutableArray<T> ToImmutableArray<T>(this ReadOnlySpan<T> items)
        {
            return Create(items);
        }

        /// <summary>
        /// Produce an immutable array of contents from specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element in the list.</typeparam>
        /// <param name="items">The elements to store in the array.</param>
        /// <returns>An immutable array containing the specified items.</returns>
        public static ImmutableArray<T> ToImmutableArray<T>(this Span<T> items)
        {
            return Create((ReadOnlySpan<T>)items);
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> populated with the contents of the specified sequence.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="items">The elements to store in the array.</param>
        /// <returns>An immutable array.</returns>
        public static ImmutableArray<T> CreateRange<T>(IEnumerable<T> items)
        {
            Requires.NotNull(items, nameof(items));

            // As an optimization, if the provided enumerable is actually a
            // boxed ImmutableArray<T> instance, reuse the underlying array if possible.
            // Note that this allows for automatic upcasting and downcasting of arrays
            // where the CLR allows it.
            if (items is IImmutableArray immutableArray)
            {
                Array? array = immutableArray.Array;
                if (array == null)
                {
                    throw new InvalidOperationException(SR.InvalidOperationOnDefaultArray);
                }

                // `array` must not be null at this point, and we know it's an
                // ImmutableArray<T> or ImmutableArray<SomethingDerivedFromT> as they are
                // the only types that could be both IEnumerable<T> and IImmutableArray.
                // As such, we know that items is either an ImmutableArray<T> or
                // ImmutableArray<TypeDerivedFromT>, and we can cast the array to T[].
                return new ImmutableArray<T>((T[])array);
            }

            // We don't recognize the source as an array that is safe to use.
            // So clone the sequence into an array and return an immutable wrapper.
            int count;
            if (items.TryGetCount(out count))
            {
                // We know how long the sequence is. Linq's built-in ToArray extension method
                // isn't as comprehensive in finding the length as we are, so call our own method
                // to avoid reallocating arrays as the sequence is enumerated.
                return new ImmutableArray<T>(items.ToArray(count));
            }
            else
            {
                return new ImmutableArray<T>(items.ToArray());
            }
        }

        /// <summary>
        /// Creates an <see cref="ImmutableArray{T}"/> with the specified elements.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="items">The elements to store in the array.</param>
        /// <returns>An immutable array containing the specified items.</returns>
        public static ImmutableArray<T> Create<T>(params T[]? items)
        {
            if (items == null || items.Length == 0)
            {
                return ImmutableArray<T>.Empty;
            }

            // We can't trust that the array passed in will never be mutated by the caller.
            // The caller may have passed in an array explicitly (not relying on compiler params keyword)
            // and could then change the array after the call, thereby violating the immutable
            // guarantee provided by this struct. So we always copy the array to ensure it won't ever change.
            var tmp = new T[items.Length];
            Array.Copy(items, tmp, items.Length);
            return new ImmutableArray<T>(tmp);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}"/> struct.
        /// </summary>
        /// <param name="items">The array to initialize the array with. A defensive copy is made.</param>
        /// <param name="start">The index of the first element in the source array to include in the resulting array.</param>
        /// <param name="length">The number of elements from the source array to include in the resulting array.</param>
        /// <remarks>
        /// This overload allows helper methods or custom builder classes to efficiently avoid paying a redundant
        /// tax for copying an array when the new array is a segment of an existing array.
        /// </remarks>
        public static ImmutableArray<T> Create<T>(T[] items, int start, int length)
        {
            Requires.NotNull(items, nameof(items));
            Requires.Range(start >= 0 && start <= items.Length, nameof(start));
            Requires.Range(length >= 0 && start + length <= items.Length, nameof(length));

            if (length == 0)
            {
                // Avoid allocating an array.
                return Create<T>();
            }

            var array = new T[length];
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = items[start + i];
            }

            return new ImmutableArray<T>(array);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}"/> struct.
        /// </summary>
        /// <param name="items">The array to initialize the array with.
        /// The selected array segment may be copied into a new array.</param>
        /// <param name="start">The index of the first element in the source array to include in the resulting array.</param>
        /// <param name="length">The number of elements from the source array to include in the resulting array.</param>
        /// <remarks>
        /// This overload allows helper methods or custom builder classes to efficiently avoid paying a redundant
        /// tax for copying an array when the new array is a segment of an existing array.
        /// </remarks>
        public static ImmutableArray<T> Create<T>(ImmutableArray<T> items, int start, int length)
        {
            Requires.Range(start >= 0 && start <= items.Length, nameof(start));
            Requires.Range(length >= 0 && start + length <= items.Length, nameof(length));

            if (length == 0)
            {
                return Create<T>();
            }

            if (start == 0 && length == items.Length)
            {
                return items;
            }

            var array = new T[length];
            Array.Copy(items.array!, start, array, 0, length);
            return new ImmutableArray<T>(array);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}"/> struct.
        /// </summary>
        /// <param name="items">The source array to initialize the resulting array with.</param>
        /// <param name="selector">The function to apply to each element from the source array.</param>
        /// <remarks>
        /// This overload allows efficient creation of an <see cref="ImmutableArray{T}"/> based on an existing
        /// <see cref="ImmutableArray{T}"/>, where a mapping function needs to be applied to each element from
        /// the source array.
        /// </remarks>
        public static ImmutableArray<TResult> CreateRange<TSource, TResult>(ImmutableArray<TSource> items, Func<TSource, TResult> selector)
        {
            Requires.NotNull(selector, nameof(selector));

            int length = items.Length;

            if (length == 0)
            {
                return Create<TResult>();
            }

            var array = new TResult[length];
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = selector(items[i]);
            }

            return new ImmutableArray<TResult>(array);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}"/> struct.
        /// </summary>
        /// <param name="items">The source array to initialize the resulting array with.</param>
        /// <param name="start">The index of the first element in the source array to include in the resulting array.</param>
        /// <param name="length">The number of elements from the source array to include in the resulting array.</param>
        /// <param name="selector">The function to apply to each element from the source array included in the resulting array.</param>
        /// <remarks>
        /// This overload allows efficient creation of an <see cref="ImmutableArray{T}"/> based on a slice of an existing
        /// <see cref="ImmutableArray{T}"/>, where a mapping function needs to be applied to each element from the source array
        /// included in the resulting array.
        /// </remarks>
        public static ImmutableArray<TResult> CreateRange<TSource, TResult>(ImmutableArray<TSource> items, int start, int length, Func<TSource, TResult> selector)
        {
            int itemsLength = items.Length;

            Requires.Range(start >= 0 && start <= itemsLength, nameof(start));
            Requires.Range(length >= 0 && start + length <= itemsLength, nameof(length));
            Requires.NotNull(selector, nameof(selector));

            if (length == 0)
            {
                return Create<TResult>();
            }

            var array = new TResult[length];
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = selector(items[i + start]);
            }

            return new ImmutableArray<TResult>(array);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}"/> struct.
        /// </summary>
        /// <param name="items">The source array to initialize the resulting array with.</param>
        /// <param name="selector">The function to apply to each element from the source array.</param>
        /// <param name="arg">An argument to be passed to the selector mapping function.</param>
        /// <remarks>
        /// This overload allows efficient creation of an <see cref="ImmutableArray{T}"/> based on an existing
        /// <see cref="ImmutableArray{T}"/>, where a mapping function needs to be applied to each element from
        /// the source array.
        /// </remarks>
        public static ImmutableArray<TResult> CreateRange<TSource, TArg, TResult>(ImmutableArray<TSource> items, Func<TSource, TArg, TResult> selector, TArg arg)
        {
            Requires.NotNull(selector, nameof(selector));

            int length = items.Length;

            if (length == 0)
            {
                return Create<TResult>();
            }

            var array = new TResult[length];
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = selector(items[i], arg);
            }

            return new ImmutableArray<TResult>(array);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}"/> struct.
        /// </summary>
        /// <param name="items">The source array to initialize the resulting array with.</param>
        /// <param name="start">The index of the first element in the source array to include in the resulting array.</param>
        /// <param name="length">The number of elements from the source array to include in the resulting array.</param>
        /// <param name="selector">The function to apply to each element from the source array included in the resulting array.</param>
        /// <param name="arg">An argument to be passed to the selector mapping function.</param>
        /// <remarks>
        /// This overload allows efficient creation of an <see cref="ImmutableArray{T}"/> based on a slice of an existing
        /// <see cref="ImmutableArray{T}"/>, where a mapping function needs to be applied to each element from the source array
        /// included in the resulting array.
        /// </remarks>
        public static ImmutableArray<TResult> CreateRange<TSource, TArg, TResult>(ImmutableArray<TSource> items, int start, int length, Func<TSource, TArg, TResult> selector, TArg arg)
        {
            int itemsLength = items.Length;

            Requires.Range(start >= 0 && start <= itemsLength, nameof(start));
            Requires.Range(length >= 0 && start + length <= itemsLength, nameof(length));
            Requires.NotNull(selector, nameof(selector));

            if (length == 0)
            {
                return Create<TResult>();
            }

            var array = new TResult[length];
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = selector(items[i + start], arg);
            }

            return new ImmutableArray<TResult>(array);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}.Builder"/> class.
        /// </summary>
        /// <typeparam name="T">The type of elements stored in the array.</typeparam>
        /// <returns>A new builder.</returns>
        public static ImmutableArray<T>.Builder CreateBuilder<T>()
        {
            return Create<T>().ToBuilder();
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ImmutableArray{T}.Builder"/> class.
        /// </summary>
        /// <typeparam name="T">The type of elements stored in the array.</typeparam>
        /// <param name="initialCapacity">The size of the initial array backing the builder.</param>
        /// <returns>A new builder.</returns>
        public static ImmutableArray<T>.Builder CreateBuilder<T>(int initialCapacity)
        {
            return new ImmutableArray<T>.Builder(initialCapacity);
        }

        /// <summary>
        /// Enumerates a sequence exactly once and produces an immutable array of its contents.
        /// </summary>
        /// <typeparam name="TSource">The type of element in the sequence.</typeparam>
        /// <param name="items">The sequence to enumerate.</param>
        /// <returns>An immutable array containing the specified items.</returns>
        public static ImmutableArray<TSource> ToImmutableArray<TSource>(this IEnumerable<TSource> items)
        {
            if (items is ImmutableArray<TSource>)
            {
                return (ImmutableArray<TSource>)items;
            }

            return CreateRange(items);
        }

        /// <summary>
        /// Returns an immutable copy of the current contents of the builder's collection.
        /// </summary>
        /// <param name="builder">The builder to create the immutable array from.</param>
        /// <returns>An immutable array containing the specified items from <paramref name="builder"/>.</returns>
        public static ImmutableArray<TSource> ToImmutableArray<TSource>(this ImmutableArray<TSource>.Builder builder)
        {
            Requires.NotNull(builder, nameof(builder));

            return builder.ToImmutable();
        }

        /// <summary>
        /// Searches an entire one-dimensional sorted <see cref="ImmutableArray{T}"/> for a specific element,
        /// using the <see cref="IComparable{T}"/> generic interface implemented by each element
        /// of the <see cref="ImmutableArray{T}"/> and by the specified object.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="array">The sorted, one-dimensional array to search.</param>
        /// <param name="value">The object to search for.</param>
        /// <returns>
        /// The index of the specified <paramref name="value"/> in the specified array, if <paramref name="value"/> is found.
        /// If <paramref name="value"/> is not found and <paramref name="value"/> is less than one or more elements in array,
        /// a negative number which is the bitwise complement of the index of the first
        /// element that is larger than <paramref name="value"/>. If <paramref name="value"/> is not found and <paramref name="value"/> is greater
        /// than any of the elements in array, a negative number which is the bitwise
        /// complement of (the index of the last element plus 1).
        /// </returns>
        /// <exception cref="InvalidOperationException">
        /// <paramref name="value"/> does not implement the <see cref="IComparable{T}"/> generic interface, and
        /// the search encounters an element that does not implement the <see cref="IComparable{T}"/>
        /// generic interface.
        /// </exception>
        public static int BinarySearch<T>(this ImmutableArray<T> array, T value)
        {
            return Array.BinarySearch<T>(array.array!, value);
        }

        /// <summary>
        /// Searches an entire one-dimensional sorted <see cref="ImmutableArray{T}"/> for a value using
        /// the specified <see cref="IComparer{T}"/> generic interface.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="array">The sorted, one-dimensional array to search.</param>
        /// <param name="value">The object to search for.</param>
        /// <param name="comparer">
        /// The <see cref="IComparer{T}"/> implementation to use when comparing
        /// elements; or null to use the <see cref="IComparable{T}"/> implementation of each
        /// element.
        /// </param>
        /// <returns>
        /// The index of the specified <paramref name="value"/> in the specified array, if <paramref name="value"/> is found.
        /// If <paramref name="value"/> is not found and <paramref name="value"/> is less than one or more elements in array,
        /// a negative number which is the bitwise complement of the index of the first
        /// element that is larger than <paramref name="value"/>. If <paramref name="value"/> is not found and <paramref name="value"/> is greater
        /// than any of the elements in array, a negative number which is the bitwise
        /// complement of (the index of the last element plus 1).
        /// </returns>
        /// <exception cref="InvalidOperationException">
        /// <paramref name="comparer"/> is null, <paramref name="value"/> does not implement the <see cref="IComparable{T}"/> generic interface, and
        /// the search encounters an element that does not implement the <see cref="IComparable{T}"/>
        /// generic interface.
        /// </exception>
        public static int BinarySearch<T>(this ImmutableArray<T> array, T value, IComparer<T>? comparer)
        {
            return Array.BinarySearch<T>(array.array!, value, comparer);
        }

        /// <summary>
        /// Searches a range of elements in a one-dimensional sorted <see cref="ImmutableArray{T}"/> for
        /// a value, using the <see cref="IComparable{T}"/> generic interface implemented by
        /// each element of the <see cref="ImmutableArray{T}"/> and by the specified value.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="array">The sorted, one-dimensional array to search.</param>
        /// <param name="index">The starting index of the range to search.</param>
        /// <param name="length">The length of the range to search.</param>
        /// <param name="value">The object to search for.</param>
        /// <returns>
        /// The index of the specified <paramref name="value"/> in the specified <paramref name="array"/>, if <paramref name="value"/> is found.
        /// If <paramref name="value"/> is not found and <paramref name="value"/> is less than one or more elements in <paramref name="array"/>,
        /// a negative number which is the bitwise complement of the index of the first
        /// element that is larger than <paramref name="value"/>. If <paramref name="value"/> is not found and <paramref name="value"/> is greater
        /// than any of the elements in <paramref name="array"/>, a negative number which is the bitwise
        /// complement of (the index of the last element plus 1).
        /// </returns>
        /// <exception cref="InvalidOperationException">
        /// <paramref name="value"/> does not implement the <see cref="IComparable{T}"/> generic interface, and
        /// the search encounters an element that does not implement the <see cref="IComparable{T}"/>
        /// generic interface.
        /// </exception>
        /// <exception cref="ArgumentException">
        /// <paramref name="index"/> and <paramref name="length"/> do not specify a valid range in <paramref name="array"/>.
        /// </exception>
        /// <exception cref="ArgumentOutOfRangeException">
        /// <paramref name="index"/> is less than the lower bound of <paramref name="array"/>. -or- <paramref name="length"/> is less than zero.
        /// </exception>
        public static int BinarySearch<T>(this ImmutableArray<T> array, int index, int length, T value)
        {
            return Array.BinarySearch<T>(array.array!, index, length, value);
        }

        /// <summary>
        /// Searches a range of elements in a one-dimensional sorted <see cref="ImmutableArray{T}"/> for
        /// a value, using the specified <see cref="IComparer{T}"/> generic
        /// interface.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the array.</typeparam>
        /// <param name="array">The sorted, one-dimensional array to search.</param>
        /// <param name="index">The starting index of the range to search.</param>
        /// <param name="length">The length of the range to search.</param>
        /// <param name="value">The object to search for.</param>
        /// <param name="comparer">
        /// The <see cref="IComparer{T}"/> implementation to use when comparing
        /// elements; or null to use the <see cref="IComparable{T}"/> implementation of each
        /// element.
        /// </param>
        /// <returns>
        /// The index of the specified <paramref name="value"/> in the specified <paramref name="array"/>, if <paramref name="value"/> is found.
        /// If <paramref name="value"/> is not found and <paramref name="value"/> is less than one or more elements in <paramref name="array"/>,
        /// a negative number which is the bitwise complement of the index of the first
        /// element that is larger than <paramref name="value"/>. If <paramref name="value"/> is not found and <paramref name="value"/> is greater
        /// than any of the elements in <paramref name="array"/>, a negative number which is the bitwise
        /// complement of (the index of the last element plus 1).
        /// </returns>
        /// <exception cref="InvalidOperationException">
        /// <paramref name="comparer"/> is null, <paramref name="value"/> does not implement the <see cref="IComparable{T}"/> generic
        /// interface, and the search encounters an element that does not implement the
        /// <see cref="IComparable{T}"/> generic interface.
        /// </exception>
        /// <exception cref="ArgumentException">
        /// <paramref name="index"/> and <paramref name="length"/> do not specify a valid range in <paramref name="array"/>.-or-<paramref name="comparer"/> is null,
        /// and <paramref name="value"/> is of a type that is not compatible with the elements of <paramref name="array"/>.
        /// </exception>
        /// <exception cref="ArgumentOutOfRangeException">
        /// <paramref name="index"/> is less than the lower bound of <paramref name="array"/>. -or- <paramref name="length"/> is less than zero.
        /// </exception>
        public static int BinarySearch<T>(this ImmutableArray<T> array, int index, int length, T value, IComparer<T>? comparer)
        {
            return Array.BinarySearch<T>(array.array!, index, length, value, comparer);
        }
    }
}