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.