use itertools::Itertools;
use log::debug;
use serde::{Deserialize, Serialize};

use crate::graph::Graph;

use super::simplices::Triangle;

/// Triangulation structure designed to store a "gluing" of triangles.
///
/// This can store any orientable triangulation where every edge is between exactly two triangles.
/// Internally three half-edges of each triangle are stored with a pointer to the half-edge
/// they are adjacent to. Additionally this stores the vertex labels of the three vertices of
/// each triangle opposite the half-edges.
#[derive(Debug, Default, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Triangulation2D {
    /// Number of vertices in the triangulation
    pub num_vertices: usize,
    /// List holding triangles of the triangulation.
    ///
    /// Note that the `neighbours` field of each triangle is used to store the indices of
    /// the half-edge each half-edge is adjacent to. This encodes both the label of the
    /// neighbouring triangle and the back index (the index in the `neighbour` list back).
    ///
    /// The encoding works as follows, given the "half-edge" label `i`:
    /// - `triangle_label = i / 3`
    /// - `edge_index = i % 3`
    pub triangles: Vec<Triangle>,
}

impl Triangulation2D {
    /// Creates and empty triangulation
    pub fn empty() -> Self {
        Self::default()
    }
}

impl Triangulation2D {
    /// Returns the number of vertices in the triangulation
    #[inline]
    pub fn num_vertices(&self) -> usize {
        self.num_vertices
    }

    /// Returns the number of triangles in the triangulation
    #[inline]
    pub fn num_triangles(&self) -> usize {
        // Division must be exact for a valid triangulation
        self.triangles.len()
    }

    /// Returns the number of edges in the triangulation
    ///
    /// Note: this is simply `num_triangles * 3 / 2`
    #[inline]
    pub fn num_edges(&self) -> usize {
        // Division must be exact for a valid triangulation
        self.triangles.len() * 3 / 2
    }

    /// Returns the number of half edges of the triangulation
    ///
    /// Note: this is simply `num_triangles * 3`
    #[inline]
    pub fn num_halfedges(&self) -> usize {
        self.triangles.len() * 3
    }
}

/// Methods and associated functions to access and work with half-edges
impl Triangulation2D {
    /// Returns the label of the adjacent `halfedge`
    #[inline]
    pub fn adjacent_halfedge(&self, halfedge: usize) -> usize {
        self.triangles[halfedge / 3].neighbours[halfedge % 3]
    }

    /// Returns the label of the triangle the `halfedge` is part of.
    ///
    /// Note: this is simply `halfedge / 3`
    #[inline]
    pub fn triangle_label(halfedge: usize) -> usize {
        halfedge / 3
    }

    /// Returns the index of the halfedge in the corresponding triangulation.
    ///
    /// This is simply `halfedge % 3` and means the index of neighbouring triangle
    /// in the `neighbours` list of [`Triangle`] corresponding to the half-edge.
    #[inline]
    pub fn halfedge_index(halfedge: usize) -> usize {
        halfedge % 3
    }

    /// Returns the label of the next `halfedge`.
    ///
    /// This is simply `3 * (halfedge / 3) + (halfedge + 1) % 3`
    #[inline]
    pub fn next_halfedge(halfedge: usize) -> usize {
        3 * (halfedge / 3) + (halfedge + 1) % 3
    }

    /// Returns the label of the previous `halfedge`.
    ///
    /// This is simply `3 * (halfedge / 3) + (halfedge + 2) % 3`
    #[inline]
    pub fn prev_halfedge(halfedge: usize) -> usize {
        3 * (halfedge / 3) + (halfedge + 2) % 3
    }

    /// Returns the label of the halfedge given by a `triangle_label` and `halfedge_index`
    ///
    /// Note that `halfedge_index` must be 0, 1, or 2. If another index is used, this function
    /// will give a result, but it does not correspond to a half-edge of the given triangle.
    /// Note this function is simply `3 * triangle_label + halfedge_index`
    #[inline]
    pub fn halfedge_label(triangle_label: usize, halfedge_index: usize) -> usize {
        3 * triangle_label + halfedge_index
    }
}

impl Triangulation2D {
    /// Returns a reference to the triangle list of the [`Triangulation2D`]
    #[inline]
    pub fn get_triangles(&self) -> &[Triangle] {
        &self.triangles
    }

    /// Returns a reference to the triangle given by `label`
    ///
    /// Note that the `neighbours` field hold the labels of the adjacent half-edges, encoding
    /// the triangle label as `i / 3` and the back-index as `i % 3`. Also see [`Triangulation2D`].
    ///
    /// # Panic
    /// This method will panic if `label >= self.num_triangles()`
    #[inline]
    pub fn get_triangle(&self, label: usize) -> &Triangle {
        &self.triangles[label]
    }

    /// Returns a mutable reference to the triangle given by `label`
    ///
    /// See [`Triangulation2D::get_triangle()`] for more details.
    ///
    /// # Panic
    /// This method will panic if `label >= self.num_triangles()`
    #[inline]
    pub fn get_mut_triangle(&mut self, label: usize) -> &mut Triangle {
        &mut self.triangles[label]
    }

    /// Returns the label of the triangle neighbouring `label` on the `index` side.
    ///
    /// # Panic
    /// This method will panic if `label >= self.num_triangles()` or `index >= 3`
    #[inline]
    pub fn get_neighbour(&self, label: usize, index: usize) -> usize {
        self.get_triangle(label).get_neighbour(index)
    }

    /// Returns the label and backindex of triangle neighbouring `label` on the `index` side.
    ///
    /// # Panic
    /// This method will panic if `label >= self.num_triangles()` or `index >= 3`
    #[inline]
    pub fn get_neighbour_backindex(&self, label: usize, index: usize) -> (usize, usize) {
        self.get_triangle(label).get_neighbour_backindex(index)
    }

    /// Returns the neighbouring triangle labels of the triangle given by `label`
    ///
    /// # Panic
    /// This method will panic if `label >= self.num_triangles()`
    #[inline]
    pub fn get_neighbours(&self, label: usize) -> [usize; 3] {
        self.get_triangle(label).get_neighbours()
    }

    #[inline]
    pub fn get_neighbours_backindices(&self, label: usize) -> [(usize, usize); 3] {
        self.get_triangle(label).get_neighbours_backindices()
    }

    /// Returns the vertices of the triangle by `label`
    ///
    /// # Panic
    /// This method will panic if `label >= self.num_triangles()`
    #[inline]
    pub fn get_triangle_vertices(&self, label: usize) -> [usize; 3] {
        self.get_triangle(label).vertices
    }
}

impl Triangulation2D {
    /// Returns oriented dual graph of the [`Triangulation`]
    ///
    /// Note that this graph is oriented in the sense that the links are given in counter-clockwise
    /// (positive) order.
    pub fn dual_graph(&self) -> Graph {
        Graph::new_from_iter(
            self.triangles
                .iter()
                .map(|triangle| triangle.neighbours.iter().map(|&nbr_edge| nbr_edge / 3)),
        )
    }

    /// Returns vertex graph of the [`Triangulation`]
    ///
    /// Note that this graph is not necessarily oriented, i.e. the ordering of the neighbours
    /// of each node is arbitrary.
    pub fn vertex_graph(&self) -> Graph {
        let mut vertex_neighbours = vec![Vec::new(); self.num_vertices()];
        for triangle in self.triangles.iter() {
            let [v0, v1, v2] = triangle.vertices;

            vertex_neighbours[v0].push(v1);
            vertex_neighbours[v1].push(v2);
            vertex_neighbours[v2].push(v0);
        }

        Graph::new_from_iter(vertex_neighbours.into_iter().map(|nbrs| nbrs.into_iter()))
    }

    /// Returns vertex graph of the [`Triangulation`] explicity making all edges single edges
    pub fn vertex_graph_noduplicates(&self) -> Graph {
        let mut vertex_neighbours = vec![Vec::new(); self.num_vertices()];
        for triangle in self.triangles.iter() {
            let [v0, v1, v2] = triangle.vertices;

            vertex_neighbours[v0].push(v1);
            vertex_neighbours[v1].push(v2);
            vertex_neighbours[v2].push(v0);
        }

        Graph::new_from_iter(
            vertex_neighbours
                .into_iter()
                .map(|nbrs| nbrs.into_iter().unique()),
        )
    }
}

/// Checks to check the validity of the [`Triangulation2D`] structure
// TODO: Return not `bool`, but `Result<(), SomeProperError>`
impl Triangulation2D {
    /// Check if the [`Triangulation2D`] is properly biconnective, i.e. that each triangle
    /// neighbour points back the the triangle at the correct index.
    pub fn check_biconnectivity(&self) -> bool {
        for (label, triangle) in self.triangles.iter().enumerate() {
            for (nbr_label, backindex) in triangle.get_neighbours_backindices() {
                if self.get_neighbour(nbr_label, backindex) != label {
                    debug!("Neighbour {nbr_label} is not correctly connected back to {label}.");
                    return false;
                }
            }
        }
        true
    }

    /// Count the number of vertices by looking at all the vertex labels on each triangle.
    ///
    /// Note: if the [`Triangulation2D`] is a correct structure, this should be equal to
    /// `self.num_vertices()` which is just a direct lookup. Whereas this method can be slow.
    pub fn count_vertices(&self) -> usize {
        self.triangles
            .iter()
            .flat_map(|triangle| triangle.vertices.into_iter())
            .unique()
            .count()
    }

    /// Checks if `num_vertices` is set correctly based on the vertices of each triangle
    pub fn check_num_vertices(&self) -> bool {
        self.count_vertices() == self.num_vertices()
    }

    /// Checks whether the two vertices between each triangle are also correctly ordered vertices
    /// of the corresponding neighbouring triangle.
    pub fn check_vertex_consistency(&self) -> bool {
        for triangle in self.triangles.iter() {
            for (index, (nbr_label, backindex)) in triangle
                .get_neighbours_backindices()
                .into_iter()
                .enumerate()
            {
                let vertices = triangle.vertices;
                let nbr_vertices = self.get_triangle_vertices(nbr_label);

                if vertices[(index + 1) % 3] != nbr_vertices[(backindex + 2) % 3] {
                    debug!("Triangulation does not have correctly ordered vertices");
                    return false;
                }

                if vertices[(index + 2) % 3] != nbr_vertices[(backindex + 1) % 3] {
                    debug!("Triangulation does not have correctly ordered vertices");
                    return false;
                }
            }
        }

        true
    }
}
