Struct orx_imp_vec::ImpVec

source ·

pub struct ImpVec<T, P = SplitVec<T>>where
    P: PinnedVec<T>,{ /* private fields */ }

Expand description

ImpVec stands for ‘immutable-push-vec’.

It may orx_split_vec::SplitVec as the underlying data structure providing flexible growth strategies, or orx_fixed_vec::FixedVec with a preset strict capacity while providing standard vector complexity in common operations.

In addition, it allows to push/extend the vector with an immutable reference.

This allows to hold on the references of already pushed elements while building the collection.

Implementations§

source §

impl<T, P> ImpVec<T, P>where P: PinnedVecSimple<T>, T: NotSelfRefVecItem,

source

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

Inserts an element at position index within the vector, shifting all elements after it to the right.

Panics

Panics if index >= len.

Safety

insert operation for an ImpVec where the elements are T: NotSelfRefVecItem is safe; in this case, pinned vector shares the same safety requirements as std::vec::Vec which is readily provided by the borrow checker.

source

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

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

Panics

Panics if index is out of bounds.

Safety

remove operation for a ImpVec where the elements are T: NotSelfRefVecItem is safe; in this case, pinned vector shares the same safety requirements as std::vec::Vec which is readily provided by the borrow checker.

source

pub fn pop(&mut self) -> Option<T>

Removes the last element from a vector and returns it, or None if it is empty.

Safety

pop operation for a ImpVec where the elements are T: NotSelfRefVecItem is safe; in this case, pinned vector shares the same safety requirements as std::vec::Vec which is readily provided by the borrow checker.

source §

impl<T, P> ImpVec<T, P>where P: PinnedVec<T>,

source

pub fn into_pinned(self) -> P

Converts the ImpVec into underlying PinnedVec.

This operation corresponds to moving the pinned vec out of a ref cell; and hence, is not expensive. Likewise, the pinned vec can then be converted back into an imp vec by wrapping it up by a ref cell under the hood.

Converting an ImpVec to PinnedVec is useful for the following reasons:

It reduces one level of abstraction by getting rid of the ref cell, and hence, achieving SplitVec or FixedVec (same as std vec) performance depending on the type of the pinned vec.
It means that immutable pushes are not allowed anymore.
- In a vector holding inter-element references, this means that such references will not be added or removed.
- In other words, it safely ensures that the building of the structure is completed.

Examples

You may see and example back-and-forth conversions between a PinnedVec.

Complete type annotations are not needed byt added to make the conversions explicitly visible.

use orx_imp_vec::prelude::*;

let imp: ImpVec<char, SplitVec<char, Doubling>> = SplitVec::with_doubling_growth(2).into();
for _ in 0..3 {
    imp.push('s');
}
assert_eq!(imp, vec!['s', 's', 's']);

let split: SplitVec<char, Doubling> = imp.into_pinned();
assert_eq!(split, vec!['s', 's', 's']);

let imp_again: ImpVec<_, _> = split.into();
imp_again.push('s');
assert_eq!(imp_again, vec!['s', 's', 's', 's']);

let split_back = imp_again.into_pinned();
assert_eq!(split_back, vec!['s', 's', 's', 's']);

source §

impl<T, P> ImpVec<T, P>where P: PinnedVec<T>,

source

pub fn iter(&self) -> Iter<'_, T, P> ⓘ

Returns an iterator for the imp-vec.

source

pub fn iter_mut(&mut self) -> IterMut<'_, T, P> ⓘ

Returns a mutable iterator for the imp-vec.

source §

impl<T, P> ImpVec<T, P>where P: PinnedVec<T>,

source

pub fn push(&self, value: T)

Appends an element to the back of a collection.

Unlike std::vec::Vec or orx_split_vec::SplitVec; push operation for ImpVec does not require a mutable reference.

Examples

use orx_imp_vec::prelude::*;

let vec: ImpVec<_, _> = FixedVec::new(10).into();
vec.push(1);
vec.push(2);

// since push does not require a mut reference,
// it is legal to hold on to other immutable references
// while pushing elements.
let ref_elem = &vec[1];
let ref_elem_addr = ref_elem as *const i32;
assert_eq!(2, *ref_elem);

vec.push(3);
vec.push(4);
vec.push(5);

assert_eq!(2, *ref_elem);
assert_eq!(vec, [1, 2, 3, 4, 5]);

let ref_elem_addr_after_growth = &vec[1] as *const i32;
assert_eq!(ref_elem_addr, ref_elem_addr_after_growth);

source §

impl<'a, T, P> ImpVec<T, P>where P: PinnedVec<T> + 'a,

source

pub fn push_get_ref<'b>(&'b self, value: T) -> &'a Twhere 'a: 'b,

Appends an element to the back of a collection and returns a reference to it.

The reference will always be valid unless the collection is mutated; note that methods that grows the vector do not require a mutable reference, such as, push, push_get_ref, extend or extend_from_slice methods.

Examples

Hold on to valid references while pushing new items, as long as the collection is not mutated with methods such as insert, remove or pop.

use orx_imp_vec::prelude::*;

let vec: ImpVec<_, _> = FixedVec::new(10).into();
let ref1 = vec.push_get_ref(1);
let ref_elem_addr = ref1 as *const i32;

vec.push(2);
vec.push(3);
let ref4 = vec.push_get_ref(4);

// capacity is expaneded here from 4 to 8; however, in chunks;
// therefore, data is not moved around and the references remain valid.
let ref5 = vec.push_get_ref(5);


assert_eq!(ref1, &1);
assert_eq!(ref4, &4);
assert_eq!(ref5, &5);
assert_eq!(vec, [1, 2, 3, 4, 5]);

let ref_elem_addr_after_growth = &vec[0] as *const i32;
assert_eq!(ref_elem_addr, ref_elem_addr_after_growth);

As you may see below, any mutable method that can possibly invalidate the references are not allowed.

use orx_imp_vec::prelude::*;

let mut vec: ImpVec<_, _> = SplitVec::with_linear_growth(10).into(); // mut required for the `insert`
let ref1 = vec.push_get_ref(1);
vec.push(2);
vec.push(3);

assert_eq!(ref1, &1);
assert_eq!(vec, [1, 2, 3]);

vec.insert(0, 42);
assert_eq!(vec, [42, 1, 2, 3]);

// below line does not compile as the 'insert' call breaks reference 'ref1'
// let value1 = *ref1;

source §

impl<'a, T, P> ImpVec<T, P>where P: PinnedVec<T> + 'a, T: SelfRefVecItem<'a> + 'a,

source

pub fn set_prev(&mut self, idx: usize, prev_idx: Option<usize>)

Sets the prev reference of the element at the idx to the element at the prev_idx.

If prev_idx.is none() the prev reference will be set to None.

Panics

Panics if idx is out of bounds; or if prev_idx.is_some() and the underlying id is out of bounds.

Safety

The call is trivially safe when prev_idx.is_none() since the optional reference is just set to None.

Otherwise, the method call is safe due to the following reasons:

Due to bounds-checks both the main element and the target element that the main element will hold a reference of belong to the vector; in other words, the main element will be holding a reference to another element in the same vector.
Since ImpVec wraps a PinnedVec, memory location of the target element cannot be change while the vector is growing.
The methods which can possibly change the memory location of the target element such as remove, pop, swap, truncate or insert are unsafe for PinnedVecs, and hence, for ImpVecs.
The only safe method which could change the memory location of the target element is clear method. This is safe since it would drop the main element at the same time together with its reference and target element.

Due to these guarantees, the built up inter-elements reference is and will remain valid.

source

pub fn set_next(&mut self, idx: usize, next_idx: Option<usize>)

Sets the next reference of the element at the idx to the element at the next_idx.

If next_idx.is none() the prev reference will be set to None.

Panics

Panics if idx is out of bounds; or if prev_idx.is_some() and the underlying id is out of bounds.

Safety

The call is trivially safe when next_idx.is_none() since the optional reference is just set to None.

Otherwise, the method call is safe due to the following reasons:

Due to bounds-checks both the main element and the target element that the main element will hold a reference of belong to the vector; in other words, the main element will be holding a reference to another element in the same vector.
Since ImpVec wraps a PinnedVec, memory location of the target element cannot be change while the vector is growing.
The methods which can possibly change the memory location of the target element such as remove, pop, swap, truncate or insert are unsafe for PinnedVecs, and hence, for ImpVecs.
The only safe method which could change the memory location of the target element is clear method. This is safe since it would drop the main element at the same time together with its reference and target element.