package net.caraus.labyrinth;

import com.badlogic.gdx.graphics.glutils.ShapeRenderer;
import java.util.ArrayList;
import java.util.HashSet;

public class WaveTracing {
    private Maze maze;
    private Point start;
    private Point finish;
    private int[][] mark;
    private int n = 1;

    private ArrayList<Point> startLocations = new ArrayList<>();
    private ArrayList<Point> finishLocations = new ArrayList<>();
    private Point solution = null;

    public WaveTracing(Maze maze, Point start, Point finish) {
        this.maze = maze;
        this.start = start;
        this.finish = finish;

        initializeMarks();
    }

    private void initializeMarks() {
        this.mark = new int[this.maze.width()][this.maze.height()]; // Метки локаций.

        for (var column: mark) {
            for (var y = 0; y < column.length; ++y) {
                column[y] = 0;
            }
        }
        mark[this.start.x()][this.start.y()] = 1;
        mark[this.finish.x()][this.finish.y()] = 1;

        this.startLocations.add(this.start);
        this.finishLocations.add(this.finish);
    }

    private ArrayList<Point> solveOneSide(ArrayList<Point> locations) {
        // Локации со следующим N.
        ArrayList<Point> nextLocations = new ArrayList<>();

        // Посетить локации, помеченные числом N.
        for (var nLocation: locations) {
            // Просмотр соседей.
            for (var i = 0; i < 4; ++i) {
                var neighbour = new Point(nLocation.x() + Maze.DX[i], nLocation.y() + Maze.DY[i]);

                if (maze.canGo(nLocation, i) && this.mark[neighbour.x()][neighbour.y()] == 0) {
                    // Локация доступна и помечена нулем.
                    // Есть шанс найти решения.
                    nextLocations.add(neighbour);
                }
            }
        }
        return nextLocations;
    }

    private Point startAndFinishIntersect() {
        HashSet<Point> nextLocations = new HashSet<>(this.startLocations);
        nextLocations.retainAll(this.finishLocations);

        return nextLocations.stream().findFirst().orElse(null);
    }

    public Solution solve() {
        // Пессимично полагаем, что решения нет.
        var noSolution = true;
        Point intersection;

        if (this.solution != null) {
            return Solution.DONE;
        }
        this.startLocations = solveOneSide(this.startLocations);
        if ((intersection = startAndFinishIntersect()) != null) {
            this.solution = intersection;
        }
        this.finishLocations = solveOneSide(this.finishLocations);
        if ((intersection = startAndFinishIntersect()) != null) {
            this.solution = intersection;
        }
        HashSet<Point> nextLocations = new HashSet<>(this.startLocations);
        nextLocations.addAll(this.finishLocations);

        for (var nLocation: nextLocations) {
            this.mark[nLocation.x()][nLocation.y()] = this.n + 1;
        }
        if (!nextLocations.isEmpty()) {
            noSolution = false;
            this.n += 1;
        }
        if (this.solution != null) {
            return Solution.DONE;
        } else if (noSolution) {
            return Solution.NO_SOLUTION;
        } else {
            return Solution.CONTINUE;
        }
    }

    private void drawProgress(ShapeRenderer shape) {
        final float markSize = 20.0f;
        final float halfMark = Maze.CELL_SIZE / 2 - markSize / 2;

        for (var x = 0; x < this.maze.width(); ++x) {
            for (var y = 0; y < this.maze.height(); ++y) {
                if (this.mark[x][y] == this.n) {
                    shape.rect((x + 1) * Maze.CELL_SIZE + halfMark,
                            (this.maze.height() - y) * Maze.CELL_SIZE + halfMark,
                            markSize, markSize);
                }
            }
        }
    }

    private void drawResult(ShapeRenderer shape, Point nLocation) {
        final float markSize = 20.0f;
        final float halfMark = Maze.CELL_SIZE / 2 - markSize / 2;

        shape.ellipse((nLocation.x() + 1) * Maze.CELL_SIZE + halfMark,
                (this.maze.height() - nLocation.y()) * Maze.CELL_SIZE + halfMark,
                markSize, markSize);
        var currentN = this.mark[nLocation.x()][nLocation.y()] - 1;
        if (currentN == 0) {
            return;
        }
        for (var i = 0; i < 4; ++i) {
            var neighbour = new Point(nLocation.x() + Maze.DX[i], nLocation.y() + Maze.DY[i]);

            if (maze.canGo(nLocation, i) && this.mark[neighbour.x()][neighbour.y()] == currentN) {
                drawResult(shape, neighbour);
            }
        }
    }

    public void draw(ShapeRenderer shape) {
        if (this.solution == null) {
            drawProgress(shape);
        } else {
            drawResult(shape, this.solution);
        }
    }
}