//! Pathfinder algorithms on a grid. The grid is stack-based, we only use heap allocations
//! in solvers.
const std = @import("std");

const Str = []const u8;

/// Various predefined valid neighbour directions on a 2D grid.
pub const D2 = struct {
    pub const horizontal = [_][2]i2{ .{ 0, -1 }, .{ 0, 1 } };
    pub const vertical = [_][2]i2{ .{ -1, 0 }, .{ 1, 0 } };
    pub const HV = horizontal ++ vertical;
    pub const diagonal = [_][2]i2{ .{ -1, -1 }, .{ -1, 1 }, .{ 1, -1 }, .{ 1, 1 } };
    pub const all = HV ++ diagonal;
};

/// Grid for various pathfinder algorithms.
/// `T` is the type of Grid items.
/// `GRID_ROWS` and `GRID_COLS` defines the Grid size.
pub fn Grid(comptime T: type, comptime GRID_ROWS: usize, comptime GRID_COLS: usize) type {
    return struct {
        grid: [GRID_ROWS][GRID_COLS]T = undefined,

        const QueueType = struct {
            state: [2]usize,
            cost: T,
        };

        pub fn setGrid(self: *@This(), grid: [GRID_ROWS][GRID_COLS]T) void {
            self.grid = grid;
        }

        /// Parses a grid-file located in `path`. The items must be separated with `sep`.
        pub fn parseGridFromCSV(self: *@This(), comptime path: Str, sep: Str) !void {
            const input = @embedFile(path);
            var lines = std.mem.tokenize(u8, input, "\n");

            var ret: [GRID_ROWS][GRID_COLS]T = undefined;

            var row: usize = 0;
            while (lines.next()) |line| : (row += 1) {
                var items = std.mem.tokenize(u8, line, sep);

                var col: usize = 0;
                while (items.next()) |item| : (col += 1) {
                    switch (@typeInfo(T)) {
                        .Int => |item_type| {
                            if (item_type.signedness == .unsigned) {
                                ret[row][col] = try std.fmt.parseUnsigned(T, item, 0);
                            } else {
                                ret[row][col] = try std.fmt.parseInt(T, item, 0);
                            }
                        },
                        .Float => ret[row][col] = try std.fmt.parseFloat(T, item),
                        else => @compileError("unsupported type: " ++ @typeName(T)),
                    }
                }
            }
            self.setGrid(ret);
        }

        fn lessThan(context: void, a: QueueType, b: QueueType) std.math.Order {
            _ = context;
            if (a.cost == b.cost) {
                return .eq;
            } else if (a.cost < b.cost) {
                return .lt;
            } else {
                return .gt;
            }
        }

        /// Finds shortest path between `start` and `goal` using Dijkstra's algorithm.
        /// Returns the path length or `error.PathNotFound`.
        pub fn dijkstra(
            self: *@This(),
            allocator: std.mem.Allocator,
            start: [2]usize,
            goal: [2]usize,
            dir: anytype,
        ) !T {
            var CostGrid = switch (@typeInfo(T)) {
                .Int => [_][GRID_COLS]T{[_]T{std.math.maxInt(T)} ** GRID_COLS} ** GRID_ROWS,
                .Float => [_][GRID_COLS]T{[_]T{std.math.floatMax(T)} ** GRID_COLS} ** GRID_ROWS,
                else => @compileError("unsupported type: " ++ @typeName(T)),
            };
            CostGrid[start[0]][start[1]] = 0;

            var queue = std.PriorityQueue(QueueType, void, comptime lessThan).init(allocator, {});
            defer queue.deinit();

            try queue.add(.{ .state = start, .cost = 0 });

            while (queue.removeOrNull()) |curr| {
                if (std.meta.eql(curr.state, goal)) {
                    return curr.cost;
                }
                for (dir) |d| {
                    const diffrow = @as(isize, @intCast(curr.state[0])) + d[0];
                    if (diffrow < 0 or diffrow >= GRID_ROWS) continue;
                    const dr = @as(usize, @intCast(diffrow));

                    const diffcol = @as(isize, @intCast(curr.state[1])) + d[1];
                    if (diffcol < 0 or diffcol >= GRID_COLS) continue;
                    const dc = @as(usize, @intCast(diffcol));

                    const cost = CostGrid[curr.state[0]][curr.state[1]] + self.grid[dr][dc];

                    if (cost < CostGrid[dr][dc]) {
                        CostGrid[dr][dc] = cost;
                        try queue.add(.{ .state = .{ dr, dc }, .cost = cost });
                    }
                }
            }
            return error.PathNotFound;
        }

        pub fn astar(
            self: *@This(),
            allocator: std.mem.Allocator,
            start: [2]usize,
            goal: [2]usize,
            dir: anytype,
            heuristics: anytype,
        ) !T {
            var CostGrid = switch (@typeInfo(T)) {
                .Int => [_][GRID_COLS]T{[_]T{std.math.maxInt(T)} ** GRID_COLS} ** GRID_ROWS,
                .Float => [_][GRID_COLS]T{[_]T{std.math.floatMax(T)} ** GRID_COLS} ** GRID_ROWS,
                else => @compileError("unsupported type: " ++ @typeName(T)),
            };
            CostGrid[start[0]][start[1]] = 0;

            var queue = std.PriorityQueue(QueueType, void, comptime lessThan).init(allocator, {});
            defer queue.deinit();

            try queue.add(.{ .state = start, .cost = 0 });

            while (queue.removeOrNull()) |curr| {
                if (std.meta.eql(curr.state, goal)) {
                    return curr.cost;
                }
                for (dir) |d| {
                    const diffrow = @as(isize, @intCast(curr.state[0])) + d[0];
                    if (diffrow < 0 or diffrow >= GRID_ROWS) continue;
                    const dr = @as(usize, @intCast(diffrow));

                    const diffcol = @as(isize, @intCast(curr.state[1])) + d[1];
                    if (diffcol < 0 or diffcol >= GRID_COLS) continue;
                    const dc = @as(usize, @intCast(diffcol));

                    const cost = CostGrid[curr.state[0]][curr.state[1]] + self.grid[dr][dc];

                    if (cost < CostGrid[dr][dc]) {
                        CostGrid[dr][dc] = cost;
                        try queue.add(
                            .{ .state = .{ dr, dc }, .cost = cost + try heuristics(.{ dr, dc }, goal) },
                        );
                    }
                }
            }
            return error.PathNotFound;
        }
    };
}