use std::collections::VecDeque;

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

use crate::graph::Graph;

use super::{simplices::CausalTriangle as Triangle, triangulation2d::Triangulation2D};

#[derive(Debug, Clone, PartialEq, Eq, Hash, Default, Serialize, Deserialize)]
pub struct CausalTriangulation2D {
    pub ntime: u16,
    pub triangles: Vec<Triangle>,
    pub vertex_times: Vec<u16>,
}

impl CausalTriangulation2D {
    pub fn to_triangulation2d(&self) -> Triangulation2D {
        Triangulation2D {
            nvertices: self.num_vertices(),
            triangles: self.triangles.iter().map(From::from).collect(),
        }
    }

    pub fn into_triangulation2d(self) -> Triangulation2D {
        Triangulation2D {
            nvertices: self.num_vertices(),
            triangles: self.triangles.into_iter().map(From::from).collect(),
        }
    }
}

impl CausalTriangulation2D {
    /// Returns the number of vertices in the triangulation
    pub fn num_vertices(&self) -> usize {
        self.vertex_times.len()
    }

    /// Returns the number of triangles in the triangulation
    pub fn num_triangles(&self) -> usize {
        self.triangles.len()
    }

    /// Returns the number of edges in the triangulation
    ///
    /// Note this is just given by `3/2*num_triangles` as every edge connects only two triangle sides.
    /// This means this does assume the triangulation is proper, in the sense that only two triangles
    /// are connected to an edge.
    pub fn num_edges(&self) -> usize {
        self.triangles.len() * 3 / 2
    }
}

impl CausalTriangulation2D {
    /// 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()),
        )
    }
}

impl CausalTriangulation2D {
    pub fn timeslice_volume_profile(&self) -> Vec<usize> {
        let mut profile = vec![0; self.ntime as usize];
        for triangle in &self.triangles {
            profile[triangle.t as usize] += 1;
        }
        profile
    }
}

impl CausalTriangulation2D {
    /// Returns whether the triangulation obeys the absolute ordering of triangle neighbours
    /// such that the first (index 0) neighbour is the time-like neighbour.
    ///
    /// See also notes on fields of [`CausalTriangle`](super::simplices::CausalTriangle).
    pub fn check_neighbour_ordering(&self) -> bool {
        for triangle in &self.triangles {
            let t_self = triangle.t;
            let t_nbr = self.triangles[triangle.neighbours[0]].t;

            use super::simplices::CausalSimplex2Kind as TriangleType;
            match triangle.kind {
                TriangleType::S21 => {
                    if (t_nbr + 1) % self.ntime != t_self {
                        return false;
                    }
                }
                TriangleType::S12 => {
                    if t_nbr != (t_self + 1) % self.ntime {
                        return false;
                    }
                }
            }
        }
        true
    }

    pub fn check_biconnectivity(&self) -> bool {
        for (label, triangle) in self.triangles.iter().enumerate() {
            for nbr_label in triangle.neighbours {
                let nbr_triangle = &self.triangles[nbr_label];
                if !nbr_triangle.neighbours.iter().any(|&x| x == label) {
                    debug!(
                        "Neighbour {nbr_label} of {label}({:?}) does not have it as neighbour",
                        nbr_triangle.neighbours
                    );
                    return false;
                }
            }
        }
        true
    }

    /// 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 (label, triangle) in self.triangles.iter().enumerate() {
            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 == label)
                    .peekable();
                if back_indices.peek().is_none() {
                    debug!("Triangulation is not properly biconnective");
                    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 {
                    debug!("Triangulation does not have correctly ordered vertices");
                    return false;
                }
            }
        }

        true
    }
}

impl CausalTriangulation2D {
    pub fn get_future_neighbour(&self, label: usize) -> Option<usize> {
        let triangle = &self.triangles[label];
        match triangle.kind {
            super::simplices::CausalSimplex2Kind::S21 => None,
            super::simplices::CausalSimplex2Kind::S12 => Some(triangle.neighbours[0]),
        }
    }

    pub fn get_past_neighbour(&self, label: usize) -> Option<usize> {
        let triangle = &self.triangles[label];
        match triangle.kind {
            super::simplices::CausalSimplex2Kind::S21 => Some(triangle.neighbours[0]),
            super::simplices::CausalSimplex2Kind::S12 => None,
        }
    }

    pub fn get_timelike_neighbour(&self, label: usize) -> usize {
        self.triangles[label].neighbours[0]
    }

    pub fn get_left_neighbour(&self, label: usize) -> usize {
        let triangle = &self.triangles[label];
        match triangle.kind {
            super::simplices::CausalSimplex2Kind::S21 => triangle.neighbours[2],
            super::simplices::CausalSimplex2Kind::S12 => triangle.neighbours[1],
        }
    }

    pub fn get_right_neighbour(&self, label: usize) -> usize {
        let triangle = &self.triangles[label];
        match triangle.kind {
            super::simplices::CausalSimplex2Kind::S21 => triangle.neighbours[1],
            super::simplices::CausalSimplex2Kind::S12 => triangle.neighbours[2],
        }
    }

    pub fn get_spacelike_neighbours(&self, label: usize) -> &[usize] {
        &self.triangles[label].neighbours[1..]
    }
}

impl CausalTriangulation2D {
    /// Walk along triangles until the original triangle is reached
    ///
    /// Restrict to stay between the origin timeslice and `ntime` further timeslices, find
    /// the shortest loop under this restriction.
    ///
    /// Note: the returned path is in the past direction, ending not stating with the `origin`
    pub fn identify_timelike_loop(&self, origin: usize) -> Vec<usize> {
        let origin_triangle = &self.triangles[origin];
        // Make sure the starting triangle is of 21-type, get neighbour if not.
        let (origin, origin_triangle) = match origin_triangle.kind {
            super::simplices::CausalSimplex2Kind::S21 => (origin, origin_triangle),
            super::simplices::CausalSimplex2Kind::S12 => {
                let upper = origin_triangle.neighbours[0];
                (upper, &self.triangles[upper])
            }
        };
        let t_origin = origin_triangle.t;

        let mut visited = vec![None; self.triangles.len()];
        visited[origin] = Some(usize::MAX);

        let mut queue = VecDeque::with_capacity(2 * self.triangles.len() / (self.ntime as usize));
        queue.push_back(origin);

        'outer: loop {
            let label = queue
                .pop_front()
                .expect("Loop should always be found in proper CDT");
            if let Some(nbr) = self.get_future_neighbour(label) {
                if nbr == origin {
                    // Went back to original triangle
                    visited[nbr] = Some(label);
                    break 'outer;
                }

                if self.triangles[nbr].t != t_origin && visited[nbr].is_none() {
                    visited[nbr] = Some(label);
                    {
                        queue.push_back(nbr);
                    }
                }
            }
            for &nbr in self.get_spacelike_neighbours(label) {
                // Only consider unvisited nodes
                if visited[nbr].is_some() {
                    continue;
                }
                visited[nbr] = Some(label);
                queue.push_back(nbr);
            }
        }

        // Rewalk path
        let mut path = Vec::with_capacity((self.ntime * 2).into());
        let mut current_triangle = origin;
        loop {
            current_triangle = visited[current_triangle]
                .expect("The path should have been fully explored by construction");
            path.push(current_triangle);
            if current_triangle == origin {
                break;
            }
        }

        path
    }
}
