Struct quadtree_rs::Quadtree

pub struct Quadtree<U, V> where
    U: PrimInt + Default,  { /* fields omitted */ }

A data structure for storing and accessing data in 2d space.

For historical context, other implementations, and potential uses of a quadtree, see the quadtree article on Wikipedia.

Parameterization

Quadtree<U, V> is parameterized over

• U, the type of the coordinate, and
• V, the value being stored.

U must implement num::PrimInt and a set of arithmetic operations necessary for coordinate insertion and comparison. U must also implement std::default for derive_builder semantics.

Strictness

Some methods (.query(), .modify(), and .delete()) have strict variants. While the default behavior is for any operation to apply to all regions which intersect some operational region, the strict behavior is for the operation to apply only to those regions which are totally contained by the operational region.

Methods

impl<U, V> Quadtree<U, V> where
    U: PrimInt + Default, 

pub fn new(depth: usize) -> Self

Creates a new, empty quadtree with some depth. A quadtree with depth n will accept coordinates in the range [0, 2^n].

use quadtree_rs::{point::Point, Quadtree};

let qt = Quadtree::<u32, u8>::new(/*depth=*/ 2);

// The anchor of a rectangular region is its top-left coordinate.
// By default, quadtrees are anchored at (0, 0).
assert_eq!(qt.anchor(), Point {x: 0, y: 0});
assert_eq!(qt.depth(), 2);
assert_eq!(qt.width(), 4);
assert_eq!(qt.height(), 4);

pub fn new_with_anchor(anchor: Point<U>, depth: usize) -> Self

Creates a new, empty quadtree with some depth and an explicit anchor.

The anchor of a rectangular region is its upper-left coordinate. The anchor argument is of type point::Point, and can either be explicit (Point {x: 2, y: 4}) or implicit ((2, 4).into()).

use quadtree_rs::{point::Point, Quadtree};

let anchor = Point {x: 2, y: 4};
let depth = 3_usize;
let qt = Quadtree::<u32, u8>::new_with_anchor(anchor, depth);

assert_eq!(qt.depth(), 3);
assert_eq!(qt.anchor(), Point {x: 2, y: 4});
assert_eq!(qt.width(), 8);
assert_eq!(qt.height(), 8);

pub fn anchor(&self) -> Point<U>

The top-left corner (anchor) of the region which this quadtree represents.

pub fn width(&self) -> usize

The width of the region which this quadtree represents.

pub fn height(&self) -> usize

The height of the region which this quadtree represents.

pub fn depth(&self) -> usize

The depth of the quadtree.

pub fn len(&self) -> usize

The number of elements in the quadtree.

pub fn is_empty(&self) -> bool

Whether or not the quadtree is empty.

pub fn contains(&self, area: Area<U>) -> bool

Whether or not some trial region could fit in the region which this quadtree represents.

pub fn insert(&mut self, region: Area<U>, val: V) -> Option<u64>

Associate some value with a region in the quadtree.

If insertion is successful, returns a unique handle to the value.

If the region is too large for, or doesn't overlap with, the region which this quadtree represents, returns None.

use quadtree_rs::{area::AreaBuilder, point::Point, Quadtree};

let mut qt = Quadtree::<u32, i8>::new(8);

let region = AreaBuilder::default()
    .anchor(Point {x: 4, y: 5})
    .dimensions((2,3))
    .build().unwrap();

let handle_a_1 = qt.insert(region, 5).unwrap();
let handle_a_2 = qt.insert(region, 5).unwrap();

// Even though we inserted 5 at the same point in the quadtree, the
// two handles returned were not the same.
assert_ne!(handle_a_1, handle_a_2);

pub fn insert_pt(&mut self, point: Point<U>, val: V) -> Option<u64>

Alias for .insert() which expects a Point instead of an Area.

(An Area is really just a Point with dimensions (1, 1), so the point still has to fit within the region.)

use quadtree_rs::{point::Point, Quadtree};

let mut qt = Quadtree::<u32, i8>::new(2);

assert!(qt.insert_pt(Point { x: 1, y: 2 }, 5_i8).is_some());

pub fn get(&self, handle: u64) -> Option<&Entry<U, V>>

Given the handle from an .insert() operation, provides read-only access to the associated Entry<U, V> struct.

Handles are unique and never re-used, so lookup of a handle to a now-deleted entry can fail and return None.

use quadtree_rs::{area::AreaBuilder, point::Point, Quadtree};

let mut qt = Quadtree::<u32, f32>::new(4);

let region = AreaBuilder::default()
    .anchor(Point {x: 0, y: 1})
    .dimensions((2, 3))
    .build().unwrap();
let handle = qt.insert(region, 9.87).unwrap();

let entry = qt.get(handle).unwrap();
assert_eq!(entry.value_ref(), &9.87);

pub fn get_mut(&mut self, handle: u64) -> Option<&mut Entry<U, V>>

A mutable variant of .get() which provides mutable access to the associated Entry<U, V> struct.

use quadtree_rs::{area::AreaBuilder, point::Point, Quadtree};

let mut qt = Quadtree::<u32, f32>::new(4);

let region = AreaBuilder::default()
    .anchor(Point {x: 0, y: 1})
    .dimensions((2, 3))
    .build().unwrap();
let handle: u64 = qt.insert(region, 9.87).unwrap();

if let Some(entry) = qt.get_mut(handle) {
  *entry.value_mut() += 1.0;
}

assert_eq!(qt.get(handle).unwrap().value_ref(), &10.87);

Important traits for Query<'a, U, V>

impl<'a, U, V> Iterator for Query<'a, U, V> where
    U: PrimInt + Default,  type Item = &'a Entry<U, V>;

pub fn query(&self, area: Area<U>) -> Query<U, V>

Returns an iterator over &Entry<U, V> structs representing values within the query region.

use quadtree_rs::{area::AreaBuilder, Quadtree};

//   0123456
// 0 ░░░░░░░
// 1 ░░▒▒▒░░    (2,1)->3x2
// 2 ░░▒▒▒░░
// 3 ░░░░░░░
// 4 ░▒▒▒░░░    (1,4)->3x1
// 5 ░░░░░░░
let mut qt = Quadtree::<u32, char>::new(4);

let region_a = AreaBuilder::default()
    .anchor((2, 1).into())
    .dimensions((3, 2))
    .build().unwrap();
qt.insert(region_a, 'a');

let region_b = AreaBuilder::default()
    .anchor((1, 4).into())
    .dimensions((3, 1))
    .build().unwrap();
qt.insert(region_b, 'b');

//   0123456
// 0 ░░░░░░░
// 1 ░░▓▒▒░░  <-- Query over the region
// 2 ░░▒▒▒░░      (2,1)->1x1
// 3 ░░░░░░░
// 4 ░▒▒▒░░░
// 5 ░░░░░░░
let region_c = AreaBuilder::default()
    .anchor((2, 1).into()).build().unwrap();
let mut query_a = qt.query(region_c);

// We can use the Entry API to destructure the result.
let entry = query_a.next().unwrap();
assert_eq!(entry.area().height(), 2);
assert_eq!(entry.value_ref(), &'a');

// But that was the only result.
assert!(query_a.next().is_none());

//   0123456
// 0 ░░░░░░░
// 1 ░▒▓▓▓▒░  <-- query over the region
// 2 ░▒▓▓▓▒░      (0,0)->6x6.
// 3 ░▒▒▒▒▒░
// 4 ░▓▓▓▒▒░
// 5 ░░░░░░░
let region_d = AreaBuilder::default()
    .anchor((1, 1).into())
    .dimensions((4, 4))
    .build().unwrap();
let query_b = qt.query(region_d);

// It's unspecified what order the regions should
// return in, but there will be two of them.
assert_eq!(query_b.count(), 2);

Important traits for Query<'a, U, V>

impl<'a, U, V> Iterator for Query<'a, U, V> where
    U: PrimInt + Default,  type Item = &'a Entry<U, V>;

pub fn query_strict(&self, area: Area<U>) -> Query<U, V>

A strict variant of .query().

pub fn modify<F>(&mut self, area: Area<U>, f: F) where
    F: Fn(&mut V) + Copy, 

Accepts a modification lambda and applies it to all elements in the quadtree which intersecting the described region.

use quadtree_rs::{area::AreaBuilder, Quadtree};

let mut qt = Quadtree::<u8, bool>::new(3);

let region_a = AreaBuilder::default()
    .anchor((0, 0).into())
    .build().unwrap();
let handle = qt.insert(region_a, true).unwrap();

// Run a modification lambda over all values in region_a...
qt.modify(region_a, |i| *i = false);

// ...and verify that the value was applied.
assert_eq!(qt.get(handle).unwrap().value_ref(), &false);

pub fn modify_strict<F>(&mut self, area: Area<U>, f: F) where
    F: Fn(&mut V) + Copy, 

A strict variant of .modify().

pub fn modify_all<F>(&mut self, f: F) where
    F: Fn(&mut V) + Copy, 

Alias for .modify() which runs over the entire quadtree.

pub fn reset(&mut self)

Resets the quadtree to a totally empty state.

Important traits for IntoIter<U, V>

impl<U, V> Iterator for IntoIter<U, V> where
    U: PrimInt + Default,  type Item = Entry<U, V>;

pub fn delete(&mut self, area: Area<U>) -> IntoIter<U, V>

Deletes all value associations which overlap a region in the tree.

Along the way, consumed Entry<U, V> entries are collected and returned in an iterator IntoIter<U, V>.

use quadtree_rs::{area::AreaBuilder, Quadtree};

let mut qt = Quadtree::<u32, f64>::new(4);

let region_a = AreaBuilder::default()
    .anchor((0, 0).into())
    .dimensions((2, 2))
    .build().unwrap();
qt.insert(region_a, 1.23);

let region_b = AreaBuilder::default()
    .anchor((1, 1).into())
    .dimensions((3, 2))
    .build().unwrap();
qt.insert(region_b, 4.56);

//   0123
// 0 ░░
// 1 ░▓╳░  <-- ╳ is the deletion region
// 2  ░░░

let region_c = AreaBuilder::default()
    .anchor((2, 1).into()).build().unwrap();
let mut returned_entries = qt.delete(region_c);

// We've removed one object from the quadtree.
assert_eq!(returned_entries.next().unwrap().value_ref(),
           &4.56);

// And left one behind.
assert_eq!(qt.len(), 1);

Important traits for IntoIter<U, V>

impl<U, V> Iterator for IntoIter<U, V> where
    U: PrimInt + Default,  type Item = Entry<U, V>;

pub fn delete_strict(&mut self, area: Area<U>) -> IntoIter<U, V>

A strict variant of .delete().

pub fn delete_by_handle(&mut self, handle: u64) -> Option<Entry<U, V>>

Given an handle, deletes a single item from the Quadtree. If that handle was found, delete_by_handle() returns an Entry<U, V> containing its former region and value. Otherwise, returns None.

Important traits for IntoIter<U, V>

impl<U, V> Iterator for IntoIter<U, V> where
    U: PrimInt + Default,  type Item = Entry<U, V>;

pub fn retain<F>(&mut self, f: F) -> IntoIter<U, V> where
    F: FnMut(&mut V) -> bool,
    U: Hash, 

Retains only the elements specified by the predicate.

In other words, remove all items such that f(&mut v) returns false.

Important traits for Iter<'a, U, V>

impl<'a, U, V> Iterator for Iter<'a, U, V> where
    U: PrimInt + Default,  type Item = &'a Entry<U, V>;

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

Returns an iterator (Iter<U, V>) over all &'a Entry<U, V> region/value associations in the Quadtree.

Important traits for Regions<'a, U, V>

impl<'a, U, V> Iterator for Regions<'a, U, V> where
    U: PrimInt + Default,  type Item = Area<U>;

pub fn regions(&self) -> Regions<U, V>

Returns an iterator (Regions<U, V>) over all Area<U> regions in the Quadtree.

Important traits for Values<'a, U, V>

impl<'a, U, V> Iterator for Values<'a, U, V> where
    U: PrimInt + Default,  type Item = &'a V;

pub fn values(&self) -> Values<U, V>

Returns an iterator (Values<U, V>) over all &'a V values in the Quadtree.

Trait Implementations

impl<U: PartialEq, V: PartialEq> PartialEq<Quadtree<U, V>> for Quadtree<U, V> where
    U: PrimInt + Default, 

fn eq(&self, other: &Quadtree<U, V>) -> bool

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

fn ne(&self, other: &Quadtree<U, V>) -> bool

This method tests for !=.

impl<U: Eq, V: Eq> Eq for Quadtree<U, V> where
    U: PrimInt + Default, 

impl<'a, U, V> IntoIterator for &'a Quadtree<U, V> where
    U: PrimInt + Default, 

type Item = &'a Entry<U, V>

The type of the elements being iterated over.

type IntoIter = Iter<'a, U, V>

Which kind of iterator are we turning this into?

Important traits for Iter<'a, U, V>

impl<'a, U, V> Iterator for Iter<'a, U, V> where
    U: PrimInt + Default,  type Item = &'a Entry<U, V>;

fn into_iter(self) -> Iter<'a, U, V>

Creates an iterator from a value.

impl<U, V> IntoIterator for Quadtree<U, V> where
    U: PrimInt + Default, 

type Item = Entry<U, V>

The type of the elements being iterated over.

type IntoIter = IntoIter<U, V>

Which kind of iterator are we turning this into?

Important traits for IntoIter<U, V>

impl<U, V> Iterator for IntoIter<U, V> where
    U: PrimInt + Default,  type Item = Entry<U, V>;

fn into_iter(self) -> IntoIter<U, V>

Creates an iterator from a value.

impl<U, V> Extend<((U, U), V)> for Quadtree<U, V> where
    U: PrimInt + Default, 

Extend<((U, U), V)> will silently drop values whose coordinates do not fit in the region represented by the Quadtree. It is the responsibility of the callsite to ensure these points fit.

fn extend<T>(&mut self, iter: T) where
    T: IntoIterator<Item = ((U, U), V)>, 

Extends a collection with the contents of an iterator.

impl<U: Debug, V: Debug> Debug for Quadtree<U, V> where
    U: PrimInt + Default, 

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

Formats the value using the given formatter.