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

taffy/compute/grid/types/
cell_occupancy.rs
