coloctree 0.1.1

use rand::seq::SliceRandom;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
/// A 2D point u32 component
pub struct Point {
    /// The abscissa
    pub x: u32,
    /// The ordonate
    pub y: u32,
}

static DIRECTION_8_NEIGHBORS: [(i32, i32); 8] = [
    (-1, -1),
    (-1, 0),
    (-1, 1),
    (0, -1),
    (0, 1),
    (1, -1),
    (1, 0),
    (1, 1),
];

static DIRECTION_4_NEIGHBORS: [(i32, i32); 4] = [(-1, 0), (0, -1), (0, 1), (1, 0)];

impl Point {
    /// The euclidian distance but squared since we don't need the square root
    pub fn distance_squared(&self, other: &Point) -> usize {
        let dx = (self.x as i16) - (other.x as i16);
        let dy = (self.y as i16) - (other.y as i16);
        (dx * dx + dy * dy) as usize
    }

    fn neighbors_from_direction(&self, directions: &[(i32, i32)]) -> Vec<Self> {
        let mut neigh = Vec::new();
        for (dx, dy) in directions {
            let n_x = self.x as i32 + dx;
            let n_y = self.y as i32 + dy;

            if n_x >= 0 && n_y >= 0 {
                neigh.push(Point {
                    x: n_x as u32,
                    y: n_y as u32,
                });
            }
        }

        neigh
    }

    fn _neighbors8_ite(&self) -> impl Iterator<Item = Self> {
        let directions: [(i32, i32); 8] = [
            (-1, -1),
            (-1, 0),
            (-1, 1),
            (0, -1),
            (0, 1),
            (1, -1),
            (1, 0),
            (1, 1),
        ];
        let mut iter = Vec::new();
        for (dx, dy) in &directions {
            let n_x = self.x as i32 + dx;
            let n_y = self.y as i32 + dy;

            if n_x >= 0 && n_y >= 0 {
                iter.push(Point {
                    x: n_x as u32,
                    y: n_y as u32,
                });
            }
        }

        // NOTE: The shuffle should be made outside.
        iter.shuffle(&mut rand::rng());
        iter.into_iter()
    }

    /// The 8 neighbors of a point. Also called "Moore neighborhood".
    pub fn neighbors_8(&self) -> Vec<Self> {
        self.neighbors_from_direction(&DIRECTION_8_NEIGHBORS)
    }

    /// The 4 neighbors of a point. Also called "Von Neumann neighborhood".
    pub fn neighbors_4(&self) -> Vec<Self> {
        self.neighbors_from_direction(&DIRECTION_4_NEIGHBORS)
    }
}

#[derive(Clone, Debug)]
pub enum QuadTree {
    Empty,
    Point(Point),
    Node(QuadTreeNode),
}

impl QuadTree {
    pub fn is_empty(&self) -> bool {
        matches!(self, QuadTree::Empty)
    }
}

#[derive(Clone, Debug)]
pub struct QuadTreeNode {
    children: Box<[QuadTree; 4]>,
    corner_down: Point,
    corner_up: Point,
}
impl QuadTreeNode {
    pub fn new(corner_down: Point, corner_up: Point) -> Self {
        Self {
            children: vec![QuadTree::Empty; 4].try_into().unwrap(),
            corner_down,
            corner_up,
        }
    }
    pub fn insert(&mut self, point: Point) {
        println!("{:?} -> {:?}", point, self);
        let index_cadran = self.i_cadrant(point);
        match &mut self.children[index_cadran] {
            QuadTree::Empty => self.children[index_cadran] = QuadTree::Point(point),
            QuadTree::Point(old_point) => {
                if *old_point == point {
                    panic!("Point already in the QuadTree !");
                }
                let mut new_corner_up = self.corner_up;
                let mut new_corner_down = self.corner_down;

                match index_cadran {
                    0 => {
                        new_corner_up.x = (new_corner_down.x >> 1) + (new_corner_up.x >> 1);
                        new_corner_up.y = (new_corner_down.y >> 1) + (new_corner_up.y >> 1);
                    }
                    1 => {
                        new_corner_up.y = (new_corner_down.y >> 1) + (new_corner_up.y >> 1);
                        new_corner_down.x = (new_corner_down.x >> 1) + (new_corner_up.x >> 1) + 1;
                    }
                    2 => {
                        new_corner_up.x = (new_corner_down.x >> 1) + (new_corner_up.x >> 1);
                        new_corner_down.y = (new_corner_down.y >> 1) + (new_corner_up.y >> 1) + 1;
                    }
                    3 => {
                        new_corner_down.x = (new_corner_down.x >> 1) + (new_corner_up.x >> 1) + 1;
                        new_corner_down.y = (new_corner_down.y >> 1) + (new_corner_up.y >> 1) + 1;
                    }
                    _ => panic!("There is cadrant >= 4 or < 0 !"),
                };

                let mut quad = QuadTreeNode::new(new_corner_down, new_corner_up);
                quad.insert(*old_point);
                quad.insert(point);

                self.children[index_cadran] = QuadTree::Node(quad);
            }
            QuadTree::Node(quad) => {
                quad.insert(point);
            }
        }
    }
    pub fn remove(&mut self, point: Point) -> bool {
        let index_cadran = self.i_cadrant(point);
        match &mut self.children[index_cadran] {
            QuadTree::Empty => false,
            QuadTree::Point(old_point) => {
                if *old_point != point {
                    false
                } else {
                    self.children[index_cadran] = QuadTree::Empty;
                    true
                }
            }
            QuadTree::Node(quad) => {
                if quad.remove(point) {
                    if quad.is_empty() {
                        self.children[index_cadran] = QuadTree::Empty;
                    }
                    true
                } else {
                    false
                }
            }
        }
    }
    fn i_cadrant(&self, point: Point) -> usize {
        let mil_x = (self.corner_up.x >> 1) + (self.corner_down.x >> 1);
        let mil_y = (self.corner_up.y >> 1) + (self.corner_down.y >> 1);

        let Point { x, y } = point;

        if x <= mil_x {
            if y <= mil_y { 0 } else { 2 }
        } else {
            if y <= mil_y { 1 } else { 3 }
        }
    }

    pub fn is_empty(&self) -> bool {
        self.children[0].is_empty()
            && self.children[1].is_empty()
            && self.children[2].is_empty()
            && self.children[3].is_empty()
    }
    pub fn is_in(&self, point: Point) -> bool {
        point.x >= self.corner_down.x
            && point.y >= self.corner_down.y
            && point.x <= self.corner_up.x
            && point.y <= self.corner_up.y
    }
    pub fn find_nearest_neighbor_slow(&self, point: &Point) -> Option<Point> {
        let mut nearest_point: Option<Point> = None;
        let mut min_distance = self.corner_up.distance_squared(&self.corner_down);

        for child in &*self.children {
            match child {
                QuadTree::Empty => {}
                QuadTree::Point(candidate_point) => {
                    let distance = candidate_point.distance_squared(point);
                    if distance < min_distance {
                        nearest_point = Some(*candidate_point);
                        min_distance = distance;
                    }
                }
                QuadTree::Node(quad_child) => {
                    if let Some(candidate_point) = quad_child.find_nearest_neighbor_slow(point) {
                        let distance = candidate_point.distance_squared(point);
                        if distance < min_distance {
                            nearest_point = Some(candidate_point);
                            min_distance = distance;
                        }
                    }
                }
            }
        }

        nearest_point
    }

    pub fn find_nearest_neighbor(&self, point: &Point, mut min_distance: usize) -> Option<Point> {
        let mut nearest_point: Option<Point> = None;
        let mut as_visited_cadrant_i = 15; // NOTE: Bigger than 4

        // If the point we are looking for is in this sub-region
        if self.is_in(*point) {
            // Visit first the sub-sub-region containing the point
            let index_cadrant = self.i_cadrant(*point);
            as_visited_cadrant_i = index_cadrant;
            match &self.children[index_cadrant] {
                QuadTree::Empty => {}
                QuadTree::Point(candidate_point) => {
                    // We found a point that is not very far away
                    let distance = candidate_point.distance_squared(point);
                    if distance < min_distance {
                        nearest_point = Some(*candidate_point);
                        min_distance = distance;
                    }
                }
                QuadTree::Node(quad_child) => {
                    // This sub-region shouldn't be empty as we delete empty sub-region, so we found
                    // a point that is not very far away
                    if let Some(candidate_point) =
                        quad_child.find_nearest_neighbor(point, min_distance)
                    {
                        let distance = candidate_point.distance_squared(point);
                        if distance < min_distance {
                            nearest_point = Some(candidate_point);
                            min_distance = distance;
                        }
                    }
                    // NOTE: Can add a "else panic!"
                }
            }
        }

        // Visit the others sub-region if the point can be inside
        for child_i in 0..4 {
            // NOTE: We don't visit the previous sub-region!
            if child_i == as_visited_cadrant_i {
                continue;
            }

            let child = &self.children[child_i];
            match child {
                QuadTree::Empty => {}
                QuadTree::Point(candidate_point) => {
                    // If it's a point, maybe it's closer!
                    let distance = candidate_point.distance_squared(point);
                    if distance < min_distance {
                        nearest_point = Some(*candidate_point);
                        min_distance = distance;
                    }
                }
                QuadTree::Node(quad_child) => {
                    // NOTE: We first check that a corner point is closer
                    // BUG: That doesn't work. You have to check for the closer BORDER point
                    if quad_child.can_have_closer_corner(point, min_distance) {
                        if let Some(candidate_point) =
                            quad_child.find_nearest_neighbor(point, min_distance)
                        {
                            let distance = candidate_point.distance_squared(point);
                            if distance < min_distance {
                                nearest_point = Some(candidate_point);
                                min_distance = distance;
                            }
                        }
                    }
                }
            }
        }

        nearest_point
    }
    pub fn corners(&self) -> [Point; 4] {
        [
            self.corner_down,
            Point {
                x: self.corner_up.x,
                y: self.corner_down.y,
            },
            Point {
                x: self.corner_down.x,
                y: self.corner_up.y,
            },
            self.corner_up,
        ]
    }
    /// Check if any corners is closer than min_distance
    pub fn can_have_closer_corner(&self, point: &Point, min_distance: usize) -> bool {
        for corner in self.corners() {
            if corner.distance_squared(point) < min_distance {
                return true;
            }
        }

        false
    }
}