#include <fmt/core.h>
#include <string>
#include "algos/rand.hpp"
#include "constants.hpp"
#include "algos/maze.hpp"
#include <algorithm>

using std::string;
using matrix::Matrix;

namespace maze {
  inline bool complete(Matrix& maze, size_t width, size_t height) {
    for(size_t row = 1; row < height; row += 2) {
      for(size_t col = 1; col < width; col += 2) {
        if(maze[row][col] != 0) return false;
      }
    }

    return true;
  }

  std::vector<Point> neighborsAB(Matrix& maze, Point on) {
    std::vector<Point> result;

    std::array<Point, 4> points{{
      {on.x, on.y - 2},
        {on.x, on.y + 2},
        {on.x - 2, on.y},
        {on.x + 2, on.y}
    }};

    for(auto point : points) {
      if(matrix::inbounds(maze, point.x, point.y)) {
        result.push_back(point);
      }
    }

    return result;
  }

  std::vector<Point> neighbors(Matrix& maze, Point on) {
    std::vector<Point> result;

    std::array<Point, 4> points{{
      {on.x, on.y - 2},
        {on.x, on.y + 2},
        {on.x - 2, on.y},
        {on.x + 2, on.y}
    }};

    for(auto point : points) {
      if(matrix::inbounds(maze, point.x, point.y)) {
        if(maze[point.y][point.x] == WALL_VALUE) {
          result.push_back(point);
        }
      }
    }

    return result;
  }

  inline std::pair<Point, Point> find_coord(Matrix& maze, size_t width, size_t height) {
    for(size_t y = 1; y < height; y += 2) {
      for(size_t x = 1; x < width; x += 2) {
        if(maze[y][x] == WALL_VALUE) {
          auto found = neighborsAB(maze, {x, y});

          for(auto point : found) {
            if(maze[point.y][point.x] == 0) {
              return {{x, y}, point};
            }
          }
        }
      }
    }

    matrix::dump("BAD MAZE", maze);
    dbc::sentinel("failed to find coord?");
  }

  bool Builder::room_should_exist(Room& room, bool allow_dupes) {
    // padding by 1 for the perimeter wall
    if(!matrix::inbounds($walls, room.x - 1, room.y - 1) ||
      !matrix::inbounds($walls, room.x + room.width + 2, room.y + room.height + 2))
    {
      return false;
    }

    if(room.overlaps($no_rooms_region)) {
      return false;
    }

    for(auto& other : $rooms) {
      bool is_duped = allow_dupes ? room == other : room != other;

      if(is_duped && room.overlaps(other)) {
        return false;
      }
    }

    // it's in the map and doesn't collide with another room
    return true;
  }

  inline size_t room_sweetspot(size_t width, size_t room_size) {
    if(width < 20) {
      return 4;
    } else if(width < 30) {
      return (width / room_size / 2);
    } if(width < 50) {
      return width / room_size;
    } else {
      return width / 2;
    }
  }

  void Builder::randomize_rooms(size_t room_size) {
    std::shuffle($dead_ends.begin(), $dead_ends.end(), Random::GENERATOR);
    size_t max_rooms = room_sweetspot($width, room_size);

    // use those dead ends to randomly place rooms
    for(auto at : $dead_ends) {
      // don't bother with dead ends near the edge
      if(at.x < 2 || at.y < 2 || at.x > $width - 3 || at.y > $height - 3) continue;

      // quit after we've hit the room max threshold
      if($rooms.size() > max_rooms) break;

      // get the room corners randomized
      std::array<Point, 4> starts{{
        {at.x, at.y}, // top left
          {at.x - room_size + 1, at.y}, // top right
          {at.x - room_size + 1, at.y - room_size + 1}, // bottom right
          {at.x, at.y - room_size + 1} // bottom left
      }};

      size_t offset = Random::uniform(0, 3);

      // BUG: this still accidentally merges rooms
      for(size_t i = 0; i < starts.size(); i++) {
        size_t index = (i + offset) % starts.size();
        Room cur{starts[index].x, starts[index].y, room_size, room_size};

        // if it's out of bounds skip it
        if(room_should_exist(cur)) {
          $rooms.push_back(cur);
          break;
        }
      }
    }
  }

  void Builder::clear() {
    matrix::assign($walls, WALL_VALUE);
  }

  void Builder::divide(Point start, Point end) {
    for(matrix::line it{start, end}; it.next();) {
      $walls[it.y][it.x] = 0;
      $walls[it.y+1][it.x] = 0;
    }
  }

  void Builder::hunt_and_kill(Point on) {
    if($rooms.size() > 0) place_rooms();

    while(!complete($walls, $width, $height)) {
      auto n = neighbors($walls, on);

      if(n.size() == 0) {
        // no neighbors, must be dead end
        add_dead_end(on);
        auto t = find_coord($walls, $width, $height);
        on = t.first;
        $walls[on.y][on.x] = 0;
        size_t row = (on.y + t.second.y) / 2;
        size_t col = (on.x + t.second.x) / 2;
        $walls[row][col] = 0;
      } else {
        // found neighbors, pick random one
        auto nb = n[Random::abs(size_t(0), n.size() - 1)];
        $walls[nb.y][nb.x] = 0;

        size_t row = (nb.y + on.y) / 2;
        size_t col = (nb.x + on.x) / 2;
        $walls[row][col] = 0;
        on = nb;
      }
    }

    if($rooms.size() > 0) place_rooms();
  }

  void Builder::place_rooms() {
    for(auto& room : $rooms) {
      for(matrix::rectangle it{$walls, room.x, room.y, room.width, room.height}; it.next();) {
        $walls[it.y][it.x] = SPACE_VALUE;
      }
    }
  }

  void Builder::inner_donut(float outer_rad, float inner_rad) {
    size_t x = $width / 2;
    size_t y = $height / 2;

    for(matrix::circle it{$walls, {x, y}, outer_rad}; it.next();)
    {
      for(int x = it.left; x < it.right; x++) {
        $walls[it.y][x] = 0;
      }
    }

    for(matrix::circle it{$walls, {x, y}, inner_rad}; it.next();)
    {
      for(int x = it.left; x < it.right; x++) {
        $walls[it.y][x] = 1;
      }
    }
  }

  void Builder::remove_dead_ends() {
    dbc::check($dead_ends.size() > 0, "you have to run an algo first, no dead_ends to remove");

    for(auto at : $dead_ends) {
      for(matrix::compass it{$walls, at.x, at.y}; it.next();) {
        if($walls[it.y][it.x] == SPACE_VALUE) {
          punch_dead_end(at.x, at.y, it.x, it.y);
          break;
        }
      }
    }
  }

  void Builder::dump(const std::string& msg, bool path_too) {
    Matrix wall_copy = $walls;

    // mark the rooms too, but not if pathing
    if(!path_too) {
      for(auto& room : $rooms) {
        for(matrix::rectangle it{wall_copy, room.x, room.y, room.width, room.height};
            it.next();)
        {
          if(wall_copy[it.y][it.x] == 0) {
            wall_copy[it.y][it.x] = ROOM_SPACE_VALUE;
          }
        }
      }
    }

    // mark dead ends
    for(auto at : $dead_ends) {
      // don't mark dead ends if there's something else there
      wall_copy[at.y][at.x] = DEAD_END_VALUE;
    }

    for(auto [at, _] : $doors) {
      wall_copy[at.y][at.x] = DOOR_VALUE;
    }

    if(path_too) {
      for(matrix::each_cell it{wall_copy}; it.next();) {
        if(wall_copy[it.y][it.x] == SPACE_VALUE) {
          wall_copy[it.y][it.x] = $pathing.$paths[it.y][it.x];
        }
      }
    }

    matrix::dump(msg, wall_copy);
  }

  void Builder::enclose() {
    for(matrix::perimeter it{0, 0, $width, $height}; it.next();) {
      $walls[it.y][it.x] = WALL_VALUE;
      Point at{it.x,it.y};
      if($doors.contains(at)) $doors.erase(at);
    }
  }

  void Builder::open_box(size_t outer_size) {
    size_t center_x = $width / 2;
    size_t center_y = $height / 2;

    // compensate for the box's border now
    outer_size++;

    // this can't be right but for now it's working
    size_t x = center_x - outer_size;
    size_t y = center_y - outer_size;
    // BUG: is the + 1 here because the bug in perimeter
    size_t width = (outer_size * 2) + 1;
    size_t height = (outer_size * 2) + 1;

    for(matrix::perimeter p{x, y, width, height}; p.next();) {
      for(matrix::compass it{$walls, p.x, p.y}; it.next();) {
        if($ends_map.contains({it.x, it.y})) {
          $walls[y][x] = 0;
          break;
        }
      }
    }
  }

  bool Builder::valid_door(size_t x, size_t y) {
    return (space_available(x, y - 1) && space_available(x, y + 1)) // north south
      || (space_available(x - 1, y) && space_available(x + 1, y));
  }

  void Builder::place_doors() {
    for(auto room : $rooms) {
      int best_longest = 0;
      Point best_door{0,0};
      bool door_found = false;

      // do an initial pathing check and if it's good then done
      int longest = compute_paths(room.x, room.y);
      if(longest < WALL_PATH_LIMIT && longest > int($width * 2)) continue;

      // can't path out of the room, so now punch a hole until it can
      matrix::perimeter it{room.x - 1, room.y - 1, room.width + 2, room.height + 2};

      while(it.next()) {
        if($walls[it.y][it.x] == WALL_VALUE) {
          // valid doors are free north/south or east/west
          if(!valid_door(it.x, it.y)) continue;

          $walls[it.y][it.x] = SPACE_VALUE;

          longest = compute_paths(room.x, room.y);

          // keep track of the best door so far, which is the one with the longest path
          if(longest != WALL_PATH_LIMIT && longest > best_longest) {
            best_longest = longest;
            best_door = {it.x, it.y};
          }
          $walls[it.y][it.x] = WALL_VALUE;
        }

        dbc::check(best_longest < WALL_PATH_LIMIT, "bad best_longest!");
        if(best_longest > int($width * 2)) break;
      }

      // should now have a door with the longest path
      $walls[best_door.y][best_door.x] = SPACE_VALUE;
      $doors.insert_or_assign(best_door, true);
    }
  }

  void Builder::inner_box(size_t outer_size, size_t inner_size) {
    size_t x = matrix::width($walls) / 2;
    size_t y = matrix::height($walls) / 2;

    for(matrix::box it{$walls, x, y, outer_size}; it.next();)
    {
      $walls[it.y][it.x] = 0;
    }

    for(matrix::box it{$walls, x, y, inner_size}; it.next();)
    {
      $walls[it.y][it.x] = 1;
    }

    // make a fake room that blocks others
    $no_rooms_region = {x - outer_size, y - outer_size, outer_size * 2 + 1, outer_size * 2 + 1};
  }

  void Builder::add_dead_end(Point at) {
    // doing this ensures no dupes, if it's !inserted then it already existed
    auto [_, inserted] = $ends_map.insert_or_assign(at, true);

    // so skip it, it isn't new
    if(inserted) {
      $dead_ends.push_back(at);
    }
  }

  int Builder::compute_paths(size_t x, size_t y) {
    Point test{x, y};
    $pathing.set_target(test);
    int longest = $pathing.compute_paths($walls);
    // $pathing.dump("AFTER COMPUTE");
    $pathing.clear_target(test);
    return longest;
  }

  bool Builder::validate() {
    size_t width = matrix::width($walls);
    size_t height = matrix::height($walls);

    // no rooms can overlap
    for(auto& room : $rooms) {
      if(!room_should_exist(room)) return false;
    }

    for(matrix::perimeter it{0, 0, width, height}; it.next();) {
      if($ends_map.contains({it.x, it.y})) return false;
      if($doors.contains({it.x, it.y})) return false;
      if($walls[it.y][it.x] != WALL_VALUE) return false;
    }

    if($rooms.size() <= 1) return true;

    // initial path test can just use one room then look for
    // any cells that are empty in the walls map but unpathed in the paths
    Room test_room = $rooms.at(Random::abs(size_t(0), $rooms.size() - 1));
    compute_paths(test_room.x, test_room.y);

    for(matrix::each_cell it{$walls}; it.next();) {
      if($walls[it.y][it.x] == SPACE_VALUE &&
          $pathing.$paths[it.y][it.x] == WALL_PATH_LIMIT) {
        return false;
      }
    }

    return true;
  }

  bool Builder::space_available(size_t x, size_t y) {
    return (matrix::inbounds($walls, x, y) && // in bounds
            $walls[y][x] == SPACE_VALUE && // is a space
            !$doors.contains({x, y}) && // no door there
            (x > 0 && y > 0 && x < $width - 2 && y < $height - 2)); // not perimeter;
  }

  void Builder::punch_dead_end(size_t at_x, size_t at_y, size_t x, size_t y) {
    int diff_x = at_x - x;
    int diff_y = at_y - y;
    $walls[at_y + diff_y][at_x + diff_x] = SPACE_VALUE;
  }

  bool Builder::repair() {
    enclose();
    // if it's already valid then done
    if(validate()) return true;

    std::vector<Point> removed_ends;
    bool now_valid = false;

    for(auto& at : $dead_ends) {
      // punch a hole for this dead end
      for(matrix::compass it{$walls, at.x, at.y}; it.next();) {
        if($walls[it.y][it.x] == SPACE_VALUE) {
          punch_dead_end(at.x, at.y, it.x, it.y);
          removed_ends.push_back({it.x, it.y});
          break;
        }
      }

      // if that validates it then done
      if(validate()) {
        now_valid = true;
        break;
      }
    }

    // now go back and see if we can add any back
    for(auto& at : removed_ends) {
      auto temp = $walls[at.y][at.x];
      $walls[at.y][at.x] = WALL_VALUE;

      if(!validate()) {
        $walls[at.y][at.x] = temp;
      }
    }

    enclose();
    return validate();
  }

  std::pair<Builder, bool> script(Map& map, nlohmann::json& config) {
    maze::Builder maze(map);

    for(auto& action : config) {
      std::string aname = action["action"];

      if(aname == "hunt_and_kill") {
        maze.hunt_and_kill();
      } else if(aname == "clear") {
        maze.clear();
      } else if(aname == "inner_box") {
        std::vector<int> data = action["data"];
        maze.inner_box(data[0], data[1]);
      } else if(aname == "randomize_rooms") {
        std::vector<int> data = action["data"];
        maze.randomize_rooms(data[0]);
      } else if(aname == "open_box") {
        std::vector<int> data = action["data"];
        maze.open_box(data[0]);
      } else if(aname == "place_doors") {
        maze.place_doors();
      } else if(aname == "divide") {
        std::vector<size_t> data = action["data"];
        maze.divide({data[0], data[1]}, {data[2], data[3]});
      } else if(aname == "inner_donut") {
        std::vector<float> data = action["data"];
        maze.inner_donut(data[0], data[1]);
      } else if(aname == "remove_dead_ends") {
        maze.remove_dead_ends();
      } else if(aname == "enclose") {
        maze.enclose();
      } else {
        dbc::sentinel(fmt::format("Invalid maze action {}", aname));
      }
    }

    bool valid = maze.repair();

    return {maze, valid};
  }
}
