Struct KdTrie 

pub struct KdTrie<V> {
    root: Node<V>,
    dimensions: usize,
}

A K-dimensional trie data structure that efficiently stores values indexed by multi-dimensional coordinates.

The difference between KdTrie and MultiIndexed is that the latter has the dimension as part of the type, which allows for more type safety. The KdTrie itself may be useful in a situation where the dimension is not known at compile time.

The trie is structured as a tree where each level corresponds to one dimension of the coordinate space. For example, in a 3D trie, the first level corresponds to the x-coordinate, the second level to the y-coordinate, and the third level to the z-coordinate. This structure allows for efficient storage and retrieval of values in a sparse coordinate space.

Thread Safety

KdTrie is designed to be thread-safe and wait-free, allowing concurrent insertions and retrievals from multiple threads. This is achieved through the use of atomic operations and the thread-safe properties of the underlying TwoEndedGrove data structure.

Memory Efficiency

The trie only allocates memory for coordinates that are actually used, making it memory-efficient for sparse data. Each node in the trie is either an inner node (which contains child nodes) or a leaf node (which contains values).

Type Parameters

• V: The type of values stored in the trie

Fields

root: Node<V>

dimensions: usize

Implementations

impl<V> KdTrie<V>

pub fn iter(&self) -> Iter<'_, V, Vec<i32>>

pub fn iter_mut(&mut self) -> IterMut<'_, V, Vec<i32>>

impl<V> KdTrie<V>

pub fn new(dimensions: usize) -> Self

Creates a new KdTrie with the specified number of dimensions.

Parameters

• dimensions: The number of dimensions for the trie (must be greater than 0)

Panics

Panics if dimensions is 0.

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

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

Parameters

• coords: A slice of coordinates with length equal to self.dimensions

Returns

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

Panics

Panics if the length of coords does not match the number of dimensions.

pub fn insert(&self, coords: &[i32], value: V)

Inserts a value at the specified coordinates.

This method traverses the trie structure to find the appropriate location for the value, creating nodes as needed along the way.

Parameters

• coords: A slice of coordinates with length equal to self.dimensions
• value: The value to insert at the specified coordinates

Panics

Panics if the length of coords does not match the number of dimensions.

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

Attempts to insert a value at the specified coordinates.

This method traverses the trie structure to find the appropriate location for the value, creating nodes as needed along the way.

This method will only insert the value if the coordinate is not already occupied. If the coordinate is already occupied, the value is returned in the Err variant.

Parameters

• coords: A slice of coordinates with length equal to self.dimensions
• value: The value to insert at the specified coordinates

Returns

• Ok(()) if the value was successfully inserted
• Err(value) if the coordinate was already occupied, returning the value that we tried to insert

Panics

Panics if the length of coords does not match the number of dimensions.

Examples

use once::multiindexed::KdTrie;

let trie = KdTrie::<i32>::new(2);

assert_eq!(trie.try_insert(&[-3, 1], 10), Ok(()));
assert_eq!(trie.try_insert(&[-3, 1], 10), Err(10)); // Coordinate already occupied

pub fn get_mut(&mut self, coords: &[i32]) -> 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. When you have exclusive access, there’s no possibility of concurrent access, so the atomic synchronization used by get is unnecessary.

Parameters

• coords: A slice of coordinates with length equal to self.dimensions

Returns

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

Panics

Panics if the length of coords does not match the number of dimensions.

Examples

use once::multiindexed::KdTrie;

let mut trie = KdTrie::<i32>::new(2);
trie.insert(&[1, 2], 42);

// Modify the value through a mutable reference
if let Some(value) = trie.get_mut(&[1, 2]) {
    *value = 100;
}

assert_eq!(trie.get(&[1, 2]), Some(&100));
assert_eq!(trie.get_mut(&[0, 0]), None);

pub fn dimensions(&self) -> usize

pub(super) fn root(&self) -> &Node<V>

pub(super) fn root_mut(&mut self) -> &mut Node<V>

Trait Implementations

impl<V: Clone> Clone for KdTrie<V>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<V: Debug> Debug for KdTrie<V>

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

Formats the value using the given formatter.

impl<V> Drop for KdTrie<V>

fn drop(&mut self)

Executes the destructor for this type.

impl<V: Hash> Hash for KdTrie<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<V> Index<&[i32]> for KdTrie<V>

type Output = V

The returned type after indexing.

fn index(&self, index: &[i32]) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<V> IndexMut<&[i32]> for KdTrie<V>

fn index_mut(&mut self, index: &[i32]) -> &mut Self::Output

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

impl<'a, V> IntoIterator for &'a KdTrie<V>

type IntoIter = Iter<'a, V, Vec<i32>>

Which kind of iterator are we turning this into?

type Item = (Vec<i32>, &'a V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, V> IntoIterator for &'a mut KdTrie<V>

type IntoIter = IterMut<'a, V, Vec<i32>>

Which kind of iterator are we turning this into?

type Item = (Vec<i32>, &'a mut V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<V: PartialEq> PartialEq for KdTrie<V>

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<V: Eq> Eq for KdTrie<V>