package org.djutils.draw.line;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;

import org.djutils.draw.DrawRuntimeException;
import org.djutils.draw.Drawable2d;
import org.djutils.draw.point.Point2d;
import org.junit.Test;

/**
 * ConvexHullTest.java.
 * <p>
 * Copyright (c) 2020-2022 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
 * BSD-style license. See <a href="https://djutils.org/docs/current/djutils/licenses.html">DJUTILS License</a>.
 * </p>
 * @author <a href="https://www.tudelft.nl/averbraeck">Alexander Verbraeck</a>
 * @author <a href="https://www.tudelft.nl/pknoppers">Peter Knoppers</a>
 */
public class ConvexHullTest
{

    /**
     * Create the map of all convex hull implementations.
     * @return Map&lt;String, ConvexHullImplementation&gt;; the map of all convex hull implementations
     */
    public static Map<String, ConvexHullImplementation> getImplementations()
    {
        Map<String, ConvexHullImplementation> implementations = new LinkedHashMap<>();
        implementations.put("Monotone", new ConvexHullImplementation()
        {
            @Override
            public Polygon2d run(final List<Point2d> points) throws NullPointerException, DrawRuntimeException
            {
                return ConvexHull.convexHullMonotone(points);
            }
        });
        implementations.put("Alshamrani", new ConvexHullImplementation()
        {
            @Override
            public Polygon2d run(final List<Point2d> points) throws NullPointerException, DrawRuntimeException
            {
                return ConvexHull.convexHullAlshamrani(points);
            }
        });
        implementations.put("Default", new ConvexHullImplementation()
        {
            @Override
            public Polygon2d run(final List<Point2d> points) throws NullPointerException, DrawRuntimeException
            {
                return ConvexHull.convexHull(points);
            }
        });
        return implementations;
    }

    /**
     * Test a convex hull implementation.
     */
    @Test
    public void testConvexHull()
    {
        Map<String, ConvexHullImplementation> implementations = getImplementations();
        for (String name : implementations.keySet())
        {
            ConvexHullImplementation chi = implementations.get(name);
            try
            {
                chi.run(null);
                fail("should have thrown a NullPointerException");
            }
            catch (NullPointerException npe)
            {
                // Ignore expected exception
            }

            try
            {
                chi.run(new ArrayList<>());
                fail("Empty list should have thrown a DrawRuntimeException");
            }
            catch (DrawRuntimeException dre)
            {
                // Ignore expected exception
            }

            Point2d testPoint = new Point2d(2, 3);
            List<Point2d> points = Arrays.asList(testPoint);
            try
            {
                chi.run(points);
                fail("List with only one point should have thrown a DrawRuntimeException");
            }
            catch (DrawRuntimeException dre)
            {
                // Ignore expected exception
            }
            
            // Verify that the provided array was not modified.
            assertEquals("points still contains one point", 1, points.size());
            assertEquals("points still contains testPoint", testPoint, points.get(0));
            
            points = new ArrayList<>();
            points.add(testPoint);
            points.add(testPoint);
            try
            {
                chi.run(points);
                fail("List with only two identical should have thrown a DrawRuntimeException");
            }
            catch (DrawRuntimeException dre)
            {
                // Ignore expected exception
            }
            
            // Verify that the provided array was not modified.
            assertEquals("points still contains one point", 2, points.size());
            assertEquals("first points is testPoint", testPoint, points.get(0));
            assertEquals("second points is testPoint", testPoint, points.get(1));
        }
        try
        {
            ConvexHull.convexHull(new LinkedHashSet<Drawable2d>());
            fail("empty collection should have thrown a DrawRuntimeException");
        }
        catch (DrawRuntimeException dre)
        {
            // Ignore expected exception
        }

        try
        {
            ConvexHull.convexHull((Collection<Drawable2d>) null);
            fail("null collection should have thrown a NullPointerException");
        }
        catch (NullPointerException npe)
        {
            // Ignore expected exception
        }

        // Example set from https://rosettacode.org/wiki/Convex_hull#Java
        List<Point2d> points = Arrays.asList(new Point2d(16, 3), new Point2d(12, 17), new Point2d(0, 6), new Point2d(-4, -6),
                new Point2d(16, 6), new Point2d(16, -7), new Point2d(16, -3), new Point2d(17, -4), new Point2d(5, 19),
                new Point2d(19, -8), new Point2d(3, 16), new Point2d(12, 13), new Point2d(3, -4), new Point2d(17, 5),
                new Point2d(-3, 15), new Point2d(-3, -9), new Point2d(0, 11), new Point2d(-9, -3), new Point2d(-4, -2),
                new Point2d(12, 10));
        Polygon2d expectedResult = new Polygon2d(new Point2d(-9, -3), new Point2d(-3, -9), new Point2d(19, -8),
                new Point2d(17, 5), new Point2d(12, 17), new Point2d(5, 19), new Point2d(-3, 15));
        checkImplementations(implementations, points, expectedResult);
        Collections.shuffle(points, new Random(123));
        checkImplementations(implementations, points, expectedResult);

        assertEquals("convex hull of iterator", expectedResult, ConvexHull.convexHull(points.iterator()));

        assertEquals("convex hull of one drawable", expectedResult, ConvexHull.convexHull(new PolyLine2d(points)));

        assertEquals("convex hull of two drawables", expectedResult,
                ConvexHull.convexHull(new PolyLine2d(points), new Point2d(1, 2)));
        assertEquals("convex hull of two drawables", expectedResult,
                ConvexHull.convexHull(new Point2d(1, 2), new PolyLine2d(points)));

        Collection<Drawable2d> collection = new LinkedHashSet<>();
        collection.add(new PolyLine2d(points));
        assertEquals("convex hull of collection of one Drawable2d object", expectedResult, ConvexHull.convexHull(collection));

        collection.add(new Point2d(1, 2));
        assertEquals("convex hull of collection of two Drawable2d objects", expectedResult, ConvexHull.convexHull(collection));

        points = new ArrayList<>();
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -2; y <= 2; y++)
            {
                points.add(new Point2d(x, y));
            }
        }
        expectedResult = new Polygon2d(new Point2d(-1, -2), new Point2d(1, -2), new Point2d(1, 2), new Point2d(-1, 2));
        checkImplementations(implementations, points, expectedResult);
        Collections.shuffle(points, new Random(234));
        checkImplementations(implementations, points, expectedResult);

        points.add(new Point2d(-1.1, 0));
        points.add(new Point2d(0, -2.1));
        points.add(new Point2d(1.1, 0));
        points.add(new Point2d(0, 2.1));
        expectedResult = new Polygon2d(new Point2d(-1.1, 0), new Point2d(-1, -2), new Point2d(0, -2.1), new Point2d(1, -2),
                new Point2d(1.1, 0), new Point2d(1, 2), new Point2d(0, 2.1), new Point2d(-1, 2));
        checkImplementations(implementations, points, expectedResult);
        Collections.shuffle(points, new Random(345));
        checkImplementations(implementations, points, expectedResult);

        points.clear();
        double radius = 5000.0 / 64;
        double centerX = 1.5;
        double centerY = 10.5;
        // These for loops should not suffer from rounding errors
        for (double x = centerX - radius; x <= centerX + radius; x += 1)
        {
            for (double y = centerY - radius; y <= centerY + radius; y += 1)
            {
                double distance = Math.hypot(x - centerX, y - centerY);
                if (distance <= radius)
                {
                    points.add(new Point2d(x, y));
                }
            }
        }
        // It is a bit hard to construct the expected result; we'll use the result of convexHullMonotone as reference because it
        // is simpler and therefore less likely to contain errors.
        expectedResult = ConvexHull.convexHullMonotone(new ArrayList<>(points));
        checkImplementations(implementations, points, expectedResult);
        Collections.shuffle(points, new Random(456));
        checkImplementations(implementations, points, expectedResult);
    }

    /**
     * Compare performance.
     * @param args String[]; the command line arguments (not used)
     * @throws IOException ...
     */
    public static void main(final String[] args) throws IOException
    {
        Map<String, ConvexHullImplementation> implementations = getImplementations();
        List<Point2d> points = new ArrayList<>();
        double centerX = 1.5;
        double centerY = 10.5;
        System.out.println("type return when the profiler is ready");
        System.in.read();
        for (double radius = 5000.0 / 64; radius <= 6000; radius *= 2)
        {
            // These for loops should not suffer from rounding errors
            points.clear();
            for (double x = centerX - radius; x <= centerX + radius; x += 1)
            {
                for (double y = centerY - radius; y <= centerY + radius; y += 1)
                {
                    double distance = Math.hypot(x - centerX, y - centerY);
                    if (distance <= radius)
                    {
                        points.add(new Point2d(x, y));
                    }
                }
            }
            System.out.print("radius=" + radius + "; ordered input data\n");
            for (String name : implementations.keySet())
            {
                ConvexHullImplementation implementation = implementations.get(name);
                List<Point2d> workList = new ArrayList<>(points);
                System.gc();
                long startNanos = System.nanoTime();
                implementation.run(workList);
                long endNanos = System.nanoTime();
                double duration = (endNanos - startNanos) / 1e9;
                System.out.println(String.format("%d points %s: %.3f s", points.size(), name, duration));
            }
            Collections.shuffle(points, new Random(876));
            System.out.print("Radius=" + radius + "; scrambled input data\n");
            for (String name : implementations.keySet())
            {
                ConvexHullImplementation implementation = implementations.get(name);
                List<Point2d> workList = new ArrayList<>(points);
                System.gc();
                long startNanos = System.nanoTime();
                implementation.run(workList);
                long endNanos = System.nanoTime();
                double duration = (endNanos - startNanos) / 1e9;
                System.out.println(String.format("%d points %s: %.3f s", points.size(), name, duration));
            }
        }
    }

    /**
     * Check that all implementations of convex hull give the expected result.
     * @param implementations Map&lt;String, ConvexHullImplementation&gt;; the implementations to check
     * @param in List&lt;Point2d&gt;; the input for the convex hull implementations
     * @param expectedResult Polygon2d; the expected result
     */
    public static void checkImplementations(final Map<String, ConvexHullImplementation> implementations, final List<Point2d> in,
            final Polygon2d expectedResult)
    {
        for (String name : implementations.keySet())
        {
            Polygon2d result = implementations.get(name).run(new ArrayList<>(in));
            if (!result.equals(expectedResult))
            {
                System.err.println("Discrepancy for " + name);
                System.err.println("        result: " + result.toPlot());
                System.err.println("expectedResult: " + expectedResult.toPlot());
                System.err.println("         input: " + in);
                implementations.get(name).run(new ArrayList<>(in));
            }
            assertEquals(name, expectedResult, result);
        }

    }

    /**
     * Wrapper for any convex hull implementation.
     */
    interface ConvexHullImplementation
    {
        /**
         * Run a particular implementation of the convex hull algorithm.
         * @param points List&lt;Point2d&gt;; the points for which the convex hull must be constructed
         * @return Polygon2d; the convex hull of the points
         * @throws NullPointerException when list is null
         * @throws DrawRuntimeException when list is empty
         */
        Polygon2d run(List<Point2d> points) throws NullPointerException, DrawRuntimeException;
    }

}