namespace Godosa.Core.Runs;

/// <summary>Route planning for run scripts (docs/notes/run-scripts-routing.md): a way over a grid (8 neighbours) cut into
/// the legs the game's own router accepts, the script seals that close a way, and portal hops between walkable areas. Pure;
/// the game passes its grid, its router's acceptance test and its portals.</summary>
public static class RouteLegs
{
    /// <summary>Breadth-first over <c>[0,width)×[0,height)</c>, 8 neighbours, until <paramref name="goal"/>: each reached
    /// cell → the one it was reached from (start → itself).</summary>
    public static Dictionary<(long X, long Y), (long X, long Y)> Reach((long X, long Y) start, (long X, long Y) goal, long width, long height,
        Func<long, long, bool> blocked)
    {
        var from = new Dictionary<(long X, long Y), (long X, long Y)> { [start] = start };
        var queue = new Queue<(long X, long Y)>([start]);
        while (queue.Count > 0 && !from.ContainsKey(goal))
        {
            var at = queue.Dequeue();
            for (var dx = -1; dx <= 1; dx++)
                for (var dy = -1; dy <= 1; dy++)
                {
                    var next = (at.X + dx, at.Y + dy);
                    if (from.ContainsKey(next) || next.Item1 < 0 || next.Item2 < 0 || next.Item1 >= width || next.Item2 >= height
                        || blocked(next.Item1, next.Item2))
                        continue;
                    from[next] = at;
                    queue.Enqueue(next);
                }
        }
        return from;
    }

    /// <summary>The cells from <paramref name="start"/> (excluded) to <paramref name="goal"/> (included); null when walled
    /// off.</summary>
    public static List<(long X, long Y)>? Path((long X, long Y) start, (long X, long Y) goal, long width, long height, Func<long, long, bool> blocked)
    {
        var from = Reach(start, goal, width, height, blocked);
        return from.ContainsKey(goal) ? Trace(from, start, goal) : null;
    }

    /// <summary>Legs along <paramref name="path"/>: from each stop the farthest path cell <paramref name="accepts"/> (the
    /// game's router takes the trip), until the goal; null when the router takes no further cell from a stop.</summary>
    public static List<(long X, long Y)>? Legs((long X, long Y) start, IReadOnlyList<(long X, long Y)> path,
        Func<(long X, long Y), (long X, long Y), bool> accepts) => Legs(start, path, accepts, out _);

    /// <inheritdoc cref="Legs(ValueTuple{long, long}, IReadOnlyList{ValueTuple{long, long}}, Func{ValueTuple{long, long}, ValueTuple{long, long}, bool})"/>
    /// <param name="stuck">The stop no leg leaves (refusals name it).</param>
    public static List<(long X, long Y)>? Legs((long X, long Y) start, IReadOnlyList<(long X, long Y)> path,
        Func<(long X, long Y), (long X, long Y), bool> accepts, out (long X, long Y) stuck)
    {
        var legs = new List<(long X, long Y)>();
        var (stop, index) = (start, 0);
        while (index < path.Count)
        {
            var best = path.Count - 1;
            while (best >= index && !accepts(stop, path[best]))
                best--;
            if (best < index)
            {
                stuck = stop;
                return null;
            }
            (stop, index) = (path[best], best + 1);
            legs.Add(stop);
        }
        stuck = default;
        return legs;
    }

    /// <summary>The <paramref name="soft"/> cells (blocked by the game's scripts, opened later) the way would cross once
    /// open, start to goal, at most <paramref name="max"/>; empty when walled off anyway or open already.</summary>
    public static List<(long X, long Y)> Seals((long X, long Y) start, (long X, long Y) goal, long width, long height,
        Func<long, long, bool> blocked, Func<long, long, bool> soft, int max = 8)
    {
        if (Path(start, goal, width, height, blocked) != null)
            return [];
        var way = Path(start, goal, width, height, (x, y) => blocked(x, y) && !soft(x, y));
        return way == null ? [] : way.Where(c => soft(c.X, c.Y)).Take(max).ToList();
    }

    /// <summary>Portal hops: breadth-first over portal exits from <paramref name="start"/>; the portals to take, in order, so
    /// that <paramref name="reaches"/> (a walk inside one area) gets to <paramref name="goal"/>; empty when it walks there;
    /// null when no chain does.</summary>
    public static List<TPortal>? Hops<TPos, TPortal>(TPos start, TPos goal, IReadOnlyList<TPortal> portals, Func<TPortal, TPos> at,
        Func<TPortal, TPos> exit, Func<TPos, TPos, bool> reaches) where TPos : notnull
    {
        var via = new Dictionary<TPos, (TPos From, TPortal? Portal)> { [start] = (start, default) };
        var queue = new Queue<TPos>([start]);
        while (queue.Count > 0)
        {
            var here = queue.Dequeue();
            if (reaches(here, goal))
            {
                var hops = new List<TPortal>();
                for (var p = here; !EqualityComparer<TPos>.Default.Equals(p, start); p = via[p].From)
                    hops.Add(via[p].Portal!);
                hops.Reverse();
                return hops;
            }
            foreach (var portal in portals)
                if (!via.ContainsKey(exit(portal)) && reaches(here, at(portal)))
                {
                    via[exit(portal)] = (here, portal);
                    queue.Enqueue(exit(portal));
                }
        }
        return null;
    }

    private static List<(long X, long Y)> Trace(Dictionary<(long X, long Y), (long X, long Y)> from, (long X, long Y) start, (long X, long Y) goal)
    {
        var path = new List<(long X, long Y)>();
        for (var c = goal; c != start; c = from[c])
            path.Add(c);
        path.Reverse();
        return path;
    }
}