// Squarified treemap (Bruls, Huijsen, van Wijk, 2000).
//
// Pure TS, no deps. Returns laid-out rectangles in container percentages.

export interface Sized {
  /** Non-negative weight; floored to a minimum by the caller. */
  weight: number
}

export interface Rect {
  x: number
  y: number
  w: number
  h: number
}

export type Laid<T extends Sized> = T & Rect

export function squarify<T extends Sized>(
  items: readonly T[],
  container: { w: number; h: number } = { w: 100, h: 100 }
): Array<Laid<T>> {
  if (items.length === 0) return []

  const totalWeight = items.reduce((s, it) => s + Math.max(0, it.weight), 0)
  if (totalWeight <= 0) {
    return items.map((it) => ({ ...it, x: 0, y: 0, w: 0, h: 0 }))
  }

  const totalArea = container.w * container.h
  const sorted = [...items].sort((a, b) => b.weight - a.weight)
  const sized = sorted.map((it) => ({
    item: it,
    area: (Math.max(0, it.weight) / totalWeight) * totalArea,
  }))

  const out: Array<Laid<T>> = []
  layout(sized, { x: 0, y: 0, w: container.w, h: container.h }, out)
  return out
}

interface Sized2<T> {
  item: T
  area: number
}

function layout<T extends Sized>(
  rest: Array<Sized2<T>>,
  region: Rect,
  out: Array<Laid<T>>
): void {
  let pending: Array<Sized2<T>> = []
  let cur = region

  for (const s of rest) {
    if (pending.length === 0) {
      pending.push(s)
      continue
    }
    const next = [...pending, s]
    if (worst(next, shorterSide(cur)) <= worst(pending, shorterSide(cur))) {
      pending = next
    } else {
      const { rectsConsumed, remaining } = placeRow(pending, cur)
      for (const r of rectsConsumed) out.push(r as Laid<T>)
      cur = remaining
      pending = [s]
    }
  }
  if (pending.length > 0) {
    const { rectsConsumed } = placeRow(pending, cur)
    for (const r of rectsConsumed) out.push(r as Laid<T>)
  }
}

function shorterSide(r: Rect): number {
  return Math.min(r.w, r.h)
}

function worst<T>(row: Array<Sized2<T>>, w: number): number {
  let sum = 0
  let max = -Infinity
  let min = Infinity
  for (const r of row) {
    sum += r.area
    if (r.area > max) max = r.area
    if (r.area < min) min = r.area
  }
  if (sum <= 0) return Infinity
  const w2 = w * w
  const sum2 = sum * sum
  return Math.max((w2 * max) / sum2, sum2 / (w2 * min))
}

function placeRow<T extends Sized>(
  row: Array<Sized2<T>>,
  region: Rect
): { rectsConsumed: Array<Laid<T>>; remaining: Rect } {
  const rowSum = row.reduce((s, r) => s + r.area, 0)
  const horizontal = region.w >= region.h
  const out: Array<Laid<T>> = []

  if (horizontal) {
    const rowW = rowSum / region.h
    let y = region.y
    for (const r of row) {
      const h = r.area / rowW
      out.push({ ...r.item, x: region.x, y, w: rowW, h } as Laid<T>)
      y += h
    }
    return {
      rectsConsumed: out,
      remaining: {
        x: region.x + rowW,
        y: region.y,
        w: region.w - rowW,
        h: region.h,
      },
    }
  } else {
    const rowH = rowSum / region.w
    let x = region.x
    for (const r of row) {
      const w = r.area / rowH
      out.push({ ...r.item, x, y: region.y, w, h: rowH } as Laid<T>)
      x += w
    }
    return {
      rectsConsumed: out,
      remaining: {
        x: region.x,
        y: region.y + rowH,
        w: region.w,
        h: region.h - rowH,
      },
    }
  }
}