Struct stack_graphs::arena::Deque

#[repr(C)]
pub struct Deque<T> { /* private fields */ }

An arena-allocated deque.

Under the covers, this is implemented as a List. Because these lists are singly-linked, we can only add elements to, and remove them from, one side of the list.

To handle this, each deque stores its contents either forwards or backwards. We automatically shift between these two representations as needed, depending on the requirements of each method.

Note that we cache the result of reversing the list, so it should be quick to switch back and forth between representations as long as you have not added any additional elements to the deque! If performance is critical, you should ensure that you don’t call methods in a pattern that causes the deque to reverse itself each time you add an element.

Implementations

impl<T> Deque<T>

pub fn new_arena() -> DequeArena<T>

Creates a new DequeArena that will manage deques of this type.

pub fn is_empty(&self) -> bool

Returns whether this deque is empty.

pub fn empty() -> Deque<T>

Returns an empty deque.

pub fn have_reversal(&self, arena: &DequeArena<T>) -> bool

Returns whether we have already calculated the reversal of this deque.

pub fn iter_unordered<'a>(
    &self,
    arena: &'a DequeArena<T>
) -> impl Iterator<Item = &'a T> + 'a

Returns an iterator over the contents of this deque, with no guarantee about the ordering of the elements. (By not caring about the ordering of the elements, you can call this method regardless of which direction the deque’s elements are currently stored. And that, in turn, means that we only need shared access to the arena, and not mutable access to it.)

impl<T> Deque<T>where
    T: Clone,

pub fn ensure_backwards(&mut self, arena: &mut DequeArena<T>)

Ensures that this deque has computed its backwards-facing list of elements.

pub fn ensure_forwards(&mut self, arena: &mut DequeArena<T>)

Ensures that this deque has computed its forwards-facing list of elements.

pub fn push_front(&mut self, arena: &mut DequeArena<T>, element: T)

Pushes a new element onto the front of this deque.

pub fn push_back(&mut self, arena: &mut DequeArena<T>, element: T)

Pushes a new element onto the back of this deque.

pub fn pop_front<'a>(&mut self, arena: &'a mut DequeArena<T>) -> Option<&'a T>

Removes and returns the element from the front of this deque. If the deque is empty, returns None.

pub fn pop_back<'a>(&mut self, arena: &'a mut DequeArena<T>) -> Option<&'a T>

Removes and returns the element from the back of this deque. If the deque is empty, returns None.

pub fn iter<'a>(
    &self,
    arena: &'a mut DequeArena<T>
) -> impl Iterator<Item = &'a T> + 'a

Returns an iterator over the contents of this deque in a forwards direction.

pub fn iter_reversed<'a>(
    &self,
    arena: &'a mut DequeArena<T>
) -> impl Iterator<Item = &'a T> + 'a

Returns an iterator over the contents of this deque in a backwards direction.

impl<T> Deque<T>where
    T: Clone,

pub fn equals_with<F>(
    self,
    arena: &mut DequeArena<T>,
    other: Deque<T>,
    eq: F
) -> boolwhere
    F: FnMut(&T, &T) -> bool,

pub fn cmp_with<F>(
    self,
    arena: &mut DequeArena<T>,
    other: Deque<T>,
    cmp: F
) -> Orderingwhere
    F: FnMut(&T, &T) -> Ordering,

impl<T> Deque<T>where
    T: Clone + Eq,

pub fn equals(self, arena: &mut DequeArena<T>, other: Deque<T>) -> bool

impl<T> Deque<T>where
    T: Clone + Ord,

pub fn cmp(self, arena: &mut DequeArena<T>, other: Deque<T>) -> Ordering

impl<T> Deque<T>

pub fn iter_reused<'a>(
    &self,
    arena: &'a DequeArena<T>
) -> impl Iterator<Item = &'a T> + 'a

Returns an iterator over the contents of this deque in a forwards direction, assuming that we have already computed its forwards-facing list of elements via ensure_forwards. Panics if we haven’t already computed it.

pub fn iter_reversed_reused<'a>(
    &self,
    arena: &'a DequeArena<T>
) -> impl Iterator<Item = &'a T> + 'a

Returns an iterator over the contents of this deque in a backwards direction, assuming that we have already computed its backwards-facing list of elements via ensure_backwards. Panics if we haven’t already computed it.

Trait Implementations

impl<T> Clone for Deque<T>

fn clone(&self) -> Deque<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Niche for Deque<T>where
    ReversibleList<T>: Niche,

type Output = MaybeUninit<Deque<T>>

The type that is used to store values of Self inside of a ControlledOption. This might be Self itself, if your niche is a valid instance of the type, but which violates some runtime constraint. But if you cannot easily create your niche as an instance of Self, you can use some other type, you can use some other type instead.

fn none() -> Self::Output

Returns the niche value for this type that should be used to represent None for a ControlledOption.

fn is_none(value: &Self::Output) -> bool

Returns whether value is the niche value for this type.

fn into_some(value: Self) -> Self::Output

Transforms a non-niche value of this type into its Output type. When Output is Self, this will be the identity function.

fn from_some(value: Self::Output) -> Self

Transforms a non-niche value of this type from its Output type. When Output is Self, this will be the identity function.

impl<T> Copy for Deque<T>