[−][src]Struct hopscotch::Queue
A hopscotch queue with keys of type K
and items of type V
.
A note on pointers: By default, queues use Rc
smart
pointers internally, but this prevents them from implementing Sync
and
Send
, which means they cannot be sent across thread boundaries. Thanks
to the archery
crate, in contexts
where you want Queue
to implement Sync
and Send
, you can
instantiate the third type parameter P
to ArcK
instead
of its default value of RcK
(these types are re-exported
from archery
for convenience). As of last benchmarking, using the
Arc
variant imposes an approximate 15% extra cost for
mutation operations (push
and pop
), and
negligible extra cost for access operations (get
,
after
, before
, etc.).
Implementations
impl<K: Ord + Clone, V, P: SharedPointerKind> Queue<K, V, P>
[src]
pub fn new() -> Queue<K, V, P>
[src]
Make a new queue.
Examples
use hopscotch::Queue; let mut queue: Queue<usize, usize> = Queue::new();
If we want to use Arc
pointers and get thread-safety at the expense of
a little performance:
use hopscotch::{Queue, ArcK}; let mut queue: Queue<usize, usize, ArcK> = Queue::new();
pub fn with_capacity(capacity: usize) -> Queue<K, V, P>
[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);
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, P>
[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, P>
[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!"]);
Trait Implementations
impl<K: Clone + Ord, V: Clone, P: Clone + SharedPointerKind> Clone for Queue<K, V, P>
[src]
impl<K: Clone + Ord + Debug, V: Debug, P: SharedPointerKind> Debug for Queue<K, V, P>
[src]
impl<K: Clone + Ord, V, P: SharedPointerKind> Default for Queue<K, V, P>
[src]
impl<K: Clone + Ord + Eq, V: Eq, P: SharedPointerKind> Eq for Queue<K, V, P>
[src]
impl<K: Ord + Clone, V, P: SharedPointerKind> Extend<(K, V)> for Queue<K, V, P>
[src]
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = (K, V)>,
[src]
I: IntoIterator<Item = (K, V)>,
fn extend_one(&mut self, item: A)
[src]
fn extend_reserve(&mut self, additional: usize)
[src]
impl<K: Ord + Clone, V, P: SharedPointerKind> FromIterator<(K, V)> for Queue<K, V, P>
[src]
fn from_iter<I>(iter: I) -> Self where
I: IntoIterator<Item = (K, V)>,
[src]
I: IntoIterator<Item = (K, V)>,
impl<K: Clone + Ord + Hash, V: Hash, P: SharedPointerKind> Hash for Queue<K, V, P>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<K: Clone + Ord, V: Ord, P: SharedPointerKind> Ord for Queue<K, V, P>
[src]
fn cmp(&self, other: &Queue<K, V, P>) -> Ordering
[src]
#[must_use]fn max(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn min(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn clamp(self, min: Self, max: Self) -> Self
[src]
impl<K: Clone + Ord + PartialEq, V: PartialEq, P: SharedPointerKind> PartialEq<Queue<K, V, P>> for Queue<K, V, P>
[src]
impl<K: Clone + Ord, V: PartialOrd, P: SharedPointerKind> PartialOrd<Queue<K, V, P>> for Queue<K, V, P>
[src]
Auto Trait Implementations
impl<K, V, P> RefUnwindSafe for Queue<K, V, P> where
K: RefUnwindSafe,
P: RefUnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
P: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V, P> Send for Queue<K, V, P> where
K: Send,
P: Send,
V: Send,
K: Send,
P: Send,
V: Send,
impl<K, V, P> Sync for Queue<K, V, P> where
K: Sync,
P: Sync,
V: Sync,
K: Sync,
P: Sync,
V: Sync,
impl<K, V, P> Unpin for Queue<K, V, P> where
K: Unpin,
P: Unpin,
V: Unpin,
K: Unpin,
P: Unpin,
V: Unpin,
impl<K, V, P> UnwindSafe for Queue<K, V, P> where
K: RefUnwindSafe + UnwindSafe,
P: UnwindSafe,
V: UnwindSafe,
K: RefUnwindSafe + UnwindSafe,
P: UnwindSafe,
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> 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>,