///|
priv struct FreeRect {
  x : Int
  y : Int
  width : Int
  height : Int
}

///|
fn rect_area(rect : Rect) -> Int {
  rect.width * rect.height
}

///|
fn placed_area(placed : Placed) -> Int {
  placed.width * placed.height
}

///|
fn bin_area(bin : Bin) -> Int {
  bin.width * bin.height
}

///|
fn right_limit(options : PackOptions) -> Int {
  options.bin.width - options.padding.outer
}

///|
fn bottom_limit(options : PackOptions) -> Int {
  options.bin.height - options.padding.outer
}

///|
fn total_placed_area(placements : ArrayView[Placed]) -> Int {
  let mut area = 0
  for placed in placements {
    area = area + placed_area(placed)
  }
  area
}

///|
fn occupancy_permille(bin : Bin, placements : ArrayView[Placed]) -> Int {
  let area = bin_area(bin)
  if area <= 0 {
    0
  } else {
    total_placed_area(placements) * 1000 / area
  }
}

///|
fn waste_area(bin : Bin, placements : ArrayView[Placed]) -> Int {
  bin_area(bin) - total_placed_area(placements)
}

///|
fn make_layout(
  bin : Bin,
  placements : Array[Placed],
  unpacked : Array[Rect],
  algorithm : Algorithm,
) -> Layout {
  Layout::{
    bin,
    placements,
    unpacked,
    algorithm,
    occupancy_permille: occupancy_permille(bin, placements),
    waste_area: waste_area(bin, placements),
  }
}

///|
fn make_placed(
  rect : Rect,
  x : Int,
  y : Int,
  width : Int,
  height : Int,
) -> Placed {
  Placed::{
    id: rect.id,
    x,
    y,
    width,
    height,
    rotated: width != rect.width || height != rect.height,
    original_width: rect.width,
    original_height: rect.height,
  }
}

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

///|
fn compare_rects(a : Rect, b : Rect, order : SortOrder) -> Int {
  let primary = match order {
    InputOrder => 0
    AreaDesc => compare_desc(rect_area(a), rect_area(b))
    HeightDesc => compare_desc(a.height, b.height)
    WidthDesc => compare_desc(a.width, b.width)
    PerimeterDesc => compare_desc(a.width + a.height, b.width + b.height)
  }
  if primary != 0 {
    primary
  } else if a.id < b.id {
    -1
  } else if a.id > b.id {
    1
  } else {
    0
  }
}

///|
fn sorted_rects(rects : ArrayView[Rect], order : SortOrder) -> Array[Rect] {
  let work = rects.to_owned()
  if order != InputOrder {
    work.sort_by((a, b) => compare_rects(a, b, order))
  }
  work
}

///|
fn orientation_candidates(
  rect : Rect,
  allow_rotate : Bool,
) -> Array[(Int, Int)] {
  let out : Array[(Int, Int)] = []
  out.push((rect.width, rect.height))
  if allow_rotate && rect.width != rect.height {
    out.push((rect.height, rect.width))
  }
  out
}

///|
fn better_orientation(a : (Int, Int), b : (Int, Int)) -> Bool {
  let (aw, ah) = a
  let (bw, bh) = b
  if ah < bh {
    true
  } else if ah > bh {
    false
  } else {
    aw < bw
  }
}

///|
fn overlaps(a : Placed, b : Placed) -> Bool {
  a.x < b.x + b.width &&
  b.x < a.x + a.width &&
  a.y < b.y + b.height &&
  b.y < a.y + a.height
}

///|
fn maybe_duplicate_id(rects : ArrayView[Rect]) -> String? {
  for i in 0.. String? {
  for i in 0..