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

jagua_rs/probs/spp/entities/
problem.rs
