Crate hopscotch

A hopscotch::Queue<K, V> is a first-in-first-out queue where each Item<K, V> in the queue has

• a value of type V,
• an immutable tag of type K, and
• a unique index of type u64 which is assigned in sequential order of insertion starting at 0 when the queue is created.

In addition to supporting the ordinary push, pop, and get methods of a FIFO queue, a hopscotch queue also supports the special, optimized methods after, after_mut, before, and before_mut.

These methods find the next (or previous) Item (or ItemMut) in the queue whose tag is equal to any of a given set of tags. For instance, the signature of after is:

pub fn after<'a, Tags>(&self, index: u64, tags: Tags) -> Option<Item<K, V>>
    where
        Tags: IntoIterator<Item = &'a K>,
        K: 'a,

If we use &[K] for Tags, this signature simplifies to:

pub fn after(&self, index: u64, tags: &[K]) -> Option<Item<K, V>>

These methods are the real benefit of using a hopscotch queue over another data structure. Their asymptotic time complexity is:

• linear relative to the number of tags queried,
• logarithmic relative to the total number of distinct tags in the queue,
• constant relative to the length of the queue, and
• constant relative to the distance between successive items with the same tag.

Hopscotch queues also provide flexible iterators Iter/IterMut to efficiently traverse portions of their contents, sliced by index using Iter::until/IterMut::until and Iter::after/IterMut::after, and filtered by set of desired tags using Iter::matching_only/IterMut::matching_only.

Structs

ArcK

Type constructors for Arc pointers.

Item

An immutable reference to an item currently in the queue.

ItemMut

A mutable reference to an item currently in the queue.

Iter

An iterator over immutable references to items in a queue. Created by Queue::iter.

IterMut

An iterator over mutable references to items in a queue. Created by Queue::iter_mut.

Popped

An item that has been popped from the queue.

Queue

A hopscotch queue with keys of type K and items of type V.

RcK

Type constructors for Rc pointers.

Traits

SharedPointerKind

Trait for type constructors of reference-counting pointers.