package net.caraus.labyrinth;

import java.util.ArrayList;
import java.util.Random;

public final class KruskalMaze {
    private Maze theMaze;
    private int[][] mark;

    public KruskalMaze(int width, int height) {
        this.theMaze = new Maze(width, height);
    }

    private void breakWall(Wall wall) {
        if (wall.delta().x() == -1) {
            this.theMaze.at(wall.xy()).leftWall(false);
        } else if (wall.delta().x() == 1) {
            this.theMaze.at(wall.xy().x() + 1, wall.xy().y()).leftWall(false);
        } else if (wall.delta().y() == -1) {
            this.theMaze.at(wall.xy()).upWall(false);
        } else {
            this.theMaze.at(wall.xy().x(), wall.xy().y() + 1).upWall(false);
        }
    }

    public boolean isConnected(Point start, Point finish) {
        this.mark = new int[this.theMaze.width()][this.theMaze.height()]; // Метки локаций.

        for (int x = 0; x < this.theMaze.width(); ++x) {
            for (int y = 0; y < this.theMaze.height(); ++y) {
                this.mark[x][y] = 0;
            }
        }
        this.mark[start.x()][start.y()] = 1;

        return solve(start, finish);
    }

    private boolean solve(Point start, Point finish) {
        // Используем алгоритм волновой трассировки.
        int n = 1;

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

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

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

                        if (neighbour.x() == finish.x() && neighbour.y() == finish.y()) {
                            return true;
                        }
                    }
                }
            }
            locations = nextLocations;
            ++n;
        } while (!locations.isEmpty());

        return false;
    }

    public Maze generate() {
        final var wallCount = (this.theMaze.width() - 1) * this.theMaze.height()
            + (this.theMaze.height() - 1) * this.theMaze.width();
        ArrayList<Wall> walls = new ArrayList<>(wallCount);
        ArrayList<Double> temp = new ArrayList<>(wallCount);
        var random = new Random();

        // Заполнение массива Temp случайными числами.
        for (int i = 0; i < wallCount; ++i) {
            temp.add(random.nextDouble());
        }
        // Заполнение массива стен.
        // Сначала все горизонтальные.
        for (var i = 1; i < this.theMaze.width(); ++i) {
            for (var j = 0; j < this.theMaze.height(); ++j) {
                walls.add(new Wall(new Point(i, j), new Point(-1, 0)));
            }
        }
        // Затем все вертикальные.
        for (var i = 0; i < this.theMaze.width(); ++i) {
            for (var j = 1; j < this.theMaze.height(); ++j) {
                walls.add(new Wall(new Point(i, j), new Point(0, -1)));
            }
        }
        for (var i = 0; i < wallCount; ++i) {
            for (var j = i; j < wallCount; ++j) {
                // Перемешиваем массив стен.
                if (temp.get(i) > temp.get(j)) {
                    var tempr = temp.get(i);
                    temp.set(i, temp.get(j));
                    temp.set(j, tempr);

                    var tempw = walls.get(i);
                    walls.set(i, walls.get(j));
                    walls.set(j, tempw);
                }
            }
        }
        var locations = this.theMaze.width() * this.theMaze.height();
        int i = 0;
        while (locations > 1) {
            var curWall = walls.get(i);
            ++i;
            if (!isConnected(curWall.xy(), curWall.end())) {
                breakWall(curWall);
                --locations;
            }
        }
        return this.theMaze;
    }
}