This is my first attempt at a quad tree, actually at just about any linked structure. My code is working and I was able to keep Node and Link private. I'm happy to hear any comments, but specifically was wondering:

- I see people using Option<Box<>> for Link, but in this case I couldn't make it work
- It seem inefficient to replace Link::Node with a new node each time. Is there a way to simply update the Node that is already there?

Thanks!

Joe

```
pub struct Qtree {
head: Link,
}
enum Link {
Empty,
Trap(usize, usize),
Node(Box<Node>),
}
struct Node {
pivot_x: usize,
pivot_y: usize,
q1: Link, // quadrants around the pivot
q2: Link,
q3: Link,
q4: Link,
}
impl Qtree {
pub fn new() -> Self {
Self { head: Link::Empty }
}
// insert a trap into the quad tree
pub fn insert(&mut self, x: usize, y: usize) {
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => {
self.head = Link::Trap(x, y);
},
Link::Trap(xtr, ytr) => {
let new_node = Box::new(Node {
pivot_x: x,
pivot_y: y,
q1: Link::Trap(x, y),
q2: Link::Empty,
q3: Link::Empty,
q4: Link::Empty,
});
self.head = Link::Node(new_node);
self.insert(xtr, ytr);
},
Link::Node(node) => {
// recursively insert a trap into a node in the proper quadrant
let mut nqt = Qtree::new();
if x < node.pivot_x {
if y < node.pivot_y {
nqt.head = node.q3;
nqt.insert(x, y);
let new_node = Box::new(Node {
pivot_x: node.pivot_x,
pivot_y: node.pivot_y,
q1: node.q1,
q2: node.q2,
q3: nqt.head,
q4: node.q4,
});
self.head = Link::Node(new_node);
} else {
nqt.head = node.q2;
nqt.insert(x, y);
let new_node = Box::new(Node {
pivot_x: node.pivot_x,
pivot_y: node.pivot_y,
q1: node.q1,
q2: nqt.head,
q3: node.q3,
q4: node.q4,
});
self.head = Link::Node(new_node);
}
} else {
if y < node.pivot_y {
nqt.head = node.q4;
nqt.insert(x, y);
let new_node = Box::new(Node {
pivot_x: node.pivot_x,
pivot_y: node.pivot_y,
q1: node.q1,
q2: node.q2,
q3: node.q3,
q4: nqt.head,
});
self.head = Link::Node(new_node);
} else {
nqt.head = node.q1;
nqt.insert(x, y);
let new_node = Box::new(Node {
pivot_x: node.pivot_x,
pivot_y: node.pivot_y,
q1: nqt.head,
q2: node.q2,
q3: node.q3,
q4: node.q4,
});
self.head = Link::Node(new_node);
}
}
},
}
}
}
```