miscellaneous_grids 2.1.0

use std::{
    hash::Hash,
    mem,
    ops::{Index, IndexMut},
};

use nalgebra::Point;

use crate::{TileIndex, TileIndexOffset, tile_rect::TileRect};

#[derive(Clone, Debug)]
pub struct TileGrid<T: Empty, const D: usize> {
    bounds: TileRect<D>,
    tiles: Box<[T]>,
}

pub trait Empty: Default + 'static {
    /// The value returned by this should match the value of default for this type.
    fn empty() -> &'static Self;

    fn is_empty(&self) -> bool;
}

impl<T: 'static> Empty for Option<T> {
    fn empty() -> &'static Self {
        &None
    }

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

impl<T: 'static> Empty for Vec<T> {
    fn empty() -> &'static Self {
        const { &Vec::new() }
    }

    fn is_empty(&self) -> bool {
        Vec::is_empty(self)
    }
}

impl Empty for bool {
    fn empty() -> &'static Self {
        &false
    }

    fn is_empty(&self) -> bool {
        !self
    }
}

impl<T: Empty, const D: usize> Default for TileGrid<T, D> {
    fn default() -> Self {
        Self {
            bounds: TileRect::default(),
            tiles: Box::new([]),
        }
    }
}

impl<T: Empty, const D: usize> Index<TileIndex<D>> for TileGrid<T, D> {
    type Output = T;

    fn index(&self, index: TileIndex<D>) -> &Self::Output {
        let Some(index) = self.linear_index_of(index) else {
            return T::empty();
        };

        &self.tiles[index]
    }
}

impl<T: Empty, const D: usize> IndexMut<TileIndex<D>> for TileGrid<T, D> {
    fn index_mut(&mut self, index: TileIndex<D>) -> &mut Self::Output {
        self.expand_to_fit_index(index);

        let index = self
            .linear_index_of(index)
            .expect("Tile index should be present");

        &mut self.tiles[index]
    }
}

impl<T: Empty, const D: usize> TileGrid<T, D> {
    pub fn from_slice(tiles: Box<[T]>, bounds: TileRect<D>) -> Option<Self> {
        (tiles.len() == bounds.area()).then_some(Self { bounds, tiles })
    }

    pub fn shift(&mut self, offset: TileIndexOffset<D>) {
        self.bounds.origin += offset;
    }

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

    pub fn into_slice(self) -> Box<[T]> {
        self.tiles
    }

    pub fn as_slice(&self) -> &[T] {
        &self.tiles
    }

    pub fn as_slice_mut(&mut self) -> &mut [T] {
        &mut self.tiles
    }

    fn linear_index_of(&self, index: TileIndex<D>) -> Option<usize> {
        if !self.bounds.contains_point(index) {
            return None;
        }

        let tile_offset = index - self.bounds.origin;

        let tile_offset = tile_offset.map(|x| x as usize);

        let mut acc = 1;

        Some((0..D).fold(0, |linear_index, axis| {
            let coefficient = acc;
            acc *= self.bounds.size[axis];
            linear_index + tile_offset[axis] * coefficient
        }))
    }

    /// Returns whether any expansion occurred
    pub fn expand_to_fit_index(&mut self, index: TileIndex<D>) -> bool {
        let mut bounds = self.bounds;
        let expanded = bounds.expand_to_include_index(index, self.bounds.size / 2);

        if expanded {
            self.set_bounds(bounds);
        }

        expanded
    }

    /// Returns whether any expansion occurred
    pub fn expand_to_fit_bounds(&mut self, new_bounds: TileRect<D>) -> bool {
        let mut bounds = self.bounds;
        let expanded = bounds.expand_to_include_bounds(new_bounds, self.bounds.size / 2);

        if expanded {
            self.set_bounds(bounds);
        }

        expanded
    }

    pub fn shrink_to_fit<const D_MINUS_ONE: usize>(&mut self) {
        const {
            assert!(D > 0);
            assert!(D - 1 == D_MINUS_ONE);
        }

        let mut new_bounds = self.bounds;

        'outer: for axis in 0..D {
            'inner: loop {
                if new_bounds.size[axis] == 0 {
                    continue 'outer;
                }

                let mut slice = Point::from([None; D]);
                slice[axis] = Some(new_bounds.max(axis));

                for index in self.bounds.slice_indexes::<D_MINUS_ONE>(slice) {
                    if !self[index].is_empty() {
                        break 'inner;
                    }
                }

                new_bounds.size[axis] -= 1;
            }

            'inner: loop {
                if new_bounds.size[axis] == 0 {
                    continue 'outer;
                }

                let mut slice = Point::from([None; D]);
                slice[axis] = Some(new_bounds.min(axis));

                for index in self.bounds.slice_indexes::<D_MINUS_ONE>(slice) {
                    if !self[index].is_empty() {
                        break 'inner;
                    }
                }

                new_bounds.size[axis] -= 1;
                new_bounds.origin[axis] += 1;
            }
        }

        self.set_bounds(new_bounds);
    }

    pub fn set_bounds(&mut self, bounds: TileRect<D>) {
        self.tiles = bounds
            .indexes()
            .map(|index| {
                if let Some(linear_index) = self.linear_index_of(index) {
                    mem::take(&mut self.tiles[linear_index])
                } else {
                    T::default()
                }
            })
            .collect();

        self.bounds = bounds;
    }

    pub fn get_disjoint_mut<const N: usize>(
        &mut self,
        indexes: [TileIndex<D>; N],
    ) -> Option<[&mut T; N]> {
        for &index in &indexes {
            self.expand_to_fit_index(index);
        }

        let linear_indexes = indexes.map(|index| {
            self.linear_index_of(index)
                .expect("Should have expanded to fit all indexes")
        });

        self.tiles.get_disjoint_mut(linear_indexes).ok()
    }
}

#[derive(Clone, Debug)]
pub struct IntoIter<T: Empty, const D: usize> {
    inner: TileGrid<T, D>,
    index: usize,
}

impl<T: Empty, const D: usize> Iterator for IntoIter<T, D> {
    type Item = (TileIndex<D>, T);

    fn next(&mut self) -> Option<Self::Item> {
        while self.inner.tiles.get(self.index)?.is_empty() {
            self.index += 1;
        }

        let tile_index = self
            .inner
            .bounds
            .linear_index_to_tile_index(self.index)
            .unwrap();

        let tile = mem::take(&mut self.inner.tiles[self.index]);
        self.index += 1;

        Some((tile_index, tile))
    }
}

impl<T: Empty, const D: usize> IntoIterator for TileGrid<T, D> {
    type Item = (TileIndex<D>, T);

    type IntoIter = IntoIter<T, D>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            inner: self,
            index: 0,
        }
    }
}

#[derive(Clone, Debug)]
pub struct Iter<'a, T: Empty, const D: usize> {
    bounds: TileRect<D>,
    tiles: &'a [T],
    index: usize,
}

impl<'a, T: Empty, const D: usize> Iterator for Iter<'a, T, D> {
    type Item = (TileIndex<D>, &'a T);

    fn next(&mut self) -> Option<Self::Item> {
        while self.tiles.first()?.is_empty() {
            self.tiles.split_off_first().unwrap();
            self.index += 1;
        }

        let tile_index = self.bounds.linear_index_to_tile_index(self.index).unwrap();
        let tile = self.tiles.split_off_first().unwrap();

        self.index += 1;

        Some((tile_index, tile))
    }
}

impl<T: Empty, const D: usize> TileGrid<T, D> {
    pub fn iter(&self) -> Iter<'_, T, D> {
        Iter {
            bounds: self.bounds,
            tiles: &self.tiles,
            index: 0,
        }
    }
}

impl<'a, T: Empty, const D: usize> IntoIterator for &'a TileGrid<T, D> {
    type Item = (TileIndex<D>, &'a T);

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

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

#[derive(Debug)]
pub struct IterMut<'a, T: Empty, const D: usize> {
    bounds: TileRect<D>,
    tiles: &'a mut [T],
    index: usize,
}

impl<'a, T: Empty, const D: usize> Iterator for IterMut<'a, T, D> {
    type Item = (TileIndex<D>, &'a mut T);

    fn next(&mut self) -> Option<Self::Item> {
        while self.tiles.first()?.is_empty() {
            self.tiles.split_off_first_mut().unwrap();
            self.index += 1;
        }

        let tile_index = self.bounds.linear_index_to_tile_index(self.index).unwrap();
        let tile = self.tiles.split_off_first_mut().unwrap();

        self.index += 1;

        Some((tile_index, tile))
    }
}

impl<T: Empty, const D: usize> TileGrid<T, D> {
    pub fn iter_mut(&mut self) -> IterMut<'_, T, D> {
        IterMut {
            bounds: self.bounds,
            tiles: &mut self.tiles,
            index: 0,
        }
    }
}

impl<'a, T: Empty, const D: usize> IntoIterator for &'a mut TileGrid<T, D> {
    type Item = (TileIndex<D>, &'a mut T);

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

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

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

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

impl<T: Empty + Eq, const D: usize> Eq for TileGrid<T, D> {}