[−][src]Struct hamming_heap::HammingHeap
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(), ());
Methods
impl<T> HammingHeap<T>
[src]
pub fn new() -> Self
[src]
pub fn new_distances(distances: usize) -> Self
[src]
Automatically initializes self with distances
distances.
pub fn clear(&mut self)
[src]
This allows the queue to be cleared so that we don't need to reallocate memory.
pub fn set_distances(&mut self, distances: usize)
[src]
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)>
[src]
This removes the nearest candidate from the queue.
pub fn push(&mut self, distance: u32, node: T)
[src]
Inserts a node.
pub fn best(&self) -> Option<u32>
[src]
Returns the best distance if not empty.
pub fn iter(&self) -> impl Iterator<Item = (u32, &T)>
[src]
Iterate over the entire queue in best-to-worse order.
pub fn iter_mut(&mut self) -> impl Iterator<Item = (u32, &mut T)>
[src]
Iterate over the entire queue in best-to-worse order.
Trait Implementations
impl<T: Clone> Clone for HammingHeap<T>
[src]
fn clone(&self) -> HammingHeap<T>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<T> Default for HammingHeap<T>
[src]
impl<T: Debug> Debug for HammingHeap<T>
[src]
Auto Trait Implementations
impl<T> Sync for HammingHeap<T> where
T: Sync,
T: Sync,
impl<T> Send for HammingHeap<T> where
T: Send,
T: Send,
impl<T> Unpin for HammingHeap<T> where
T: Unpin,
T: Unpin,
impl<T> RefUnwindSafe for HammingHeap<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
impl<T> UnwindSafe for HammingHeap<T> where
T: UnwindSafe,
T: UnwindSafe,
Blanket Implementations
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,