Struct QuadTree

pub struct QuadTree<C, Item, Cap = DynCap>
where
    C: Coordinate,
{ /* private fields */ }

Parameter

C: The type used for coordinates Item: The type to be saved CAP: The maximum capacity of each level

Implementations

impl<C, Item, Cap> QuadTree<C, Item, Cap>

where Cap: Capacity, C: Coordinate,

pub fn new_with_capacity(boundary: Boundary<C>, capacity: Cap) -> Self

Create a new quad tree for a given area where each level of the tree has a given capacity.

Example

use qutee::*;
struct MyItem;
let tree = QuadTree::<_, MyItem, DynCap>::new_with_capacity(Boundary::between_points((10,10), (20,20)), DynCap::new(20));
assert_eq!(tree.capacity(), 20);

pub fn insert_at( &mut self, point: impl Into<Point<C>>, value: Item, ) -> Result<(), QuadTreeError<C>>

Insert new item into the quad tree.

Errors

Returns an error if the point is out of bounds.

Example

use qutee::*;
let mut tree = QuadTree::<_,_,ConstCap<2>>::new_with_const_cap(Boundary::between_points((0,0), (10,10)));
assert!(tree.insert_at((5,5), ()).is_ok());
assert!(tree.insert_at((11,11), ()).is_err());

pub fn insert_at_unchecked(&mut self, point: impl Into<Point<C>>, value: Item)

Same as insert_at except that no bounds check is performed.

Example

use qutee::*;
let mut tree = QuadTree::<_,_,ConstCap<2>>::new_with_const_cap(Boundary::between_points((0,0), (10,10)));
tree.insert_at_unchecked((5,5), ());
assert_eq!(tree.iter().count(), 1);

pub fn query<A>(&self, area: A) -> Query<'_, C, A, Item, Cap>

where A: Area<C>,

Get all items in a given area.

Example

use qutee::*;
let mut tree = QuadTree::<_,_,ConstCap<2>>::new_with_const_cap(Boundary::between_points((0,0), (10,10)));
tree.insert_at((3,5), 1);
tree.insert_at((1,0), 2);
tree.insert_at((7,3), 4);
tree.insert_at((9,4), 5);
let mut res = tree.query(Boundary::between_points((2,1), (8,9))).copied().collect::<Vec<_>>();
res.sort();
assert_eq!(res, vec![1,4]);

pub fn query_points<A>(&self, area: A) -> QueryPoints<'_, C, A, Item, Cap>

where A: Area<C>,

Get all items in a given area and their coordinates.

Example

use qutee::*;
let mut tree = QuadTree::<_,_,ConstCap<2>>::new_with_const_cap(Boundary::between_points((0,0), (10,10)));
tree.insert_at((3,5), 1);
tree.insert_at((1,0), 2);
tree.insert_at((7,3), 4);
tree.insert_at((9,4), 5);
let mut res = tree.query_points(Boundary::between_points((2,1), (8,9))).copied().collect::<Vec<_>>();
res.sort_by(|a,b| a.1.cmp(&b.1));
assert_eq!(res, vec![
    ((3,5).into(), 1),
    ((7,3).into(), 4),
]);

pub fn iter(&self) -> Iter<'_, C, Item, Cap>

Get an iterator over all items.

pub fn iter_points(&self) -> IterPoints<'_, C, Item, Cap>

Get an iterator over all items and their coordinates.

pub fn boundary(&self) -> &Boundary<C>

Returns the boundary of this QuadTree

pub fn capacity(&self) -> usize

Returns the capacity

impl<C, Item, Cap> QuadTree<C, Item, Cap>

where Cap: Capacity, C: Coordinate, Item: AsPoint<C>,

pub fn insert(&mut self, item: Item) -> Result<(), QuadTreeError<C>>

Insert a new item

Errors

Returns an error if the item is out of bounds.

Example

use qutee::*;
struct Item {
    x: usize,
    y: usize,
}
impl AsPoint<usize> for Item {
    fn as_point(&self) -> Point<usize> {
        (self.x, self.y).into()
    }
}
let mut quad_tree = QuadTree::new_with_dyn_cap(Boundary::between_points((0,0),(10,10)), 5);
assert!(quad_tree.insert(Item {
    x: 5,
    y: 5,
}).is_ok());

pub fn insert_unchecked(&mut self, item: Item)

Same as insert except that no bounds check is performed.

impl<C, Item> QuadTree<C, Item, DynCap>

where C: Coordinate,

pub fn new_with_dyn_cap(boundary: Boundary<C>, cap: usize) -> Self

Create a new QuadTree

impl<C, Item, const CAP: usize> QuadTree<C, Item, ConstCap<CAP>>

where C: Coordinate,

pub fn new_with_const_cap(boundary: Boundary<C>) -> Self

Create a new QuadTree with a constant capacity

Trait Implementations

impl<C, Item: Clone, Cap: Clone> Clone for QuadTree<C, Item, Cap>

where C: Coordinate + Clone,

fn clone(&self) -> QuadTree<C, Item, Cap>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<C, Item: Debug, Cap: Debug> Debug for QuadTree<C, Item, Cap>

where C: Coordinate + Debug,

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

Formats the value using the given formatter.

impl<C, Item: PartialEq, Cap: PartialEq> PartialEq for QuadTree<C, Item, Cap>

where C: Coordinate + PartialEq,

fn eq(&self, other: &QuadTree<C, Item, Cap>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<C, Item: Eq, Cap: Eq> Eq for QuadTree<C, Item, Cap>

where C: Coordinate + Eq,

impl<C, Item, Cap> StructuralPartialEq for QuadTree<C, Item, Cap>

where C: Coordinate,