bin_packing/two_d/
model.rs

1//! Data model types for 2D rectangular bin packing problems and solutions.
2
3use serde::{Deserialize, Serialize};
4
5use crate::{BinPackingError, Result};
6
7/// Algorithm selector for [`solve_2d`](super::solve_2d).
8#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, Default)]
9#[serde(rename_all = "snake_case")]
10pub enum TwoDAlgorithm {
11    /// Try multiple strategies and return the best.
12    #[default]
13    Auto,
14    /// Classic MaxRects best-area-fit construction.
15    MaxRects,
16    /// MaxRects with best-short-side-fit placement scoring.
17    MaxRectsBestShortSideFit,
18    /// MaxRects with best-long-side-fit placement scoring.
19    MaxRectsBestLongSideFit,
20    /// MaxRects with bottom-left placement scoring.
21    MaxRectsBottomLeft,
22    /// MaxRects with contact-point placement scoring.
23    MaxRectsContactPoint,
24    /// Skyline-based construction.
25    Skyline,
26    /// Skyline construction ranked by minimum waste.
27    SkylineMinWaste,
28    /// Guillotine beam search.
29    Guillotine,
30    /// Guillotine beam search with best-short-side-fit candidate ranking.
31    GuillotineBestShortSideFit,
32    /// Guillotine beam search with best-long-side-fit candidate ranking.
33    GuillotineBestLongSideFit,
34    /// Guillotine beam search with shorter-leftover-axis split selection.
35    GuillotineShorterLeftoverAxis,
36    /// Guillotine beam search with longer-leftover-axis split selection.
37    GuillotineLongerLeftoverAxis,
38    /// Guillotine beam search with minimum-area split selection.
39    GuillotineMinAreaSplit,
40    /// Guillotine beam search with maximum-area split selection.
41    GuillotineMaxAreaSplit,
42    /// Next-fit decreasing height shelf heuristic.
43    NextFitDecreasingHeight,
44    /// First-fit decreasing height shelf heuristic.
45    FirstFitDecreasingHeight,
46    /// Best-fit decreasing height shelf heuristic.
47    BestFitDecreasingHeight,
48    /// Multistart MaxRects meta-strategy.
49    MultiStart,
50}
51
52/// A sheet stock entry that demands can be placed on.
53#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
54pub struct Sheet2D {
55    /// Human-readable identifier for this sheet type.
56    pub name: String,
57    /// Sheet width.
58    pub width: u32,
59    /// Sheet height.
60    pub height: u32,
61    /// Per-unit cost of consuming a sheet of this type.
62    #[serde(default = "default_sheet_cost")]
63    pub cost: f64,
64    /// Optional cap on the number of sheets of this type that may be used.
65    #[serde(default)]
66    pub quantity: Option<usize>,
67}
68
69/// A demand for a set of identical rectangular pieces.
70#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
71pub struct RectDemand2D {
72    /// Human-readable identifier for the demand.
73    pub name: String,
74    /// Required width of each rectangle.
75    pub width: u32,
76    /// Required height of each rectangle.
77    pub height: u32,
78    /// Number of identical rectangles required.
79    pub quantity: usize,
80    /// Whether the solver may rotate this rectangle 90 degrees.
81    #[serde(default = "default_can_rotate")]
82    pub can_rotate: bool,
83}
84
85/// A single rectangle placed on a packed sheet.
86#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
87pub struct Placement2D {
88    /// Name of the originating demand.
89    pub name: String,
90    /// X offset of the rectangle's top-left corner on the sheet.
91    pub x: u32,
92    /// Y offset of the rectangle's top-left corner on the sheet.
93    pub y: u32,
94    /// Width of the placed rectangle after any rotation.
95    pub width: u32,
96    /// Height of the placed rectangle after any rotation.
97    pub height: u32,
98    /// Whether the rectangle was rotated 90 degrees from its declared orientation.
99    pub rotated: bool,
100}
101
102/// A single packed sheet layout produced by the solver.
103#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
104pub struct SheetLayout2D {
105    /// Name of the sheet type consumed by this layout.
106    pub sheet_name: String,
107    /// Sheet width.
108    pub width: u32,
109    /// Sheet height.
110    pub height: u32,
111    /// Cost of consuming this sheet.
112    pub cost: f64,
113    /// Rectangles placed on this sheet.
114    pub placements: Vec<Placement2D>,
115    /// Total area occupied by the placements.
116    pub used_area: u64,
117    /// Total wasted area on this sheet.
118    pub waste_area: u64,
119}
120
121/// Metrics captured while running a 2D solver.
122#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
123pub struct SolverMetrics2D {
124    /// Number of top-level solver iterations performed.
125    pub iterations: usize,
126    /// Number of states explored during search.
127    pub explored_states: usize,
128    /// Free-form notes emitted by the solver for diagnostics.
129    pub notes: Vec<String>,
130}
131
132/// A complete solution returned by [`solve_2d`](super::solve_2d).
133#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
134pub struct TwoDSolution {
135    /// Name of the algorithm that produced this solution.
136    pub algorithm: String,
137    /// Whether the layouts are guillotine-compatible.
138    pub guillotine: bool,
139    /// Number of sheets consumed.
140    pub sheet_count: usize,
141    /// Total wasted area across all sheets.
142    pub total_waste_area: u64,
143    /// Total material cost across all sheets.
144    pub total_cost: f64,
145    /// Per-sheet layouts in descending order of utilization.
146    pub layouts: Vec<SheetLayout2D>,
147    /// Rectangles the solver was unable to place.
148    pub unplaced: Vec<RectDemand2D>,
149    /// Metrics captured while solving.
150    pub metrics: SolverMetrics2D,
151}
152
153/// Input problem passed to [`solve_2d`](super::solve_2d).
154#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
155pub struct TwoDProblem {
156    /// Available sheet types.
157    pub sheets: Vec<Sheet2D>,
158    /// Rectangular demands to be placed on the sheets.
159    pub demands: Vec<RectDemand2D>,
160}
161
162/// Options controlling how [`solve_2d`](super::solve_2d) runs.
163#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
164pub struct TwoDOptions {
165    /// Algorithm to dispatch to.
166    #[serde(default)]
167    pub algorithm: TwoDAlgorithm,
168    /// Number of multistart restarts used by randomized strategies.
169    #[serde(default = "default_multistart_runs")]
170    pub multistart_runs: usize,
171    /// Beam width for the guillotine beam search backend.
172    #[serde(default = "default_beam_width")]
173    pub beam_width: usize,
174    /// Whether layouts must be guillotine-compatible.
175    #[serde(default)]
176    pub guillotine_required: bool,
177    /// Optional seed for reproducible randomized algorithms.
178    #[serde(default)]
179    pub seed: Option<u64>,
180}
181
182impl Default for TwoDOptions {
183    fn default() -> Self {
184        Self {
185            algorithm: TwoDAlgorithm::Auto,
186            multistart_runs: default_multistart_runs(),
187            beam_width: default_beam_width(),
188            guillotine_required: false,
189            seed: None,
190        }
191    }
192}
193
194#[derive(Debug, Clone, PartialEq, Eq)]
195pub(crate) struct ItemInstance2D {
196    pub(crate) name: String,
197    pub(crate) width: u32,
198    pub(crate) height: u32,
199    pub(crate) can_rotate: bool,
200}
201
202impl ItemInstance2D {
203    pub(crate) fn orientations(&self) -> impl Iterator<Item = (u32, u32, bool)> + '_ {
204        let primary = std::iter::once((self.width, self.height, false));
205        let rotated = self
206            .can_rotate
207            .then_some((self.height, self.width, true))
208            .filter(|(width, height, _)| *width != self.width || *height != self.height)
209            .into_iter();
210        primary.chain(rotated)
211    }
212}
213
214const MAX_DIMENSION: u32 = 1 << 30;
215
216#[derive(Debug, Clone, Copy, PartialEq, Eq)]
217pub(crate) struct Rect {
218    pub(crate) x: u32,
219    pub(crate) y: u32,
220    pub(crate) width: u32,
221    pub(crate) height: u32,
222}
223
224impl TwoDProblem {
225    pub(crate) fn validate(&self) -> Result<()> {
226        if self.sheets.is_empty() {
227            return Err(BinPackingError::InvalidInput(
228                "at least one sheet stock entry is required".to_string(),
229            ));
230        }
231
232        if self.demands.is_empty() {
233            return Err(BinPackingError::InvalidInput(
234                "at least one rectangular demand entry is required".to_string(),
235            ));
236        }
237
238        for sheet in &self.sheets {
239            if sheet.width == 0 || sheet.height == 0 {
240                return Err(BinPackingError::InvalidInput(format!(
241                    "sheet `{}` must have positive width and height",
242                    sheet.name
243                )));
244            }
245
246            if sheet.width > MAX_DIMENSION || sheet.height > MAX_DIMENSION {
247                return Err(BinPackingError::InvalidInput(format!(
248                    "sheet `{}` dimensions exceed the supported maximum of {}",
249                    sheet.name, MAX_DIMENSION
250                )));
251            }
252
253            if !sheet.cost.is_finite() || sheet.cost < 0.0 {
254                return Err(BinPackingError::InvalidInput(format!(
255                    "sheet `{}` must have a finite non-negative cost",
256                    sheet.name
257                )));
258            }
259        }
260
261        for demand in &self.demands {
262            if demand.width == 0 || demand.height == 0 {
263                return Err(BinPackingError::InvalidInput(format!(
264                    "demand `{}` must have positive width and height",
265                    demand.name
266                )));
267            }
268
269            if demand.width > MAX_DIMENSION || demand.height > MAX_DIMENSION {
270                return Err(BinPackingError::InvalidInput(format!(
271                    "demand `{}` dimensions exceed the supported maximum of {}",
272                    demand.name, MAX_DIMENSION
273                )));
274            }
275
276            if demand.quantity == 0 {
277                return Err(BinPackingError::InvalidInput(format!(
278                    "demand `{}` must have positive quantity",
279                    demand.name
280                )));
281            }
282        }
283
284        Ok(())
285    }
286
287    pub(crate) fn ensure_feasible_demands(&self) -> Result<()> {
288        for demand in &self.demands {
289            let feasible = self.sheets.iter().any(|sheet| {
290                (sheet.width >= demand.width && sheet.height >= demand.height)
291                    || (demand.can_rotate
292                        && sheet.width >= demand.height
293                        && sheet.height >= demand.width)
294            });
295
296            if !feasible {
297                return Err(BinPackingError::Infeasible2D {
298                    item: demand.name.clone(),
299                    width: demand.width,
300                    height: demand.height,
301                });
302            }
303        }
304
305        Ok(())
306    }
307
308    pub(crate) fn expanded_items(&self) -> Vec<ItemInstance2D> {
309        let mut items = Vec::new();
310        for demand in &self.demands {
311            for _ in 0..demand.quantity {
312                items.push(ItemInstance2D {
313                    name: demand.name.clone(),
314                    width: demand.width,
315                    height: demand.height,
316                    can_rotate: demand.can_rotate,
317                });
318            }
319        }
320
321        items
322    }
323}
324
325impl Rect {
326    pub(crate) fn area(self) -> u64 {
327        u64::from(self.width) * u64::from(self.height)
328    }
329
330    pub(crate) fn fits(self, width: u32, height: u32) -> bool {
331        width <= self.width && height <= self.height
332    }
333
334    pub(crate) fn intersects(self, other: Self) -> bool {
335        let self_right = self.x.saturating_add(self.width);
336        let self_bottom = self.y.saturating_add(self.height);
337        let other_right = other.x.saturating_add(other.width);
338        let other_bottom = other.y.saturating_add(other.height);
339
340        self.x < other_right
341            && self_right > other.x
342            && self.y < other_bottom
343            && self_bottom > other.y
344    }
345
346    pub(crate) fn contains(self, other: Self) -> bool {
347        self.x <= other.x
348            && self.y <= other.y
349            && self.x.saturating_add(self.width) >= other.x.saturating_add(other.width)
350            && self.y.saturating_add(self.height) >= other.y.saturating_add(other.height)
351    }
352}
353
354impl TwoDSolution {
355    pub(crate) fn from_layouts(
356        algorithm: impl Into<String>,
357        guillotine: bool,
358        sheets: &[Sheet2D],
359        layouts: Vec<(usize, Vec<Placement2D>)>,
360        unplaced_items: Vec<ItemInstance2D>,
361        metrics: SolverMetrics2D,
362    ) -> Self {
363        let mut computed_layouts = layouts
364            .into_iter()
365            .map(|(sheet_index, placements)| {
366                let sheet = &sheets[sheet_index];
367                let sheet_area = u64::from(sheet.width) * u64::from(sheet.height);
368                let used_area = placements
369                    .iter()
370                    .map(|placement| u64::from(placement.width) * u64::from(placement.height))
371                    .sum::<u64>();
372                // In debug builds, fail loudly if a solver produced more used
373                // area than the sheet provides — that indicates overlapping or
374                // off-sheet placements upstream. Release builds fall back to
375                // saturating subtraction so the bug surfaces as "0 waste"
376                // instead of a u64 underflow panic.
377                debug_assert!(
378                    used_area <= sheet_area,
379                    "sheet `{}` placements use {used_area} area but sheet capacity is {sheet_area}",
380                    sheet.name,
381                );
382                let waste_area = sheet_area.saturating_sub(used_area);
383
384                SheetLayout2D {
385                    sheet_name: sheet.name.clone(),
386                    width: sheet.width,
387                    height: sheet.height,
388                    cost: sheet.cost,
389                    placements,
390                    used_area,
391                    waste_area,
392                }
393            })
394            .collect::<Vec<_>>();
395
396        computed_layouts.sort_by(|left, right| {
397            right
398                .used_area
399                .cmp(&left.used_area)
400                .then_with(|| left.sheet_name.cmp(&right.sheet_name))
401        });
402
403        let total_waste_area = computed_layouts.iter().map(|layout| layout.waste_area).sum();
404        let total_cost = computed_layouts.iter().map(|layout| layout.cost).sum();
405        let mut unplaced = unplaced_items
406            .into_iter()
407            .map(|item| RectDemand2D {
408                name: item.name,
409                width: item.width,
410                height: item.height,
411                quantity: 1,
412                can_rotate: item.can_rotate,
413            })
414            .collect::<Vec<_>>();
415        unplaced.sort_by(|left, right| {
416            let left_area = u64::from(left.width) * u64::from(left.height);
417            let right_area = u64::from(right.width) * u64::from(right.height);
418            right_area.cmp(&left_area)
419        });
420
421        Self {
422            algorithm: algorithm.into(),
423            guillotine,
424            sheet_count: computed_layouts.len(),
425            total_waste_area,
426            total_cost,
427            layouts: computed_layouts,
428            unplaced,
429            metrics,
430        }
431    }
432
433    pub(crate) fn is_better_than(&self, other: &Self) -> bool {
434        (
435            self.unplaced.len(),
436            self.sheet_count,
437            self.total_waste_area,
438            OrderedFloat(self.total_cost),
439        ) < (
440            other.unplaced.len(),
441            other.sheet_count,
442            other.total_waste_area,
443            OrderedFloat(other.total_cost),
444        )
445    }
446}
447
448#[derive(Debug, Clone, Copy, PartialEq)]
449struct OrderedFloat(pub f64);
450
451impl Eq for OrderedFloat {}
452
453impl PartialOrd for OrderedFloat {
454    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
455        Some(self.cmp(other))
456    }
457}
458
459impl Ord for OrderedFloat {
460    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
461        self.0.total_cmp(&other.0)
462    }
463}
464
465fn default_sheet_cost() -> f64 {
466    1.0
467}
468
469fn default_can_rotate() -> bool {
470    true
471}
472
473fn default_multistart_runs() -> usize {
474    12
475}
476
477fn default_beam_width() -> usize {
478    8
479}
480
481#[cfg(test)]
482mod tests {
483    use serde_json::json;
484
485    use super::*;
486
487    fn sample_problem() -> TwoDProblem {
488        TwoDProblem {
489            sheets: vec![Sheet2D {
490                name: "sheet".to_string(),
491                width: 10,
492                height: 8,
493                cost: 1.0,
494                quantity: None,
495            }],
496            demands: vec![
497                RectDemand2D {
498                    name: "panel".to_string(),
499                    width: 4,
500                    height: 3,
501                    quantity: 2,
502                    can_rotate: true,
503                },
504                RectDemand2D {
505                    name: "brace".to_string(),
506                    width: 2,
507                    height: 2,
508                    quantity: 1,
509                    can_rotate: false,
510                },
511            ],
512        }
513    }
514
515    #[test]
516    fn serde_defaults_fill_in_optional_sheet_and_option_fields() {
517        let sheet: Sheet2D =
518            serde_json::from_value(json!({ "name": "sheet", "width": 12, "height": 8 }))
519                .expect("sheet");
520        assert_eq!(sheet.cost, 1.0);
521        assert_eq!(sheet.quantity, None);
522
523        let demand: RectDemand2D = serde_json::from_value(
524            json!({ "name": "panel", "width": 5, "height": 4, "quantity": 1 }),
525        )
526        .expect("demand");
527        assert!(demand.can_rotate);
528
529        let options: TwoDOptions = serde_json::from_value(json!({})).expect("options");
530        assert_eq!(options, TwoDOptions::default());
531    }
532
533    #[test]
534    fn validation_rejects_missing_or_invalid_two_d_inputs() {
535        let missing_sheets = TwoDProblem { sheets: Vec::new(), demands: sample_problem().demands };
536        assert!(matches!(
537            missing_sheets.validate(),
538            Err(BinPackingError::InvalidInput(message))
539                if message == "at least one sheet stock entry is required"
540        ));
541
542        let missing_demands = TwoDProblem { sheets: sample_problem().sheets, demands: Vec::new() };
543        assert!(matches!(
544            missing_demands.validate(),
545            Err(BinPackingError::InvalidInput(message))
546                if message == "at least one rectangular demand entry is required"
547        ));
548
549        let zero_sheet = TwoDProblem {
550            sheets: vec![Sheet2D {
551                name: "sheet".to_string(),
552                width: 0,
553                height: 8,
554                cost: 1.0,
555                quantity: None,
556            }],
557            demands: vec![RectDemand2D {
558                name: "panel".to_string(),
559                width: 1,
560                height: 1,
561                quantity: 1,
562                can_rotate: false,
563            }],
564        };
565        assert!(matches!(
566            zero_sheet.validate(),
567            Err(BinPackingError::InvalidInput(message))
568                if message == "sheet `sheet` must have positive width and height"
569        ));
570
571        let zero_demand = TwoDProblem {
572            sheets: vec![Sheet2D {
573                name: "sheet".to_string(),
574                width: 8,
575                height: 8,
576                cost: 1.0,
577                quantity: None,
578            }],
579            demands: vec![RectDemand2D {
580                name: "panel".to_string(),
581                width: 0,
582                height: 2,
583                quantity: 1,
584                can_rotate: false,
585            }],
586        };
587        assert!(matches!(
588            zero_demand.validate(),
589            Err(BinPackingError::InvalidInput(message))
590                if message == "demand `panel` must have positive width and height"
591        ));
592
593        let zero_quantity = TwoDProblem {
594            sheets: vec![Sheet2D {
595                name: "sheet".to_string(),
596                width: 8,
597                height: 8,
598                cost: 1.0,
599                quantity: None,
600            }],
601            demands: vec![RectDemand2D {
602                name: "panel".to_string(),
603                width: 2,
604                height: 2,
605                quantity: 0,
606                can_rotate: false,
607            }],
608        };
609        assert!(matches!(
610            zero_quantity.validate(),
611            Err(BinPackingError::InvalidInput(message))
612                if message == "demand `panel` must have positive quantity"
613        ));
614    }
615
616    #[test]
617    fn feasibility_expansion_and_geometry_helpers_cover_rotation_paths() {
618        let feasible = sample_problem();
619        feasible.validate().expect("sample input should validate");
620        feasible.ensure_feasible_demands().expect("sample input should be feasible");
621
622        let rotated_only = TwoDProblem {
623            sheets: vec![Sheet2D {
624                name: "sheet".to_string(),
625                width: 4,
626                height: 6,
627                cost: 1.0,
628                quantity: None,
629            }],
630            demands: vec![RectDemand2D {
631                name: "rotated".to_string(),
632                width: 6,
633                height: 4,
634                quantity: 1,
635                can_rotate: true,
636            }],
637        };
638        rotated_only.ensure_feasible_demands().expect("rotation should make item feasible");
639
640        let infeasible = TwoDProblem {
641            sheets: vec![Sheet2D {
642                name: "sheet".to_string(),
643                width: 4,
644                height: 6,
645                cost: 1.0,
646                quantity: None,
647            }],
648            demands: vec![RectDemand2D {
649                name: "oversized".to_string(),
650                width: 7,
651                height: 4,
652                quantity: 1,
653                can_rotate: false,
654            }],
655        };
656        assert!(matches!(
657            infeasible.ensure_feasible_demands(),
658            Err(BinPackingError::Infeasible2D { item, width, height })
659                if item == "oversized" && width == 7 && height == 4
660        ));
661
662        let items = feasible.expanded_items();
663        assert_eq!(items.len(), 3);
664        assert_eq!(items[0].name, "panel");
665        assert_eq!(items[2].name, "brace");
666
667        let outer = Rect { x: 0, y: 0, width: 10, height: 8 };
668        let inner = Rect { x: 2, y: 2, width: 3, height: 4 };
669        let disjoint = Rect { x: 10, y: 0, width: 2, height: 2 };
670        assert_eq!(outer.area(), 80);
671        assert!(outer.fits(5, 4));
672        assert!(outer.contains(inner));
673        assert!(outer.intersects(inner));
674        assert!(!outer.intersects(disjoint));
675    }
676
677    #[test]
678    fn from_layouts_sorts_outputs_and_better_than_prefers_fewer_sheets() {
679        let sheets = vec![
680            Sheet2D { name: "alpha".to_string(), width: 10, height: 10, cost: 2.0, quantity: None },
681            Sheet2D { name: "beta".to_string(), width: 8, height: 8, cost: 1.0, quantity: None },
682        ];
683
684        let solution = TwoDSolution::from_layouts(
685            "maxrects",
686            false,
687            &sheets,
688            vec![
689                (
690                    1,
691                    vec![Placement2D {
692                        name: "small".to_string(),
693                        x: 0,
694                        y: 0,
695                        width: 4,
696                        height: 4,
697                        rotated: false,
698                    }],
699                ),
700                (
701                    0,
702                    vec![
703                        Placement2D {
704                            name: "large".to_string(),
705                            x: 0,
706                            y: 0,
707                            width: 5,
708                            height: 5,
709                            rotated: false,
710                        },
711                        Placement2D {
712                            name: "medium".to_string(),
713                            x: 5,
714                            y: 0,
715                            width: 2,
716                            height: 2,
717                            rotated: false,
718                        },
719                    ],
720                ),
721            ],
722            vec![
723                ItemInstance2D { name: "wide".to_string(), width: 6, height: 2, can_rotate: true },
724                ItemInstance2D { name: "tiny".to_string(), width: 1, height: 1, can_rotate: false },
725            ],
726            SolverMetrics2D { iterations: 3, explored_states: 2, notes: vec!["test".to_string()] },
727        );
728
729        assert_eq!(solution.layouts[0].sheet_name, "alpha");
730        assert_eq!(solution.layouts[1].sheet_name, "beta");
731        assert_eq!(solution.unplaced[0].name, "wide");
732        assert_eq!(solution.total_cost, 3.0);
733        assert_eq!(solution.total_waste_area, 119);
734
735        let worse = TwoDSolution { sheet_count: solution.sheet_count + 1, ..solution.clone() };
736        assert!(solution.is_better_than(&worse));
737    }
738
739    /// Edge cases for `Rect` geometry helpers that the placement code relies
740    /// on. Each assertion pins down behavior that a plausible refactor could
741    /// silently flip (for example, changing `intersects` to use `<=` instead
742    /// of `<` would turn edge-touching rectangles into overlapping ones).
743    #[test]
744    fn rect_helpers_handle_boundary_cases() {
745        // Touching along a single edge does NOT count as intersecting.
746        // `left_right == right.x` means the strict `<` in `intersects` fails.
747        let left = Rect { x: 0, y: 0, width: 5, height: 5 };
748        let right = Rect { x: 5, y: 0, width: 5, height: 5 };
749        assert!(!left.intersects(right), "edge-touching rects are not intersecting");
750        assert!(!right.intersects(left), "intersects is symmetric for edge-touching rects");
751
752        // Touching at a single corner is also not intersecting.
753        let corner = Rect { x: 5, y: 5, width: 5, height: 5 };
754        assert!(!left.intersects(corner));
755
756        // Overlap by even one unit IS intersecting.
757        let overlap_by_one = Rect { x: 4, y: 0, width: 5, height: 5 };
758        assert!(left.intersects(overlap_by_one));
759
760        // Self-containment holds (contains uses `<=` and `>=`).
761        assert!(left.contains(left), "a rect should contain itself");
762
763        // Exact fit — `fits` uses `<=` so identical dimensions are accepted.
764        assert!(left.fits(5, 5));
765        // One unit larger in either dimension does not fit.
766        assert!(!left.fits(6, 5));
767        assert!(!left.fits(5, 6));
768
769        // Area widens to u64 so extreme dimensions do not overflow.
770        let huge = Rect { x: 0, y: 0, width: u32::MAX, height: u32::MAX };
771        assert_eq!(huge.area(), u64::from(u32::MAX) * u64::from(u32::MAX));
772    }
773
774    /// `TwoDSolution::is_better_than` compares on a 4-key tuple:
775    /// (unplaced count, sheet_count, total_waste_area, total_cost).
776    /// Verify each key is consulted in order as a tiebreaker.
777    #[test]
778    fn two_d_is_better_than_tie_breaks_on_each_key() {
779        let sheets = vec![Sheet2D {
780            name: "s".to_string(),
781            width: 10,
782            height: 10,
783            cost: 1.0,
784            quantity: None,
785        }];
786        let base = TwoDSolution::from_layouts(
787            "test",
788            false,
789            &sheets,
790            vec![(
791                0,
792                vec![Placement2D {
793                    name: "x".to_string(),
794                    x: 0,
795                    y: 0,
796                    width: 5,
797                    height: 5,
798                    rotated: false,
799                }],
800            )],
801            Vec::new(),
802            SolverMetrics2D { iterations: 0, explored_states: 0, notes: Vec::new() },
803        );
804
805        // Fewer unplaced beats more unplaced (primary key).
806        let more_unplaced = TwoDSolution {
807            unplaced: vec![RectDemand2D {
808                name: "u".to_string(),
809                width: 1,
810                height: 1,
811                quantity: 1,
812                can_rotate: false,
813            }],
814            ..base.clone()
815        };
816        assert!(base.is_better_than(&more_unplaced));
817        assert!(!more_unplaced.is_better_than(&base));
818
819        // Fewer sheets wins when unplaced ties.
820        let more_sheets = TwoDSolution { sheet_count: base.sheet_count + 1, ..base.clone() };
821        assert!(base.is_better_than(&more_sheets));
822
823        // Less waste wins when unplaced and sheets tie.
824        let more_waste =
825            TwoDSolution { total_waste_area: base.total_waste_area + 100, ..base.clone() };
826        assert!(base.is_better_than(&more_waste));
827
828        // Lower cost wins when every preceding key ties.
829        let more_cost = TwoDSolution { total_cost: base.total_cost + 1.0, ..base.clone() };
830        assert!(base.is_better_than(&more_cost));
831
832        // Strictly equal solutions are not "better than" each other.
833        assert!(!base.is_better_than(&base));
834    }
835
836    /// `ItemInstance2D::orientations` should collapse the rotated orientation
837    /// to a no-op when the item is square, even if `can_rotate` is true.
838    /// That avoids the solver double-evaluating an identical placement.
839    #[test]
840    fn item_orientations_collapse_squares_to_one_arm() {
841        let square =
842            ItemInstance2D { name: "square".to_string(), width: 5, height: 5, can_rotate: true };
843        let orientations = square.orientations().collect::<Vec<_>>();
844        assert_eq!(
845            orientations.len(),
846            1,
847            "square with can_rotate=true should emit exactly one orientation"
848        );
849        assert_eq!(orientations[0], (5, 5, false));
850
851        let non_square =
852            ItemInstance2D { name: "rect".to_string(), width: 3, height: 7, can_rotate: true };
853        let orientations = non_square.orientations().collect::<Vec<_>>();
854        assert_eq!(orientations.len(), 2);
855        assert_eq!(orientations[0], (3, 7, false));
856        assert_eq!(orientations[1], (7, 3, true));
857
858        let non_rotatable =
859            ItemInstance2D { name: "rect".to_string(), width: 3, height: 7, can_rotate: false };
860        let orientations = non_rotatable.orientations().collect::<Vec<_>>();
861        assert_eq!(orientations.len(), 1);
862        assert_eq!(orientations[0], (3, 7, false));
863    }
864}
bin_packing/two_d/model.rs

bin_packing/two_d/
model.rs
