pack_it_up 1.1.0

pack_it_up is a simple Rust library that implements various bin packing algorithms
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use crate::online::first_fit::__internal_first_fit;
use crate::wrapper::SizedWrapper;
use crate::{Bin, Pack};

/// Pack items in bins using the [First-fit-decreasing](https://en.wikipedia.org/wiki/First-fit-decreasing_bin_packing)
/// bin packing algorithm.
pub fn first_fit_decreasing<T>(bin_size: usize, mut items: Vec<T>) -> Vec<Bin<T>>
where
    T: Pack,
{
    assert!(bin_size > 0, "Bin size must be greater than 0");

    // Sort the items in decreasing order
    items.sort_unstable_by(|a, b| b.size().cmp(&a.size()));

    let lower_bound: usize = ((items.iter().map(|item| item.size()).sum::<usize>() as f64)
        / (bin_size as f64))
        .ceil() as usize;

    // Use the normal first fit implementation
    __internal_first_fit(bin_size, items, lower_bound)
}

/// Pack items in bins using the [First-fit-decreasing](https://en.wikipedia.org/wiki/First-fit-decreasing_bin_packing)
/// bin packing algorithm.
///
/// Unlike [`first_fit_decreasing`], the items don't have to implement [`Pack`].
/// Instead, you need to provide a function that returns the size of the item.
///
/// This function will be cloned for each item
/// (but if it's a simple function pointer or a non-capturing closure, then it is a no-op).

pub fn first_fit_decreasing_by_key<T, SizeFunc>(
    bin_size: usize,
    items: Vec<T>,
    key_func: SizeFunc,
) -> Vec<Bin<T>>
where
    SizeFunc: Fn(&T) -> usize + Clone,
{
    assert!(bin_size > 0, "Bin size must be greater than 0");

    // Sort the items in decreasing order
    let mut items: Vec<_> = items
        .into_iter()
        .map(|item| SizedWrapper::new(key_func.clone(), item))
        .collect();

    items.sort_unstable_by(|a, b| b.size().cmp(&a.size()));

    let lower_bound: usize = ((items.iter().map(|item| item.size()).sum::<usize>() as f64)
        / (bin_size as f64))
        .ceil() as usize;

    // Use the normal first fit implementation
    __internal_first_fit(bin_size, items, lower_bound)
        .into_iter()
        .map(|bin| bin.map(|item| item.take()))
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::tests::{generate_test_bins, generate_test_set_a};

    #[test]
    fn it_works() {
        let (test_data, bin_size) = generate_test_set_a();

        let result = first_fit_decreasing(bin_size, test_data);

        // First fit decreasing would result in the optimal solution

        let expected = generate_test_bins(
            20,
            vec![
                vec![19, 1],          // 20
                vec![19, 1],          // 20
                vec![10, 10],         // 20
                vec![10, 4, 3, 1, 1], //19
            ],
        );

        assert_eq!(expected, result)
    }

    #[test]
    fn it_works_by_key() {
        let (test_data, bin_size) = generate_test_set_a();

        let test_data = test_data
            .into_iter()
            .map(|item| item.make_unpacked())
            .collect::<Vec<_>>();

        let result = first_fit_decreasing_by_key(bin_size, test_data, |item| item.size);

        // First fit decreasing by key would result in the optimal solution

        let expected: Vec<_> = generate_test_bins(
            20,
            vec![
                vec![19, 1],          // 20
                vec![19, 1],          // 20
                vec![10, 10],         // 20
                vec![10, 4, 3, 1, 1], //19
            ],
        )
        .into_iter()
        .map(|bin| bin.map(|item| item.make_unpacked()))
        .collect();

        assert_eq!(expected, result)
    }
}