use super::{fixed_triangulation::FixedTriangulation, triangle::Orientation};
use dyntri_core::triangulation::{
    CausalTriangulation2D,
    simplices::{CausalSimplex2Kind, CausalTriangle},
};

pub fn reconstruct_causal_triangulation2d(
    triangulation: &FixedTriangulation,
) -> CausalTriangulation2D {
    let triangles = &triangulation.triangles;

    // Find a up triangle to start with
    let mut starting_triangle_marker = 0;
    // Walk right until we find an up-triangle
    for _ in 0..triangles.len() {
        let current_triangle = triangles[starting_triangle_marker];
        if matches!(current_triangle.orientation, Orientation::Up) {
            break;
        }
        starting_triangle_marker = current_triangle.right;
    }

    // Map arbitrary associated triangle labels to dense vertex labels
    let mut vertex_labels = SparseToDenseMap::new(triangles.len() + 1);

    let mut vertex_times = vec![None; triangles.len() / 2];
    let mut new_triangles: Vec<Option<CausalTriangle>> = vec![None; triangulation.triangles.len()];
    for t in 0..(triangulation.ntime) {
        let prev_marker = identify_triangles_timeslice(
            triangulation,
            &mut new_triangles,
            &mut vertex_times,
            &mut vertex_labels,
            t,
            starting_triangle_marker,
        );
        // `prev_marker` is always `Down` triangle, so we go up to the next time-slice
        starting_triangle_marker = triangles[prev_marker].center;
    }

    let triangles = new_triangles
        .into_iter()
        .collect::<Option<_>>()
        .expect("All triangles should have been explored");

    let vertex_times = vertex_times
        .into_iter()
        .collect::<Option<_>>()
        .expect("All vertices should have been explored");

    CausalTriangulation2D {
        ntime: triangulation.ntime,
        simplices: triangles,
        vertex_times,
    }
}

// Identify all vertices belonging to each triangle in a time-slice labelling it with time `t`.
//
// This returns the label of a `Down`-type triangle in this time-slice
// Note: `starting_triangle_marker` must point to and `Up` type triangle.
fn identify_triangles_timeslice(
    triangulation: &FixedTriangulation,
    new_triangles: &mut [Option<CausalTriangle>],
    vertex_times: &mut [Option<u16>],
    vertex_labels: &mut SparseToDenseMap,
    t: u16,
    starting_triangle_marker: usize,
) -> usize {
    let triangles = &triangulation.triangles;
    // Track current triangle label
    let mut triangle_marker = starting_triangle_marker;

    // `starting_triangle` must point up
    assert!(matches!(
        triangles[triangle_marker].orientation,
        Orientation::Up
    ));

    // Walk left until we find a triangle is opposite orientation (thus down)
    loop {
        let current_triangle = triangles[triangle_marker];
        if matches!(current_triangle.orientation, Orientation::Down) {
            break;
        }
        triangle_marker = current_triangle.left;
    }
    // Keep track of this `Down`-triangle as the `start_marker`
    let start_marker = triangle_marker;

    // Identify the upper and lower vertex labels
    let current_triangle = triangles[triangle_marker];
    let mut upper = vertex_labels.map(current_triangle.center);
    let mut lower = vertex_labels.map(current_triangle.right);

    // Walk left identifying the vertices of each triangle
    triangle_marker = current_triangle.left;
    loop {
        let current_triangle = triangles[triangle_marker];
        match current_triangle.orientation {
            Orientation::Down => {
                let new_triangle = CausalTriangle {
                    t,
                    kind: CausalSimplex2Kind::S12,
                    neighbours: [
                        triangulation.get_halfedge_center(triangle_marker),
                        triangulation.get_halfedge_left(triangle_marker),
                        triangulation.get_halfedge_right(triangle_marker),
                    ],
                    vertices: [lower, upper, vertex_labels.map(current_triangle.center)],
                };
                upper = vertex_labels.map(current_triangle.center);
                new_triangles[triangle_marker] = Some(new_triangle);
            }
            Orientation::Up => {
                // When `Up` set the `time` of the corresponding vertex to the same as the triangle
                vertex_times[vertex_labels.map(triangle_marker)] = Some(t);

                let new_triangle = CausalTriangle {
                    t,
                    kind: CausalSimplex2Kind::S21,
                    neighbours: [
                        triangulation.get_halfedge_center(triangle_marker),
                        triangulation.get_halfedge_right(triangle_marker),
                        triangulation.get_halfedge_left(triangle_marker),
                    ],
                    vertices: [upper, vertex_labels.map(triangle_marker), lower],
                };
                lower = vertex_labels.map(triangle_marker);
                new_triangles[triangle_marker] = Some(new_triangle);
            }
        }
        if triangle_marker == start_marker {
            break;
        }
        triangle_marker = current_triangle.left;
    }

    start_marker
}

impl FixedTriangulation {
    /// Returns the halfedge label for the center neighbour of `label`
    fn get_halfedge_center(&self, label: usize) -> usize {
        let nbr_label = self.triangles[label].center;
        3 * nbr_label
    }

    /// Returns the halfedge label for the center neighbour of `label`
    fn get_halfedge_left(&self, label: usize) -> usize {
        let nbr_label = self.triangles[label].left;
        // Left neighbour, so back must be right
        match self.triangles[nbr_label].orientation {
            Orientation::Down => 3 * nbr_label + 2,
            Orientation::Up => 3 * nbr_label + 1,
        }
    }

    /// Returns the halfedge label for the center neighbour of `label`
    fn get_halfedge_right(&self, label: usize) -> usize {
        let nbr_label = self.triangles[label].right;
        // Right neighbour, so back must be left
        match self.triangles[nbr_label].orientation {
            Orientation::Down => 3 * nbr_label + 1,
            Orientation::Up => 3 * nbr_label + 2,
        }
    }
}

#[derive(Debug, Clone)]
struct SparseToDenseMap {
    map: Vec<Option<usize>>,
    next_available: usize,
}

impl SparseToDenseMap {
    fn new(max_sparse_index: usize) -> Self {
        SparseToDenseMap {
            map: vec![None; max_sparse_index + 1],
            next_available: 0,
        }
    }

    fn map(&mut self, sparse_index: usize) -> usize {
        *self
            .map
            .get_mut(sparse_index)
            .expect("Given sparse_index is larger than max_sparse_index")
            .get_or_insert_with(|| {
                let dense_index = self.next_available;
                self.next_available += 1;
                dense_index
            })
    }
}

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

    #[test]
    fn test_map() {
        let mut map = SparseToDenseMap::new(5);
        assert_eq!(map.map(4), 0);
        assert_eq!(map.map(4), 0);
        assert_eq!(map.map(1), 1);
        assert_eq!(map.map(3), 2);
        assert_eq!(map.map(5), 3);
        assert_eq!(map.map(4), 0);
        assert_eq!(map.map(5), 3);
        assert_eq!(map.map(2), 4);
        assert_eq!(map.map(0), 5);
        assert_eq!(map.map(5), 3);
    }
}
