jagua_rs/probs/spp/entities/
problem.rs

1use crate::Instant;
2use crate::entities::{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 anyhow::{Result, ensure};
8use itertools::Itertools;
9
10/// Modifiable counterpart of [`SPInstance`]: items can be placed and removed, strip can be extended or fitted.
11#[derive(Clone)]
12pub struct SPProblem {
13    pub(crate) instance: SPInstance,
14    pub(crate) strip: Strip,
15    pub(crate) layout: Layout,
16    pub(crate) item_demand_qtys: Vec<usize>,
17}
18
19impl SPProblem {
20    /// Creates a problem, returning an error if its strip cannot form a container.
21    pub fn new(instance: SPInstance) -> Result<Self> {
22        let item_demand_qtys = instance.items.iter().map(|(_, qty)| *qty).collect_vec();
23        let strip = instance.base_strip;
24        let layout = Layout::new(strip.try_into()?);
25
26        Ok(Self {
27            instance,
28            strip,
29            layout,
30            item_demand_qtys,
31        })
32    }
33
34    /// Modifies the width of the strip in the back, keeping the front fixed.
35    /// Returns an error without changing the problem if the new container is invalid.
36    pub fn change_strip_width(&mut self, new_width: f32) -> Result<()> {
37        ensure!(new_width > 0.0, "strip width must be positive");
38        let mut strip = self.strip;
39        strip.set_width(new_width);
40        let container = strip.try_into()?;
41        self.layout.swap_container(container);
42        self.strip = strip;
43        Ok(())
44    }
45
46    /// Shrinks the strip to the minimum width that fits all items.
47    /// Returns an error if no items are placed.
48    pub fn fit_strip(&mut self) -> Result<()> {
49        ensure!(!self.layout.is_empty(), "cannot fit an empty strip");
50        let collision_free_before = self.layout.is_collision_free();
51
52        //Find the rightmost item in the strip and add some tolerance (avoiding false collision positives)
53        let item_x_max = self
54            .layout
55            .placed_items
56            .values()
57            .map(|pi| pi.shape.bbox.x_max)
58            .max_by(f32::total_cmp)
59            .unwrap()
60            * 1.00001;
61
62        // add the shape offset if any, the strip needs to be at least `offset` wider than the items
63        let fitted_width = item_x_max + self.strip.shape_modify_config.offset.unwrap_or(0.0);
64
65        self.change_strip_width(fitted_width)?;
66        debug_assert_eq!(collision_free_before, self.layout.is_collision_free());
67        Ok(())
68    }
69
70    /// Places an item according to the given `SPPlacement` in the problem.
71    /// Panics if the item's demand is exhausted.
72    pub fn place_item(&mut self, placement: SPPlacement) -> PItemKey {
73        self.register_included_item(placement.item_idx);
74        let item = self.instance.item(placement.item_idx);
75
76        self.layout.place_item(item, placement.d_transf)
77    }
78
79    /// Removes a placed item from the strip. Returns the placement of the item.
80    pub fn remove_item(&mut self, pkey: PItemKey) -> SPPlacement {
81        let pi = self.layout.remove_item(pkey);
82        self.deregister_included_item(pi.item.idx);
83
84        SPPlacement {
85            item_idx: pi.item.idx,
86            d_transf: pi.d_transf,
87        }
88    }
89
90    /// Creates a snapshot of the current state of the problem as a [`SPSolution`].
91    #[must_use]
92    pub fn save(&self) -> SPSolution {
93        let solution = SPSolution {
94            layout_snapshot: self.layout.save(),
95            strip: self.strip,
96            time_stamp: Instant::now(),
97        };
98
99        debug_assert!(problem_matches_solution(self, &solution));
100
101        solution
102    }
103
104    /// Restores the state of the problem to the given [`SPSolution`].
105    pub fn restore(&mut self, solution: &SPSolution) {
106        // A saved solution may use a different strip width.
107        if self.layout.restore(&solution.layout_snapshot).is_err() {
108            self.layout = Layout::from_snapshot(&solution.layout_snapshot);
109        }
110        self.strip = solution.strip;
111
112        //Restore the item demands
113        {
114            self.item_demand_qtys
115                .iter_mut()
116                .enumerate()
117                .for_each(|(idx, qty)| *qty = self.instance.item_qty(idx));
118
119            self.layout
120                .placed_items
121                .iter()
122                .for_each(|(_, pi)| self.item_demand_qtys[pi.item.idx] -= 1);
123        }
124        debug_assert!(problem_matches_solution(self, solution));
125    }
126
127    fn register_included_item(&mut self, item_idx: usize) {
128        assert!(self.item_demand_qtys[item_idx] > 0, "item demand exhausted");
129        self.item_demand_qtys[item_idx] -= 1;
130    }
131
132    fn deregister_included_item(&mut self, item_idx: usize) {
133        self.item_demand_qtys[item_idx] += 1;
134    }
135
136    #[must_use]
137    pub fn instance(&self) -> &SPInstance {
138        &self.instance
139    }
140
141    #[must_use]
142    pub fn strip(&self) -> &Strip {
143        &self.strip
144    }
145
146    #[must_use]
147    pub fn layout(&self) -> &Layout {
148        &self.layout
149    }
150
151    #[must_use]
152    pub fn item_demand_qtys(&self) -> &[usize] {
153        &self.item_demand_qtys
154    }
155
156    #[must_use]
157    pub fn density(&self) -> f32 {
158        self.layout.density()
159    }
160
161    #[must_use]
162    pub fn strip_width(&self) -> f32 {
163        self.strip.width
164    }
165
166    #[must_use]
167    pub fn n_placed_items(&self) -> usize {
168        self.layout.placed_items.len()
169    }
170}
171
172/// Represents a placement of an item in the strip packing problem.
173#[derive(Debug, Clone, Copy)]
174pub struct SPPlacement {
175    pub item_idx: usize,
176    pub d_transf: DTransformation,
177}
jagua_rs/probs/spp/entities/problem.rs

jagua_rs/probs/spp/entities/
problem.rs
