miscellaneous_grids 0.9.0

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

use nalgebra::{Vector2, point, vector};

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

#[derive(Clone, Debug)]
pub struct TileGrid<T: Empty> {
    bounds: TileRect,
    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> Default for TileGrid<T> {
    fn default() -> Self {
        Self {
            bounds: TileRect::default(),
            tiles: Box::new([]),
        }
    }
}

impl<T: Empty> Index<TileIndex> for TileGrid<T> {
    type Output = T;

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

        &self.tiles[index]
    }
}

impl<T: Empty> IndexMut<TileIndex> for TileGrid<T> {
    fn index_mut(&mut self, index: TileIndex) -> &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> TileGrid<T> {
    pub fn shift(&mut self, offset: TileIndexOffset) {
        self.bounds.origin += offset;
    }

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

    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) -> Option<usize> {
        let tile_offset = index - self.bounds.origin;
        let tile_offset = vector![
            usize::try_from(tile_offset.x).ok()?,
            usize::try_from(tile_offset.y).ok()?,
        ];

        (tile_offset.x < self.bounds.size.x && tile_offset.y < self.bounds.size.y)
            .then(|| tile_offset.x + tile_offset.y * self.bounds.size.x)
    }

    /// Returns whether or not any expansion occurred
    pub fn expand_to_fit_index(&mut self, index: TileIndex) -> 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 or not any expansion occurred
    pub fn expand_to_fit_bounds(&mut self, new_bounds: TileRect) -> 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(&mut self) {
        let mut new_bounds = self.bounds;

        // Shrink from right
        'outer: loop {
            let x = new_bounds.right();

            if new_bounds.size.x == 0 {
                break;
            }

            for y in self.bounds.top()..self.bounds.bottom() + 1 {
                if !self[point![x, y]].is_empty() {
                    break 'outer;
                }
            }

            new_bounds.size.x -= 1;
        }

        // Shrink from bottom
        'outer: loop {
            let y = new_bounds.bottom();

            if new_bounds.size.y == 0 {
                break;
            }

            for x in self.bounds.left()..self.bounds.right() + 1 {
                if !self[point![x, y]].is_empty() {
                    break 'outer;
                }
            }

            new_bounds.size.y -= 1;
        }

        // Shrink from left
        'outer: loop {
            let x = new_bounds.left();

            if new_bounds.size.x == 0 {
                break;
            }

            for y in self.bounds.top()..self.bounds.bottom() + 1 {
                if !self[point![x, y]].is_empty() {
                    break 'outer;
                }
            }

            new_bounds.size.x -= 1;
            new_bounds.origin.x += 1;
        }

        // Shrink from top
        'outer: loop {
            let y = new_bounds.top();

            if new_bounds.size.y == 0 {
                break;
            }

            for x in self.bounds.left()..self.bounds.right() + 1 {
                if !self[point![x, y]].is_empty() {
                    break 'outer;
                }
            }

            new_bounds.size.y -= 1;
            new_bounds.origin.y += 1;
        }

        self.set_bounds(new_bounds);
    }

    pub fn set_bounds(&mut self, bounds: TileRect) {
        let offset = bounds.origin - self.bounds.origin;

        self.tiles = (0..bounds.area())
            .map(|i| {
                let new_index = vector![i % bounds.size.x, i / bounds.size.x,];
                let old_index =
                    Vector2::from_fn(|i, _| new_index[i].wrapping_add_signed(offset[i]));

                if old_index.x < self.bounds.size.x && old_index.y < self.bounds.size.y {
                    mem::take(&mut self.tiles[old_index.x + old_index.y * self.bounds.size.x])
                } else {
                    T::default()
                }
            })
            .collect();

        self.bounds = bounds;
    }

    pub fn get_disjoint_mut<const N: usize>(
        &mut self,
        indexes: [TileIndex; 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> {
    inner: TileGrid<T>,
    index: usize,
}

impl<T: Empty> Iterator for IntoIter<T> {
    type Item = (TileIndex, 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> IntoIterator for TileGrid<T> {
    type Item = (TileIndex, T);

    type IntoIter = IntoIter<T>;

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

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

impl<'a, T: Empty> Iterator for Iter<'a, T> {
    type Item = (TileIndex, &'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> TileGrid<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            bounds: self.bounds,
            tiles: &self.tiles,
            index: 0,
        }
    }
}

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

    type IntoIter = Iter<'a, T>;

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

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

impl<'a, T: Empty> Iterator for IterMut<'a, T> {
    type Item = (TileIndex, &'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> TileGrid<T> {
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            bounds: self.bounds,
            tiles: &mut self.tiles,
            index: 0,
        }
    }
}

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

    type IntoIter = IterMut<'a, T>;

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

impl<T: Empty + Hash> Hash for TileGrid<T> {
    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> PartialEq for TileGrid<T> {
    fn eq(&self, other: &Self) -> bool {
        self.iter().zip(other.iter()).all(|(a, b)| a == b)
    }
}

impl<T: Empty + Eq> Eq for TileGrid<T> {}