map_tile_toolkit/

slicer.rs

//! The public slicing API: [`SlicerAll`] (every tile a polyline touches) and [`SlicerOne`] (one fixed
//! tile), both over the stateless [`Grid`] engine.
//!
//! Each polyline added with [`add_feature`](SlicerAll::add_feature) (or
//! [`add_feature_with`](SlicerAll::add_feature_with), to attach a **per-feature** attribute) is an
//! independent **feature**, sliced and recorded per tile; one polyline can yield several runs in a
//! tile (it left and re-entered), which stay grouped as that tile's feature. Read back with borrowed
//! iterators: [`SlicerAll::iter_tiles`] → [`TileView::iter_features`] → [`FeatureView::iter_polylines`]
//! (and [`FeatureView::attr`] for the attribute), or [`SlicerOne::iter_features`] directly. Runs are
//! in each tile's local frame (origin at the tile's `[0, 0]` corner, so in-tile vertices land in
//! `0..extent`); [`merge`](crate::merge) is the inverse.
//!
//! Attributes are a second, optional generic axis (`A`, default `()`): orthogonal to the per-vertex
//! [`Vertex`] payload, stored once per feature-piece, and — because `A = ()` is zero-sized — free
//! unless used. A feature split across tiles carries a clone of its attribute into each.
//!
//! Storage: each tile is a flattened [`TileBuf`] — one `verts` arena with `u32` run/feature boundary
//! offsets, not nested `Vec`s. [`SlicerAll`] holds `Vec<TileBuf>` (stable slots) plus a `BTreeMap`
//! from [`TileId`] to slot for find-or-insert and ordered reads; [`SlicerOne`] holds one `TileBuf`.

use std::collections::BTreeMap;

use geo_types::Coord;

use crate::TileError;
use crate::clip_polyline::to_local;
use crate::grid::{Grid, RouteSink};
use crate::tile::TileId;
use crate::vertex::Vertex;

/// One tile's accumulated geometry, flattened into a single vertex arena with `u32` boundary offsets
/// instead of nested `Vec`s. Only non-empty features are recorded.
/// V is the vertex type that must implement [Vertex] trait, defaults to `Coord<i32>`
/// A is the attribute type that must be clonable, defaults to `()`
#[derive(Debug, Clone, PartialEq, Eq)]
struct TileBuf<V, A> {
    /// The tile this buffer holds.
    tile: TileId,
    /// Every run's vertices concatenated, in the tile's local frame.
    verts: Vec<V>,
    /// End offset into `verts` per run: run `r` is `verts[run_ends[r-1]..run_ends[r]]` (`run_ends[-1] ≡ 0`).
    run_ends: Vec<u32>,
    /// End offset into `run_ends` per feature: feature `f` owns runs `run_ends[feat_ends[f-1]..feat_ends[f]]`, ≥1 each.
    feat_ends: Vec<u32>,
    /// Per-feature attribute, parallel to `feat_ends`. `A = ()` never allocates, so the channel is free unless used.
    feat_attrs: Vec<A>,
    /// [`SlicerAll`] step this tile was last written at — vs. the current step (run continuity) and the
    /// feature start (new feature vs. re-entry). Unused by [`SlicerOne`].
    open_step: u64,
}

impl<V, A> TileBuf<V, A> {
    fn new(tile: TileId) -> Self {
        Self {
            tile,
            verts: Vec::new(),
            run_ends: Vec::new(),
            feat_ends: Vec::new(),
            feat_attrs: Vec::new(),
            open_step: 0,
        }
    }

    /// Append one run's vertices to the arena and record its end offset.
    #[expect(
        clippy::cast_possible_truncation,
        reason = "a tile holds far fewer than u32::MAX vertices (a polyline is capped at u16 each)"
    )]
    fn push_run(&mut self, run: Vec<V>) {
        self.verts.extend(run);
        self.run_ends.push(self.verts.len() as u32);
    }

    /// Record non-empty `runs` as one new feature carrying `attr` in this tile (each added polyline
    /// is independent).
    #[expect(
        clippy::cast_possible_truncation,
        reason = "run count per tile stays far below u32::MAX"
    )]
    fn absorb(&mut self, runs: Vec<Vec<V>>, attr: A) {
        debug_assert!(!runs.is_empty(), "empty features are never recorded");
        for run in runs {
            self.push_run(run);
        }
        self.feat_ends.push(self.run_ends.len() as u32);
        self.feat_attrs.push(attr);
    }
}

/// Iterate a tile's features from its flat offset arrays, reconstructing each as a [`FeatureView`].
fn features_of<V: Vertex, A>(
    buf: &TileBuf<V, A>,
) -> impl Iterator<Item = FeatureView<'_, V, A>> + use<'_, V, A> {
    let verts = buf.verts.as_slice();
    let run_ends = buf.run_ends.as_slice();
    let feat_ends = buf.feat_ends.as_slice();
    let feat_attrs = buf.feat_attrs.as_slice();
    (0..feat_ends.len()).map(move |f| {
        let rs = if f == 0 { 0 } else { feat_ends[f - 1] as usize };
        let re = feat_ends[f] as usize;
        // Vertex offset where this feature's first run begins (end of the previous feature's run).
        let start = if rs == 0 { 0 } else { run_ends[rs - 1] };
        FeatureView {
            verts,
            start,
            run_ends: &run_ends[rs..re],
            attr: &feat_attrs[f],
        }
    })
}

/// A borrowed view of one tile's accumulated features, yielded by [`SlicerAll::iter_tiles`].
pub struct TileView<'a, V: Vertex, A = ()> {
    buf: &'a TileBuf<V, A>,
}

impl<'a, V: Vertex, A> TileView<'a, V, A> {
    /// The tile this view is for.
    #[must_use]
    pub fn tile_id(&self) -> TileId {
        self.buf.tile
    }

    /// Iterate this tile's features, in the order they were first added.
    pub fn iter_features(&self) -> impl Iterator<Item = FeatureView<'a, V, A>> + use<'a, V, A> {
        features_of(self.buf)
    }
}

/// A borrowed view of one feature's clipped polylines within a tile, yielded by
/// [`TileView::iter_features`] / [`SlicerOne::iter_features`].
pub struct FeatureView<'a, V: Vertex, A = ()> {
    /// The whole tile's vertex arena; polylines are subslices of it.
    verts: &'a [V],
    /// Vertex offset where this feature's first run begins.
    start: u32,
    /// End offsets (into `verts`) of this feature's runs.
    run_ends: &'a [u32],
    /// This feature's per-feature attribute (duplicated into every tile it touches). `&()` when the
    /// attribute channel is unused.
    attr: &'a A,
}

impl<'a, V: Vertex, A> FeatureView<'a, V, A> {
    /// This feature's per-feature attribute in this tile — the value passed to
    /// [`add_feature_with`](SlicerAll::add_feature_with), duplicated onto every tile the feature
    /// touches. With the default `A = ()` this is a reference to the unit value.
    #[must_use]
    pub fn attr(&self) -> &'a A {
        self.attr
    }

    /// Iterate this feature's polylines (runs) in this tile, each a vertex slice in the tile's local
    /// frame. A feature yields several polylines where the input left the tile and re-entered.
    pub fn iter_polylines(&self) -> impl Iterator<Item = &'a [V]> + use<'a, V, A> {
        let verts = self.verts;
        let mut prev = self.start as usize;
        self.run_ends.iter().map(move |&end| {
            let end = end as usize;
            let run = &verts[prev..end];
            prev = end;
            run
        })
    }
}

/// Slices integer polylines into per-tile pieces on an integer grid, accumulating every tile each
/// polyline touches.
///
/// Generic over two independent axes:
/// - the [`Vertex`] type `V` (defaults to [`Coord<i32>`]) — plain coordinates or payload-carrying
///   vertices (e.g. a **per-vertex** M value via [`Measured`](crate::Measured)); the payload rides
///   through slicing unchanged;
/// - a **per-feature** attribute type `A` (defaults to `()`) — an id, a property map, anything you
///   want re-associated with each sliced piece. With `A = ()` the attribute channel is a zero-sized
///   type and costs nothing.
///
/// The two are orthogonal: `SlicerAll<Measured<M>, Attrs>` carries per-vertex M *and* per-feature
/// attributes without either taxing the other. Add a polyline with no attribute via
/// [`add_feature`](Self::add_feature) (only when `A = ()`), or with one via
/// [`add_feature_with`](Self::add_feature_with); read them back with
/// [`iter_tiles`](Self::iter_tiles), reaching each piece's attribute through
/// [`FeatureView::attr`]. A feature split across tiles has its attribute duplicated onto every tile
/// it touches (so `A` must be [`Clone`]).
///
/// The slicer never panics: bad input (an oversized polyline, or coordinates that overflow the tile
/// math) yields an [`TileError`] instead.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SlicerAll<V: Vertex = Coord<i32>, A = ()> {
    grid: Grid,
    /// Per-tile buffers in insertion order; slots are stable (never moved) so `index` can address
    /// them by position.
    tiles: Vec<TileBuf<V, A>>,
    /// [`TileId`] → slot in `tiles`, ordered so reads come out by tile and find-or-insert is cheap.
    index: BTreeMap<TileId, u32>,
    /// Monotonic segment counter for the direct-build run continuity (see [`RouteSink::emit`]). A gap
    /// is inserted at each polyline boundary so a run never continues across separate polylines.
    step: u64,
    /// The `step` value at the start of the feature currently being added (set in
    /// [`begin_polyline`](RouteSink::begin_polyline)). A tile whose `open_step` predates it has not yet
    /// been touched by this feature, so the next run there opens a new feature rather than extending.
    feature_start: u64,
    /// Most-recently resolved `(tile, slot)`, so consecutive writes to the same tile — the common
    /// case for a dense polyline — skip the `index` lookup entirely. Slots are stable, so this never
    /// goes stale; [`clear`](Self::clear) resets it.
    last_slot: Option<(TileId, u32)>,
    /// The attribute of the feature currently being routed (set by
    /// [`add_feature_with`](Self::add_feature_with)), cloned into each tile the feature reaches.
    /// `None` between features.
    pending_attr: Option<A>,
}

impl<V: Vertex, A> SlicerAll<V, A> {
    fn from_grid(grid: Grid) -> Self {
        Self {
            grid,
            tiles: Vec::new(),
            index: BTreeMap::new(),
            step: 0,
            feature_start: 0,
            last_slot: None,
            pending_attr: None,
        }
    }

    /// Create a slicer with the given tile side / per-tile output resolution `extent` and `buffer`.
    ///
    /// Coordinates are integers in tile space: a vertex belongs to tile `x.div_euclid(extent)` and is
    /// emitted at `x − tile·extent ∈ [0, extent)`. Project / simplify / affine-scale float source data
    /// into this space (e.g. with `geo`) before slicing.
    ///
    /// # Errors
    ///
    /// - [`TileError::InvalidExtent`] if `extent` is `0` or greater than `i32::MAX`.
    /// - [`TileError::BufferTooLarge`] if `buffer` is not strictly less than half the `extent`.
    pub fn new(extent: u32, buffer: u16) -> Result<Self, TileError> {
        Ok(Self::from_grid(Grid::new(extent, buffer)?))
    }

    /// The tile side / per-tile output resolution: kept vertices land in `0..extent`.
    #[must_use]
    pub fn extent(&self) -> u32 {
        self.grid.extent()
    }

    /// The buffer kept around every tile, in tile-space units.
    #[must_use]
    pub fn buffer(&self) -> u16 {
        self.grid.buffer()
    }

    /// Add `polyline` as an independent feature carrying `attr`: slice it into every tile it touches,
    /// storing its runs as a fresh feature in each and duplicating `attr` onto every tile it reaches.
    /// Chainable. Reach the attribute back through [`FeatureView::attr`].
    ///
    /// When `A = ()`, prefer [`add_feature`](Self::add_feature), which passes the unit attribute for
    /// you.
    ///
    /// **Atomic:** on error the pieces written so far are rolled back, so a failed polyline leaves the
    /// accumulator unchanged and usable — safe to skip the offending input and keep adding. (Errors
    /// only arise for pathological input: an oversized polyline, an adversarial spread, or coordinates
    /// near the `i32` limits.)
    ///
    /// # Errors
    ///
    /// [`TileError::PolylineTooLarge`], [`TileError::TooManyTiles`], or [`TileError::Overflow`].
    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    pub fn add_feature_with<P: AsRef<[V]>>(
        &mut self,
        polyline: P,
        attr: A,
    ) -> Result<&mut Self, TileError>
    where
        A: Clone,
    {
        let grid = self.grid; // `Grid` is `Copy`, so the walk can borrow `self` mutably as the sink.
        // Savepoint for rollback: how many tiles existed, and the last step used, before this feature.
        // Every piece this feature writes lands in a tile created after `tiles_before`, or bumps an
        // existing tile's `open_step` past `step_before` — so the two mark exactly what to undo.
        let tiles_before = self.tiles.len();
        let step_before = self.step;
        self.pending_attr = Some(attr);
        let result = grid.route(polyline.as_ref(), self);
        self.pending_attr = None;
        if let Err(err) = result {
            self.rollback_feature(tiles_before, step_before);
            return Err(err);
        }
        Ok(self)
    }

    /// Undo a partially-written feature after [`add_feature`](Self::add_feature) errored mid-walk,
    /// restoring the observable state (tiles and their features) to the savepoint. Only ever runs on
    /// the rare error path, so an `O(tiles)` scan is fine.
    fn rollback_feature(&mut self, tiles_before: usize, step_before: u64) {
        // Tiles that already existed but this feature appended to (`open_step` moved past the
        // savepoint): drop the single feature span it added, and the runs/vertices behind it.
        for buf in &mut self.tiles[..tiles_before] {
            if buf.open_step > step_before {
                buf.feat_ends.pop();
                buf.feat_attrs.pop();
                let runs_keep = buf.feat_ends.last().copied().unwrap_or(0) as usize;
                let verts_keep = if runs_keep == 0 {
                    0
                } else {
                    buf.run_ends[runs_keep - 1] as usize
                };
                buf.run_ends.truncate(runs_keep);
                buf.verts.truncate(verts_keep);
            }
        }
        // Tiles created during this feature are contiguous at the end: drop them and their index
        // entries. (Their stale `open_step` on kept tiles is harmless — the step counter only climbs,
        // so a later feature's start still outranks it and reads it as a fresh, separate feature.)
        for buf in self.tiles.drain(tiles_before..) {
            self.index.remove(&buf.tile);
        }
        self.last_slot = None;
    }

    /// The slot of `tile`'s buffer, creating it on first touch. A one-entry cache skips the `index`
    /// lookup when the same tile was just written (consecutive segments in a tile — the common case).
    #[expect(
        clippy::cast_possible_truncation,
        reason = "tile count stays far below u32::MAX"
    )]
    fn tile_slot(&mut self, tile: TileId) -> usize {
        if let Some((last, slot)) = self.last_slot
            && last == tile
        {
            return slot as usize;
        }
        let slot = if let Some(&slot) = self.index.get(&tile) {
            slot
        } else {
            let slot = self.tiles.len() as u32;
            self.tiles.push(TileBuf::new(tile));
            self.index.insert(tile, slot);
            slot
        };
        self.last_slot = Some((tile, slot));
        slot as usize
    }

    /// Iterate the touched tiles, ordered by [`TileId`], borrowing so the accumulator can keep
    /// growing afterwards. Each [`TileView`] exposes that tile's features.
    pub fn iter_tiles(&self) -> impl Iterator<Item = TileView<'_, V, A>> {
        let tiles = self.tiles.as_slice();
        self.index.values().map(move |&slot| TileView {
            buf: &tiles[slot as usize],
        })
    }

    /// Number of tiles the accumulator has touched.
    #[must_use]
    pub fn len(&self) -> usize {
        self.tiles.len()
    }

    /// Whether nothing has been accumulated yet.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.tiles.is_empty()
    }

    /// Discard everything accumulated so far, keeping the extent/buffer config.
    pub fn clear(&mut self) {
        self.tiles.clear();
        self.index.clear();
        self.step = 0;
        self.feature_start = 0;
        self.last_slot = None;
        self.pending_attr = None;
    }
}

impl<V: Vertex> SlicerAll<V, ()> {
    /// Add `polyline` as an independent feature with no attribute — shorthand for
    /// [`add_feature_with`](Self::add_feature_with)`(polyline, ())`. Available only when `A = ()`.
    ///
    /// # Errors
    ///
    /// [`TileError::PolylineTooLarge`], [`TileError::TooManyTiles`], or [`TileError::Overflow`].
    pub fn add_feature<P: AsRef<[V]>>(&mut self, polyline: P) -> Result<&mut Self, TileError> {
        self.add_feature_with(polyline, ())
    }
}

impl<V: Vertex, A: Clone> RouteSink<V> for SlicerAll<V, A> {
    /// A polyline boundary: burn one step so the first segment of this polyline cannot continue a run
    /// left open by the previous polyline (its runs stay separate, even in a shared tile), and record
    /// that step as this feature's start so `emit` knows which tiles it has already reached.
    fn begin_polyline(&mut self) {
        self.step = self.step.wrapping_add(1);
        self.feature_start = self.step;
    }

    /// Advance to the next segment.
    fn begin_segment(&mut self) {
        self.step = self.step.wrapping_add(1);
    }

    /// Append segment `a`–`c` to `tile`'s buffer (localized by `origin`), extending the tile's open
    /// run if the preceding one or two segments also landed here, else starting a new run — and, when
    /// a new run, opening a new feature unless this feature already reached the tile (a re-entry).
    #[expect(
        clippy::cast_possible_truncation,
        reason = "run/vertex counts per tile stay far below u32::MAX"
    )]
    fn emit(&mut self, tile: TileId, origin: Coord<i32>, a: V, c: V) -> Result<(), TileError> {
        let step = self.step;
        let feature_start = self.feature_start;
        let slot = self.tile_slot(tile);
        let buf = &mut self.tiles[slot];
        // Continue the open run iff the previous segment (step − 1) also landed in this tile. The
        // per-polyline gap in `begin_polyline` guarantees this never matches across polylines, and a
        // fresh tile (`open_step == 0`) never matches (the first step is ≥ 2 after the gap).
        let continues = buf.open_step == step.wrapping_sub(1);
        // Bridge a single-segment excursion: this tile was last written exactly two steps ago (the one
        // segment in between missed it) within *this* feature. That skipped segment connects the run's
        // tail to this segment's `a` — both kept — so join them into one run rather than splitting,
        // matching `slice_one`'s "break only at a dropped vertex". The `feature_start` guard keeps the
        // two-step gap from spanning a polyline boundary (where it would be a coincidence, not a
        // bridge).
        let bridges =
            !continues && buf.open_step == step.wrapping_sub(2) && buf.open_step >= feature_start;
        let c_local = to_local(c, origin)?;
        if continues {
            buf.verts.push(c_local);
            *buf.run_ends
                .last_mut()
                .expect("continuing implies an open run") = buf.verts.len() as u32;
        } else if bridges {
            // Append both endpoints of this segment: `a` is the bridge vertex just outside the tile,
            // not yet in the run.
            buf.verts.push(to_local(a, origin)?);
            buf.verts.push(c_local);
            *buf.run_ends
                .last_mut()
                .expect("bridging implies an open run") = buf.verts.len() as u32;
        } else {
            let a_local = to_local(a, origin)?;
            buf.verts.push(a_local);
            buf.verts.push(c_local);
            buf.run_ends.push(buf.verts.len() as u32);
            // Every step of this feature is ≥ `feature_start`, so an earlier `open_step` means this
            // tile has not yet been touched by the current feature → open a new one. Otherwise the
            // feature already has a run here (it left and re-entered) → extend that run span.
            if buf.open_step < feature_start {
                buf.feat_ends.push(buf.run_ends.len() as u32);
                // A new feature span in this tile: record the current feature's attribute (cloned,
                // so a feature spanning several tiles carries it into each).
                buf.feat_attrs.push(
                    self.pending_attr
                        .as_ref()
                        .expect("a feature is being routed")
                        .clone(),
                );
            } else {
                *buf.feat_ends
                    .last_mut()
                    .expect("a prior run this feature implies a feature span") =
                    buf.run_ends.len() as u32;
            }
        }
        buf.open_step = step;
        Ok(())
    }
}

/// Slices integer polylines into pieces for **one fixed tile**, accumulating only that tile.
///
/// The single-tile counterpart to [`SlicerAll`]: [`add_feature`](Self::add_feature) /
/// [`add_feature_with`](Self::add_feature_with) work exactly the same, but each polyline is clipped
/// only to this slicer's [`tile`](Self::tile). Because there is a single tile, the read API skips the
/// tile level — [`iter_features`](Self::iter_features) yields the features directly.
///
/// Generic over the [`Vertex`] type `V` (defaults to [`Coord<i32>`]) and the per-feature attribute
/// type `A` (defaults to `()`); see [`SlicerAll`] for both axes.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SlicerOne<V: Vertex = Coord<i32>, A = ()> {
    grid: Grid,
    buf: TileBuf<V, A>,
}

impl<V: Vertex, A> SlicerOne<V, A> {
    fn from_grid(grid: Grid, tile: TileId) -> Self {
        Self {
            grid,
            buf: TileBuf::new(tile),
        }
    }

    /// Create a slicer bound to `tile`, with the given tile side / per-tile output resolution `extent`
    /// and `buffer` (see [`SlicerAll::new`](crate::SlicerAll::new) for the coordinate model).
    ///
    /// # Errors
    ///
    /// - [`TileError::InvalidExtent`] if `extent` is `0` or greater than `i32::MAX`.
    /// - [`TileError::BufferTooLarge`] if `buffer` is not strictly less than half the `extent`.
    pub fn new(extent: u32, buffer: u16, tile: TileId) -> Result<Self, TileError> {
        Ok(Self::from_grid(Grid::new(extent, buffer)?, tile))
    }

    /// The tile side / per-tile output resolution: kept vertices land in `0..extent`.
    #[must_use]
    pub fn extent(&self) -> u32 {
        self.grid.extent()
    }

    /// The buffer kept around every tile, in tile-space units.
    #[must_use]
    pub fn buffer(&self) -> u16 {
        self.grid.buffer()
    }

    /// The tile this slicer clips into.
    #[must_use]
    pub fn tile(&self) -> TileId {
        self.buf.tile
    }

    /// Add `polyline` as an independent feature carrying `attr`, clipped to this slicer's
    /// [`tile`](Self::tile). Chainable. The feature (and its attribute) is recorded only if something
    /// of `polyline` lands in the tile; otherwise `attr` is dropped. Reach it back through
    /// [`FeatureView::attr`].
    ///
    /// When `A = ()`, prefer [`add_feature`](Self::add_feature).
    ///
    /// Atomic: the polyline is fully sliced first, so on error the accumulator is left unchanged.
    ///
    /// # Errors
    ///
    /// [`TileError::Overflow`] if the tile's box or a kept vertex overflows `i32`.
    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    pub fn add_feature_with<P: AsRef<[V]>>(
        &mut self,
        polyline: P,
        attr: A,
    ) -> Result<&mut Self, TileError> {
        let runs = self.grid.slice_one(polyline.as_ref(), self.buf.tile)?;
        if !runs.is_empty() {
            self.buf.absorb(runs, attr);
        }
        Ok(self)
    }

    /// Iterate this tile's features, in the order they were first added. Each [`FeatureView`] exposes
    /// that feature's clipped polylines and its [`attr`](FeatureView::attr).
    pub fn iter_features(&self) -> impl Iterator<Item = FeatureView<'_, V, A>> {
        features_of(&self.buf)
    }

    /// Number of features accumulated for the tile.
    #[must_use]
    pub fn len(&self) -> usize {
        self.buf.feat_ends.len()
    }

    /// Whether nothing has been accumulated yet.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.buf.feat_ends.is_empty()
    }

    /// Discard everything accumulated so far, keeping the extent/buffer/tile config.
    pub fn clear(&mut self) {
        self.buf = TileBuf::new(self.buf.tile);
    }
}

impl<V: Vertex> SlicerOne<V, ()> {
    /// Add `polyline` as an independent feature with no attribute — shorthand for
    /// [`add_feature_with`](Self::add_feature_with)`(polyline, ())`. Available only when `A = ()`.
    ///
    /// # Errors
    ///
    /// [`TileError::Overflow`] if the tile's box or a kept vertex overflows `i32`.
    pub fn add_feature<P: AsRef<[V]>>(&mut self, polyline: P) -> Result<&mut Self, TileError> {
        self.add_feature_with(polyline, ())
    }
}