Struct bounded_vec_deque::BoundedVecDeque

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

A double-ended queue|ringbuffer with an upper bound on its length.

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 the queue. extend(), append(), and from_iter() push onto the back in this manner, and iterating over BoundedVecDeque goes front to back.

This type is a wrapper around VecDeque. Almost all of its associated functions delegate to VecDeque’s (after enforcing the length bound).

Capacity and reallocation

At the time of writing, VecDeque behaves as follows:

• It always keeps its capacity at one less than a power of two.
• It always keeps an allocation (unlike e.g. Vec, where new() does not allocate and the capacity can be reduced to zero).
• Its reserve_exact() is just an alias for reserve().

This behavior is inherited by BoundedVecDeque (because it is merely a wrapper). It is not documented by VecDeque (and is thus subject to change), but has been noted here because it may be surprising or undesirable.

Users may wish to use maximum lengths that are one less than powers of two to prevent (at least with the current VecDeque reallocation strategy) “wasted space” caused by the capacity growing beyond the maximum length.

Implementations

impl<T> BoundedVecDeque<T>

pub fn new(max_len: usize) -> Self

Creates a new, empty BoundedVecDeque.

The capacity is set to the length limit (as a result, no reallocations will be necessary unless the length limit is later raised).

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let deque: BoundedVecDeque<i32> = BoundedVecDeque::new(255);

assert!(deque.is_empty());
assert_eq!(deque.max_len(), 255);
assert!(deque.capacity() >= 255);

pub fn with_capacity(capacity: usize, max_len: usize) -> Self

Creates a new, empty BoundedVecDeque with space for at least capacity elements.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let deque: BoundedVecDeque<i32> = BoundedVecDeque::with_capacity(63, 255);

assert!(deque.is_empty());
assert_eq!(deque.max_len(), 255);
assert!(deque.capacity() >= 63);

pub fn from_iter<I>(iterable: I, max_len: usize) -> Self where
    I: IntoIterator<Item = T>, 

Creates a new BoundedVecDeque from an iterator or iterable.

At most max_len items are taken from the iterator.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let five_fives = ::std::iter::repeat(5).take(5);

let deque: BoundedVecDeque<i32> = BoundedVecDeque::from_iter(five_fives, 7);

assert!(deque.iter().eq(&[5, 5, 5, 5, 5]));

let mut numbers = 0..;

let deque: BoundedVecDeque<i32> = BoundedVecDeque::from_iter(numbers.by_ref(), 7);

assert!(deque.iter().eq(&[0, 1, 2, 3, 4, 5, 6]));
assert_eq!(numbers.next(), Some(7));

pub fn from_unbounded(vec_deque: VecDeque<T>, max_len: usize) -> Self

Creates a new BoundedVecDeque from a VecDeque.

If vec_deque contains more than max_len items, excess items are dropped from the back. If the capacity is greater than max_len, it is shrunk to fit.

Examples

use ::std::collections::VecDeque;
use ::bounded_vec_deque::BoundedVecDeque;

let unbounded = VecDeque::from(vec![42]);

let bounded = BoundedVecDeque::from_unbounded(unbounded, 255);

pub fn into_unbounded(self) -> VecDeque<T>

Converts the BoundedVecDeque to VecDeque.

This is a minimal-cost conversion.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let bounded = BoundedVecDeque::from_iter(vec![0, 1, 2, 3], 255);
let unbounded = bounded.into_unbounded();

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to an element in the VecDeque by index.

Returns None if there is no such element.

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

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(12);
deque.push_back(3);
deque.push_back(4);
deque.push_back(5);

if let Some(elem) = deque.get_mut(1) {
    *elem = 7;
}

assert!(deque.iter().eq(&[3, 7, 5]));

pub fn swap(&mut self, i: usize, j: usize)

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

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(12);
deque.push_back(3);
deque.push_back(4);
deque.push_back(5);
assert!(deque.iter().eq(&[3, 4, 5]));

deque.swap(0, 2);

assert!(deque.iter().eq(&[5, 4, 3]));

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

Reserves capacity for at least additional more elements to be inserted.

To avoid frequent reallocations, more space than requested may be reserved.

Panics

Panics if the requested new capacity exceeds the maximum length, or if the actual new capacity overflows usize.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(vec![1], 255);

deque.reserve(10);

assert!(deque.capacity() >= 11);

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

Reserves the minimum capacity for exactly additional more elements to be inserted.

Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore capacity cannot be relied upon to be precisely minimal. Prefer reserve() if future insertions are expected.

At the time of writing, this method is equivalent to reserve() because of VecDeque’s capacity management. It has been provided anyway for compatibility reasons. See the relevant section of the type-level documentation for details.

Panics

Panics if the requested new capacity exceeds the maximum length, or if the actual new capacity overflows usize.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(vec![1], 255);

deque.reserve_exact(10);

assert!(deque.capacity() >= 11);

pub fn reserve_maximum(&mut self)

Reserves enough capacity for the collection to be filled to its maximum length.

Does nothing if the capacity is already sufficient.

See the reserve_exact() documentation for caveats about capacity management.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(vec![1], 255);

deque.reserve_maximum();

assert!(deque.capacity() >= 255);

pub fn shrink_to_fit(&mut self)

Reduces the capacity as much as possible.

The capacity is reduced to as close to the length as possible. However, there are restrictions on how much the capacity can be reduced, and on top of that, the allocator may not shrink the allocation as much as VecDeque requests.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::with_capacity(15, 15);
deque.push_back(0);
deque.push_back(1);
deque.push_back(2);
deque.push_back(3);
assert_eq!(deque.capacity(), 15);

deque.shrink_to_fit();

assert!(deque.capacity() >= 4);

pub fn max_len(&self) -> usize

Returns the maximum number of elements.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let deque: BoundedVecDeque<i32> = BoundedVecDeque::new(255);

assert_eq!(deque.max_len(), 255);

pub fn set_max_len(&mut self, max_len: usize) -> Drain<'_, T>

Changes the maximum number of elements to max_len.

If there are more elements than the new maximum, they are removed from the back and yielded by the returned iterator (in front-to-back order).

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque: BoundedVecDeque<i32> = BoundedVecDeque::new(7);
deque.extend(vec![0, 1, 2, 3, 4, 5, 6]);
assert_eq!(deque.max_len(), 7);

assert!(deque.set_max_len(3).eq(vec![3, 4, 5, 6]));

assert_eq!(deque.max_len(), 3);
assert!(deque.iter().eq(&[0, 1, 2]));

pub fn truncate(&mut self, new_len: usize)

Decreases the length, dropping excess elements from the back.

If new_len is greater than the current length, this has no effect.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(5);
deque.push_back(10);
deque.push_back(15);
assert!(deque.iter().eq(&[5, 10, 15]));

deque.truncate(1);

assert!(deque.iter().eq(&[5]));

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

Returns a front-to-back iterator of immutable references.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(5);
deque.push_back(3);
deque.push_back(4);

let deque_of_references: Vec<&i32> = deque.iter().collect();

assert_eq!(&deque_of_references[..], &[&5, &3, &4]);

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

Returns a front-to-back iterator of mutable references.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(5);
deque.push_back(3);
deque.push_back(4);

for number in deque.iter_mut() {
    *number -= 2;
}
let deque_of_references: Vec<&mut i32> = deque.iter_mut().collect();

assert_eq!(&deque_of_references[..], &[&mut 3, &mut 1, &mut 2]);

pub fn as_unbounded(&self) -> &VecDeque<T>

Returns a reference to the underlying VecDeque.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let bounded = BoundedVecDeque::from_iter(vec![0, 1, 2, 3], 255);
let unbounded_ref = bounded.as_unbounded();

pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T])

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

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(0);
deque.push_back(1);
deque.push_front(10);
deque.push_front(9);

deque.as_mut_slices().0[0] = 42;
deque.as_mut_slices().1[0] = 24;

assert_eq!(deque.as_slices(), (&[42, 10][..], &[24, 1][..]));

pub fn is_full(&self) -> bool

Returns true if the BoundedVecDeque is full (and false otherwise).

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(3);

deque.push_back(0);
assert!(!deque.is_full());
deque.push_back(1);
assert!(!deque.is_full());
deque.push_back(2);
assert!(deque.is_full());

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T> where
    R: RangeBounds<usize>, 

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

Note 1: The element range is removed even if the iterator is not consumed until the end.

Note 2: It is unspecified how many elements are removed from the deque if the Drain value is not dropped but the borrow it holds expires (e.g. due to forget()).

Panics

Panics if the start index is greater than the end index or if the end index is greater than the length of the deque.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(vec![0, 1, 2, 3], 7);

assert!(deque.drain(2..).eq(vec![2, 3]));

assert!(deque.iter().eq(&[0, 1]));

// A full range clears all contents
deque.drain(..);

assert!(deque.is_empty());

pub fn clear(&mut self)

Removes all values.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(0);
assert!(!deque.is_empty());

deque.clear();

assert!(deque.is_empty());

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

Returns a mutable reference to the front element.

Returns None if the deque is empty.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);

assert_eq!(deque.front_mut(), None);

deque.push_back(0);
deque.push_back(1);

if let Some(x) = deque.front_mut() {
    *x = 9;
}

assert_eq!(deque.front(), Some(&9));

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

Returns a mutable reference to the back element.

Returns None if the deque is empty.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);

assert_eq!(deque.back_mut(), None);

deque.push_back(0);
deque.push_back(1);

if let Some(x) = deque.back_mut() {
    *x = 9;
}

assert_eq!(deque.back(), Some(&9));

pub fn push_front(&mut self, value: T) -> Option<T>

Pushes an element onto the front of the deque.

If the deque is full, an element is removed from the back and returned.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(2);

assert_eq!(deque.push_front(0), None);
assert_eq!(deque.push_front(1), None);
assert_eq!(deque.push_front(2), Some(0));
assert_eq!(deque.push_front(3), Some(1));
assert_eq!(deque.front(), Some(&3));

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

Removes and returns the first element.

Returns None if the deque is empty.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(0);
deque.push_back(1);

assert_eq!(deque.pop_front(), Some(0));
assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_front(), None);

pub fn push_back(&mut self, value: T) -> Option<T>

Pushes an element onto the back of the deque.

If the deque is full, an element is removed from the front and returned.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(2);

assert_eq!(deque.push_back(0), None);
assert_eq!(deque.push_back(1), None);
assert_eq!(deque.push_back(2), Some(0));
assert_eq!(deque.push_back(3), Some(1));
assert_eq!(deque.back(), Some(&3));

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

Removes and returns the last element.

Returns None if the deque is empty.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(0);
deque.push_back(1);

assert_eq!(deque.pop_back(), Some(1));
assert_eq!(deque.pop_back(), Some(0));
assert_eq!(deque.pop_back(), None);

pub fn swap_remove_front(&mut self, index: usize) -> Option<T>

Removes and returns the element at index, filling the gap with the element at the front.

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

Returns None if index is out of bounds.

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

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);

assert_eq!(deque.swap_remove_front(0), None);

deque.extend(vec![0, 1, 2, 3, 4, 5, 6]);

assert_eq!(deque.swap_remove_front(3), Some(3));
assert!(deque.iter().eq(&[1, 2, 0, 4, 5, 6]));

pub fn swap_remove_back(&mut self, index: usize) -> Option<T>

Removes and returns the element at index, filling the gap with the element at the back.

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

Returns None if index is out of bounds.

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

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);

assert_eq!(deque.swap_remove_back(0), None);

deque.extend(vec![0, 1, 2, 3, 4, 5, 6]);

assert_eq!(deque.swap_remove_back(3), Some(3));
assert!(deque.iter().eq(&[0, 1, 2, 6, 4, 5]));

pub fn insert_spill_back(&mut self, index: usize, value: T) -> Option<T>

Inserts an element at index in the deque, displacing the back if necessary.

Elements with indices greater than or equal to index are shifted one place towards the back to make room. If the deque is full, an element is removed from the back and returned.

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

Panics

Panics if index is greater than the length.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(5);
deque.extend(vec!['a', 'b', 'c', 'd']);

assert_eq!(deque.insert_spill_back(1, 'e'), None);
assert!(deque.iter().eq(&['a', 'e', 'b', 'c', 'd']));
assert_eq!(deque.insert_spill_back(1, 'f'), Some('d'));
assert!(deque.iter().eq(&['a', 'f', 'e', 'b', 'c']));

pub fn insert_spill_front(&mut self, index: usize, value: T) -> Option<T>

Inserts an element at index in the deque, displacing the front if necessary.

If the deque is full, an element is removed from the front and returned, and elements with indices less than or equal to index are shifted one place towards the front to make room. Otherwise, elements with indices greater than or equal to index are shifted one place towards the back to make room.

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

Panics

Panics if index is greater than the length.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(5);
deque.extend(vec!['a', 'b', 'c', 'd']);

assert_eq!(deque.insert_spill_front(3, 'e'), None);
assert!(deque.iter().eq(&['a', 'b', 'c', 'e', 'd']));
assert_eq!(deque.insert_spill_front(3, 'f'), Some('a'));
assert!(deque.iter().eq(&['b', 'c', 'e', 'f', 'd']));

pub fn remove(&mut self, index: usize) -> Option<T>

Removes and returns the element at index.

Elements with indices greater than index are shifted towards the front to fill the gap.

Returns None if index is out of bounds.

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

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);

assert_eq!(deque.remove(0), None);

deque.extend(vec![0, 1, 2, 3, 4, 5, 6]);

assert_eq!(deque.remove(3), Some(3));
assert!(deque.iter().eq(&[0, 1, 2, 4, 5, 6]));

pub fn split_off(&mut self, at: usize) -> Self

Splits the deque in two at the given index.

Returns a new BoundedVecDeque containing elements [at, len), leaving self with elements [0, at). The capacity and maximum length of self are unchanged, and the new deque has the same maximum length as self.

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

Panics

Panics if at > len.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(vec![0, 1, 2, 3], 7);

let other_deque = deque.split_off(2);

assert!(other_deque.iter().eq(&[2, 3]));
assert!(deque.iter().eq(&[0, 1]));

pub fn append<'a>(&'a mut self, other: &'a mut Self) -> Append<'a, T>

Moves all the elements of other into self, leaving other empty.

Elements from other are pushed onto the back of self. If the maximum length is exceeded, excess elements from the front of self are yielded by the returned iterator.

Panics

Panics if the new number of elements in self overflows a usize.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(vec![0, 1, 2, 3], 7);
let mut other_deque = BoundedVecDeque::from_iter(vec![4, 5, 6, 7, 8], 7);

assert!(deque.append(&mut other_deque).eq(vec![0, 1]));

assert!(deque.iter().eq(&[2, 3, 4, 5, 6, 7, 8]));
assert!(other_deque.is_empty());

pub fn retain<F>(&mut self, predicate: F) where
    F: FnMut(&T) -> bool, 

Retains only the elements specified by the predicate.

predicate is called for each element; each element for which it returns false is removed. This method operates in place and preserves the order of the retained elements.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(1..5, 7);

deque.retain(|&x| x % 2 == 0);

assert!(deque.iter().eq(&[2, 4]));

pub fn resize(&mut self, new_len: usize, value: T) where
    T: Clone, 

Modifies the deque in-place so that its length is equal to new_len.

This is done either by removing excess elements from the back or by pushing clones of value to the back.

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::from_iter(vec![5, 10, 15], 7);

deque.resize(2, 0);

assert!(deque.iter().eq(&[5, 10]));

deque.resize(5, 20);

assert!(deque.iter().eq(&[5, 10, 20, 20, 20]));

Methods from Deref<Target = VecDeque<T>>

pub fn get(&self, index: usize) -> Option<&T>

Provides a reference to the element at the given index.

Element at index 0 is the front of the queue.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
assert_eq!(buf.get(1), Some(&4));

pub fn capacity(&self) -> usize

Returns the number of elements the deque can hold without reallocating.

Examples

use std::collections::VecDeque;

let buf: VecDeque<i32> = VecDeque::with_capacity(10);
assert!(buf.capacity() >= 10);

pub fn allocator(&self) -> &A

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

Returns a reference to the underlying allocator.

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

Returns a front-to-back iterator.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(3);
buf.push_back(4);
let b: &[_] = &[&5, &3, &4];
let c: Vec<&i32> = buf.iter().collect();
assert_eq!(&c[..], b);

pub fn as_slices(&self) -> (&[T], &[T])

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

use std::collections::VecDeque;

let mut deque = VecDeque::new();

deque.push_back(0);
deque.push_back(1);
deque.push_back(2);

assert_eq!(deque.as_slices(), (&[0, 1, 2][..], &[][..]));

deque.push_front(10);
deque.push_front(9);

assert_eq!(deque.as_slices(), (&[9, 10][..], &[0, 1, 2][..]));

pub fn len(&self) -> usize

Returns the number of elements in the deque.

Examples

use std::collections::VecDeque;

let mut deque = VecDeque::new();
assert_eq!(deque.len(), 0);
deque.push_back(1);
assert_eq!(deque.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the deque is empty.

Examples

use std::collections::VecDeque;

let mut deque = VecDeque::new();
assert!(deque.is_empty());
deque.push_front(1);
assert!(!deque.is_empty());

pub fn range<R>(&self, range: R) -> Iter<'_, T> where
    R: RangeBounds<usize>, 

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

use std::collections::VecDeque;

let deque: VecDeque<_> = [1, 2, 3].into();
let range = deque.range(2..).copied().collect::<VecDeque<_>>();
assert_eq!(range, [3]);

// A full range covers all contents
let all = deque.range(..);
assert_eq!(all.len(), 3);

pub fn contains(&self, x: &T) -> bool where
    T: PartialEq<T>, 

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

This operation is O(n).

Note that if you have a sorted VecDeque, binary_search may be faster.

Examples

use std::collections::VecDeque;

let mut deque: VecDeque<u32> = VecDeque::new();

deque.push_back(0);
deque.push_back(1);

assert_eq!(deque.contains(&1), true);
assert_eq!(deque.contains(&10), false);

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

Provides a reference to the front element, or None if the deque is empty.

Examples

use std::collections::VecDeque;

let mut d = VecDeque::new();
assert_eq!(d.front(), None);

d.push_back(1);
d.push_back(2);
assert_eq!(d.front(), Some(&1));

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

Provides a reference to the back element, or None if the deque is empty.

Examples

use std::collections::VecDeque;

let mut d = VecDeque::new();
assert_eq!(d.back(), None);

d.push_back(1);
d.push_back(2);
assert_eq!(d.back(), Some(&2));

pub fn binary_search(&self, x: &T) -> Result<usize, usize> where
    T: Ord, 

Binary searches this VecDeque for a given element. This behaves similarly to contains if this VecDeque is sorted.

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned. If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

See also binary_search_by, binary_search_by_key, and partition_point.

Examples

Looks up a series of four elements. The first is found, with a uniquely determined position; the second and third are not found; the fourth could match any position in [1, 4].

use std::collections::VecDeque;

let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();

assert_eq!(deque.binary_search(&13),  Ok(9));
assert_eq!(deque.binary_search(&4),   Err(7));
assert_eq!(deque.binary_search(&100), Err(13));
let r = deque.binary_search(&1);
assert!(matches!(r, Ok(1..=4)));

If you want to insert an item to a sorted deque, while maintaining sort order, consider using partition_point:

use std::collections::VecDeque;

let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
let idx = deque.partition_point(|&x| x < num);
// The above is equivalent to `let idx = deque.binary_search(&num).unwrap_or_else(|x| x);`
deque.insert(idx, num);
assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);

pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize> where
    F: FnMut(&'a T) -> Ordering, 

Binary searches this VecDeque with a comparator function. This behaves similarly to contains if this VecDeque is sorted.

The comparator function should implement an order consistent with the sort order of the deque, returning an order code that indicates whether its argument is Less, Equal or Greater than the desired target.

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned. If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

See also binary_search, binary_search_by_key, and partition_point.

Examples

Looks up a series of four elements. The first is found, with a uniquely determined position; the second and third are not found; the fourth could match any position in [1, 4].

use std::collections::VecDeque;

let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();

assert_eq!(deque.binary_search_by(|x| x.cmp(&13)),  Ok(9));
assert_eq!(deque.binary_search_by(|x| x.cmp(&4)),   Err(7));
assert_eq!(deque.binary_search_by(|x| x.cmp(&100)), Err(13));
let r = deque.binary_search_by(|x| x.cmp(&1));
assert!(matches!(r, Ok(1..=4)));

pub fn binary_search_by_key<'a, B, F>(
    &'a self,
    b: &B,
    f: F
) -> Result<usize, usize> where
    F: FnMut(&'a T) -> B,
    B: Ord, 

Binary searches this VecDeque with a key extraction function. This behaves similarly to contains if this VecDeque is sorted.

Assumes that the deque is sorted by the key, for instance with make_contiguous().sort_by_key() using the same key extraction function.

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned. If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

See also binary_search, binary_search_by, and partition_point.

Examples

Looks up a series of four elements in a slice of pairs sorted by their second elements. The first is found, with a uniquely determined position; the second and third are not found; the fourth could match any position in [1, 4].

use std::collections::VecDeque;

let deque: VecDeque<_> = [(0, 0), (2, 1), (4, 1), (5, 1),
         (3, 1), (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
         (1, 21), (2, 34), (4, 55)].into();

assert_eq!(deque.binary_search_by_key(&13, |&(a, b)| b),  Ok(9));
assert_eq!(deque.binary_search_by_key(&4, |&(a, b)| b),   Err(7));
assert_eq!(deque.binary_search_by_key(&100, |&(a, b)| b), Err(13));
let r = deque.binary_search_by_key(&1, |&(a, b)| b);
assert!(matches!(r, Ok(1..=4)));

pub fn partition_point<P>(&self, pred: P) -> usize where
    P: FnMut(&T) -> bool, 

Returns the index of the partition point according to the given predicate (the index of the first element of the second partition).

The deque is assumed to be partitioned according to the given predicate. This means that all elements for which the predicate returns true are at the start of the deque and all elements for which the predicate returns false are at the end. For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0 (all odd numbers are at the start, all even at the end).

If the deque is not partitioned, the returned result is unspecified and meaningless, as this method performs a kind of binary search.

See also binary_search, binary_search_by, and binary_search_by_key.

Examples

use std::collections::VecDeque;

let deque: VecDeque<_> = [1, 2, 3, 3, 5, 6, 7].into();
let i = deque.partition_point(|&x| x < 5);

assert_eq!(i, 4);
assert!(deque.iter().take(i).all(|&x| x < 5));
assert!(deque.iter().skip(i).all(|&x| !(x < 5)));

If you want to insert an item to a sorted deque, while maintaining sort order:

use std::collections::VecDeque;

let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
let idx = deque.partition_point(|&x| x < num);
deque.insert(idx, num);
assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);

Trait Implementations

impl<T> AsRef<VecDeque<T, Global>> for BoundedVecDeque<T>

fn as_ref(&self) -> &VecDeque<T>

Converts this type into a shared reference of the (usually inferred) input type.

impl<T: Clone> Clone for BoundedVecDeque<T>

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

Mutates self into a clone of other (like *self = other.clone()).

self is cleared, and the elements of other are cloned and added. The maximum length is set to the same as other’s.

This method reuses self’s allocation, but due to API limitations, the allocation cannot be shrunk to fit the maximum length. Because of this, if self’s capacity is more than the new maximum length, it is shrunk to fit other’s length.

fn clone(&self) -> Self

Returns a copy of the value.

impl<T: Debug> Debug for BoundedVecDeque<T>

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

Formats the value using the given formatter.

impl<T> Deref for BoundedVecDeque<T>

type Target = VecDeque<T, Global>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T> Extend<T> for BoundedVecDeque<T>

fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = T>, 

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

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

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

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

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

impl<T: Hash> Hash for BoundedVecDeque<T>

fn hash<H>(&self, hasher: &mut H) where
    H: Hasher, 

Feeds self into hasher.

Only the values contained in self are hashed; the length bound is ignored.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<T> Index<usize> for BoundedVecDeque<T>

fn index(&self, index: usize) -> &T

Returns a reference to an element in the VecDeque by index.

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

Panics

Panics if there is no such element (i.e. index >= len).

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(7);
deque.push_back(3);
deque.push_back(4);
deque.push_back(5);

let value = &deque[1];

assert_eq!(value, &4);

type Output = T

The returned type after indexing.

impl<T> IndexMut<usize> for BoundedVecDeque<T>

fn index_mut(&mut self, index: usize) -> &mut T

Returns a mutable reference to an element in the VecDeque by index.

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

Panics

Panics if there is no such element (i.e. index >= len).

Examples

use ::bounded_vec_deque::BoundedVecDeque;

let mut deque = BoundedVecDeque::new(12);
deque.push_back(3);
deque.push_back(4);
deque.push_back(5);

deque[1] = 7;

assert_eq!(deque[1], 7);

impl<T> IntoIterator for BoundedVecDeque<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<'a, T> IntoIterator for &'a BoundedVecDeque<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 BoundedVecDeque<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.