Struct orx_imp_vec::ImpVec

source ·

pub struct ImpVec<T, P>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 iter(&self) -> ImpVecIter<'_, T, P> ⓘ

Returns an iterator for the imp-vec.

source

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

Returns a mutable iterator for the imp-vec.

source §

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

source

pub unsafe fn get_mut<'b>(&self, index: usize) -> Option<&'a mut T>where 'a: 'b,

Returns a mutable reference to the item at the index-th position of the vector; returns None if index is out of bounds.

The main purpose of this method is to be able to build vectors elements of which reference other elements, while these references lead to cyclic relations.

Safety

This method allows to mutate an existing element of the vector with an immutable reference. For obvious reasons, this operation is not safe. Therefore, it is important that this method is used in limited scopes, where the caller is able to guarantee the safety of the call.

You may see in the next section such an example where the unsafe get_mut method is called only once to complete the cycle of references of points of a triangle.

Examples

use orx_imp_vec::prelude::*;
use std::fmt::Debug;

#[derive(Debug)]
struct Point<'a, T> {
    data: T,
    next: Option<&'a Point<'a, T>>,
}
impl<'a, T: PartialEq + Debug> PartialEq for Point<'a, T> {
    fn eq(&self, other: &Self) -> bool {
        let ptr_eq =
            |l1, r1| std::ptr::eq(l1 as *const Point<'_, T>, r1 as *const Point<'_, T>);
        self.data == other.data
            && match (self.next, other.next) {
                (Some(l1), Some(r1)) => ptr_eq(l1, r1),
                _ => {
                    core::mem::discriminant(&self.next) == core::mem::discriminant(&other.next)
                }
            }
    }
}

// build cyclic reference of three points:
// Point('x') -> Point('y') -> Point('z') -> Point('x') -> ...

// the vector will grow; however, this does not invalidate references
// since `SplitVec` and `FixedVec` both implement `PinnedVec`.
let triangle: ImpVec<_, _> = SplitVec::with_doubling_growth(2).into();

let z = triangle.push_get_ref(Point {
    data: 'z',
    next: None, /*none for now*/
});
let y = triangle.push_get_ref(Point {
    data: 'y',
    next: Some(z),
});
let x = triangle.push_get_ref(Point {
    data: 'x',
    next: Some(y),
});

// close the circle with the unsafe call
unsafe { triangle.get_mut(0) }.unwrap().next = Some(x);

let mut curr = x;
let mut relations = curr.data.to_string();
for _ in 0..4 {
    curr = curr.next.unwrap();
    relations.push_str(" -> ");
    relations.push(curr.data);
}
println!("{}", relations);
assert_eq!("x -> y -> z -> x -> y", relations);

assert_eq!(
    &x,
    &x.next.unwrap().next.unwrap().next.unwrap() // x -> y -> z -> x
);

source

pub unsafe fn get_ref<'b>(&self, index: usize) -> Option<&'b T>where 'a: 'b,

Returns a reference to the item at the index-th position of the vector; returns None if index is out of bounds.

The main purpose of this method is to be able to build vectors elements of which reference other elements, while these references lead to cyclic relations.

Safety

This method allows to mutate an existing element of the vector with an immutable reference. For obvious reasons, this operation is not safe. Therefore, it is important that this method is used in limited scopes, where the caller is able to guarantee the safety of the call. See the get_mut examples related to safety.

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;