Struct VecCell 

pub struct VecCell<K, const D: usize>
where
    K: Eq + Hash,
{ /* private fields */ }

Bucket sort points into cubes with Vec-backed storage

VecCell is a spatial data structure that can efficiently update one point at a time (see PointUpdate) and find all points that are near a position in space (see PointsNearBall).

Points are stored in VecCell by key. The caller can choose a generic key type K appropriately. For example, K could be usize and map to an array index. Or it could be an enum that distinguishes between primary and ghost site positions.

Internally, VecCell stores a D-dimensional vector of cells that partition space. Each bucket is a hypercube with an edge length equal to the nominal search radius. When searching for points near a position in space, VecCell first determines which bucket that point is in. Then it iterates over all the keys in all the cells within the given search radius. To perform this iteration efficiently, VecCell pre-computes a set of stencils up to the given maximum search radius given at const

In systems with low density fluctuations, the time complexity of VecCell is O(1). More generally, and important when density fluctuations are present, the time complexity scales with the maximum number of points in any of the cells.

VecCell performs best when the search radius is equal to the nominal search radius. In that case, 2D searches loop over 9 cells and 3D searches loop over 27. The caller must filter the output of this iteration because the resulting hypercube covers more volume than the given hypersphere. When searching with a radius larger than the nominal, many more cells must be iterated leading to slower performance. At the same time, the stencil covers less excess volume and therefore fewer points must be filtered.

VecCell stores each cell at a unique index backed by storage in Vec. This performs very well in dense, compact systems. However, the memory utilization scales with the volume of the cube that spans from the most negative point to the most positive point. In dilute systems, VecCell can therefore waste a lot of memory storing empty cells. Use HashCell and occasionally call its shrink_to_fit method to limit the memory required to model dilute systems.

Examples

The default VecCell set both the nominal and maximum search radii to 1.0.

use hoomd_spatial::VecCell;

let vec_cell = VecCell::<usize, 3>::default();

Use the builder API to set any or all parameters:

use hoomd_spatial::VecCell;

let vec_cell = VecCell::<usize, 3>::builder()
    .nominal_search_radius(2.5.try_into()?)
    .maximum_search_radius(7.5)
    .build();

Implementations

impl<K, const D: usize> VecCell<K, D>

where K: Copy + Eq + Hash,

pub fn builder() -> VecCellBuilder<K, D>

Construct a VecCell builder.

Use the builder to set any or all parameters and construct a VecCell.

Example

use hoomd_spatial::VecCell;

let vec_cell = VecCell::<usize, 3>::builder()
    .nominal_search_radius(2.5.try_into()?)
    .maximum_search_radius(7.5)
    .build();

pub fn shrink_to_fit(&mut self)

Remove excess capacity from dynamically allocated arrays.

At this time, shrink_to_fit only reduces the memory utilized by the cell contents. It does not shrink the D-dimensional storage to match the range spanned by points currently in the data structure.

Trait Implementations

impl<K, const D: usize> Clone for VecCell<K, D>

where K: Eq + Hash + Clone,

fn clone(&self) -> VecCell<K, D>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K, const D: usize> Debug for VecCell<K, D>

where K: Eq + Hash + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, const D: usize> Default for VecCell<K, D>

where K: Copy + Eq + Hash,

fn default() -> Self

Construct a default VecCell.

The default sets both the nominal and maximum search radii to 1.0.

Example

use hoomd_spatial::VecCell;

let vec_cell = VecCell::<usize, 3>::default();

impl<'de, K, const D: usize> Deserialize<'de> for VecCell<K, D>

where K: Eq + Hash + Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, const D: usize> Display for VecCell<K, D>

where K: Eq + Hash,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Summarize the contents of the cell list.

This is a slow operation. It is meant to be printed to logs only occasionally, such as at the end of a benchmark or simulation.

Example

use hoomd_spatial::VecCell;
use log::info;

let vec_cell = VecCell::<usize, 3>::default();

info!("{vec_cell}");

impl<K, const D: usize> IndexFromPosition<Cartesian<D>> for VecCell<K, D>

where K: Eq + Hash,

type Location = [i64; D]

Orderable type based on the site’s position.

fn location_from_position(&self, position: &Cartesian<D>) -> Self::Location

Determine the location of a site based on its position.

impl<K, const D: usize> PointUpdate<Cartesian<D>, K> for VecCell<K, D>

where K: Copy + Eq + Hash,

fn insert(&mut self, key: K, position: Cartesian<D>)

Insert or update a point identified by a key.

Example

use hoomd_spatial::{PointUpdate, VecCell};

let mut vec_cell = VecCell::default();

vec_cell.insert(0, [1.25, 2.5].into());

fn remove(&mut self, key: &K)

Remove the point with the given key.

Example

use hoomd_spatial::{PointUpdate, VecCell};

let mut vec_cell = VecCell::default();
vec_cell.insert(0, [1.25, 2.5].into());

vec_cell.remove(&0)

fn len(&self) -> usize

Get the number of points in the spatial data structure.

Example

use hoomd_spatial::{PointUpdate, VecCell};

let mut vec_cell = VecCell::default();
vec_cell.insert(0, [1.25, 2.5].into());

assert_eq!(vec_cell.len(), 1)

fn is_empty(&self) -> bool

Test if the spatial data structure is empty.

Example

use hoomd_spatial::{PointUpdate, VecCell};

let mut vec_cell = VecCell::<usize, 2>::default();

assert!(vec_cell.is_empty());

fn contains_key(&self, key: &K) -> bool

Test if the spatial data structure contains a key.

use hoomd_spatial::{PointUpdate, VecCell};

let mut vec_cell = VecCell::default();
vec_cell.insert(0, [1.25, 2.5].into());

assert!(vec_cell.contains_key(&0));

fn clear(&mut self)

Remove all points.

Example

use hoomd_spatial::{PointUpdate, VecCell};

let mut vec_cell = VecCell::default();
vec_cell.insert(0, [1.25, 2.5].into());

vec_cell.clear();

impl<const D: usize, K> PointsNearBall<Cartesian<D>, K> for VecCell<K, D>

where K: Copy + Eq + Hash,

fn points_near_ball( &self, position: &Cartesian<D>, radius: f64, ) -> impl Iterator<Item = K>

Find all the points that might be in the given ball.

points_near_ball will iterate over all points in the given ball and possibly others as well. VecCell may iterate over the points in any order.

Example

use hoomd_spatial::{PointUpdate, PointsNearBall, VecCell};

let mut vec_cell = VecCell::default();
vec_cell.insert(0, [1.25, 0.0].into());
vec_cell.insert(1, [3.25, 0.75].into());
vec_cell.insert(2, [-10.0, 12.0].into());

for key in vec_cell.points_near_ball(&[2.0, 0.0].into(), 1.0) {
    println!("{key}");
}

Prints (in any order):

0
1

Panics

Panics when radius is larger than the maximum search radius provided at construction, rounded up to the nearest integer multiple of the nominal search radius.

fn is_all_pairs() -> bool

Is this spatial data structures AllPairs?

impl<K, const D: usize> Serialize for VecCell<K, D>

where K: Eq + Hash + Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<K, const D: usize> WithSearchRadius for VecCell<K, D>

where K: Copy + Eq + Hash,

fn with_search_radius(radius: PositiveReal) -> Self

Construct a VecCell with the given search radius.

Set both the nominal and maximum search radii to radius.

Example

use hoomd_spatial::{VecCell, WithSearchRadius};

let vec_cell = VecCell::<usize, 3>::with_search_radius(2.5.try_into()?);