Struct coca::collections::deque::Deque

source · [−]
pub struct Deque<T, S: Storage<ArrayLayout<T>>, I: Capacity> { /* private fields */ }
Expand description

A double-ended queue implemented with a ring buffer.

The “default” usage of this type as a queue is to use push_back to add to the queue, and pop_front to remove from it.

Since Deque is a ring buffer, its elements are not necessarily contiguous in memory. If you want to access the elements as a single slice, such as for efficient sorting, you can use make_contiguous. It rotates the Deque so that its elements do not wrap, and returns a mutable slice to the now contiguous element sequence.

Deque is designed to work with any capacity between 2 and usize::max_value() / 2 (inclusive). As such, almost all indexing operations are implemented as storage[(offset + index) % capacity]; you may therefore observe disproportionate performance benefits when the capacity is known at compile time, especially with powers of 2, which allow this expression to be optimized to storage[(offset + index) & (CAPACITY - 1)].

Implementations

Decomposes a Deque<T, S, I> into its raw parts.

Returns the raw storage type, the front offset and the length of the deque in elements. These are the same arguments in the same order as the arguments to from_raw_parts.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 3];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_front(1);
deque.push_back(2);
let (buf, front, len) = deque.into_raw_parts();
unsafe {
    assert_eq!(buf[2].assume_init(), 1);
    assert_eq!(buf[0].assume_init(), 2);
    // buf[1] is uninitialized
}

Creates a Deque<T, S, I> directly from its raw parts.

Safety

Callers must ensure that the first length values after front (modulo buf.capacity()) are initialized, and that front and length are both less than or equal to buf.capacity().

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 3];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_front(1);
deque.push_back(2);

let (buf, front, len) = deque.into_raw_parts();
let deque = unsafe { coca::collections::SliceDeque::from_raw_parts(buf, front, len) };
assert_eq!(deque, &[1, 2]);

Returns the number of elements the deque can hold.

Returns the number of elements currently in the deque.

Returns true exactly when the deque contains zero elements.

Returns true exactly when the deque contains the maximum number of elements.

Returns true if the Deque contains an element equal to the given value.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 3];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(0);
deque.push_back(1);
assert_eq!(deque.contains(&1), true);
assert_eq!(deque.contains(&10), false);

Returns a reference to the element at the given index, or None if the index is out of bounds.

The element at index 0 is the front of the queue.

Returns a mutable reference to the element at the given index, or None if the index is out of bounds.

The element at index 0 is the front of the queue.

Returns a reference to the front element, or None if the Deque is empty.

Returns a mutable reference to the front element, or None if the Deque is empty.

Returns a reference to the back element, or None if the Deque is empty.

Returns a mutable reference to the back element, or None if the Deque is empty.

Removes the first element and returns it, or None if the Deque is empty.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 3];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(1);
deque.push_back(2);
assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_front(), Some(2));
assert_eq!(deque.pop_front(), None);

Removes the last element and returns it, or None if the Deque is empty.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 3];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(1);
deque.push_back(3);
assert_eq!(deque.pop_back(), Some(3));
assert_eq!(deque.pop_back(), Some(1));
assert_eq!(deque.pop_back(), None);

Prepends an element to the front of the Deque, returning Err(value) if it is already full.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 3];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
assert!(deque.try_push_front(1).is_ok());
assert!(deque.try_push_front(2).is_ok());
assert!(deque.try_push_front(3).is_ok());
assert_eq!(deque.try_push_front(4), Err(4));

Prepends an element to the front of the Deque.

Panics

Panics if the deque is already at capacity. See try_push_front for a checked variant that never panics.

Prepends an element to the front of the Deque, replacing and returning the back element if the Deque is already full.

Examples
let mut deque = coca::collections::InlineDeque::<&'static str, 2>::new();
 
assert!(deque.force_push_front("Alice").is_none());
assert!(deque.force_push_front("Bob").is_none());
assert_eq!(deque.force_push_front("Charlie"), Some("Alice"));
 
assert_eq!(deque[0], "Charlie");
assert_eq!(deque[1], "Bob");

Appends an element to the back of the Deque, returning Err(value) if it is already full.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 3];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
assert!(deque.try_push_back(1).is_ok());
assert!(deque.try_push_back(2).is_ok());
assert!(deque.try_push_back(3).is_ok());
assert_eq!(deque.try_push_back(4), Err(4));

Appends an element to the back of the Deque.

Panics

Panics if the deque is already at capacity. See try_push_back for a checked variant that never panics.

Appends an element to the back of the Deque, replacing and returning the front element if the Deque is already full.

Examples
let mut deque = coca::collections::InlineDeque::<&'static str, 2>::new();
 
assert!(deque.force_push_back("Hello").is_none());
assert!(deque.force_push_back("World").is_none());
assert_eq!(deque.force_push_back("Peace"), Some("Hello"));
 
assert_eq!(deque[0], "World");
assert_eq!(deque[1], "Peace");

Shortens the Deque, keeping the first len elements and dropping the rest.

If len is greater than the deque’s current length, this has no effect.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(5);
deque.push_back(10);
deque.push_back(15);
assert_eq!(deque.as_slices(), (&[5, 10, 15][..], &[][..]));
deque.truncate(1);
assert_eq!(deque.as_slices(), (&[5][..], &[][..]));

Clears the Deque, dropping all values.

Swaps the elements at indices i and j.

i and j may be equal.

The element at index 0 is the front of the queue.

Panics

Panics if either index is out of bounds.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(2);
deque.push_back(1);
deque.push_front(3);
deque.swap(0, 2);
assert_eq!(deque, &[1, 2, 3]);

Removes an element from anywhere in the Deque and returns it, replacing it with the front element.

This does not preserve ordering, but is O(1).

Returns None if index is out of bounds.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(1);
deque.push_back(2);
deque.push_back(3);
assert_eq!(deque.swap_remove_front(2), Some(3));
assert_eq!(deque, &[2, 1]);

Removes an element from anywhere in the Deque and returns it, replacing it with the back element.

This does not preserve ordering, but is O(1).

Returns None if index is out of bounds.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(1);
deque.push_back(2);
deque.push_back(3);
assert_eq!(deque.swap_remove_back(0), Some(1));
assert_eq!(deque, &[3, 2]);

Inserts an element at index within the Deque, returning Err(value) if it is full.

Whichever end is closer to the insertion point will be moved to make room, and all elements in between will be shifted to new positions.

The element at index 0 is the front of the queue.

Panics

Panics if index is greater than the deque’s length.

Examples
let mut backing_region = [core::mem::MaybeUninit::<char>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<char>::from(&mut backing_region[..]);
deque.push_back('a');
deque.push_back('b');
deque.push_back('c');
assert_eq!(deque, &['a', 'b', 'c']);

assert!(deque.try_insert(1, 'd').is_ok());
assert_eq!(deque, &['a', 'd', 'b', 'c']);

Inserts an element at index within the Deque.

Whichever end is closer to the insertion point will be moved to make room, and all elements in between will be shifted to new positions.

The element at index 0 is the front of the queue.

Panics

Panics if index is greater than the deque’s length, or if the deque is already at capacity. See try_insert for a checked version.

Removes and returns the element at index from the Deque, or None if index is out of bounds.

Whichever end is closer to the removal point will be moved to fill the gap, and all affected elements will be shifted to new positions.

The element at index 0 is the front of the queue.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(1);
deque.push_back(2);
deque.push_back(3);
assert_eq!(deque.remove(1), Some(2));
assert_eq!(deque, &[1, 3]);

Places an element at position index within the Deque, returning the element previously stored there.

Panics

Panics if index is greater than or equal to the deque’s length.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(1);
deque.push_back(2);
deque.push_back(4);
assert_eq!(deque.replace(2, 3), 4);
assert_eq!(deque, &[1, 2, 3]);

Retains only the elements specified by the predicate.

In other words, remove all elements e such that f(&e) returns false. This method operates in place, visiting each element exactly once in the original order, and preserves the order of the retained elements.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(1);
deque.push_back(2);
deque.push_back(3);
deque.push_back(4);
deque.retain(|&x| x % 2 == 0);
assert_eq!(deque, &[2, 4]);

Rotates the Deque mid places to the left.

Equivalently,

  • Rotates mid into the first position.
  • Pops the first mid items and pushes them to the end.
  • Rotates len() - mid places to the right.
Panics

Panics if mid is greater than the deque’s length. Note that mid == len() does not panic and is a no-op rotation.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 16];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
for x in 0..10 { deque.push_back(x); }
for i in 1..10 {
    deque.rotate_left(3);
    assert_eq!(deque.front(), Some(&(i * 3 % 10)));
}
deque.rotate_left(3);
assert_eq!(deque, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

Rotates the Deque k places to the right.

Equivalently,

  • Rotates the first item into position k.
  • Pops the last k items and pushes them to the front.
  • Rotates len() - k places to the left.
Panics

Panics if k is greater than the deque’s length. Note that k == len() does not panic and is a no-op rotation.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 16];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
for x in 0..10 { deque.push_back(x); }
for i in 1..10 {
    deque.rotate_right(3);
    assert_eq!(deque.get(i * 3 % 10), Some(&0));
}
deque.rotate_right(3);
assert_eq!(deque, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

Returns a pair of slices which contain, in order, the contents of the Deque.

If make_contiguous was previously called, all elements of the deque will be in the first slice and the second slice will be empty.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(2);
deque.push_back(1);
deque.push_front(3);
assert_eq!(deque.as_slices(), (&[3][..], &[2, 1][..]));

Returns a pair of mutable slices which contain, in order, the contents of the Deque.

If make_contiguous was previously called, all elements of the deque will be in the first slice and the second slice will be empty.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(2);
deque.push_back(1);
deque.push_front(3);
deque.as_mut_slices().0[0] = 1;
deque.as_mut_slices().1[1] = 3;
assert_eq!(deque.as_slices(), (&[1][..], &[2, 3][..]));

Rearranges the internal storage of the Deque so it is one contiguous slice, which is then returned.

This does not change the order of the inserted elements. As it returns a mutable slice, this can be used to sort or binary search a deque.

Once the internal storage is contiguous, the as_slices and as_mut_slices methods will return the entire contents of the Deque in a single slice.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(2);
deque.push_back(1);
assert_eq!(deque, &[2, 1]);

deque.push_front(3);
assert_eq!(deque, &[3, 2, 1]);

Returns a front-to-back iterator.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(5);
deque.push_back(3);
deque.push_back(4);

let mut it = deque.iter();
assert_eq!(it.next(), Some(&5));
assert_eq!(it.next(), Some(&3));
assert_eq!(it.next(), Some(&4));
assert!(it.next().is_none());

Returns a front-to-back iterator that returns mutable references.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 4];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.push_back(5);
deque.push_back(3);
deque.push_back(4);
for num in deque.iter_mut() {
    *num = *num - 2;
}
assert_eq!(deque, &[3, 1, 2]);

Creates an iterator that covers the specified range in the Deque.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the deque.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 8];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.extend(1..=5);
assert_eq!(deque, &[1, 2, 3, 4, 5]);

let mut it = deque.range(2..4);
assert_eq!(it.next(), Some(&3));
assert_eq!(it.next(), Some(&4));
assert!(it.next().is_none());

Creates a mutable iterator that covers the specified range in the Deque.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the deque.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 8];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.extend(1..=5);
assert_eq!(deque, &[1, 2, 3, 4, 5]);

deque.range_mut(2..4).for_each(|x| *x *= 2);
assert_eq!(deque, &[1, 2, 6, 8, 5]);

Creates a draining iterator that removes the specified range in the deque and yields the removed items.

When the iterator is dropped, all elements in the range are removed from the deque, even if the iterator was not fully consumed. If the iterator is not dropped (with core::mem::forget for example), it is unspecified how many elements are removed.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the deque.

Examples
let mut backing_region = [core::mem::MaybeUninit::<i32>::uninit(); 8];
let mut deque = coca::collections::SliceDeque::<i32>::from(&mut backing_region[..]);
deque.extend(1..=5);

let mut drained = deque.drain(2..4);
assert_eq!(drained.next(), Some(3));
assert_eq!(drained.next(), Some(4));
assert!(drained.next().is_none());

drop(drained);
assert_eq!(deque, [1, 2, 5]);

// A full range clears the deque
deque.drain(..);
assert!(deque.is_empty());
This is supported on crate feature alloc only.

Creates an empty AllocDeque with the specified capacity.

Panics

Panics if capacity cannot be represented by the a usize.

Constructs a new deque backed by an inline array.

Panics

Panics if C cannot be represented as a value of type I.

Examples
let deque = coca::collections::InlineDeque::<u32, 7>::new();
assert_eq!(deque.len(), 0);
assert_eq!(deque.capacity(), 7);

Trait Implementations

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Returns the “default value” for a type. Read more

Executes the destructor for this type. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Converts a contiguous block of memory into an empty deque.

Panics

This may panic if the index type I cannot represent buf.capacity().

Performs the conversion.

Feeds this value into the given Hasher. Read more

Feeds a slice of this type into the given Hasher. Read more

The returned type after indexing.

Performs the indexing (container[index]) operation. Read more

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

Converts the Deque into a front-to-back iterator yielding elements by value.

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

This method returns an Ordering between self and other. Read more

Compares and returns the maximum of two values. Read more

Compares and returns the minimum of two values. Read more

Restrict a value to a certain interval. Read more

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method returns an ordering between self and other values if one exists. Read more

This method tests less than (for self and other) and is used by the < operator. Read more

This method tests less than or equal to (for self and other) and is used by the <= operator. Read more

This method tests greater than (for self and other) and is used by the > operator. Read more

This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Performs the conversion.

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

🔬 This is a nightly-only experimental API. (toowned_clone_into)

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.