binpack2d 1.0.1

//! A two-dimensional rectangle bin packer using the *GUILLOTINE* data structure to keep track of
//! free space of the bin where rectangles may be placed. Allows for more fine-grained control over
//! the bin-packing strategy.
//!
//! # Quick Start
//!
//! This example demonstrates the usage of the "Guillotine" bin-packing algorithm. A comparable code
//! sample for a high-level implementation can be looked up in the [`binpack`] module description.
//!
//! [`binpack`]: crate::binpack
//!
//! ```rust
//! use binpack2d::{BinPacker, Dimension};
//! use binpack2d::guillotine::{GuillotineBin, RectHeuristic, SplitHeuristic};
//!
//! // 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
//! let mut bin = GuillotineBin::new(1024, 1024);
//!
//! // Perform the bin packing operation on the list of items.
//! // Passing `true` to the "merge" parameter allows the method to defragment the internal
//! // free rectangles list, which results in improved packing performance at the cost of a small
//! // speed hit.
//! // Using `BestAreaFit` placement and `ShorterAxis` split rules. (Note: Not all placement and
//! // split rule combinations work equally well.)
//! let (inserted, rejected) = bin.insert_list(
//!     &items_to_place,
//!     true,
//!     RectHeuristic::BestAreaFit,
//!     SplitHeuristic::ShorterAxis,
//! );
//!
//! // 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.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 crate::binpack::BinError;
use std::fmt::{Display, Formatter};
use std::mem;
use std::slice::Iter;

use super::{visualize_bin, BinPacker};
use crate::dimension::Dimension;
use crate::rectangle::Rectangle;

/// List of supported heuristic rules for *GUILLOTINE* data structures that can be used when deciding
/// where to place a new rectangle.
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum RectHeuristic {
    /// Positions the rectangle against the short side of a free rectangle into which it fits the best.
    BestShortSideFit,
    /// Positions the rectangle against the long side of a free rectangle into which it fits the best.
    BestLongSideFit,
    /// Positions the rectangle into the smallest free rect into which it fits.
    BestAreaFit,
    /// Positions the rectangle against the short side of a free rectangle into which it fits the least.
    WorstShortSideFit,
    /// Positions the rectangle against the long side of a free rectangle into which it fits the least.
    WorstLongSideFit,
    /// Positions the rectangle into the largest free rect into which it fits.
    WorstAreaFit,
}

/// List of supported heuristic rules that can be used when the packer needs to decide whether to
/// subdivide the remaining free space in horizontal or vertical direction.
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum SplitHeuristic {
    ShorterLeftoverAxis,
    LongerLeftoverAxis,
    MinimizeArea,
    MaximizeArea,
    ShorterAxis,
    LongerAxis,
}

/// A two-dimensional rectangle bin packer using the *GUILLOTINE* data structure to keep track of the
/// free space of the bin where rectangles may be placed.
///
/// It can be used to pack multiple rectangles of arbitrary size into a "bin" of rectangular shape
/// with the goal to add as many rectangles as possible into the bin.
#[derive(Clone, Debug, PartialEq)]
pub struct GuillotineBin {
    /// Horizontal dimension of the bin.
    bin_width: i32,
    /// Vertical dimension of the bin.
    bin_height: i32,
    /// Keeps track of used areas within the bin.
    rects_used: Vec<Rectangle>,
    /// Keeps track of free areas within the bin.
    rects_free: Vec<Rectangle>,

    /// Implicitly used for the methods defined by the `BinPacker` trait.
    default_rect_choice: RectHeuristic,
    /// Implicitly used for the methods defined by the `BinPacker` trait.
    default_split_method: SplitHeuristic,
    /// Implicitly used for the methods defined by the `BinPacker` trait.
    default_merge: bool,
}

impl BinPacker for GuillotineBin {
    fn width(&self) -> i32 {
        self.bin_width
    }

    fn height(&self) -> i32 {
        self.bin_height
    }

    fn clear_with(&mut self, capacity: usize) {
        self.rects_used.clear();
        self.rects_used.shrink_to(capacity.max(4));
        self.rects_free.clear();
        self.rects_free.shrink_to((capacity * 4).max(16));
        self.rects_free.push(Rectangle::new(
            0,
            0,
            Dimension::with_id(0, self.bin_width, self.bin_height, 0),
        ));
    }

    fn grow(&mut self, dw: u32, dh: u32) {
        if dw > 0 {
            self.rects_free.push(Rectangle::new(
                self.bin_width,
                0,
                Dimension::with_id(0, dw as i32, self.bin_height, 0)
            ));
            self.bin_width += dw as i32;
        }

        if dh > 0 {
            self.rects_free.push(Rectangle::new(
                0,
                self.bin_height,
                Dimension::with_id(0, self.bin_width, dh as i32, 0)
            ));
            self.bin_height += dh as i32;
        }
    }

    fn shrink(&mut self, binary: bool) {
        if self.rects_used.is_empty() {
            return;
        }

        let mut min_x = i32::MAX;
        let mut min_y = i32::MAX;
        let mut max_x = i32::MIN;
        let mut max_y = i32::MIN;

        // finding borders
        for rect in &self.rects_used {
            min_x = min_x.min(rect.x_total());
            min_y = min_y.min(rect.y_total());
            max_x = max_x.max(rect.x_total() + rect.width_total());
            max_y = max_y.max(rect.y_total() + rect.height_total());
        }

        let mut new_width = max_x - min_x;
        let mut new_height = max_y - min_y;

        if binary {
            // attempt to shrink to the next lower power of two
            let mut cur_width = self.bin_width;
            while new_width <= (cur_width >> 1) {
                cur_width >>= 1;
            }
            new_width = cur_width;

            let mut cur_height = self.bin_height;
            while new_height <= (cur_height >> 1) {
                cur_height >>= 1;
            }
            new_height = cur_height;
        }

        // adjusting rectangle positions
        if new_width != self.bin_width || new_height != self.bin_height {
            if min_x > 0 || min_y > 0 {
                for rect in &mut self.rects_used {
                    rect.set_x_total(rect.x_total() - min_x);
                    rect.set_y_total(rect.y_total() - min_y);
                }
                for rect in &mut self.rects_free {
                    rect.set_x_total(rect.x_total() - min_x);
                    rect.set_y_total(rect.y_total() - min_y);
                }
            }

            self.bin_width = new_width;
            self.bin_height = new_height;
        }
    }

    fn insert(&mut self, dim: &Dimension) -> Option<Rectangle> {
        self.insert(
            dim,
            self.default_merge,
            self.default_rect_choice,
            self.default_split_method,
        )
    }

    fn insert_list(&mut self, nodes: &[Dimension]) -> (Vec<Rectangle>, Vec<Dimension>) {
        self.insert_list(
            nodes,
            self.default_merge,
            self.default_rect_choice,
            self.default_split_method,
        )
    }

    fn occupancy(&self) -> f32 {
        if self.bin_width == 0 || self.bin_height == 0 {
            return 0.0;
        }

        let area: i64 = self.rects_used.iter().map(|r| r.dim().area()).sum();

        area as f32 / (self.bin_width * self.bin_height) as f32
    }

    fn as_slice(&self) -> &[Rectangle] {
        &self.rects_used
    }

    fn is_empty(&self) -> bool {
        self.rects_used.is_empty()
    }

    fn len(&self) -> usize {
        self.rects_used.len()
    }

    fn iter(&self) -> Iter<'_, Rectangle> {
        self.rects_used.iter()
    }

    fn find_by_id(&self, id: isize) -> Option<Rectangle> {
        self.rects_used
            .iter()
            .find(|&n| n.dim().id() == id)
            .map(|r| r.to_owned())
    }

    fn visualize(&self) -> String {
        if let Some(output) = visualize_bin(self.bin_width, self.bin_height, &self.rects_used) {
            output
        } else {
            format!("{self}")
        }
    }
}

impl GuillotineBin {
    /// Creates an empty bin of the given size.
    ///
    /// Minimum width and height of a bin is 1.
    pub fn new(width: i32, height: i32) -> Self {
        Self::with_capacity(width, height, 4)
    }

    /// Creates an empty bin of the given size and reserves space for at least `capacity` number
    /// of mapped rectangle to improve performance.
    ///
    /// Minimum width and height of a bin is 1.
    pub fn with_capacity(width: i32, height: i32, capacity: usize) -> Self {
        let mut result = Self {
            bin_width: width.max(1),
            bin_height: height.max(1),
            rects_used: Vec::with_capacity(capacity.max(4)),
            rects_free: Vec::with_capacity((capacity * 4).max(4 * 4)),
            default_rect_choice: RectHeuristic::BestShortSideFit,
            default_split_method: SplitHeuristic::ShorterLeftoverAxis,
            default_merge: true,
        };
        result.rects_free.push(Rectangle::new(
            0,
            0,
            Dimension::with_id(0, result.bin_width, result.bin_height, 0),
        ));

        result
    }

    /// Returns the default [`RectHeuristic`] choice, which is used by the [`BinPacker`] trait's
    /// [`insert`] and [`insert_list`] methods.
    ///
    /// [`insert`]: BinPacker::insert
    /// [`insert_list`]: BinPacker::insert_list
    pub fn default_choice(&self) -> RectHeuristic {
        self.default_rect_choice
    }

    /// Can be used to override the default [`RectHeuristic`] choice, which is used by the
    /// [`BinPacker`] trait's [`insert`] and [`insert_list`] methods.
    ///
    /// [`insert`]: BinPacker::insert
    /// [`insert_list`]: BinPacker::insert_list
    pub fn set_default_choice(&mut self, choice: RectHeuristic) {
        self.default_rect_choice = choice;
    }

    /// Returns the default [`SplitHeuristic`] method, which is used by the [`BinPacker`] trait's
    /// [`insert`] and [`insert_list`] methods.
    ///
    /// [`insert`]: BinPacker::insert
    /// [`insert_list`]: BinPacker::insert_list
    pub fn default_method(&self) -> SplitHeuristic {
        self.default_split_method
    }

    /// Can be used to override the default [`SplitHeuristic`] method, which is used by the
    /// [`BinPacker`] trait's [`insert`] and [`insert_list`] methods.
    ///
    /// [`insert`]: BinPacker::insert
    /// [`insert_list`]: BinPacker::insert_list
    pub fn set_default_method(&mut self, method: SplitHeuristic) {
        self.default_split_method = method;
    }

    /// Returns whether a free Rectangle Merge is performed by the [`BinPacker`]
    /// trait's [`insert`] and [`insert_list`] methods.
    ///
    /// [`insert`]: BinPacker::insert
    /// [`insert_list`]: BinPacker::insert_list
    pub fn default_merge(&self) -> bool {
        self.default_merge
    }

    /// Can be used to override whether a free Rectangle Merge is performed by the
    /// [`BinPacker`] trait's [`insert`] and [`insert_list`] methods.
    ///
    /// [`insert`]: BinPacker::insert
    /// [`insert_list`]: BinPacker::insert_list
    pub fn set_default_merge(&mut self, merge: bool) {
        self.default_merge = merge;
    }

    /// Inserts a single [`Dimension`] object into the bin.
    ///
    /// `dim` refers to the object to be packed into the bin.
    ///
    /// `merge` indicates whether to perform free Rectangle Merge procedure after packing the
    /// new rectangle. This procedure tries to defragment the list of disjoint free rectangles to
    /// improve packing performance, but also takes up some extra time.
    ///
    /// `choice` specifies the rectangle choice heuristic to use.
    ///
    /// `method` specifies the rectangle split heuristic to use.
    ///
    /// Returns a copy of the packed [`Rectangle`] if the object was inserted successful,
    /// or `None` otherwise.
    pub fn insert(
        &mut self,
        dim: &Dimension,
        merge: bool,
        choice: RectHeuristic,
        method: SplitHeuristic,
    ) -> Option<Rectangle> {
        // Empty or too big dimension objects are always rejected
        if dim.is_empty()
            || dim.width_total() > self.bin_width
            || dim.height_total() > self.bin_height
        {
            return None;
        }

        // Find where to put the new rectangle
        let (free_node_index, new_rect) = self.find_position_for_new_node(dim, choice);

        if let Some(new_rect) = new_rect {
            // Remove the space that was just consumed by the new rectangle
            let free_rect = self.rects_free[free_node_index];
            self.split_free_rect_by_heuristic(&free_rect, &new_rect, method);
            self.rects_free.swap_remove(free_node_index);

            // Perform a Rectangle Merge step if desired
            if merge {
                self.merge_free_list();
            }

            // Remember the new used rectangle
            self.rects_used.push(new_rect.to_owned());

            Some(new_rect)
        } else {
            // Abort if we didn't have enough space in the bin
            None
        }
    }

    /// 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.
    ///
    /// `merge` indicates whether to perform free Rectangle Merge procedure after packing the
    /// new rectangle. This procedure tries to defragment the list of disjoint free rectangles to
    /// improve packing performance, but also takes up some extra time.
    ///
    /// `choice` specifies the rectangle choice heuristic to use.
    ///
    /// `method` specifies the rectangle split heuristic to use.
    ///
    /// Returns a list with all successfully inserted [`Rectangle`] objects.
    ///
    /// This method performs slower than [`insert`], but may result in more tightly
    /// packed bins for greater numbers of dimension objects.
    ///
    /// [`insert`]: GuillotineBin::insert
    pub fn insert_list(
        &mut self,
        nodes: &[Dimension],
        merge: bool,
        choice: RectHeuristic,
        method: SplitHeuristic,
    ) -> (Vec<Rectangle>, Vec<Dimension>) {
        let mut inserted = Vec::with_capacity(nodes.len().max(1));
        let mut rejected = nodes.to_vec();

        // Remember variables about the best packing choice we have made so far during the
        // iteration process
        let mut best_free_rect = 0usize;
        let mut best_node = 0usize;
        let mut best_flipped = false;

        // Pack rectangles one at a time until we have cleared the `nodes` array of all rectangles.
        // `nodes` will get destroyed in the process.
        while !rejected.is_empty() {
            let mut best_score = i32::MAX;

            let mut i = 0usize;
            let free_size = self.rects_free.len();
            'free_loop: while i < free_size {
                let free_rect = &self.rects_free[i];

                let mut j = 0usize;
                let nodes_size = rejected.len();
                while j < nodes_size {
                    let node = &rejected[j];

                    if node.width_total() == free_rect.width_total()
                        && node.height_total() == free_rect.height_total()
                    {
                        // If this rectangle is a perfect match, we pick it instantly
                        best_free_rect = i;
                        best_node = j;
                        best_flipped = false;
                        best_score = i32::MIN;
                        break 'free_loop;
                    } else if node.height_total() == free_rect.width_total()
                        && node.width_total() == free_rect.height_total()
                    {
                        // If flipping this rectangle is a perfect match, pick that then
                        best_free_rect = i;
                        best_node = j;
                        best_flipped = true;
                        best_score = i32::MIN;
                        break 'free_loop;
                    } else if node.width_total() <= free_rect.width_total()
                        && node.height_total() <= free_rect.height_total()
                    {
                        // Try if we can fit the rectangle upright
                        let score = self.score_by_heuristic(node, free_rect, choice);
                        if score < best_score {
                            best_free_rect = i;
                            best_node = j;
                            best_flipped = false;
                            best_score = score;
                        }
                    } else if node.height_total() <= free_rect.width_total()
                        && node.width_total() <= free_rect.height_total()
                    {
                        // If not, then perhaps flipping sideways will make it fit?
                        let score = self.score_by_heuristic(
                            &Dimension::with_id(0, node.width_total(), node.height_total(), 0),
                            free_rect,
                            choice,
                        );
                        if score < best_score {
                            best_free_rect = i;
                            best_node = j;
                            best_flipped = true;
                            best_score = score;
                        }
                    }

                    j += 1;
                }

                i += 1;
            }

            // If we didn't manage to find any rectangle to pack, abort
            if best_score == i32::MAX {
                break;
            }

            // Otherwise, we're good to go and do the actual packing
            let mut new_node = Rectangle::new(
                self.rects_free[best_free_rect].x() + rejected[best_node].padding(),
                self.rects_free[best_free_rect].y() + rejected[best_node].padding(),
                rejected[best_node].to_owned(),
            );

            if best_flipped {
                new_node.dim_mut().flip();
            }

            // Remove the free space we lost in the bin
            self.split_free_rect_by_heuristic(
                &self.rects_free[best_free_rect].to_owned(),
                &new_node,
                method,
            );
            self.rects_free.swap_remove(best_free_rect);

            // Remove the rectangle we just packed from the input list
            rejected.swap_remove(best_node);

            // Perform a Rectangle Merge step if desired
            if merge {
                self.merge_free_list();
            }

            // Remember the new used rectangle
            self.rects_used.push(new_node.to_owned());
            inserted.push(new_node);
        }

        (inserted, rejected)
    }

    /// Returns a mutable reference to the internal list of free rectangles.
    ///
    /// You may alter this vector any way desired, as long as the end result still is a list of
    /// disjoint rectangles.
    ///
    /// (Added for potential future use.)
    #[allow(dead_code)]
    pub(crate) fn get_free_rects(&mut self) -> &mut Vec<Rectangle> {
        &mut self.rects_free
    }

    /// Returns a mutable reference to the internal list of used rectangles.
    ///
    /// You may alter this vector at will, for example, you can move a `Rectangle` from this list
    /// to the Free Rectangles list to free up space on-the-fly, but notice that this causes
    /// fragmentation.
    ///
    /// (Added for potential future use.)
    #[allow(dead_code)]
    pub(crate) fn get_used_rects(&mut self) -> &mut Vec<Rectangle> {
        &mut self.rects_used
    }

    /// Goes through the list of free rectangles and finds the best one to place a rectangle of
    /// given size into.
    ///
    /// Returns a tuple with the index of the free rectangle in the freeRectangles array
    /// into which the new rect was placed, as well as an optional [`Rectangle`] structure that
    /// represents the placement of the new rectangle into the best free rectangle.
    ///
    /// Running time is Theta(|freeRectangles|).
    fn find_position_for_new_node(
        &self,
        dim: &Dimension,
        choice: RectHeuristic,
    ) -> (usize, Option<Rectangle>) {
        let mut node_index = 0usize;
        let mut best_node = None;
        let mut best_score = i32::MAX;

        // Try each free rectangle to find the best one for placement
        for (i, rect) in self.rects_free.iter().enumerate() {
            if dim.width_total() == rect.width_total() && dim.height_total() == rect.height_total()
            {
                // If this is a perfect fit upright, choose it immediately
                let node = best_node.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                node.set_location_total(rect.x_total(), rect.y_total());
                node.dim_mut().set_dimension(dim.width(), dim.height());
                node_index = i;
                break;
            } else if dim.height_total() == rect.width_total()
                && dim.width_total() == rect.height_total()
            {
                // If this is a perfect fit sideways, choose it
                let node = best_node.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                node.set_location_total(rect.x_total(), rect.y_total());
                node.dim_mut().set_dimension(dim.height(), dim.width());
                node_index = i;
                break;
            } else if dim.width_total() <= rect.width_total()
                && dim.height_total() <= rect.height_total()
            {
                // Does the rectangle fit upright?
                let score = self.score_by_heuristic(dim, rect, choice);
                if score < best_score {
                    let node = best_node.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                    node.set_location_total(rect.x_total(), rect.y_total());
                    node.dim_mut().set_dimension(dim.width(), dim.height());
                    best_score = score;
                    node_index = i;
                }
            } else if dim.height_total() <= rect.width_total()
                && dim.width_total() <= rect.height_total()
            {
                // Does the rectangle fit sideways?
                let score = self.score_by_heuristic(dim, rect, choice);
                if score < best_score {
                    let node = best_node.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                    node.set_location_total(rect.x_total(), rect.y_total());
                    node.dim_mut().set_dimension(dim.height(), dim.width());
                    best_score = score;
                    node_index = i;
                }
            }
        }

        (node_index, best_node)
    }

    /// Returns the heuristic score value for placing a rectangle of size width*height into freeRect.
    /// Does not try to rotate.
    fn score_by_heuristic(
        &self,
        dim: &Dimension,
        free_rect: &Rectangle,
        choice: RectHeuristic,
    ) -> i32 {
        match choice {
            RectHeuristic::BestAreaFit => self.score_baf(dim, free_rect),
            RectHeuristic::BestShortSideFit => self.score_bssf(dim, free_rect),
            RectHeuristic::BestLongSideFit => self.score_blsf(dim, free_rect),
            RectHeuristic::WorstAreaFit => self.score_waf(dim, free_rect),
            RectHeuristic::WorstShortSideFit => self.score_wssf(dim, free_rect),
            RectHeuristic::WorstLongSideFit => self.score_wlsf(dim, free_rect),
        }
    }

    /// Computes score value if a rect of the given size was placed into the given free rectangle.
    /// In these score values, smaller is better.
    fn score_baf(&self, dim: &Dimension, free_rect: &Rectangle) -> i32 {
        (free_rect.dim().area_total() - dim.area_total()) as i32
    }

    /// Computes score value if a rect of the given size was placed into the given free rectangle.
    /// In these score values, smaller is better.
    fn score_bssf(&self, dim: &Dimension, free_rect: &Rectangle) -> i32 {
        let leftover_h = free_rect.width_total().abs_diff(dim.width_total());
        let leftover_v = free_rect.height_total().abs_diff(dim.height_total());
        leftover_v.min(leftover_h) as i32
    }

    /// Computes score value if a rect of the given size was placed into the given free rectangle.
    /// In these score values, smaller is better.
    fn score_blsf(&self, dim: &Dimension, free_rect: &Rectangle) -> i32 {
        let leftover_h = free_rect.width_total().abs_diff(dim.width_total());
        let leftover_v = free_rect.height_total().abs_diff(dim.height_total());
        leftover_v.max(leftover_h) as i32
    }

    /// Computes (penalty) score value if a rect of the given size was placed into the given free
    /// rectangle. In these score values, smaller is better.
    fn score_waf(&self, dim: &Dimension, free_rect: &Rectangle) -> i32 {
        -self.score_baf(dim, free_rect)
    }

    /// Computes (penalty) score value if a rect of the given size was placed into the given free
    /// rectangle. In these score values, smaller is better.
    fn score_wssf(&self, dim: &Dimension, free_rect: &Rectangle) -> i32 {
        -self.score_bssf(dim, free_rect)
    }

    /// Computes (penalty) score value if a rect of the given size was placed into the given free
    /// rectangle. In these score values, smaller is better.
    fn score_wlsf(&self, dim: &Dimension, free_rect: &Rectangle) -> i32 {
        -self.score_blsf(dim, free_rect)
    }

    /// Splits the given L-shaped free rectangle into two new free rectangles after `placed_rect`
    /// has been placed into it. Determines the split axis by using the given heuristic.
    fn split_free_rect_by_heuristic(
        &mut self,
        free_rect: &Rectangle,
        placed_rect: &Rectangle,
        method: SplitHeuristic,
    ) {
        // Compute the lengths of the leftover area
        let w = free_rect.width_total() - placed_rect.width_total();
        let h = free_rect.height_total() - placed_rect.height_total();

        // Placing placed_rect into free_rect results in an L-shaped free area, which must be split
        // into two disjoint rectangles. This can be achieved with by splitting the L-shape using a
        // single line. We have two choices: horizontal or vertical.

        // Use the given heuristic to decide which choice to make.
        let split_horizontal = match method {
            // Split along the shorter leftover axis
            SplitHeuristic::ShorterLeftoverAxis => w <= h,
            // Split along the longer leftover axis
            SplitHeuristic::LongerLeftoverAxis => w > h,
            // Maximize the larger area == minimize the smaller area.
            // Tries to make the single bigger rectangle.
            SplitHeuristic::MinimizeArea => {
                placed_rect.width_total() * h > w * placed_rect.height_total()
            }
            // Maximize the smaller area == minimize the larger area.
            // Tries to make the rectangles more even-sized.
            SplitHeuristic::MaximizeArea => {
                placed_rect.width_total() * h <= w * placed_rect.height_total()
            }
            // Split along the shorter total axis
            SplitHeuristic::ShorterAxis => free_rect.width_total() <= free_rect.height_total(),
            // Split along the longer total axis
            SplitHeuristic::LongerAxis => free_rect.width_total() > free_rect.height_total(),
        };

        // Perform the actual split
        self.split_free_rect_along_axis(free_rect, placed_rect, split_horizontal);
    }

    /// This function will add the two generated rectangles into the rects_free array.
    ///
    /// The caller is expected to remove the original rectangle from the rects_free array after that.
    fn split_free_rect_along_axis(
        &mut self,
        free_rect: &Rectangle,
        placed_rect: &Rectangle,
        split_horizontal: bool,
    ) {
        // Form the two new rectangles
        let mut bottom = Rectangle::new(
            free_rect.x_total(),
            free_rect.y_total() + placed_rect.height_total(),
            Dimension::with_id(
                0,
                0,
                free_rect.height_total() - placed_rect.height_total(),
                0,
            ),
        );

        let mut right = Rectangle::new(
            free_rect.x_total() + placed_rect.width_total(),
            free_rect.y_total(),
            Dimension::with_id(0, free_rect.width_total() - placed_rect.width_total(), 0, 0),
        );

        if split_horizontal {
            // split horizontally
            bottom.dim_mut().set_width(free_rect.width());
            right.dim_mut().set_height(placed_rect.height());
        } else {
            // split vertically
            bottom.dim_mut().set_width(placed_rect.width());
            right.dim_mut().set_height(free_rect.height());
        }

        // Add the new rectangles into the free rectangle pool if they weren't degenerate
        if !bottom.dim().is_empty_total() {
            self.rects_free.push(bottom);
        }
        if !right.dim().is_empty_total() {
            self.rects_free.push(right);
        }
    }

    /// Performs a Rectangle Merge operation.
    ///
    /// This procedure looks for adjacent free rectangles and merges them if they can be represented
    /// with a single rectangle. Takes up Theta(|freeRectangles|^2) time.
    fn merge_free_list(&mut self) {
        // Do a Theta(n^2) loop to see if any pair of free rectangles could me merged into one.
        // Note that we miss any opportunities to merge three rectangles into one.
        // (should call this function again to detect that)
        let mut i = 0usize;
        let mut free_size = self.rects_free.len();
        while i < free_size {
            let mut rect1 = self.rects_free[i];

            let mut j = i + 1;
            while j < free_size {
                let rect2 = &self.rects_free[j];
                if rect1.width_total() == rect2.width_total() && rect1.x_total() == rect2.x_total()
                {
                    if rect1.y_total() == rect2.y_total() + rect2.height_total() {
                        rect1.set_y_total(rect1.y_total() - rect2.height_total());
                        let rect1_height = rect1.height();
                        rect1.dim_mut().set_height(rect1_height + rect2.height());
                        let _ = mem::replace(&mut self.rects_free[i], rect1);
                        self.rects_free.swap_remove(j);
                        free_size -= 1;
                    } else if rect1.y_total() + rect1.height_total() == rect2.y_total() {
                        let rect1_height = rect1.height();
                        rect1.dim_mut().set_height(rect1_height + rect2.height());
                        let _ = mem::replace(&mut self.rects_free[i], rect1);
                        self.rects_free.swap_remove(j);
                        free_size -= 1;
                    } else {
                        j += 1;
                    }
                } else if rect1.height_total() == rect2.height_total()
                    && rect1.y_total() == rect2.y_total()
                {
                    if rect1.x_total() == rect2.x_total() + rect2.width_total() {
                        rect1.set_x_total(rect1.x_total() - rect2.width_total());
                        let rect1_width = rect1.width();
                        rect1.dim_mut().set_width(rect1_width + rect2.width());
                        let _ = mem::replace(&mut self.rects_free[i], rect1);
                        self.rects_free.swap_remove(j);
                        free_size -= 1;
                    } else if rect1.x_total() + rect1.width_total() == rect2.x_total() {
                        let rect1_width = rect1.width();
                        rect1.dim_mut().set_width(rect1_width + rect2.width());
                        let _ = mem::replace(&mut self.rects_free[i], rect1);
                        self.rects_free.swap_remove(j);
                        free_size -= 1;
                    } else {
                        j += 1;
                    }
                } else {
                    j += 1;
                }
            }

            i += 1;
        }
    }
}

impl<Idx> std::ops::Index<Idx> for GuillotineBin
where
    Idx: std::slice::SliceIndex<[Rectangle]>,
{
    type Output = Idx::Output;

    fn index(&self, index: Idx) -> &Self::Output {
        &self.rects_used[index]
    }
}

impl Display for GuillotineBin {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "Bin(width: {}, height: {}, rectangles: {})",
            self.bin_width,
            self.bin_height,
            self.rects_used.len()
        )
    }
}

/// 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 given heuristic `choice` and `method`.
/// Optionally, performs an additional `merge` step to keep fragmentation to a minimum.
///
/// 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`]: GuillotineBin::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::binpack::BinPacker;
/// use binpack2d::binpack::guillotine::{RectHeuristic, SplitHeuristic, pack_bins};
/// use binpack2d::dimension::Dimension;
///
/// // 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, placed according to the given heuristic hints
/// let bins = pack_bins(&nodes,
///                      16, 12,
///                      true,
///                      RectHeuristic::BestShortSideFit,
///                      SplitHeuristic::ShorterLeftoverAxis,
///                      true)
///     .expect("Items should not be rejected");
///
/// assert_eq!(1, bins.len());
/// assert_eq!(3, bins[0].len());
/// ```
pub fn pack_bins(
    nodes: &[Dimension],
    bin_width: i32,
    bin_height: i32,
    merge: bool,
    choice: RectHeuristic,
    method: SplitHeuristic,
    optimized: bool,
) -> Result<Vec<GuillotineBin>, BinError> {
    if optimized {
        pack_bins_list(nodes, bin_width, bin_height, merge, choice, method)
    } else {
        pack_bins_single(nodes, bin_width, bin_height, merge, choice, method)
    }
}

/// Inserts nodes via insert_list().
fn pack_bins_list(
    nodes: &[Dimension],
    bin_width: i32,
    bin_height: i32,
    merge: bool,
    choice: RectHeuristic,
    method: SplitHeuristic,
) -> Result<Vec<GuillotineBin>, 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 = GuillotineBin::new(bin_width, bin_height);
    let (inserted, mut rejected) = bin.insert_list(nodes, merge, choice, method);

    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 = GuillotineBin::new(bin_width, bin_height);
        let (inserted, mut rejected) = bin.insert_list(&nodes_left, merge, choice, method);

        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(
    nodes: &[Dimension],
    bin_width: i32,
    bin_height: i32,
    merge: bool,
    choice: RectHeuristic,
    method: SplitHeuristic,
) -> Result<Vec<GuillotineBin>, 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, merge, choice, method).is_some() {
                inserted = true;
                break;
            }
        }

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

    Ok(bins)
}

#[cfg(test)]
mod tests;