Struct SortedIndexBuffer 

pub struct SortedIndexBuffer<T> { /* private fields */ }

A buffer indexed by a u64 sequence number.

This behaves idential to a BTreeMap<u64, T>, but is optimized for the case where the indices are mostly contiguous, with occasional gaps.

It will have large memory overhead if the indices are very sparse, so it should not be used as a general-purpose sorted map.

Internals

The underlying storage is a contiguous buffer of Option<T> of twice the size of the key range, rounded up to the next power of two. We track min and max.

The buffer is a Vec<Option<T>>, which can have some additional unused capacity.

|x_xxxx|________| max-min=6, page size 8, buffer fits in first page ^ min ^ max |_x|xxxx| max-min=6, page size 8, buffer spans two pages ^ min ^ max

Access is O(1). Insertion and removal is usually O(1), but will occasionally move contents around to resize the buffer, which is O(n). Moving will only happen every O(n.next_power_of_two()) operations, so amortized complexity is still O(1).

Implementations

impl<T> SortedIndexBuffer<T>

pub fn with_capacity(capacity: usize) -> Self

Create a new SortedIndexBuffer with the given initial capacity.

pub fn new() -> Self

Create a new, empty SortedIndexBuffer.

pub fn is_empty(&self) -> bool

Returns true if the buffer contains no elements.

pub fn contains_key(&self, index: u64) -> bool

Returns true if the buffer contains an element at the given index.

pub fn keys_range<R: RangeBounds<u64>>( &self, range: R, ) -> impl DoubleEndedIterator<Item = u64> + '_

Iterate over all keys in the given index range in ascending order.

pub fn values_range<R: RangeBounds<u64>>( &self, range: R, ) -> impl DoubleEndedIterator<Item = &T> + '_

Iterate over all values in the given index range in ascending order of their keys.

pub fn values_range_mut<R: RangeBounds<u64>>( &mut self, range: R, ) -> impl DoubleEndedIterator<Item = &mut T> + '_

Iterate over all values in the given index range in ascending order of their keys.

pub fn iter_range<R: RangeBounds<u64>>( &self, range: R, ) -> impl DoubleEndedIterator<Item = (u64, &T)> + '_

Iterate over all (index, value) pairs in the given index range in ascending order of their keys.

pub fn retain(&mut self, f: impl FnMut(u64, &mut T) -> bool)

pub fn retain_range<R: RangeBounds<u64>>(&mut self, range: R)

Retain only the elements in the given index range.

pub fn keys(&self) -> impl DoubleEndedIterator<Item = u64> + '_

Iterate over all keys in the buffer in ascending order.

pub fn values(&self) -> impl DoubleEndedIterator<Item = &T> + '_

Iterate over all values in the buffer in ascending order of their keys.

pub fn values_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> + '_

Iterate over all values in the buffer in ascending order of their keys.

pub fn iter(&self) -> impl DoubleEndedIterator<Item = (u64, &T)> + '_

Iterate over all (index, value) pairs in the buffer in ascending order of their keys.

Values are returned by reference.

pub fn into_iter(self) -> impl DoubleEndedIterator<Item = (u64, T)>

Turn into an iterator over all (index, value) pairs in the buffer in ascending order of their keys.

This is an explicit method instead of implementing IntoIterator, so we can return a DoubleEndedIterator without having to name the iterator type.

pub fn get(&self, index: u64) -> Option<&T>

Get a reference to the value at the given index, if it exists.

pub fn insert(&mut self, index: u64, value: T)

Insert value at index.

pub fn remove(&mut self, index: u64) -> Option<T>

Remove value at index.

Trait Implementations

impl<T: Clone> Clone for SortedIndexBuffer<T>

fn clone(&self) -> SortedIndexBuffer<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for SortedIndexBuffer<T>

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

Formats the value using the given formatter.

impl<T> Default for SortedIndexBuffer<T>

fn default() -> Self

Returns the “default value” for a type.