immutable quadtree implementation

quad_tree.rs

use std::fmt::Debug;
use std::mem;
use crate::quad_tree::shape::{Point, Rectangle};

pub struct QuadTree<TValue: Debug> {
    root: HeapQuadTreeNode<TValue>,
}

impl<TValue: Debug + Copy + Clone> QuadTree<TValue> {
    pub fn new() -> Self {
        QuadTree {
            root: None
        }
    }

    pub fn insert(&mut self, point: Point, value: TValue) {
        let root = self.root.take();
        self.root = self._insert(root, point, value);
    }

    fn _insert(&mut self,
               mut current: HeapQuadTreeNode<TValue>,
               point: Point,
               value: TValue) -> HeapQuadTreeNode<TValue> {
        if current.is_none() {
            return Some(Box::new(QuadTreeNode::new(point, value)));
        }

        let current_box = current.as_mut().unwrap();
        let quad_side = QuadTree::<TValue>::define_side(&point, &current_box.point);
        let node_ref = &mut current_box.quads[quad_side as usize];

        let mut node = self._insert(node_ref.take(), point, value);
        *node_ref = node.take();
        return current.take();
    }

    pub fn foreach<F: FnMut(&Point, &TValue)>(&mut self, mut f: F) {
        let root = self.root.take();
        let root = self._foreach(root, &mut f);
        self.root = root;
    }

    fn _foreach<F: FnMut(&Point, &TValue)>(&self, mut current: HeapQuadTreeNode<TValue>, f: &mut F) -> HeapQuadTreeNode<TValue> {
        type Side = QuadTreeNodeSide;

        if current.is_none() {
            return None;
        }
        let mut node_ref = current.unwrap();

        f(&node_ref.point, &node_ref.value);

        node_ref.quads[Side::TopLeft as usize]
            = self._foreach(node_ref.quads[Side::TopLeft as usize].take(), f);
        node_ref.quads[Side::TopRight as usize]
            = self._foreach(node_ref.quads[Side::TopRight as usize].take(), f);
        node_ref.quads[Side::BottomLeft as usize]
            = self._foreach(node_ref.quads[Side::BottomLeft as usize].take(), f);
        node_ref.quads[Side::BottomRight as usize]
            = self._foreach(node_ref.quads[Side::BottomRight as usize].take(), f);

        return Some(node_ref)
    }

    pub fn search_as_window(&mut self, window: &Rectangle) -> Vec<(Point, TValue)> {
        self._search_as_window(window)
    }

    fn _search_as_window(&mut self, window: &Rectangle) -> Vec<(Point, TValue)>  {
        let mut result: Vec<(Point, TValue)> = vec![];

        self.foreach(|point_ref: &Point, value_ref: &TValue| {
            if window.is_include(point_ref) {
                result.push((point_ref.clone(), value_ref.clone()))
            }
        });

        return result;
    }

    fn define_side(new_point: &Point, current_point: &Point) -> QuadTreeNodeSide {
        type Side = QuadTreeNodeSide;

        let is_left = new_point.x <= current_point.x;
        let is_top = new_point.y >= current_point.y;

        if is_left && is_top {
            return Side::TopLeft;
        } else if !is_left && is_top {
            return Side::TopRight;
        } else if is_left && !is_top {
            return Side::BottomLeft;
        } else if !is_left && !is_top {
            return Side::BottomRight;
        }

        return Side::Center;
    }
}

struct QuadTreeNode<TValue: Debug> {
    point: Point,
    value: TValue,
    // [TL,TR,
    // BL, BR]
    quads: [HeapQuadTreeNode<TValue>; 4],
}

enum QuadTreeNodeSide {
    TopLeft,
    TopRight,
    BottomLeft,
    BottomRight,
    Center,
}

impl<TValue: Debug> QuadTreeNode<TValue> {
    pub fn new(point: Point, value: TValue) -> Self {
        QuadTreeNode {
            point,
            value,
            quads: [None, None, None, None],
        }
    }
}

type HeapQuadTreeNode<TValue> = Option<Box<QuadTreeNode<TValue>>>;

pub mod shape {
    #[derive(Debug, Copy, Clone)]
    pub struct Point<T = isize> {
        pub x: T,
        pub y: T,
    }

    #[derive(Debug)]
    pub struct Rectangle<T=isize> {
        pub x0: T,
        pub y0: T,
        pub x1: T,
        pub y1: T
    }

    impl Rectangle {
        pub fn is_include(&self, point: &Point) -> bool {
            return self.x0 <= point.x
                && self.x1 >= point.x
                && self.y0 <= point.y
                && self.y1 >= point.y;
        }
    }
}