///|
fn grid_min(a : Int, b : Int) -> Int {
  if a < b {
    a
  } else {
    b
  }
}

///|
fn grid_max(a : Int, b : Int) -> Int {
  if a > b {
    a
  } else {
    b
  }
}

///|
fn rect_intersection_area(
  ax : Int,
  ay : Int,
  aw : Int,
  ah : Int,
  bx : Int,
  by : Int,
  bw : Int,
  bh : Int,
) -> Int {
  let left = grid_max(ax, bx)
  let top = grid_max(ay, by)
  let right = grid_min(ax + aw, bx + bw)
  let bottom = grid_min(ay + ah, by + bh)
  if right <= left || bottom <= top {
    0
  } else {
    (right - left) * (bottom - top)
  }
}

///|
fn placed_cell_overlap(placed : Placed, cell : DensityCell) -> Int {
  rect_intersection_area(
    placed.x,
    placed.y,
    placed.width,
    placed.height,
    cell.x,
    cell.y,
    cell.width,
    cell.height,
  )
}

///|
fn cell_width_at(layout : Layout, col : Int, cell_width : Int) -> Int {
  let start = col * cell_width
  grid_min(cell_width, layout.bin.width - start)
}

///|
fn cell_height_at(layout : Layout, row : Int, cell_height : Int) -> Int {
  let start = row * cell_height
  grid_min(cell_height, layout.bin.height - start)
}

///|
fn empty_density_cell(
  col : Int,
  row : Int,
  x : Int,
  y : Int,
  width : Int,
  height : Int,
) -> DensityCell {
  DensityCell::{
    col,
    row,
    x,
    y,
    width,
    height,
    used_area: 0,
    capacity: width * height,
    occupancy_permille: 0,
  }
}

///|
fn measure_density_cell(
  layout : Layout,
  col : Int,
  row : Int,
  cell_width : Int,
  cell_height : Int,
) -> DensityCell {
  let x = col * cell_width
  let y = row * cell_height
  let width = cell_width_at(layout, col, cell_width)
  let height = cell_height_at(layout, row, cell_height)
  let mut cell = empty_density_cell(col, row, x, y, width, height)
  let mut used = 0
  for placed in layout.placements {
    used = used + placed_cell_overlap(placed, cell)
  }
  cell = DensityCell::{
    col,
    row,
    x,
    y,
    width,
    height,
    used_area: used,
    capacity: width * height,
    occupancy_permille: scale_permille(used, width * height),
  }
  cell
}

///|
fn count_occupied_cells(cells : ArrayView[DensityCell]) -> Int {
  let mut count = 0
  for cell in cells {
    if cell.used_area > 0 {
      count = count + 1
    }
  }
  count
}

///|
fn densest_cell(cells : ArrayView[DensityCell]) -> DensityCell {
  let mut best = cells[0]
  for cell in cells {
    if cell.occupancy_permille > best.occupancy_permille {
      best = cell
    } else if cell.occupancy_permille == best.occupancy_permille &&
      cell.used_area > best.used_area {
      best = cell
    }
  }
  best
}

///|
fn sparsest_cell(cells : ArrayView[DensityCell]) -> DensityCell {
  let mut best = cells[0]
  for cell in cells {
    if cell.occupancy_permille < best.occupancy_permille {
      best = cell
    } else if cell.occupancy_permille == best.occupancy_permille &&
      cell.capacity > best.capacity {
      best = cell
    }
  }
  best
}

///|
/// Build a coarse density grid for a validated layout.
pub fn density_grid(
  layout : Layout,
  cell_width? : Int = 8,
  cell_height? : Int = 8,
) -> Result[GridReport, PackError] {
  if cell_width <= 0 || cell_height <= 0 {
    return Err(InvalidCellSize(width=cell_width, height=cell_height))
  }
  match validate_layout(layout) {
    Err(err) => return Err(err)
    Ok(_) => ()
  }
  let cols = ceil_div(layout.bin.width, cell_width)
  let rows = ceil_div(layout.bin.height, cell_height)
  let cells : Array[DensityCell] = []
  for row in 0.. Char {
  if permille == 0 {
    '.'
  } else if permille < 250 {
    ':'
  } else if permille < 500 {
    '+'
  } else if permille < 750 {
    '*'
  } else if permille < 1000 {
    '#'
  } else {
    '@'
  }
}

///|
/// Render density grid as a compact heatmap.
pub fn to_heatmap_preview(report : GridReport) -> String {
  let out = StringBuilder()
  for row in 0.. String {
  let out = StringBuilder()
  out.write_string(
    "row,col,x,y,width,height,used_area,capacity,occupancy_permille\n",
  )
  for cell in report.cells {
    out.write_string("\{cell.row},")
    out.write_string("\{cell.col},")
    out.write_string("\{cell.x},")
    out.write_string("\{cell.y},")
    out.write_string("\{cell.width},")
    out.write_string("\{cell.height},")
    out.write_string("\{cell.used_area},")
    out.write_string("\{cell.capacity},")
    out.write_string("\{cell.occupancy_permille}")
    out.write_char('\n')
  }
  out.to_string()
}

///|
fn write_cell_summary(
  out : StringBuilder,
  label : String,
  cell : DensityCell,
) -> Unit {
  out.write_string(label)
  out.write_string(": row=")
  out.write_string("\{cell.row}")
  out.write_string(" col=")
  out.write_string("\{cell.col}")
  out.write_string(" used=")
  out.write_string("\{cell.used_area}")
  out.write_string("/")
  out.write_string("\{cell.capacity}")
  out.write_string(" occ=")
  out.write_string("\{cell.occupancy_permille}/1000")
  out.write_char('\n')
}

///|
/// Human-readable grid report.
pub fn to_density_report(report : GridReport) -> String {
  let out = StringBuilder()
  out.write_string("rectloom density grid\n")
  out.write_string("cells=")
  out.write_string("\{report.cells.length()}")
  out.write_string(" cols=")
  out.write_string("\{report.cols}")
  out.write_string(" rows=")
  out.write_string("\{report.rows}")
  out.write_string(" cell=")
  out.write_string("\{report.cell_width}x\{report.cell_height}")
  out.write_char('\n')
  out.write_string("occupied_cells=")
  out.write_string("\{report.occupied_cells}")
  out.write_string(" empty_cells=")
  out.write_string("\{report.empty_cells}")
  out.write_char('\n')
  write_cell_summary(out, "densest", report.densest_cell)
  write_cell_summary(out, "sparsest", report.sparsest_cell)
  out.write_string("heatmap:\n")
  out.write_string(to_heatmap_preview(report))
  out.write_char('\n')
  out.to_string()
}

///|
fn cell_has_point(cell : DensityCell, x : Int, y : Int) -> Bool {
  x >= cell.x &&
  y >= cell.y &&
  x < cell.x + cell.width &&
  y < cell.y + cell.height
}

///|
/// Find the density cell that contains a point.
pub fn find_density_cell(report : GridReport, x : Int, y : Int) -> DensityCell? {
  for cell in report.cells {
    if cell_has_point(cell, x, y) {
      return Some(cell)
    }
  }
  None
}

///|
/// Count placements touching a coarse grid cell.
pub fn placements_touching_cell(
  layout : Layout,
  cell : DensityCell,
) -> Result[Int, PackError] {
  match validate_layout(layout) {
    Err(err) => return Err(err)
    Ok(_) => ()
  }
  let mut count = 0
  for placed in layout.placements {
    if placed_cell_overlap(placed, cell) > 0 {
      count = count + 1
    }
  }
  Ok(count)
}

///|
/// Stable compact signature useful for snapshot tests.
pub fn layout_signature(layout : Layout) -> Result[String, PackError] {
  match validate_layout(layout) {
    Err(err) => return Err(err)
    Ok(_) => ()
  }
  let out = StringBuilder()
  out.write_string("\{layout.bin.width}x\{layout.bin.height}:")
  out.write_string(algorithm_name(layout.algorithm))
  out.write_string(":")
  for i in 0..