using System;
using System.Collections.Generic;

namespace Amphora.RandomComparisons
{
    /// <summary>
    /// Checks the shape of the draws games build on a generator: event times and counts, bell curves, points in a
    /// circle, dice and picks.  Each is compared with its exact distribution.  Most are also run against a tempting
    /// wrong way of making the same draw, which must fail.
    /// </summary>
    public static class DistributionChecks
    {
        public const int Parts = 256;
        public const int PolarSide = 16;
        public const double TwoPi = 2 * Math.PI;

        private static NamedOutcome Expecting(NamedOutcome outcome, bool expectsFailure)
        {
            return new NamedOutcome(outcome.Name, outcome.Outcome, expectsFailure);
        }

        private static int PartOf(double fraction, int parts)
        {
            int part = (int)(fraction * parts);
            if (part < 0)
            {
                return 0;
            }

            return part >= parts ? parts - 1 : part;
        }

        /// <summary>
        /// Passes each draw through the curve's cumulative distribution, which makes a fair draw uniform, and tests the
        /// result for being uniform.
        /// </summary>
        private static NamedOutcome Shape(string name, long draws, Func<double> draw, Func<double, double> cumulative,
            bool expectsFailure = false)
        {
            var counts = new int[Parts];
            for (long i = 0; i < draws; i++)
            {
                counts[PartOf(cumulative(draw()), Parts)]++;
            }

            return Expecting(BoundedChecks.Uniform(name, counts, draws), expectsFailure);
        }

        private static NamedOutcome Categories(string name, double[] observed, double[] probabilities, long draws,
            bool expectsFailure = false)
        {
            var expected = new double[probabilities.Length];
            for (int i = 0; i < expected.Length; i++)
            {
                expected[i] = probabilities[i] * draws;
            }

            double statistic;
            double degrees = Stats.ChiSquareOfCategories(observed, expected, minimumExpected: 5, out statistic);
            string detail = (degrees + 1) + " categories, chi-square " + statistic.ToString("0.0");
            return new NamedOutcome(name, new Outcome(Stats.ChiSquareTwoSided(statistic, degrees), detail),
                expectsFailure);
        }

        private static NamedOutcome StaysIn(string name, long outside, string where)
        {
            return new NamedOutcome(name + " stays in its range",
                new Outcome(outside == 0 ? 1 : 0, outside + " draws outside " + where));
        }

        private static NamedOutcome CountsOf(string name, long draws, double lambda, Func<int> sample,
            bool expectsFailure = false)
        {
            int categories = (int)(lambda + 12 * Math.Sqrt(lambda) + 20);
            double[] probabilities = Stats.PoissonProbabilities(lambda, categories);
            double tail = 1;
            for (int i = 0; i < categories - 1; i++)
            {
                tail -= probabilities[i];
            }

            probabilities[categories - 1] = Math.Max(0, tail);
            var observed = new double[categories];
            for (long i = 0; i < draws; i++)
            {
                observed[Math.Min(sample(), categories - 1)]++;
            }

            return Categories(name, observed, probabilities, draws, expectsFailure);
        }

        private static void Events<GeneratorType>(RandOf<GeneratorType> rand, long draws, List<NamedOutcome> into)
            where GeneratorType : struct, IRandomGenerator
        {
            const double mean = 10;
            Func<double, double> exponential = value => -Math.Exp(-value / mean) + 1;
            into.Add(Shape("NextEvent(10)", draws, () => rand.NextEvent(mean), exponential));
            into.Add(Shape("uniform from 0 to twice the mean instead", draws, () => rand.NextDouble() * 2 * mean,
                exponential, expectsFailure: true));

            double[] means = { 10, 1000000, 0.1 };
            double[] spans = { 15, 1, 1 };
            foreach (int index in new[] { 0, 1, 2 })
            {
                double eventMean = means[index];
                double span = spans[index];
                Func<double, double> truncated = value =>
                    (1 - Math.Exp(-value / eventMean)) / (1 - Math.Exp(-span / eventMean));
                string name = "NextEventWithin(" + eventMean + ", " + span + ")";
                long outside = 0;
                into.Add(Shape(name, draws, () =>
                {
                    double time = rand.NextEventWithin(eventMean, span);
                    if (time < 0 || time >= span)
                    {
                        outside++;
                    }

                    return time;
                }, truncated));
                into.Add(StaysIn(name, outside, "[0, " + span + ")"));
                if (index == 0)
                {
                    into.Add(Shape("uniform over the span instead", draws, () => rand.NextDouble() * span, truncated,
                        expectsFailure: true));
                }
            }
        }

        private static void EventLists<GeneratorType>(RandOf<GeneratorType> rand, long draws, List<NamedOutcome> into)
            where GeneratorType : struct, IRandomGenerator
        {
            const double span = 8;
            const int count = 5;
            long calls = draws / count;
            var times = new List<double>();
            var pooled = new int[Parts];
            var firsts = new int[Parts];
            var lasts = new int[Parts];
            var unspared = new int[Parts];
            var unsparedLasts = new int[Parts];
            long outside = 0;
            for (long call = 0; call < calls; call++)
            {
                times.Clear();
                rand.NextEventsWithin(span, count, times);
                for (int i = 0; i < count; i++)
                {
                    if (times[i] < 0 || times[i] >= span || (i > 0 && times[i] < times[i - 1]))
                    {
                        outside++;
                    }

                    pooled[PartOf(times[i] / span, Parts)]++;
                }

                // The smallest of five even draws falls below t with chance 1 - (1 - t/span)^5, the largest with chance
                // (t/span)^5.
                firsts[PartOf(1 - Math.Pow(1 - times[0] / span, count), Parts)]++;
                lasts[PartOf(Math.Pow(times[count - 1] / span, count), Parts)]++;

                // The tempting mistake: five gaps scaled so the fifth event is at the span, with no gap after it.
                double total = 0;
                var running = new double[count];
                for (int i = 0; i < count; i++)
                {
                    total += rand.NextEvent(1.0);
                    running[i] = total;
                }

                for (int i = 0; i < count; i++)
                {
                    unspared[PartOf(running[i] / total, Parts)]++;
                }

                unsparedLasts[PartOf(Math.Pow(running[count - 1] / total, count), Parts)]++;
            }

            long positions = calls * count;
            into.Add(BoundedChecks.Uniform("NextEventsWithin(8, 5), all times", pooled, positions));
            into.Add(BoundedChecks.Uniform("NextEventsWithin(8, 5), earliest", firsts, calls));
            into.Add(BoundedChecks.Uniform("NextEventsWithin(8, 5), latest", lasts, calls));
            into.Add(StaysIn("NextEventsWithin(8, 5)", outside, "[0, 8) or out of order"));
            into.Add(Expecting(BoundedChecks.Uniform("five gaps scaled to the span instead, all times", unspared,
                positions), expectsFailure: true));
            into.Add(Expecting(BoundedChecks.Uniform("five gaps scaled to the span instead, latest", unsparedLasts,
                calls), expectsFailure: true));
        }

        private static void Counts<GeneratorType>(RandOf<GeneratorType> rand, long draws, List<NamedOutcome> into)
            where GeneratorType : struct, IRandomGenerator
        {
            double[] means = { 2, 1, 1, 0.5 };
            double[] spans = { 1, 3, 12, 12.5 };
            for (int index = 0; index < means.Length; index++)
            {
                double mean = means[index];
                double span = spans[index];
                into.Add(CountsOf("EventCount(" + mean + ", " + span + ")", draws, span / mean,
                    () => rand.EventCount(mean, span)));
            }

            into.Add(CountsOf("one too many events instead", draws, 3, () => rand.EventCount(1, 3) + 1,
                expectsFailure: true));

            // The chance of an event within a span is the share of waits that fit in it.  The mean for a chance is the
            // one whose waits fit in the interval that often.
            long hits = 0;
            for (long i = 0; i < draws; i++)
            {
                if (rand.NextEvent(8) <= 5)
                {
                    hits++;
                }
            }

            into.Add(BoundedChecks.Proportion("ChanceWithin(8, 5) against the waits", hits, draws,
                EventRate.ChanceWithin(8, 5)));
            into.Add(BoundedChecks.Proportion("a linear chance, span over mean, instead", hits, draws, 5.0 / 8,
                expectsFailure: true));
            double meanFor = EventRate.MeanFor(0.3, 10);
            hits = 0;
            for (long i = 0; i < draws; i++)
            {
                if (rand.NextEvent(meanFor) <= 10)
                {
                    hits++;
                }
            }

            into.Add(BoundedChecks.Proportion("MeanFor(0.3, 10) against the waits", hits, draws, 0.3));
        }

        private static Func<double, double> BellCumulative(double min, double max, double mode, double tightness)
        {
            double modeFraction = (mode - min) / (max - min);
            double a = 1 + tightness * modeFraction;
            double b = modeFraction == 0 ? 1 + tightness : (1 + tightness * Math.Pow(modeFraction, -tightness *
                modeFraction)) / a;
            return value => 1 - Math.Pow(1 - Math.Pow((value - min) / (max - min), a), b);
        }

        private static void Bells<GeneratorType>(RandOf<GeneratorType> rand, long draws, List<NamedOutcome> into)
            where GeneratorType : struct, IRandomGenerator
        {
            double[] shapeA = { 2, 0.5, 5, 1, 30 };
            double[] shapeB = { 3, 2, 0.5, 1, 30 };
            for (int index = 0; index < shapeA.Length; index++)
            {
                double a = shapeA[index];
                double b = shapeB[index];
                into.Add(Shape("Kumaraswamy(" + a + ", " + b + ")", draws, () => rand.Kumaraswamy(a, b),
                    value => 1 - Math.Pow(1 - Math.Pow(value, a), b)));
            }

            into.Add(Shape("the shape numbers swapped instead", draws, () => rand.Kumaraswamy(3, 2),
                value => 1 - Math.Pow(1 - Math.Pow(value, 2), 3), expectsFailure: true));

            double[] mins = { 2, -5, 0, 0, 0 };
            double[] maxes = { 10, 5, 1, 1, 100 };
            double[] modes = { 4, 0, 1, 0, 70 };
            double[] tightnesses = { 4, 10, 4, 4, 40 };
            for (int index = 0; index < mins.Length; index++)
            {
                double min = mins[index];
                double max = maxes[index];
                double mode = modes[index];
                double tightness = tightnesses[index];
                string name = "Bell(" + min + ", " + max + ", " + mode + ", " + tightness + ")";
                long outside = 0;
                into.Add(Shape(name, draws, () =>
                {
                    double value = rand.Bell(min, max, mode, tightness);
                    if (value < min || value >= max)
                    {
                        outside++;
                    }

                    return value;
                }, BellCumulative(min, max, mode, tightness)));
                into.Add(StaysIn(name, outside, "[" + min + ", " + max + ")"));
            }

            into.Add(Shape("a hill in the middle whatever the mode, instead", draws,
                () => 2 + 8 * rand.Kumaraswamy(5, 5), BellCumulative(2, 10, 4, 4), expectsFailure: true));
        }

        private static double AngleInTurns(double x, double y)
        {
            double angle = Math.Atan2(y, x) / TwoPi;
            return angle < 0 ? angle + 1 : angle;
        }

        /// <summary>
        /// Counts points in a grid of rings of equal area by wedges of equal angle, which a fair point in a disc or a
        /// ring lands in evenly.
        /// </summary>
        private static NamedOutcome Polar(string name, long draws, double innerRadius, double outerRadius,
            Action<double[]> draw, bool expectsFailure = false)
        {
            var counts = new int[PolarSide * PolarSide];
            var point = new double[2];
            double innerSquared = innerRadius * innerRadius;
            double areaSpan = outerRadius * outerRadius - innerSquared;
            for (long i = 0; i < draws; i++)
            {
                draw(point);
                double ring = (point[0] * point[0] + point[1] * point[1] - innerSquared) / areaSpan;
                counts[PartOf(ring, PolarSide) * PolarSide + PartOf(AngleInTurns(point[0], point[1]), PolarSide)]++;
            }

            return Expecting(BoundedChecks.Uniform(name, counts, draws), expectsFailure);
        }

        private static void Circles<GeneratorType>(RandOf<GeneratorType> rand, long draws, List<NamedOutcome> into)
            where GeneratorType : struct, IRandomGenerator
        {
            const double radius = 3;
            long outside = 0;
            into.Add(Polar("InCircle(3)", draws, 0, radius, point =>
            {
                double x;
                double y;
                rand.InCircle(radius, out x, out y);
                if (x * x + y * y > radius * radius * (1 + 1e-12))
                {
                    outside++;
                }

                point[0] = x;
                point[1] = y;
            }));
            into.Add(StaysIn("InCircle(3)", outside, "the disc"));
            into.Add(Polar("a distance that is the radius times a draw, instead", draws, 0, radius, point =>
            {
                double distance = radius * rand.NextDouble();
                double angle = rand.NextDouble() * TwoPi;
                point[0] = distance * Math.Cos(angle);
                point[1] = distance * Math.Sin(angle);
            }, expectsFailure: true));

            outside = 0;
            into.Add(Polar("InRing(1, 3)", draws, 1, radius, point =>
            {
                double x;
                double y;
                rand.InRing(1, radius, out x, out y);
                double distanceSquared = x * x + y * y;
                if (distanceSquared > radius * radius * (1 + 1e-12) || distanceSquared < 1 - 1e-12)
                {
                    outside++;
                }

                point[0] = x;
                point[1] = y;
            }));
            into.Add(StaysIn("InRing(1, 3)", outside, "the ring"));
            into.Add(Polar("a distance spread evenly from 1 to 3, instead", draws, 1, radius, point =>
            {
                double distance = 1 + 2 * rand.NextDouble();
                double angle = rand.NextDouble() * TwoPi;
                point[0] = distance * Math.Cos(angle);
                point[1] = distance * Math.Sin(angle);
            }, expectsFailure: true));

            outside = 0;
            var directions = new int[Parts];
            var squareDirections = new int[Parts];
            for (long i = 0; i < draws; i++)
            {
                double x;
                double y;
                rand.OnCircle(radius, out x, out y);
                if (Math.Abs(Math.Sqrt(x * x + y * y) - radius) > 1e-12 * radius)
                {
                    outside++;
                }

                directions[PartOf(AngleInTurns(x, y), Parts)]++;

                // The tempting mistake: a point in a square, scaled to the circle, bunches up along the diagonals.
                double squareX = rand.NextDouble() * 2 - 1;
                double squareY = rand.NextDouble() * 2 - 1;
                squareDirections[PartOf(AngleInTurns(squareX, squareY), Parts)]++;
            }

            into.Add(BoundedChecks.Uniform("OnCircle(3), by angle", directions, draws));
            into.Add(StaysIn("OnCircle(3)", outside, "the circle"));
            into.Add(Expecting(BoundedChecks.Uniform("a point in a square, scaled to the circle, instead",
                squareDirections, draws), expectsFailure: true));
        }

        /// <summary>
        /// Returns the chance of each total of dice, found by adding one die at a time.
        /// </summary>
        public static double[] SumProbabilities(int dice, int sides)
        {
            var returnMe = new double[dice * sides + 1];
            returnMe[0] = 1;
            for (int die = 1; die <= dice; die++)
            {
                var next = new double[returnMe.Length];
                for (int total = 0; total < returnMe.Length; total++)
                {
                    if (returnMe[total] == 0)
                    {
                        continue;
                    }

                    for (int face = 1; face <= sides; face++)
                    {
                        next[total + face] += returnMe[total] / sides;
                    }
                }

                returnMe = next;
            }

            return returnMe;
        }

        private static void Walk(int dice, int sides, int keep, bool highest, int face, int remaining, int[] counts,
            double[] probabilities, double[] factorials)
        {
            if (face == sides - 1)
            {
                counts[face] = remaining;
                double ways = factorials[dice] / Math.Pow(sides, dice);
                foreach (int count in counts)
                {
                    ways /= factorials[count];
                }

                int kept = keep;
                int total = 0;
                for (int step = 0; step < sides && kept > 0; step++)
                {
                    int which = highest ? sides - 1 - step : step;
                    int taken = Math.Min(counts[which], kept);
                    total += taken * (which + 1);
                    kept -= taken;
                }

                probabilities[total] += ways;
                return;
            }

            for (int count = 0; count <= remaining; count++)
            {
                counts[face] = count;
                Walk(dice, sides, keep, highest, face + 1, remaining - count, counts, probabilities, factorials);
            }
        }

        /// <summary>
        /// Returns the chance of each total of the highest or lowest few of some dice, by going through every way the
        /// dice can land in faces.
        /// </summary>
        public static double[] KeptProbabilities(int dice, int sides, int keep, bool highest)
        {
            var factorials = new double[dice + 1];
            factorials[0] = 1;
            for (int i = 1; i <= dice; i++)
            {
                factorials[i] = factorials[i - 1] * i;
            }

            var returnMe = new double[dice * sides + 1];
            Walk(dice, sides, keep, highest, 0, dice, new int[sides], returnMe, factorials);
            return returnMe;
        }

        private static NamedOutcome Totals(string name, long draws, double[] probabilities, Func<int> roll,
            bool expectsFailure = false)
        {
            var observed = new double[probabilities.Length];
            for (long i = 0; i < draws; i++)
            {
                observed[roll()]++;
            }

            return Categories(name, observed, probabilities, draws, expectsFailure);
        }

        private static void Dice<GeneratorType>(RandOf<GeneratorType> rand, long draws, List<NamedOutcome> into)
            where GeneratorType : struct, IRandomGenerator
        {
            into.Add(Totals("Roll(3, 6)", draws, SumProbabilities(3, 6), () => rand.Roll(3, 6)));
            into.Add(Totals("one draw from 3 to 18, instead", draws, SumProbabilities(3, 6),
                () => rand.NextInt(3, 19), expectsFailure: true));
            into.Add(Totals("RollKeepHighest(4, 6, 3)", draws, KeptProbabilities(4, 6, 3, true),
                () => rand.RollKeepHighest(4, 6, 3)));
            into.Add(Totals("the first die dropped instead of the lowest", draws, KeptProbabilities(4, 6, 3, true),
                () => rand.Roll(3, 6), expectsFailure: true));
            into.Add(Totals("RollKeepHighest(2, 20, 1)", draws, KeptProbabilities(2, 20, 1, true),
                () => rand.RollKeepHighest(2, 20, 1)));
            into.Add(Totals("a single die instead of the best of two", draws, KeptProbabilities(2, 20, 1, true),
                () => rand.Roll(1, 20), expectsFailure: true));
            into.Add(Totals("RollKeepLowest(3, 20, 1)", draws, KeptProbabilities(3, 20, 1, false),
                () => rand.RollKeepLowest(3, 20, 1)));
            into.Add(Totals("RollKeepHighest(10, 6, 5)", draws, KeptProbabilities(10, 6, 5, true),
                () => rand.RollKeepHighest(10, 6, 5)));
        }

        private static List<int> KeysOfPermutations()
        {
            var returnMe = new List<int>();
            for (int first = 0; first < 4; first++)
            {
                for (int second = 0; second < 4; second++)
                {
                    for (int third = 0; third < 4; third++)
                    {
                        for (int fourth = 0; fourth < 4; fourth++)
                        {
                            if (first != second && first != third && first != fourth && second != third &&
                                second != fourth && third != fourth)
                            {
                                returnMe.Add(first * 64 + second * 16 + third * 4 + fourth);
                            }
                        }
                    }
                }
            }

            return returnMe;
        }

        private static NamedOutcome Even(string name, long draws, int[] counts, List<int> keys,
            bool expectsFailure = false)
        {
            var observed = new double[keys.Count];
            var probabilities = new double[keys.Count];
            for (int i = 0; i < keys.Count; i++)
            {
                observed[i] = counts[keys[i]];
                probabilities[i] = 1.0 / keys.Count;
            }

            return Categories(name, observed, probabilities, draws, expectsFailure);
        }

        private static void Picks<GeneratorType>(RandOf<GeneratorType> rand, long draws, List<NamedOutcome> into)
            where GeneratorType : struct, IRandomGenerator
        {
            var weights = new List<double> { 1, 2, 3, 4 };
            var weighted = new double[4];
            var unweighted = new double[4];
            for (long i = 0; i < draws; i++)
            {
                weighted[rand.PickWeightedIndex(weights)]++;
                unweighted[rand.NextInt(4)]++;
            }

            var shares = new[] { 0.1, 0.2, 0.3, 0.4 };
            into.Add(Categories("PickWeightedIndex(1, 2, 3, 4)", weighted, shares, draws));
            into.Add(Categories("an even pick instead", unweighted, shares, draws, expectsFailure: true));

            var permutations = KeysOfPermutations();
            var shuffled = new int[256];
            var swappedAnywhere = new int[256];
            var items = new int[4];
            for (long i = 0; i < draws; i++)
            {
                for (int item = 0; item < 4; item++)
                {
                    items[item] = item;
                }

                rand.Shuffle(items);
                shuffled[items[0] * 64 + items[1] * 16 + items[2] * 4 + items[3]]++;

                // The tempting mistake: swap each place with any place, which makes some orders likelier.
                for (int item = 0; item < 4; item++)
                {
                    items[item] = item;
                }

                for (int place = 0; place < 4; place++)
                {
                    int other = rand.NextInt(4);
                    int held = items[place];
                    items[place] = items[other];
                    items[other] = held;
                }

                swappedAnywhere[items[0] * 64 + items[1] * 16 + items[2] * 4 + items[3]]++;
            }

            into.Add(Even("Shuffle of 4 items", draws, shuffled, permutations));
            into.Add(Even("swapping each place with any place instead", draws, swappedAnywhere, permutations,
                expectsFailure: true));

            var pairs = new List<int>();
            for (int mask = 0; mask < 32; mask++)
            {
                if (Bits.PopCount((ulong)mask) == 2)
                {
                    pairs.Add(mask);
                }
            }

            var sampled = new int[32];
            var consecutive = new int[32];
            var five = new[] { 0, 1, 2, 3, 4 };
            var chosen = new List<int>();
            for (long i = 0; i < draws; i++)
            {
                chosen.Clear();
                rand.Sample(five, 2, chosen);
                sampled[(1 << chosen[0]) | (1 << chosen[1])]++;
                int start = rand.NextInt(4);
                consecutive[(1 << start) | (1 << (start + 1))]++;
            }

            into.Add(Even("Sample of 2 from 5", draws, sampled, pairs));
            into.Add(Even("two neighbors from a random start instead", draws, consecutive, pairs,
                expectsFailure: true));

            long bools = 0;
            long chances = 0;
            for (long i = 0; i < draws; i++)
            {
                if (rand.NextBool())
                {
                    bools++;
                }

                if (rand.Chance(0.3))
                {
                    chances++;
                }
            }

            into.Add(BoundedChecks.Proportion("NextBool()", bools, draws, 0.5));
            into.Add(BoundedChecks.Proportion("Chance(0.3)", chances, draws, 0.3));
        }

        public static List<NamedOutcome> Run<GeneratorType>(GeneratorType start, Scale scale)
            where GeneratorType : struct, IRandomGenerator
        {
            var rand = new RandOf<GeneratorType>(start);
            long draws = scale.Count(1L << 21, minimum: 1L << 17);
            var returnMe = new List<NamedOutcome>();
            Events(rand, draws, returnMe);
            EventLists(rand, draws, returnMe);
            Counts(rand, scale.Count(1L << 19, minimum: 1L << 15), returnMe);
            Bells(rand, draws, returnMe);
            Circles(rand, draws, returnMe);
            Dice(rand, scale.Count(1L << 20, minimum: 1L << 16), returnMe);
            Picks(rand, scale.Count(1L << 20, minimum: 1L << 16), returnMe);
            return returnMe;
        }
    }
}