[−][src]Struct hopscotch::Queue
A hopscotch queue with keys of type K
and items of type V
.
Methods
impl<K: Eq + Hash + Clone, V> Queue<K, V, RandomState>
[src]
pub fn new() -> Queue<K, V>
[src]
pub fn with_capacity(capacity: usize) -> Queue<K, V>
[src]
Make a new queue with a given initial allocated capacity.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = Queue::with_capacity(10);
impl<K: Eq + Hash + Clone, V, S: BuildHasher> Queue<K, V, S>
[src]
pub fn len(&self) -> usize
[src]
The number of items currently in the queue.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..4).zip(0..4).collect(); assert_eq!(queue.len(), 4);
pub fn is_empty(&self) -> bool
[src]
Returns true
if and only if the queue is empty.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = Queue::new(); assert!(queue.is_empty()); queue.push(0, 100); assert!(!queue.is_empty());
pub fn push(&mut self, tag: K, value: V) -> u64
[src]
Push a new item into the queue, returning its assigned index.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, String> = Queue::new(); queue.push(0, "Hello!".to_string());
pub fn pop(&mut self) -> Option<Popped<K, V>>
[src]
Pop an item off the back of the queue and return it.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, String> = Queue::new(); queue.push(42, "Hello!".to_string()); let item = queue.pop()?; assert_eq!(item.index, 0); assert_eq!(item.tag, 42); assert_eq!(item.value, "Hello!");
pub fn clear(&mut self)
[src]
Clear the contents of the queue without de-allocating the queue's memory (though memory will still be freed for the individual elements of the queue).
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); queue.clear(); assert_eq!(queue.len(), 0);
pub fn next_index(&self) -> u64
[src]
The index which will be assigned to the next item to be added to the queue, whenever it is added.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = Queue::new(); assert_eq!(queue.next_index(), 0); let i = queue.push(0, 100); assert_eq!(i, 0); assert_eq!(queue.next_index(), 1);
pub fn earliest(&self) -> Option<Item<K, V>>
[src]
Get an immutable reference to the earliest item to have been inserted into the queue, which is still in the queue.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); queue.pop(); queue.pop(); assert_eq!(*queue.earliest()?.value(), 2);
pub fn earliest_mut(&mut self) -> Option<ItemMut<K, V>>
[src]
Get an immutable reference to the earliest item to have been inserted into the queue, which is still in the queue.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); queue.pop(); queue.pop(); *queue.earliest_mut()?.value_mut() = 500; assert_eq!(*queue.earliest()?.value(), 500);
pub fn latest(&self) -> Option<Item<K, V>>
[src]
Get an immutable reference to the latest item to have been inserted into the queue.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); assert_eq!(*queue.latest()?.value(), 9);
pub fn latest_mut(&mut self) -> Option<ItemMut<K, V>>
[src]
Get an immutable reference to the earliest item to have been inserted into the queue, which is still in the queue.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); *queue.latest_mut()?.value_mut() = 500; assert_eq!(*queue.latest()?.value(), 500);
pub fn contains(&self, x: &V) -> bool where
V: PartialEq,
[src]
V: PartialEq,
Returns true
if and only if the queue contains an item whose value is
equal to the given value.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); assert_eq!(queue.contains(&5), true); assert_eq!(queue.contains(&500), false);
pub fn contains_tag(&self, t: &K) -> bool
[src]
Returns true
if and only if the queue contains an item whose tag is
equal to the given tag.
This takes time logarithmic in the total number of tags in the queue, which is much faster than traversing the entire queue in search of a tag.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); assert_eq!(queue.contains_tag(&5), true); assert_eq!(queue.contains_tag(&500), false);
pub fn get(&self, index: u64) -> Option<Item<K, V>>
[src]
Get a reference to the earliest item exactly at index
.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); assert_eq!(*queue.get(0)?.as_ref(), 0);
As noted elsewhere, if we pop
off this value, the index we
supplied no longer will refer to any item in the queue, even though the
queue still contains items:
queue.pop(); assert!(queue.get(0).is_none());
pub fn get_mut(&mut self, index: u64) -> Option<ItemMut<K, V>>
[src]
Get a mutable reference to the earliest item exactly at index
.
Examples
let mut queue: Queue<usize, usize> = (0..10).zip(0..10).collect(); let mut n = queue.get_mut(0)?; *n.as_mut() = 5000; assert_eq!(*queue.get(0)?.as_ref(), 5000);
As noted elsewhere, if we pop
off this value, the index we
supplied no longer will refer to any item in the queue, even though the
queue still contains items:
queue.pop(); assert!(queue.get(0).is_none());
pub fn after<'a, Tags>(&self, index: u64, tags: Tags) -> Option<Item<K, V>> where
Tags: IntoIterator<Item = &'a K>,
K: 'a,
[src]
Tags: IntoIterator<Item = &'a K>,
K: 'a,
Get a reference to the earliest item after or including index
whose
tag is one of those given.
The Tags
type for the list of desired tags can be anything which
implements IntoIterator<Item = &K>
. The usual choice for this is
&[K]
(as seen in the examples below), but in cases where there is an
extant collection of tags, you can avoid re-allocating by passing an
iterator over that same collection.
Examples
Suppose we construct a queue that contains the phrase "Hello world!" in both English and French, interleaved, each word tagged with its language (0 = English; 1 = French):
let mut queue: Queue<usize, String> = vec![(0, "Hello".to_string()), (1, "Bonjour".to_string()), (0, "world!".to_string()), (1, "le monde!".to_string())].into_iter().collect();
Starting from index 0, the earliest word tagged as English is "Hello"; the earliest tagged as French is "Bonjour"; the earliest tagged as either is "Hello":
assert_eq!(queue.after(0, &[0])?.as_ref(), "Hello"); assert_eq!(queue.after(0, &[1])?.as_ref(), "Bonjour"); assert_eq!(queue.after(0, &[0, 1])?.as_ref(), "Hello");
Starting inclusively after index 1:
assert_eq!(queue.after(1, &[0])?.as_ref(), "world!"); assert_eq!(queue.after(1, &[1])?.as_ref(), "Bonjour"); assert_eq!(queue.after(1, &[0, 1])?.as_ref(), "Bonjour");
Starting inclusively after index 2:
assert_eq!(queue.after(2, &[0])?.as_ref(), "world!"); assert_eq!(queue.after(2, &[1])?.as_ref(), "le monde!"); assert_eq!(queue.after(2, &[0, 1])?.as_ref(), "world!");
Starting inclusively after index 3:
assert!(queue.after(3, &[0]).is_none()); assert_eq!(queue.after(3, &[1])?.as_ref(), "le monde!"); assert_eq!(queue.after(3, &[0, 1])?.as_ref(), "le monde!");
Starting inclusively after index 4:
assert!(queue.after(4, &[0]).is_none()); assert!(queue.after(4, &[1]).is_none()); assert!(queue.after(4, &[0, 1]).is_none());
pub fn after_mut<'a, Tags>(
&mut self,
index: u64,
tags: Tags
) -> Option<ItemMut<K, V>> where
Tags: IntoIterator<Item = &'a K>,
K: 'a,
[src]
&mut self,
index: u64,
tags: Tags
) -> Option<ItemMut<K, V>> where
Tags: IntoIterator<Item = &'a K>,
K: 'a,
Get a mutable reference to the earliest item after or including index
whose tag is one of those given.
The Tags
type for the list of desired tags can be anything which
implements IntoIterator<Item = &K>
. The usual choice for this is
&[K]
(as seen in the examples below), but in cases where there is an
extant collection of tags, you can avoid re-allocating by passing an
iterator over that same collection.
This uses the same semantics for lookup as after
: see its
documentation for more examples.
Examples
Suppose we construct a queue that contains the phrase "Hello world!" in both English and French, interleaved, each word tagged with its language (0 = English; 1 = French):
use hopscotch::Queue; let mut queue: Queue<usize, String> = vec![(0, "Hello".to_string()), (1, "Bonjour".to_string()), (0, "world!".to_string()), (1, "le monde!".to_string())].into_iter().collect(); let beginning = 0; // same start index for both calls to `after_mut` *queue.after_mut(beginning, &[0])?.as_mut() = "Goodbye".to_string(); *queue.after_mut(beginning, &[1])?.as_mut() = "Au revoir".to_string(); assert_eq!(queue.get(0)?.as_ref(), "Goodbye"); assert_eq!(queue.get(1)?.as_ref(), "Au revoir");
pub fn before<'a, Tags>(&self, index: u64, tags: Tags) -> Option<Item<K, V>> where
Tags: IntoIterator<Item = &'a K>,
K: 'a,
[src]
Tags: IntoIterator<Item = &'a K>,
K: 'a,
Get a reference to the latest item before or including index
whose tag
is one of those given.
The Tags
type for the list of desired tags can be anything which
implements IntoIterator<Item = &K>
. The usual choice for this is
&[K]
(as seen in the examples below), but in cases where there is an
extant collection of tags, you can avoid re-allocating by passing an
iterator over that same collection.
Examples
Suppose we construct a queue that contains the phrase "Hello world!" in both English and French, interleaved, each word tagged with its language (0 = English; 1 = French):
use hopscotch::Queue; let mut queue: Queue<usize, String> = vec![(0, "Hello".to_string()), (1, "Bonjour".to_string()), (0, "world!".to_string()), (1, "le monde!".to_string())].into_iter().collect();
Starting from index 4 (which is after the end of the queue), the latest word tagged as English is "world!"; the latest tagged as French is "le monde!"; the latest tagged as either is "le monde!":
assert_eq!(queue.before(4, &[0])?.as_ref(), "world!"); assert_eq!(queue.before(4, &[1])?.as_ref(), "le monde!"); assert_eq!(queue.before(4, &[0, 1])?.as_ref(), "le monde!");
Starting inclusively before index 3 (the end of the queue), we get the same results as any query after the end of the queue:
assert_eq!(queue.before(3, &[0])?.as_ref(), "world!"); assert_eq!(queue.before(3, &[1])?.as_ref(), "le monde!"); assert_eq!(queue.before(3, &[0, 1])?.as_ref(), "le monde!");
Starting inclusively before index 2:
assert_eq!(queue.before(2, &[0])?.as_ref(), "world!"); assert_eq!(queue.before(2, &[1])?.as_ref(), "Bonjour"); assert_eq!(queue.before(2, &[0, 1])?.as_ref(), "world!");
Starting inclusively before index 1:
assert_eq!(queue.before(1, &[0])?.as_ref(), "Hello"); assert_eq!(queue.before(1, &[1])?.as_ref(), "Bonjour"); assert_eq!(queue.before(1, &[0, 1])?.as_ref(), "Bonjour");
Starting inclusively before index 0:
assert_eq!(queue.before(0, &[0])?.as_ref(), "Hello"); assert!(queue.before(0, &[1]).is_none()); assert_eq!(queue.before(0, &[0, 1])?.as_ref(), "Hello");
pub fn before_mut<'a, Tags>(
&mut self,
index: u64,
tags: Tags
) -> Option<ItemMut<K, V>> where
Tags: IntoIterator<Item = &'a K>,
K: 'a,
[src]
&mut self,
index: u64,
tags: Tags
) -> Option<ItemMut<K, V>> where
Tags: IntoIterator<Item = &'a K>,
K: 'a,
Get a mutable reference to the latest item before or including index
whose tag is one of those given.
The Tags
type for the list of desired tags can be anything which
implements IntoIterator<Item = &K>
. The usual choice for this is
&[K]
(as seen in the examples below), but in cases where there is an
extant collection of tags, you can avoid re-allocating by passing an
iterator over that same collection.
This uses the same semantics for lookup as before
: see its
documentation for more examples.
Examples
Suppose we construct a queue that contains the phrase "Hello world!" in both English and French, interleaved, each word tagged with its language (0 = English; 1 = French):
use hopscotch::Queue; let mut queue: Queue<usize, String> = vec![(0, "Hello".to_string()), (1, "Bonjour".to_string()), (0, "world!".to_string()), (1, "le monde!".to_string())].into_iter().collect(); let end = 5; // same end index for both calls to `after_mut` *queue.before_mut(end, &[0])?.as_mut() = "my friends!".to_string(); *queue.before_mut(end, &[1])?.as_mut() = "mes amis!".to_string(); assert_eq!(queue.get(2)?.as_ref(), "my friends!"); assert_eq!(queue.get(3)?.as_ref(), "mes amis!");
pub fn shrink_to_fit(&mut self)
[src]
Shrink the memory used by the queues in this queue as much as possible.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, ()> = Queue::new(); for _ in 0 .. 10_000 { queue.push(0, ()); } for _ in 0 .. 10_000 { queue.pop(); } queue.shrink_to_fit();
pub fn iter(&self) -> Iter<K, V, impl Iterator<Item = &K> + Clone, S>
[src]
Get an iterator of immutable items currently in the queue, in insertion order from earliest to latest.
This iterator can be further restricted using its after
, until
, and
matching_only
methods to start at a given index, terminate at a given
index, and return only certain tags, respectively.
The returned iterator is double-ended, and therefore can be traversed in
reverse order using the .rev()
method.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, String> = vec![(0, "Hello".to_string()), (1, "Bonjour".to_string()), (0, "world!".to_string()), (1, "le monde!".to_string())].into_iter().collect(); let english: Vec<&str> = queue .iter() .matching_only(&[0]) .map(|i| i.value().as_ref()).collect(); assert_eq!(english, &["Hello", "world!"]); let all_backwards: Vec<&str> = queue.iter().rev() // <-- notice the reversal .map(|i| i.value().as_ref()).collect(); assert_eq!(all_backwards, &["le monde!", "world!", "Bonjour", "Hello"]);
pub fn iter_mut(&mut self) -> IterMut<K, V, impl Iterator<Item = &K> + Clone, S>
[src]
Get an iterator of mutable items currently in the queue, in insertion order from earliest to latest.
This iterator can be further restricted using its after
, until
, and
matching_only
methods to start at a given index, terminate at a given
index, and return only certain tags, respectively.
The returned iterator is double-ended, and therefore can be traversed in
reverse order using the .rev()
method.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, String> = vec![(0, "Hello".to_string()), (1, "Bonjour".to_string()), (0, "world!".to_string()), (1, "le monde!".to_string())].into_iter().collect(); for mut item in queue.iter_mut().matching_only(&[0]) { *item.as_mut() = item.as_mut().to_uppercase(); } let words: Vec<&str> = queue.iter() .map(|i| i.value().as_ref()).collect(); assert_eq!(words, &["HELLO", "Bonjour", "WORLD!", "le monde!"]);
pub fn with_hasher(make_hasher: fn() -> S) -> Queue<K, V, S>
[src]
Make an empty queue which will use the given hash builder initializer to hash tags internally.
The given function pointer will be invoked to make a BuildHasher
on
every push
operation, so it is essential for performance that it be
fast.
The same warning applies here as does for any hashing-based structure: supplying your own hasher can lead to a DoS attack vector in the form of maliciously crafted inputs that cause many hash collisions.
pub fn with_capacity_and_hasher(
capacity: usize,
make_hasher: fn() -> S
) -> Queue<K, V, S>
[src]
capacity: usize,
make_hasher: fn() -> S
) -> Queue<K, V, S>
Make an empty queue with the capacity to hold a given number of elements without further allocation, and which will use the given hash builder initializer to hash tags internally.
The given function pointer will be invoked to make a BuildHasher
on
every push
operation, so it is essential for performance that it be
fast.
The same warning applies here as does for any hashing-based structure: supplying your own hasher can lead to a DoS attack vector in the form of maliciously crafted inputs that cause many hash collisions.
Trait Implementations
impl<K: Clone + Eq + Hash, V: Clone, S: Clone> Clone for Queue<K, V, S>
[src]
impl<K: Eq + Hash + Clone, V> Extend<(K, V)> for Queue<K, V>
[src]
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = (K, V)>,
[src]
I: IntoIterator<Item = (K, V)>,
impl<K: Eq + Hash + Clone, V> FromIterator<(K, V)> for Queue<K, V>
[src]
fn from_iter<I>(iter: I) -> Self where
I: IntoIterator<Item = (K, V)>,
[src]
I: IntoIterator<Item = (K, V)>,
Auto Trait Implementations
impl<K, V, S> RefUnwindSafe for Queue<K, V, S> where
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V, S> Send for Queue<K, V, S> where
K: Send + Sync,
S: Send + Sync,
V: Send,
K: Send + Sync,
S: Send + Sync,
V: Send,
impl<K, V, S> Sync for Queue<K, V, S> where
K: Send + Sync,
S: Send + Sync,
V: Sync,
K: Send + Sync,
S: Send + Sync,
V: Sync,
impl<K, V, S> Unpin for Queue<K, V, S> where
K: Unpin,
V: Unpin,
K: Unpin,
V: Unpin,
impl<K, V, S> UnwindSafe for Queue<K, V, S> where
K: RefUnwindSafe + UnwindSafe,
S: RefUnwindSafe,
V: UnwindSafe,
K: RefUnwindSafe + UnwindSafe,
S: RefUnwindSafe,
V: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> Same<T> for T
type Output = T
Should always be Self
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,