Struct KeyChordQueue

pub struct KeyChordQueue(pub VecDeque<KeyChord>);

Manually add key chords to be processed as through they were pressed by the user.

Normally this does not need to be manipulated. It is a kind of escape hatch.

Tuple Fields

0: VecDeque<KeyChord>

Methods from Deref<Target = VecDeque<KeyChord>>

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);
buf.push_back(6);
assert_eq!(buf.get(1), Some(&4));

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

Provides a mutable 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);
buf.push_back(6);
assert_eq!(buf[1], 4);
if let Some(elem) = buf.get_mut(1) {
    *elem = 7;
}
assert_eq!(buf[1], 7);

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

Swaps elements at indices i and j.

i and j may be equal.

Element at index 0 is the front of the queue.

Panics

Panics if either index is out of bounds.

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, [3, 4, 5]);
buf.swap(0, 2);
assert_eq!(buf, [5, 4, 3]);

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 reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for at least additional more elements to be inserted in the given deque. Does nothing if the capacity is already sufficient.

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

Panics

Panics if the new capacity overflows usize.

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<i32> = [1].into();
buf.reserve_exact(10);
assert!(buf.capacity() >= 11);

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

Reserves capacity for at least additional more elements to be inserted in the given deque. The collection may reserve more space to speculatively avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<i32> = [1].into();
buf.reserve(10);
assert!(buf.capacity() >= 11);

pub fn try_reserve_exact( &mut self, additional: usize, ) -> Result<(), TryReserveError>

Tries to reserve the minimum capacity for at least additional more elements to be inserted in the given deque. After calling try_reserve_exact, capacity will be greater than or equal to self.len() + additional if it returns Ok(()). Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore, capacity can not be relied upon to be precisely minimal. Prefer try_reserve if future insertions are expected.

Errors

If the capacity overflows usize, or the allocator reports a failure, then an error is returned.

Examples

use std::collections::TryReserveError;
use std::collections::VecDeque;

fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    let mut output = VecDeque::new();

    // Pre-reserve the memory, exiting if we can't
    output.try_reserve_exact(data.len())?;

    // Now we know this can't OOM(Out-Of-Memory) in the middle of our complex work
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // very complicated
    }));

    Ok(output)
}

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>

Tries to reserve capacity for at least additional more elements to be inserted in the given deque. The collection may reserve more space to speculatively avoid frequent reallocations. After calling try_reserve, capacity will be greater than or equal to self.len() + additional if it returns Ok(()). Does nothing if capacity is already sufficient. This method preserves the contents even if an error occurs.

Errors

If the capacity overflows usize, or the allocator reports a failure, then an error is returned.

Examples

use std::collections::TryReserveError;
use std::collections::VecDeque;

fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    let mut output = VecDeque::new();

    // Pre-reserve the memory, exiting if we can't
    output.try_reserve(data.len())?;

    // Now we know this can't OOM in the middle of our complex work
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // very complicated
    }));

    Ok(output)
}

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the deque as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the deque that there is space for a few more elements.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);
buf.extend(0..4);
assert_eq!(buf.capacity(), 15);
buf.shrink_to_fit();
assert!(buf.capacity() >= 4);

pub fn shrink_to(&mut self, min_capacity: usize)

Shrinks the capacity of the deque with a lower bound.

The capacity will remain at least as large as both the length and the supplied value.

If the current capacity is less than the lower limit, this is a no-op.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);
buf.extend(0..4);
assert_eq!(buf.capacity(), 15);
buf.shrink_to(6);
assert!(buf.capacity() >= 6);
buf.shrink_to(0);
assert!(buf.capacity() >= 4);

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

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

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

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);
buf.truncate(1);
assert_eq!(buf, [5]);

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 iter_mut(&mut self) -> IterMut<'_, T>

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

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(3);
buf.push_back(4);
for num in buf.iter_mut() {
    *num = *num - 2;
}
let b: &[_] = &[&mut 3, &mut 1, &mut 2];
assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], 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 as_mut_slices(&mut self) -> (&mut [T], &mut [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_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 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 range_mut<R>(&mut self, range: R) -> IterMut<'_, T>

where R: RangeBounds<usize>,

Creates an iterator that covers the specified mutable 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 mut deque: VecDeque<_> = [1, 2, 3].into();
for v in deque.range_mut(2..) {
  *v *= 2;
}
assert_eq!(deque, [1, 2, 6]);

// A full range covers all contents
for v in deque.range_mut(..) {
  *v *= 2;
}
assert_eq!(deque, [2, 4, 12]);

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

where R: RangeBounds<usize>,

Removes the specified range from the deque in bulk, returning all removed elements as an iterator. If the iterator is dropped before being fully consumed, it drops the remaining removed elements.

The returned iterator keeps a mutable borrow on the queue to optimize its implementation.

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.

Leaking

If the returned iterator goes out of scope without being dropped (due to mem::forget, for example), the deque may have lost and leaked elements arbitrarily, including elements outside the range.

Examples

use std::collections::VecDeque;

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

// A full range clears all contents, like `clear()` does
deque.drain(..);
assert!(deque.is_empty());

pub fn clear(&mut self)

Clears the deque, removing all values.

Examples

use std::collections::VecDeque;

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

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

where T: PartialEq,

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 front_mut(&mut self) -> Option<&mut T>

Provides a mutable 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_mut(), None);

d.push_back(1);
d.push_back(2);
match d.front_mut() {
    Some(x) => *x = 9,
    None => (),
}
assert_eq!(d.front(), Some(&9));

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 back_mut(&mut self) -> Option<&mut T>

Provides a mutable 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);
match d.back_mut() {
    Some(x) => *x = 9,
    None => (),
}
assert_eq!(d.back(), Some(&9));

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

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

Examples

use std::collections::VecDeque;

let mut d = VecDeque::new();
d.push_back(1);
d.push_back(2);

assert_eq!(d.pop_front(), Some(1));
assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);

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

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

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
assert_eq!(buf.pop_back(), None);
buf.push_back(1);
buf.push_back(3);
assert_eq!(buf.pop_back(), Some(3));

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

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

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

Examples

#![feature(vec_deque_pop_if)]
use std::collections::VecDeque;

let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
let pred = |x: &mut i32| *x % 2 == 0;

assert_eq!(deque.pop_front_if(pred), Some(0));
assert_eq!(deque, [1, 2, 3, 4]);
assert_eq!(deque.pop_front_if(pred), None);

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

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

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

Examples

#![feature(vec_deque_pop_if)]
use std::collections::VecDeque;

let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
let pred = |x: &mut i32| *x % 2 == 0;

assert_eq!(deque.pop_back_if(pred), Some(4));
assert_eq!(deque, [0, 1, 2, 3]);
assert_eq!(deque.pop_back_if(pred), None);

pub fn push_front(&mut self, value: T)

Prepends an element to the deque.

Examples

use std::collections::VecDeque;

let mut d = VecDeque::new();
d.push_front(1);
d.push_front(2);
assert_eq!(d.front(), Some(&2));

pub fn push_back(&mut self, value: T)

Appends an element to the back of the deque.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(1);
buf.push_back(3);
assert_eq!(3, *buf.back().unwrap());

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

Removes an element from anywhere in the deque and returns it, replacing it with the first element.

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

Returns None if index is out of bounds.

Element at index 0 is the front of the queue.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
assert_eq!(buf.swap_remove_front(0), None);
buf.push_back(1);
buf.push_back(2);
buf.push_back(3);
assert_eq!(buf, [1, 2, 3]);

assert_eq!(buf.swap_remove_front(2), Some(3));
assert_eq!(buf, [2, 1]);

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

Removes an element from anywhere in the deque and returns it, replacing it with the last element.

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

Returns None if index is out of bounds.

Element at index 0 is the front of the queue.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
assert_eq!(buf.swap_remove_back(0), None);
buf.push_back(1);
buf.push_back(2);
buf.push_back(3);
assert_eq!(buf, [1, 2, 3]);

assert_eq!(buf.swap_remove_back(0), Some(1));
assert_eq!(buf, [3, 2]);

pub fn insert(&mut self, index: usize, value: T)

Inserts an element at index within the deque, shifting all elements with indices greater than or equal to index towards the back.

Element at index 0 is the front of the queue.

Panics

Panics if index is strictly greater than deque’s length

Examples

use std::collections::VecDeque;

let mut vec_deque = VecDeque::new();
vec_deque.push_back('a');
vec_deque.push_back('b');
vec_deque.push_back('c');
assert_eq!(vec_deque, &['a', 'b', 'c']);

vec_deque.insert(1, 'd');
assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);

vec_deque.insert(4, 'e');
assert_eq!(vec_deque, &['a', 'd', 'b', 'c', 'e']);

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

Removes and returns the element at index from the deque. Whichever end is closer to the removal point will be moved to make room, and all the affected elements will be moved to new positions. Returns None if index is out of bounds.

Element at index 0 is the front of the queue.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back('a');
buf.push_back('b');
buf.push_back('c');
assert_eq!(buf, ['a', 'b', 'c']);

assert_eq!(buf.remove(1), Some('b'));
assert_eq!(buf, ['a', 'c']);

pub fn split_off(&mut self, at: usize) -> VecDeque<T, A>

where A: Clone,

Splits the deque into two at the given index.

Returns a newly allocated VecDeque. self contains elements [0, at), and the returned deque contains elements [at, len).

Note that the capacity of self does not change.

Element at index 0 is the front of the queue.

Panics

Panics if at > len.

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<_> = ['a', 'b', 'c'].into();
let buf2 = buf.split_off(1);
assert_eq!(buf, ['a']);
assert_eq!(buf2, ['b', 'c']);

pub fn append(&mut self, other: &mut VecDeque<T, A>)

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

Panics

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

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<_> = [1, 2].into();
let mut buf2: VecDeque<_> = [3, 4].into();
buf.append(&mut buf2);
assert_eq!(buf, [1, 2, 3, 4]);
assert_eq!(buf2, []);

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&T) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all elements e for which 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

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..5);
buf.retain(|&x| x % 2 == 0);
assert_eq!(buf, [2, 4]);

Because the elements are visited exactly once in the original order, external state may be used to decide which elements to keep.

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..6);

let keep = [false, true, true, false, true];
let mut iter = keep.iter();
buf.retain(|_| *iter.next().unwrap());
assert_eq!(buf, [2, 3, 5]);

pub fn retain_mut<F>(&mut self, f: F)

where F: FnMut(&mut T) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&mut 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

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..5);
buf.retain_mut(|x| if *x % 2 == 0 {
    *x += 1;
    true
} else {
    false
});
assert_eq!(buf, [3, 5]);

pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T)

Modifies the deque in-place so that len() is equal to new_len, either by removing excess elements from the back or by appending elements generated by calling generator to the back.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);

buf.resize_with(5, Default::default);
assert_eq!(buf, [5, 10, 15, 0, 0]);

buf.resize_with(2, || unreachable!());
assert_eq!(buf, [5, 10]);

let mut state = 100;
buf.resize_with(5, || { state += 1; state });
assert_eq!(buf, [5, 10, 101, 102, 103]);

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

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

This method does not allocate and does not change the order of the inserted elements. As it returns a mutable slice, this can be used to sort 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

Sorting the content of a deque.

use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);

buf.push_back(2);
buf.push_back(1);
buf.push_front(3);

// sorting the deque
buf.make_contiguous().sort();
assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));

// sorting it in reverse order
buf.make_contiguous().sort_by(|a, b| b.cmp(a));
assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));

Getting immutable access to the contiguous slice.

use std::collections::VecDeque;

let mut buf = VecDeque::new();

buf.push_back(2);
buf.push_back(1);
buf.push_front(3);

buf.make_contiguous();
if let (slice, &[]) = buf.as_slices() {
    // we can now be sure that `slice` contains all elements of the deque,
    // while still having immutable access to `buf`.
    assert_eq!(buf.len(), slice.len());
    assert_eq!(slice, &[3, 2, 1] as &[_]);
}

pub fn rotate_left(&mut self, n: usize)

Rotates the double-ended queue n places to the left.

Equivalently,

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

Panics

If n is greater than len(). Note that n == len() does not panic and is a no-op rotation.

Complexity

Takes *O*(min(n, len() - n)) time and no extra space.

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<_> = (0..10).collect();

buf.rotate_left(3);
assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);

for i in 1..10 {
    assert_eq!(i * 3 % 10, buf[0]);
    buf.rotate_left(3);
}
assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

pub fn rotate_right(&mut self, n: usize)

Rotates the double-ended queue n places to the right.

Equivalently,

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

Panics

If n is greater than len(). Note that n == len() does not panic and is a no-op rotation.

Complexity

Takes *O*(min(n, len() - n)) time and no extra space.

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<_> = (0..10).collect();

buf.rotate_right(3);
assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);

for i in 1..10 {
    assert_eq!(0, buf[i * 3 % 10]);
    buf.rotate_right(3);
}
assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

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

where T: Ord,

Binary searches this VecDeque for a given element. If the VecDeque is not sorted, the returned result is unspecified and meaningless.

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);
// If `num` is unique, `s.partition_point(|&x| x < num)` (with `<`) is equivalent to
// `s.binary_search(&num).unwrap_or_else(|x| x)`, but using `<=` may allow `insert`
// to shift less elements.
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.

The comparator function should return an order code that indicates whether its argument is Less, Equal or Greater the desired target. If the VecDeque is not sorted or if the comparator function does not implement an order consistent with the sort order of the underlying VecDeque, the returned result is unspecified and meaningless.

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.

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 deque is not sorted by the key, the returned result is unspecified and meaningless.

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 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]);

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

Modifies the deque in-place so that len() is equal to new_len, either by removing excess elements from the back or by appending clones of value to the back.

Examples

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);

buf.resize(2, 0);
assert_eq!(buf, [5, 10]);

buf.resize(5, 20);
assert_eq!(buf, [5, 10, 20, 20, 20]);

Trait Implementations

impl Debug for KeyChordQueue

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

Formats the value using the given formatter.

impl Default for KeyChordQueue

fn default() -> KeyChordQueue

Returns the “default value” for a type.

impl Deref for KeyChordQueue

type Target = VecDeque<KeyChord>

The resulting type after dereferencing.

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

Dereferences the value.

impl DerefMut for KeyChordQueue

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl FromReflect for KeyChordQueue

where KeyChordQueue: Any + Send + Sync, VecDeque<KeyChord>: FromReflect + TypePath + MaybeTyped + RegisterForReflection,

fn from_reflect(reflect: &dyn PartialReflect) -> Option<Self>

Constructs a concrete instance of Self from a reflected value.

fn take_from_reflect( reflect: Box<dyn PartialReflect>, ) -> Result<Self, Box<dyn PartialReflect>>

Attempts to downcast the given value to Self using, constructing the value using from_reflect if that fails.

impl GetTypeRegistration for KeyChordQueue

where KeyChordQueue: Any + Send + Sync, VecDeque<KeyChord>: FromReflect + TypePath + MaybeTyped + RegisterForReflection,

fn get_type_registration() -> TypeRegistration

Returns the default TypeRegistration for this type.

fn register_type_dependencies(registry: &mut TypeRegistry)

Registers other types needed by this type.

impl PartialReflect for KeyChordQueue

where KeyChordQueue: Any + Send + Sync, VecDeque<KeyChord>: FromReflect + TypePath + MaybeTyped + RegisterForReflection,

fn get_represented_type_info(&self) -> Option<&'static TypeInfo>

Returns the TypeInfo of the type represented by this value.

fn try_apply(&mut self, value: &dyn PartialReflect) -> Result<(), ApplyError>

Tries to apply a reflected value to this value.

fn reflect_kind(&self) -> ReflectKind

Returns a zero-sized enumeration of “kinds” of type.

fn reflect_ref(&self) -> ReflectRef<'_>

Returns an immutable enumeration of “kinds” of type.

fn reflect_mut(&mut self) -> ReflectMut<'_>

Returns a mutable enumeration of “kinds” of type.

fn reflect_owned(self: Box<Self>) -> ReflectOwned

Returns an owned enumeration of “kinds” of type.

fn try_into_reflect( self: Box<Self>, ) -> Result<Box<dyn Reflect>, Box<dyn PartialReflect>>

Attempts to cast this type to a boxed, fully-reflected value.

fn try_as_reflect(&self) -> Option<&dyn Reflect>

Attempts to cast this type to a fully-reflected value.

fn try_as_reflect_mut(&mut self) -> Option<&mut dyn Reflect>

Attempts to cast this type to a mutable, fully-reflected value.

fn into_partial_reflect(self: Box<Self>) -> Box<dyn PartialReflect>

Casts this type to a boxed, reflected value.

fn as_partial_reflect(&self) -> &dyn PartialReflect

Casts this type to a reflected value.

fn as_partial_reflect_mut(&mut self) -> &mut dyn PartialReflect

Casts this type to a mutable, reflected value.

fn reflect_partial_eq(&self, value: &dyn PartialReflect) -> Option<bool>

Returns a “partial equality” comparison result.

fn reflect_clone(&self) -> Result<Box<dyn Reflect>, ReflectCloneError>

Attempts to clone Self using reflection.

fn apply(&mut self, value: &(dyn PartialReflect + 'static))

Applies a reflected value to this value.

fn clone_value(&self) -> Box<dyn PartialReflect>

👎Deprecated since 0.16.0: to clone reflected values, prefer using reflect_clone. To convert reflected values to dynamic ones, use to_dynamic.

Clones Self into its dynamic representation.

fn to_dynamic(&self) -> Box<dyn PartialReflect>

Converts this reflected value into its dynamic representation based on its kind.

fn reflect_hash(&self) -> Option<u64>

Returns a hash of the value (which includes the type).

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

Debug formatter for the value.

fn is_dynamic(&self) -> bool

Indicates whether or not this type is a dynamic type.

impl Reflect for KeyChordQueue

where KeyChordQueue: Any + Send + Sync, VecDeque<KeyChord>: FromReflect + TypePath + MaybeTyped + RegisterForReflection,

fn into_any(self: Box<Self>) -> Box<dyn Any>

Returns the value as a Box<dyn Any>.

fn as_any(&self) -> &dyn Any

Returns the value as a &dyn Any.

fn as_any_mut(&mut self) -> &mut dyn Any

Returns the value as a &mut dyn Any.

fn into_reflect(self: Box<Self>) -> Box<dyn Reflect>

Casts this type to a boxed, fully-reflected value.

fn as_reflect(&self) -> &dyn Reflect

Casts this type to a fully-reflected value.

fn as_reflect_mut(&mut self) -> &mut dyn Reflect

Casts this type to a mutable, fully-reflected value.

fn set(&mut self, value: Box<dyn Reflect>) -> Result<(), Box<dyn Reflect>>

Performs a type-checked assignment of a reflected value to this value.

impl TupleStruct for KeyChordQueue

where KeyChordQueue: Any + Send + Sync, VecDeque<KeyChord>: FromReflect + TypePath + MaybeTyped + RegisterForReflection,

fn field(&self, index: usize) -> Option<&dyn PartialReflect>

Returns a reference to the value of the field with index index as a &dyn Reflect.

fn field_mut(&mut self, index: usize) -> Option<&mut dyn PartialReflect>

Returns a mutable reference to the value of the field with index index as a &mut dyn Reflect.

fn field_len(&self) -> usize

Returns the number of fields in the tuple struct.

fn iter_fields(&self) -> TupleStructFieldIter<'_>

Returns an iterator over the values of the tuple struct’s fields.

fn to_dynamic_tuple_struct(&self) -> DynamicTupleStruct

Creates a new DynamicTupleStruct from this tuple struct.

fn clone_dynamic(&self) -> DynamicTupleStruct

👎Deprecated since 0.16.0: use to_dynamic_tuple_struct instead

Clones the struct into a DynamicTupleStruct.

fn get_represented_tuple_struct_info(&self) -> Option<&'static TupleStructInfo>

Will return None if TypeInfo is not available.

impl TypePath for KeyChordQueue

where KeyChordQueue: Any + Send + Sync,

fn type_path() -> &'static str

Returns the fully qualified path of the underlying type.

fn short_type_path() -> &'static str

Returns a short, pretty-print enabled path to the type.

fn type_ident() -> Option<&'static str>

Returns the name of the type, or None if it is anonymous.

fn crate_name() -> Option<&'static str>

Returns the name of the crate the type is in, or None if it is anonymous.

fn module_path() -> Option<&'static str>

Returns the path to the module the type is in, or None if it is anonymous.

impl Typed for KeyChordQueue

where KeyChordQueue: Any + Send + Sync, VecDeque<KeyChord>: FromReflect + TypePath + MaybeTyped + RegisterForReflection,

fn type_info() -> &'static TypeInfo

Returns the compile-time info for the underlying type.

impl Resource for KeyChordQueue

where Self: Send + Sync + 'static,