Struct GenQueue

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

A queue with generation.

Generation increases whenever you take a value out of the queue, so that this would be useful when you need to know how many items are taken out since a specific time.

Examples

use my_ecs::ds::GenQueue;

let mut queue = GenQueue::new();

// Calls lots of push_back() and pop_front() on the queue...

// We're going to detect when this value will be returned.
let value = 123;
queue.push_back(value);
let expire = queue.generation() + queue.len() as u64;

// Calls lots of push_back() and pop_front() on the queue...

// `value` will be returned when queue's generation reaches `expire`.
while let Some(taken) = queue.pop_front() {
    if queue.generation() == expire {
        assert_eq!(taken, value);
    }
}

Implementations

impl<T> GenQueue<T>

pub const fn new() -> Self

Creates a new empty GenQueue.

Examples

See GenQueue document.

pub fn generation(&self) -> u64

Returns current generation of the queue.

Note that generation increases by 1 whenever you call GenQueue::pop_front.

Examples

See GenQueue document.

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

Returns a mutable reference to the value at the beginning of the queue.

Examples

use my_ecs::ds::GenQueue;

let mut queue = GenQueue::new();
queue.push_back(0);
queue.push_back(1);
assert_eq!(queue.front_mut(), Some(&mut 0));

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

Returns a mutable reference to the value at the end of the queue.

Examples

use my_ecs::ds::GenQueue;

let mut queue = GenQueue::new();
queue.push_back(0);
queue.push_back(1);
assert_eq!(queue.back_mut(), Some(&mut 1));

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

Appends the given value to the end of the queue.

Examples

See GenQueue document.

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

Removes a value from the beginning of the queue then returns it.

Note that this operation increases queue’s generation by 1.

Examples

See GenQueue document.

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);
buf.push_back(6);
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. Otherwise, the exact split point depends on implementation details and is not guaranteed.

Examples

use std::collections::VecDeque;

let mut deque = VecDeque::new();

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

let expected = [0, 1, 2];
let (front, back) = deque.as_slices();
assert_eq!(&expected[..front.len()], front);
assert_eq!(&expected[front.len()..], back);

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

let expected = [9, 10, 0, 1, 2];
let (front, back) = deque.as_slices();
assert_eq!(&expected[..front.len()], front);
assert_eq!(&expected[front.len()..], back);

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,

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

Trait Implementations

impl<T: Clone> Clone for GenQueue<T>

fn clone(&self) -> GenQueue<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for GenQueue<T>

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

Formats the value using the given formatter.

impl<T> Default for GenQueue<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Deref for GenQueue<T>

type Target = VecDeque<T>

The resulting type after dereferencing.

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

Dereferences the value.

impl<T> Resource for GenQueue<T>

where T: Send + 'static,