Struct stack_graphs::arena::Deque

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

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 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
) -> bool where
    F: FnMut(&T, &T) -> bool, 

pub fn cmp_with<F>(
    self,
    arena: &mut DequeArena<T>,
    other: Deque<T>,
    cmp: F
) -> Ordering where
    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> Copy for Deque<T>