///|
fn padded_overlap_at(
  placed : Placed,
  x : Int,
  y : Int,
  width : Int,
  height : Int,
  gap : Int,
) -> Bool {
  x < placed.x + placed.width + gap &&
  placed.x < x + width + gap &&
  y < placed.y + placed.height + gap &&
  placed.y < y + height + gap
}

///|
fn skyline_fits_at(
  placements : ArrayView[Placed],
  x : Int,
  y : Int,
  width : Int,
  height : Int,
  options : PackOptions,
) -> Bool {
  if x < options.padding.outer || y < options.padding.outer {
    return false
  }
  if x + width > right_limit(options) || y + height > bottom_limit(options) {
    return false
  }
  for placed in placements {
    if padded_overlap_at(placed, x, y, width, height, options.padding.inner) {
      return false
    }
  }
  true
}

///|
fn skyline_candidate_better(
  candidate : (Int, Int, Int, Int),
  previous : (Int, Int, Int, Int),
) -> Bool {
  let (cx, cy, cw, ch) = candidate
  let (px, py, pw, ph) = previous
  if cy < py {
    true
  } else if cy > py {
    false
  } else if cx < px {
    true
  } else if cx > px {
    false
  } else {
    better_orientation((cw, ch), (pw, ph))
  }
}

///|
fn skyline_find_position(
  placements : ArrayView[Placed],
  rect : Rect,
  options : PackOptions,
) -> (Int, Int, Int, Int)? {
  let mut best : (Int, Int, Int, Int)? = None
  for size in orientation_candidates(rect, options.allow_rotate) {
    let (width, height) = size
    if width > right_limit(options) - options.padding.outer ||
      height > bottom_limit(options) - options.padding.outer {
      continue
    }
    let mut y = options.padding.outer
    while y + height <= bottom_limit(options) {
      let mut x = options.padding.outer
      while x + width <= right_limit(options) {
        if skyline_fits_at(placements, x, y, width, height, options) {
          let candidate = (x, y, width, height)
          match best {
            None => best = Some(candidate)
            Some(previous) =>
              if skyline_candidate_better(candidate, previous) {
                best = Some(candidate)
              }
          }
        }
        x = x + 1
      }
      y = y + 1
    }
  }
  best
}

///|
fn pack_skyline(rects : ArrayView[Rect], options : PackOptions) -> Layout {
  let placements : Array[Placed] = []
  let unpacked : Array[Rect] = []
  let ordered = sorted_rects(rects, options.sort)
  for rect in ordered {
    match skyline_find_position(placements, rect, options) {
      Some((x, y, width, height)) =>
        placements.push(make_placed(rect, x, y, width, height))
      None => unpacked.push(rect)
    }
  }
  make_layout(options.bin, placements, unpacked, SkylineBottomLeft)
}