nucleation 0.10.14

//! A tile: an axis-aligned voxel block that a source can yield independently.
//!
//! Blocks are stored as a deduplicated palette plus sorted `(position, index)`
//! cells. Sorting at construction is what makes downstream iteration
//! order-independent without every consumer having to re-sort.

use std::collections::BTreeMap;

use crate::block_entity::BlockEntity;
use crate::block_state::BlockState;
use crate::world_segment::ids::TileId;

/// Inclusive world-space bounds.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct TileBounds {
    pub min: (i32, i32, i32),
    pub max: (i32, i32, i32),
}

impl TileBounds {
    pub fn contains(&self, x: i32, y: i32, z: i32) -> bool {
        x >= self.min.0
            && x <= self.max.0
            && y >= self.min.1
            && y <= self.max.1
            && z >= self.min.2
            && z <= self.max.2
    }
}

/// One tile's non-air blocks.
///
/// Memory note: this holds every non-air block in the tile, including
/// substrate. Substrate is dropped by `segment_tile`, not here, so that
/// classification stays a pure decision a test can drive directly.
pub struct VoxelTile {
    id: TileId,
    bounds: TileBounds,
    palette: Vec<BlockState>,
    /// Sorted by position. `(x, y, z, palette_index)`.
    cells: Vec<((i32, i32, i32), u32)>,
    /// Block entities keyed by their world-space block position.
    block_entities: Vec<BlockEntity>,
}

impl VoxelTile {
    /// Build a tile from an arbitrary, arbitrarily-ordered block stream.
    ///
    /// # Duplicate positions
    ///
    /// The same position may legitimately arrive more than once — region and
    /// chunk readers overlap, and so do tile margins. The winner is
    /// **content-defined, never order-defined**: of the states offered for a
    /// position, the one with the lexicographically smallest canonical
    /// [`palette_key`] is kept, and the rest are discarded.
    ///
    /// A last-write-wins `insert` would make the surviving block a function of
    /// arrival order, and since classification can differ between the
    /// candidates (one substrate, one artificial) that would change the cluster
    /// set — breaking the module's central guarantee that identical input plus
    /// identical config yields byte-identical output.
    ///
    /// The tie-break is deliberately arbitrary but total: any rule works so
    /// long as it depends only on content, and `palette_key` is already the
    /// canonical string used for palette dedup, so no new notion of block
    /// identity is introduced.
    ///
    /// Blocks outside `bounds` are dropped.
    pub fn from_blocks(
        id: TileId,
        bounds: TileBounds,
        blocks: impl Iterator<Item = ((i32, i32, i32), BlockState)>,
    ) -> Self {
        Self::from_blocks_and_block_entities(id, bounds, blocks, std::iter::empty())
    }

    /// Build a tile while retaining block entities whose positions lie within
    /// its bounds. The simpler [`Self::from_blocks`] remains available for
    /// sources that do not expose NBT-bearing blocks.
    pub fn from_blocks_and_block_entities(
        id: TileId,
        bounds: TileBounds,
        blocks: impl Iterator<Item = ((i32, i32, i32), BlockState)>,
        block_entities: impl Iterator<Item = BlockEntity>,
    ) -> Self {
        let mut seen: Vec<BlockState> = Vec::new();
        // Canonical key of `seen[i]`, kept alongside so a duplicate can be
        // resolved by key without re-deriving it. One clone per distinct
        // state, not one per block.
        let mut seen_keys: Vec<String> = Vec::new();
        let mut lookup: BTreeMap<String, u32> = BTreeMap::new();
        // BTreeMap keyed by position: dedupes repeated positions and yields
        // sorted order for free.
        let mut cells: BTreeMap<(i32, i32, i32), u32> = BTreeMap::new();

        for (pos, state) in blocks {
            if !bounds.contains(pos.0, pos.1, pos.2) {
                continue;
            }
            let key = palette_key(&state);
            let idx = match lookup.get(&key) {
                Some(i) => *i,
                None => {
                    let i = seen.len() as u32;
                    seen.push(state);
                    seen_keys.push(key.clone());
                    lookup.insert(key, i);
                    i
                }
            };
            match cells.entry(pos) {
                std::collections::btree_map::Entry::Vacant(e) => {
                    e.insert(idx);
                }
                std::collections::btree_map::Entry::Occupied(mut e) => {
                    // Smaller canonical key wins. Equal keys mean equal states,
                    // so the comparison never has to break a genuine tie.
                    if seen_keys[idx as usize] < seen_keys[*e.get() as usize] {
                        e.insert(idx);
                    }
                }
            }
        }

        // Compact: keep only states some surviving cell references, ordered by
        // canonical key. A state that lost every duplicate contest it entered
        // must not linger in the palette, or `palette_len` — and any future
        // consumer of palette order — would still depend on arrival order.
        let mut used: Vec<u32> = cells.values().copied().collect();
        used.sort_unstable();
        used.dedup();
        used.sort_by(|a, b| seen_keys[*a as usize].cmp(&seen_keys[*b as usize]));

        let mut remap: Vec<u32> = vec![u32::MAX; seen.len()];
        let mut palette: Vec<BlockState> = Vec::with_capacity(used.len());
        for (new_idx, old_idx) in used.iter().enumerate() {
            remap[*old_idx as usize] = new_idx as u32;
            palette.push(seen[*old_idx as usize].clone());
        }

        let cells: Vec<((i32, i32, i32), u32)> = cells
            .into_iter()
            .map(|(pos, old)| (pos, remap[old as usize]))
            .collect();

        let mut block_entities_by_pos: BTreeMap<(i32, i32, i32), BlockEntity> = BTreeMap::new();
        for block_entity in block_entities {
            let pos = block_entity.position;
            if !bounds.contains(pos.0, pos.1, pos.2) {
                continue;
            }
            match block_entities_by_pos.entry(pos) {
                std::collections::btree_map::Entry::Vacant(entry) => {
                    entry.insert(block_entity);
                }
                std::collections::btree_map::Entry::Occupied(entry) => {
                    debug_assert_eq!(
                        entry.get(),
                        &block_entity,
                        "one world position yielded conflicting block entities"
                    );
                }
            }
        }

        VoxelTile {
            id,
            bounds,
            palette,
            cells,
            block_entities: block_entities_by_pos.into_values().collect(),
        }
    }

    pub fn id(&self) -> TileId {
        self.id
    }

    pub fn bounds(&self) -> &TileBounds {
        &self.bounds
    }

    pub fn len(&self) -> usize {
        self.cells.len()
    }

    pub fn is_empty(&self) -> bool {
        self.cells.is_empty()
    }

    pub fn palette_len(&self) -> usize {
        self.palette.len()
    }

    /// Blocks in ascending position order.
    pub fn blocks(&self) -> impl Iterator<Item = ((i32, i32, i32), &BlockState)> + '_ {
        self.cells
            .iter()
            .map(move |(pos, idx)| (*pos, &self.palette[*idx as usize]))
    }

    /// NBT-bearing blocks in ascending world-position order.
    pub fn block_entities(&self) -> &[BlockEntity] {
        &self.block_entities
    }
}

/// Canonical string for palette dedup: name plus sorted properties.
fn palette_key(state: &BlockState) -> String {
    let mut props: Vec<String> = state
        .properties
        .iter()
        .map(|(k, v)| format!("{k}={v}"))
        .collect();
    props.sort();
    format!("{}[{}]", state.get_name(), props.join(","))
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::world_segment::ids::TileId;

    fn bs(name: &str) -> BlockState {
        BlockState::new(name)
    }

    fn bounds() -> TileBounds {
        TileBounds {
            min: (0, 0, 0),
            max: (15, 15, 15),
        }
    }

    #[test]
    fn bounds_contains_is_inclusive() {
        let b = bounds();
        assert!(b.contains(0, 0, 0));
        assert!(b.contains(15, 15, 15));
        assert!(!b.contains(16, 0, 0));
        assert!(!b.contains(-1, 0, 0));
    }

    #[test]
    fn tile_stores_blocks_and_dedupes_palette() {
        let tile = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((1, 2, 3), bs("minecraft:stone")),
                ((4, 5, 6), bs("minecraft:stone")),
                ((7, 8, 9), bs("minecraft:redstone_wire")),
            ]
            .into_iter(),
        );
        assert_eq!(tile.len(), 3);
        assert_eq!(
            tile.palette_len(),
            2,
            "identical states share a palette entry"
        );
        assert_eq!(tile.id(), TileId { x: 0, z: 0 });
    }

    #[test]
    fn tile_drops_out_of_bounds_blocks() {
        let tile = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((1, 1, 1), bs("minecraft:stone")),
                ((99, 1, 1), bs("minecraft:stone")),
            ]
            .into_iter(),
        );
        assert_eq!(tile.len(), 1, "out-of-bounds blocks are rejected");
    }

    #[test]
    fn tile_retains_only_in_bounds_block_entities() {
        let tile = VoxelTile::from_blocks_and_block_entities(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![((1, 2, 3), bs("minecraft:chest"))].into_iter(),
            vec![
                BlockEntity::new("minecraft:chest".to_string(), (1, 2, 3)),
                BlockEntity::new("minecraft:chest".to_string(), (99, 2, 3)),
            ]
            .into_iter(),
        );
        assert_eq!(tile.block_entities().len(), 1);
        assert_eq!(tile.block_entities()[0].position, (1, 2, 3));
    }

    /// Names and their canonical `palette_key`s, so the expected winner below
    /// is arithmetic rather than intuition:
    ///   "minecraft:redstone_wire[]"
    ///   "minecraft:stone[]"
    /// `'r'` (0x72) < `'s'` (0x73) at the first differing byte, so
    /// `redstone_wire` is the lexicographically smaller key and must win
    /// whichever order the two are supplied in.
    #[test]
    fn duplicate_positions_resolve_to_the_smaller_palette_key_either_way() {
        let forward = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((1, 1, 1), bs("minecraft:stone")),
                ((1, 1, 1), bs("minecraft:redstone_wire")),
            ]
            .into_iter(),
        );
        let reverse = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((1, 1, 1), bs("minecraft:redstone_wire")),
                ((1, 1, 1), bs("minecraft:stone")),
            ]
            .into_iter(),
        );

        for (label, tile) in [("forward", &forward), ("reverse", &reverse)] {
            assert_eq!(tile.len(), 1, "{label}: one position, one cell");
            let got: Vec<_> = tile
                .blocks()
                .map(|(p, b)| (p, b.get_name().to_string()))
                .collect();
            assert_eq!(
                got,
                vec![((1, 1, 1), "minecraft:redstone_wire".to_string())],
                "{label}: the lexicographically smaller palette key must win"
            );
        }
    }

    #[test]
    fn the_palette_is_content_defined_not_insertion_ordered() {
        // A losing duplicate must not leave a phantom palette entry behind,
        // otherwise `palette_len` depends on input order even though `blocks`
        // does not.
        let forward = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((1, 1, 1), bs("minecraft:stone")),
                ((1, 1, 1), bs("minecraft:redstone_wire")),
            ]
            .into_iter(),
        );
        let reverse = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((1, 1, 1), bs("minecraft:redstone_wire")),
                ((1, 1, 1), bs("minecraft:stone")),
            ]
            .into_iter(),
        );
        assert_eq!(forward.palette_len(), 1, "the losing state is not retained");
        assert_eq!(forward.palette_len(), reverse.palette_len());
    }

    #[test]
    fn blocks_iterate_in_sorted_order_regardless_of_insertion_order() {
        let forward = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((1, 1, 1), bs("minecraft:stone")),
                ((2, 2, 2), bs("minecraft:dirt")),
                ((3, 3, 3), bs("minecraft:redstone_wire")),
            ]
            .into_iter(),
        );
        let reverse = VoxelTile::from_blocks(
            TileId { x: 0, z: 0 },
            bounds(),
            vec![
                ((3, 3, 3), bs("minecraft:redstone_wire")),
                ((2, 2, 2), bs("minecraft:dirt")),
                ((1, 1, 1), bs("minecraft:stone")),
            ]
            .into_iter(),
        );
        let f: Vec<_> = forward
            .blocks()
            .map(|(p, b)| (p, b.get_name().to_string()))
            .collect();
        let r: Vec<_> = reverse
            .blocks()
            .map(|(p, b)| (p, b.get_name().to_string()))
            .collect();
        assert_eq!(f, r, "iteration order must not depend on insertion order");
    }
}