using System;
using System.Collections.Generic;
using System.Threading;
using Avalonia;

namespace Cfa.Ui.Graph;

internal static class EdgeAvoidance
{
    public static void Apply(
        PhysicsNode[] nodes,
        Point[] positions,
        Vector[] forces,
        PhysicsOptions options,
        CancellationToken token
    )
    {
        if (options.EdgeCrossingStrength == 0 && options.EdgeNodeStrength == 0)
            return;
        var cellSize = Math.Max(240, options.EdgeClearance * 2);
        var cells = new Dictionary<(int X, int Y), List<int>>();
        for (var i = 1; i < nodes.Length; i++)
        {
            token.ThrowIfCancellationRequested();
            var start = positions[nodes[i].Parent];
            var end = positions[i];
            foreach (var key in Keys(start, end, options.EdgeClearance, cellSize))
            {
                if (!cells.TryGetValue(key, out var edges))
                    cells[key] = edges = [];
                edges.Add(i);
            }
        }
        var pairs = new HashSet<(int, int)>();
        for (var i = 1; i < nodes.Length && options.EdgeCrossingStrength > 0; i++)
        {
            token.ThrowIfCancellationRequested();
            var a = nodes[i].Parent;
            foreach (var key in Keys(positions[a], positions[i], options.EdgeClearance, cellSize))
            {
                foreach (var j in cells[key])
                {
                    if (j <= i || !pairs.Add((i, j)))
                        continue;
                    var b = nodes[j].Parent;
                    if (a == b || a == j || b == i)
                        continue;
                    var crossing = Crosses(positions[a], positions[i], positions[b], positions[j]);
                    var bestDistance = double.PositiveInfinity;
                    var endpoint = -1;
                    var edgeStart = -1;
                    var edgeEnd = -1;
                    var fraction = 0d;
                    var offset = default(Vector);
                    Consider(a, b, j);
                    Consider(i, b, j);
                    Consider(b, a, i);
                    Consider(j, a, i);
                    if (!crossing && bestDistance >= options.EdgeClearance)
                        continue;
                    var direction =
                        bestDistance > 1e-8
                            ? offset / bestDistance
                            : Normal(positions[edgeStart], positions[edgeEnd], endpoint);
                    // A crossing endpoint moves through the opposing edge, not farther
                    // into its current side. Near misses instead repel continuously.
                    var magnitude = crossing
                        ? bestDistance + options.EdgeClearance
                        : options.EdgeClearance - bestDistance;
                    var force = direction * (magnitude * options.EdgeCrossingStrength * (crossing ? -1 : 1));
                    forces[endpoint] += force;
                    forces[edgeStart] -= force * (1 - fraction);
                    forces[edgeEnd] -= force * fraction;

                    void Consider(int point, int first, int second)
                    {
                        var t = Fraction(positions[point], positions[first], positions[second]);
                        var closest = positions[first] + (positions[second] - positions[first]) * t;
                        var delta = new Vector(positions[point].X - closest.X, positions[point].Y - closest.Y);
                        if (delta.Length >= bestDistance)
                            return;
                        bestDistance = delta.Length;
                        endpoint = point;
                        edgeStart = first;
                        edgeEnd = second;
                        fraction = t;
                        offset = delta;
                    }
                }
            }
        }
        if (options.EdgeNodeStrength == 0)
            return;
        for (var i = 0; i < nodes.Length; i++)
        {
            token.ThrowIfCancellationRequested();
            var key = ((int)Math.Floor(positions[i].X / cellSize), (int)Math.Floor(positions[i].Y / cellSize));
            if (!cells.TryGetValue(key, out var edges))
                continue;
            foreach (var edge in edges)
            {
                var parent = nodes[edge].Parent;
                if (i == edge || i == parent)
                    continue;
                var t = Fraction(positions[i], positions[parent], positions[edge]);
                if (t <= 0 || t >= 1)
                    continue;
                var closest = positions[parent] + (positions[edge] - positions[parent]) * t;
                var offset = new Vector(positions[i].X - closest.X, positions[i].Y - closest.Y);
                var distance = offset.Length;
                if (distance >= options.EdgeClearance)
                    continue;
                var direction = distance > 1e-8 ? offset / distance : Normal(positions[parent], positions[edge], i);
                var force = direction * ((options.EdgeClearance - distance) * options.EdgeNodeStrength);
                forces[i] += force;
                forces[parent] -= force * (1 - t);
                forces[edge] -= force * t;
            }
        }
    }

    private static double Fraction(Point point, Point start, Point end)
    {
        var dx = end.X - start.X;
        var dy = end.Y - start.Y;
        var squared = dx * dx + dy * dy;
        return squared < 1e-12 ? 0 : Math.Clamp(((point.X - start.X) * dx + (point.Y - start.Y) * dy) / squared, 0, 1);
    }

    private static Vector Normal(Point start, Point end, int id)
    {
        var vector = new Vector(start.Y - end.Y, end.X - start.X);
        return vector.Length > 1e-8 ? vector / vector.Length * (id % 2 == 0 ? 1 : -1) : new Vector(0, 1);
    }

    private static bool Crosses(Point a, Point b, Point c, Point d)
    {
        static double Side(Point p, Point q, Point r) => (q.X - p.X) * (r.Y - p.Y) - (q.Y - p.Y) * (r.X - p.X);
        return Side(a, b, c) * Side(a, b, d) < 0 && Side(c, d, a) * Side(c, d, b) < 0;
    }

    private static IEnumerable<(int X, int Y)> Keys(Point start, Point end, double margin, double size)
    {
        for (
            var x = (int)Math.Floor((Math.Min(start.X, end.X) - margin) / size);
            x <= (int)Math.Floor((Math.Max(start.X, end.X) + margin) / size);
            x++
        )
        for (
            var y = (int)Math.Floor((Math.Min(start.Y, end.Y) - margin) / size);
            y <= (int)Math.Floor((Math.Max(start.Y, end.Y) + margin) / size);
            y++
        )
            yield return (x, y);
    }
}