binpack2d/

binpack.rs

//! Provides a bin packing trait with associated functions to perform bin packing independently
//! from specific bin packer algorithms.
//!
//! # Quick Start
//!
//! This example demonstrates a high-level approach for packing items into bins, without having to
//! know about specific implementation details. Comparable code samples can be looked up in the
//! module descriptions of the individual bin-packing algorithms.
//!
//! ```rust
//! use binpack2d::{bin_new, BinType, Dimension};
//!
//! // Create a number of items to be placed into the bin.
//! let items_to_place = vec![
//!     // Items with autogenerated identifiers.
//!     // Identifiers start at 1 and increment by 1 per call.
//!     Dimension::new(188, 300),
//!     Dimension::new(32, 32),
//!     Dimension::new(420, 512),
//!     Dimension::new(620, 384),
//!     // Three more items with explicit identifiers: -1, 300, and 9528 respectively
//!     Dimension::with_id(-1, 160, 214, 0),
//!     Dimension::with_id(300, 384, 640, 0),
//!     Dimension::with_id(9528, 400, 200, 0),
//! ];
//!
//! // Create a bin with the dimensions 1024x1024, using the "MaxRects" bin type.
//! let mut bin = bin_new(BinType::MaxRects, 1024, 1024);
//!
//! // Perform the bin packing operation on the list of items.
//! let (inserted, rejected) = bin.insert_list(&items_to_place);
//!
//! // Let's see if our item with id=9528 was successfully inserted...
//! if let Some(rect) = &bin.find_by_id(9528) {
//!     println!("Item with id {} was placed into the bin at position (x: {}, y: {})",
//!              rect.dim().id(), rect.x(), rect.y());
//! } else {
//!     println!("Item with id 9528 could not be placed into the bin.");
//! }
//!
//! // List all successfully inserted rectangles.
//! if !inserted.is_empty() {
//!     inserted.iter().for_each(|rect| println!("Inserted: {}", rect));
//! } else {
//!     println!("No rectangles were added to the bin.");
//! }
//!
//! // List all items which could not be inserted into the bin.
//! if !rejected.is_empty() {
//!     rejected.iter().for_each(|item| println!("Rejected: {}", item));
//! } else {
//!     println!("No items were rejected.");
//! }
//!
//! println!("Occupancy of the bin: {:.1} %", bin.occupancy() * 100.0);
//! ```

use self::guillotine::GuillotineBin;
use self::maxrects::MaxRectsBin;
use crate::dimension::Dimension;
use crate::rectangle::Rectangle;
use std::error::Error;
use std::fmt::{Display, Formatter};
use std::slice::Iter;

pub mod guillotine;
pub mod maxrects;

/// List of available bin packing algorithms.
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum BinType {
    /// Refers to the [`MaxRectsBin`] packing algorithm.
    MaxRects,
    /// Refers to the [`GuillotineBin`] packing algorithm.
    Guillotine,
}

/// Represents the core of a bin-packing algorithm.
///
/// This trait provides a common set of methods for packing 2D rectangles into larger bins, which
/// is implemented by all bin-packing algorithms provided by this package.
pub trait BinPacker: Display {
    /// Returns the width of the bin.
    fn width(&self) -> i32;

    /// Returns the height of the bin.
    fn height(&self) -> i32;

    /// Removes all mapped rectangles from the bin.
    fn clear(&mut self) {
        self.clear_with(4);
    }

    /// Just as [`clear`], this method removes all mapped rectangle from the bin, but
    /// also sets initial capacity of the internal rectangle lists to improve performance.
    ///
    /// [`clear`]: BinPacker::clear
    fn clear_with(&mut self, capacity: usize);

    /// Increases dimension of the bin by the specified values.
    ///
    /// `dw` indicates how much to grow horizontally.
    /// `dh` indicates how much to grow vertically.
    fn grow(&mut self, dw: u32, dh: u32);

    /// Attempts to shrink the bin as much as possible.
    ///
    /// `binary` specifies whether the shrinking process should only try to reduce dimensions
    /// by 50 percent for each iteration.
    ///
    /// Does nothing if the bin is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use binpack2d::{bin_new, BinType, Dimension};
    ///
    /// let mut bin = bin_new(BinType::MaxRects, 64, 64);
    /// let node = Dimension::new(25, 10);
    /// bin.insert(&node);
    /// println!("Bin before shrinkage: {}", bin);
    ///
    /// bin.shrink(true);
    /// println!("Bin after binary shrinkage: {}", bin);
    ///
    /// bin.shrink(false);
    /// println!("Bin after arbitrary shrinkage: {}", bin);
    /// ```
    fn shrink(&mut self, binary: bool);

    /// Inserts a single [`Dimension`] object into the bin.
    ///
    /// `dim` refers to the object to be packed into the bin.
    ///
    /// Returns a copy of the packed [`Rectangle`] if the object was inserted successful,
    /// or `None` otherwise.
    ///
    /// **Note:** This trait method performs the operation with sane default values for
    /// packer-specific implementations. You can override them by the bin packer's own
    /// `set_default_*()` methods.
    fn insert(&mut self, dim: &Dimension) -> Option<Rectangle>;

    /// Attempts to insert the given list of [`Dimension`] objects into the bin.
    ///
    /// `nodes` specifies the list of [`Dimension`] objects to insert.
    /// <!-- All successfully inserted objects will be removed from the list in the process. -->
    ///
    /// Returns a a tuple consisting of the list with all successfully inserted [`Rectangle`] objects
    /// and a list of rejected [`Dimension`] objects.
    ///
    /// This method performs slower than [`insert`], but may result in more tightly
    /// packed bins for greater numbers of dimension objects.
    ///
    /// [`insert`]: BinPacker::insert
    ///
    /// **Note:** This trait method performs the operation with sane default values for
    /// packer-specific implementations. You can override them by the bin packer's own
    /// `set_default_*()` methods.
    fn insert_list(&mut self, nodes: &[Dimension]) -> (Vec<Rectangle>, Vec<Dimension>);

    /// Computes the ratio of used surface area to the total bin area and returns it as a
    /// normalized value in the range `[0.0, 1.0]`.
    fn occupancy(&self) -> f32;

    /// Extracts a slice containing the entire list of mapped rectangles.
    ///
    /// Equivalent to `&bin[..]`.
    fn as_slice(&self) -> &[Rectangle];

    /// Returns `true` if the list of mapped rectangles contains no entries.
    fn is_empty(&self) -> bool;

    /// Returns the number of mapped rectangles in this `Bin`.
    fn len(&self) -> usize;

    /// Returns an iterator over the list of mapped rectangles.
    fn iter(&self) -> Iter<'_, Rectangle>;

    /// Returns the first mapped rectangle with the specified identifier, if available.
    /// Returns `None` otherwise.
    fn find_by_id(&self, id: isize) -> Option<Rectangle>;

    /// Returns a visual representation of the bin as ascii graphics `String`.
    ///
    /// # Notes
    ///
    /// Only bins with 62 or fewer mapped rectangles will be visualized. For bins with a
    /// higher number of mapped rectangles the default string representation is returned instead.
    ///
    /// Digits `0` to `9` are used to visualize the first ten mapped rectangles. Ascii characters
    /// in small letters, `a` to `z`, are used for rectangles 10 to 35. Ascii characters in capital
    /// letters, `A` to `Z` are used for rectangles 36 to 61. Empty cells are represented by
    /// dots (`.`)
    fn visualize(&self) -> String;
}

/// This error is returned when items could not be placed into bins.
#[derive(Debug, PartialEq)]
pub enum BinError {
    /// Item does not fit into the bin because item dimension is bigger than bin dimension.
    ItemTooBig,
    /// Item has a dimension of 0 and can therefore not be meaningfully placed into the bin.
    ItemTooSmall,
    /// A generic "catch-all" error, which is returned when the cause could not be determined.
    Unspecified,
}

impl Display for BinError {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        let s = match self {
            Self::ItemTooBig => "item is too big for the bin",
            Self::ItemTooSmall => "item with no space cannot be placed into the bin",
            _ => "unspecified error",
        };
        f.write_str(s)
    }
}

impl Error for BinError {}

/// Creates an empty bin of the given size, using the specified [`BinType`] implementation.
pub fn bin_new(bin_type: BinType, width: i32, height: i32) -> Box<dyn BinPacker> {
    match bin_type {
        BinType::MaxRects => Box::new(MaxRectsBin::new(width, height)),
        BinType::Guillotine => Box::new(GuillotineBin::new(width, height)),
    }
}

/// Creates an empty bin of the given size and reserves space for at least `capacity` number
/// of mapped rectangle to improve performance, using the specified [`BinType`] implementation.
pub fn bin_with_capacity(
    bin_type: BinType,
    width: i32,
    height: i32,
    capacity: usize,
) -> Box<dyn BinPacker> {
    match bin_type {
        BinType::MaxRects => Box::new(MaxRectsBin::with_capacity(width, height, capacity)),
        BinType::Guillotine => Box::new(GuillotineBin::with_capacity(width, height, capacity)),
    }
}

/// A convenience function that attempts to insert a given list of `Dimension` objects into a
/// variable number of bins.
///
/// New bins are created on demand, using the default heuristic rules for the given [`BinType`].
///
/// Specify true for `optimize` to use [`insert_list`] internally, which results in an improved
/// bin layout but at the cost of a worse processing performance.
///
/// [`insert_list`]: BinPacker::insert_list
///
/// Returns a list of bins with the packed rectangle nodes as a [`Result`] value.
///
/// # Errors
///
/// A [`BinError`] is returned for nodes which are either empty or too big for the bin.
///
/// # Examples
/// ```
/// use binpack2d::{BinPacker, BinType, Dimension, pack_bins};
///
/// // Defining three items of different size
/// let nodes = vec![Dimension::new(2, 4), Dimension::new(8, 6), Dimension::new(6, 6)];
///
/// // Returned list of bin object contains all nodes
/// let bins = pack_bins(BinType::Guillotine, &nodes, 16, 12, true)
///     .expect("Items should not be rejected");
///
/// assert_eq!(1, bins.len());
/// assert_eq!(3, bins[0].len());
/// ```
pub fn pack_bins(
    bin_type: BinType,
    nodes: &[Dimension],
    bin_width: i32,
    bin_height: i32,
    optimized: bool,
) -> Result<Vec<Box<dyn BinPacker>>, BinError> {
    if optimized {
        pack_bins_list(bin_type, nodes, bin_width, bin_height)
    } else {
        pack_bins_single(bin_type, nodes, bin_width, bin_height)
    }
}

/// Inserts nodes via insert_list().
fn pack_bins_list(
    bin_type: BinType,
    nodes: &[Dimension],
    bin_width: i32,
    bin_height: i32,
) -> Result<Vec<Box<dyn BinPacker>>, BinError> {
    let mut bins = Vec::new();
    if nodes.is_empty() || bin_width == 0 || bin_height == 0 {
        return Ok(bins);
    }

    // first pass is done separately to avoid a (potentially) costly clone operation
    let mut bin = bin_new(bin_type, bin_width, bin_height);
    let (inserted, mut rejected) = bin.insert_list(nodes);

    if inserted.is_empty() && !rejected.is_empty() {
        // remaining nodes are too big and will be silently skipped
        rejected.clear();
    }

    if !inserted.is_empty() {
        bins.push(bin);
    }

    // subsequent passes are done in a loop
    let mut nodes_left = rejected;
    while !nodes_left.is_empty() {
        let mut bin = bin_new(bin_type, bin_width, bin_height);
        let (inserted, mut rejected) = bin.insert_list(&nodes_left);

        if inserted.is_empty() && !rejected.is_empty() {
            // remaining nodes are too big or too small
            let result = rejected
                .iter()
                .map(|r| {
                    if r.width_total() == 0 || r.height_total() == 0 {
                        BinError::ItemTooSmall
                    } else if r.width_total() > bin_width || r.height_total() > bin_height {
                        BinError::ItemTooBig
                    } else {
                        BinError::Unspecified
                    }
                })
                .next();
            if let Some(result) = result {
                return Err(result);
            } else {
                // Should not happen
                eprintln!("pack_bins(): Could not insert remaining items");
                rejected.clear();
            }
        }

        if !inserted.is_empty() {
            bins.push(bin);
        }

        // preparing for next iteration
        nodes_left.clear();
        nodes_left.append(&mut rejected);
    }

    Ok(bins)
}

/// Inserts nodes via insert().
fn pack_bins_single(
    bin_type: BinType,
    nodes: &[Dimension],
    bin_width: i32,
    bin_height: i32,
) -> Result<Vec<Box<dyn BinPacker>>, BinError> {
    let mut bins = Vec::new();
    if nodes.is_empty() || bin_width == 0 || bin_height == 0 {
        return Ok(bins);
    }

    for node in nodes {
        if node.is_empty() {
            return Err(BinError::ItemTooSmall);
        } else if node.width_total() > bin_width || node.height_total() > bin_height {
            return Err(BinError::ItemTooBig);
        }

        // try inserting node into existing bins
        let mut inserted = false;
        for bin in &mut bins {
            if bin.insert(node).is_some() {
                inserted = true;
                break;
            }
        }

        // create new bin if needed
        if !inserted {
            bins.push(bin_new(bin_type, bin_width, bin_height));
            if let Some(bin) = bins.last_mut() {
                bin.insert(node).expect("Object should fit into the bin");
            }
        }
    }

    Ok(bins)
}

/// A helper method for visualizing bin content.
fn visualize_bin(width: i32, height: i32, rects: &Vec<Rectangle>) -> Option<String> {
    if width > 0 && height > 0 && rects.len() <= 62 {
        // initializing grid
        let size = (width * height) as usize;
        let mut grid = vec![0u32; size];

        for y in 0..height {
            for x in 0..width {
                for (i, r) in rects.iter().enumerate() {
                    if r.y() <= y && r.y() + r.height() > y && r.x() <= x && r.x() + r.width() > x {
                        let pos = (y * width + x) as usize;
                        grid[pos] = (i + 1) as u32;
                    }
                }
            }
        }

        // converting grid to string
        let mut output = String::with_capacity(grid.len() + height as usize);
        for y in 0..height {
            let pos = (y * width) as usize;
            let line: String = grid[pos..(pos + width as usize)]
                .iter()
                .map(|v| match v {
                    0 => '.',
                    1..=10 => char::from_digit(v - 1, 10).unwrap_or('?'),
                    11..=36 => char::from_u32('a' as u32 + v - 11).unwrap_or('?'),
                    37..=62 => char::from_u32('A' as u32 + v - 37).unwrap_or('?'),
                    _ => '?',
                })
                .collect();
            output.push_str(&line);
            output.push('\n');
        }
        output.pop(); // last newline not needed
        Some(output)
    } else {
        None
    }
}

#[cfg(test)]
mod tests;