Struct vec_vp_tree::VpTree

pub struct VpTree<T, D> { /* fields omitted */ }

An implementation of a vantage-point tree backed by a vector.

Only bulk insert/removals are provided in order to keep the tree balanced.

Methods

impl<T> VpTree<T, <T as KnownDist>::DistFn> where
    T: KnownDist, 

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

Collect the results of items into the tree, and build the tree using the known distance function for T.

If items is Vec<T>, use from_vec to avoid a copy.

If you want to provide a custom distance function, use new_with_dist() instead.

fn from_vec(items: Vec<T>) -> Self

Build the tree directly from items using the known distance function for T.

If you want to provide a custom distance function, use from_vec_with_dist() instead.

impl<T, D: DistFn<T>> VpTree<T, D>

fn new_with_dist<I: IntoIterator<Item = T>>(items: I, dist_fn: D) -> Self

Collect the results of items into the tree, and build the tree using the given distance function dist_fn.

If items is Vec<T>, use from_vec_with_dist to avoid a copy.

fn from_vec_with_dist(items: Vec<T>, dist_fn: D) -> Self

Build the tree directly from items using the given distance function dist_fn.

fn dist_fn<D_: DistFn<T>>(self, dist_fn: D_) -> VpTree<T, D_>

Apply a new distance function and rebuild the tree, returning the transformed type.

fn rebuild(&mut self)

Rebuild the full tree.

This is only necessary if the one or more properties of a contained item which determine their distance via D: DistFn<T> was somehow changed without the tree being rebuilt, or a panic occurred during a mutation and was caught.

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

Add new_items to the tree and rebuild it.

fn retain<F>(&mut self, ret_fn: F) where
    F: FnMut(&T) -> bool, 

Iterate over the contained items, dropping them if ret_fn returns false, keeping them otherwise.

The tree will be rebuilt afterwards.

fn items(&self) -> &[T]

Get a slice of the items in the tree.

These items may have been rearranged from the order which they were inserted.

Note

It is a logic error for an item to be modified in such a way that the item's distance to any other item, as determined by D: DistFn<T>, changes while it is in the tree without the tree being rebuilt. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

If you wish to mutate one or more of the contained items, use .with_mut_items() instead, to ensure the tree is rebuilt after the mutation.

fn with_mut_items<F>(&mut self, mut_fn: F) where
    F: FnOnce(&mut [T]), 

Get a scoped mutable slice to the contained items.

The tree will be rebuilt after mut_fn returns, in assumption that it will modify one or more of the contained items such that their distance to others, as determined by D: DistFn<T>, changes.

Note

If a panic is initiated in mut_fn and then caught outside this method, the tree will need to be manually rebuilt with .rebuild().

fn k_nearest<'t, O: Borrow<T>>(
    &'t self,
    origin: O,
    k: usize
) -> Vec<Neighbor<'t, T>>

Get a vector of the k nearest neighbors to origin, sorted in ascending order by the distance.

Note

If origin is contained within the tree, which is allowed by the API contract, it will be returned in the results. In this case, it may be preferable to start with a higher k and filter out duplicate entries.

If k > self.items.len(), then obviously only self.items.len() items will be returned.

Panics

If the tree was in an invalid state. This can happen if a panic occurred during a mutation and was then caught without calling .rebuild().

fn within_radius<'t, O: Borrow<T>>(
    &'t self,
    origin: O,
    radius: u64
) -> Vec<Neighbor<'t, T>>

fn into_vec(self) -> Vec<T>

Consume self and return the vector of items.

The items may have been rearranged from the order in which they were inserted.

Trait Implementations

impl<T: Clone, D: Clone> Clone for VpTree<T, D>

fn clone(&self) -> VpTree<T, D>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, D: DistFn<T>> Debug for VpTree<T, D>

Prints the contained items as well as the tree structure, if it is in a valid state.

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

Formats the value using the given formatter.