rustial_engine/symbols/

cross_tile_index.rs

//! Cross-tile symbol index for deduplicating labels at tile boundaries.
//!
//! Matching MapLibre's `CrossTileSymbolIndex`, this module assigns stable
//! cross-tile IDs to symbol candidates so that the same conceptual label
//! appearing at a tile edge is placed exactly once, regardless of how many
//! tiles contain a copy of that feature.
//!
//! # Architecture
//!
//! The index is organised in three layers:
//!
//! | Type | Scope |
//! |------|-------|
//! | [`TileSymbolGrid`] | Per-tile spatial lookup: grid-snapped anchor positions grouped by symbol key. |
//! | [`LayerCrossTileIndex`] | Per-style-layer zoom-stratified collection of tile grids, with parent/child matching. |
//! | [`CrossTileSymbolIndex`] | Top-level facade keyed by style-layer id. |
//!
//! When a tile's symbol candidates are registered the index first attempts to
//! match each candidate against existing entries at other zoom levels (parent
//! tiles when zooming in, child tiles when zooming out). A match reuses the
//! existing cross-tile ID so that fade state, collision results, and
//! deduplication all refer to the same logical symbol. Candidates that find
//! no match receive a fresh unique ID.
//!
//! Tile eviction removes all entries for that tile and releases the
//! associated cross-tile IDs so they can be reclaimed.

use rustial_math::TileId;
use std::collections::{HashMap, HashSet};

// ---------------------------------------------------------------------------
// Constants
// ---------------------------------------------------------------------------

/// Tile-local coordinate extent (matches MapLibre's EXTENT = 8192).
///
/// Symbol anchor coordinates within a tile are expressed in `[0, EXTENT)`.
/// The rounding factor below converts these to a coarser grid used for
/// fuzzy spatial matching across zoom levels.
const EXTENT: f64 = 8192.0;

/// Grid down-sampling factor: `512 / EXTENT / 2`.
///
/// Anchor positions are multiplied by this factor before rounding so that
/// nearby symbols snap to the same grid cell. At EXTENT = 8192 this gives
/// a grid spacing of roughly 4 pixels in tile-local space.
const ROUNDING_FACTOR: f64 = 512.0 / EXTENT / 2.0;

// ---------------------------------------------------------------------------
// Cross-tile ID generator
// ---------------------------------------------------------------------------

/// Monotonically increasing cross-tile ID allocator.
///
/// Each unique conceptual symbol receives a distinct ID that persists as long
/// as the symbol remains indexed.  IDs are never reused; once evicted the
/// counter simply moves forward.
#[derive(Debug, Clone, Default)]
struct CrossTileIdGenerator {
    next_id: u64,
}

impl CrossTileIdGenerator {
    /// Allocate a fresh cross-tile ID.
    fn generate(&mut self) -> u64 {
        self.next_id += 1;
        self.next_id
    }
}

// ---------------------------------------------------------------------------
// Symbol key
// ---------------------------------------------------------------------------

/// Composite key that identifies a conceptual symbol independent of tile.
///
/// Two symbols are considered "the same" if they share the same source layer,
/// label text, and icon image. Feature IDs are intentionally excluded because
/// the same real-world feature is often split across adjacent tiles with
/// different local feature indices.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct SymbolKey {
    /// Source layer name (e.g. `"poi"`, `"place_label"`).
    source_layer: String,
    /// Label text content, or empty if icon-only.
    text: String,
    /// Icon image id, or empty if text-only.
    icon: String,
}

// ---------------------------------------------------------------------------
// Grid-snapped position
// ---------------------------------------------------------------------------

/// An anchor position rounded to the cross-tile matching grid.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct GridPosition {
    x: i32,
    y: i32,
}

// ---------------------------------------------------------------------------
// Per-tile spatial index
// ---------------------------------------------------------------------------

/// Per-tile spatial index of symbol entries grouped by [`SymbolKey`].
///
/// When a tile is registered each symbol candidate is bucketed by its key.
/// Within each bucket the grid-snapped anchor position and assigned
/// cross-tile ID are stored so that later tiles can search for matches.
#[derive(Debug, Clone)]
struct TileSymbolGrid {
    /// The tile this grid belongs to.
    tile_id: TileId,
    /// Unique instance identifier used to detect stale re-registrations.
    instance_id: u64,
    /// Symbol entries grouped by key. Each entry stores `(grid_pos, cross_tile_id)`.
    entries: HashMap<SymbolKey, Vec<(GridPosition, u64)>>,
}

impl TileSymbolGrid {
    /// Create a new empty grid for the given tile.
    fn new(tile_id: TileId, instance_id: u64) -> Self {
        Self {
            tile_id,
            instance_id,
            entries: HashMap::new(),
        }
    }

    /// Attempt to match an incoming candidate against this grid's entries.
    ///
    /// Returns the cross-tile ID of the first spatially matching entry that
    /// has not already been claimed in `used_ids`, or `None` if no match.
    ///
    /// `scaled_pos` must already be converted to this grid's coordinate
    /// system via [`scaled_coordinates`].
    fn find_match(
        &self,
        key: &SymbolKey,
        scaled_pos: GridPosition,
        tolerance: i32,
        used_ids: &HashSet<u64>,
    ) -> Option<u64> {
        let bucket = self.entries.get(key)?;
        for &(pos, cross_tile_id) in bucket {
            if (pos.x - scaled_pos.x).abs() <= tolerance
                && (pos.y - scaled_pos.y).abs() <= tolerance
                && !used_ids.contains(&cross_tile_id)
            {
                return Some(cross_tile_id);
            }
        }
        None
    }

    /// Collect all cross-tile IDs stored in this grid.
    fn all_cross_tile_ids(&self) -> Vec<u64> {
        self.entries
            .values()
            .flat_map(|bucket| bucket.iter().map(|&(_, id)| id))
            .collect()
    }
}

// ---------------------------------------------------------------------------
// Coordinate scaling helpers
// ---------------------------------------------------------------------------

/// Convert a candidate's tile-local anchor into grid coordinates relative
/// to `target_tile`, adjusting for zoom difference.
///
/// This mirrors MapLibre's `TileLayerIndex.getScaledCoordinates`: the
/// candidate's world-space position (tile origin + anchor) is projected into
/// `target_tile`'s local grid at the rounding resolution.
fn scaled_coordinates(
    anchor_x: f64,
    anchor_y: f64,
    candidate_tile: TileId,
    target_tile: TileId,
) -> GridPosition {
    let z_diff = candidate_tile.zoom as i32 - target_tile.zoom as i32;
    let scale = ROUNDING_FACTOR / 2.0_f64.powi(z_diff);

    let x_world = (candidate_tile.x as f64 * EXTENT + anchor_x) * scale;
    let y_world = (candidate_tile.y as f64 * EXTENT + anchor_y) * scale;

    let x_offset = target_tile.x as f64 * EXTENT * ROUNDING_FACTOR;
    let y_offset = target_tile.y as f64 * EXTENT * ROUNDING_FACTOR;

    GridPosition {
        x: (x_world - x_offset).floor() as i32,
        y: (y_world - y_offset).floor() as i32,
    }
}

/// Snap a tile-local anchor to the grid at native resolution (no zoom
/// scaling). Used when inserting entries into the grid for their own tile.
fn native_grid_position(anchor_x: f64, anchor_y: f64) -> GridPosition {
    GridPosition {
        x: (anchor_x * ROUNDING_FACTOR).floor() as i32,
        y: (anchor_y * ROUNDING_FACTOR).floor() as i32,
    }
}

// ---------------------------------------------------------------------------
// Per-layer cross-tile index
// ---------------------------------------------------------------------------

/// Per-style-layer cross-tile index stratified by zoom level.
///
/// Each zoom level maps tile keys to their [`TileSymbolGrid`]. When a new
/// tile is added the index searches grids at other zoom levels for matching
/// symbols, propagating cross-tile IDs across parent/child relationships.
#[derive(Debug, Clone, Default)]
struct LayerCrossTileIndex {
    /// `zoom -> (tile_key -> grid)`.
    grids: HashMap<u8, HashMap<u64, TileSymbolGrid>>,
    /// `zoom -> set_of_cross_tile_ids` currently claimed at that zoom.
    used_ids: HashMap<u8, HashSet<u64>>,
}

/// Compute a u64 tile key from a `TileId` for use as a hash-map key.
/// Uses a simple bit-packing: `(z << 48) | (x << 24) | y`.
fn tile_key(tile: &TileId) -> u64 {
    ((tile.zoom as u64) << 48) | ((tile.x as u64) << 24) | (tile.y as u64)
}

/// Check whether `child` is a descendant of `parent` in the tile tree.
fn is_child_of(child: &TileId, parent: &TileId) -> bool {
    if child.zoom <= parent.zoom {
        return false;
    }
    let dz = child.zoom - parent.zoom;
    (child.x >> dz) == parent.x && (child.y >> dz) == parent.y
}

/// Scale `child` up to `target_zoom` (must be <= child.zoom) to get the
/// ancestor tile coordinates at that zoom.
fn scaled_to(tile: &TileId, target_zoom: u8) -> TileId {
    if target_zoom >= tile.zoom {
        return *tile;
    }
    let dz = tile.zoom - target_zoom;
    TileId::new(target_zoom, tile.x >> dz, tile.y >> dz)
}

impl LayerCrossTileIndex {
    /// Register a tile's symbol candidates, assigning cross-tile IDs.
    ///
    /// Returns `true` if any IDs were newly assigned (i.e. the symbol set
    /// changed), which signals that placement should re-run.
    fn add_tile(
        &mut self,
        tile_id: TileId,
        instance_id: u64,
        candidates: &mut [SymbolCandidateEntry],
        id_gen: &mut CrossTileIdGenerator,
    ) -> bool {
        let tk = tile_key(&tile_id);

        // If we already have this exact instance, skip.
        if let Some(zoom_grids) = self.grids.get(&tile_id.zoom) {
            if let Some(existing) = zoom_grids.get(&tk) {
                if existing.instance_id == instance_id {
                    return false;
                }
            }
        }

        // Remove previously claimed IDs for this tile slot (replacement).
        if let Some(zoom_grids) = self.grids.get(&tile_id.zoom) {
            if let Some(old_grid) = zoom_grids.get(&tk) {
                let old_ids = old_grid.all_cross_tile_ids();
                if let Some(used) = self.used_ids.get_mut(&tile_id.zoom) {
                    for id in &old_ids {
                        used.remove(id);
                    }
                }
            }
        }

        // Clear candidate cross-tile IDs before matching.
        for c in candidates.iter_mut() {
            c.assigned_cross_tile_id = 0;
        }

        // Ensure used-ID set exists for this zoom.
        let zoom_used = self.used_ids.entry(tile_id.zoom).or_default();

        // Search other zoom levels for matches.
        for (&z, zoom_grids) in &self.grids {
            if z > tile_id.zoom {
                // z is a child zoom: search child grids whose tile is a
                // descendant of the incoming tile.
                for grid in zoom_grids.values() {
                    if is_child_of(&grid.tile_id, &tile_id) {
                        Self::match_candidates(
                            candidates,
                            grid,
                            &tile_id,
                            zoom_used,
                        );
                    }
                }
            } else {
                // z is a parent (or same) zoom: scale the incoming tile up
                // to that zoom and look for the parent grid.
                let parent_coord = scaled_to(&tile_id, z);
                let parent_key = tile_key(&parent_coord);
                if let Some(parent_grid) = zoom_grids.get(&parent_key) {
                    Self::match_candidates(
                        candidates,
                        parent_grid,
                        &tile_id,
                        zoom_used,
                    );
                }
            }
        }

        // Assign new IDs to any unmatched candidates.
        for c in candidates.iter_mut() {
            if c.assigned_cross_tile_id == 0 {
                let id = id_gen.generate();
                c.assigned_cross_tile_id = id;
                zoom_used.insert(id);
            }
        }

        // Build and store the tile grid.
        let mut grid = TileSymbolGrid::new(tile_id, instance_id);
        for c in candidates.iter() {
            let key = c.key.clone();
            let pos = native_grid_position(c.anchor_x, c.anchor_y);
            grid.entries
                .entry(key)
                .or_default()
                .push((pos, c.assigned_cross_tile_id));
        }

        self.grids
            .entry(tile_id.zoom)
            .or_default()
            .insert(tk, grid);

        true
    }

    /// Match unassigned candidates against an existing tile grid.
    fn match_candidates(
        candidates: &mut [SymbolCandidateEntry],
        grid: &TileSymbolGrid,
        candidate_tile: &TileId,
        used_ids: &mut HashSet<u64>,
    ) {
        // Tolerance: 1 grid unit when same zoom, widens for parent tiles.
        let tolerance = if grid.tile_id.zoom < candidate_tile.zoom {
            1
        } else {
            1i32 << (grid.tile_id.zoom as i32 - candidate_tile.zoom as i32).max(0)
        };

        for c in candidates.iter_mut() {
            if c.assigned_cross_tile_id != 0 {
                continue;
            }
            let scaled = scaled_coordinates(
                c.anchor_x,
                c.anchor_y,
                *candidate_tile,
                grid.tile_id,
            );
            if let Some(matched_id) =
                grid.find_match(&c.key, scaled, tolerance, used_ids)
            {
                c.assigned_cross_tile_id = matched_id;
                used_ids.insert(matched_id);
            }
        }
    }

    /// Remove grids for tiles whose instance IDs are not in `current_ids`.
    ///
    /// Returns `true` if any grids were removed.
    fn remove_stale(&mut self, current_ids: &HashSet<u64>) -> bool {
        let mut changed = false;
        for (&z, zoom_grids) in self.grids.iter_mut() {
            let before = zoom_grids.len();
            let used = self.used_ids.entry(z).or_default();
            zoom_grids.retain(|_tk, grid| {
                if current_ids.contains(&grid.instance_id) {
                    true
                } else {
                    // Release cross-tile IDs.
                    for id in grid.all_cross_tile_ids() {
                        used.remove(&id);
                    }
                    false
                }
            });
            if zoom_grids.len() != before {
                changed = true;
            }
        }
        changed
    }

    /// Remove all grids associated with a specific tile.
    fn remove_tile(&mut self, tile_id: &TileId) {
        let tk = tile_key(tile_id);
        if let Some(zoom_grids) = self.grids.get_mut(&tile_id.zoom) {
            if let Some(grid) = zoom_grids.remove(&tk) {
                if let Some(used) = self.used_ids.get_mut(&tile_id.zoom) {
                    for id in grid.all_cross_tile_ids() {
                        used.remove(&id);
                    }
                }
            }
        }
    }
}

// ---------------------------------------------------------------------------
// Public: symbol candidate entry (lightweight input)
// ---------------------------------------------------------------------------

/// Lightweight input record fed into the cross-tile index.
///
/// Callers convert their full [`super::SymbolCandidate`] into this compact
/// representation before passing it to [`CrossTileSymbolIndex::assign`].
/// The index writes back the assigned cross-tile ID into
/// [`assigned_cross_tile_id`](Self::assigned_cross_tile_id).
#[derive(Debug, Clone)]
pub struct SymbolCandidateEntry {
    /// Composite symbol key (source layer + text + icon).
    key: SymbolKey,
    /// Tile-local anchor X in `[0, EXTENT)`.
    anchor_x: f64,
    /// Tile-local anchor Y in `[0, EXTENT)`.
    anchor_y: f64,
    /// Cross-tile ID written by the index. Zero means unassigned.
    pub assigned_cross_tile_id: u64,
}

impl SymbolCandidateEntry {
    /// Create a new candidate entry.
    ///
    /// `source_layer`, `text`, and `icon` form the deduplication key.
    /// `anchor_x` and `anchor_y` are the symbol's position within the tile
    /// in tile-local coordinates (range `[0, EXTENT)`, matching the MVT
    /// geometry coordinate space).
    pub fn new(
        source_layer: &str,
        text: &str,
        icon: &str,
        anchor_x: f64,
        anchor_y: f64,
    ) -> Self {
        Self {
            key: SymbolKey {
                source_layer: source_layer.to_owned(),
                text: text.to_owned(),
                icon: icon.to_owned(),
            },
            anchor_x,
            anchor_y,
            assigned_cross_tile_id: 0,
        }
    }
}

// ---------------------------------------------------------------------------
// Public: top-level cross-tile symbol index
// ---------------------------------------------------------------------------

/// Cross-tile symbol index that deduplicates labels across tile boundaries.
///
/// This is the top-level entry point, keyed by style-layer id. Each style
/// layer has an independent [`LayerCrossTileIndex`] so that labels from
/// different layers do not interfere with each other.
///
/// # Usage
///
/// ```text
/// let mut index = CrossTileSymbolIndex::new();
///
/// // For each tile's symbol candidates:
/// let changed = index.assign("poi-labels", tile_id, instance_id, &mut entries);
///
/// // After placement, prune tiles no longer visible:
/// index.prune_stale("poi-labels", &active_instance_ids);
///
/// // When a tile is evicted from the cache:
/// index.remove_tile(&tile_id);
/// ```
#[derive(Debug, Clone, Default)]
pub struct CrossTileSymbolIndex {
    /// Per-layer index, keyed by style-layer id.
    layers: HashMap<String, LayerCrossTileIndex>,
    /// Monotonic ID generator shared across all layers.
    id_gen: CrossTileIdGenerator,
    /// Global instance-ID counter for tile registrations.
    next_instance_id: u64,
}

impl CrossTileSymbolIndex {
    /// Create an empty cross-tile symbol index.
    pub fn new() -> Self {
        Self::default()
    }

    /// Allocate a unique instance ID for a tile registration.
    ///
    /// Each call to [`assign`](Self::assign) should use a fresh instance ID
    /// so the index can detect when a tile's data has been replaced (e.g.
    /// after a style change or data update).
    pub fn next_instance_id(&mut self) -> u64 {
        self.next_instance_id += 1;
        self.next_instance_id
    }

    /// Register a tile's symbol candidates and assign cross-tile IDs.
    ///
    /// After this call, each entry in `candidates` will have a non-zero
    /// [`assigned_cross_tile_id`](SymbolCandidateEntry::assigned_cross_tile_id)
    /// that is stable across zoom transitions and tile reloads.
    ///
    /// Returns `true` if any IDs changed (caller should re-run placement).
    pub fn assign(
        &mut self,
        layer_id: &str,
        tile_id: TileId,
        instance_id: u64,
        candidates: &mut [SymbolCandidateEntry],
    ) -> bool {
        let layer_index = self
            .layers
            .entry(layer_id.to_owned())
            .or_default();
        layer_index.add_tile(tile_id, instance_id, candidates, &mut self.id_gen)
    }

    /// Remove grids for tiles whose instance IDs are no longer active.
    ///
    /// Call this after each placement frame with the set of instance IDs
    /// that are still in use. Returns `true` if any stale grids were removed.
    pub fn prune_stale(
        &mut self,
        layer_id: &str,
        current_instance_ids: &HashSet<u64>,
    ) -> bool {
        if let Some(layer_index) = self.layers.get_mut(layer_id) {
            layer_index.remove_stale(current_instance_ids)
        } else {
            false
        }
    }

    /// Remove all index entries for a specific tile across all layers.
    ///
    /// Call this when a tile is evicted from the tile cache to release the
    /// associated cross-tile IDs.
    pub fn remove_tile(&mut self, tile_id: &TileId) {
        for layer_index in self.layers.values_mut() {
            layer_index.remove_tile(tile_id);
        }
    }

    /// Remove index state for layers that are no longer active.
    ///
    /// `active_layers` is the set of style-layer IDs currently in use.
    /// Any layer not in this set has its index state dropped.
    pub fn prune_layers(&mut self, active_layers: &HashSet<String>) {
        self.layers.retain(|id, _| active_layers.contains(id));
    }

    /// Total number of indexed tiles across all layers and zoom levels.
    pub fn tile_count(&self) -> usize {
        self.layers
            .values()
            .flat_map(|layer| layer.grids.values())
            .map(|zoom_grids| zoom_grids.len())
            .sum()
    }

    /// Total number of indexed symbol entries across all tiles and layers.
    pub fn entry_count(&self) -> usize {
        self.layers
            .values()
            .flat_map(|layer| layer.grids.values())
            .flat_map(|zoom_grids| zoom_grids.values())
            .map(|grid| {
                grid.entries.values().map(|bucket| bucket.len()).sum::<usize>()
            })
            .sum()
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;

    /// Helper: build a candidate entry at a position within a tile.
    fn entry(source_layer: &str, text: &str, anchor_x: f64, anchor_y: f64) -> SymbolCandidateEntry {
        SymbolCandidateEntry::new(source_layer, text, "", anchor_x, anchor_y)
    }

    #[test]
    fn assigns_unique_ids_to_distinct_symbols() {
        let mut index = CrossTileSymbolIndex::new();
        let iid = index.next_instance_id();
        let tile = TileId::new(10, 512, 512);
        let mut candidates = vec![
            entry("poi", "Restaurant", 100.0, 200.0),
            entry("poi", "Cafe", 300.0, 400.0),
        ];
        index.assign("symbols", tile, iid, &mut candidates);

        assert_ne!(candidates[0].assigned_cross_tile_id, 0);
        assert_ne!(candidates[1].assigned_cross_tile_id, 0);
        assert_ne!(
            candidates[0].assigned_cross_tile_id,
            candidates[1].assigned_cross_tile_id
        );
    }

    #[test]
    fn matches_same_symbol_across_parent_and_child_tiles() {
        let mut index = CrossTileSymbolIndex::new();

        // Register a symbol in a parent tile at zoom 10.
        // Anchor (2048, 2048) is the centre of the top-left quadrant.
        let parent = TileId::new(10, 512, 512);
        let parent_iid = index.next_instance_id();
        let mut parent_candidates = vec![entry("poi", "Museum", 2048.0, 2048.0)];
        index.assign("symbols", parent, parent_iid, &mut parent_candidates);
        let parent_id = parent_candidates[0].assigned_cross_tile_id;
        assert_ne!(parent_id, 0);

        // Register the same symbol in the top-left child tile at zoom 11.
        // The parent's local (2048, 2048) maps to (4096, 4096) in the child
        // because the child covers exactly the top-left quadrant of the parent
        // and its local EXTENT is doubled relative to the parent's sub-region.
        let child = TileId::new(11, 1024, 1024);
        let child_iid = index.next_instance_id();
        let mut child_candidates = vec![entry("poi", "Museum", 4096.0, 4096.0)];
        index.assign("symbols", child, child_iid, &mut child_candidates);

        // The child should inherit the parent's cross-tile ID.
        assert_eq!(child_candidates[0].assigned_cross_tile_id, parent_id);
    }

    #[test]
    fn does_not_match_different_text() {
        let mut index = CrossTileSymbolIndex::new();

        // Parent anchor at (2048, 2048) -- centre of top-left quadrant.
        let parent = TileId::new(10, 512, 512);
        let parent_iid = index.next_instance_id();
        let mut parent_candidates = vec![entry("poi", "Museum", 2048.0, 2048.0)];
        index.assign("symbols", parent, parent_iid, &mut parent_candidates);
        let parent_id = parent_candidates[0].assigned_cross_tile_id;

        // Same world position in the child but different label text.
        let child = TileId::new(11, 1024, 1024);
        let child_iid = index.next_instance_id();
        let mut child_candidates = vec![entry("poi", "Library", 4096.0, 4096.0)];
        index.assign("symbols", child, child_iid, &mut child_candidates);

        // Different text should not reuse the parent ID.
        assert_ne!(child_candidates[0].assigned_cross_tile_id, parent_id);
    }

    #[test]
    fn eviction_removes_tile_entries() {
        let mut index = CrossTileSymbolIndex::new();

        let tile = TileId::new(10, 512, 512);
        let iid = index.next_instance_id();
        let mut candidates = vec![entry("poi", "Park", 1000.0, 2000.0)];
        index.assign("symbols", tile, iid, &mut candidates);

        assert_eq!(index.entry_count(), 1);
        assert_eq!(index.tile_count(), 1);

        index.remove_tile(&tile);

        assert_eq!(index.entry_count(), 0);
        assert_eq!(index.tile_count(), 0);
    }

    #[test]
    fn prune_stale_removes_old_tiles() {
        let mut index = CrossTileSymbolIndex::new();

        let tile_a = TileId::new(10, 512, 512);
        let iid_a = index.next_instance_id();
        let mut a = vec![entry("poi", "A", 100.0, 100.0)];
        index.assign("symbols", tile_a, iid_a, &mut a);

        let tile_b = TileId::new(10, 513, 512);
        let iid_b = index.next_instance_id();
        let mut b = vec![entry("poi", "B", 100.0, 100.0)];
        index.assign("symbols", tile_b, iid_b, &mut b);

        assert_eq!(index.tile_count(), 2);

        // Only keep tile_a.
        let mut active = HashSet::new();
        active.insert(iid_a);
        let changed = index.prune_stale("symbols", &active);
        assert!(changed);
        assert_eq!(index.tile_count(), 1);
    }

    #[test]
    fn same_instance_id_is_no_op() {
        let mut index = CrossTileSymbolIndex::new();

        let tile = TileId::new(10, 512, 512);
        let iid = index.next_instance_id();
        let mut candidates = vec![entry("poi", "Park", 1000.0, 2000.0)];
        let changed1 = index.assign("symbols", tile, iid, &mut candidates);
        assert!(changed1);

        // Re-registering with the same instance ID should be a no-op.
        let mut candidates2 = vec![entry("poi", "Park", 1000.0, 2000.0)];
        let changed2 = index.assign("symbols", tile, iid, &mut candidates2);
        assert!(!changed2);
    }

    #[test]
    fn adjacent_tiles_at_same_zoom_do_not_cross_match() {
        let mut index = CrossTileSymbolIndex::new();

        // Two adjacent tiles at the same zoom with the same label text
        // but different tile-local positions should get distinct IDs.
        let tile_a = TileId::new(10, 512, 512);
        let iid_a = index.next_instance_id();
        let mut a = vec![entry("poi", "Church", 7000.0, 4096.0)];
        index.assign("symbols", tile_a, iid_a, &mut a);

        let tile_b = TileId::new(10, 513, 512);
        let iid_b = index.next_instance_id();
        let mut b = vec![entry("poi", "Church", 100.0, 4096.0)];
        index.assign("symbols", tile_b, iid_b, &mut b);

        // Same zoom tiles are indexed independently; they should only
        // match if one is a parent/child of the other.
        assert_ne!(
            a[0].assigned_cross_tile_id,
            b[0].assigned_cross_tile_id
        );
    }

    #[test]
    fn child_registered_first_propagates_to_parent() {
        let mut index = CrossTileSymbolIndex::new();

        // Register a child tile first.
        // Anchor (4096, 4096) = centre of child (11, 1024, 1024).
        let child = TileId::new(11, 1024, 1024);
        let child_iid = index.next_instance_id();
        let mut child_candidates = vec![entry("poi", "Station", 4096.0, 4096.0)];
        index.assign("symbols", child, child_iid, &mut child_candidates);
        let child_id = child_candidates[0].assigned_cross_tile_id;

        // Now register the parent with the world-equivalent anchor.
        // Child local (4096, 4096) maps to parent local (2048, 2048).
        let parent = TileId::new(10, 512, 512);
        let parent_iid = index.next_instance_id();
        let mut parent_candidates = vec![entry("poi", "Station", 2048.0, 2048.0)];
        index.assign("symbols", parent, parent_iid, &mut parent_candidates);

        assert_eq!(parent_candidates[0].assigned_cross_tile_id, child_id);
    }

    #[test]
    fn prune_layers_removes_unused_layers() {
        let mut index = CrossTileSymbolIndex::new();

        let tile = TileId::new(10, 512, 512);
        let iid = index.next_instance_id();
        let mut a = vec![entry("poi", "A", 100.0, 100.0)];
        index.assign("layer-a", tile, iid, &mut a);

        let iid2 = index.next_instance_id();
        let mut b = vec![entry("road", "B", 200.0, 200.0)];
        index.assign("layer-b", tile, iid2, &mut b);

        assert_eq!(index.tile_count(), 2);

        let mut active = HashSet::new();
        active.insert("layer-a".to_owned());
        index.prune_layers(&active);

        assert_eq!(index.tile_count(), 1);
    }

    #[test]
    fn replacement_tile_reclaims_ids() {
        let mut index = CrossTileSymbolIndex::new();

        let tile = TileId::new(10, 512, 512);
        let iid1 = index.next_instance_id();
        let mut a = vec![entry("poi", "Old", 100.0, 100.0)];
        index.assign("symbols", tile, iid1, &mut a);
        let old_id = a[0].assigned_cross_tile_id;

        // Replace with a new instance (e.g. tile data updated).
        let iid2 = index.next_instance_id();
        let mut b = vec![entry("poi", "New", 100.0, 100.0)];
        index.assign("symbols", tile, iid2, &mut b);

        // The old ID should have been released and a new one assigned.
        assert_ne!(b[0].assigned_cross_tile_id, old_id);
        assert_eq!(index.tile_count(), 1);
    }

    #[test]
    fn multi_zoom_chain_propagates_ids() {
        let mut index = CrossTileSymbolIndex::new();

        // Three zoom levels: z9 -> z10 -> z11, all referencing the same
        // world position.  Each child is the top-left quadrant of its
        // parent, so the tile-local anchor doubles at each step:
        //   z9  (256, 256) anchor (1024, 1024)
        //   z10 (512, 512) anchor (2048, 2048)   -- 1024 * 2
        //   z11 (1024,1024) anchor (4096, 4096)   -- 2048 * 2
        let z9 = TileId::new(9, 256, 256);
        let iid9 = index.next_instance_id();
        let mut c9 = vec![entry("poi", "Bridge", 1024.0, 1024.0)];
        index.assign("symbols", z9, iid9, &mut c9);
        let id9 = c9[0].assigned_cross_tile_id;

        // Register at zoom 10 (child of z9).
        let z10 = TileId::new(10, 512, 512);
        let iid10 = index.next_instance_id();
        let mut c10 = vec![entry("poi", "Bridge", 2048.0, 2048.0)];
        index.assign("symbols", z10, iid10, &mut c10);
        assert_eq!(c10[0].assigned_cross_tile_id, id9);

        // Register at zoom 11 (child of z10).
        let z11 = TileId::new(11, 1024, 1024);
        let iid11 = index.next_instance_id();
        let mut c11 = vec![entry("poi", "Bridge", 4096.0, 4096.0)];
        index.assign("symbols", z11, iid11, &mut c11);
        assert_eq!(c11[0].assigned_cross_tile_id, id9);
    }
}