Struct MultiIndexed 

pub struct MultiIndexed<const K: usize, V> {
    trie: KdTrie<V>,
    min_coords: [AtomicI32; K],
    max_coords: [AtomicI32; K],
}

A multi-dimensional array that allows efficient storage and retrieval of values using K-dimensional integer coordinates.

MultiIndexed<K, V> provides a thread-safe and wait-free way to store values indexed by multi-dimensional coordinates. It is implemented using a K-dimensional trie structure that efficiently handles sparse data, where each level of the trie corresponds to one dimension of the coordinate space.

The MultiIndexed is created with a fixed number of dimensions K and can store values of any type V. Each dimension can have both positive and negative indices.

Thread Safety

MultiIndexed is designed to be thread-safe and wait-free, allowing concurrent insertions and retrievals from multiple threads. This makes it suitable for parallel algorithms that need to build up a shared data structure.

Memory Efficiency

The underlying trie structure allocates memory only for coordinates that are actually used, making it memory-efficient for sparse data. The implementation uses a series of TwoEndedGrove instances to store the trie nodes, which themselves use a block-based allocation strategy.

Performance Characteristics

• Insertion: O(K) time complexity,
• Retrieval: O(K) time complexity,
• Memory Usage: amortized O(N) space complexity, where N is the number of inserted elements

Note

Inserting a value at a coordinate that is already occupied will panic. Values can be mutated in place through exclusive (&mut) references via get_mut or IndexMut. However, while insertion only requires a shared reference, concurrent mutation is not supported.

For performance reasons, we do not allow K = 0.

Examples

Correct usage:

use once::MultiIndexed;

// Create a 3-dimensional array
let array = MultiIndexed::<3, i32>::new();

// Insert values at specific coordinates
array.insert([1, 2, 3], 42);
array.insert([5, 0, 2], 100);
array.insert([-1, -2, 3], 200); // Negative coordinates are supported

// Retrieve values
assert_eq!(array.get([1, 2, 3]), Some(&42));
assert_eq!(array.get([5, 0, 2]), Some(&100));
assert_eq!(array.get([-1, -2, 3]), Some(&200));
assert_eq!(array.get([0, 0, 0]), None); // No value at these coordinates

Incorrect usage:

use once::MultiIndexed;

let array = MultiIndexed::<2, i32>::new();

array.insert([1, 2], 42);
array.insert([1, 2], 43); // Panics because the value at [1, 2] is already set

use once::MultiIndexed;

let incorrect = MultiIndexed::<0, ()>::new();

Fields

trie: KdTrie<V>

min_coords: [AtomicI32; K]

max_coords: [AtomicI32; K]

Implementations

impl<const K: usize, V> MultiIndexed<K, V>

pub fn iter(&self) -> Iter<'_, V, [i32; K]>

Returns an iterator over all coordinate-value pairs in the array.

The iterator yields ([i32; K], &V) tuples in lexicographic order of coordinates.

Examples

use once::MultiIndexed;

let array = MultiIndexed::<2, i32>::new();
array.insert([3, 4], 10);
array.insert([1, 2], 20);

let mut items: Vec<_> = array.iter().collect();

assert_eq!(items, vec![([1, 2], &20), ([3, 4], &10)]);

pub fn iter_mut(&mut self) -> IterMut<'_, V, [i32; K]>

Returns a mutable iterator over all coordinate-value pairs in the array.

The iterator yields ([i32; K], &mut V) tuples in lexicographic order of coordinates.

Examples

use once::MultiIndexed;

let mut array = MultiIndexed::<2, i32>::new();
array.insert([1, 2], 10);
array.insert([3, 4], 20);

for (_, v) in array.iter_mut() {
    *v *= 2;
}

assert_eq!(array.get([1, 2]), Some(&20));
assert_eq!(array.get([3, 4]), Some(&40));

impl<const K: usize, V> MultiIndexed<K, V>

const POSITIVE_DIMS: ()

pub fn new() -> Self

Creates a new empty MultiIndexed array with K dimensions.

Examples

use once::MultiIndexed;

// Create a 2D array for strings
let array = MultiIndexed::<2, String>::new();

// Create a 3D array for integers
let array3d = MultiIndexed::<3, i32>::new();

// Create a 4D array for custom types
struct Point {
    x: f64,
    y: f64,
}
let array4d = MultiIndexed::<4, Point>::new();

pub fn get(&self, coords: impl Into<[i32; K]>) -> Option<&V>

Retrieves a reference to the value at the specified coordinates, if it exists.

Parameters

• coords: An array of K integer coordinates

Returns

• Some(&V) if a value exists at the specified coordinates
• None if no value exists at the specified coordinates

Examples

use once::MultiIndexed;

// Basic retrieval in a 3D array
let array = MultiIndexed::<3, i32>::new();
array.insert([1, 2, 3], 42);

assert_eq!(array.get([1, 2, 3]), Some(&42));
assert_eq!(array.get([0, 0, 0]), None);

// Retrieval with negative coordinates
array.insert([-5, -10, 15], 100);
assert_eq!(array.get([-5, -10, 15]), Some(&100));

// Retrieval in a 2D array
let array2d = MultiIndexed::<2, String>::new();
array2d.insert([0, 0], "Origin".to_string());
array2d.insert([10, -5], "Far point".to_string());

assert_eq!(array2d.get([0, 0]), Some(&"Origin".to_string()));
assert_eq!(array2d.get([10, -5]), Some(&"Far point".to_string()));
assert_eq!(array2d.get([1, 1]), None);

// Retrieval in a 1D array
let array1d = MultiIndexed::<1, f64>::new();
array1d.insert([0], 3.14);
array1d.insert([-10], -2.71);

assert_eq!(array1d.get([0]), Some(&3.14));
assert_eq!(array1d.get([-10]), Some(&-2.71));
assert_eq!(array1d.get([5]), None);

pub fn get_mut(&mut self, coords: impl Into<[i32; K]>) -> Option<&mut V>

Retrieves a mutable reference to the value at the specified coordinates, if it exists.

This method can only be called if we have an exclusive reference to self. Having an exclusive reference prevents concurrent access, so the atomic synchronization used by get is unnecessary. This makes it safe to return a mutable reference to the stored value.

Parameters

• coords: An array of K integer coordinates

Returns

• Some(&mut V) if a value exists at the specified coordinates
• None if no value exists at the specified coordinates

Examples

use once::MultiIndexed;

let mut array = MultiIndexed::<3, Vec<i32>>::new();
array.insert([1, 2, 3], vec![1, 2, 3]);
array.insert([4, 5, 6], vec![4, 5, 6]);

// Modify the vectors in place
if let Some(vec) = array.get_mut([1, 2, 3]) {
    vec.push(4);
    vec.push(5);
}

assert_eq!(array.get([1, 2, 3]), Some(&vec![1, 2, 3, 4, 5]));

pub fn insert(&self, coords: impl Into<[i32; K]>, value: V)

Inserts a value at the specified coordinates.

This operation is thread-safe and can be called from multiple threads. However, this method panics if a value already exists at the specified coordinates. Therefore, it should only be called at most once for any given set of coordinates.

Parameters

• coords: An array of K integer coordinates
• value: The value to insert at the specified coordinates

Examples

use once::MultiIndexed;

// Basic insertion in a 3D array
let array = MultiIndexed::<3, i32>::new();
array.insert([1, 2, 3], 42);

// Insertion with negative coordinates
array.insert([-5, 0, 10], 100);
array.insert([0, -3, -7], 200);

// Insertion in a 2D array
let array2d = MultiIndexed::<2, String>::new();
array2d.insert([0, 0], "Origin".to_string());
array2d.insert([10, -5], "Far point".to_string());

// Insertion in a 1D array
let array1d = MultiIndexed::<1, f64>::new();
array1d.insert([0], 3.14);
array1d.insert([-10], -2.71);

Panics

This method will panic if a value already exists at the specified coordinates:

use once::MultiIndexed;

let array = MultiIndexed::<2, i32>::new();
array.insert([1, 2], 42);
array.insert([1, 2], 43); // Panics

pub fn try_insert(&self, coords: impl Into<[i32; K]>, value: V) -> Result<(), V>

fn update_bounds(&self, coords: &[i32; K])

pub fn is_empty(&self) -> bool

Returns true if no values have been inserted.

The bounds are loaded with Relaxed ordering, then a single Acquire fence synchronizes with the Release stores in update_bounds. This is cheaper than per-load Acquire and is sufficient: once the fence executes, all prior Release stores (across every dimension) are visible.

pub fn min_coords(&self) -> Option<[i32; K]>

Returns the per-dimension minimum coordinates, or None if empty.

The Acquire fence in is_empty synchronizes with the Release stores in update_bounds, so subsequent Relaxed loads on the remaining dimensions see consistent values.

pub fn max_coords(&self) -> Option<[i32; K]>

Returns the per-dimension maximum coordinates, or None if empty.

The Acquire fence in is_empty synchronizes with the Release stores in update_bounds, so subsequent Relaxed loads on the remaining dimensions see consistent values.

Trait Implementations

impl<const K: usize, V> Clone for MultiIndexed<K, V>

where V: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<const K: usize, V: Debug> Debug for MultiIndexed<K, V>

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

Formats the value using the given formatter.

impl<const K: usize, V> Default for MultiIndexed<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<const K: usize, V: Hash> Hash for MultiIndexed<K, V>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<const K: usize, V, I: Into<[i32; K]>> Index<I> for MultiIndexed<K, V>

type Output = V

The returned type after indexing.

fn index(&self, index: I) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<const K: usize, V, I: Into<[i32; K]>> IndexMut<I> for MultiIndexed<K, V>

fn index_mut(&mut self, index: I) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, const K: usize, V> IntoIterator for &'a MultiIndexed<K, V>

type IntoIter = Iter<'a, V, [i32; K]>

Which kind of iterator are we turning this into?

type Item = ([i32; K], &'a V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, const K: usize, V> IntoIterator for &'a mut MultiIndexed<K, V>

type IntoIter = IterMut<'a, V, [i32; K]>

Which kind of iterator are we turning this into?

type Item = ([i32; K], &'a mut V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<const K: usize, V> PartialEq for MultiIndexed<K, V>

where V: PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<const K: usize, V> Eq for MultiIndexed<K, V>

where V: Eq,