Struct InsertionSet

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

A set of pending insertions on a Vec

When multiple insertions at a

See module documentation for an overview.

Implementations

impl<T> InsertionSet<T>

pub fn new() -> Self

Create a new InsertionSet

pub fn push(&mut self, insertion: Insertion<T>)

Queue the specified insertion

If there are multiple insertions at the same index, they will be applied in the order queued.

pub fn insert(&mut self, index: usize, element: T)

Insert the element to be inserted before the given index

If multiple elements are queued to be inserted at the same index, they will be applied in the original order queued.

pub fn applied(self, target: Vec<T>) -> Vec<T>

Apply all of the pending insertions against the specified vector, returning the result

pub fn desired_insertions(&self) -> usize

The number of insertions that are currently queued

pub fn list_updated_locations( &mut self, target: &[T], ) -> Vec<(OriginalLocation, usize)>

List the updated locations of all the elements (both original and newly inserted).

See Self::compute_updated_locations for details

pub fn compute_updated_locations<F>(&mut self, target: &[T], func: F)

where F: FnMut(OriginalLocation, usize),

Compute the updated locations of all the elements (both original and newly inserted).

Assumes this set of insertions are being applied against the specified slice, invoking the callback on each element (even if the location is unchanged).

If any of the insertion indexes are out of bounds of the original vec, then this function will panic.

pub fn apply(&mut self, target: &mut Vec<T>)

Applies all the insertions to the specified target vector.

This reuses the Vector’s existing memory if possible, but may require a reallocation (due to new values)

The average runtime of this function is O(n + m), where n is the number of existing elements and m is the number of insertions. The worst case running time is O((k * log(k)) where k = n + m.

Trait Implementations

impl<T> Default for InsertionSet<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> FromIterator<(usize, T)> for InsertionSet<T>

fn from_iter<I: IntoIterator<Item = (usize, T)>>(iter: I) -> Self

Creates a value from an iterator.

impl<T> FromIterator<Insertion<T>> for InsertionSet<T>

fn from_iter<I: IntoIterator<Item = Insertion<T>>>(iter: I) -> Self

Creates a value from an iterator.