// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using System.Diagnostics;

namespace Roslyn.Utilities
{
    internal static class ArrayExtensions
    {
        internal static T[] Copy<T>(this T[] array, int start, int length)
        {
            // It's ok for 'start' to equal 'array.Length'.  In that case you'll
            // just get an empty array back.
            Debug.Assert(start >= 0);
            Debug.Assert(start <= array.Length);

            if (start + length > array.Length)
            {
                length = array.Length - start;
            }

            T[] newArray = new T[length];
            Array.Copy(array, start, newArray, 0, length);
            return newArray;
        }

        internal static T[] InsertAt<T>(this T[] array, int position, T item)
        {
            T[] newArray = new T[array.Length + 1];
            if (position > 0)
            {
                Array.Copy(array, newArray, position);
            }

            if (position < array.Length)
            {
                Array.Copy(array, position, newArray, position + 1, array.Length - position);
            }

            newArray[position] = item;
            return newArray;
        }

        internal static T[] Append<T>(this T[] array, T item)
        {
            return InsertAt(array, array.Length, item);
        }

        internal static T[] InsertAt<T>(this T[] array, int position, T[] items)
        {
            T[] newArray = new T[array.Length + items.Length];
            if (position > 0)
            {
                Array.Copy(array, newArray, position);
            }

            if (position < array.Length)
            {
                Array.Copy(array, position, newArray, position + items.Length, array.Length - position);
            }

            items.CopyTo(newArray, position);
            return newArray;
        }

        internal static T[] Append<T>(this T[] array, T[] items)
        {
            return InsertAt(array, array.Length, items);
        }

        internal static T[] RemoveAt<T>(this T[] array, int position)
        {
            return RemoveAt(array, position, 1);
        }

        internal static T[] RemoveAt<T>(this T[] array, int position, int length)
        {
            if (position + length > array.Length)
            {
                length = array.Length - position;
            }

            T[] newArray = new T[array.Length - length];
            if (position > 0)
            {
                Array.Copy(array, newArray, position);
            }

            if (position < newArray.Length)
            {
                Array.Copy(array, position + length, newArray, position, newArray.Length - position);
            }

            return newArray;
        }

        internal static T[] ReplaceAt<T>(this T[] array, int position, T item)
        {
            T[] newArray = new T[array.Length];
            Array.Copy(array, newArray, array.Length);
            newArray[position] = item;
            return newArray;
        }

        internal static T[] ReplaceAt<T>(this T[] array, int position, int length, T[] items)
        {
            return InsertAt(RemoveAt(array, position, length), position, items);
        }

        internal static void ReverseContents<T>(this T[] array)
        {
            ReverseContents(array, 0, array.Length);
        }

        internal static void ReverseContents<T>(this T[] array, int start, int count)
        {
            int end = start + count - 1;
            for (int i = start, j = end; i < j; i++, j--)
            {
                T tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        // same as Array.BinarySearch, but without using IComparer to compare ints
        internal static int BinarySearch(this int[] array, int value)
        {
            var low = 0;
            var high = array.Length - 1;

            while (low <= high)
            {
                var middle = low + ((high - low) >> 1);
                var midValue = array[middle];

                if (midValue == value)
                {
                    return middle;
                }
                else if (midValue > value)
                {
                    high = middle - 1;
                }
                else
                {
                    low = middle + 1;
                }
            }

            return ~low;
        }

        public static bool SequenceEqual<T>(this T[]? first, T[]? second, Func<T, T, bool> comparer)
        {
            RoslynDebug.Assert(comparer != null);

            if (first == second)
            {
                return true;
            }

            if (first == null || second == null || first.Length != second.Length)
            {
                return false;
            }

            for (var i = 0; i < first.Length; i++)
            {
                if (!comparer(first[i], second[i]))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Search a sorted integer array for the target value in O(log N) time.
        /// </summary>
        /// <param name="array">The array of integers which must be sorted in ascending order.</param>
        /// <param name="value">The target value.</param>
        /// <returns>An index in the array pointing to the position where <paramref name="value"/> should be
        /// inserted in order to maintain the sorted order. All values to the right of this position will be
        /// strictly greater than <paramref name="value"/>. Note that this may return a position off the end
        /// of the array if all elements are less than or equal to <paramref name="value"/>.</returns>
        internal static int BinarySearchUpperBound(this int[] array, int value)
        {
            int low = 0;
            int high = array.Length - 1;

            while (low <= high)
            {
                int middle = low + ((high - low) >> 1);
                if (array[middle] > value)
                {
                    high = middle - 1;
                }
                else
                {
                    low = middle + 1;
                }
            }

            return low;
        }
    }
}