///|
/// A 2D grid map for pathfinding.
///
/// Cells are stored in row-major order:
///   index(x, y) = y * width + x
pub struct Grid {
  priv width : Int
  priv height : Int
  priv cells : Array[Cell]
}

///|
fn valid_dimensions(width : Int, height : Int) -> Bool {
  width >= 1 && height >= 1 && width <= 2147483647 / height
}

///|
/// Creates an empty Grid where all cells are traversable (Cell::Empty).
///
/// # Arguments
/// * `width`  - number of columns (must be > 0)
/// * `height` - number of rows    (must be > 0)
///
/// Returns a 1x1 grid when dimensions are non-positive or their cell count
/// would overflow `Int`. Use `try_new` when invalid input must be reported.
pub fn Grid::new(width : Int, height : Int) -> Grid {
  let valid = valid_dimensions(width, height)
  let w = if valid { width } else { 1 }
  let h = if valid { height } else { 1 }
  let size = w * h
  let cells = Array::make(size, Cell::Empty)
  { width: w, height: h, cells }
}

///|
/// Creates a Grid, returning `None` for non-positive or overflowing dimensions.
pub fn Grid::try_new(width : Int, height : Int) -> Grid? {
  if !valid_dimensions(width, height) {
    return None
  }
  Some(Grid::new(width, height))
}

///|
/// Creates a Grid from an existing array of cells.
///
/// Returns `None` for invalid dimensions, non-positive terrain weights, or a
/// cell array length that does not match `width * height`.
pub fn Grid::from_cells(
  width : Int,
  height : Int,
  cells : Array[Cell],
) -> Grid? {
  if !valid_dimensions(width, height) || cells.length() != width * height {
    return None
  }
  for cell in cells {
    if !cell.is_valid() {
      return None
    }
  }
  let copied_cells = Array::make(cells.length(), Cell::Empty)
  for index = 0; index < cells.length(); index = index + 1 {
    copied_cells[index] = cells[index]
  }
  Some({ width, height, cells: copied_cells })
}

///|
/// Converts 2D coordinates to the linear cell array index.
fn Grid::index(self : Grid, x : Int, y : Int) -> Int {
  y * self.width + x
}

///|
/// Returns the total number of cells in the grid.
pub fn Grid::size(self : Grid) -> Int {
  self.width * self.height
}

///|
/// Returns the number of columns in the grid.
pub fn Grid::width(self : Grid) -> Int {
  self.width
}

///|
/// Returns the number of rows in the grid.
pub fn Grid::height(self : Grid) -> Int {
  self.height
}

///|
/// Checks if a point is within the grid bounds.
pub fn Grid::in_bounds(self : Grid, p : Point) -> Bool {
  p.x >= 0 && p.x < self.width && p.y >= 0 && p.y < self.height
}

///|
/// Checks if a cell is passable (exists in bounds and is not Blocked).
pub fn Grid::is_passable(self : Grid, p : Point) -> Bool {
  if !self.in_bounds(p) {
    return false
  }
  let cell = self.get_cell(p.x, p.y)
  cell.is_passable()
}

///|
/// Checks if a cell is passable by raw coordinates.
pub fn Grid::is_passable_xy(self : Grid, x : Int, y : Int) -> Bool {
  if x < 0 || x >= self.width || y < 0 || y >= self.height {
    return false
  }
  let idx = self.index(x, y)
  self.cells[idx].is_passable()
}

///|
/// Returns the traversal cost at (x, y). Returns -1.0 for blocked cells
/// and out-of-bounds positions.
pub fn Grid::cost(self : Grid, x : Int, y : Int) -> Double {
  if x < 0 || x >= self.width || y < 0 || y >= self.height {
    return -1.0
  }
  let idx = self.index(x, y)
  self.cells[idx].cost()
}

///|
/// Returns the traversal cost at a point. Returns -1.0 for blocked cells.
pub fn Grid::cost_at(self : Grid, p : Point) -> Double {
  self.cost(p.x, p.y)
}

///|
/// Returns the cell at (x, y), or `Blocked` when out of bounds.
pub fn Grid::get_cell(self : Grid, x : Int, y : Int) -> Cell {
  if x < 0 || x >= self.width || y < 0 || y >= self.height {
    return Cell::Blocked
  }
  self.cells[self.index(x, y)]
}

///|
/// Returns the cell at a point, or `Blocked` when out of bounds.
pub fn Grid::get_cell_at(self : Grid, p : Point) -> Cell {
  self.get_cell(p.x, p.y)
}

///|
/// Returns the cell at (x, y), or `None` when the coordinates are out of bounds.
pub fn Grid::try_get_cell(self : Grid, x : Int, y : Int) -> Cell? {
  if x < 0 || x >= self.width || y < 0 || y >= self.height {
    return None
  }
  Some(self.cells[self.index(x, y)])
}

///|
/// Sets the Cell at (x, y). Returns a new Grid (immutable style).
/// Invalid coordinates and non-positive weighted cells leave the grid unchanged.
pub fn Grid::set_cell(self : Grid, x : Int, y : Int, cell : Cell) -> Grid {
  if x < 0 || x >= self.width || y < 0 || y >= self.height {
    return self
  }
  if !cell.is_valid() {
    return self
  }
  let idx = self.index(x, y)
  let new_cells = Array::make(self.cells.length(), Cell::Empty)
  for i = 0; i < self.cells.length(); i = i + 1 {
    new_cells[i] = self.cells[i]
  }
  new_cells[idx] = cell
  { width: self.width, height: self.height, cells: new_cells }
}

///|
/// Tries to set one cell, returning `None` for invalid coordinates or terrain.
pub fn Grid::try_set_cell(self : Grid, x : Int, y : Int, cell : Cell) -> Grid? {
  if x < 0 || x >= self.width || y < 0 || y >= self.height || !cell.is_valid() {
    return None
  }
  Some(self.set_cell(x, y, cell))
}

///|
/// Applies multiple cell updates with a single grid copy.
///
/// Out-of-bounds points and invalid weighted cells are ignored. Prefer this
/// method when loading maps or placing many obstacles: it runs in O(N + K)
/// for N grid cells and K updates, while K chained `set_cell` calls copy the
/// grid K times.
pub fn Grid::set_cells(self : Grid, updates : Array[(Point, Cell)]) -> Grid {
  let new_cells = Array::make(self.cells.length(), Cell::Empty)
  for index = 0; index < self.cells.length(); index = index + 1 {
    new_cells[index] = self.cells[index]
  }
  for update in updates {
    let (point, cell) = update
    if self.in_bounds(point) && cell.is_valid() {
      new_cells[self.index(point.x, point.y)] = cell
    }
  }
  { width: self.width, height: self.height, cells: new_cells }
}

///|
/// Sets a wall (Blocked cell) at (x, y).
pub fn Grid::set_wall(self : Grid, x : Int, y : Int) -> Grid {
  self.set_cell(x, y, Cell::Blocked)
}

///|
/// Sets a positive weighted cell at (x, y); invalid input leaves the grid unchanged.
pub fn Grid::set_weighted(self : Grid, x : Int, y : Int, weight : Int) -> Grid {
  self.set_cell(x, y, Cell::Weighted(weight))
}

///|
/// Tries to set positive weighted terrain and reports invalid input as `None`.
pub fn Grid::try_set_weighted(
  self : Grid,
  x : Int,
  y : Int,
  weight : Int,
) -> Grid? {
  self.try_set_cell(x, y, Cell::Weighted(weight))
}

///|
/// Checks if start and goal are both valid for pathfinding.
pub fn Grid::is_valid_search(self : Grid, start : Point, goal : Point) -> Bool {
  self.in_bounds(start) &&
  self.in_bounds(goal) &&
  self.is_passable(start) &&
  self.is_passable(goal)
}

///|
/// Counts the number of blocked cells in the grid.
pub fn Grid::num_walls(self : Grid) -> Int {
  let mut count = 0
  for i = 0; i < self.cells.length(); i = i + 1 {
    match self.cells[i] {
      Cell::Blocked => count = count + 1
      _ => ()
    }
  }
  count
}

///|
/// Counts the number of passable cells in the grid.
pub fn Grid::num_passable(self : Grid) -> Int {
  self.size() - self.num_walls()
}

///|
/// Returns a copy of the grid with all cells reset to Empty.
pub fn Grid::clear(self : Grid) -> Grid {
  let cells = Array::make(self.size(), Cell::Empty)
  { width: self.width, height: self.height, cells }
}