use fnv::FnvHasher;
use std::collections::HashMap;
use crate::math::{Point, Real, Vector, DIM};
use std::hash::BuildHasher;
#[derive(Copy, Clone, Debug)]
pub struct DeterministicState;
impl BuildHasher for DeterministicState {
type Hasher = FnvHasher;
fn build_hasher(&self) -> FnvHasher {
FnvHasher::with_key(1820)
}
}
#[derive(PartialEq, Debug, Clone)]
pub struct HGrid<T> {
cells: HashMap<Point<i64>, Vec<T>, DeterministicState>,
cell_width: Real,
}
impl<T> HGrid<T> {
pub fn new(cell_width: Real) -> Self {
Self {
cells: HashMap::with_hasher(DeterministicState),
cell_width,
}
}
pub fn cell_width(&self) -> Real {
self.cell_width
}
fn quantify(value: Real, cell_width: Real) -> i64 {
na::try_convert::<Real, f64>((value / cell_width).floor()).unwrap() as i64
}
fn quantify_ceil(value: Real, cell_width: Real) -> i64 {
na::try_convert::<Real, f64>((value / cell_width).ceil()).unwrap() as i64
}
pub fn key(&self, point: &Point<Real>) -> Point<i64> {
Point::from(point.coords.map(|e| Self::quantify(e, self.cell_width)))
}
pub fn clear(&mut self) {
self.cells.clear();
}
pub fn insert(&mut self, point: &Point<Real>, element: T) {
let key = self.key(point);
self.cells.entry(key).or_insert(Vec::new()).push(element)
}
pub fn cell_containing_point(&self, point: &Point<Real>) -> Option<&Vec<T>> {
let key = self.key(point);
self.cells.get(&key)
}
pub fn cells(&self) -> impl Iterator<Item = (&Point<i64>, &Vec<T>)> {
self.cells.iter()
}
pub fn inner_table(&self) -> &HashMap<Point<i64>, Vec<T>, DeterministicState> {
&self.cells
}
pub fn cell(&self, key: &Point<i64>) -> Option<&Vec<T>> {
self.cells.get(key)
}
pub fn neighbor_cells(
&self,
cell: &Point<i64>,
radius: Real,
) -> impl Iterator<Item = (Point<i64>, &Vec<T>)> {
let cells = &self.cells;
let quantified_radius = Self::quantify_ceil(radius, self.cell_width);
CellRangeIterator::with_center(*cell, quantified_radius)
.filter_map(move |cell| cells.get(&cell).map(|c| (cell, c)))
}
pub fn cells_intersecting_aabb(
&self,
mins: &Point<Real>,
maxs: &Point<Real>,
) -> impl Iterator<Item = (Point<i64>, &Vec<T>)> {
let cells = &self.cells;
let start = self.key(mins);
let end = self.key(maxs);
CellRangeIterator::new(start, end)
.filter_map(move |cell| cells.get(&cell).map(|c| (cell, c)))
}
}
struct CellRangeIterator {
start: Point<i64>,
end: Point<i64>,
curr: Point<i64>,
done: bool,
}
impl CellRangeIterator {
fn new(start: Point<i64>, end: Point<i64>) -> Self {
Self {
start,
end,
curr: start,
done: false,
}
}
fn with_center(center: Point<i64>, radius: i64) -> Self {
let start = center - Vector::repeat(radius as i64);
Self {
start,
end: center + Vector::repeat(radius as i64),
curr: start,
done: false,
}
}
}
impl Iterator for CellRangeIterator {
type Item = Point<i64>;
fn next(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
if self.curr == self.end {
self.done = true;
Some(self.curr)
} else {
let result = self.curr;
for i in 0..DIM {
self.curr[i] += 1;
if self.curr[i] > self.end[i] {
self.curr[i] = self.start[i];
} else {
break;
}
}
Some(result)
}
}
}
#[cfg(test)]
mod test {
#[test]
#[cfg(feature = "dim2")]
fn grid_neighbor_iterator() {
use super::CellRangeIterator;
use crate::math::Point;
let expected = [
Point::new(-1, 0),
Point::new(0, 0),
Point::new(1, 0),
Point::new(2, 0),
Point::new(3, 0),
Point::new(-1, 1),
Point::new(0, 1),
Point::new(1, 1),
Point::new(2, 1),
Point::new(3, 1),
Point::new(-1, 2),
Point::new(0, 2),
Point::new(1, 2),
Point::new(2, 2),
Point::new(3, 2),
Point::new(-1, 3),
Point::new(0, 3),
Point::new(1, 3),
Point::new(2, 3),
Point::new(3, 3),
];
let iter = CellRangeIterator::with_center(Point::new(1, 2), 2);
assert!(iter.zip(expected.into_iter()).all(|(a, b)| a == *b))
}
}