Struct ChainNoGenArena 

pub struct ChainNoGenArena<P: Ptr, T> { /* private fields */ }

The same as crate::ChainArena except that the interlinks have no generation counters.

The advantage of this is reduced memory footprint at the expense of generation checks from the interlinks. This is mainly intended for internal usage within data structures.

Implementations

impl<P: Ptr, T> ChainNoGenArena<P, T>

Note

P Ptrs to links in a ChainNoGenArena follow the same validity rules as Ptrs in a regular Arena (see the documentation on the main impl<P: Ptr, T> Arena<P, T>), except that ChainNoGenArenas automatically update internal interlinks to maintain the linked-list nature of the chains. The public interface has been designed such that it is not possible to break the doubly linked invariant that each interlink Ptr from one link to its neighbor has exactly one corresponding interlink Ptr pointing from the neighbor back to itself. However, note that external copies of interlinks may be indirectly invalidated by operations on a neighboring link.

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

pub fn len(&self) -> usize

Returns the number of links in the arena

pub fn is_empty(&self) -> bool

Returns if the arena is empty

pub fn capacity(&self) -> usize

Returns the capacity of the arena

pub fn generation(&self) -> P::Gen

Follows Arena::generation

pub fn reserve(&mut self, additional: usize)

Follows Arena::reserve

pub fn insert( &mut self, prev_next: (Option<P::Inx>, Option<P::Inx>), t: T, ) -> Result<P, T>

If prev_next.0.is_none() && prev_next.1.is_none() then a new chain is started in the arena. If prev_next.0.is_some() || prev_next.1.is_some() then the link is inserted in an existing chain and the neighboring interlinks reroute to the new link. prev_next.0.is_some() && prev_next.1.is_none() and the reverse is allowed even if the link is not at the start or end of the chain; this function will detect this and derive the unknown Ptr, inserting in the middle of the chain as usual. The Ptr to the new link is returned.

Errors

If a Ptr is invalid, or prev_next.0.is_some() && prev_next.1.is_some() && !self.are_neighbors(prev, next), then ownership of t is returned.

pub fn insert_with<F: FnOnce(P) -> T>( &mut self, prev_next: (Option<P::Inx>, Option<P::Inx>), create: F, ) -> Option<P>

The same as ChainNoGenArena::insert except that the inserted T is created by create. The Ptr that will point to the new element is passed to create, and this Ptr is also returned. create is not called and None is returned if the prev_next setup would be invalid.

pub fn insert_new(&mut self, t: T) -> P

Inserts t as a single link in a new chain and returns a Ptr to it

pub fn insert_new_with<F: FnOnce(P) -> T>(&mut self, create: F) -> P

Inserts the T returned by create as a new single link chain into the arena and returns a Ptr to it. create is given the the same Ptr that is returned, which is useful for initialization of immutable structures that need to reference themselves.

pub fn insert_new_cyclic(&mut self, t: T) -> P

Inserts t as a single link cyclical chain and returns a Ptr to it

pub fn insert_new_cyclic_with<F: FnOnce(P) -> T>(&mut self, create: F) -> P

Like ChainNoGenArena::insert_new_with but with a single link cyclical chain.

pub fn insert_start(&mut self, p_start: P, t: T) -> Result<P, T>

Inserts t as a new start link of a chain which has p_start as its preexisting first link. Returns ownership of t if p_start is not valid or is not the start of a chain

pub fn insert_end(&mut self, p_end: P, t: T) -> Result<P, T>

Inserts t as the new end link of a chain which has p_end as its preexisting end link. Returns ownership of t if p_end is not valid or is not the end of a chain

pub fn contains(&self, p: P) -> bool

Returns if p is a valid Ptr

pub fn are_neighbors(&self, p_prev: P, p_next: P) -> bool

Returns if p_prev and p_next are neighbors on the same chain, such that self.get_link(p_prev).unwrap().next() == Some(p_next) or self.get_link(p_next).unwrap().prev() == Some(p_prev). Note that self.are_neighbors(p0, p1) is not necessarily equal to self.are_neighbors(p1, p0) because of the directionality. This function returns true for the single link cyclic chain case with p0 == p1. Incurs only one internal lookup because of invariants. Additionally returns false if p_prev or p_next are invalid Ptrs.

pub fn are_neighbors_inx(&self, p_prev: P::Inx, p_next: P::Inx) -> bool

The same as ChainNoGenArena::are_neighbors but with P::Inx

pub fn get_link(&self, p: P) -> Option<&LinkNoGen<P, T>>

Returns a reference to a link pointed to by p. Returns None if p is invalid.

pub fn get_link_mut(&mut self, p: P) -> Option<LinkNoGen<P, &mut T>>

Returns a mutable reference to a link pointed to by p. Returns None if p is invalid.

pub fn get2_link_mut( &mut self, p0: P, p1: P, ) -> Option<(LinkNoGen<P, &mut T>, LinkNoGen<P, &mut T>)>

Gets two LinkNoGen<P, &mut T> references pointed to by p0 and p1. If p0 == p1 or a pointer is invalid, None is returned.

pub fn get(&self, p: P) -> Option<&T>

Returns a &T reference pointed to by p. Returns None if p is invalid.

pub fn get_mut(&mut self, p: P) -> Option<&mut T>

Returns a &mut T reference pointed to by p. Returns None if p is invalid.

pub fn get2_mut(&mut self, p0: P, p1: P) -> Option<(&mut T, &mut T)>

Gets two &mut T references pointed to by p0 and p1. If p0 == p1 or a Ptr is invalid, None is returned.

pub fn remove(&mut self, p: P) -> Option<LinkNoGen<P, T>>

Removes the link at p. If the link is in the middle of the chain, the neighbors of p are rerouted to be neighbors of each other so that the chain remains continuous. Returns None if p is not valid.

pub fn remove_chain(&mut self, p: P) -> Option<usize>

Efficiently removes the entire chain that p is connected to (which might only include itself). Returns the length of the chain. Returns None if p is not valid.

pub fn invalidate(&mut self, p: P) -> Option<P>

Invalidates all references to the link pointed to by p, and returns a new valid reference. Any interlinks inside the arena that also pointed to p are updated to use the new valid reference. Remember that any external interlink pointers that used p are invalidated as well as the link itself. Does no invalidation and returns None if p is invalid.

pub fn replace_and_keep_gen(&mut self, p: P, new: T) -> Result<T, T>

Replaces the T in the link pointed to by p with new, returns the old T, and keeps the internal generation counter as-is so that previously constructed Ptrs are still valid.

Errors

Returns ownership of new instead if p is invalid

pub fn replace_and_update_gen(&mut self, p: P, new: T) -> Result<(T, P), T>

Replaces the T in the link pointed to by p with new, returns a tuple of the old T and new P, and updates the internal generation counter so that previous Plinks to this link are invalidated.

Errors

Does no invalidation and returns ownership of new if p is invalid

pub fn swap(&mut self, p0: P, p1: P) -> Option<()>

Swaps the T at indexes p0 and p1 and keeps the generation counters and link connections as-is. If p0 == p1 then nothing occurs. Returns None if p0 or p1 are invalid.

pub fn connect(&mut self, p_prev: P, p_next: P) -> Option<()>

Connects the interlinks of p_prev and p_next such that p_prev will be previous to p_next. Returns None if p_prev has a next interlink, p_next has a previous interlink, or the pointers are invalid.

pub fn break_prev(&mut self, p: P) -> Option<()>

Breaks the previous interlink of p. Returns None if p is invalid or does not have a prev link.

pub fn break_next(&mut self, p: P) -> Option<()>

Breaks the next interlink of p. Returns None if p is invalid or does not have a next link.

pub fn exchange_next(&mut self, p0: P, p1: P) -> Option<()>

Exchanges the endpoints of the interlinks right after p0 and p1. Returns None if the links do not have next interlinks or if the pointers are invalid.

An interesting property of this function when applied to cyclic chains, is that exchange_next on two Ptrs of the same cyclic chain always results in two cyclic chains (except for if p0 == p1), and exchange_next on two Ptrs of two separate cyclic chains always results in a single cyclic chain.

pub fn clear(&mut self)

Drops all links from the arena and invalidates all pointers previously created from it. This has no effect on allocated capacity.

pub fn clear_and_shrink(&mut self)

Performs a ChainNoGenArena::clear and resets capacity to 0

pub fn compress_and_shrink(&mut self)

Compresses the arena by moving around entries to be able to shrink the capacity down to the length. All links and link prev-next relations remain, but all Ptrs and interlinks are invalidated. New Ptrs to the entries can be found again by iterators and advancers. Notably, when iterating or advancing after a call to this function or during mapping with ChainNoGenArena::compress_and_shrink_with, whole chains at a time are advanced through without discontinuity (although there is not a specified ordering of links within the chain). Additionally, cache locality is improved by neighboring links being moved close together in memory.

pub fn compress_and_shrink_with<F: FnMut(P, &mut T, P)>(&mut self, map: F)

The same as ChainNoGenArena::compress_and_shrink except that map is run on every (P, &mut T, P) with the first P being the old Ptr and the last being the new Ptr.

pub fn from_arena( arena: Arena<P, LinkNoGen<P, T>>, ) -> Result<Self, &'static str>

Creates a ChainNoGenArena<P, T> directly from an Arena<P, LinkNoGen<P, T>>. Returns an error if interlink transitivity fails to hold.

pub fn clone_from_with<U, F: FnMut(P, &LinkNoGen<P, U>) -> T>( &mut self, source: &ChainNoGenArena<P, U>, map: F, )

Has the same properties of Arena::clone_from_with, preserving interlinks as well.

pub fn clone_to_chain_arena<U, F: FnMut(P, &T) -> U>( &self, chain_arena: &mut ChainArena<P, U>, map: F, )

Overwrites arena (dropping all preexisting T, overwriting the generation counter, and reusing capacity) with the Ptr mapping of self, except that the interlink structure has been dropped.

pub fn clone_to_arena<U, F: FnMut(P, &LinkNoGen<P, T>) -> U>( &self, arena: &mut Arena<P, U>, map: F, )

Overwrites arena (dropping all preexisting T, overwriting the generation counter, and reusing capacity) with the Ptr mapping of self, except that the interlink structure has been dropped.

impl<P: Ptr, T> ChainNoGenArena<P, T>

All the iterators here can return values in arbitrary order, except for ChainNoGenArena::advancer_chain.

pub fn advancer(&self) -> PtrAdvancer<P, T>

Advances over every valid Ptr in self.

Has the same properties as crate::Arena::advancer

pub fn advancer_chain(&self, p_init: P::Inx) -> ChainPtrAdvancer<P, T>

Advances over every valid Ptr in the chain that contains p_init. This does not support invalidating Ptrs or changing the interlinks of the chain of p_init during the loop.

Note

This handles cyclical chains, however if links or interlinks of the chain that contains p_init are invalidated during the loop, or if the chain starts as noncyclical and is reconnected to become cyclical during the loop, it can lead to a loop where the same Ptr can be returned multiple times. There is a internal fail safe that prevents non-termination.

pub fn ptrs(&self) -> Ptrs<'_, P, LinkNoGen<P, T>>

Iteration over all valid Ps in the arena

pub fn vals(&self) -> Vals<'_, P, LinkNoGen<P, T>>

Iteration over &LinkNoGen<P, T>

pub fn vals_mut(&mut self) -> ValsLinkMut<'_, P, T>

Mutable iteration over LinkNoGen<P, &mut T>

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

Iteration over (P, &LinkNoGen<P, T>) tuples

pub fn iter_chain(&self, p_init: P::Inx) -> IterChain<'_, P, T>

Iteration over (P, &LinkNoGen<P, T>) tuples corresponding to all links in the chain that p_init is connected to, according to the order of ChainNoGenArena::advancer_chain

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

Mutable iteration over (P, LinkNoGen<P, &mut T>) tuples

pub fn drain(&mut self) -> Drain<'_, P, LinkNoGen<P, T>>

Same as crate::Arena::drain

pub fn capacity_drain(self) -> CapacityDrain<P, LinkNoGen<P, T>>

Same as crate::Arena::capacity_drain

pub fn compress_and_shrink_recaster(&mut self) -> Arena<P, P>

Performs ChainNoGenArena::compress_and_shrink and returns an Arena<P, P> that can be used for Recasting

Trait Implementations

impl<P: Ptr, T> ArenaTrait for ChainNoGenArena<P, T>

fn insert(&mut self, link: Self::E) -> P

Uses ChainArena::insert with link.prev_next() and link.t

type Adv = PtrAdvancer<P, T>

type E = LinkNoGen<P, T>

The element type

type GetMutRes<'a> = LinkNoGen<P, &'a mut T> where Self: 'a

type GetRes<'a> = &'a <ChainNoGenArena<P, T> as ArenaTrait>::E where Self: 'a

type P = P

The Ptr type

fn new() -> Self

fn capacity(&self) -> usize

fn generation(&self) -> P::Gen

fn len(&self) -> usize

fn is_empty(&self) -> bool

fn remove(&mut self, p: Self::P) -> Option<Self::E>

fn get(&self, p: Self::P) -> Option<&Self::E>

fn get_mut(&mut self, p: Self::P) -> Option<LinkNoGen<P, &mut T>>

fn advancer(&self) -> Self::Adv

fn contains(&self, p: Self::P) -> bool

fn clear(&mut self)

fn clear_and_shrink(&mut self)

impl<P: Ptr, T: Clone> Clone for ChainNoGenArena<P, T>

Implemented if T: Clone.

fn clone(&self) -> Self

Has the Ptr preserving properties of Arena::clone

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

Has the Ptr and capacity preserving properties of Arena::clone_from

impl<P: Ptr, T: Debug> Debug for ChainNoGenArena<P, T>

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

Formats the value using the given formatter.

impl<P: Ptr, T> Default for ChainNoGenArena<P, T>

fn default() -> Self

Returns the “default value” for a type.

impl<P: Ptr, T> FromIterator<T> for ChainNoGenArena<P, T>

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

Inserts as single link chains

impl<P: Ptr, T, B: Borrow<P>> Index<B> for ChainNoGenArena<P, T>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<P: Ptr, T, B: Borrow<P>> IndexMut<B> for ChainNoGenArena<P, T>

fn index_mut(&mut self, index: B) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, P: Ptr, T> IntoIterator for &'a ChainNoGenArena<P, T>

type IntoIter = Iter<'a, P, LinkNoGen<P, T>>

Which kind of iterator are we turning this into?

type Item = (P, &'a LinkNoGen<P, T>)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, P: Ptr, T> IntoIterator for &'a mut ChainNoGenArena<P, T>

fn into_iter(self) -> Self::IntoIter

This returns an IterMut. Use ChainNoGenArena::drain for by-value consumption.

type IntoIter = IterLinkMut<'a, P, T>

Which kind of iterator are we turning this into?

type Item = (P, LinkNoGen<P, &'a mut T>)

The type of the elements being iterated over.

impl<P: Ptr, T> IntoIterator for ChainNoGenArena<P, T>

type IntoIter = CapacityDrain<P, LinkNoGen<P, T>>

Which kind of iterator are we turning this into?

type Item = (P, LinkNoGen<P, T>)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<P: Ptr, T: PartialEq> PartialEq for ChainNoGenArena<P, T>

fn eq(&self, other: &ChainNoGenArena<P, T>) -> bool

Checks if all (P, LinkNoGen<P, T>) pairs are equal. This is sensitive to Ptr indexes and generation counters, but does not compare arena capacities or self.generation().

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<P: Ptr, I, T: Recast<I>> Recast<I> for ChainNoGenArena<P, T>

fn recast<R: Recaster<Item = I>>( &mut self, recaster: &R, ) -> Result<(), <R as Recaster>::Item>

Rewrites all the <R as Recaster>::Items of self according to the <recaster as Recaster>::map.

impl<P: Ptr, T: Eq> Eq for ChainNoGenArena<P, T>