using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;

namespace ArrayAlgorithms
{
    public class Sort
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void Swap<T>(T[] array, int key1, int key2)
        {
            T tmp = array[key1];
            array[key1] = array[key2];
            array[key2] = tmp;
            //Swap(ref array[key1], ref array[key2]);
        }

        private static void HeapSort<T>(T[] array, int left, int right, IComparer<T> comparer)
        {
            int i;
            //Поднимаем выше элементы с большими значениями
            //В корне - макс. элемент
            for (i = left + (right - left) / 2; i >= left; --i)
                SiftDown(array, i, right, comparer);

            //Вытаскиваем максимум, помещаем в конец,
            //сокращаем правую границу на 1 и просеиваем кучу
            for (i = right; i > left; --i)
            {
                Swap(array, 0, i);
                SiftDown(array, 0, i - 1, comparer);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void SiftDown<T>(T[] array, int itemIndex, int right, IComparer<T> comparer)
        {
            while (itemIndex * 2 + 1 <= right)
            {
                int maxChild;
                if (itemIndex * 2 + 1 >= right || comparer.Compare(array[itemIndex * 2 + 1], array[itemIndex * 2 + 2]) > 0)// array[itemIndex * 2 + 1] > array[itemIndex * 2 + 2])
                    maxChild = itemIndex * 2 + 1;
                else
                    maxChild = itemIndex * 2 + 2;

                if (comparer.Compare(array[itemIndex], array[maxChild]) < 0)//  array[itemIndex] < array[maxChild])
                {
                    Swap(array, itemIndex, maxChild);
                    itemIndex = maxChild;
                }
                else break;
            }
        }

        private static int Partition<T>(T[] input, int left, int right, IComparer<T> comparer)
        {
            //int index = left + (right - left) / 2;
            //SwapIfGreater(input, Comparer<int>.Default, left, index);
            //SwapIfGreater(input, Comparer<int>.Default, left, right);
            //SwapIfGreater(input, Comparer<int>.Default, index, right);

            //int pivot = input[index];
            //Swap(input, index, right);
            //int i = left, j = right - 1;

            //for(;i< j;)
            //{
            //    do { }
            //    while (i<right-1&&input[i++] < pivot) ;
            //    do
            //    {
            //    }

            //    while (j>=left&&input[j--] >= pivot) ;
            //    if (i < j)
            //        Swap(input, i, j);
            //    else break;
            //}
            //if(i<right)
            //    Swap(input, i, right);
            //return i;

            var index = left + (right - left) / 2;
            SwapIfGreater(input, comparer, left, right);
            SwapIfGreater(input, comparer, left, index);
            SwapIfGreater(input, comparer, right, index);
            //В последний элемент блока записываем медиану первого, среднего и последнего
            var pivot = input[right];

            var i = left;
            for (var j = left; j < right; ++j)
            {
                if (comparer.Compare(input[j], pivot) <= 0)// <= pivot)
                    Swap(input, i++, j);
            }

            input[right] = input[i];
            input[i] = pivot;

            return i;
        }

        public static int IsSorted(int[] array)
        {
            for (var i = 0; i < array.Length - 1; ++i)
                if (array[i] > array[i + 1])
                    return i;
            return -1;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void SwapIfGreater<T>(T[] array, IComparer<T> comparer, int key1, int key2)
        {
            if (comparer.Compare(array[key1], array[key2]) > 0)
                Swap(array, key1, key2);
            //Swap(ref array[key1], ref array[key2]);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void InsertionSort<T>(T[] array, int l, int r, IComparer<T> comparer)
        {
            for (var i = l + 1; i <= r; ++i)
            {
                int j;
                var key = array[i];
                for (j = i; j > l && comparer.Compare(array[j - 1], key) > 0; --j)
                    array[j] = array[j - 1];
                array[j] = key;
            }
        }


        private static void QuickSort<T>(T[] input, int left, int right, IComparer<T> comparer, int depth = 32)
        {
            while (true)
            {
                var length = right - left + 1;
                if (length <= 16)
                {
                    switch (length)
                    {
                        case 1:
                            break;
                        case 2:
                            SwapIfGreater(input, comparer, left, right);
                            break;
                        case 3:
                            SwapIfGreater(input, comparer, left, right - 1);
                            SwapIfGreater(input, comparer, left, right);
                            SwapIfGreater(input, comparer, right - 1, right);
                            break;
                        default:
                            InsertionSort(input, left, right, comparer);
                            break;
                    }
                }
                else if (depth == 0)
                {
                    HeapSort(input, left, right, comparer);
                }
                else
                {
                    --depth;
                    var q = Partition(input, left, right, comparer);
                    QuickSort(input, left, q - 1, comparer, depth);
                    left = q + 1;
                    continue;
                }
                break;
            }
        }

        public static void QuickSort<T>(T[] array, IComparer<T> comparer)
        {
            QuickSort(array, 0, array.Length - 1, Comparer<T>.Default);
        }



        private static void HeapSort<T>(T[] array, int left, int right) where T :IComparable<T>
        {
            int i;
            //Поднимаем выше элементы с большими значениями
            //В корне - макс. элемент
            for (i = left + (right - left) / 2; i >= left; --i)
                SiftDown(array, i, right);

            //Вытаскиваем максимум, помещаем в конец,
            //сокращаем правую границу на 1 и просеиваем кучу
            for (i = right; i > left; --i)
            {
                Swap(array, 0, i);
                SiftDown(array, 0, i - 1);
            }
        }
        //[MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void SiftDown<T>(T[] array, int itemIndex, int right) where T :IComparable<T>
        {
            while (itemIndex * 2 + 1 <= right)
            {
                int maxChild;
                if (itemIndex * 2 + 1 >= right || array[itemIndex * 2 + 1].CompareTo(array[itemIndex * 2 + 2]) > 0)// array[itemIndex * 2 + 1] > array[itemIndex * 2 + 2])
                    maxChild = itemIndex * 2 + 1;
                else
                    maxChild = itemIndex * 2 + 2;

                if (array[itemIndex].CompareTo(array[maxChild]) < 0)//  array[itemIndex] < array[maxChild])
                {
                    Swap(array, itemIndex, maxChild);
                    itemIndex = maxChild;
                }
                else break;
            }
        }

        private static int Partition<T>(T[] input, int left, int right) where T :IComparable<T>
        {
            //int index = left + (right - left) / 2;
            //SwapIfGreater(input, Comparer<int>.Default, left, index);
            //SwapIfGreater(input, Comparer<int>.Default, left, right);
            //SwapIfGreater(input, Comparer<int>.Default, index, right);

            //int pivot = input[index];
            //Swap(input, index, right);
            //int i = left, j = right - 1;

            //for(;i< j;)
            //{
            //    do { }
            //    while (i<right-1&&input[i++] < pivot) ;
            //    do
            //    {
            //    }

            //    while (j>=left&&input[j--] >= pivot) ;
            //    if (i < j)
            //        Swap(input, i, j);
            //    else break;
            //}
            //if(i<right)
            //    Swap(input, i, right);
            //return i;

            var index = left + (right - left) / 2;
            SwapIfGreater(input, left, right);
            SwapIfGreater(input, left, index);
            SwapIfGreater(input, right, index);
            //В последний элемент блока записываем медиану первого, среднего и последнего
            var pivot = input[right];

            var i = left;
            for (var j = left; j < right; ++j)
            {
                if (input[j].CompareTo( pivot) <= 0)// <= pivot)
                    Swap(input, i++, j);
            }

            input[right] = input[i];
            input[i] = pivot;

            return i;
        }



        public static void TestSort(Action<int[]> sort, int size)
        {
            var array = new int[size];
            var rnd = new Random();
            for (var i = 0; i < size; ++i)
                array[i] = rnd.Next();
            var sw = new System.Diagnostics.Stopwatch();

            sw.Start();
            sort(array);
            sw.Stop();

            if (IsSorted(array) > 0)
                Console.WriteLine("Sorting failed!");
            Console.WriteLine("Random test " + size + " " + sort.Method + ": " + sw.ElapsedMilliseconds);

            for (var i = 0; i < size; ++i)
                array[i] = i + rnd.Next(50) * (rnd.Next(2) > 0 ? -1 : 1);
            sw.Restart();
            sort(array);
            sw.Stop();
            Console.WriteLine("Nearly sorted test " + size + " " + sort.Method + ": " + sw.ElapsedMilliseconds);

            for (var i = 0; i < size; ++i)
                array[i] = size - i;
            sw.Restart();
            sort(array);
            sw.Stop();
            Console.WriteLine("Reversed test " + size + " " + sort.Method + ": " + sw.ElapsedMilliseconds);


            var values = new int[100];
            for (int i = 0; i < 100; i++)
                values[i] = rnd.Next();

            for (var i = 0; i < size; ++i)
                array[i] = values[rnd.Next(100)];//rnd.Next((int)Math.Sqrt(size)/10);

            sw.Restart();
            sort(array);
            sw.Stop();
            Console.WriteLine("Few unique test " + size + " " + sort.Method + ": " + sw.ElapsedMilliseconds);

        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void SwapIfGreater<T>(T[] array,  int key1, int key2)where T :IComparable<T>
        {
            if (array[key1].CompareTo(array[key2]) > 0)
                Swap(array, key1, key2);
            //Swap(ref array[key1], ref array[key2]);
        }

        //[MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void InsertionSort<T>(T[] array, int l, int r)where T :IComparable<T>
        {
            for (var i = l + 1; i <= r; ++i)
            {
                int j;
                var key = array[i];
                for (j = i; j > l && array[j - 1].CompareTo(key) > 0; --j)
                    array[j] = array[j - 1];
                array[j] = key;
            }
        }


        private static void QuickSort<T>(T[] input, int left, int right, int depth = 32)where T :IComparable<T>
        {
            while (true)
            {
                var length = right - left + 1;
                if (length <= 16)
                {
                    switch (length)
                    {
                        case 1:
                            break;
                        case 2:
                            SwapIfGreater(input,  left, right);
                            break;
                        case 3:
                            SwapIfGreater(input,  left, right - 1);
                            SwapIfGreater(input,  left, right);
                            SwapIfGreater(input,  right - 1, right);
                            break;
                        default:
                            InsertionSort(input, left, right);
                            break;
                    }
                }
                else if (depth == 0)
                {
                    HeapSort(input, left, right);
                }
                else
                {
                    --depth;
                    var q = Partition(input, left, right);
                    QuickSort(input, left, q - 1, depth);
                    left = q + 1;
                    continue;
                }
                break;
            }
        }

        public static void QuickSort<T>(T[] array) where T :IComparable<T>
        {

            //if(typeof(T).IsPrimitive)
            //{

            //    //NativeMethods.CppSort.CppQuickSort(array, 0, array.Length - 1);
            //}
            //else
            QuickSort(array, 0, array.Length - 1);// Comparer<T>.Default);

        }



    }
}