`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, `[src]

#### `pub fn new(depth: usize) -> Self`[src]

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`[src]

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>`[src]

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

#### `pub fn width(&self) -> usize`[src]

The width of the region which this quadtree represents.

#### `pub fn height(&self) -> usize`[src]

The height of the region which this quadtree represents.

#### `pub fn len(&self) -> usize`[src]

The number of elements in the quadtree.

#### `pub fn is_empty(&self) -> bool`[src]

Whether or not the quadtree is empty.

#### `pub fn contains(&self, area: Area<U>) -> bool`[src]

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>`[src]

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>`[src]

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>>`[src]

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>>`[src]

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>### 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>`[src]

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>### 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>`[src]

A strict variant of `.query()`.

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

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, `[src]

A strict variant of `.modify()`.

#### `pub fn modify_all<F>(&mut self, f: F) where    F: Fn(&mut V) + Copy, `[src]

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

#### `pub fn reset(&mut self)`[src]

Resets the quadtree to a totally empty state.

#### ⓘImportant traits for IntoIter<U, V>### 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>`[src]

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>### 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>`[src]

A strict variant of `.delete()`.

#### `pub fn delete_by_handle(&mut self, handle: u64) -> Option<Entry<U, V>>`[src]

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>### 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, `[src]

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>### 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>`[src]

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>### 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>`[src]

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

#### ⓘImportant traits for Values<'a, U, V>### 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>`[src]

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

## Trait Implementations

### `impl<U, V> Extend<((U, U), V)> for Quadtree<U, V> where    U: PrimInt + Default, `[src]

`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.

### `impl<'a, U, V> IntoIterator for &'a Quadtree<U, V> where    U: PrimInt + Default, `[src]

#### `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?

### `impl<U, V> IntoIterator for Quadtree<U, V> where    U: PrimInt + Default, `[src]

#### `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?

## Blanket Implementations

### `impl<I> IntoIterator for I where    I: Iterator, `[src]

#### `type Item = <I as Iterator>::Item`

The type of the elements being iterated over.

#### `type IntoIter = I`

Which kind of iterator are we turning this into?

### `impl<T, U> TryFrom for T where    U: Into<T>, `[src]

#### `type Error = Infallible`

The type returned in the event of a conversion error.

### `impl<T, U> TryInto for T where    U: TryFrom<T>, `[src]

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

The type returned in the event of a conversion error.