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::Vec;
7use core::cmp::max;
8use core::fmt::Debug;
9use core::ops::Range;
10use grid::Grid;
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 dynamically sized matrix (2d grid) which tracks the occupancy of each grid cell during auto-placement
25/// It also keeps tabs on how many tracks there are and which tracks are implicit and which are explicit.
26pub(crate) struct CellOccupancyMatrix {
27    /// The grid of occupancy states
28    inner: Grid<CellOccupancyState>,
29    /// The counts of implicit and explicit columns
30    columns: TrackCounts,
31    /// The counts of implicit and explicit rows
32    rows: TrackCounts,
33}
34
35/// Debug impl that represents the matrix in a compact 2d text format
36impl Debug for CellOccupancyMatrix {
37    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
38        writeln!(
39            f,
40            "Rows: neg_implicit={} explicit={} pos_implicit={}",
41            self.rows.negative_implicit, self.rows.explicit, self.rows.positive_implicit
42        )?;
43        writeln!(
44            f,
45            "Cols: neg_implicit={} explicit={} pos_implicit={}",
46            self.columns.negative_implicit, self.columns.explicit, self.columns.positive_implicit
47        )?;
48        writeln!(f, "State:")?;
49
50        for row_idx in 0..self.inner.rows() {
51            for cell in self.inner.iter_row(row_idx) {
52                let letter = match *cell {
53                    CellOccupancyState::Unoccupied => '_',
54                    CellOccupancyState::DefinitelyPlaced => 'D',
55                    CellOccupancyState::AutoPlaced => 'A',
56                };
57                write!(f, "{letter}")?;
58            }
59            writeln!(f)?;
60        }
61
62        Ok(())
63    }
64}
65
66impl CellOccupancyMatrix {
67    /// Create a CellOccupancyMatrix given a set of provisional track counts. The grid can expand as needed to fit more tracks,
68    /// the provisional track counts represent a best effort attempt to avoid the extra allocations this requires.
69    pub fn with_track_counts(columns: TrackCounts, rows: TrackCounts) -> Self {
70        Self { inner: Grid::new(rows.len(), columns.len()), rows, columns }
71    }
72
73    /// Determines whether the specified area fits within the tracks currently represented by the matrix
74    pub fn is_area_in_range(
75        &self,
76        primary_axis: AbsoluteAxis,
77        primary_range: Range<i16>,
78        secondary_range: Range<i16>,
79    ) -> bool {
80        if primary_range.start < 0 || primary_range.end > self.track_counts(primary_axis).len() as i16 {
81            return false;
82        }
83        if secondary_range.start < 0 || secondary_range.end > self.track_counts(primary_axis.other_axis()).len() as i16
84        {
85            return false;
86        }
87        true
88    }
89
90    /// Expands the grid (potentially in all 4 directions) in order to ensure that the specified range fits within the allocated space
91    fn expand_to_fit_range(&mut self, row_range: Range<i16>, col_range: Range<i16>) {
92        // Calculate number of rows and columns missing to accommodate ranges (if any)
93        let req_negative_rows = max(-row_range.start, 0);
94        let req_positive_rows = max(row_range.end - self.rows.len() as i16, 0);
95        let req_negative_cols = max(-col_range.start, 0);
96        let req_positive_cols = max(col_range.end - self.columns.len() as i16, 0);
97
98        let old_row_count = self.rows.len();
99        let old_col_count = self.columns.len();
100        let new_row_count = old_row_count + (req_negative_rows + req_positive_rows) as usize;
101        let new_col_count = old_col_count + (req_negative_cols + req_positive_cols) as usize;
102
103        let mut data = Vec::with_capacity(new_row_count * new_col_count);
104
105        // Push new negative rows
106        for _ in 0..(req_negative_rows as usize * new_col_count) {
107            data.push(CellOccupancyState::Unoccupied);
108        }
109
110        // Push existing rows
111        for row in 0..old_row_count {
112            // Push new negative columns
113            for _ in 0..req_negative_cols {
114                data.push(CellOccupancyState::Unoccupied);
115            }
116            // Push existing columns
117            for col in 0..old_col_count {
118                data.push(*self.inner.get(row, col).unwrap());
119            }
120            // Push new positive columns
121            for _ in 0..req_positive_cols {
122                data.push(CellOccupancyState::Unoccupied);
123            }
124        }
125
126        // Push new negative rows
127        for _ in 0..(req_positive_rows as usize * new_col_count) {
128            data.push(CellOccupancyState::Unoccupied);
129        }
130
131        // Update self with new data
132        self.inner = Grid::from_vec(data, new_col_count);
133        self.rows.negative_implicit += req_negative_rows as u16;
134        self.rows.positive_implicit += req_positive_rows as u16;
135        self.columns.negative_implicit += req_negative_cols as u16;
136        self.columns.positive_implicit += req_positive_cols as u16;
137    }
138
139    /// Mark an area of the matrix as occupied, expanding the allocated space as necessary to accommodate the passed area.
140    pub fn mark_area_as(
141        &mut self,
142        primary_axis: AbsoluteAxis,
143        primary_span: Line<OriginZeroLine>,
144        secondary_span: Line<OriginZeroLine>,
145        value: CellOccupancyState,
146    ) {
147        let (row_span, column_span) = match primary_axis {
148            AbsoluteAxis::Horizontal => (secondary_span, primary_span),
149            AbsoluteAxis::Vertical => (primary_span, secondary_span),
150        };
151
152        let mut col_range = self.columns.oz_line_range_to_track_range(column_span);
153        let mut row_range = self.rows.oz_line_range_to_track_range(row_span);
154
155        // Check that if the resolved ranges fit within the allocated grid. And if they don't then expand the grid to fit
156        // and then re-resolve the ranges once the grid has been expanded as the resolved indexes may have changed
157        let is_in_range = self.is_area_in_range(AbsoluteAxis::Horizontal, col_range.clone(), row_range.clone());
158        if !is_in_range {
159            self.expand_to_fit_range(row_range.clone(), col_range.clone());
160            col_range = self.columns.oz_line_range_to_track_range(column_span);
161            row_range = self.rows.oz_line_range_to_track_range(row_span);
162        }
163
164        for x in row_range {
165            for y in col_range.clone() {
166                *self.inner.get_mut(x as usize, y as usize).unwrap() = value;
167            }
168        }
169    }
170
171    /// Determines whether a grid area specified by the bounding grid lines in OriginZero coordinates
172    /// is entirely unnocupied. Returns true if all grid cells within the grid area are unnocupied, else false.
173    pub fn line_area_is_unoccupied(
174        &self,
175        primary_axis: AbsoluteAxis,
176        primary_span: Line<OriginZeroLine>,
177        secondary_span: Line<OriginZeroLine>,
178    ) -> bool {
179        let primary_range = self.track_counts(primary_axis).oz_line_range_to_track_range(primary_span);
180        let secondary_range = self.track_counts(primary_axis.other_axis()).oz_line_range_to_track_range(secondary_span);
181        self.track_area_is_unoccupied(primary_axis, primary_range, secondary_range)
182    }
183
184    /// Determines whether a grid area specified by a range of indexes into this CellOccupancyMatrix
185    /// is entirely unnocupied. Returns true if all grid cells within the grid area are unnocupied, else false.
186    pub fn track_area_is_unoccupied(
187        &self,
188        primary_axis: AbsoluteAxis,
189        primary_range: Range<i16>,
190        secondary_range: Range<i16>,
191    ) -> bool {
192        let (row_range, col_range) = match primary_axis {
193            AbsoluteAxis::Horizontal => (secondary_range, primary_range),
194            AbsoluteAxis::Vertical => (primary_range, secondary_range),
195        };
196
197        // Search for occupied cells in the specified area. Out of bounds cells are considered unoccupied.
198        for x in row_range {
199            for y in col_range.clone() {
200                match self.inner.get(x as usize, y as usize) {
201                    None | Some(CellOccupancyState::Unoccupied) => continue,
202                    _ => return false,
203                }
204            }
205        }
206
207        true
208    }
209
210    /// Determines whether the specified row contains any items
211    pub fn row_is_occupied(&self, row_index: usize) -> bool {
212        if row_index >= self.inner.rows() {
213            return false;
214        }
215        self.inner.iter_row(row_index).any(|cell| !matches!(cell, CellOccupancyState::Unoccupied))
216    }
217
218    /// Determines whether the specified column contains any items
219    pub fn column_is_occupied(&self, column_index: usize) -> bool {
220        if column_index >= self.inner.cols() {
221            return false;
222        }
223        self.inner.iter_col(column_index).any(|cell| !matches!(cell, CellOccupancyState::Unoccupied))
224    }
225
226    /// Returns the track counts of this CellOccunpancyMatrix in the relevant axis
227    pub fn track_counts(&self, track_type: AbsoluteAxis) -> &TrackCounts {
228        match track_type {
229            AbsoluteAxis::Horizontal => &self.columns,
230            AbsoluteAxis::Vertical => &self.rows,
231        }
232    }
233
234    /// Given an axis and a track index
235    /// Search backwards from the end of the track and find the last grid cell matching the specified state (if any)
236    /// Return the index of that cell or None.
237    pub fn last_of_type(
238        &self,
239        track_type: AbsoluteAxis,
240        start_at: OriginZeroLine,
241        kind: CellOccupancyState,
242    ) -> Option<OriginZeroLine> {
243        let track_counts = self.track_counts(track_type.other_axis());
244        let track_computed_index = track_counts.oz_line_to_next_track(start_at);
245
246        // Index out of boudnds: no track to search
247        if track_computed_index < 0 || track_computed_index >= self.inner.rows() as i16 {
248            return None;
249        }
250
251        let maybe_index = match track_type {
252            AbsoluteAxis::Horizontal => {
253                self.inner.iter_row(track_computed_index as usize).rposition(|item| *item == kind)
254            }
255            AbsoluteAxis::Vertical => {
256                self.inner.iter_col(track_computed_index as usize).rposition(|item| *item == kind)
257            }
258        };
259
260        maybe_index.map(|idx| track_counts.track_to_prev_oz_line(idx as u16))
261    }
262}
taffy/compute/grid/types/cell_occupancy.rs

taffy/compute/grid/types/
cell_occupancy.rs
