Struct TwoEndedGrove 

pub struct TwoEndedGrove<T> {
    non_neg: Grove<T>,
    neg: Grove<T>,
    min: AtomicI32,
    max: AtomicI32,
}

A bidirectional sparse vector that supports both positive and negative indices.

TwoEndedGrove extends the functionality of Grove by allowing elements to be indexed using both positive and negative integers. It maintains two separate Grove instances: one for non-negative indices and another for negative indices.

This data structure is primarily used as the backing store for the nodes in KdTrie.

Examples

use once::TwoEndedGrove;

let grove = TwoEndedGrove::<i32>::new();

// Insert elements at both positive and negative indices
grove.insert(-5, 10);
grove.insert(0, 20);
grove.insert(5, 30);

// Retrieve elements
assert_eq!(grove.get(-5), Some(&10));
assert_eq!(grove.get(0), Some(&20));
assert_eq!(grove.get(5), Some(&30));
assert_eq!(grove.get(-2), None); // No element at this index

// Get the range of valid indices
assert_eq!(grove.range(), -5..6);

Fields

non_neg: Grove<T>

neg: Grove<T>

min: AtomicI32

max: AtomicI32

Implementations

impl<T> TwoEndedGrove<T>

pub fn new() -> Self

Creates a new empty TwoEndedGrove.

Examples

use once::TwoEndedGrove;

let grove = TwoEndedGrove::<i32>::new();

pub fn insert(&self, idx: i32, value: T)

Inserts a value at the specified index.

This operation is thread-safe and can be called from multiple threads. This method panics if a value already exists at the specified index.

Parameters

• idx: The index at which to insert the value
• value: The value to insert

Examples

use once::TwoEndedGrove;

let grove = TwoEndedGrove::<i32>::new();
grove.insert(-5, 10);
grove.insert(5, 20);

pub fn try_insert(&self, idx: i32, value: T) -> Result<(), T>

Attempts to insert a value at the specified index.

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

Parameters

• idx: The index at which to insert the value
• value: The value to insert

Returns

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

Examples

use once::TwoEndedGrove;

let grove = TwoEndedGrove::<i32>::new();
assert_eq!(grove.try_insert(-5, 10), Ok(()));
assert_eq!(grove.try_insert(-5, 20), Err(20)); // Index already occupied

pub fn get(&self, idx: i32) -> Option<&T>

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

Parameters

• idx: The index of the value to retrieve

Returns

• Some(&T) if a value exists at the specified index
• None if no value exists at the specified index

Examples

use once::TwoEndedGrove;

let grove = TwoEndedGrove::<i32>::new();
grove.insert(-5, 10);

assert_eq!(grove.get(-5), Some(&10));
assert_eq!(grove.get(0), None);

pub fn get_mut(&mut self, idx: i32) -> Option<&mut T>

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

This method can only be called if we have an exclusive reference to self, which may not be very common in practice. It is mainly used for the Drop implementation of the MultiIndexed, which allows to use non-atomic operations for performance.

Parameters

• idx: The index of the value to retrieve

Returns

• Some(&mut T) if a value exists at the specified index
• None if no value exists at the specified index

Examples

use once::TwoEndedGrove;

let mut grove = TwoEndedGrove::<i32>::new();
grove.insert(-5, 10);

if let Some(value) = grove.get_mut(-5) {
    *value = 20;
}

assert_eq!(grove.get(-5), Some(&20));

pub fn range(&self) -> Range<i32>

Returns the range of indices that have values in the TwoEndedGrove.

We return both the minimum and maximum indices at the same time to optimize memory orderings.

Returns

A Range representing the range of indices that have values in the TwoEndedGrove. It is not guaranteed that all indices in the range have values. However, it is guaranteed that only the indices in the range have values if the TwoEndedGrove is not being concurrently modified.

Examples

use once::TwoEndedGrove;

let grove = TwoEndedGrove::<i32>::new();
grove.insert(-5, 10);
grove.insert(0, 20);
grove.insert(5, 30);

assert_eq!(grove.range(), -5..6);

pub fn iter(&self) -> impl Iterator<Item = (i32, &T)>

pub fn iter_mut(&mut self) -> impl Iterator<Item = (i32, &mut T)>

pub fn values(&self) -> impl Iterator<Item = &T>

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T>

pub fn is_set(&self, idx: i32) -> bool

Checks if a value exists at the specified index.

Parameters

• idx: The index to check

Returns

true if a value exists at the specified index, false otherwise.

Examples

use once::TwoEndedGrove;

let grove = TwoEndedGrove::<i32>::new();
grove.insert(-5, 10);

assert!(grove.is_set(-5));
assert!(!grove.is_set(0));

Trait Implementations

impl<T: Clone> Clone for TwoEndedGrove<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for TwoEndedGrove<T>

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

Formats the value using the given formatter.

impl<T> Default for TwoEndedGrove<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Hash> Hash for TwoEndedGrove<T>

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<T> Index<i32> for TwoEndedGrove<T>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T> IndexMut<i32> for TwoEndedGrove<T>

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

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

impl<T: PartialEq> PartialEq for TwoEndedGrove<T>

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<T: Eq> Eq for TwoEndedGrove<T>