use itertools::Itertools;
use nalgebra::{
    allocator::Allocator, DefaultAllocator, DimName, DimNameDiff, DimNameSub, RealField, Vector2,
    U1,
};

use crate::{misc::FloatingPoint, prelude::NurbsSurface, surface::UVDirection};

use super::{cardinal_direction::CardinalDirection, SurfacePoint};

/// Node for adaptive tessellation of a surface
#[derive(Clone, Debug)]
pub struct AdaptiveTessellationNode<T: RealField, D: DimName>
where
    D: DimNameSub<U1>,
    DefaultAllocator: Allocator<D>,
    DefaultAllocator: Allocator<DimNameDiff<D, U1>>,
{
    /// id of the node
    id: usize,
    /// children of the node
    children: Option<[usize; 2]>,
    /// corners of the node
    /// left-bottom, right-bottom, right-top, left-top order
    pub(crate) corners: [SurfacePoint<T, DimNameDiff<D, U1>>; 4],
    /// neighbors of the node
    pub(crate) neighbors: CardinalDirection<usize>,
    /// mid points of the node
    pub(crate) mid_points: CardinalDirection<SurfacePoint<T, DimNameDiff<D, U1>>>,
    /// divided direction of the node
    pub(crate) direction: UVDirection,
    uv_center: Vector2<T>,
}

impl<T: FloatingPoint, D: DimName> AdaptiveTessellationNode<T, D>
where
    D: DimNameSub<U1>,
    DefaultAllocator: Allocator<D>,
    DefaultAllocator: Allocator<DimNameDiff<D, U1>>,
{
    pub fn new<N: Into<CardinalDirection<usize>>>(
        id: usize,
        corners: [SurfacePoint<T, DimNameDiff<D, U1>>; 4],
        neighbors: N,
    ) -> Self {
        let uv_center = (corners[0].uv + corners[2].uv) * T::from_f64(0.5).unwrap();
        Self {
            id,
            corners,
            neighbors: neighbors.into(),
            children: None,
            mid_points: CardinalDirection::default(),
            direction: UVDirection::V,
            uv_center,
        }
    }

    pub fn id(&self) -> usize {
        self.id
    }

    /// check if the node is a leaf
    pub fn is_leaf(&self) -> bool {
        self.children.is_none()
    }

    /// get the division direction of the node
    pub fn division(&self) -> UVDirection {
        self.direction
    }

    /// get the corners of the node
    /// [left-bottom, right-bottom, right-top, left-top] order
    pub fn corners(&self) -> &[SurfacePoint<T, DimNameDiff<D, U1>>; 4] {
        &self.corners
    }

    pub fn neighbors(&self) -> &CardinalDirection<usize> {
        &self.neighbors
    }

    pub fn assign_children(&mut self, children: [usize; 2]) {
        self.children = Some(children);
    }

    /// Evaluate the center of the node
    pub fn center(&self, surface: &NurbsSurface<T, D>) -> SurfacePoint<T, DimNameDiff<D, U1>> {
        evaluate_surface(surface, self.uv_center)
    }

    /// Get the uv center of the node
    pub fn uv_center(&self) -> Vector2<T> {
        self.uv_center
    }

    /// Get the corners of the edge of the node based on the divided direction
    pub fn get_edge_corners(
        &self,
        nodes: &Vec<Self>,
        edge_index: usize, // [left-bottom, right-bottom, right-top, left-top] order
    ) -> Vec<SurfacePoint<T, DimNameDiff<D, U1>>> {
        match &self.children {
            Some(children) => match self.direction {
                UVDirection::U => match edge_index {
                    0 => nodes[children[0]].get_edge_corners(nodes, 0),
                    1 => [
                        nodes[children[0]].get_edge_corners(nodes, 1),
                        nodes[children[1]].get_edge_corners(nodes, 1),
                    ]
                    .concat(),
                    2 => nodes[children[1]].get_edge_corners(nodes, 2),
                    3 => [
                        nodes[children[1]].get_edge_corners(nodes, 3),
                        nodes[children[0]].get_edge_corners(nodes, 3),
                    ]
                    .concat(),
                    _ => vec![],
                },
                UVDirection::V => match edge_index {
                    0 => [
                        nodes[children[0]].get_edge_corners(nodes, 0),
                        nodes[children[1]].get_edge_corners(nodes, 0),
                    ]
                    .concat(),
                    1 => nodes[children[1]].get_edge_corners(nodes, 1),
                    2 => [
                        nodes[children[1]].get_edge_corners(nodes, 2),
                        nodes[children[0]].get_edge_corners(nodes, 2),
                    ]
                    .concat(),
                    3 => nodes[children[0]].get_edge_corners(nodes, 3),
                    _ => vec![],
                },
            },
            None => {
                // if its a leaf, there are no children to obtain uvs from
                vec![self.corners[edge_index].clone()]
            }
        }
    }

    /// Get all corners of the node
    pub fn get_all_corners(
        &self,
        nodes: &Vec<Self>,
        edge_index: usize, // [left-bottom, right-bottom, right-top, left-top] order
    ) -> Vec<SurfacePoint<T, DimNameDiff<D, U1>>> {
        let base_arr = vec![self.corners[edge_index].clone()];

        match self.neighbors[edge_index] {
            None => base_arr,
            Some(neighbor) => {
                let orig = &self.corners;
                // get opposite edges uvs
                let opposite_index = (edge_index + 2) % 4;
                let neighbor = &nodes[neighbor];
                let corners = neighbor.get_edge_corners(nodes, opposite_index);

                // clip the range of uvs to match self one
                let idx = edge_index % 2; // left-bottom, right-top to x, right-bottom, left-top to y
                let e = T::default_epsilon();
                let lower = orig[0].uv[idx] + e;
                let upper = orig[2].uv[idx] - e;
                let corner = corners
                    .into_iter()
                    .filter(|c| lower <= c.uv[idx] && c.uv[idx] <= upper)
                    .rev()
                    .collect_vec();
                [base_arr, corner].concat()
            }
        }
    }

    /// Evaluate the mid point of the node
    pub fn evaluate_mid_point(
        &mut self,
        surface: &NurbsSurface<T, D>,
        direction: NeighborDirection,
    ) -> SurfacePoint<T, DimNameDiff<D, U1>> {
        match self.mid_points.at(direction) {
            Some(ref p) => p.clone(),
            None => {
                let uv = match direction {
                    NeighborDirection::South => {
                        Vector2::new(self.uv_center.x, self.corners[0].uv.y)
                    }
                    NeighborDirection::East => Vector2::new(self.corners[1].uv.x, self.uv_center.y),
                    NeighborDirection::North => {
                        Vector2::new(self.uv_center.x, self.corners[2].uv.y)
                    }
                    NeighborDirection::West => Vector2::new(self.corners[0].uv.x, self.uv_center.y),
                };
                let pt = evaluate_surface(surface, uv);
                let index: usize = direction.into();
                self.mid_points[index] = Some(pt.clone());
                pt
            }
        }
    }

    /// Check if the node has bad normals
    fn has_bad_normals(&self) -> bool {
        self.corners.iter().any(|c| c.is_normal_degenerated())
    }

    /// Fix the degenerated normals
    fn fix_normals(&mut self) {
        let l = self.corners.len();

        for i in 0..l {
            if self.corners[i].is_normal_degenerated() {
                // get neighbors
                let v1 = &self.corners[(i + 1) % l];
                let v2 = &self.corners[(i + 3) % l];
                // correct the normal
                self.corners[i].normal = if v1.is_normal_degenerated() {
                    v2.normal.clone()
                } else {
                    v1.normal.clone()
                };
            }
        }
    }

    /// Check if the node should be divided
    /// if the norm of the adjacent normals is greater than the normal_tolerance, the node should be divided
    /// Compute the maximum 3D edge length among the four edges of this node.
    pub fn max_edge_length(&self) -> T {
        let edges = [
            (self.corners[0].point(), self.corners[1].point()), // bottom
            (self.corners[1].point(), self.corners[2].point()), // right
            (self.corners[2].point(), self.corners[3].point()), // top
            (self.corners[3].point(), self.corners[0].point()), // left
        ];
        edges
            .iter()
            .map(|(a, b)| (*a - *b).norm())
            .fold(T::zero(), |acc, x| if x > acc { x } else { acc })
    }

    pub fn should_divide(&mut self, normal_tolerance: T) -> Option<DividableDirection> {
        if self.has_bad_normals() {
            self.fix_normals();
            //don't divide any further when encountering a degenerate normal
            return None;
        }

        let tolerance_squared = normal_tolerance * normal_tolerance;

        let v_direction = (self.corners[0].normal() - self.corners[1].normal()).norm_squared()
            > tolerance_squared
            || (self.corners[2].normal() - self.corners[3].normal()).norm_squared()
                > tolerance_squared;
        let v_direction = v_direction && self.corners.iter().all(|c| !c.is_u_constrained());

        let u_direction = (self.corners[1].normal() - self.corners[2].normal()).norm_squared()
            > tolerance_squared
            || (self.corners[3].normal() - self.corners[0].normal()).norm_squared()
                > tolerance_squared;
        let u_direction = u_direction && self.corners.iter().all(|c| !c.is_v_constrained());

        match (u_direction, v_direction) {
            (true, true) => Some(DividableDirection::Both),
            (true, false) => Some(DividableDirection::U),
            (false, true) => Some(DividableDirection::V),
            (false, false) => {
                None
                /*
                let center = self.center(surface);
                if (center.normal() - self.corners[0].normal()).norm_squared()
                    > options.norm_tolerance
                    || (center.normal() - self.corners[1].normal()).norm_squared()
                        > options.norm_tolerance
                    || (center.normal() - self.corners[2].normal()).norm_squared()
                        > options.norm_tolerance
                    || (center.normal() - self.corners[3].normal()).norm_squared()
                        > options.norm_tolerance
                {
                    Some(DividableDirection::Both)
                } else {
                    None
                }
                */
            }
        }
    }
}

/// Evaluate the surface at a given uv coordinate
fn evaluate_surface<T: FloatingPoint, D>(
    surface: &NurbsSurface<T, D>,
    uv: Vector2<T>,
) -> SurfacePoint<T, DimNameDiff<D, U1>>
where
    D: DimName + DimNameSub<U1>,
    DefaultAllocator: Allocator<D>,
    DefaultAllocator: Allocator<DimNameDiff<D, U1>>,
{
    let derivs = surface.rational_derivatives(uv.x, uv.y, 1);
    let pt = derivs[0][0].clone();
    let norm = derivs[1][0].cross(&derivs[0][1]);
    let is_normal_degenerated = norm.magnitude_squared() < T::default_epsilon();
    SurfacePoint::new(
        uv,
        pt.into(),
        if !is_normal_degenerated {
            norm.normalize()
        } else {
            norm
        },
        is_normal_degenerated,
    )
}

/// Enum to represent the direction in which a node can be divided
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum DividableDirection {
    Both,
    U,
    V,
}

/// Enum to represent the direction of a neighbor
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum NeighborDirection {
    South = 0,
    East = 1,
    North = 2,
    West = 3,
}

impl NeighborDirection {
    pub fn opposite(self) -> Self {
        match self {
            Self::South => Self::North,
            Self::East => Self::West,
            Self::North => Self::South,
            Self::West => Self::East,
        }
    }
}

impl From<NeighborDirection> for usize {
    fn from(val: NeighborDirection) -> Self {
        val as usize
    }
}
