Struct FixedHammingHeap

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

This keeps the nearest cap items at all times.

This heap is not intended to be popped. Instead, this maintains the best cap items, and then when you are done adding items, you may fill a slice or iterate over the results. Theoretically, this could also allow popping elements in constant time, but that would incur a performance penalty for the highly specialized purpose this serves. This is specifically tailored for doing hamming space nearest neighbor searches.

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::FixedHammingHeap;
let mut candidates = FixedHammingHeap::new_distances(129);
candidates.set_capacity(3);
candidates.push((0u128 ^ !0u128).count_ones(), ());

Implementations

impl<T> FixedHammingHeap<T>

pub fn new() -> Self

pub fn new_distances(distances: usize) -> Self

Automatically initializes self with distances distances.

pub fn set_capacity(&mut self, cap: usize)

This sets the capacity of the queue to cap, meaning that adding items to the queue will eject the worst ones if they are better once cap is reached. If the capacity is lowered, this removes the worst elements to keep size == cap.

pub fn set_len(&mut self, len: usize)

This removes elements until it reaches len. If len is higher than the current number of elements, this does nothing. If the len is lowered, this will unconditionally allow insertions until cap is reached.

pub fn len(&self) -> usize

Gets the len or size of the heap.

pub fn is_empty(&self) -> bool

Checks if the heap is empty.

pub fn clear(&mut self)

Clear the queue while maintaining the allocated 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 push(&mut self, distance: u32, item: T) -> bool

Add a feature to the search.

Returns true if it was added.

pub fn fill_slice<'a>(&self, s: &'a mut [T]) -> &'a mut [T]

where T: Clone,

Fill a slice with the top elements and return the part of the slice written.

pub fn worst(&self) -> u32

Gets the worst distance in the queue currently.

This is initialized to max (which is the worst possible distance) until cap elements have been inserted.

pub fn at_cap(&self) -> bool

Returns true if the cap has been reached.

pub fn iter(&mut 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.

pub unsafe fn push_at_cap(&mut self, distance: u32, item: T) -> bool

Add a feature to the search with the precondition we are already at the cap.

Warning: This function cannot cause undefined behavior, but it can be used incorrectly. This should only be called after at_cap() can been called and returns true. This shouldn’t be used unless you profile and actually find that the branch predictor is having issues with the if statement in push().

Trait Implementations

impl<T: Clone> Clone for FixedHammingHeap<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for FixedHammingHeap<T>

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

Formats the value using the given formatter.

impl<T> Default for FixedHammingHeap<T>

fn default() -> Self

Returns the “default value” for a type.