binpack2d/binpack/

maxrects.rs

//! A two-dimensional rectangle bin packer using the *MAXRECTS* data structure to keep track of
//! free space of the bin where rectangles may be placed. A good choice for most use cases.
//!
//! # Quick Start
//!
//! This example demonstrates the usage of the "MaxRects" 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::maxrects::{Heuristic, MaxRectsBin};
//!
//! // 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 = MaxRectsBin::new(1024, 1024);
//!
//! // Perform the bin packing operation on the list of items, using tetris-style placement rule.
//! let (inserted, rejected) = bin.insert_list(&items_to_place, Heuristic::BottomLeftRule);
//!
//! // 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::slice::Iter;

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

/// List of supported heuristic rules for *MAXRECTS* data structures that can be used when deciding
/// where to place a new rectangle.
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum Heuristic {
    /// 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,
    /// Does the Tetris placement.
    BottomLeftRule,
    /// Chooses the placement where the rectangle touches other rectangles as much as possible.
    ///
    /// **Note:** Average packing speed of this rule is worse than that of the other rules.
    ContactPointRule,
}

/// A two-dimensional rectangle bin packer using the *MAXRECTS* data structure and different
/// bin packing algorithms that use this structure.
///
/// 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 MaxRectsBin {
    /// 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>,

    // Internally used to speed up packing operations
    new_rects_free_size: usize,
    // Internally used to speed up packing operations
    new_rects_free: Vec<Rectangle>,

    /// Implicitly used for the methods defined by the `BinPacker` trait.
    default_heuristic: Heuristic,
}

impl BinPacker for MaxRectsBin {
    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);
                }
                for rect in &mut self.new_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_heuristic)
    }

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

    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 MaxRectsBin {
    /// 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)),
            new_rects_free_size: 0,
            new_rects_free: Vec::new(),
            default_heuristic: Heuristic::BestShortSideFit,
        };
        result.rects_free.push(Rectangle::new(
            0,
            0,
            Dimension::with_id(0, result.bin_width, result.bin_height, 0),
        ));

        result
    }

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

    /// Can be used to override the default [`Heuristic`] rule, 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_rule(&mut self, rule: Heuristic) {
        self.default_heuristic = rule;
    }

    /// Inserts a single [`Dimension`] object into the bin.
    ///
    /// `dim` refers to the object to be packed into the bin.
    ///
    /// `rule` specifies the rectangle placement rule to use for the packing operation.
    ///
    /// Returns a copy of the packed [`Rectangle`] if the object was inserted successful,
    /// or `None` otherwise.
    pub fn insert(&mut self, dim: &Dimension, rule: Heuristic) -> 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;
        }

        let (_, _, result) = match rule {
            Heuristic::BestShortSideFit => self.find_bssf(dim),
            Heuristic::BestLongSideFit => self.find_blsf(dim),
            Heuristic::BestAreaFit => self.find_baf(dim),
            Heuristic::BottomLeftRule => self.find_blr(dim),
            Heuristic::ContactPointRule => self.find_cpr(dim),
        };

        if let Some(new_node) = &result {
            self.place_rect(new_node);

            Some(*new_node)
        } else {
            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.
    ///
    /// `rule` specifies the rectangle placement rule to use for the packing operations.
    ///
    /// 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`]: MaxRectsBin::insert
    pub fn insert_list(
        &mut self,
        nodes: &[Dimension],
        rule: Heuristic,
    ) -> (Vec<Rectangle>, Vec<Dimension>) {
        let mut inserted = Vec::with_capacity(nodes.len());
        let mut rejected = nodes.to_vec();

        while !rejected.is_empty() {
            let mut best_score1 = i32::MAX;
            let mut best_score2 = i32::MAX;
            let mut best_index = None;
            let mut best_node = None;

            for (i, dim) in rejected.iter().enumerate() {
                let (score1, score2, new_node) = self.score_rect(dim, rule);

                if score1 < best_score1 || (score1 == best_score1 && score2 < best_score2) {
                    best_score1 = score1;
                    best_score2 = score2;
                    best_index = Some(i);
                    best_node = new_node;
                }
            }

            if best_index.is_none() {
                break;
            }

            debug_assert!(best_node.is_some());

            self.place_rect(&best_node.unwrap());
            inserted.push(best_node.unwrap());
            rejected.swap_remove(best_index.unwrap());
        }

        (inserted, rejected)
    }

    /// Computes the placement score for placing the given `Dimension` with the given rule.
    ///
    /// Returns a tuple consisting of the primary and secondary placement scores, as well as
    /// the `Rectangle` structure where the requested `Dimension` can be placed.
    fn score_rect(&self, dim: &Dimension, rule: Heuristic) -> (i32, i32, Option<Rectangle>) {
        let (mut score1, mut score2, new_node) = match rule {
            Heuristic::BestShortSideFit => self.find_bssf(dim),
            Heuristic::BestLongSideFit => self.find_blsf(dim),
            Heuristic::BestAreaFit => self.find_baf(dim),
            Heuristic::BottomLeftRule => self.find_blr(dim),
            Heuristic::ContactPointRule => self.find_cpr(dim),
        };

        // Cannot fit the current rectangle.
        if new_node.is_none() {
            score1 = i32::MAX;
            score2 = i32::MAX;
        }

        (score1, score2, new_node)
    }

    /// Places the given rectangle into the bin.
    fn place_rect(&mut self, rect: &Rectangle) {
        let mut idx = 0usize;
        while idx < self.rects_free.len() {
            let node = self.rects_free[idx];
            if self.split_free_node(&node, rect) {
                self.rects_free.swap_remove(idx);
                continue;
            }
            idx += 1;
        }

        self.prune_free_list();

        self.rects_used.push(rect.to_owned());
    }

    /// Attempts to find the best rectangle position in the bin, using the [`Heuristic::BottomLeftRule`] rule.
    fn find_blr(&self, dim: &Dimension) -> (i32, i32, Option<Rectangle>) {
        let mut result = None;

        let mut best_x = i32::MAX;
        let mut best_y = i32::MAX;
        for rect in &self.rects_free {
            if rect.width_total() >= dim.width_total() && rect.height_total() >= dim.height_total()
            {
                let top_y = rect.y_total() + dim.height_total();

                if top_y < best_y || (top_y == best_y && rect.x_total() < best_x) {
                    let best_node = result.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                    best_node.set_location_total(rect.x_total(), rect.y_total());
                    best_node.dim_mut().set_dimension(dim.width(), dim.height());
                    best_x = rect.x_total();
                    best_y = top_y;
                }
            }
        }

        (best_y, best_x, result)
    }

    /// Attempts to find the best rectangle position in the bin, using the [`Heuristic::BestShortSideFit`] rule.
    fn find_bssf(&self, dim: &Dimension) -> (i32, i32, Option<Rectangle>) {
        let mut result = None;

        let mut best_short_side_fit = i32::MAX;
        let mut best_long_size_fit = i32::MAX;
        for rect in &self.rects_free {
            if rect.width_total() >= dim.width_total() && rect.height_total() >= dim.height_total()
            {
                let leftover_h = rect.width_total().abs_diff(dim.width_total()) as i32;
                let leftover_v = rect.height_total().abs_diff(dim.height_total()) as i32;
                let short_side_fit = leftover_h.min(leftover_v);
                let long_side_fit = leftover_h.max(leftover_v);

                if short_side_fit < best_short_side_fit
                    || (short_side_fit == best_short_side_fit && long_side_fit < best_long_size_fit)
                {
                    let best_node = result.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                    best_node.set_location_total(rect.x_total(), rect.y_total());
                    best_node.dim_mut().set_dimension(dim.width(), dim.height());
                    best_short_side_fit = short_side_fit;
                    best_long_size_fit = long_side_fit;
                }
            }
        }

        (best_short_side_fit, best_long_size_fit, result)
    }

    /// Attempts to find the best rectangle position in the bin, using the [`Heuristic::BestLongSideFit`] rule.
    fn find_blsf(&self, dim: &Dimension) -> (i32, i32, Option<Rectangle>) {
        let mut result = None;

        let mut best_short_side_fit = i32::MAX;
        let mut best_long_size_fit = i32::MAX;
        for rect in &self.rects_free {
            if rect.width_total() >= dim.width_total() && rect.height_total() >= dim.height_total()
            {
                let leftover_h = rect.width_total().abs_diff(dim.width_total()) as i32;
                let leftover_v = rect.height_total().abs_diff(dim.height_total()) as i32;
                let short_side_fit = leftover_h.min(leftover_v);
                let long_side_fit = leftover_h.max(leftover_v);

                if long_side_fit < best_long_size_fit
                    || (long_side_fit == best_long_size_fit && short_side_fit < best_short_side_fit)
                {
                    let best_node = result.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                    best_node.set_location_total(rect.x_total(), rect.y_total());
                    best_node.dim_mut().set_dimension(dim.width(), dim.height());
                    best_short_side_fit = short_side_fit;
                    best_long_size_fit = long_side_fit;
                }
            }
        }

        (best_long_size_fit, best_short_side_fit, result)
    }

    /// Attempts to find the best rectangle position in the bin, using the [`Heuristic::BestAreaFit`] rule.
    fn find_baf(&self, dim: &Dimension) -> (i32, i32, Option<Rectangle>) {
        let mut result = None;

        let mut best_area_fit = i64::MAX;
        let mut best_short_side_fit = i64::MAX;
        // let mut best_fit = (u32::MAX, 0u32);
        for rect in &self.rects_free {
            if rect.width_total() >= dim.width_total() && rect.height_total() >= dim.height_total()
            {
                let leftover_h = rect.width_total().abs_diff(dim.width_total());
                let leftover_v = rect.height_total().abs_diff(dim.height_total());
                let short_side_fit = leftover_h.min(leftover_v) as i64;

                let area_fit = rect.dim().area_total() - dim.area_total();
                if area_fit < best_area_fit
                    || (area_fit == best_area_fit && short_side_fit < best_short_side_fit)
                {
                    let best_node = result.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                    best_node.set_location_total(rect.x_total(), rect.y_total());
                    best_node.dim_mut().set_dimension(dim.width(), dim.height());
                    best_area_fit = area_fit;
                    best_short_side_fit = short_side_fit;
                }
            }
        }

        (best_area_fit as i32, best_short_side_fit as i32, result)
    }

    /// Attempts to find the best rectangle position in the bin, using the [`Heuristic::ContactPointRule`] rule.
    fn find_cpr(&self, dim: &Dimension) -> (i32, i32, Option<Rectangle>) {
        let mut result = None;

        let mut best_score = -1;
        for rect in &self.rects_free {
            if rect.width_total() >= dim.width_total() && rect.height_total() >= dim.height_total()
            {
                let score = self.contact_point_score_node(
                    rect.x_total(),
                    rect.y_total(),
                    dim.width_total(),
                    dim.height_total(),
                );
                if score > best_score {
                    let best_node = result.get_or_insert_with(|| Rectangle::new(0, 0, *dim));
                    best_node.set_location_total(rect.x_total(), rect.y_total());
                    best_node.dim_mut().set_dimension(dim.width(), dim.height());
                    best_score = score;
                }
            }
        }

        // Reversing score since we are minimizing, but for contact point score, bigger is better.
        best_score = -best_score;

        // No secondary score needed
        (best_score, 0, result)
    }

    /// Computes the placement score for the "CP" variant.
    fn contact_point_score_node(&self, x: i32, y: i32, width: i32, height: i32) -> i32 {
        let mut score = 0;

        if x == 0 || x + width == self.bin_width {
            score += height;
        }
        if y == 0 || y + height == self.bin_height {
            score += width;
        }

        for rect in &self.rects_used {
            if rect.x_total() == x + width || rect.x_total() + rect.width_total() == x {
                score += Self::common_interval_length(
                    rect.y_total(),
                    rect.y_total() + rect.height_total(),
                    y,
                    y + height,
                );
            }
            if rect.y_total() == y + height || rect.y_total() + rect.height_total() == y {
                score += Self::common_interval_length(
                    rect.x_total(),
                    rect.x_total() + rect.width_total(),
                    x,
                    x + width,
                );
            }
        }

        score
    }

    /// Returns whether the specified free node was split.
    fn split_free_node(&mut self, free: &Rectangle, used: &Rectangle) -> bool {
        // Test with SAT if the rectangles even intersect
        if used.x_total() >= free.x_total() + free.width_total()
            || used.x_total() + used.width_total() <= free.x_total()
            || used.y_total() >= free.y_total() + free.height_total()
            || used.y_total() + used.height_total() <= free.y_total()
        {
            return false;
        }

        // We add up to four new free rectangles to the free rectangles list below. None of these
        // four newly added free rectangles can overlap any other three, so keep a mark of them
        // to avoid testing them against each other.
        self.new_rects_free_size = self.new_rects_free.len();

        if used.x_total() < free.x_total() + free.width_total()
            && used.x_total() + used.width_total() > free.x_total()
        {
            // New node at the top side of the used node
            if used.y_total() > free.y_total()
                && used.y_total() < free.y_total() + free.height_total()
            {
                let mut new_node = free.to_owned();
                let new_y = new_node.y_total();
                new_node.dim_mut().set_height(used.y_total() - new_y);
                self.insert_new_free_rect(&new_node);
            }

            // New node at the bottom side of the used node.
            if used.y_total() + used.height_total() < free.y_total() + free.height_total() {
                let mut new_node = free.to_owned();
                new_node.set_y_total(used.y_total() + used.height_total());
                new_node.dim_mut().set_height(
                    free.y_total() + free.height_total() - (used.y_total() + used.height_total()),
                );
                self.insert_new_free_rect(&new_node);
            }
        }

        if used.y_total() < free.y_total() + free.height_total()
            && used.y_total() + used.height_total() > free.y_total()
        {
            // New node at the left side of the used node.
            if used.x_total() > free.x_total()
                && used.x_total() < free.x_total() + free.width_total()
            {
                let mut new_node = free.to_owned();
                let new_x = new_node.x_total();
                new_node.dim_mut().set_width(used.x_total() - new_x);
                self.insert_new_free_rect(&new_node);
            }

            // New node at the right side of the used node.
            if used.x_total() + used.width_total() < free.x_total() + free.width_total() {
                let mut new_node = free.to_owned();
                new_node.set_x_total(used.x_total() + used.width_total());
                new_node.dim_mut().set_width(
                    free.x_total() + free.width_total() - (used.x_total() + used.width_total()),
                );
                self.insert_new_free_rect(&new_node);
            }
        }

        true
    }

    fn insert_new_free_rect(&mut self, new_node: &Rectangle) {
        debug_assert!(new_node.width_total() > 0);
        debug_assert!(new_node.height_total() > 0);

        let mut i = 0usize;
        while i < self.new_rects_free_size {
            let cur_node = &self.new_rects_free[i];

            // This new free rectangle is already accounted for?
            if cur_node.contains_total(new_node) {
                return;
            }

            // Does this new free rectangle obsolete a previous new free rectangle?
            if new_node.contains_total(cur_node) {
                // Remove i'th new free rectangle, but do so by retaining the order
                // of the older vs newest free rectangles that we may still be placing
                // in calling function split_free_node().
                self.new_rects_free_size -= 1;
                self.new_rects_free[i] = self.new_rects_free[self.new_rects_free_size];
                self.new_rects_free.swap_remove(self.new_rects_free_size);
            } else {
                i += 1;
            }
        }
        self.new_rects_free.push(new_node.to_owned());
    }

    /// Goes through the free rectangles list and removes any redundant nodes.
    fn prune_free_list(&mut self) {
        for rect in &self.rects_free {
            self.new_rects_free.retain(|r| !rect.contains_total(r));
        }

        // For testing purposes: comment the block above and uncomment the block below
        // for rect in &self.rects_free {
        //     let mut j = 0usize;
        //     let mut new_size = self.new_rects_free.len();
        //     while j < new_size {
        //         if rect.contains_total(&self.new_rects_free[j]) {
        //             self.new_rects_free.swap_remove(j);
        //             new_size -= 1;
        //         } else {
        //             // The old free rectangles can never be contained in any of the new free
        //             // rectangles (the new free rectangles keep shrinking in size)
        //             assert!(!rect.contains_total(&self.new_rects_free[j]));
        //
        //             j += 1;
        //         }
        //     }
        // }

        // Merge new and old free rectangles to the group of old free rectangles.
        self.rects_free.append(&mut self.new_rects_free);

        #[cfg(debug_assertions)]
        for (i, rect1) in self.rects_free.iter().enumerate() {
            for rect2 in self.rects_free.iter().skip(i + 1) {
                debug_assert!(!rect1.contains_total(rect2));
                debug_assert!(!rect2.contains_total(rect1));
            }
        }
    }

    /// Returns 0 if the two intervals i1 and i2 are disjoint, or the length of their overlap, otherwise.
    fn common_interval_length(i1start: i32, i1end: i32, i2start: i32, i2end: i32) -> i32 {
        if i1end < i2start || i2end < i1start {
            0
        } else {
            i1end.min(i2end) - i1start.max(i2start)
        }
    }
}

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

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

impl Display for MaxRectsBin {
    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 `rule`.
///
/// 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`]: MaxRectsBin::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::maxrects::{Heuristic, 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 rule
/// let bins = pack_bins(&nodes, 16, 12, Heuristic::BestShortSideFit, 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,
    rule: Heuristic,
    optimized: bool,
) -> Result<Vec<MaxRectsBin>, BinError> {
    if optimized {
        pack_bins_list(nodes, bin_width, bin_height, rule)
    } else {
        pack_bins_single(nodes, bin_width, bin_height, rule)
    }
}

/// Inserts nodes via insert_list().
fn pack_bins_list(
    nodes: &[Dimension],
    bin_width: i32,
    bin_height: i32,
    rule: Heuristic,
) -> Result<Vec<MaxRectsBin>, 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 = MaxRectsBin::new(bin_width, bin_height);
    let (inserted, mut rejected) = bin.insert_list(nodes, rule);

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

        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,
    rule: Heuristic,
) -> Result<Vec<MaxRectsBin>, 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, rule).is_some() {
                inserted = true;
                break;
            }
        }

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

    Ok(bins)
}

#[cfg(test)]
mod tests;