pub const PADDING: u32 = 1;
#[derive(Debug)]
struct Shelf {
y: u32,
height: u32,
cursor_x: u32,
}
#[derive(Debug)]
pub struct ShelfPacker {
width: u32,
height: u32,
shelves: Vec<Shelf>,
next_y: u32,
}
impl ShelfPacker {
pub fn new(width: u32, height: u32) -> Self {
Self {
width,
height,
shelves: Vec::new(),
next_y: 0,
}
}
pub fn insert(&mut self, w: u32, h: u32) -> Option<(u32, u32)> {
if w == 0 || h == 0 || w > self.width || h > self.height {
return None;
}
let (pw, ph) = (w + PADDING, h + PADDING);
for shelf in &mut self.shelves {
if ph <= shelf.height && ph * 2 >= shelf.height && shelf.cursor_x + pw <= self.width {
let pos = (shelf.cursor_x, shelf.y);
shelf.cursor_x += pw;
return Some(pos);
}
}
if self.next_y + ph <= self.height && pw <= self.width {
let shelf = Shelf {
y: self.next_y,
height: ph,
cursor_x: pw,
};
let pos = (0, self.next_y);
self.next_y += ph;
self.shelves.push(shelf);
return Some(pos);
}
None
}
}
#[cfg(test)]
mod tests {
use super::*;
use wasm_bindgen_test::wasm_bindgen_test;
#[wasm_bindgen_test(unsupported = test)]
fn page_sized_rects_and_padded_shelf_heights_are_exact() {
let mut packer = ShelfPacker::new(16, 16);
assert_eq!(packer.insert(17, 1), None);
assert_eq!(packer.insert(1, 17), None);
assert_eq!(packer.insert(0, 4), None);
assert_eq!(packer.insert(16, 7), None);
assert_eq!(packer.insert(15, 7), Some((0, 0)));
assert_eq!(packer.insert(15, 7), Some((0, 8)));
assert_eq!(packer.insert(1, 7), None);
}
#[wasm_bindgen_test(unsupported = test)]
fn same_height_rects_share_a_shelf() {
let mut p = ShelfPacker::new(128, 128);
assert_eq!(p.insert(32, 32), Some((0, 0)));
assert_eq!(p.insert(32, 32), Some((33, 0)), "1 px padding gap");
assert_eq!(p.insert(32, 32), Some((66, 0)));
}
#[wasm_bindgen_test(unsupported = test)]
fn taller_rect_opens_a_new_shelf() {
let mut p = ShelfPacker::new(128, 128);
assert_eq!(p.insert(32, 32), Some((0, 0)));
assert_eq!(p.insert(32, 64), Some((0, 33)), "below the 33-high shelf");
assert_eq!(p.insert(32, 32), Some((33, 0)));
}
#[wasm_bindgen_test(unsupported = test)]
fn tiny_rect_does_not_waste_a_tall_shelf() {
let mut p = ShelfPacker::new(256, 256);
assert_eq!(p.insert(64, 64), Some((0, 0)));
assert_eq!(p.insert(8, 8), Some((0, 65)));
}
#[wasm_bindgen_test(unsupported = test)]
fn full_shelf_wraps() {
let mut p = ShelfPacker::new(70, 128);
assert_eq!(p.insert(32, 32), Some((0, 0)));
assert_eq!(p.insert(32, 32), Some((33, 0)));
assert_eq!(p.insert(32, 32), Some((0, 33)));
}
#[wasm_bindgen_test(unsupported = test)]
fn overflow_and_oversize_return_none() {
let mut p = ShelfPacker::new(64, 64);
assert!(p.insert(63, 63).is_some());
assert_eq!(p.insert(32, 32), None, "page is spent");
let mut q = ShelfPacker::new(64, 64);
assert_eq!(q.insert(65, 8), None, "wider than the page");
assert_eq!(q.insert(0, 8), None, "degenerate");
}
#[wasm_bindgen_test(unsupported = test)]
fn placements_never_overlap_or_escape() {
let mut p = ShelfPacker::new(256, 256);
let sizes = [
(32, 32),
(16, 16),
(48, 24),
(32, 32),
(8, 8),
(96, 32),
(32, 32),
(64, 64),
(24, 48),
(32, 32),
];
let mut placed: Vec<(u32, u32, u32, u32)> = Vec::new();
for (w, h) in sizes {
if let Some((x, y)) = p.insert(w, h) {
assert!(x + w <= 256 && y + h <= 256, "escaped the page");
for &(px, py, pw, ph) in &placed {
let disjoint = x >= px + pw || px >= x + w || y >= py + ph || py >= y + h;
assert!(disjoint, "({x},{y},{w},{h}) overlaps ({px},{py},{pw},{ph})");
}
placed.push((x, y, w, h));
}
}
assert!(placed.len() >= 8, "packer should fit most of the set");
}
}