use std::fmt::Display;

use dyntri_core::graph::graph::{Graph, Node};
use slab::Slab;

use super::{HalfEdge, PlanarMap};

#[derive(Debug, Clone, Default)]
/// A planar map in half-edge permutation encoding which cannot grow
pub struct FixedPlanarMap {
    edges: Box<[HalfEdge]>,
}

impl FixedPlanarMap {
    pub fn from_planar_map(map: &PlanarMap) -> Self {
        let mut index_map = vec![usize::MAX; map.edges.capacity()];
        for (new_index, (label, _)) in map.edges.iter().enumerate() {
            index_map[label] = new_index;
        }
        let mut edges = Vec::with_capacity(map.edges.len());
        for (_, edge) in map.edges.iter() {
            edges.push(HalfEdge {
                next: index_map[edge.next],
                previous: index_map[edge.previous],
                adjacent: index_map[edge.adjacent],
            });
        }

        Self {
            edges: edges.into_boxed_slice(),
        }
    }

    pub fn to_planar_map(&self) -> PlanarMap {
        let mut edges = Slab::with_capacity(self.len());
        for (index, edge) in self.edges.iter().copied().enumerate() {
            assert_eq!(
                index,
                edges.insert(edge),
                "By contruction of the Slab dataset the returned label should be the index"
            )
        }
        PlanarMap { edges }
    }
}

impl From<PlanarMap> for FixedPlanarMap {
    fn from(value: PlanarMap) -> Self {
        Self::from_planar_map(&value)
    }
}

impl From<&PlanarMap> for FixedPlanarMap {
    fn from(value: &PlanarMap) -> Self {
        Self::from_planar_map(value)
    }
}

impl From<&FixedPlanarMap> for PlanarMap {
    fn from(value: &FixedPlanarMap) -> Self {
        value.to_planar_map()
    }
}

impl From<FixedPlanarMap> for PlanarMap {
    fn from(value: FixedPlanarMap) -> Self {
        value.to_planar_map()
    }
}

impl FixedPlanarMap {
    #[inline]
    /// Returns the number of half-edges in the planar map
    pub fn len(&self) -> usize {
        self.edges.len()
    }

    #[must_use]
    #[inline]
    /// Returns if the map has no edges
    pub fn is_empty(&self) -> bool {
        self.edges.is_empty()
    }

    #[inline]
    /// Returns the label of the next half-edge in the planar map
    pub fn get_next(&self, label: usize) -> usize {
        self.edges[label].next
    }

    #[inline]
    pub fn get_previous(&self, label: usize) -> usize {
        self.edges[label].previous
    }

    #[inline]
    /// Returns the label of the previous half-edge in the planar map
    pub fn get_adjacent(&self, label: usize) -> usize {
        self.edges[label].adjacent
    }
}

impl Display for FixedPlanarMap {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "(")?;
        let mut edges_iter = self.edges.iter();
        if let Some(edge) = edges_iter.next() {
            write!(f, "0: {} {} {}", edge.next, edge.previous, edge.adjacent)?;
        }
        for (i, edge) in edges_iter.enumerate() {
            write!(
                f,
                ", {}: {} {} {}",
                i + 1,
                edge.next,
                edge.previous,
                edge.adjacent
            )?;
        }
        write!(f, ")")?;
        Ok(())
    }
}

impl FixedPlanarMap {
    /// Construct the dual graph of the [FixedPlanarMap]
    ///
    /// This means the graph where the nodes represent the faces and the links the edges
    /// connecting the faces
    pub fn construct_dual_graph(&self) -> Graph {
        let (faces, edge_face_labels) = identify_faces(self);
        let nodes = faces
            .into_iter()
            .map(|quad| {
                let neighbours = quad
                    .into_iter()
                    .map(|edge_label| {
                        let adjacent = self.get_adjacent(edge_label);
                        edge_face_labels[adjacent]
                    })
                    .collect();
                Node::new(neighbours)
            })
            .collect();

        Graph::new(nodes)
    }

    /// Construct the vertex graph of the [FixedPlanarMap]
    ///
    /// This means the graph where the nodes represent the vertices and the links the edges
    /// connecting the vertices.
    pub fn construct_vertex_graph(&self) -> Graph {
        let (vertices, edge_vertex_labels) = identify_vertices(self);
        let nodes = vertices
            .into_iter()
            .map(|vertex| {
                let neighbours = vertex
                    .into_iter()
                    .map(|edge_label| {
                        let adjacent = self.get_adjacent(edge_label);
                        edge_vertex_labels[adjacent]
                    })
                    .collect();
                Node::new(neighbours)
            })
            .collect();

        Graph::new(nodes)
    }
}

/// Return the edge labels in the faces and the face labels the edges belong to
fn identify_faces(map: &FixedPlanarMap) -> (Vec<Vec<usize>>, Vec<usize>) {
    let face_len = map.len() / 3; // By Euler characteristic for a triangulation

    let mut faces = Vec::with_capacity(face_len);
    // Keep track of edges that are visited and store which quad they belong to
    let mut visited_edges = vec![None; map.len()];

    for start_edge in 0..map.len() {
        // Skip if edge is already visited -> loop already identified
        if visited_edges[start_edge].is_some() {
            continue;
        }
        let face = identify_face(map, start_edge, faces.len(), &mut visited_edges);
        faces.push(face);
    }

    let visited_edges = visited_edges
        .into_iter()
        .collect::<Option<_>>()
        .unwrap_or_else(|| panic!("All edges should have been explored"));

    (faces, visited_edges)
}

fn identify_face(
    map: &FixedPlanarMap,
    start_edge: usize,
    face_label: usize,
    visited_edges: &mut [Option<usize>],
) -> Vec<usize> {
    let mut face = Vec::with_capacity(3);
    let mut current_edge = start_edge;
    loop {
        assert!(
            visited_edges[current_edge].is_none(),
            "Edges should not appear in more than one loop"
        );
        visited_edges[current_edge] = Some(face_label);
        face.push(current_edge);

        current_edge = map.get_next(current_edge);

        if current_edge == start_edge {
            break;
        }
    }
    face
}

/// Return the edge labels going away from each vertex and the vertex labels each edge belongs to
fn identify_vertices(map: &FixedPlanarMap) -> (Vec<Vec<usize>>, Vec<usize>) {
    let vertex_len = map.len() / 3 + 2; // By Euler characteristic assuming a triangulation

    let mut vertices = Vec::with_capacity(vertex_len);
    // Keep track of edges that are visited and store which vertex they belong to
    let mut visited_edges = vec![None; map.len()];

    for start_edge in 0..map.len() {
        // Skip if edge is already visited -> loop already identified
        if visited_edges[start_edge].is_some() {
            continue;
        }
        let vertex = identify_vertex(map, start_edge, vertices.len(), &mut visited_edges);
        vertices.push(vertex);
    }

    let visited_edges = visited_edges
        .into_iter()
        .collect::<Option<_>>()
        .unwrap_or_else(|| panic!("All edges should have been explored"));

    (vertices, visited_edges)
}

fn identify_vertex(
    map: &FixedPlanarMap,
    start_edge: usize,
    vertex_label: usize,
    visited_edges: &mut [Option<usize>],
) -> Vec<usize> {
    let mut vertex = Vec::with_capacity(6); // Capacity should be reasonably good for a triangulation
    let mut current_edge = start_edge;
    loop {
        assert!(
            visited_edges[current_edge].is_none(),
            "Edges should not appear in more than one loop"
        );
        visited_edges[current_edge] = Some(vertex_label);
        vertex.push(current_edge);

        let adjacent = map.get_adjacent(current_edge);
        current_edge = map.get_next(adjacent);

        if current_edge == start_edge {
            break;
        }
    }
    vertex
}
