Struct beehive::KdTree

pub struct KdTree<V, T> { /* fields omitted */ }

Generic KD-tree in hex space, implemented on a flat vector.

This implementation is not self-balancing. It may be necessary to rebuild trees after many insertions or deletions.

This type is only available with the collections feature.

Example

The collection can be created from (Geom<V>, T) iterators, where V is the coordinate unit and T is the associated value, and queried using hex geometries.

use std::iter::FromIterator;
use beehive::{PointAxial, VectorAxial, QuadPrism, KdTree};

let mut tree = KdTree::from_iter(vec![
    (PointAxial::new(0, 0, 0).into(), 2),
    (PointAxial::new(10, -10, 0).into(), 3),
    (PointAxial::new(-2, 4, 0).into(), 4),
    (PointAxial::new(1, -1, 0).into(), 5),
]);

// Individual inserts are also possible, but can result in sub-optimal
// structure depending on the order of insertion, since the tree cannot
// self-balance.
tree.insert(QuadPrism::from_base_size_axial(
    PointAxial::new(-100, -100, 0),
    VectorAxial::new(200, 200, 1),
), 1);

// Trees can be queried with points or (more commonly) QuadPrisms.
let query = tree.query(QuadPrism::from_base_size_axial(
    PointAxial::new(-10, -2, 0),
    VectorAxial::new(12, 8, 1),
));

let mut value = 0;
let mut count = 0;

for (_, n) in query {
    value += *n;
    count += 1;
}

assert_eq!(4, count);
assert_eq!(12, value);

// When the tree becomes unbalanced, it might be useful to rebuild the
// tree using the `FromIterator` implementation:
let rebuilt_tree = KdTree::from_iter(tree);

Methods

impl<V, T> KdTree<V, T>

pub fn new() -> Self

Creates an empty tree.

impl<V, T> KdTree<V, T> where
    V: Copy + Num + PartialOrd, 

pub fn count(&self) -> usize

Returns the count of nodes in this tree.

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

pub fn max_depth(&self) -> usize

Returns the maximum possible depth of this tree.

This can be used to determine whether the tree is out of balance, but can be inaccurate when the tree had a high capacity.

pub fn exact_depth(&self) -> usize

Returns the exact depth of this tree.

This is more accurate than max_depth but involves looking at the last elements in the underlying Vec.

pub fn insert<G>(&mut self, geom: G, data: T) where
    G: Into<Geom<V>>, 

Inserts one node into the tree. Insert order affects balance.

When it's necessary to insert a lot of data, using FromIterator may result in a more efficient tree.

pub fn get<F>(&self, predicate: F) -> Option<(&Geom<V>, &T)> where
    F: FnMut(&T) -> bool, 

Returns a reference to an arbitrary node where predicate is true for its tag, or None if there is no such node.

pub fn get_mut<F>(&mut self, predicate: F) -> Option<(&Geom<V>, &mut T)> where
    F: FnMut(&T) -> bool, 

Returns a mutable reference to an arbitrary node where predicate is true for its tag, or None if there is no such node.

pub fn remove<F>(&mut self, predicate: F) -> Option<(Geom<V>, T)> where
    F: FnMut(&T) -> bool, 

Removes an arbitrary node where predicate is true for its tag and returns it, or None if there is no such node.

pub fn query<G>(&self, geom: G) -> Query<V, T> where
    G: Into<Geom<V>>, 

Returns an iterator through all nodes whose geometry intersects with geom, in an arbitrary order.

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

Returns an iterator through all nodes, in an arbitrary order.

impl<V, T: PartialEq> KdTree<V, T> where
    V: Copy + Num + PartialOrd, 

pub fn get_at_data(&self, data: &T) -> Option<(&Geom<V>, &T)>

Returns a reference to an arbitrary node where its tag is equal to data, or None if there is no such node.

pub fn get_mut_at_data(&mut self, data: &T) -> Option<(&Geom<V>, &mut T)>

Returns a mutable reference to an arbitrary node where its tag is equal to data, or None if there is no such node.

pub fn remove_at_data(&mut self, data: &T) -> Option<(Geom<V>, T)>

Removes an arbitrary node where its tag is equal to data and returns it, or None if there is no such node.

Trait Implementations

impl<V: Clone, T: Clone> Clone for KdTree<V, T>

fn clone(&self) -> KdTree<V, T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<V: Debug, T: Debug> Debug for KdTree<V, T>

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

Formats the value using the given formatter.

impl<V, T> Default for KdTree<V, T>

fn default() -> Self

Returns the "default value" for a type.

impl<V: Eq, T: Eq> Eq for KdTree<V, T>

impl<V, T> FromIterator<(Geom<V>, T)> for KdTree<V, T> where
    V: Copy + Num + PartialOrd, 

fn from_iter<I: IntoIterator<Item = (Geom<V>, T)>>(into_iter: I) -> Self

Creates a value from an iterator.

impl<V, T> IntoIterator for KdTree<V, T> where
    V: Copy + Num + PartialOrd, 

type IntoIter = IntoIter<V, T>

Which kind of iterator are we turning this into?

type Item = (Geom<V>, T)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<V: PartialEq, T: PartialEq> PartialEq<KdTree<V, T>> for KdTree<V, T>

fn eq(&self, other: &KdTree<V, T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &KdTree<V, T>) -> bool

This method tests for !=.

impl<V, T> StructuralEq for KdTree<V, T>

impl<V, T> StructuralPartialEq for KdTree<V, T>