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

use crate::graph::Graph;

use super::{
    causal_triangulation2d::CausalTriangulation2D, simplices::Triangle,
    triangulation_halfedge::TriangulationHalfEdge,
};

///
///
/// Note the `vertices` labels in the `triangles` must be dense. In the sense that they are
/// labelled with the integers `0..num_vertices`.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Triangulation2D {
    pub nvertices: usize,
    pub triangles: Vec<Triangle>,
}

impl Default for Triangulation2D {
    fn default() -> Self {
        Self::empty()
    }
}

impl Triangulation2D {
    pub fn empty() -> Self {
        Triangulation2D {
            nvertices: 0,
            triangles: Vec::new(),
        }
    }
}

impl Triangulation2D {
    pub fn num_vertices(&self) -> usize {
        self.nvertices
    }
}

impl From<CausalTriangulation2D> for Triangulation2D {
    fn from(value: CausalTriangulation2D) -> Self {
        value.into_triangulation2d()
    }
}

impl From<&CausalTriangulation2D> for Triangulation2D {
    fn from(value: &CausalTriangulation2D) -> Self {
        value.to_triangulation2d()
    }
}

impl Triangulation2D {
    /// Returns dual graph of the [`Triangulation`]
    pub fn dual_graph(&self) -> Graph {
        Graph::new_from_iter(
            self.triangles
                .iter()
                .map(|triangle| triangle.neighbours.iter().copied()),
        )
    }

    /// Returns vertex graph of the [`Triangulation`]
    ///
    /// Note that this graph is not neccesarily 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()),
        )
    }

    /// Returns oriented vertex graph of the [`Triangulation`]
    ///
    /// Note that this graph is oriented, e.g. the ordering of the neighbours are in
    /// counter-clockwise (positive) order on the embedding surface.
    pub fn vertex_graph_oriented(&self) -> Graph {
        let edgemap = TriangulationHalfEdge::from_triangulation(self);

        let mut visited_halfedges = vec![false; edgemap.len()];
        let mut vertex_neighbours = vec![Vec::new(); self.num_vertices()];
        for i in 0..edgemap.len() {
            if visited_halfedges[i] {
                continue;
            }
            // Vertex label at the start of the half-edge (opposite next half-edge)
            let v0 = self.triangles[i / 3].vertices[(i + 1) % 3];

            let mut marker = i;
            loop {
                // Vertex label at the end of the half-edge (opposite prev half-edge)
                let v1 = self.triangles[marker / 3].vertices[(marker + 2) % 3];
                vertex_neighbours[v0].push(v1);

                visited_halfedges[marker] = true;

                // Walk to next outgoing edge (counter-clockwise, thus prev then adjacent)
                marker = edgemap.adjacent(3 * (marker / 3) + (marker + 2) % 3);
                if marker == i {
                    break;
                }
            }
        }

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

impl Triangulation2D {
    /// 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 {
            for (i, &nbr) in triangle.neighbours.iter().enumerate() {
                let nbr_triangle = &self.triangles[nbr];
                let mut back_indices = nbr_triangle
                    .neighbours
                    .iter()
                    .positions(|&x| x == nbr)
                    .peekable();
                if back_indices.peek().is_none() {
                    return false;
                }
                let mut correct = false;
                for inbr in back_indices {
                    if triangle.vertices[(i + 1) % 3] == nbr_triangle.vertices[(inbr + 2) % 3]
                        && triangle.vertices[(i + 2) % 3] == nbr_triangle.vertices[(inbr + 1) % 3]
                    {
                        correct = true;
                        break;
                    }
                }
                if !correct {
                    return false;
                }
            }
        }

        true
    }
}

// fn check_cyclic_equality<T: Eq, const N: usize>(lhs: &[T; N], rhs: &[T; N]) -> bool {
//     let mut equal = true;
//     for shift in 0..lhs.len() {
//         equal = true;
//         for i in 0..lhs.len() {
//             if lhs[(i + shift) % lhs.len()] != rhs[i] {
//                 equal = false;
//                 break;
//             }
//         }
//     }
//     equal
// }

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_vertex_graph() {
        let triangulation = Triangulation2D {
            triangles: vec![
                Triangle {
                    neighbours: [0, 0, 1],
                    vertices: [0, 0, 1],
                },
                Triangle {
                    neighbours: [0, 1, 1],
                    vertices: [2, 0, 0],
                },
            ],
            nvertices: 3,
        };

        assert_eq!(
            triangulation.vertex_graph(),
            Graph::new_from_iter(
                [vec![0, 1, 0, 2], vec![0], vec![0]]
                    .into_iter()
                    .map(|v| v.into_iter())
            )
        );
    }

    #[test]
    fn test_vertex_graph_noduplicates() {
        let triangulation = Triangulation2D {
            triangles: vec![
                Triangle {
                    neighbours: [0, 0, 1],
                    vertices: [0, 0, 1],
                },
                Triangle {
                    neighbours: [0, 1, 1],
                    vertices: [2, 0, 0],
                },
            ],
            nvertices: 3,
        };

        assert_eq!(
            triangulation.vertex_graph_noduplicates(),
            Graph::new_from_iter(
                [vec![0, 1, 2], vec![0], vec![0]]
                    .into_iter()
                    .map(|v| v.into_iter())
            )
        );
    }

    #[test]
    fn test_vertex_graph_oriented() {
        let triangulation = Triangulation2D {
            triangles: vec![
                Triangle {
                    neighbours: [0, 0, 1],
                    vertices: [0, 0, 1],
                },
                Triangle {
                    neighbours: [0, 1, 1],
                    vertices: [2, 0, 0],
                },
            ],
            nvertices: 3,
        };

        assert_eq!(
            triangulation.vertex_graph_oriented(),
            Graph::new_from_iter(
                [vec![1, 0, 2, 0], vec![0], vec![0]]
                    .into_iter()
                    .map(|v| v.into_iter())
            )
        );
    }
}
