package maze;

import java.util.ArrayDeque;
import java.util.Random;
import java.util.Set;
import java.util.stream.Stream;
import static java.util.stream.Collectors.*;
import static java.util.stream.IntStream.*;

import maze.CanvasArea.Brush;

public class Maze {
  static class Room {
    final int x, y;
    Room(int x, int y) { this.x = x; this.y = y; }
  }
  
  public static boolean[][] generateMaze(Random random, int width, int height) {
    boolean[][] cells = new boolean[1 + 2 * width][1 + 2 * height];
    Set<Room> notVisited =       
      range(0, width * height).mapToObj(i -> new Room(i % width, i % height)).collect(toSet());
    
    Room current = notVisited.iterator().next();   // get first
    cells[1 + 2 * current.x][1 + 2 * current.y] = true;  // create the room
    notVisited.remove(current);  // avoid to visit the same room twice

    ArrayDeque<Room> stack = new ArrayDeque<>();
    for(;;) {
      Room neighbor = pickANeighbor(random, current.x, current.y, width, height, notVisited);
      if (neighbor != null) {
        stack.push(current);
        cells[1 + current.x + neighbor.x][1 + current.y + neighbor.y] = true;  // create a gate between the two rooms 
        cells[1 + 2 * neighbor.x][1 + 2 * neighbor.y] = true;  // create the new room
        notVisited.remove(neighbor);
        current = neighbor;
        continue;
      }
      if (!stack.isEmpty()) {
        current = stack.pop();
        continue;
      }
      if (notVisited.isEmpty()) {
        break;
      }
      current = notVisited.iterator().next();   // get first
      cells[1 + 2 * current.x][1 + 2 * current.y] = true;
      notVisited.remove(current);
    }
    return cells;
  }

  // pick a room inside the set possibleNeighBors that is a neighbor of the room (x, y)
  private static Room pickANeighbor(Random random, int x, int y, int width, int height, Set<Room> possibleNeighbors) {
    Room[] neightbors =
        Stream.of(new Room(x - 1, y), new Room(x + 1, y), new Room(x, y - 1), new Room(x, y + 1))
          .filter(cell -> cell.x >= 0 && cell.x < width && cell.y >= 0 && cell.y < height
                          && !possibleNeighbors.contains(cell))
          .toArray(Room[]::new);
    return (neightbors.length == 0)? null: neightbors[random.nextInt(neightbors.length)];
  }

  public static void main(String[] args) {
    int w = 60, canvasW = (w * 2 + 1);
    int h = 32, canvasH = (h * 2 + 1);

    CanvasArea area = new CanvasArea("Maze", canvasW * 5, canvasH * 5);
    area.clear(Brush.BLACK);
    boolean[][] cells = generateMaze(new Random(0), w, h);
    for(int i = 0; i < canvasW; i++) {
      for(int j = 0; j < canvasH; j++) {
        if (cells[i][j]) {
          area.drawRectangle(i * 5, j * 5, 5, 5, Brush.PINK.asOpaque());
        }
      }
    }
  }
}