Crate hopscotch

A hopscotch::Queue is a earliest-in-earliest-out (FIFO) queue where each Item in the queue has

• a value,
• 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 methods after and before (and their respective _mut variants):

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

These methods find next Item (or ItemMut) in the queue whose tag is equal to any of a given set of tags.

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 of the same tag.

This data structure is significantly optimized for small keys. The types usable as tags are limited to: u8, u16, u32, u64, usize, i8, i16, i32, i64, isize, or any third-party types which are instances of the nohash-hasher crate's IsEnabled trait. In practice, it's usually the right choice to just pick one of these tag types.

Structs

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.
IterMut	An iterator over mutable references to items in a queue.
Popped	An item that has been popped from the queue.
Queue	A hopscotch queue with keys of type K and items of type T.