bin_packer_3d 1.0.0

Three dimensional fitting algorithm to fit smaller boxes inside of a larger box
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

use crate::bin::Bin;
use crate::error::{Error, Result};
use crate::item::{Item, ItemId};

/**
While loop to pack items into a bin, using a First Fit Descending approach.

When you pack an item into a bin, find the best fit, which will change the dimensions available
to pack items into. While there are still items to pack and dimensions large enough to hold at
least one of the items, it will continue to pack the same bin. If there is no remaining space in
the bin large enough for an item, a new dimension will be added to the available blocks. After
there are no more items needing to be packed, returns a list of lists of the items in their
bins. (first bin is first nested list, second is the second, etc.)

```rust
  use bin_packer_3d::bin::Bin;
  use bin_packer_3d::item::Item;
  use bin_packer_3d::packing_algorithm::packing_algorithm;

  let deck = Item::new("deck", [2.0, 8.0, 12.0]);
  let die = Item::new("die", [8.0, 8.0, 8.0]);
  let items = vec![deck.clone(), deck.clone(), die, deck.clone(), deck];

  let packed_items = packing_algorithm(Bin::new([8.0, 8.0, 12.0]), &items);
  assert_eq!(packed_items, Ok(vec![vec!["deck", "deck", "deck", "deck"], vec!["die"]]));
```
**/

pub fn packing_algorithm<'a>(
    bin: Bin<'a>,
    items: &'a Vec<Item<'_>>,
) -> Result<Vec<Vec<&'a ItemId>>> {
    if !items.iter().all(|item| bin.fits(item)) {
        return Err(Error::AllItemsMustFit(format!(
            "All items must fit within the bin dimensions."
        )));
    }

    let mut items_to_pack = items.clone();

    // Sort the items in descending order, where order is based on the longest dimension:

    items_to_pack.sort_by(|a, b| b.cmp(&a));

    let mut packed_bins: Vec<Bin<'a>> = Vec::new();
    let mut bin_currently_packing = bin.clone_as_empty_bin();

    loop {
        match (
            items_to_pack.is_empty(),
            bin_currently_packing.items.is_empty(),
        ) {
            (true, true) => break,
            (true, false) => {
                // no more items to pack:
                packed_bins.push(bin_currently_packing);
                break;
            }
            (false, _) => {
                if let Some(packed_item_index) = items_to_pack
                    .clone()
                    .into_iter()
                    .enumerate()
                    .find_map(|(item_index, item)| {
                        bin_currently_packing.try_packing(item).map(|_| item_index)
                    })
                {
                    items_to_pack.remove(packed_item_index);
                } else {
                    // We can't fit any more items into the current bin - add it to our packed_bins, and
                    // open up a new bin to pack.

                    let packed_bin =
                        std::mem::replace(&mut bin_currently_packing, bin.clone_as_empty_bin());
                    packed_bins.push(packed_bin);
                }
            }
        }
    }

    // map the bins back into their Vec<ItemId> representations:

    Ok(packed_bins
        .into_iter()
        .map(|bin| bin.items.into_iter().map(|item| item.id).collect())
        .collect())
}