Enum imbl::vector::Focus

source ·
pub enum Focus<'a, A> {
    // some variants omitted
}
Expand description

Focused indexing over a Vector.

By remembering the last tree node accessed through an index lookup and the path we took to get there, we can speed up lookups for adjacent indices tremendously. Lookups on indices in the same node are instantaneous, and lookups on sibling nodes are also very fast.

A Focus can also be used as a restricted view into a vector, using the narrow and split_at methods.

§When should I use a Focus for better performance?

Focus is useful when you need to perform a large number of index lookups that are more likely than not to be close to each other. It’s usually worth using a Focus in any situation where you’re batching a lot of index lookups together, even if they’re not obviously adjacent - there’s likely to be some performance gain for even completely random access.

If you’re just iterating forwards or backwards over the Vector in order, you’re better off with a regular iterator, which, in fact, is implemented using a Focus, but provides a simpler interface.

If you’re just doing a very small number of index lookups, the setup cost for the Focus is probably not worth it.

A Focus is never faster than an index lookup on a small Vector with a length below the internal RRB tree’s branching factor of 64.

§Examples

This example is contrived, as the better way to iterate forwards or backwards over a vector is with an actual iterator. Even so, the version using a Focus should run nearly an order of magnitude faster than the version using index lookups at a length of 1000. It should also be noted that vector::Iter is actually implemented using a Focus behind the scenes, so the performance of the two should be identical.

let mut vec: Vector<i64> = Vector::from_iter(0..1000);

// Summing a vector, the slow way:
let mut sum = 0;
for i in 0..1000 {
    sum += *vec.get(i).unwrap();
}
assert_eq!(499500, sum);

// Summing a vector faster using a Focus:
let mut sum = 0;
let mut focus = vec.focus();
for i in 0..1000 {
    sum += *focus.get(i).unwrap();
}
assert_eq!(499500, sum);

// And the easy way, for completeness:
let sum: i64 = vec.iter().sum();
assert_eq!(499500, sum);

Implementations§

source§

impl<'a, A> Focus<'a, A>
where A: 'a,

source

pub fn new(vector: &'a Vector<A>) -> Self

Construct a Focus for a Vector.

source

pub fn len(&self) -> usize

Get the length of the focused Vector.

source

pub fn is_empty(&self) -> bool

Test if the focused Vector is empty.

source

pub fn get(&mut self, index: usize) -> Option<&A>

Get a reference to the value at a given index.

source

pub fn index(&mut self, index: usize) -> &A

Get a reference to the value at a given index.

Panics if the index is out of bounds.

source

pub fn chunk_at(&mut self, index: usize) -> (Range<usize>, &[A])

Get the chunk for the given index.

This gives you a reference to the leaf node that contains the index, along with its start and end indices.

source

pub fn narrow<R>(self, range: R) -> Self
where R: RangeBounds<usize>,

Narrow the focus onto a subslice of the vector.

Focus::narrow(range) has the same effect as &slice[range], without actually modifying the underlying vector.

Panics if the range isn’t fully inside the current focus.

§Examples
let vec = Vector::from_iter(0..1000);
let narrowed = vec.focus().narrow(100..200);
let narrowed_vec = narrowed.into_iter().cloned().collect();
assert_eq!(Vector::from_iter(100..200), narrowed_vec);
source

pub fn split_at(self, index: usize) -> (Self, Self)

Split the focus into two.

Given an index index, consume the focus and produce two new foci, the left onto indices 0..index, and the right onto indices index..N where N is the length of the current focus.

Panics if the index is out of bounds.

This is the moral equivalent of slice::split_at, in that it leaves the underlying data structure unchanged, unlike Vector::split_at.

§Examples
let vec = Vector::from_iter(0..1000);
let (left, right) = vec.focus().split_at(500);
let left_vec = left.into_iter().cloned().collect();
let right_vec = right.into_iter().cloned().collect();
assert_eq!(Vector::from_iter(0..500), left_vec);
assert_eq!(Vector::from_iter(500..1000), right_vec);

Trait Implementations§

source§

impl<'a, A> Clone for Focus<'a, A>
where A: Clone + 'a,

source§

fn clone(&self) -> Self

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<'a, A> From<FocusMut<'a, A>> for Focus<'a, A>
where A: Clone + 'a,

source§

fn from(f: FocusMut<'a, A>) -> Focus<'a, A>

Converts to this type from the input type.
source§

impl<'a, A> IntoIterator for Focus<'a, A>
where A: Clone + 'a,

§

type Item = &'a A

The type of the elements being iterated over.
§

type IntoIter = Iter<'a, A>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Auto Trait Implementations§

§

impl<'a, A> Freeze for Focus<'a, A>

§

impl<'a, A> RefUnwindSafe for Focus<'a, A>
where A: RefUnwindSafe,

§

impl<'a, A> Send for Focus<'a, A>
where A: Send + Sync,

§

impl<'a, A> Sync for Focus<'a, A>
where A: Sync,

§

impl<'a, A> Unpin for Focus<'a, A>

§

impl<'a, A> UnwindSafe for Focus<'a, A>
where A: RefUnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

default unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.