vpsearch

Struct Tree

Source
pub struct Tree<Item: MetricSpace<Impl> + Clone, Impl = (), Ownership = Owned<()>> { /* private fields */ }
Expand description

The VP-Tree.

Implementations§

Source§

impl<Item: MetricSpace<Impl, UserData = ()> + Clone, Impl> Tree<Item, Impl, Owned<()>>

Source

pub fn new(items: &[Item]) -> Self

Creates a new tree from items. Maximum number of items is 2^31.

See Tree::new_with_user_data_owned.

Examples found in repository?
examples/orphan_rule.rs (line 17)
15
16
17
18
19
20
fn main() {
    let source_data = vec![vec![0; 64], vec![5; 64], vec![10; 64]];
    let vp = vpsearch::Tree::new(&source_data);
    let (index, dist) = vp.find_nearest(&vec![6; 64]);
    println!("The element at {} is the nearest, off by {}", index, dist);
}
More examples
Hide additional examples
examples/points.rs (line 22)
18
19
20
21
22
23
24
25
26
27
fn main() {

    let points = vec![Point{x:2.0,y:3.0}, Point{x:0.0,y:1.0}, Point{x:4.0,y:5.0}];

    let vp = vpsearch::Tree::new(&points);

    let (index, _) = vp.find_nearest(&Point{x:1.0,y:2.0});

    println!("The nearest point is at ({}, {})", points[index].x, points[index].y);
}
examples/newtype_ref.rs (line 20)
17
18
19
20
21
22
23
fn main() {
    let source_data = vec![[0; 64], [5; 64], [10; 64]];
    let reference_data: Vec<_> = source_data.iter().map(LotsaDimensions).collect();
    let vp = vpsearch::Tree::new(&reference_data);
    let (index, dist) = vp.find_nearest(&LotsaDimensions(&[6; 64]));
    println!("The element at {} is the nearest, off by {}", index, dist);
}
Source§

impl<U, Impl, Item: MetricSpace<Impl, UserData = U> + Clone> Tree<Item, Impl, Owned<U>>

Source

pub fn find_nearest(&self, needle: &Item) -> (usize, Item::Distance)

Finds item closest to the given needle (that can be any item) and returns index of the item in items array from new().

Returns the index of the nearest item (index from the items slice passed to new()) found and the distance from the nearest item.

Examples found in repository?
examples/orphan_rule.rs (line 18)
15
16
17
18
19
20
fn main() {
    let source_data = vec![vec![0; 64], vec![5; 64], vec![10; 64]];
    let vp = vpsearch::Tree::new(&source_data);
    let (index, dist) = vp.find_nearest(&vec![6; 64]);
    println!("The element at {} is the nearest, off by {}", index, dist);
}
More examples
Hide additional examples
examples/points.rs (line 24)
18
19
20
21
22
23
24
25
26
27
fn main() {

    let points = vec![Point{x:2.0,y:3.0}, Point{x:0.0,y:1.0}, Point{x:4.0,y:5.0}];

    let vp = vpsearch::Tree::new(&points);

    let (index, _) = vp.find_nearest(&Point{x:1.0,y:2.0});

    println!("The nearest point is at ({}, {})", points[index].x, points[index].y);
}
examples/newtype_ref.rs (line 21)
17
18
19
20
21
22
23
fn main() {
    let source_data = vec![[0; 64], [5; 64], [10; 64]];
    let reference_data: Vec<_> = source_data.iter().map(LotsaDimensions).collect();
    let vp = vpsearch::Tree::new(&reference_data);
    let (index, dist) = vp.find_nearest(&LotsaDimensions(&[6; 64]));
    println!("The element at {} is the nearest, off by {}", index, dist);
}
Source§

impl<Item: MetricSpace<Impl> + Clone, Impl> Tree<Item, Impl, Owned<Item::UserData>>

Source

pub fn new_with_user_data_owned( items: &[Item], user_data: Item::UserData, ) -> Self

Create a Vantage Point tree for fast nearest neighbor search.

  • items — Array of items that will be searched.
  • user_data — Reference to any object that is passed down to item.distance()
Source§

impl<Item: MetricSpace<Impl> + Clone, Impl> Tree<Item, Impl, ()>

Source

pub fn new_with_user_data_ref( items: &[Item], user_data: &Item::UserData, ) -> Self

The tree doesn’t have to own the UserData. You can keep passing it to find_nearest().

Source

pub fn find_nearest( &self, needle: &Item, user_data: &Item::UserData, ) -> (usize, Item::Distance)

Source§

impl<Item: MetricSpace<Impl> + Clone, Ownership, Impl> Tree<Item, Impl, Ownership>

Source

pub fn find_nearest_custom<ReturnBy: BestCandidate<Item, Impl>>( &self, needle: &Item, user_data: &Item::UserData, best_candidate: ReturnBy, ) -> ReturnBy::Output

All the bells and whistles version. For best_candidate implement BestCandidate<Item, Impl> trait.

Trait Implementations§

Source§

impl<Item: Debug + Clone + MetricSpace<UserImpl>, UserImpl, Ownership> Debug for Tree<Item, UserImpl, Ownership>

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<Item, Impl, Ownership> Freeze for Tree<Item, Impl, Ownership>
where Ownership: Freeze,

§

impl<Item, Impl, Ownership> RefUnwindSafe for Tree<Item, Impl, Ownership>
where Ownership: RefUnwindSafe, Item: RefUnwindSafe, <Item as MetricSpace<Impl>>::Distance: RefUnwindSafe,

§

impl<Item, Impl, Ownership> Send for Tree<Item, Impl, Ownership>
where Ownership: Send, Item: Send, <Item as MetricSpace<Impl>>::Distance: Send,

§

impl<Item, Impl, Ownership> Sync for Tree<Item, Impl, Ownership>
where Ownership: Sync, Item: Sync, <Item as MetricSpace<Impl>>::Distance: Sync,

§

impl<Item, Impl, Ownership> Unpin for Tree<Item, Impl, Ownership>
where Ownership: Unpin, Item: Unpin, <Item as MetricSpace<Impl>>::Distance: Unpin,

§

impl<Item, Impl, Ownership> UnwindSafe for Tree<Item, Impl, Ownership>
where Ownership: UnwindSafe, Item: UnwindSafe, <Item as MetricSpace<Impl>>::Distance: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.