miscellaneous_grids 2.1.0

use std::{hash::Hash, mem};

use nalgebra::SVector;

use crate::{
    TileIndex, TileIndexOffset,
    tile_grid::{self, Empty, TileGrid},
    tile_rect::TileRect,
};

#[derive(Clone, Debug)]
pub struct MultiTileGrid<T: Tile, S: TileShape<D>, const D: usize> {
    data: TileGrid<TileEntry<(T, S), D>, D>,
}

impl<T: Tile, S: TileShape<D>, const D: usize> Default for MultiTileGrid<T, S, D> {
    fn default() -> Self {
        Self {
            data: TileGrid::default(),
        }
    }
}

#[derive(Clone, Copy, Default, Debug)]
enum TileEntry<T, const D: usize> {
    #[default]
    Empty,
    Origin(T),
    Offset(SVector<i8, D>),
}

impl<T: 'static, const D: usize> Empty for TileEntry<T, D> {
    fn empty() -> &'static Self {
        &TileEntry::Empty
    }

    /// Returns `true` if the tile entry is [`Empty`].
    ///
    /// [`Empty`]: TileEntry::Empty
    fn is_empty(&self) -> bool {
        matches!(self, Self::Empty)
    }
}

impl<T, const D: usize> TileEntry<T, D> {
    fn offset(&self) -> Option<TileIndexOffset<D>> {
        match self {
            TileEntry::Empty => None,
            TileEntry::Origin(_) => Some([0; D].into()),
            TileEntry::Offset(offset) => Some(offset.map(isize::from)),
        }
    }
}

pub trait Tile: 'static {}

impl<T: 'static> Tile for T {}

pub trait TileShape<const D: usize>: 'static {
    /// Returned offsets must fit within a `Vector2<i8>`. Returning `[0, 0]` has no effect, as it
    /// is implied to be present no matter what is returned. Although the offsets do not need to be
    /// disjoint, returning fewer duplicates improves performance.
    fn offsets(&self) -> impl Iterator<Item = TileIndexOffset<D>>;

    fn bounds_hint(&self) -> Option<TileRect<D>> {
        None
    }
}

impl<T: Tile, S: TileShape<D>, const D: usize> MultiTileGrid<T, S, D> {
    pub fn shift(&mut self, offset: TileIndexOffset<D>) {
        self.data.shift(offset)
    }

    pub fn bounds(&self) -> TileRect<D> {
        self.data.bounds()
    }

    /// Returns whether or not any expansion occurred
    pub fn expand_to_fit_index(&mut self, index: TileIndex<D>) -> bool {
        self.data.expand_to_fit_index(index)
    }

    /// Returns whether or not any expansion occurred
    pub fn expand_to_fit_bounds(&mut self, new_bounds: TileRect<D>) -> bool {
        self.data.expand_to_fit_bounds(new_bounds)
    }

    pub fn offset_of(&self, index: TileIndex<D>) -> Option<TileIndexOffset<D>> {
        self.data[index].offset()
    }

    pub fn origin_of(&self, index: TileIndex<D>) -> Option<TileIndex<D>> {
        Some(index + self.offset_of(index)?)
    }

    pub fn get_tile(&self, index: TileIndex<D>) -> Option<IndexedTile<'_, T, S, D>> {
        if let Some(origin) = self.origin_of(index) {
            let TileEntry::Origin((tile, shape)) = &self.data[origin] else {
                unreachable!("Origin index should contain an origin entry")
            };

            Some(IndexedTile {
                tile,
                shape,
                origin,
            })
        } else {
            None
        }
    }

    pub fn get_tile_mut(&mut self, index: TileIndex<D>) -> Option<IndexedTileMut<'_, T, S, D>> {
        if let Some(origin) = self.origin_of(index) {
            let TileEntry::Origin((tile, shape)) = &mut self.data[origin] else {
                unreachable!("Origin index should contain an origin entry")
            };

            Some(IndexedTileMut {
                tile,
                shape,
                origin,
            })
        } else {
            None
        }
    }

    pub fn can_insert_tile(&self, origin: TileIndex<D>, shape: S) -> bool {
        for offset in shape.offsets().chain([[0; D].into()]) {
            let index = origin + offset;
            if !self.data[index].is_empty() {
                return false;
            }
        }

        true
    }

    pub fn insert_tile(
        &mut self,
        origin: TileIndex<D>,
        tile: T,
        shape: S,
    ) -> Result<(), TileInsertError<D>> {
        for offset in shape.offsets().chain([[0; D].into()]) {
            let index = origin + offset;
            if !self.data[index].is_empty() {
                return Err(TileInsertError::Overlap { conflict: index });
            }
        }

        unsafe { self.insert_tile_unchecked(origin, tile, shape) };

        Ok(())
    }

    pub fn insert_tile_overwriting(
        &mut self,
        origin: TileIndex<D>,
        tile: T,
        shape: S,
    ) -> Vec<RemovedTile<T, S, D>> {
        let mut removed_tiles = Vec::new();

        for offset in shape.offsets().chain([[0; D].into()]) {
            let index = origin + offset;
            if let Some(removed_tile) = self.remove_tile(index) {
                removed_tiles.push(removed_tile);
            }
        }

        unsafe { self.insert_tile_unchecked(origin, tile, shape) };

        removed_tiles
    }

    pub unsafe fn insert_tile_unchecked(&mut self, origin: TileIndex<D>, tile: T, shape: S) {
        if let Some(bounds) = shape.bounds_hint() {
            self.data
                .expand_to_fit_bounds(bounds.translate(origin.coords));
        }

        for offset in shape.offsets() {
            self.data[origin + offset] =
                TileEntry::Offset(-offset.map(|x| i8::try_from(x).expect("Shape is too big")));
        }

        self.data[origin] = TileEntry::Origin((tile, shape));
    }

    pub fn remove_tile(&mut self, index: TileIndex<D>) -> Option<RemovedTile<T, S, D>> {
        let origin = self.origin_of(index)?;

        let entry = mem::take(&mut self.data[origin]);

        let TileEntry::Origin((tile, shape)) = entry else {
            unreachable!("Origin index should contain an origin entry")
        };

        for offset in shape.offsets() {
            let index = origin + offset;
            self.data[index] = TileEntry::Empty;
        }

        Some(RemovedTile {
            tile,
            shape,
            origin,
        })
    }

    pub fn shrink_to_fit<const D_MINUS_ONE: usize>(&mut self) {
        self.data.shrink_to_fit::<D_MINUS_ONE>();
    }
}

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct RemovedTile<T: Tile, S: TileShape<D>, const D: usize> {
    pub tile: T,
    pub shape: S,
    pub origin: TileIndex<D>,
}

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct IndexedTile<'a, T: Tile, S: TileShape<D>, const D: usize> {
    pub tile: &'a T,
    pub shape: &'a S,
    pub origin: TileIndex<D>,
}

#[derive(PartialEq, Eq, Hash, Debug)]
pub struct IndexedTileMut<'a, T: Tile, S: TileShape<D>, const D: usize> {
    pub tile: &'a mut T,
    pub shape: &'a S,
    pub origin: TileIndex<D>,
}

#[derive(Clone, Copy, Debug)]
pub enum TileInsertError<const D: usize> {
    Overlap { conflict: TileIndex<D> },
}

#[derive(Clone, Debug)]
pub struct IntoIter<T: Tile, S: TileShape<D>, const D: usize> {
    inner: tile_grid::IntoIter<TileEntry<(T, S), D>, D>,
}

impl<T: Tile, S: TileShape<D>, const D: usize> Iterator for IntoIter<T, S, D> {
    type Item = RemovedTile<T, S, D>;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some((origin, entry)) = self.inner.next() {
            match entry {
                TileEntry::Origin((tile, shape)) => {
                    return Some(RemovedTile {
                        tile,
                        shape,
                        origin,
                    });
                }
                TileEntry::Empty | TileEntry::Offset(_) => (),
            }
        }

        None
    }
}

impl<T: Tile, S: TileShape<D>, const D: usize> IntoIterator for MultiTileGrid<T, S, D> {
    type Item = RemovedTile<T, S, D>;

    type IntoIter = IntoIter<T, S, D>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            inner: self.data.into_iter(),
        }
    }
}

#[derive(Clone, Debug)]
pub struct Iter<'a, T: Tile, S: TileShape<D>, const D: usize> {
    inner: tile_grid::Iter<'a, TileEntry<(T, S), D>, D>,
}

impl<'a, T: Tile, S: TileShape<D>, const D: usize> Iterator for Iter<'a, T, S, D> {
    type Item = IndexedTile<'a, T, S, D>;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some((origin, entry)) = self.inner.next() {
            match entry {
                TileEntry::Origin((tile, shape)) => {
                    return Some(IndexedTile {
                        tile,
                        shape,
                        origin,
                    });
                }
                TileEntry::Empty | TileEntry::Offset(_) => (),
            }
        }

        None
    }
}

impl<T: Tile, S: TileShape<D>, const D: usize> MultiTileGrid<T, S, D> {
    pub fn iter(&self) -> Iter<'_, T, S, D> {
        Iter {
            inner: self.data.iter(),
        }
    }
}

impl<'a, T: Tile, S: TileShape<D>, const D: usize> IntoIterator for &'a MultiTileGrid<T, S, D> {
    type Item = IndexedTile<'a, T, S, D>;

    type IntoIter = Iter<'a, T, S, D>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

#[derive(Debug)]
pub struct IterMut<'a, T: Tile, S: TileShape<D>, const D: usize> {
    inner: tile_grid::IterMut<'a, TileEntry<(T, S), D>, D>,
}

impl<'a, T: Tile, S: TileShape<D>, const D: usize> Iterator for IterMut<'a, T, S, D> {
    type Item = IndexedTileMut<'a, T, S, D>;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some((origin, entry)) = self.inner.next() {
            match entry {
                TileEntry::Origin((tile, shape)) => {
                    return Some(IndexedTileMut {
                        tile,
                        shape,
                        origin,
                    });
                }
                TileEntry::Empty | TileEntry::Offset(_) => (),
            }
        }

        None
    }
}

impl<T: Tile, S: TileShape<D>, const D: usize> MultiTileGrid<T, S, D> {
    pub fn iter_mut(&mut self) -> IterMut<'_, T, S, D> {
        IterMut {
            inner: self.data.iter_mut(),
        }
    }
}

impl<'a, T: Tile, S: TileShape<D>, const D: usize> IntoIterator for &'a mut MultiTileGrid<T, S, D> {
    type Item = IndexedTileMut<'a, T, S, D>;

    type IntoIter = IterMut<'a, T, S, D>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T: Tile + Hash, S: TileShape<D> + Hash, const D: usize> Hash for MultiTileGrid<T, S, D> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        for (i, tile) in self.iter().enumerate() {
            (i, tile).hash(state);
        }
    }
}

impl<T: Tile + Eq, S: TileShape<D> + Eq, const D: usize> PartialEq for MultiTileGrid<T, S, D> {
    fn eq(&self, other: &Self) -> bool {
        self.iter().zip(other.iter()).all(|(a, b)| a == b)
    }
}

impl<T: Tile + Eq, S: TileShape<D> + Eq, const D: usize> Eq for MultiTileGrid<T, S, D> {}