Struct acap::vp::VpTree

pub struct VpTree<T: Proximity> { /* fields omitted */ }

A vantage-point tree.

Implementations

impl<T: Proximity> VpTree<T>

pub fn new() -> Self

Create an empty tree.

pub fn balanced<I: IntoIterator<Item = T>>(items: I) -> Self

Create a balanced tree out of a sequence of items.

pub fn iter(&self) -> Iter<'_, T>

Iterate over the items stored in this tree.

pub fn balance(&mut self)

Rebalance this VP tree.

pub fn push(&mut self, item: T)

Push a new item into the tree.

Inserting elements individually tends to unbalance the tree. Use VpTree::balanced if possible to create a balanced tree from a batch of items.

Trait Implementations

impl<T> Debug for VpTree<T> where
    T: Proximity + Debug,
    DistanceValue<T>: Debug, 

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

Formats the value using the given formatter.

impl<T: Proximity> Default for VpTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Proximity> Extend<T> for VpTree<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, items: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Proximity> FromIterator<T> for VpTree<T>

fn from_iter<I: IntoIterator<Item = T>>(items: I) -> Self

Creates a value from an iterator.

impl<T: Proximity> IntoIterator for VpTree<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T: Proximity> IntoIterator for &'a VpTree<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V> NearestNeighbors<K, V> for VpTree<V> where
    K: Proximity<V, Distance = V::Distance>,
    V: Proximity, 

fn search<'k, 'v, N>(&'v self, neighborhood: N) -> N where
    K: 'k,
    V: 'v,
    N: Neighborhood<&'k K, &'v V>, 

Search for nearest neighbors and add them to a neighborhood.

fn nearest(&self, target: &K) -> Option<Neighbor<&V, K::Distance>>

Returns the nearest neighbor to target (or None if this index is empty).

fn nearest_within<D>(
    &self,
    target: &K,
    threshold: D
) -> Option<Neighbor<&V, K::Distance>> where
    D: TryInto<K::Distance>, 

Returns the nearest neighbor to target within the distance threshold, if one exists.

fn k_nearest(&self, target: &K, k: usize) -> Vec<Neighbor<&V, K::Distance>>

Returns the up to k nearest neighbors to target.

fn k_nearest_within<D>(
    &self,
    target: &K,
    k: usize,
    threshold: D
) -> Vec<Neighbor<&V, K::Distance>> where
    D: TryInto<K::Distance>, 

Returns the up to k nearest neighbors to target within the distance threshold.

fn merge_k_nearest<'v>(
    &'v self,
    target: &K,
    k: usize,
    neighbors: &mut Vec<Neighbor<&'v V, K::Distance>>
)

Merges up to k nearest neighbors into an existing sorted vector.

fn merge_k_nearest_within<'v, D>(
    &'v self,
    target: &K,
    k: usize,
    threshold: D,
    neighbors: &mut Vec<Neighbor<&'v V, K::Distance>>
) where
    D: TryInto<K::Distance>, 

Merges up to k nearest neighbors within the threshold into an existing sorted vector.

impl<K, V> ExactNeighbors<K, V> for VpTree<V> where
    K: Metric<V, Distance = V::Distance>,
    V: Metric,