Struct Stack 

pub struct Stack<T> { /* private fields */ }

Implementations

impl<T> Stack<T>

pub const fn new() -> Self

Constructs a new, empty Stack<T>.

The stack will not allocate until elements are pushed onto it.

Examples

use bump_stack::Stack;

let mut stack: Stack<i32> = Stack::new();

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty Stack<T> with at least the specified capacity.

The stack will be able to hold at least capacity elements without new allocations. This method is allowed to allocate for more elements than capacity. If capacity is zero, the stack will not allocate.

If it is important to know the exact allocated capacity of a Stack, always use the capacity method after construction.

For Stack<T> where T is a zero-sized type, there will be no allocation and the capacity will always be usize::MAX.

Examples

let mut stk = Stack::with_capacity(10);

// The stack contains no items, even though it has capacity for more
assert_eq!(stk.len(), 0);
assert!(stk.capacity() >= 10);

// These are all done without additional allocations...
for i in 0..10 {
    stk.push(i);
}
assert_eq!(stk.len(), 10);
assert!(stk.capacity() >= 10);

// ...but this may make the stack allocate a new chunk
stk.push(11);
assert_eq!(stk.len(), 11);
assert!(stk.capacity() >= 11);

// A stack of a zero-sized type will always over-allocate, since no
// allocation is necessary
let stk_units = Stack::<()>::with_capacity(10);
assert_eq!(stk_units.capacity(), usize::MAX);

pub const fn capacity(&self) -> usize

Returns the total number of elements the stack can hold without additional allocations.

Examples

let mut stk = Stack::with_capacity(10);
stk.push(42);
assert!(stk.capacity() >= 10);

A stack with zero-sized elements will always have a capacity of usize::MAX:

#[derive(Clone)]
struct ZeroSized;

assert_eq!(std::mem::size_of::<ZeroSized>(), 0);
let stk = Stack::<ZeroSized>::with_capacity(0);
assert_eq!(stk.capacity(), usize::MAX);

pub const fn len(&self) -> usize

Returns the number of elements in the stack.

Examples

let stk = Stack::from([1, 2, 3]);
assert_eq!(stk.len(), 3);

pub const fn is_empty(&self) -> bool

Returns true if the stack contains no elements.

Examples

let mut s = Stack::new();
assert!(s.is_empty());

s.push(1);
assert!(!s.is_empty());

pub fn first(&self) -> Option<&T>

Returns a reference to the first element of the stack, or None if it is empty.

Examples

let mut s = Stack::new();
assert_eq!(None, s.first());

s.push(42);
assert_eq!(Some(&42), s.first());

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

Returns a mutable reference to the first element of the slice, or None if it is empty.

Examples

let mut s = Stack::new();
assert_eq!(None, s.first_mut());

s.push(1);
if let Some(first) = s.first_mut() {
    *first = 5;
}
assert_eq!(s.first(), Some(&5));

pub fn last(&self) -> Option<&T>

Returns the reference to last element of the stack, or None if it is empty.

Examples

let mut stk = Stack::new();
assert_eq!(None, stk.last());

stk.push(1);
assert_eq!(Some(&1), stk.last());

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

Returns a mutable reference to the last item in the stack, or None if it is empty.

Examples

let mut stk = Stack::new();
assert_eq!(None, stk.last_mut());

stk.push(5);
assert_eq!(Some(&mut 5), stk.last_mut());

if let Some(last) = stk.last_mut() {
    *last = 10;
}
assert_eq!(Some(&mut 10), stk.last_mut());

pub fn push(&self, value: T) -> &T

Appends an element to the stack returning a reference to it.

Panics

Panics if the global allocator cannot allocate a new chunk of memory.

Examples

let stk = Stack::new();
let new_element = stk.push(3);

assert_eq!(new_element, &3);
assert_eq!(stk, [3]);

Time complexity

Takes amortized O(1) time. If the stack’s current chunk of memory is exhausted, it tries to use the cached one if it exists, otherwise it tries to allocate a new chunk.

If the new chunk of memory is too big, it tries to divide the capacity by two and allocate it again until it reaches the minimum capacity. If it does, it panics.

pub fn push_mut(&mut self, value: T) -> &mut T

Appends an element to the stack, returning a mutable reference to it.

Panics

Panics if there is no way to allocate memory for a new capacity.

Examples

let mut stk = Stack::from([1, 2]);
let last = stk.push_mut(3);
assert_eq!(*last, 3);
assert_eq!(stk, [3, 2, 1]);

let last = stk.push_mut(3);
*last += 1;
assert_eq!(stk, [4, 3, 2, 1]);

Time complexity

Takes amortized O(1) time. If the stack’s current chunk of memory is exhausted, it tries to use the cached one if it exists, otherwise it tries to allocate a new chunk.

If the new chunk of memory is too big, it tries to divide the capacity by two and allocate it again until it reaches the minimum capacity. If it does, it panics.

pub fn push_with<F>(&self, f: F) -> &T

where F: FnOnce() -> T,

Pre-allocate space for an element in this stack, initializes it using the closure, and returns a reference to the new element.

Examples

let stk = Stack::new();
let new_element = stk.push_with(|| 3);

assert_eq!(new_element, &3);
assert_eq!(stk, [3]);

Time complexity

Takes amortized O(1) time. If the stack’s current chunk of memory is exhausted, it tries to use the cached one if it exists, otherwise it tries to allocate a new chunk.

If the new chunk of memory is too big, it tries to divide the capacity by two and allocate it again until it reaches the minimum capacity. If it does, it panics.

pub fn push_mut_with<F>(&mut self, f: F) -> &mut T

where F: FnOnce() -> T,

Pre-allocate space for an element in this stack, initializes it using the closure, and returns a mutable reference to the new element.

Examples

let mut stk = Stack::from([1, 2]);
let last = stk.push_mut(3);
assert_eq!(*last, 3);
assert_eq!(stk, [3, 2, 1]);

let last = stk.push_mut(3);
*last += 1;
assert_eq!(stk, [4, 3, 2, 1]);

Time complexity

Takes amortized O(1) time. If the stack’s current chunk of memory is exhausted, it tries to use the cached one if it exists, otherwise it tries to allocate a new chunk.

If the new chunk of memory is too big, it tries to divide the capacity by two and allocate it again until it reaches the minimum capacity. If it does, it panics.

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

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

Examples

let mut stk = Stack::from([1, 2, 3]);
assert_eq!(stk.pop(), Some(3));
assert_eq!(stk, [2, 1]);

pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T>

Removes and returns the last element from a stack if the predicate returns true, or None if the predicate returns false or the stack is empty (the predicate will not be called in that case).

Examples

let mut stk = Stack::from([1, 2, 3, 4]);
let pred = |x: &mut i32| *x % 2 == 0;

assert_eq!(stk.pop_if(pred), Some(4));
assert_eq!(stk, [3, 2, 1]);
assert_eq!(stk.pop_if(pred), None);

pub fn clear(&mut self)

Clears the stack, dropping all elements.

This method leaves the biggest chunk of memory for future allocations.

The order of dropping elements is not defined.

Examples

let mut stk = Stack::from([1, 2, 3]);

stk.clear();

assert!(stk.is_empty());
assert!(stk.capacity() > 0);

pub fn contains(&self, value: &T) -> bool

where T: PartialEq,

Returns true if the stack contains an element with the given value.

This operation is O(n).

Examples

let stk = Stack::from([3, 8, 12]);
assert!(stk.contains(&8));
assert!(!stk.contains(&20));

pub fn to_vec(&self) -> Vec<T>

where T: Clone,

Copies self into a Vec.

Examples

let s = Stack::from([10, 40, 30]);
let v = s.to_vec();
assert_eq!(v, &[30, 40, 10]);

pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T>

Returns an iterator over the stack.

The iterator yields all items’ references in inverted order of their insertion, corresponding to a LIFO structure behavior.

Examples

let stk = Stack::from([1, 2, 4]);
let mut iterator = stk.iter();

assert_eq!(iterator.next(), Some(&4));
assert_eq!(iterator.next(), Some(&2));
assert_eq!(iterator.next(), Some(&1));
assert_eq!(iterator.next(), None);

Since Stack allows to push new elements using immutable reference to itself, you can push during iteration. But iteration is running over elements existing at the moment of the iterator creating. It guarantees that you won’t get infinite loop.

let stk = Stack::from([1, 2, 4]);

for elem in stk.iter() {
    stk.push(*elem);
}
assert_eq!(stk.len(), 6);
assert_eq!(stk, [1, 2, 4, 4, 2, 1]);

pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T>

Returns a mutable iterator over the stack.

The iterator yields all items’ references in inverted order of their insertion, corresponding to a LIFO structure behavior.

Examples

let mut stk = Stack::from([1, 2, 4]);

for elem in stk.iter_mut() {
    *elem *= 2;
}

assert_eq!(&stk, &[8, 4, 2]);

pub fn chunks(&self) -> impl DoubleEndedIterator<Item = &[T]>

Returns an iterator over slices corresponding to the stack’s memory chunks.

The iterator yields all items’ references in inverted order of their insertion, corresponding to a LIFO structure behavior.

Examples

let stk = Stack::from([0, 1, 2]);
assert_eq!(stk.chunks().collect::<Vec<_>>(), [&[2, 1, 0]]);

// fill up the first chunk
for i in 3..stk.capacity() {
    stk.push(i);
}
assert_eq!(stk.chunks().count(), 1);

// create a new chunk
stk.push(42);
assert_eq!(stk.chunks().count(), 2);

pub fn chunks_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut [T]>

Returns an iterator over mutable slices corresponding to the stack’s memory chunks.

The iterator yields all items’ references in inverted order of their insertion, corresponding to a LIFO structure behavior.

Examples

let mut stk = Stack::from([0, 1, 2]);

let chunk = stk.chunks_mut().next().unwrap();
assert_eq!(chunk, [2, 1, 0]);
chunk[0] = 42;
assert_eq!(chunk, [42, 1, 0]);

Trait Implementations

impl<T> Debug for Stack<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for Stack<T>

fn default() -> Self

Creates an empty Stack<T>.

The stack will not allocate until elements are pushed onto it.

impl<T> Drop for Stack<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> From<&[T]> for Stack<T>

where T: Clone,

fn from(slice: &[T]) -> Self

Creates a Stack<T> with a chunk big enough to contain N items and fills it by cloning slice’s items.

impl<T, const N: usize> From<&[T; N]> for Stack<T>

where T: Clone,

fn from(slice: &[T; N]) -> Self

Creates a Stack<T> with a chunk big enough to contain N items and fills it by cloning slice’s items.

impl<T> From<&mut [T]> for Stack<T>

where T: Clone,

fn from(slice: &mut [T]) -> Self

Creates a Stack<T> with a chunk big enough to contain N items and fills it by cloning slice’s items.

impl<T, const N: usize> From<&mut [T; N]> for Stack<T>

where T: Clone,

fn from(slice: &mut [T; N]) -> Self

Creates a Stack<T> with a chunk big enough to contain N items and fills it by cloning slice’s items.

impl<T, const N: usize> From<[T; N]> for Stack<T>

where T: Clone,

fn from(array: [T; N]) -> Self

Creates a Stack<T> with a chunk big enough to contain N items and fills it by cloning array’s items.

impl<T> FromIterator<T> for Stack<T>

where T: Clone,

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

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a Stack<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut Stack<T>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for Stack<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, U> PartialEq<&[U]> for Stack<T>

where T: PartialEq<U>,

fn eq(&self, other: &&[U]) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U, const N: usize> PartialEq<&[U; N]> for Stack<T>

where T: PartialEq<U>,

fn eq(&self, other: &&[U; N]) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U> PartialEq<&mut [U]> for Stack<T>

where T: PartialEq<U>,

fn eq(&self, other: &&mut [U]) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U, const N: usize> PartialEq<&mut [U; N]> for Stack<T>

where T: PartialEq<U>,

fn eq(&self, other: &&mut [U; N]) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U> PartialEq<[U]> for Stack<T>

where T: PartialEq<U>,

fn eq(&self, other: &[U]) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U, const N: usize> PartialEq<[U; N]> for Stack<T>

where T: PartialEq<U>,

fn eq(&self, other: &[U; N]) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U, const N: usize> PartialEq<Stack<U>> for &[T; N]

where T: PartialEq<U>,

fn eq(&self, other: &Stack<U>) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U, const N: usize> PartialEq<Stack<U>> for &mut [T; N]

where T: PartialEq<U>,

fn eq(&self, other: &Stack<U>) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T, U, const N: usize> PartialEq<Stack<U>> for [T; N]

where T: PartialEq<U>,

fn eq(&self, other: &Stack<U>) -> bool

Tests for self and other values to be equal, and is used by ==.

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<T> Send for Stack<T>

where T: Send,