Struct quadtree_rs::Quadtree
source · pub struct Quadtree<U, V>where
U: PrimInt + Default,{ /* private fields */ }
Expand description
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, andV
, 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.
Implementations§
source§impl<U, V> Quadtree<U, V>where
U: PrimInt + Default,
impl<U, V> Quadtree<U, V>where U: PrimInt + Default,
sourcepub fn new(depth: usize) -> Self
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);
sourcepub fn new_with_anchor(anchor: Point<U>, depth: usize) -> Self
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);
sourcepub fn anchor(&self) -> Point<U>
pub fn anchor(&self) -> Point<U>
The top-left corner (anchor) of the region which this quadtree represents.
sourcepub fn contains(&self, area: Area<U>) -> bool
pub fn contains(&self, area: Area<U>) -> bool
Whether or not some trial region could fit in the region which this quadtree represents.
sourcepub fn insert(&mut self, region: Area<U>, val: V) -> Option<u64>
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);
sourcepub fn insert_pt(&mut self, point: Point<U>, val: V) -> Option<u64>
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());
sourcepub fn get(&self, handle: u64) -> Option<&Entry<U, V>>
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);
sourcepub fn get_mut(&mut self, handle: u64) -> Option<&mut Entry<U, V>>
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);
sourcepub fn query(&self, area: Area<U>) -> Query<'_, 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);
sourcepub fn modify<F>(&mut self, area: Area<U>, f: F)where
F: Fn(&mut V) + Copy,
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);
sourcepub fn modify_strict<F>(&mut self, area: Area<U>, f: F)where
F: Fn(&mut V) + Copy,
pub fn modify_strict<F>(&mut self, area: Area<U>, f: F)where F: Fn(&mut V) + Copy,
A strict variant of .modify()
.
sourcepub fn modify_all<F>(&mut self, f: F)where
F: Fn(&mut V) + Copy,
pub fn modify_all<F>(&mut self, f: F)where F: Fn(&mut V) + Copy,
Alias for .modify()
which runs over the entire
quadtree.
sourcepub fn delete(&mut self, area: Area<U>) -> IntoIter<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);
sourcepub fn delete_strict(&mut self, area: Area<U>) -> IntoIter<U, V> ⓘ
pub fn delete_strict(&mut self, area: Area<U>) -> IntoIter<U, V> ⓘ
A strict variant of .delete()
.
sourcepub fn delete_by_handle(&mut self, handle: u64) -> Option<Entry<U, V>>
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
.
sourcepub fn retain<F>(&mut self, f: F) -> IntoIter<U, V> ⓘwhere
F: FnMut(&mut V) -> bool,
U: Hash,
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
.
sourcepub fn iter(&self) -> Iter<'_, 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.
sourcepub fn regions(&self) -> Regions<'_, U, V> ⓘ
pub fn regions(&self) -> Regions<'_, U, V> ⓘ
Returns an iterator (Regions<U, V>
) over all Area<U>
regions
in the Quadtree.
sourcepub fn values(&self) -> Values<'_, U, V> ⓘ
pub fn values(&self) -> Values<'_, U, V> ⓘ
Returns an iterator (Values<U, V>
) over all &'a V
values in the
Quadtree.
Trait Implementations§
source§impl<U, V> Extend<((U, U), V)> for Quadtree<U, V>where
U: PrimInt + Default,
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.
source§fn extend<T>(&mut self, iter: T)where
T: IntoIterator<Item = ((U, U), V)>,
fn extend<T>(&mut self, iter: T)where T: IntoIterator<Item = ((U, U), V)>,
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)