Struct RangeVec 

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

RangeVec is a data structure that will return a value for any index, but only a small range of values are non-default, and only these are stored. It is based on a ring buffer (VecDeque) so that it may efficiently grow in either direction.

RangeVec requires that the stored type implement Default and Eq, and it will return the default value whenever an index outside of its stored range is accessed. The stored range will automatically be grown or shrunk to exactly match the smallest possible range of non-default values after every mutation. To facilitate this, all mutable access is currently done through closures, so that the ring buffer may be adjusted based on whether the value is equal to T::default() after mutation. There may be a guard-based API in the future as well.

Because of this, RangeVec currently has no .iter_mut() method, as without a guard it would not be possible to adjust the backing storage after a mutation. However, though less flexible, the mutate_many or mutate_non_default methods may work instead. The slice access methods as_mut_slices_with and make_contiguous_with may also be of interest. For the same reason, RangeVec implements Index so you can get elements using square bracked syntax: let x = my_range_vec[50];, but does not implement IndexMut. Again, this may be possible in the future using a guard API.

Because the backing storage is contiguous, this data structure is most efficient when all of the non-default values are within a small range. If they are sparse, consider using a map instead, particularly one with a hashing algorithm tuned for performance on integer indices.

The stored type’s implementation of Default should be fairly cheap, as it will be called frequently to initialize values before mutation of indices outside of the stored range, or to initialize default values between stored non-default values. It is a logic error for two calls to T::default() to return different results during the RangeVec’s lifetime.

Implementations

impl<T> RangeVec<T>

pub fn range(&self) -> Option<Range<usize>>

Returns the currently stored range of the internal buffer, exactly encompassing the leftmost (inclusive) and rightmost (exclusive) non-default values. This will return None if the range is empty, i.e., if there are no non-default values.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
assert_eq!(range_vec.range(), None);

range_vec.set(5, 1);
range_vec.set(10, 2);
assert_eq!(range_vec.range(), Some(5..11));

pub fn range_size(&self) -> usize

Returns the size of the stored range.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
assert_eq!(range_vec.range_size(), 0);

range_vec.set(5, 1);
range_vec.set(10, 2);
assert_eq!(range_vec.range_size(), 6);

pub fn is_empty(&self) -> bool

Returns true if there are any stored values, i.e., if any values are non-default.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
assert!(range_vec.is_empty());

range_vec.set(5, 1);
assert!(!range_vec.is_empty());

pub fn iter(&self, range: impl RangeBounds<usize>) -> Iter<'_, T>

Creates an iterator over the specified range. A range unbounded on the left will start at 0 (inclusive), and one unbounded on the right will end at usize::MAX (exclusive). The iterator will emit values of type &T.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.set(3, 1);
range_vec.set(5, 2);
let numbers: Vec<i32> = range_vec.iter(1..=7).copied().collect();
assert_eq!(numbers, vec![0, 0, 1, 0, 2, 0, 0]);

pub fn clear(&mut self)

Clears the RangeVec, resetting all values to default.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.set(3, 1);
range_vec.set(5, 2);
range_vec.clear();
assert!(range_vec.is_empty());

impl<T> RangeVec<T>

where T: Default + Eq,

pub fn new() -> Self

Creates an empty (all-default) RangeVec.

Examples

let range_vec: RangeVec<i32> = RangeVec::new();
assert_eq!(range_vec.range(), None);

pub fn get(&self, index: usize) -> &T

Provides a reference to the element at the given index, or to a default element.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.set(5, 1);
assert_eq!(range_vec.get(5), &1);
assert_eq!(range_vec.get(10), &0);

pub fn set(&mut self, index: usize, value: T)

Set the value at index index. If the element is outside of the stored range and is not equal to T::default(), the ring buffer will be grown to accomodate it. If it is inside the stored range and is equal to T::default, the ring buffer will be shrunk accordingly.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.set(5, 1);
range_vec.set(7, 2);
range_vec.set(9, 3);
assert_eq!(range_vec.range(), Some(5..10));

range_vec.set(5, 0);
assert_eq!(range_vec.range(), Some(7..10));

pub fn get_mut_with<F, R>(&mut self, index: usize, f: F) -> R

where F: FnOnce(&mut T) -> R,

Mutate the value at index index. If the element is outside of the stored range and is not equal to T::default() after mutation, the ring buffer will be grown to accomodate it. If it is inside the stored range and is equal to T::default after mutation, the ring buffer will be shrunk accordingly. Any value returned from the passed closure f will be returned from the method.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.get_mut_with(5, |v| *v = 1);
range_vec.get_mut_with(7, |v| *v += 2);
range_vec.get_mut_with(9, |v| *v = 3);
assert_eq!(range_vec.range(), Some(5..10));

range_vec.get_mut_with(5, |v| *v -= 1);
range_vec.get_mut_with(9, |v| *v = 0);
assert_eq!(range_vec.range(), Some(7..8));

pub fn mutate_many<F>(&mut self, range: impl RangeBounds<usize>, f: F)

where F: FnMut(usize, &mut T),

Mutate a range of values. This method is equivalent to calling get_mut_with repeatedly on an entire range of values, except it does not pass through the closure’s return value. In addition, it only makes the checks to grow and shrink the backing storage once. The closure is also passed the index as its first argument.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.mutate_many(5..15, |_, v| *v += 1);
range_vec.mutate_many(10..15, |_, v| *v -= 1);
range_vec.mutate_many(5..8, |i, v| *v += i as i32);
assert_eq!(range_vec.range(), Some(5..10));
assert_eq!(
    range_vec.iter(5..15).copied().collect::<Vec<i32>>(),
    vec![6, 7, 8, 1, 1, 0, 0, 0, 0, 0],
);

pub fn mutate_non_default<F>(&mut self, f: F)

where F: FnMut(usize, &mut T),

Mutate all values that are not the default value. This method will call f repeatedly on each element v where v != T::default(), and only makes the checks to grow and shrink the backing storage once. The closure is also passed the index as its first argument.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.set(5, -5);
range_vec.set(7, 1);
range_vec.set(9, 2);

range_vec.mutate_non_default(|i, v| *v += i as i32);
assert_eq!(range_vec.range(), Some(7..10));
assert_eq!(
    range_vec.iter(7..10).copied().collect::<Vec<i32>>(),
    vec![8, 0, 11],
);

pub fn reset(&mut self, index: usize)

Reset the value at a given index to T::default(), and shrink the backing storage accordingly. If index is outside the stored range, this method is a no-op.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.set(5, 1);
range_vec.set(7, 2);
range_vec.set(9, 3);

range_vec.reset(7);
assert_eq!(range_vec.range(), Some(5..10));
assert_eq!(range_vec.get(7), &0);

range_vec.reset(5);
assert_eq!(range_vec.range(), Some(9..10));

pub fn truncate(&mut self, range: impl RangeBounds<usize>)

Reset all values outside of range to T::default(), and shrink the backing storage accordingly.

Examples

let mut range_vec: RangeVec<i32> = RangeVec::new();
range_vec.set(5, 1);
range_vec.set(7, 2);
range_vec.set(9, 3);

range_vec.truncate(6..);
assert_eq!(range_vec.range(), Some(7..10));

range_vec.truncate(15..20);
assert!(range_vec.is_empty());

pub fn as_mut_slices_with<F, R>( &mut self, range: impl RangeBounds<usize>, f: F, ) -> R

where F: FnOnce(&mut [T], &mut [T]) -> R,

Mutably access the backing storage for range. This method will grow the ring buffer to include the entire range if needed, and shrink afterwards as appropriate. Because the backing storage is a ring buffer, it may be split up into two slices, which are provided as arguments to f. If all of the data is contiguous, the second slice will be empty. Any value returned from f will be returned from the method.

If you need to access a single contiguous slice and don’t care about paying the cost to rearrange the backing storage, use make_contiguous_with.

pub fn make_contiguous_with<F, R>( &mut self, range: impl RangeBounds<usize>, f: F, ) -> R

where F: FnOnce(&mut [T]) -> R,

Rearrange the backing storage to make it contiguous, and mutably access it for range. This method will grow the ring buffer to include the entire range if needed, and shrink afterwards as appropriate. Any value returned from f will be returned freom the method.

If you don’t want to pay the cost to rearrange the backing storage but are okay with the data being split up into two slices, use as_mut_slices_with.

Trait Implementations

impl<T: Clone> Clone for RangeVec<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for RangeVec<T>

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

Formats the value using the given formatter.

impl<T> Default for RangeVec<T>

where T: Default + Eq,

fn default() -> Self

Returns the “default value” for a type.

impl<T> Display for RangeVec<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Index<usize> for RangeVec<T>

where T: Default + Eq,

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.