jagua_rs/probs/spp/entities/
problem.rs

1use crate::Instant;
2use crate::entities::{Instance, Layout, PItemKey};
3use crate::geometry::DTransformation;
4use crate::probs::spp::entities::strip::Strip;
5use crate::probs::spp::entities::{SPInstance, SPSolution};
6use crate::probs::spp::util::assertions::problem_matches_solution;
7use itertools::Itertools;
8
9/// Modifiable counterpart of [`SPInstance`]: items can be placed and removed, strip can be extended or fitted.
10#[derive(Clone)]
11pub struct SPProblem {
12    pub instance: SPInstance,
13    pub strip: Strip,
14    pub layout: Layout,
15    pub item_demand_qtys: Vec<usize>,
16}
17
18impl SPProblem {
19    pub fn new(instance: SPInstance) -> Self {
20        let item_demand_qtys = instance.items.iter().map(|(_, qty)| *qty).collect_vec();
21        let strip = instance.base_strip;
22        let layout = Layout::new(strip.into());
23
24        Self {
25            instance,
26            strip,
27            layout,
28            item_demand_qtys,
29        }
30    }
31
32    /// Modifies the width of the strip in the back, keeping the front fixed.
33    pub fn change_strip_width(&mut self, new_width: f32) {
34        self.strip.set_width(new_width);
35        self.layout.swap_container(self.strip.into());
36    }
37
38    /// Shrinks the strip to the minimum width that fits all items.
39    pub fn fit_strip(&mut self) {
40        let feasible_before = self.layout.is_feasible();
41
42        //Find the rightmost item in the strip and add some tolerance (avoiding false collision positives)
43        let item_x_max = self
44            .layout
45            .placed_items
46            .values()
47            .map(|pi| pi.shape.bbox.x_max)
48            .max_by(|a, b| a.partial_cmp(b).unwrap())
49            .unwrap()
50            * 1.00001;
51
52        // add the shape offset if any, the strip needs to be at least `offset` wider than the items
53        let fitted_width = item_x_max + self.strip.shape_modify_config.offset.unwrap_or(0.0);
54
55        self.change_strip_width(fitted_width);
56        debug_assert!(feasible_before == self.layout.is_feasible());
57    }
58
59    /// Places an item according to the given `SPPlacement` in the problem.
60    pub fn place_item(&mut self, placement: SPPlacement) -> PItemKey {
61        self.register_included_item(placement.item_id);
62        let item = self.instance.item(placement.item_id);
63
64        self.layout.place_item(item, placement.d_transf)
65    }
66
67    /// Removes a placed item from the strip. Returns the placement of the item.
68    pub fn remove_item(&mut self, pkey: PItemKey) -> SPPlacement {
69        let pi = self.layout.remove_item(pkey);
70        self.deregister_included_item(pi.item_id);
71
72        SPPlacement {
73            item_id: pi.item_id,
74            d_transf: pi.d_transf,
75        }
76    }
77
78    /// Creates a snapshot of the current state of the problem as a [`SPSolution`].
79    pub fn save(&self) -> SPSolution {
80        let solution = SPSolution {
81            layout_snapshot: self.layout.save(),
82            strip: self.strip,
83            time_stamp: Instant::now(),
84        };
85
86        debug_assert!(problem_matches_solution(self, &solution));
87
88        solution
89    }
90
91    /// Restores the state of the problem to the given [`SPSolution`].
92    pub fn restore(&mut self, solution: &SPSolution) {
93        if self.strip == solution.strip {
94            // the strip is the same, restore the layout
95            self.layout.restore(&solution.layout_snapshot);
96        } else {
97            // the strip has changed, rebuild the layout
98            self.layout = Layout::from_snapshot(&solution.layout_snapshot);
99            self.strip = solution.strip;
100        }
101
102        //Restore the item demands
103        {
104            self.item_demand_qtys
105                .iter_mut()
106                .enumerate()
107                .for_each(|(id, qty)| *qty = self.instance.item_qty(id));
108
109            self.layout
110                .placed_items
111                .iter()
112                .for_each(|(_, pi)| self.item_demand_qtys[pi.item_id] -= 1);
113        }
114        debug_assert!(problem_matches_solution(self, solution));
115    }
116
117    fn register_included_item(&mut self, item_id: usize) {
118        self.item_demand_qtys[item_id] -= 1;
119    }
120
121    fn deregister_included_item(&mut self, item_id: usize) {
122        self.item_demand_qtys[item_id] += 1;
123    }
124
125    pub fn density(&self) -> f32 {
126        self.layout.density(&self.instance)
127    }
128
129    pub fn strip_width(&self) -> f32 {
130        self.strip.width
131    }
132}
133
134/// Represents a placement of an item in the strip packing problem.
135#[derive(Debug, Clone, Copy)]
136pub struct SPPlacement {
137    pub item_id: usize,
138    pub d_transf: DTransformation,
139}
jagua_rs/probs/spp/entities/problem.rs

jagua_rs/probs/spp/entities/
problem.rs
