Struct VpTree

Source

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

Expand description

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

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

Implementations§

Source §

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

Source

pub 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.

Examples found in repository ?

examples/print_tree.rs (line 13)

12fn main() {
13    let vp_tree = VpTree::new(0i32 .. 8);
14    println!("{:?}", vp_tree);
15}

Source

pub 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.

Source §

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

Source

pub 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.

Source

pub 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.

Source

pub 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.

Source

pub 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.

Source

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

Add new_items to the tree and rebuild it.

Source

pub 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.

Source

pub 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.

Source

pub 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().

Source

pub 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.