Struct hopscotch::Queue

pub struct Queue<K: Ord, V, P: SharedPointerKind = RcK> { /* fields omitted */ }

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>

pub fn new() -> Queue<K, V, P>

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>

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

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

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

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>>

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)

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

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>>

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>>

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>>

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>>

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, 

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

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>>

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>>

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, 

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, 

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, 

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, 

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)

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>

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>

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>

fn clone(&self) -> Queue<K, V, P>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Clone + Ord + Debug, V: Debug, P: SharedPointerKind> Debug for Queue<K, V, P>

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

Formats the value using the given formatter.

impl<K: Clone + Ord, V, P: SharedPointerKind> Default for Queue<K, V, P>

fn default() -> Queue<K, V, P>

Returns the "default value" for a type.

impl<K: Clone + Ord + Eq, V: Eq, P: SharedPointerKind> Eq for Queue<K, V, P>

impl<K: Ord + Clone, V, P: SharedPointerKind> Extend<(K, V)> for Queue<K, V, P>

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

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<K: Ord + Clone, V, P: SharedPointerKind> FromIterator<(K, V)> for Queue<K, V, P>

fn from_iter<I>(iter: I) -> Self where
    I: IntoIterator<Item = (K, V)>, 

Creates a value from an iterator.

impl<K: Clone + Ord + Hash, V: Hash, P: SharedPointerKind> Hash for Queue<K, V, P>

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

Feeds this value into the given [Hasher].

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

Feeds a slice of this type into the given [Hasher].

impl<K: Clone + Ord, V: Ord, P: SharedPointerKind> Ord for Queue<K, V, P>

fn cmp(&self, other: &Queue<K, V, P>) -> Ordering

This method returns an [Ordering] between self and other.

#[must_use]fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]fn clamp(self, min: Self, max: Self) -> Self

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

Restrict a value to a certain interval.

impl<K: Clone + Ord + PartialEq, V: PartialEq, P: SharedPointerKind> PartialEq<Queue<K, V, P>> for Queue<K, V, P>

fn eq(&self, other: &Queue<K, V, P>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Queue<K, V, P>) -> bool

This method tests for !=.

impl<K: Clone + Ord, V: PartialOrd, P: SharedPointerKind> PartialOrd<Queue<K, V, P>> for Queue<K, V, P>

fn partial_cmp(&self, other: &Queue<K, V, P>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.