Attempt at quad tree

[jgilray]

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:

1. I see people using Option<Box<>> for Link, but in this case I couldn't make it work
2. 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);
                    }
                }
            },
        }
    }
}

[steffahn]

@jgilray

2. 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?

Yes. For example this section

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);

can just become

node.q3 = nqt.head;
self.head = Link::Node(node);

For this to work you just need to declare node mutable, i.e. replace the Link::Node(node) => { with Link::Node(mut node) => {.

[steffahn]

Here’s a simplified / restructured version of your code avoiding all kinds of extra steps (I hope I haven’t broken or altered the algorithm along the way...)

impl Link {
    fn insert(&mut self, x: usize, y: usize) {
        match *self {
            Link::Empty => {
                *self = Link::Trap(x,y)
            }
            Link::Trap(xtr, ytr) => {
                *self = Link::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.insert(xtr, ytr);
            }
            Link::Node(ref mut node) => {
                match (x < node.pivot_x, y < node.pivot_y) {
                    (true , true ) => node.q3.insert(x,y),
                    (true , false) => node.q2.insert(x,y),
                    (false, true ) => node.q4.insert(x,y),
                    (false, false) => node.q1.insert(x,y),
                }
            }
        }
    }
}

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) {
        self.head.insert(x,y)
    }
}

[jgilray]

Great!! Thanks for all the improvements. Works like a charm. BTW, when is mem::replace() required?

[steffahn]

Sure. Your use case of mem::replace wasn’t wrong. The thing was just that instead of moving out the node, modifying it and moving it back in, one could instead just leave it in place. I went about this in steps of simplifying the code before the mem::replaces just disappeared:

First step as in my first comment, avoid the new_nodes.

Now we’d be having, basically interactions like

// simplified to leave out all the other cases
match match mem::replace(&mut self.head, Link::Empty) {
    Link::Node(mut node /* moves the field `node` out of the matched value */) => {
        let mut nqt = Qtree::new();
        nqt.head = node.q3; // move field q3 out of `node`
        nqt.insert(x, y);

        node.q3 = nqt.head; // and move `nqt.head` back into it
        self.head = Link::Node(node); // move modified value into `self.head`
    }
}

I then saw that basically you’re moving the node out of self.head, modifying it and moving it back in, so I tried switching to access through the reference:

match &mut self.head {
    Link::Node(node /* <- now a mutable reference to the field of `self.head` */) => {
        let mut nqt = Qtree::new();
        nqt.head = node.q3 // move field q3 out of `node` -- doesn't work!!!
        nqt.insert(x, y);

        node.q3 = nqt.head; // and move `nqt.head` back into it
        // self.head = Link::Node(node); this step is gone now
    }
}

to make this work again, a mem::replace for node.q3 is necessary:

match &mut self.head {
    Link::Node(node /* <- now a mutable reference to the field of `self.head` */) => {
        let mut nqt = Qtree::new();
        nqt.head = mem::replace(&mut node.q3, Link::Empty); // get field q3 out of `node`
        nqt.insert(x, y);

        node.q3 = nqt.head; // and move `nqt.head` back into it
        // self.head = Link::Node(node); this step is gone now
    }
}

^ This code does not work 100% yet. There’s some trouble in the Link::Trap case with modifying self.head while we’re in a match branch over a mutable reference to it. The way this can be fixed is matching on self.head directly.

match self.head /* does not need to move out of `head` */ {
    Link::Node(ref mut node /* <- still a mutable reference to the field of `self.head` */) => {
        let mut nqt = Qtree::new();
        nqt.head = mem::replace(&mut node.q3, Link::Empty); // get field q3 out of `node`
        nqt.insert(x, y);

        node.q3 = nqt.head; // and move `nqt.head` back into it
        // self.head = Link::Node(node); this step is gone now
    }
}

match statements do, in general, not need to move out of their scrutinee, so no replace needed necessarily. They only need to move out of the scrutinee expression (self.head here) if any branch takes a non-Copy field by value. The Link::Trap branch can now copy the xtr and ytr fields by value and works fine, and the Link::Node branch must match on node through mutable reference as to avoid any moves out of the node field of self.head. This is what theref mut keywords archieve here.

---

Going back two steps to the topic of why the node.q3 needs mem::replace now:

The reason behind why this kind of interation with node.q3 (taking out, doing a recursive call and putting back in a value) doesn’t work through a reference is that in case of a panic, the putting-back-in step could be skipped and you’d be missing a value in node.q3 entirely. (Which is problematic if you don’t own the value in node -- for an owned node, rustc would just have you would just drop all the other fields of thenode, too, in the panic case.) There’s also the alternative workaround of using crates like replace_with or take_mut. Also, this could be prettified by using mem::take if Link implements Default.

However, in this case the nqt is only created to call insert on it (a method that works through mutable reference) and then destructured again by moving out its only field, head. If instead Link has the insert method implemented on iself, then the recursive call can happen directly through a mutable reference to node.q3, leading to the final code I posted above.

[jgilray]

Thanks so much for the detailed explanation, @steffahn!