using System;
using System.Collections.Generic;
using System.Linq;
using Azimuth;
using UnitTestSharp;

namespace Blacklight.Bezier.UnitTests
{
    public class CubicReferenceResultTests : TestFixture
    {
        public class CtorTests : TestFixture
        {
            public void AssignsBothFields()
            {
                var result = new CubicReferenceResult(distance: 1, closestT: 0.5);
                CheckEqual(1.0, result.Distance);
                CheckEqual(0.5, result.ClosestT);
            }
        }
    }

    public class CubicReferenceDistanceTests : TestFixture
    {
        public static readonly CubicPiece Wave = CubicPieceTests.Wave;
        public static readonly CubicPiece Cusp = new CubicPiece(new Vector(0, 0), new Vector(1, 1), new Vector(0, 1),
            new Vector(1, 0));
        public static readonly CubicPiece Loop = new CubicPiece(new Vector(0, 0), new Vector(3, 2), new Vector(-2, 2),
            new Vector(1, 0));

        public static double Binomial(int n, int k)
        {
            double returnMe = 1;
            for (int i = 1; i <= k; i++)
            {
                returnMe = returnMe * (n - k + i) / i;
            }

            return returnMe;
        }

        /// <summary>
        /// Returns the Bernstein coefficients on [0, 1] of the monic polynomial with these roots.
        /// </summary>
        public static double[] BernsteinFromRoots(params double[] roots)
        {
            var monomial = new double[roots.Length + 1];
            monomial[0] = 1;
            for (int r = 0; r < roots.Length; r++)
            {
                for (int i = r + 1; i > 0; i--)
                {
                    monomial[i] = monomial[i - 1] - roots[r] * monomial[i];
                }

                monomial[0] = -roots[r] * monomial[0];
            }

            int degree = roots.Length;
            var returnMe = new double[degree + 1];
            for (int k = 0; k <= degree; k++)
            {
                for (int i = 0; i <= k; i++)
                {
                    returnMe[k] += Binomial(k, i) / Binomial(degree, i) * monomial[i];
                }
            }

            return returnMe;
        }

        public static double BruteForceDistance(CubicPiece piece, Vector pixel)
        {
            const int gridSteps = 2000;
            int best = 0;
            double bestSquared = double.PositiveInfinity;
            for (int i = 0; i <= gridSteps; i++)
            {
                double squared = CubicReferenceDistance.SquaredDistanceAt(piece, pixel, (double)i / gridSteps);
                if (squared < bestSquared)
                {
                    bestSquared = squared;
                    best = i;
                }
            }

            double low = (double)Math.Max(best - 1, 0) / gridSteps;
            double high = (double)Math.Min(best + 1, gridSteps) / gridSteps;
            double inverseGolden = (Math.Sqrt(5) - 1) / 2;
            for (int i = 0; i < 100; i++)
            {
                double left = high - inverseGolden * (high - low);
                double right = low + inverseGolden * (high - low);
                if (CubicReferenceDistance.SquaredDistanceAt(piece, pixel, left)
                    < CubicReferenceDistance.SquaredDistanceAt(piece, pixel, right))
                {
                    high = right;
                }
                else
                {
                    low = left;
                }
            }

            return Math.Sqrt(Math.Min(bestSquared,
                CubicReferenceDistance.SquaredDistanceAt(piece, pixel, (low + high) / 2)));
        }

        public static Vector RandomPoint(Random random, double reach)
        {
            return new Vector(SampleSets.Uniform(random, -reach, reach), SampleSets.Uniform(random, -reach, reach));
        }

        public class EvaluateTests : TestFixture
        {
            public void Ends_AreTheEndCoefficients()
            {
                double[] coefficients = { 2, -1, 5, 3 };
                CheckEqual(2.0, CubicReferenceDistance.Evaluate(coefficients, 0));
                CheckEqual(3.0, CubicReferenceDistance.Evaluate(coefficients, 1));
            }

            public void Interior_MatchesTheFactoredPolynomial()
            {
                double[] coefficients = BernsteinFromRoots(0.2, 0.7);
                CheckGreater(1e-15, Math.Abs(CubicReferenceDistance.Evaluate(coefficients, 0.4) + 0.06));
            }
        }

        public class SubdivideTests : TestFixture
        {
            public void HalvesReproduceThePolynomialOnTheirIntervals()
            {
                double[] coefficients = { 2, -1, 5, 3, -4, 1 };
                var left = new double[6];
                var right = new double[6];
                CubicReferenceDistance.Subdivide(coefficients, left, right);
                for (double s = 0; s <= 1; s += 0.125)
                {
                    CheckGreater(1e-14, Math.Abs(CubicReferenceDistance.Evaluate(left, s)
                        - CubicReferenceDistance.Evaluate(coefficients, s / 2)));
                    CheckGreater(1e-14, Math.Abs(CubicReferenceDistance.Evaluate(right, s)
                        - CubicReferenceDistance.Evaluate(coefficients, 0.5 + s / 2)));
                }
            }

            public void HalvesShareTheMiddleValue()
            {
                double[] coefficients = { 2, -1, 5, 3, -4, 1 };
                var left = new double[6];
                var right = new double[6];
                CubicReferenceDistance.Subdivide(coefficients, left, right);
                CheckEqual(left[5], right[0]);
            }
        }

        public class SignChangesTests : TestFixture
        {
            public void OneSign_IsZero()
            {
                CheckEqual(0, CubicReferenceDistance.SignChanges(new double[] { 1, 2, 3 }));
            }

            public void Alternating_CountsEachChange()
            {
                CheckEqual(3, CubicReferenceDistance.SignChanges(new double[] { 1, -1, 1, -1 }));
            }

            public void Zeros_AreSkipped()
            {
                CheckEqual(2, CubicReferenceDistance.SignChanges(new double[] { 0, 1, 0, -1, 0, 0, 1, 0 }));
            }
        }

        public class LeadingSignTests : TestFixture
        {
            public void SkipsLeadingZeros()
            {
                CheckEqual(-1, CubicReferenceDistance.LeadingSign(new double[] { 0, 0, -2, 1 }));
            }

            public void AllZero_IsZero()
            {
                CheckEqual(0, CubicReferenceDistance.LeadingSign(new double[] { 0, 0, 0 }));
            }
        }

        public class BisectRootTests : TestFixture
        {
            public void SimpleRoot_IsFoundToTheLastBit()
            {
                double root = CubicReferenceDistance.BisectRoot(BernsteinFromRoots(0.3, -1), low: 0, high: 1,
                    lowSign: -1);
                CheckGreater(1e-15, Math.Abs(root - 0.3));
            }

            public void RootOnAMidpoint_IsReturnedExactly()
            {
                CheckEqual(0.5, CubicReferenceDistance.BisectRoot(new double[] { -1, 1 }, low: 0, high: 1,
                    lowSign: -1));
            }

            public void RootOnTheLowEnd_FindsTheInteriorRoot()
            {
                double root = CubicReferenceDistance.BisectRoot(BernsteinFromRoots(0, 0.6), low: 0, high: 1,
                    lowSign: -1);
                CheckGreater(1e-15, Math.Abs(root - 0.6));
            }
        }

        public class FootCandidatesTests : TestFixture
        {
            public void FiveSeparatedRoots_FindsEachOne()
            {
                double[] roots = { 0.1, 0.3, 0.5, 0.7, 0.9 };
                var candidates = new List<double>();
                CubicReferenceDistance.FootCandidates(BernsteinFromRoots(roots), candidates,
                    CubicReferenceDistance.SmallestInterval, CubicReferenceDistance.IntervalBudget);
                foreach (double root in roots)
                {
                    CheckGreater(1e-12, candidates.Min(candidate => Math.Abs(candidate - root)));
                }
            }

            public void NoSignChange_AddsNothing()
            {
                var candidates = new List<double>();
                CubicReferenceDistance.FootCandidates(new double[] { 1, 2, 1, 3, 1, 2 }, candidates,
                    CubicReferenceDistance.SmallestInterval, CubicReferenceDistance.IntervalBudget);
                CheckEqual(0, candidates.Count);
            }

            public void RootsWithinTheSmallestInterval_ShareOneCandidateAtItsMiddle()
            {
                var candidates = new List<double>();
                CubicReferenceDistance.FootCandidates(BernsteinFromRoots(0.3, 0.4), candidates,
                    smallestInterval: 0.3, intervalBudget: CubicReferenceDistance.IntervalBudget);
                CheckEqual(1, candidates.Count);
                CheckEqual(0.375, candidates[0]);
            }

            public void RootExactlyOnASplitPoint_IsAddedOnce()
            {
                var candidates = new List<double>();
                CubicReferenceDistance.FootCandidates(new double[] { 2, -2, 0, 4 }, candidates,
                    CubicReferenceDistance.SmallestInterval, CubicReferenceDistance.IntervalBudget);
                CheckEqual(2, candidates.Count);
                CheckEqual(1, candidates.Count(candidate => candidate == 0.5));
            }

            public void OverBudget_Throws()
            {
                CheckThrow(typeof(InvalidOperationException));
                CubicReferenceDistance.FootCandidates(BernsteinFromRoots(0.1, 0.3, 0.5, 0.7, 0.9), new List<double>(),
                    CubicReferenceDistance.SmallestInterval, intervalBudget: 1);
            }
        }

        public class FootCoefficientsTests : TestFixture
        {
            public void MatchesTheOffsetDottedWithAThirdOfTheTangent()
            {
                var pixel = new Vector(1.5, 2);
                double[] coefficients = CubicReferenceDistance.FootCoefficients(Wave, pixel);
                for (double t = 0; t <= 1; t += 0.125)
                {
                    double expected = Vector.DotProduct(Wave.PointAt(t) - pixel, Wave.DerivativeAt(t)) / 3;
                    CheckGreater(1e-12, Math.Abs(CubicReferenceDistance.Evaluate(coefficients, t) - expected));
                }
            }
        }

        public class SquaredDistanceAtTests : TestFixture
        {
            public void AtTheStart_IsTheSquaredDistanceToTheFirstControlPoint()
            {
                CheckEqual(25.0, CubicReferenceDistance.SquaredDistanceAt(Wave, new Vector(3, 4), t: 0));
            }

            public void Interior_IsTheSquaredDistanceToThatCurvePoint()
            {
                var pixel = new Vector(1, 2);
                double expected = Vector.DistanceSquared(Wave.PointAt(0.5), pixel);
                CheckGreater(1e-14, Math.Abs(expected - CubicReferenceDistance.SquaredDistanceAt(Wave, pixel, t: 0.5)));
            }
        }

        public class SolveTests : TestFixture
        {
            [IgnoreTest]
            public void CheckMatchesBruteForce(CubicPiece piece, Random random, int count, double reach)
            {
                for (int i = 0; i < count; i++)
                {
                    Vector pixel = RandomPoint(random, reach);
                    CheckGreater(1e-9, Math.Abs(CubicReferenceDistance.Solve(piece, pixel).Distance
                        - BruteForceDistance(piece, pixel)));
                }
            }

            public void PointOnTheCurve_IsAtDistanceZero()
            {
                CubicReferenceResult result = CubicReferenceDistance.Solve(Wave, Wave.PointAt(0.3));
                CheckGreater(1e-15, result.Distance);
                CheckGreater(1e-12, Math.Abs(result.ClosestT - 0.3));
            }

            public void BehindTheStart_TheStartIsClosest()
            {
                CubicReferenceResult result = CubicReferenceDistance.Solve(Wave, new Vector(-2, -1));
                CheckEqual(Math.Sqrt(5), result.Distance);
                CheckEqual(0.0, result.ClosestT);
            }

            public void PastTheEnd_TheEndIsClosest()
            {
                CubicReferenceResult result = CubicReferenceDistance.Solve(Wave, new Vector(6, 2));
                CheckEqual(Math.Sqrt(8), result.Distance);
                CheckEqual(1.0, result.ClosestT);
            }

            public void NearTheCurve_RecoversTheOffset()
            {
                const double offset = 1e-9;
                Vector normal = Wave.DerivativeAt(0.3).NormalizedCopy().PerpCCW();
                CubicReferenceResult result = CubicReferenceDistance.Solve(Wave, Wave.PointAt(0.3) + offset * normal);
                CheckGreater(1e-6, Math.Abs(result.Distance - offset) / offset);
            }

            public void DegreeElevatedQuadratic_MatchesTheQuadraticReference()
            {
                var random = new Random(7);
                for (int i = 0; i < 200; i++)
                {
                    double end = SampleSets.Uniform(random, 0.1, 10);
                    CubicPiece piece = CubicPiece.FromQuadratic(new Vector(0, 0), new Vector(end / 2, 0),
                        new Vector(end, end * end / 2));
                    var pixel = new Vector(SampleSets.Uniform(random, -5, 5), SampleSets.Uniform(random, -3, 8));
                    double expected = ReferenceDistance.Solve(ShellSample.FromPosition(pixel.X, pixel.Y, end)).Distance;
                    CheckGreater(1e-12 * (1 + end * end),
                        Math.Abs(CubicReferenceDistance.Solve(piece, pixel).Distance - expected));
                }
            }

            public void CollinearDoublingBack_TheTurningPointIsClosest()
            {
                var piece = new CubicPiece(new Vector(0, 0), new Vector(2, 0), new Vector(-1, 0), new Vector(0, 0));
                double turning = (10 - Math.Sqrt(28)) / 18;
                CubicReferenceResult result = CubicReferenceDistance.Solve(piece,
                    piece.PointAt(turning) + new Vector(1, 0));
                CheckGreater(1e-14, Math.Abs(result.Distance - 1));
                CheckGreater(1e-7, Math.Abs(result.ClosestT - turning));
            }

            public void AllControlPointsTogether_IsTheDistanceToThatPoint()
            {
                var point = new Vector(1, 1);
                var piece = new CubicPiece(point, point, point, point);
                CheckEqual(5.0, CubicReferenceDistance.Solve(piece, new Vector(4, 5)).Distance);
            }

            public void Cusp_MatchesBruteForce()
            {
                CheckMatchesBruteForce(Cusp, new Random(11), count: 200, reach: 1.5);
            }

            public void Loop_MatchesBruteForce()
            {
                CheckMatchesBruteForce(Loop, new Random(13), count: 200, reach: 2);
            }

            public void RandomPieces_MatchBruteForce()
            {
                var random = new Random(17);
                for (int i = 0; i < 50; i++)
                {
                    var piece = new CubicPiece(RandomPoint(random, 1), RandomPoint(random, 1), RandomPoint(random, 1),
                        RandomPoint(random, 1));
                    CheckMatchesBruteForce(piece, random, count: 10, reach: 1.5);
                }
            }
        }
    }
}