To teach myself Rust, I implemented a simple Quadtree over 2D points with insert, delete, contain function.

My code does not seems "idiomatic rust code" to me. Also I think it's not so fast.

1. simple test for check code work

Code:

use std::ops::DerefMut;

#[derive(PartialEq, Copy, Clone)]
pub struct Point {
x: u32,
y: u32,
}

impl Point {
pub fn new(x: u32, y: u32) -> Self {
Point {
x,
y,
}
}
}

x: u32,
y: u32,
width: u32,
height: u32,
count: u8,
capacity: u8,
elements: Vec<Point>, // Option?
}

fn new(x: u32, y: u32, width: u32, height: u32, capacity: u8) -> Self {
x,
y,
width,
height,
count: 0,
capacity,
child: Vec::with_capacity(capacity as usize),
elements: Vec::with_capacity(capacity as usize),
}
}

fn contain(&mut self, p: &Point) -> bool {
// bottom left
let botlx = self.x - (self.width / 2);
let botly = self.y - (self.height / 2);
//top right
let toprx = self.x + (self.width / 2);
let topry = self.y + (self.height / 2);

p.x > botlx && p.x < toprx && p.y > botly && p.y < topry
}

fn split(&mut self) {
// center
let x = self.x;
let y = self.y;
// child node width && height
let w = self.width / 2;
let h = self.height / 2;

self.child.push(Some(Box::new(QuadNode::new(x - w / 2, y + h / 2, w, h, self.capacity))));
self.child.push(Some(Box::new(QuadNode::new(x + w / 2, y + h / 2, w, h, self.capacity))));
self.child.push(Some(Box::new(QuadNode::new(x + w / 2, y - h / 2, w, h, self.capacity))));
self.child.push(Some(Box::new(QuadNode::new(x - w / 2, y - h / 2, w, h, self.capacity))));
}

/*
fn find(&mut self, p: &Point) -> &mut QuadNode { // -> &mut QuadNode?
match self.child.len() {
0 => {
// no child
if self.contain(p) {
return self;
} else {
return None;
}
},
_ => {
// have child
let mut flag: bool = false;

for child in self.child.iter().filter_map(Option::as_ref) {

}
}
}
}
*/

fn insert(&mut self, p: Point) {
match self.child.len() {
0 => {
if self.contain(&p) {
// no child
if self.count >= self.capacity {
// need to split
self.split();
self.insert(p);
} else {
// just push
println!("insert new element");
self.count += 1;
self.elements.push(p);

}
}
}
_ => {
// have child
for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
child.insert(p);
}
}
}
}

fn delete(&mut self, p: Point) {
match self.child.len() {
0 => {
if self.contain(&p) {
self.remove(&p);
self.count -= 1;
}
}
_ => {
let mut flag: bool = false;
for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
flag = child.contain(&p);
}
if flag {
// parent node count -1
self.count -= 1;

for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
child.delete(p);
}

// need to un_split?
if self.count < self.capacity {
self.clear();
}
}
}
}
}

fn clear(&mut self) {

// add child's elements to parent node
for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
self.elements.extend(child.elements.iter().cloned()); // append?
}

// clear child node
self.child.clear();
}

fn remove(&mut self, p: &Point) {
// magic remove
let pos = self.elements.iter().position(|x| *x == *p).unwrap();
self.elements.remove(pos);
}
}

fn main() {}

}

pub fn new() -> Self {
root: None,
}
}

pub fn insert(&mut self, p: Point) {
match self.root {
Some(ref mut root) => {
root.insert(p);
}
None => {
self.root = Some(Box::new(QuadNode::new(100_000 / 2, 100_000 / 2, 100_000, 100_000, 10)));
}
}
}

pub fn init(&mut self) {
match self.root {
None => {
self.root = Some(Box::new(QuadNode::new(100_000 / 2, 100_000 / 2, 100_000, 100_000, 10)));
println!("create new node");
}
_ => {
return;
}
}
}

pub fn delete(&mut self, p: Point) {
match self.root {
Some(ref mut root) => {
root.delete(p);
}
_ => {
return;
}
}
}

pub fn contain(&mut self, p: &Point) -> bool {
match self.root {
Some(ref mut root) => {
if root.contain(p) {
return true;
} else {
return false;
}
},
_ => {
return false;
}
}
}
}


Simple test:

#[cfg(test)]
mod test {
use super::*;

#[test]
fn simple_insert_five_points() {
qtree.init();
let p1 = Point::new(10, 10);
let p2 = Point::new(30, 30);
let p3 = Point::new(40, 40);
let p4 = Point::new(190, 190);
let p5 = Point::new(170, 170);
qtree.insert(p1);
qtree.insert(p2);
qtree.insert(p3);
qtree.insert(p4);
qtree.insert(p5);
}

// soo sloooow
#[test]
qtree.init();

for i in 1..10000 {
qtree.insert(Point { x: i, y: i });
}
}
}


Edit: I wrote it to use this in my game, so an example of use is something like this (in pseudocode):

fn game_loop () {
input_player();
render();
for node.contain(player) { // no idea how to write this
player.update();
//collision detected here
}

}