function median(values: number[]): number {
  if (!values.length) return 0
  const sorted = [...values].sort((a, b) => a - b)
  const mid = Math.floor(sorted.length / 2)
  return sorted.length % 2 === 0 ? 0.5 * (sorted[mid - 1] + sorted[mid]) : sorted[mid]
}

function uniqSorted(lines: number[], extent: number): number[] {
  const out = Array.from(
    new Set(
      (lines ?? [])
        .filter((v) => Number.isFinite(v))
        .map((v) => Math.round(v))
        .filter((v) => v >= 0 && v <= extent),
    ),
  ).sort((a, b) => a - b)
  if (!out.length || out[0] !== 0) out.unshift(0)
  if (out[out.length - 1] !== extent) out.push(extent)
  return out
}

export type TilePatternRenderInput = {
  patternImage: CanvasImageSource
  canvasSize: { w: number; h: number }
  grid: { vlines: number[]; hlines: number[] }
  tilePaddingPx?: number
}

export type TilePatternRenderOutput = {
  imageData: ImageData
  tileW: number
  tileH: number
  vlines: number[]
  hlines: number[]
}

/**
 * Renders a full-frame image-space tile pattern aligned to a grid.
 * No homography / no perspective warp: each grid cell gets a scaled copy of the pattern image.
 */
export function renderTilePatternImageData(input: TilePatternRenderInput): TilePatternRenderOutput {
  const w = Math.max(1, Math.round(input.canvasSize.w))
  const h = Math.max(1, Math.round(input.canvasSize.h))
  const padding = Math.max(0, Math.round(input.tilePaddingPx ?? 0))

  let v = uniqSorted(input.grid?.vlines ?? [], w)
  const hl = uniqSorted(input.grid?.hlines ?? [], h)

  const diffsX: number[] = []
  for (let i = 0; i + 1 < v.length; i++) diffsX.push(Math.max(1, v[i + 1] - v[i]))
  const diffsY: number[] = []
  for (let i = 0; i + 1 < hl.length; i++) diffsY.push(Math.max(1, hl[i + 1] - hl[i]))
  let tileW = Math.max(1, Math.round(median(diffsX)))
  const tileH = Math.max(1, Math.round(median(diffsY)))

  // If some vertical grid spans are too wide vs tile height, subdivide them locally.
  if (tileH > 0 && v.length >= 2) {
    const refined: number[] = []
    const maxSpan = tileH * 1.6
    for (let i = 0; i + 1 < v.length; i++) {
      const x0 = v[i]
      const x1 = v[i + 1]
      const span = Math.max(1, x1 - x0)
      const splits = span > maxSpan ? Math.min(8, Math.max(2, Math.round(span / tileH))) : 1
      const step = span / splits
      for (let k = 0; k < splits; k++) refined.push(Math.round(x0 + k * step))
    }
    refined.push(v[v.length - 1])
    v = uniqSorted(refined, w)
    const diffsX2: number[] = []
    for (let i = 0; i + 1 < v.length; i++) diffsX2.push(Math.max(1, v[i + 1] - v[i]))
    tileW = Math.max(1, Math.round(median(diffsX2)))
  }

  // If the grid detector merged multiple columns, subdivide wide cells so tile width matches height.
  if (tileH > 0) {
    let ratio = tileW / tileH
    let iter = 0
    while (ratio > 1.6 && iter < 3) {
      const factor = Math.max(2, Math.min(6, Math.round(ratio)))
      const refined: number[] = []
      for (let i = 0; i + 1 < v.length; i++) {
        const x0 = v[i]
        const x1 = v[i + 1]
        const step = (x1 - x0) / factor
        for (let k = 0; k < factor; k++) refined.push(Math.round(x0 + k * step))
      }
      refined.push(v[v.length - 1])
      v = uniqSorted(refined, w)
      const diffsX2: number[] = []
      for (let i = 0; i + 1 < v.length; i++) diffsX2.push(Math.max(1, v[i + 1] - v[i]))
      tileW = Math.max(1, Math.round(median(diffsX2)))
      ratio = tileW / tileH
      iter += 1
    }
  }

  // If vertical grid lines are too sparse vs horizontal lines, rebuild columns using tileH spacing.
  if (tileH > 0) {
    const sparseV = v.length < Math.max(4, Math.round(hl.length * 0.5))
    const wideRatio = tileW / tileH > 1.8
    if (sparseV || wideRatio) {
      const start = v[0] ?? 0
      const end = v[v.length - 1] ?? w
      const refined: number[] = []
      const step = Math.max(1, tileH)
      for (let x = start; x <= end + 0.5; x += step) refined.push(Math.round(x))
      if (refined[refined.length - 1] !== Math.round(end)) refined.push(Math.round(end))
      v = uniqSorted(refined, w)
      const diffsX3: number[] = []
      for (let i = 0; i + 1 < v.length; i++) diffsX3.push(Math.max(1, v[i + 1] - v[i]))
      tileW = Math.max(1, Math.round(median(diffsX3)))
    }
  }

  const canvas = document.createElement('canvas')
  canvas.width = w
  canvas.height = h
  const ctx = canvas.getContext('2d')!
  ctx.clearRect(0, 0, w, h)

  for (let r = 0; r + 1 < hl.length; r++) {
    const y0 = hl[r]
    const y1 = hl[r + 1]
    for (let c = 0; c + 1 < v.length; c++) {
      const x0 = v[c]
      const x1 = v[c + 1]
      const px = x0 + padding
      const py = y0 + padding
      const pw = Math.max(0, x1 - x0 - 2 * padding)
      const ph = Math.max(0, y1 - y0 - 2 * padding)
      if (pw <= 0 || ph <= 0) continue
      ctx.drawImage(input.patternImage, px, py, pw, ph)
    }
  }

  const imageData = ctx.getImageData(0, 0, w, h)
  return { imageData, tileW, tileH, vlines: v, hlines: hl }
}