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

///|
fn candidate_score(free : FreeRect, w : Int, h : Int) -> Int {
  free_rect_area(free) - w * h
}

///|
fn find_best_free_rect(
  frees : ArrayView[FreeRect],
  rect : Rect,
  options : PackOptions,
) -> (Int, Int, Int, Int)? {
  let mut best : (Int, Int, Int, Int)? = None
  let mut best_score = 0
  for i in 0.. true
          Some((best_index, best_w, best_h, _)) =>
            score < best_score ||
            (score == best_score && free.y < frees[best_index].y) ||
            (
              score == best_score &&
              free.y == frees[best_index].y &&
              free.x < frees[best_index].x
            ) ||
            (
              score == best_score &&
              free.y == frees[best_index].y &&
              free.x == frees[best_index].x &&
              better_orientation((w, h), (best_w, best_h))
            )
        }
        if better {
          best = Some((i, w, h, score))
          best_score = score
        }
      }
    }
  }
  best
}

///|
fn add_free_rect(frees : Array[FreeRect], free : FreeRect) -> Unit {
  if free.width > 0 && free.height > 0 {
    frees.push(free)
  }
}

///|
fn split_free_rect(
  frees : Array[FreeRect],
  free : FreeRect,
  w : Int,
  h : Int,
  inner : Int,
) -> Unit {
  let right_x = free.x + w + inner
  let right_w = free.width - w - inner
  add_free_rect(frees, FreeRect::{
    x: right_x,
    y: free.y,
    width: right_w,
    height: h,
  })
  let below_y = free.y + h + inner
  let below_h = free.height - h - inner
  add_free_rect(frees, FreeRect::{
    x: free.x,
    y: below_y,
    width: free.width,
    height: below_h,
  })
}

///|
fn pack_guillotine(rects : ArrayView[Rect], options : PackOptions) -> Layout {
  let placements : Array[Placed] = []
  let unpacked : Array[Rect] = []
  let frees : Array[FreeRect] = []
  frees.push(FreeRect::{
    x: options.padding.outer,
    y: options.padding.outer,
    width: options.bin.width - options.padding.outer * 2,
    height: options.bin.height - options.padding.outer * 2,
  })
  let ordered = sorted_rects(rects, options.sort)
  for rect in ordered {
    match find_best_free_rect(frees, rect, options) {
      Some((index, w, h, _)) => {
        let free = frees.remove(index)
        placements.push(make_placed(rect, free.x, free.y, w, h))
        split_free_rect(frees, free, w, h, options.padding.inner)
      }
      None => unpacked.push(rect)
    }
  }
  make_layout(options.bin, placements, unpacked, GuillotineBestArea)
}