hashgrid 0.1.0

//! A 2D spatial-hash grid library
//!
//! # Type-Naming Convention
//!
//! - A: The coordinate type.
//! - T: The hashable identifier type, defaults to `u32`.
//! - S: The size of the hash table.

pub mod hash;
pub mod mapper;
pub mod range;
pub mod table;

use std::{
    hash::{BuildHasherDefault, Hash, Hasher},
    ops::RangeInclusive,
};

use smallvec::SmallVec;

use crate::{
    hash::{DummyHasher, MortonHasher},
    mapper::Mapper,
    table::Table,
};

/// A hash wrapper that only hashes the elements of the vector,
/// but does not hash the length prefix (See [Hasher::write_length_prefix]).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Vector<A>([A; 2]);

impl<A: Hash> Hash for Vector<A> {
    #[inline(always)]
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0[0].hash(state);
        self.0[1].hash(state);
    }
}

pub trait IntoCellIter<A>
where
    Self: Copy,
{
    fn iter_cells(self) -> impl Iterator<Item = [A; 2]>;
}

impl<I: IntoIterator<Item = [A; 2]> + Copy, A> IntoCellIter<A> for I {
    fn iter_cells(self) -> impl Iterator<Item = [A; 2]> {
        self.into_iter()
    }
}

#[derive(Debug, Clone)]
pub struct Entry<T, const S: usize>(pub SmallVec<[T; S]>);

impl<T, const S: usize> Default for Entry<T, S> {
    fn default() -> Self {
        Self(SmallVec::new())
    }
}

/// Default vector length per cell. It is recommended to keep this value low to avoid excessive memory usage.
const DEFAULT_S_CELLS: usize = 4;
/// Default vector length per map. It is recommended to keep this value low to avoid excessive memory usage.
const DEFAULT_S_MAPS: usize = 4;

#[derive(Debug, Clone)]
pub struct Grid<
    T,
    A,
    M: Mapper<T, A>,
    const S_CELLS: usize = DEFAULT_S_CELLS,
    const S_MAPS: usize = DEFAULT_S_MAPS,
> {
    cells: Table<Entry<T, S_CELLS>, BuildHasherDefault<MortonHasher>>,
    maps: Table<Entry<M::Entry, S_MAPS>, BuildHasherDefault<DummyHasher>>,
}

impl<T, A, M: Mapper<T, A>, const S_CELLS: usize, const S_MAPS: usize>
    Grid<T, A, M, S_CELLS, S_MAPS>
{
    pub fn with_capacity(cell: usize, map: usize) -> Self {
        Grid {
            cells: Table::with_capacity(cell),
            maps: Table::with_capacity(map),
        }
    }
}

impl<T, A, M: Mapper<T, A>, const S_CELLS: usize, const S_MAPS: usize>
    Grid<T, A, M, S_CELLS, S_MAPS>
{
    /// # SAFETY
    /// You MUST NOT modify the table structure if you are not sure what you are doing.
    pub unsafe fn inner_cells(
        &mut self,
    ) -> &mut Table<Entry<T, S_CELLS>, BuildHasherDefault<MortonHasher>> {
        &mut self.cells
    }

    /// # SAFETY
    /// You MUST NOT modify the table structure if you are not sure what you are doing.
    pub unsafe fn inner_maps(
        &mut self,
    ) -> &mut Table<Entry<M::Entry, S_MAPS>, BuildHasherDefault<DummyHasher>> {
        &mut self.maps
    }
}

impl<T, A, M: Mapper<T, A>, const S_CELLS: usize, const S_MAPS: usize>
    Grid<T, A, M, S_CELLS, S_MAPS>
where
    T: Copy + Hash + Eq,
    A: Copy + Hash + Eq,
    RangeInclusive<A>: Iterator<Item = A>,
{
    pub fn insert(&mut self, key: T, entity: M::Input) {
        let map = self.maps.get_hash_mut(&key);
        let cells = M::insert(&mut map.0, key, entity);

        for coord in cells.iter_cells() {
            let cell = self.cells.get_hash_mut(&Vector(coord));
            cell.0.push(key);
        }
    }

    pub fn remove(&mut self, key: &T) -> Option<()> {
        let map = self.maps.get_hash_mut(&key);
        let cells = M::remove(&mut map.0, key)?.iter_cells();

        for coord in cells {
            let cell = self.cells.get_hash_mut(&Vector(coord));
            // SAFETY: the key must be in the cell.
            let index = unsafe { cell.0.iter().position(|v| v == key).unwrap_unchecked() };
            cell.0.remove(index);
        }

        Some(())
    }

    /// Query the grid for entities within a range.
    ///
    /// This method does not check for duplicates caused by hash-collisions,
    /// or [Mapper]'s presentation (e.g. multi-cell item of [RangeMapper]).
    pub fn query(&self, range: impl IntoCellIter<A>) -> impl Iterator<Item = T> {
        range
            .iter_cells()
            .flat_map(|coord| self.cells.get_hash(&Vector(coord)).0.iter().copied())
    }

    pub fn clear(&mut self) {
        for cell in self.cells.inner_mut() {
            cell.0.clear();
        }
        for map in self.maps.inner_mut() {
            map.0.clear();
        }
    }
}