substrate/layout/
tiling.rs

1//! Tiling structures and helpers.
2
3use std::{any::Any, marker::PhantomData};
4
5use downcast_rs::{Downcast, impl_downcast};
6use geometry::{
7    align::AlignRectMut,
8    prelude::{AlignMode, Bbox},
9    rect::Rect,
10    side::Sides,
11    transform::TranslateMut,
12};
13use serde::{Deserialize, Serialize};
14use slotmap::{SlotMap, new_key_type};
15
16use super::{Draw, DrawReceiver, schema::Schema};
17
18/// A tileable layout object.
19pub trait Tileable<S: Schema>: Draw<S> + AlignRectMut + Downcast {}
20impl<S: Schema, T: Draw<S> + AlignRectMut + Downcast> Tileable<S> for T {}
21impl_downcast!(Tileable<S> where S: Schema);
22
23new_key_type! {
24    struct RawTileKey;
25}
26
27/// A key for indexing a [`Tile`] within an [`ArrayTiler`].
28pub struct ArrayTileKey<T> {
29    key: RawTileKey,
30    phantom: PhantomData<T>,
31}
32
33impl<T> Clone for ArrayTileKey<T> {
34    fn clone(&self) -> Self {
35        *self
36    }
37}
38
39impl<T> Copy for ArrayTileKey<T> {}
40
41/// A tile container for a [`Tileable`] object.
42#[derive(Debug, Clone, Copy)]
43pub struct Tile<T> {
44    /// The [`Tileable`] object to be tiled.
45    pub inner: T,
46    /// A rectangle used for alignment with other [`Tile`]s.
47    pub rect: Rect,
48}
49
50/// A raw tile container for a [`Tileable`] object.
51///
52/// Erases the tile type, but can be downcasted to a [`Tile`].
53pub struct RawTile<S: Schema> {
54    inner: Box<dyn Tileable<S>>,
55    rect: Rect,
56}
57
58impl<T> Tile<T> {
59    /// Creates a new [`Tile`].
60    pub fn new(inner: T, rect: Rect) -> Self {
61        Self { inner, rect }
62    }
63
64    /// Returns a new [`Tile`] with the given padding on each side.
65    pub fn with_padding(mut self, padding: Sides<i64>) -> Self {
66        self.rect = self.rect.expand_sides(padding);
67        self
68    }
69}
70
71impl<T: Bbox> Tile<T> {
72    /// Creates a new [`Tile`] from the bounding box of the provided layout object.
73    pub fn from_bbox(inner: T) -> Self {
74        let rect = inner.bbox().unwrap();
75        Self { inner, rect }
76    }
77}
78
79impl<S: Schema, T: Tileable<S>> From<Tile<T>> for RawTile<S> {
80    fn from(value: Tile<T>) -> Self {
81        Self {
82            inner: Box::new(value.inner),
83            rect: value.rect,
84        }
85    }
86}
87
88impl<S: Schema + Any> RawTile<S> {
89    /// Returns a [`Tile`] from a [`RawTile`] if the inner type is `T`. Returns the original [`RawTile`] if it isn’t.
90    pub fn downcast<T: Tileable<S>>(self) -> Result<Tile<T>, RawTile<S>> {
91        self.inner
92            .downcast()
93            .map(|inner| Tile {
94                inner: *inner,
95                rect: self.rect,
96            })
97            .map_err(|inner| RawTile {
98                inner,
99                rect: self.rect,
100            })
101    }
102
103    /// Returns a reference to the inner object if it is of type T, or None if it isn’t.
104    pub fn downcast_inner_ref<T: Tileable<S>>(&self) -> Option<&T> {
105        self.inner.downcast_ref()
106    }
107
108    /// Returns a mutable reference to the inner object if it is of type T, or None if it isn’t.
109    pub fn downcast_inner_mut<T: Tileable<S>>(&mut self) -> Option<&mut T> {
110        self.inner.downcast_mut()
111    }
112}
113
114impl<S: Schema> TranslateMut for RawTile<S> {
115    fn translate_mut(&mut self, p: geometry::prelude::Point) {
116        self.inner.translate_mut(p);
117        self.rect.translate_mut(p);
118    }
119}
120
121impl<S: Schema> Draw<S> for RawTile<S> {
122    fn draw(self, recv: &mut DrawReceiver<S>) -> crate::error::Result<()> {
123        self.inner.draw(recv)
124    }
125}
126
127/// An enumeration of alignment modes for adjacent tiles in a tiler along a given axis.
128#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
129pub enum TileAlignMode {
130    /// Aligns the positive edge of the next tile to the positive edge of the previous tile.
131    PosFlush,
132    /// Aligns the negative edge of the next tile to the positive edge of the previous tile.
133    PosAdjacent,
134    /// Aligns the negative edge of the next tile to the negative edge of the previous tile.
135    NegFlush,
136    /// Aligns the positive edge of the next tile to the negative edge of the previous tile.
137    NegAdjacent,
138    /// Aligns the centers of the two tiles along the given axis.
139    Center,
140}
141
142/// An array tiler.
143pub struct ArrayTiler<S: Schema> {
144    config: ArrayTilerConfig,
145    tiles: SlotMap<RawTileKey, RawTile<S>>,
146    array: Vec<RawTileKey>,
147}
148
149#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
150struct ArrayTilerConfig {
151    horiz_mode: TileAlignMode,
152    vert_mode: TileAlignMode,
153}
154
155impl<S: Schema + 'static, T: Tileable<S>> std::ops::Index<ArrayTileKey<T>> for ArrayTiler<S> {
156    type Output = T;
157
158    fn index(&self, index: ArrayTileKey<T>) -> &Self::Output {
159        self.get(index).unwrap()
160    }
161}
162
163impl<S: Schema> TranslateMut for ArrayTiler<S> {
164    fn translate_mut(&mut self, p: geometry::prelude::Point) {
165        for tile in &self.array {
166            self.tiles[*tile].translate_mut(p);
167        }
168    }
169}
170
171impl<S: Schema> Draw<S> for ArrayTiler<S> {
172    fn draw(mut self, cell: &mut DrawReceiver<S>) -> crate::error::Result<()> {
173        for key in self.array {
174            self.tiles.remove(key).unwrap().draw(cell)?;
175        }
176        Ok(())
177    }
178}
179
180impl<S: Schema> ArrayTiler<S> {
181    /// Creates an [`ArrayTiler`].
182    ///
183    /// `horiz_mode` and `vert_mode` specify how to align tiles in the horizontal and vertical
184    /// directions, respectively.
185    pub fn new(horiz_mode: TileAlignMode, vert_mode: TileAlignMode) -> Self {
186        Self {
187            config: ArrayTilerConfig {
188                horiz_mode,
189                vert_mode,
190            },
191            tiles: SlotMap::with_key(),
192            array: Vec::new(),
193        }
194    }
195
196    /// Pushes a new tile to the tiler, returning a key for accessing the tiled object.
197    pub fn push<T: Tileable<S>>(&mut self, tile: Tile<T>) -> ArrayTileKey<T> {
198        let mut raw_tile: RawTile<_> = tile.into();
199        if let Some(key) = self.array.last() {
200            let srect = raw_tile.rect;
201            ArrayTiler::align_with_prev(&mut raw_tile, &self.config, srect, self.tiles[*key].rect);
202        }
203        let key = self.tiles.insert(raw_tile);
204        self.array.push(key);
205        ArrayTileKey {
206            key,
207            phantom: PhantomData,
208        }
209    }
210
211    /// Pushes a `num` repetitions of a the given tile to the tiler, returning a set of keys to the
212    /// new tiled objects.
213    pub fn push_num<T: Tileable<S> + Clone>(
214        &mut self,
215        tile: Tile<T>,
216        num: usize,
217    ) -> Vec<ArrayTileKey<T>> {
218        (0..num).map(|_| self.push(tile.clone())).collect()
219    }
220
221    /// Pushes each tile in the provided iterator to the tiler, returning an iterator of keys to the new
222    /// tiled objects.
223    pub fn push_iter<'a, T: Tileable<S>>(
224        &'a mut self,
225        tiles: impl Iterator<Item = Tile<T>> + 'a,
226    ) -> impl Iterator<Item = ArrayTileKey<T>> + 'a {
227        tiles.into_iter().map(|tile| self.push(tile))
228    }
229
230    fn align_with_prev(tile: &mut RawTile<S>, config: &ArrayTilerConfig, srect: Rect, orect: Rect) {
231        tile.align_mut(
232            match config.horiz_mode {
233                TileAlignMode::PosFlush => AlignMode::Right,
234                TileAlignMode::PosAdjacent => AlignMode::ToTheRight,
235                TileAlignMode::Center => AlignMode::CenterHorizontal,
236                TileAlignMode::NegFlush => AlignMode::Left,
237                TileAlignMode::NegAdjacent => AlignMode::ToTheLeft,
238            },
239            srect,
240            orect,
241            0,
242        );
243        tile.align_mut(
244            match config.vert_mode {
245                TileAlignMode::PosFlush => AlignMode::Top,
246                TileAlignMode::PosAdjacent => AlignMode::Above,
247                TileAlignMode::Center => AlignMode::CenterVertical,
248                TileAlignMode::NegFlush => AlignMode::Bottom,
249                TileAlignMode::NegAdjacent => AlignMode::Beneath,
250            },
251            srect,
252            orect,
253            0,
254        );
255    }
256}
257impl<S: Schema + 'static> ArrayTiler<S> {
258    /// Gets a tiled object using its [`ArrayTileKey`].
259    pub fn get<T: Tileable<S>>(&self, key: ArrayTileKey<T>) -> Option<&T> {
260        self.tiles
261            .get(key.key)
262            .and_then(|raw| raw.inner.as_ref().downcast_ref())
263    }
264}
265
266/// A key for indexing a [`GridTile`] within an [`GridTiler`].
267pub struct GridTileKey<T> {
268    key: RawTileKey,
269    phantom: PhantomData<T>,
270}
271
272impl<T> Clone for GridTileKey<T> {
273    fn clone(&self) -> Self {
274        *self
275    }
276}
277
278impl<T> Copy for GridTileKey<T> {}
279
280/// A tile within a [`GridTiler`].
281#[derive(Debug, Clone, Copy)]
282pub struct GridTile<T> {
283    tile: Option<Tile<T>>,
284    colspan: usize,
285    rowspan: usize,
286}
287
288struct RawGridTile<S: Schema> {
289    raw: Option<RawTile<S>>,
290    colspan: usize,
291    rowspan: usize,
292}
293
294impl<T> GridTile<T> {
295    /// Creates a new [`GridTile`].
296    pub fn new(tile: Tile<T>) -> Self {
297        Self {
298            tile: Some(tile),
299            colspan: 1,
300            rowspan: 1,
301        }
302    }
303
304    /// Creates a new empty [`GridTile`].
305    pub fn empty() -> Self {
306        Self {
307            tile: None,
308            colspan: 1,
309            rowspan: 1,
310        }
311    }
312
313    /// Returns a new [`GridTile`] with the given column span.
314    pub fn with_colspan(mut self, colspan: usize) -> Self {
315        self.colspan = colspan;
316        self
317    }
318
319    /// Returns a new [`GridTile`] with the row span.
320    pub fn with_rowspan(mut self, rowspan: usize) -> Self {
321        self.rowspan = rowspan;
322        self
323    }
324}
325
326impl<T> From<Tile<T>> for GridTile<T> {
327    fn from(value: Tile<T>) -> Self {
328        Self::new(value)
329    }
330}
331
332impl<S: Schema, T: Tileable<S>> From<GridTile<T>> for RawGridTile<S> {
333    fn from(value: GridTile<T>) -> Self {
334        Self {
335            raw: value.tile.map(|x| x.into()),
336            colspan: value.colspan,
337            rowspan: value.rowspan,
338        }
339    }
340}
341
342/// A grid tiler.
343pub struct GridTiler<S: Schema> {
344    #[allow(dead_code)]
345    config: GridTilerConfig,
346    tiles: SlotMap<RawTileKey, RawGridTile<S>>,
347    grid: Vec<Vec<RawTileKey>>,
348}
349
350impl<S: Schema> Default for GridTiler<S> {
351    fn default() -> Self {
352        Self {
353            config: GridTilerConfig {},
354            tiles: SlotMap::with_key(),
355            grid: vec![vec![]],
356        }
357    }
358}
359
360#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
361struct GridTilerConfig {}
362
363/// A constraint on a grid row or column.
364#[derive(Debug, Clone, Copy)]
365struct GridConstraint {
366    /// The constraining row/column index.
367    start_index: usize,
368    /// The constrained row/column index.
369    end_index: usize,
370    /// The required minimum distance between the rows/columns.
371    distance: i64,
372}
373
374#[derive(Debug, Clone, Default)]
375struct GridConstraintSolver {
376    constraints: Vec<GridConstraint>,
377}
378
379impl GridConstraint {
380    fn new(start_index: usize, end_index: usize, distance: i64) -> Self {
381        assert!(start_index < end_index);
382        assert!(distance > 0);
383        Self {
384            start_index,
385            end_index,
386            distance,
387        }
388    }
389}
390
391impl GridConstraintSolver {
392    fn new() -> Self {
393        Self::default()
394    }
395
396    fn add(&mut self, constraint: GridConstraint) {
397        self.constraints.push(constraint);
398    }
399
400    fn solve(mut self) -> Vec<i64> {
401        self.constraints
402            .sort_by_key(|constraint| constraint.end_index);
403        let mut grids = vec![0];
404
405        for constraint in self.constraints {
406            if constraint.end_index >= grids.len() {
407                grids.resize(constraint.end_index + 1, 0);
408            }
409            grids[constraint.end_index] = std::cmp::max(
410                grids[constraint.end_index],
411                grids[constraint.start_index] + constraint.distance,
412            );
413        }
414
415        grids
416    }
417}
418
419/// An immutable tiled grid created by a [`GridTiler`].
420pub struct TiledGrid<S: Schema> {
421    tiles: SlotMap<RawTileKey, RawGridTile<S>>,
422}
423
424impl<S: Schema> GridTiler<S> {
425    /// Creates a [`GridTiler`].
426    ///
427    /// Populated from left-to-right and top-to-bottom.
428    pub fn new() -> Self {
429        Self::default()
430    }
431
432    /// Pushes a new tile to the tiler, returning a key for accessing the tiled object.
433    pub fn push<T: Tileable<S>>(&mut self, tile: impl Into<GridTile<T>>) -> GridTileKey<T> {
434        let raw_tile: RawGridTile<_> = tile.into().into();
435        let key = self.tiles.insert(raw_tile);
436        self.last_row_mut().push(key);
437        GridTileKey {
438            key,
439            phantom: PhantomData,
440        }
441    }
442
443    /// Pushes a `num` repetitions of a the given tile to the tiler, returning a set of keys to the
444    /// new tiled objects.
445    pub fn push_num<T: Tileable<S> + Clone>(
446        &mut self,
447        tile: impl Into<GridTile<T>>,
448        num: usize,
449    ) -> Vec<GridTileKey<T>> {
450        let tile = tile.into();
451        (0..num).map(|_| self.push(tile.clone())).collect()
452    }
453
454    /// Pushes each tile in the provided iterator to the tiler, returning an iterator of keys to the new
455    /// tiled objects.
456    pub fn push_iter<'a, T: Tileable<S>>(
457        &'a mut self,
458        tiles: impl Iterator<Item = impl Into<GridTile<T>>> + 'a,
459    ) -> impl Iterator<Item = GridTileKey<T>> + 'a {
460        tiles.into_iter().map(|tile| self.push(tile))
461    }
462
463    fn last_row_mut(&mut self) -> &mut Vec<RawTileKey> {
464        self.grid.last_mut().unwrap()
465    }
466
467    /// Ends a row of the tiler, starting a new one.
468    pub fn end_row(&mut self) {
469        self.grid.push(Vec::new());
470    }
471
472    /// Calculate the row and column indices of each tile, with the necessary shifts applied.
473    fn calculate_indices(&self) -> Vec<(usize, usize, RawTileKey)> {
474        struct ColBlockage {
475            start_col: usize,
476            /// Exclusive
477            end_col: usize,
478            /// Exclusive
479            end_row: usize,
480        }
481
482        let mut blockages: Vec<ColBlockage> = Vec::new();
483        let mut indices = Vec::new();
484
485        for (i, row) in self.grid.iter().enumerate() {
486            let mut blockage_idx = 0;
487            let mut col_idx = 0;
488            for key in row {
489                if let Some(blockage) = blockages.get(blockage_idx)
490                    && col_idx == blockage.start_col
491                {
492                    if i == blockage.end_row {
493                        blockages.remove(blockage_idx);
494                    } else {
495                        col_idx = blockage.end_col;
496                        blockage_idx += 1;
497                    }
498                }
499                let tile = &self.tiles[*key];
500                if tile.rowspan > 1 {
501                    blockages.push(ColBlockage {
502                        start_col: col_idx,
503                        end_col: col_idx + tile.colspan,
504                        end_row: i + tile.rowspan,
505                    });
506                }
507                indices.push((i, col_idx, *key));
508                col_idx += tile.colspan;
509            }
510        }
511
512        indices
513    }
514
515    /// Aligns the inserted tiles in a [`TiledGrid`].
516    pub fn tile(mut self) -> TiledGrid<S> {
517        let mut row_constraints = GridConstraintSolver::new();
518        let mut col_constraints = GridConstraintSolver::new();
519
520        let indices = self.calculate_indices();
521
522        for (i, j, key) in indices.iter().cloned() {
523            let tile = &self.tiles[key];
524
525            if let Some(raw) = &tile.raw {
526                row_constraints.add(GridConstraint::new(i, i + tile.rowspan, raw.rect.height()));
527                col_constraints.add(GridConstraint::new(j, j + tile.colspan, raw.rect.width()));
528            }
529        }
530
531        let row_grid = row_constraints.solve();
532        let col_grid = col_constraints.solve();
533
534        for (i, j, key) in indices.iter().cloned() {
535            let tile = &mut self.tiles[key];
536
537            if let Some(raw) = &mut tile.raw {
538                let align_rect = Rect::from_sides(
539                    col_grid[j],
540                    -row_grid[i + tile.rowspan],
541                    col_grid[j + tile.colspan],
542                    -row_grid[i],
543                );
544
545                raw.align_mut(AlignMode::Top, raw.rect, align_rect, 0);
546                raw.align_mut(AlignMode::Left, raw.rect, align_rect, 0);
547            }
548        }
549
550        TiledGrid { tiles: self.tiles }
551    }
552}
553
554impl<S: Schema + 'static, T: Tileable<S>> std::ops::Index<GridTileKey<T>> for TiledGrid<S> {
555    type Output = T;
556
557    fn index(&self, index: GridTileKey<T>) -> &Self::Output {
558        self.get(index).unwrap()
559    }
560}
561
562impl<S: Schema + 'static> TiledGrid<S> {
563    /// Gets a tiled object using its [`GridTileKey`].
564    pub fn get<T: Tileable<S>>(&self, key: GridTileKey<T>) -> Option<&T> {
565        self.tiles
566            .get(key.key)
567            .and_then(|raw| raw.raw.as_ref())
568            .and_then(|raw| raw.inner.as_ref().downcast_ref())
569    }
570}
571
572impl<S: Schema> Draw<S> for TiledGrid<S> {
573    fn draw(self, cell: &mut DrawReceiver<S>) -> crate::error::Result<()> {
574        for (_, tile) in self.tiles {
575            if let Some(raw) = tile.raw {
576                raw.draw(cell)?;
577            }
578        }
579        Ok(())
580    }
581}
substrate/layout/tiling.rs

substrate/layout/
tiling.rs
