taffy/compute/grid/types/
cell_occupancy.rs

1//! Contains CellOccupancyMatrix used to track occupied cells during grid placement
2use super::TrackCounts;
3use crate::compute::grid::OriginZeroLine;
4use crate::geometry::AbsoluteAxis;
5use crate::geometry::Line;
6use crate::util::sys::{new_vec_with_capacity, Vec};
7use core::cmp::{max, min};
8use core::fmt::Debug;
9use core::ops::Range;
10use smallvec::SmallVec;
11
12/// The occupancy state of a single grid cell
13#[derive(Debug, PartialEq, Eq, Clone, Copy, Default)]
14pub(crate) enum CellOccupancyState {
15    #[default]
16    /// Indicates that a grid cell is unoccupied
17    Unoccupied,
18    /// Indicates that a grid cell is occupied by a definitely placed item
19    DefinitelyPlaced,
20    /// Indicates that a grid cell is occupied by an item that was placed by the auto placement algorithm
21    AutoPlaced,
22}
23
24/// A run of occupied cells within a single track. The range is in OriginZero line coordinates
25/// along the track (so for a row track, the range spans column lines and vice versa).
26#[derive(Debug, Clone, PartialEq, Eq)]
27struct OccupiedInterval {
28    /// The range of cells covered by this interval (start line..end line in OriginZero coordinates)
29    range: Range<i16>,
30    /// The occupancy state of every cell within this interval
31    state: CellOccupancyState,
32}
33
34impl OccupiedInterval {
35    /// Whether this interval overlaps the given range
36    fn overlaps(&self, range: &Range<i16>) -> bool {
37        self.range.start < range.end && self.range.end > range.start
38    }
39}
40
41/// The occupied cells of a single track, stored as a sorted list of disjoint intervals in
42/// OriginZero line coordinates. Gaps between intervals are unoccupied. Touching intervals
43/// with the same state are merged.
44#[derive(Debug, Clone, Default)]
45struct TrackIntervals {
46    /// The sorted, disjoint list of occupied intervals within the track
47    intervals: SmallVec<[OccupiedInterval; 2]>,
48    /// The furthest end line of an auto-placed item starting in this secondary-axis track
49    auto_placement_cursor: Option<OriginZeroLine>,
50}
51
52impl TrackIntervals {
53    /// Whether the track contains any occupied cells
54    fn is_empty(&self) -> bool {
55        self.intervals.is_empty()
56    }
57
58    /// The occupancy state of the cell whose start line is at `coordinate`
59    fn state_at(&self, coordinate: i16) -> CellOccupancyState {
60        self.intervals
61            .iter()
62            .find(|interval| interval.range.start <= coordinate && coordinate < interval.range.end)
63            .map(|interval| interval.state)
64            .unwrap_or(CellOccupancyState::Unoccupied)
65    }
66
67    /// Set the cells covered by `range` to `state`, overwriting the state of any already-occupied
68    /// cells within the range (matching the overwrite semantics of a dense matrix of cells)
69    fn paint(&mut self, range: Range<i16>, state: CellOccupancyState) {
70        if range.start >= range.end {
71            return;
72        }
73
74        // Fast path: the painted range lies entirely after all existing intervals
75        // (the common case, as placement queries and inserts mostly advance forwards)
76        match self.intervals.last_mut() {
77            None => {
78                self.intervals.push(OccupiedInterval { range, state });
79                return;
80            }
81            Some(last) if last.range.end <= range.start => {
82                if last.state == state && last.range.end == range.start {
83                    last.range.end = range.end;
84                } else {
85                    self.intervals.push(OccupiedInterval { range, state });
86                }
87                return;
88            }
89            _ => {}
90        }
91
92        let mut result: SmallVec<[OccupiedInterval; 2]> = SmallVec::new();
93
94        // Intervals (or partial intervals) entirely before the painted range
95        for interval in &self.intervals {
96            if interval.range.end <= range.start {
97                result.push(interval.clone());
98            } else if interval.range.start < range.start {
99                result.push(OccupiedInterval { range: interval.range.start..range.start, state: interval.state });
100            }
101        }
102
103        // The painted range, merged with the preceding interval if it touches and has the same state
104        match result.last_mut() {
105            Some(last) if last.state == state && last.range.end == range.start => last.range.end = range.end,
106            _ => result.push(OccupiedInterval { range: range.clone(), state }),
107        }
108
109        // Intervals (or partial intervals) entirely after the painted range
110        for interval in &self.intervals {
111            let trimmed = if interval.range.start >= range.end {
112                interval.clone()
113            } else if interval.range.end > range.end {
114                OccupiedInterval { range: range.end..interval.range.end, state: interval.state }
115            } else {
116                continue;
117            };
118            match result.last_mut() {
119                Some(last) if last.state == trimmed.state && last.range.end == trimmed.range.start => {
120                    last.range.end = trimmed.range.end
121                }
122                _ => result.push(trimmed),
123            }
124        }
125
126        self.intervals = result;
127    }
128
129    /// Find the extent of the occupied interval which an auto-placement search along the track
130    /// would collide with last: the end of the last overlapping interval. Returns the extremal
131    /// occupied cell of that interval (which may lie outside `range`: every search position
132    /// before the returned extent also collides with the interval), or `None` if the range is
133    /// entirely unoccupied.
134    fn collision_extent(&self, range: &Range<i16>) -> Option<i16> {
135        let interval = self
136            .intervals
137            .iter()
138            .rev()
139            .take_while(|interval| interval.range.end > range.start)
140            .find(|interval| interval.overlaps(range))?;
141        Some(interval.range.end - 1)
142    }
143}
144
145/// A dynamically sized matrix (2d grid) which tracks the occupancy of each grid cell during auto-placement.
146/// It also keeps tabs on how many tracks there are and which tracks are implicit and which are explicit.
147///
148/// Occupancy is stored sparsely as per-track interval lists (in both orientations), so memory usage
149/// is proportional to the number of placed items rather than the total number of grid cells.
150pub(crate) struct CellOccupancyMatrix {
151    /// The counts of implicit and explicit columns
152    columns: TrackCounts,
153    /// The counts of implicit and explicit rows
154    rows: TrackCounts,
155    /// For each row track: the occupied intervals within that row (in column coordinates)
156    row_intervals: Vec<TrackIntervals>,
157    /// For each column track: the occupied intervals within that column (in row coordinates)
158    column_intervals: Vec<TrackIntervals>,
159}
160
161/// Debug impl that represents the matrix in a compact 2d text format
162impl Debug for CellOccupancyMatrix {
163    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
164        writeln!(
165            f,
166            "Rows: neg_implicit={} explicit={} pos_implicit={}",
167            self.rows.negative_implicit, self.rows.explicit, self.rows.positive_implicit
168        )?;
169        writeln!(
170            f,
171            "Cols: neg_implicit={} explicit={} pos_implicit={}",
172            self.columns.negative_implicit, self.columns.explicit, self.columns.positive_implicit
173        )?;
174        if self.rows.len() > 100 || self.columns.len() > 100 {
175            writeln!(f, "State: (not printed: more than 100 tracks)")?;
176            return Ok(());
177        }
178        writeln!(f, "State:")?;
179
180        for row in &self.row_intervals {
181            for column_index in 0..self.columns.len() {
182                let coordinate = self.columns.track_to_prev_oz_line(column_index as u16);
183                let letter = match row.state_at(coordinate.0) {
184                    CellOccupancyState::Unoccupied => '_',
185                    CellOccupancyState::DefinitelyPlaced => 'D',
186                    CellOccupancyState::AutoPlaced => 'A',
187                };
188                write!(f, "{letter}")?;
189            }
190            writeln!(f)?;
191        }
192
193        Ok(())
194    }
195}
196
197impl CellOccupancyMatrix {
198    /// Create a CellOccupancyMatrix given a set of provisional track counts. The grid can expand as needed to fit more tracks,
199    /// the provisional track counts represent a best effort attempt to avoid the extra allocations this requires.
200    pub fn with_track_counts(columns: TrackCounts, rows: TrackCounts) -> Self {
201        let mut row_intervals = new_vec_with_capacity(rows.len());
202        row_intervals.resize(rows.len(), TrackIntervals::default());
203        let mut column_intervals = new_vec_with_capacity(columns.len());
204        column_intervals.resize(columns.len(), TrackIntervals::default());
205        Self { rows, columns, row_intervals, column_intervals }
206    }
207
208    /// The per-track interval lists for tracks in the specified axis. Each row track's intervals
209    /// are in column coordinates and vice versa.
210    fn track_lists(&self, track_axis: AbsoluteAxis) -> &[TrackIntervals] {
211        match track_axis {
212            AbsoluteAxis::Horizontal => &self.column_intervals,
213            AbsoluteAxis::Vertical => &self.row_intervals,
214        }
215    }
216
217    /// Expands the grid (potentially in all 4 directions) in order to ensure that the specified
218    /// spans (in OriginZero coordinates) fit within the tracked tracks
219    fn expand_to_fit_range(&mut self, row_span: Line<OriginZeroLine>, col_span: Line<OriginZeroLine>) {
220        // Calculate number of rows and columns missing to accommodate ranges (if any)
221        let req_negative_rows = max(-(self.rows.negative_implicit as i16) - row_span.start.0, 0);
222        let req_positive_rows = max(row_span.end.0 - self.rows.implicit_end_line().0, 0);
223        let req_negative_cols = max(-(self.columns.negative_implicit as i16) - col_span.start.0, 0);
224        let req_positive_cols = max(col_span.end.0 - self.columns.implicit_end_line().0, 0);
225
226        // Add empty tracks to the front and/or back of the per-track interval lists.
227        // Interval contents are stored in OriginZero coordinates, so they do not need to shift.
228        if req_negative_rows > 0 {
229            self.row_intervals
230                .splice(0..0, core::iter::repeat_with(TrackIntervals::default).take(req_negative_rows as usize));
231        }
232        if req_positive_rows > 0 {
233            let new_len = self.row_intervals.len() + req_positive_rows as usize;
234            self.row_intervals.resize(new_len, TrackIntervals::default());
235        }
236        if req_negative_cols > 0 {
237            self.column_intervals
238                .splice(0..0, core::iter::repeat_with(TrackIntervals::default).take(req_negative_cols as usize));
239        }
240        if req_positive_cols > 0 {
241            let new_len = self.column_intervals.len() + req_positive_cols as usize;
242            self.column_intervals.resize(new_len, TrackIntervals::default());
243        }
244
245        self.rows.negative_implicit += req_negative_rows as u16;
246        self.rows.positive_implicit += req_positive_rows as u16;
247        self.columns.negative_implicit += req_negative_cols as u16;
248        self.columns.positive_implicit += req_positive_cols as u16;
249    }
250
251    /// Mark an area of the matrix as occupied, expanding the allocated space as necessary to accommodate the passed area.
252    pub fn mark_area_as(
253        &mut self,
254        primary_axis: AbsoluteAxis,
255        primary_span: Line<OriginZeroLine>,
256        secondary_span: Line<OriginZeroLine>,
257        value: CellOccupancyState,
258    ) {
259        let (row_span, column_span) = match primary_axis {
260            AbsoluteAxis::Horizontal => (secondary_span, primary_span),
261            AbsoluteAxis::Vertical => (primary_span, secondary_span),
262        };
263
264        self.expand_to_fit_range(row_span, column_span);
265
266        if value == CellOccupancyState::AutoPlaced
267            && primary_span.start < primary_span.end
268            && secondary_span.start < secondary_span.end
269        {
270            self.advance_auto_placement_cursor(primary_axis, secondary_span.start, primary_span.end);
271        }
272
273        let row_range = self.rows.oz_line_range_to_track_range(row_span);
274        let col_range = self.columns.oz_line_range_to_track_range(column_span);
275        for row_index in row_range {
276            self.row_intervals[row_index as usize].paint(column_span.start.0..column_span.end.0, value);
277        }
278        for column_index in col_range {
279            self.column_intervals[column_index as usize].paint(row_span.start.0..row_span.end.0, value);
280        }
281    }
282
283    /// Determines whether a grid area specified by the bounding grid lines in OriginZero coordinates
284    /// is entirely unnocupied. Returns true if all grid cells within the grid area are unnocupied, else false.
285    #[cfg(test)]
286    pub fn line_area_is_unoccupied(
287        &self,
288        primary_axis: AbsoluteAxis,
289        primary_span: Line<OriginZeroLine>,
290        secondary_span: Line<OriginZeroLine>,
291    ) -> bool {
292        self.line_area_collision_jump(primary_axis, primary_span, secondary_span).is_none()
293    }
294
295    /// Checks the specified area for occupied cells (`primary_span` and `secondary_span` are
296    /// bounding grid lines in OriginZero coordinates). Returns `None` if the area is entirely
297    /// unoccupied. Otherwise returns the next search position (in OriginZero coordinates, along
298    /// `primary_axis`) that is not guaranteed to collide with the occupied cells found in the
299    /// area. This allows the auto-placement search cursor to jump past collisions rather than
300    /// advancing one track at a time.
301    pub fn line_area_collision_jump(
302        &self,
303        primary_axis: AbsoluteAxis,
304        primary_span: Line<OriginZeroLine>,
305        secondary_span: Line<OriginZeroLine>,
306    ) -> Option<OriginZeroLine> {
307        let track_lists = self.track_lists(primary_axis.other_axis());
308        let secondary_counts = self.track_counts(primary_axis.other_axis());
309        let secondary_range = secondary_counts.oz_line_range_to_track_range(secondary_span);
310
311        // Out of bounds cells are considered unoccupied, so clamp the secondary range to the
312        // tracks which actually exist
313        let secondary_start = max(secondary_range.start, 0);
314        let secondary_end = min(secondary_range.end, track_lists.len() as i16);
315
316        let primary_range = primary_span.start.0..primary_span.end.0;
317
318        let mut extent: Option<i16> = None;
319        for secondary_index in secondary_start..secondary_end {
320            let Some(cell) = track_lists[secondary_index as usize].collision_extent(&primary_range) else {
321                continue;
322            };
323            extent = Some(match extent {
324                None => cell,
325                Some(best) => max(best, cell),
326            });
327        }
328
329        extent.map(|cell| OriginZeroLine(cell + 1))
330    }
331
332    /// Given a span of tracks in `axis` (in OriginZero coordinates), returns the next search
333    /// position past all non-empty tracks within the span, or `None` if all tracks within the
334    /// span are entirely unoccupied. Used to place items which span every track in the other
335    /// axis (such items can only fit in a stripe of entirely unoccupied tracks).
336    pub fn occupied_track_jump(&self, axis: AbsoluteAxis, span: Line<OriginZeroLine>) -> Option<OriginZeroLine> {
337        let counts = self.track_counts(axis);
338        let track_lists = self.track_lists(axis);
339        let range = counts.oz_line_range_to_track_range(span);
340        let start = max(range.start, 0);
341        let end = min(range.end, track_lists.len() as i16);
342        let found = (start..end).rev().find(|&index| !track_lists[index as usize].is_empty());
343        found.map(|track_index| {
344            let line = counts.track_to_prev_oz_line(track_index as u16);
345            line + 1
346        })
347    }
348
349    /// Determines whether the specified row contains any items
350    pub fn row_is_occupied(&self, row_index: usize) -> bool {
351        self.track_lists(AbsoluteAxis::Vertical).get(row_index).is_some_and(|track| !track.is_empty())
352    }
353
354    /// Determines whether the specified column contains any items
355    pub fn column_is_occupied(&self, column_index: usize) -> bool {
356        self.track_lists(AbsoluteAxis::Horizontal).get(column_index).is_some_and(|track| !track.is_empty())
357    }
358
359    /// Returns the track counts of this CellOccunpancyMatrix in the relevant axis
360    pub fn track_counts(&self, track_type: AbsoluteAxis) -> &TrackCounts {
361        match track_type {
362            AbsoluteAxis::Horizontal => &self.columns,
363            AbsoluteAxis::Vertical => &self.rows,
364        }
365    }
366
367    /// The sparse placement cursor for items starting in the given secondary-axis track.
368    pub fn auto_placement_cursor(&self, track_type: AbsoluteAxis, start_at: OriginZeroLine) -> Option<OriginZeroLine> {
369        let track_counts = self.track_counts(track_type.other_axis());
370        let track_computed_index = track_counts.oz_line_to_next_track(start_at);
371        let track_lists = self.track_lists(track_type.other_axis());
372        if track_computed_index < 0 || track_computed_index >= track_lists.len() as i16 {
373            // Index out of bounds: no tracks to search
374            return None;
375        }
376        track_lists[track_computed_index as usize].auto_placement_cursor
377    }
378
379    /// Advances the sparse placement cursor to at least `primary_end`.
380    /// The secondary-axis track must already exist in the matrix.
381    fn advance_auto_placement_cursor(
382        &mut self,
383        primary_axis: AbsoluteAxis,
384        secondary_start: OriginZeroLine,
385        primary_end: OriginZeroLine,
386    ) {
387        let track_index = self.track_counts(primary_axis.other_axis()).oz_line_to_next_track(secondary_start) as usize;
388        let tracks = match primary_axis {
389            AbsoluteAxis::Horizontal => &mut self.row_intervals,
390            AbsoluteAxis::Vertical => &mut self.column_intervals,
391        };
392        let cursor = &mut tracks[track_index].auto_placement_cursor;
393        *cursor = max(*cursor, Some(primary_end));
394    }
395}
396
397#[cfg(test)]
398mod tests {
399    use super::*;
400
401    fn interval(range: Range<i16>, state: CellOccupancyState) -> OccupiedInterval {
402        OccupiedInterval { range, state }
403    }
404
405    mod track_intervals {
406        use super::*;
407        use CellOccupancyState::{AutoPlaced, DefinitelyPlaced};
408
409        #[test]
410        fn paint_merges_touching_same_state_intervals() {
411            let mut track = TrackIntervals::default();
412            track.paint(0..2, AutoPlaced);
413            track.paint(4..6, AutoPlaced);
414            track.paint(2..4, AutoPlaced);
415            assert_eq!(track.intervals.as_slice(), &[interval(0..6, AutoPlaced)]);
416        }
417
418        #[test]
419        fn paint_does_not_merge_different_states() {
420            let mut track = TrackIntervals::default();
421            track.paint(0..2, AutoPlaced);
422            track.paint(2..4, DefinitelyPlaced);
423            assert_eq!(track.intervals.as_slice(), &[interval(0..2, AutoPlaced), interval(2..4, DefinitelyPlaced)]);
424        }
425
426        #[test]
427        fn paint_overwrites_overlapped_cells() {
428            let mut track = TrackIntervals::default();
429            track.paint(0..6, AutoPlaced);
430            track.paint(2..4, DefinitelyPlaced);
431            assert_eq!(
432                track.intervals.as_slice(),
433                &[interval(0..2, AutoPlaced), interval(2..4, DefinitelyPlaced), interval(4..6, AutoPlaced)]
434            );
435
436            // Painting over everything replaces all intervals
437            track.paint(-1..7, AutoPlaced);
438            assert_eq!(track.intervals.as_slice(), &[interval(-1..7, AutoPlaced)]);
439        }
440
441        #[test]
442        fn paint_overwrites_multiple_intervals() {
443            let mut track = TrackIntervals::default();
444            track.paint(0..2, AutoPlaced);
445            track.paint(3..5, DefinitelyPlaced);
446            track.paint(6..8, AutoPlaced);
447            track.paint(1..7, DefinitelyPlaced);
448            assert_eq!(
449                track.intervals.as_slice(),
450                &[interval(0..1, AutoPlaced), interval(1..7, DefinitelyPlaced), interval(7..8, AutoPlaced)]
451            );
452        }
453
454        #[test]
455        fn collision_extent_finds_extremal_occupied_cell() {
456            let mut track = TrackIntervals::default();
457            track.paint(2..4, AutoPlaced);
458            track.paint(6..8, DefinitelyPlaced);
459            // The last cell of the last overlapping interval
460            assert_eq!(track.collision_extent(&(0..10)), Some(7));
461            assert_eq!(track.collision_extent(&(0..7)), Some(7));
462            assert_eq!(track.collision_extent(&(0..6)), Some(3));
463            assert_eq!(track.collision_extent(&(4..6)), None);
464        }
465
466        #[test]
467        fn state_at_distinguishes_occupied_intervals_and_gaps() {
468            let mut track = TrackIntervals::default();
469            track.paint(0..2, DefinitelyPlaced);
470            track.paint(2..4, AutoPlaced);
471            track.paint(6..8, AutoPlaced);
472            track.paint(8..9, DefinitelyPlaced);
473            assert_eq!(track.state_at(0), DefinitelyPlaced);
474            assert_eq!(track.state_at(3), AutoPlaced);
475            assert_eq!(track.state_at(5), CellOccupancyState::Unoccupied);
476            assert_eq!(track.state_at(7), AutoPlaced);
477            assert_eq!(track.state_at(8), DefinitelyPlaced);
478        }
479
480        #[test]
481        fn definitely_placed_overwrite_hides_auto_placed_cells() {
482            let mut track = TrackIntervals::default();
483            track.paint(0..4, CellOccupancyState::AutoPlaced);
484            track.paint(2..4, CellOccupancyState::DefinitelyPlaced);
485            assert_eq!(track.state_at(1), CellOccupancyState::AutoPlaced);
486            assert_eq!(track.state_at(2), CellOccupancyState::DefinitelyPlaced);
487            assert_eq!(track.state_at(3), CellOccupancyState::DefinitelyPlaced);
488        }
489    }
490
491    mod cell_occupancy_matrix {
492        use super::*;
493        use crate::geometry::AbsoluteAxis::{Horizontal, Vertical};
494        use CellOccupancyState::AutoPlaced;
495
496        fn line(start: i16, end: i16) -> Line<OriginZeroLine> {
497            Line { start: OriginZeroLine(start), end: OriginZeroLine(end) }
498        }
499
500        #[test]
501        fn negative_expansion_preserves_occupancy() {
502            let mut matrix =
503                CellOccupancyMatrix::with_track_counts(TrackCounts::from_raw(0, 2, 0), TrackCounts::from_raw(0, 2, 0));
504            matrix.mark_area_as(Horizontal, line(0, 1), line(0, 1), AutoPlaced);
505            // Expand by marking an area in negative tracks
506            matrix.mark_area_as(Horizontal, line(-2, -1), line(-1, 0), AutoPlaced);
507
508            assert_eq!(*matrix.track_counts(Horizontal), TrackCounts::from_raw(2, 2, 0));
509            assert_eq!(*matrix.track_counts(Vertical), TrackCounts::from_raw(1, 2, 0));
510
511            // Original cell still occupied at the same OriginZero coordinates
512            assert!(!matrix.line_area_is_unoccupied(Horizontal, line(0, 1), line(0, 1)));
513            assert!(!matrix.line_area_is_unoccupied(Horizontal, line(-2, -1), line(-1, 0)));
514            assert!(matrix.line_area_is_unoccupied(Horizontal, line(-1, 0), line(0, 1)));
515
516            // Matrix-index based queries account for the shifted origin
517            assert!(matrix.column_is_occupied(0)); // OriginZero column -2
518            assert!(!matrix.column_is_occupied(1)); // OriginZero column -1
519            assert!(matrix.column_is_occupied(2)); // OriginZero column 0
520            assert!(matrix.row_is_occupied(0)); // OriginZero row -1
521            assert!(matrix.row_is_occupied(1)); // OriginZero row 0
522            assert!(!matrix.row_is_occupied(2)); // OriginZero row 1
523        }
524
525        #[test]
526        fn auto_placed_item_only_advances_cursor_in_first_secondary_track() {
527            for axis in [Horizontal, Vertical] {
528                let mut matrix = CellOccupancyMatrix::with_track_counts(
529                    TrackCounts::from_raw(0, 4, 0),
530                    TrackCounts::from_raw(0, 4, 0),
531                );
532                matrix.mark_area_as(axis, line(1, 3), line(1, 4), AutoPlaced);
533
534                assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(1)), Some(OriginZeroLine(3)));
535                assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(2)), None);
536                assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(3)), None);
537
538                assert!(!matrix.line_area_is_unoccupied(axis, line(1, 3), line(2, 4)));
539            }
540        }
541
542        #[test]
543        fn cursors_survive_interval_merging_and_grid_expansion() {
544            for axis in [Horizontal, Vertical] {
545                let mut matrix = CellOccupancyMatrix::with_track_counts(
546                    TrackCounts::from_raw(0, 4, 0),
547                    TrackCounts::from_raw(0, 4, 0),
548                );
549                matrix.mark_area_as(axis, line(2, 4), line(1, 2), AutoPlaced);
550                matrix.mark_area_as(axis, line(4, 8), line(0, 2), AutoPlaced);
551                matrix.mark_area_as(axis, line(8, 10), line(1, 2), CellOccupancyState::DefinitelyPlaced);
552                matrix.mark_area_as(axis, line(-3, -1), line(-2, -1), AutoPlaced);
553                matrix.mark_area_as(axis, line(12, 14), line(7, 8), AutoPlaced);
554                matrix.mark_area_as(axis, line(0, 1), line(1, 2), AutoPlaced);
555
556                assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(1)), Some(OriginZeroLine(4)));
557                assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(0)), Some(OriginZeroLine(8)));
558                assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(-2)), Some(OriginZeroLine(-1)));
559                assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(7)), Some(OriginZeroLine(14)));
560                for track in [-3, -1, 2, 8] {
561                    assert_eq!(matrix.auto_placement_cursor(axis, OriginZeroLine(track)), None);
562                }
563            }
564        }
565
566        #[test]
567        fn alternating_spans_merge_occupancy_and_skip_the_occupied_prefix() {
568            for axis in [Horizontal, Vertical] {
569                let mut matrix = CellOccupancyMatrix::with_track_counts(
570                    TrackCounts::from_raw(0, 0, 0),
571                    TrackCounts::from_raw(0, 0, 0),
572                );
573                for i in 0..128 {
574                    matrix.mark_area_as(axis, line(i, i + 1), line(i % 2, 2), AutoPlaced);
575                }
576
577                let track = &matrix.track_lists(axis.other_axis())[1];
578                assert_eq!(track.intervals.as_slice(), &[interval(0..128, AutoPlaced)]);
579                assert!(!track.intervals.spilled());
580                assert_eq!(matrix.line_area_collision_jump(axis, line(0, 1), line(1, 2)), Some(OriginZeroLine(128)));
581            }
582        }
583
584        #[test]
585        fn collision_jump_returns_next_search_position() {
586            let mut matrix =
587                CellOccupancyMatrix::with_track_counts(TrackCounts::from_raw(0, 4, 0), TrackCounts::from_raw(0, 4, 0));
588            matrix.mark_area_as(Horizontal, line(1, 3), line(0, 1), AutoPlaced);
589
590            // Jump past the end of the last colliding interval
591            assert_eq!(matrix.line_area_collision_jump(Horizontal, line(0, 2), line(0, 1)), Some(OriginZeroLine(3)));
592            assert_eq!(matrix.line_area_collision_jump(Horizontal, line(0, 4), line(0, 1)), Some(OriginZeroLine(3)));
593            // No collision in a different row
594            assert_eq!(matrix.line_area_collision_jump(Horizontal, line(0, 4), line(1, 2)), None);
595        }
596
597        #[test]
598        fn occupied_track_jump_skips_non_empty_tracks() {
599            let mut matrix =
600                CellOccupancyMatrix::with_track_counts(TrackCounts::from_raw(0, 4, 0), TrackCounts::from_raw(0, 4, 0));
601            matrix.mark_area_as(Horizontal, line(0, 1), line(1, 2), AutoPlaced);
602
603            // Vertical (row) tracks: row 1 is occupied
604            assert_eq!(matrix.occupied_track_jump(Vertical, line(0, 4)), Some(OriginZeroLine(2)));
605            assert_eq!(matrix.occupied_track_jump(Vertical, line(2, 4)), None);
606        }
607    }
608}
taffy/compute/grid/types/cell_occupancy.rs

taffy/compute/grid/types/
cell_occupancy.rs
