using System;
using System.Collections.Generic;
using System.Globalization;

namespace Amphora.PerformanceTests
{
    /// <summary>
    /// Stands for the scheduler's entry: a reference with an id to sort by.
    /// </summary>
    public sealed class IdNode
    {
        public int Id;
    }

    public sealed class ById : IComparer<IdNode>
    {
        public static readonly ById Instance = new ById();

        public int Compare(IdNode first, IdNode second)
        {
            return first.Id.CompareTo(second.Id);
        }
    }

    /// <summary>
    /// One way of putting a batch of nodes in id order, timed from the batch as the scheduler would gather it.
    /// </summary>
    public sealed class SortCandidate
    {
        public readonly string Name;
        public readonly Action<int[], IdNode[], int> Sort;

        /// <summary>
        /// Whether the candidate leaves the nodes where they were, so there is no order of them to check.
        /// </summary>
        public readonly bool LeavesNodes;

        public SortCandidate(string name, Action<int[], IdNode[], int> sort, bool leavesNodes = false)
        {
            Name = name;
            Sort = sort;
            LeavesNodes = leavesNodes;
        }
    }

    public static class ItemSorting
    {
        public static readonly int[] BatchSizes =
        {
            1, 2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 24, 28, 32, 40, 48, 64, 96, 128, 192, 256, 512, 1024, 4096, 16384,
        };

        /// <summary>
        /// The ids are out of a population this many times the batch, as when a tenth of the arcs wake.
        /// </summary>
        public const int PopulationPerItem = 10;

        public const int RunCount = 5;

        /// <summary>
        /// The candidate every other is measured against, which is framework code that doesn't change.
        /// </summary>
        public const int ControlIndex = 0;

        private static string Ratio(double control, double candidate)
        {
            return (control / candidate).ToString("0.00", CultureInfo.InvariantCulture) + "x";
        }

        public static List<SortCandidate> Candidates()
        {
            var order = new int[BatchSizes[BatchSizes.Length - 1]];
            return new List<SortCandidate>
            {
                new SortCandidate("comparer (control)",
                    (keys, nodes, count) => Array.Sort(nodes, 0, count, ById.Instance)),
                new SortCandidate("keyed", (keys, nodes, count) => Array.Sort(keys, nodes, 0, count)),
                new SortCandidate("Sort.Items", (keys, nodes, count) => Sort.Items(keys, nodes, count, order)),
                new SortCandidate("Sort.Order", (keys, nodes, count) => Sort.Order(keys, count, order),
                    leavesNodes: true),
                new SortCandidate("copy only", (keys, nodes, count) => { }),
            };
        }

        /// <summary>
        /// Ids in several ascending runs, which is what a frame's wake batch looks like when arcs fell asleep on
        /// different frames.
        /// </summary>
        public static int[] Runs(int count)
        {
            var returnMe = new int[count];
            int population = count * PopulationPerItem;
            int perRun = (count + RunCount - 1) / RunCount;
            for (int i = 0; i < count; ++i)
            {
                int run = i / perRun;
                int position = i % perRun;
                returnMe[i] = (int)((position * (long)population / perRun + run * 7) % population);
            }

            return returnMe;
        }

        /// <summary>
        /// Ids with no order at all.
        /// </summary>
        public static int[] Scattered(int count)
        {
            var returnMe = new int[count];
            int population = count * PopulationPerItem;
            for (int i = 0; i < count; ++i)
            {
                returnMe[i] = (int)(unchecked((uint)(i * 2654435761u)) % (uint)population);
            }

            return returnMe;
        }

        /// <summary>
        /// Ids already in order, as a frame's wake batch is when every arc waits the same time.
        /// </summary>
        public static int[] Ascending(int count)
        {
            var returnMe = new int[count];
            for (int i = 0; i < count; ++i)
            {
                returnMe[i] = i * PopulationPerItem;
            }

            return returnMe;
        }

        /// <summary>
        /// Ids in exactly the wrong order, which is the worst case for an insertion sort.
        /// </summary>
        public static int[] Descending(int count)
        {
            var returnMe = new int[count];
            for (int i = 0; i < count; ++i)
            {
                returnMe[i] = (count - i) * PopulationPerItem;
            }

            return returnMe;
        }

        public static void Run(string filter, int rounds)
        {
            // The last candidate only copies the batch in.  Every candidate pays for that, and at a handful of items
            // it is most of what is timed, so it is taken off before comparing.
            List<SortCandidate> candidates = Candidates();
            int copyOnlyIndex = candidates.Count - 1;
            Console.WriteLine("Sorting a batch of nodes by id, each starting from the same unsorted batch.  Every " +
                "candidate also copies the batch in, so the time of the copy-only candidate is taken off before " +
                "comparing.  Per candidate: the fastest nanoseconds a sort, warm, net of the copy, and the speedup " +
                "over the control, which is Array.Sort with a comparer.  Read the speedups, since they hold as the " +
                "machine gets busier or quieter.");
            foreach (var input in new (string Name, Func<int, int[]> Make)[]
            {
                ("runs", Runs),
                ("scattered", Scattered),
                ("ascending", Ascending),
                ("descending", Descending),
            })
            {
                Console.WriteLine();
                string header = $"{"batch (" + input.Name + ")",-20}";
                for (int c = 0; c < candidates.Count - 1; ++c)
                {
                    header += $" {candidates[c].Name,18}";
                }

                header += $" {"copy only ns",13}";
                Console.WriteLine(header);
                foreach (int size in BatchSizes)
                {
                    string name = $"{size} items, {input.Name}";
                    if (name.IndexOf(filter, StringComparison.OrdinalIgnoreCase) < 0)
                    {
                        continue;
                    }

                    int[] template = input.Make(size);
                    var templateNodes = new IdNode[size];
                    for (int i = 0; i < size; ++i)
                    {
                        templateNodes[i] = new IdNode { Id = template[i] };
                    }

                    var actions = new List<Action>();
                    var keyBuffers = new int[candidates.Count][];
                    var nodeBuffers = new IdNode[candidates.Count][];
                    for (int c = 0; c < candidates.Count; ++c)
                    {
                        keyBuffers[c] = new int[size];
                        nodeBuffers[c] = new IdNode[size];
                        int index = c;
                        actions.Add(() =>
                        {
                            Array.Copy(template, keyBuffers[index], size);
                            Array.Copy(templateNodes, nodeBuffers[index], size);
                            candidates[index].Sort(keyBuffers[index], nodeBuffers[index], size);
                        });
                    }

                    // Every candidate has to leave the same order, or its timing says nothing.
                    for (int c = 0; c < candidates.Count; ++c)
                    {
                        actions[c]();
                        if (c == copyOnlyIndex || candidates[c].LeavesNodes)
                        {
                            continue;
                        }

                        for (int i = 1; i < size; ++i)
                        {
                            if (nodeBuffers[c][i - 1].Id > nodeBuffers[c][i].Id)
                            {
                                throw new InvalidOperationException(candidates[c].Name + " left " + name +
                                    " out of order.");
                            }
                        }
                    }

                    Timing[] timings = Measurement.TimeTakingTurns(actions, rounds);
                    double copyNanoseconds = timings[copyOnlyIndex].MinimumNanoseconds;
                    double controlNet = Math.Max(1, timings[ControlIndex].MinimumNanoseconds - copyNanoseconds);
                    string row = $"{size,-20}";
                    for (int c = 0; c < candidates.Count; ++c)
                    {
                        if (c == copyOnlyIndex)
                        {
                            continue;
                        }

                        double net = Math.Max(1, timings[c].MinimumNanoseconds - copyNanoseconds);
                        row += $" {net,11:0} {Ratio(controlNet, net),6}";
                    }

                    row += $" {copyNanoseconds,13:0}";
                    Console.WriteLine(row);
                }
            }

            Console.WriteLine();
        }
    }
}