Struct HammingHeap

pub struct HammingHeap<T> { /* private fields */ }

This is a special heap specifically for hamming space searches.

This queue works by having n-bits + 1 vectors, one for each hamming distance. When we find that any item achieves a distance of n at the least, we place the index of that node into the vector associated with that distance. Any time we take an item off, we place all of its children into the appropriate distance priorities.

We maintain the lowest weight vector at any given time in the queue. When a vector runs out, we iterate until we find the next-best non-empty distance vector.

To use this you will need to call set_distances before use. This should be passed the maximum number of distances. Please keep in mind that the maximum number of hamming distances between an n bit number is n + 1. An example would be:

assert_eq!((0u128 ^ !0).count_ones(), 128);

So make sure you use n + 1 as your distances or else you may encounter a runtime panic.

use hamming_heap::HammingHeap;
let mut candidates = HammingHeap::new_distances(129);
candidates.push((0u128 ^ !0u128).count_ones(), ());

Implementations

impl<T> HammingHeap<T>

pub fn new() -> Self

pub fn new_distances(distances: usize) -> Self

Automatically initializes self with distances distances.

pub fn clear(&mut self)

This allows the queue to be cleared so that we don’t need to reallocate memory.

pub fn set_distances(&mut self, distances: usize)

Set number of distances. Also clears the heap.

This does not preserve the allocated memory, so don’t call this on each search.

If you have a 128-bit number, keep in mind that it has 129 distances because 128 is one of the possible distances.

pub fn pop(&mut self) -> Option<(u32, T)>

This removes the nearest candidate from the queue.

pub fn push(&mut self, distance: u32, node: T)

Inserts a node.

pub fn best(&self) -> Option<u32>

Returns the best distance if not empty.

pub fn iter(&self) -> impl Iterator<Item = (u32, &T)>

Iterate over the entire queue in best-to-worse order.

pub fn iter_mut(&mut self) -> impl Iterator<Item = (u32, &mut T)>

Iterate over the entire queue in best-to-worse order.

Trait Implementations

impl<T: Clone> Clone for HammingHeap<T>

fn clone(&self) -> HammingHeap<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for HammingHeap<T>

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

Formats the value using the given formatter.

impl<T> Default for HammingHeap<T>

fn default() -> Self

Returns the “default value” for a type.