use std::fmt::Display;

use dyntri_core::graph::graph::{Graph, Node};
use dyntri_core::triangulation::simplices::Triangle;
use dyntri_core::triangulation::triangulation2d::Triangulation2D;
use slab::Slab;

mod fixed;

pub use fixed::FixedPlanarMap;

#[derive(Debug, Clone, Copy, Default)]
struct HalfEdge {
    // Stores the index of related half-edges
    // Note: all half-edges in internal faces are in counter-clockwise direction
    // all half-edges of the outer face are in clockwise direction.
    next: usize,
    previous: usize,
    adjacent: usize,
}

#[derive(Debug, Clone)]
/// A planar map in half-edge permutation encoding
pub struct PlanarMap {
    edges: Slab<HalfEdge>,
}

impl PlanarMap {
    /// Creates a new [`PlanarMap`] starting with a single edge (two half).
    ///
    /// Returns the [`PlanarMap`] and the label of the root edge.
    pub fn new() -> (Self, usize) {
        let mut map = Self::empty();
        let root = map.new_edge();
        (map, root)
    }

    /// Creates a new [`PlanarMap`] with capacity for `capacity` number of half-edges.
    ///
    /// Returns the [`PlanarMap`] and the label of the root edge.
    pub fn with_capacity(capacity: usize) -> (Self, usize) {
        let mut map = Self::empty_with_capacity(capacity);
        let root = map.new_edge();
        (map, root)
    }

    /// Creates a empty [`PlanarMap`].
    pub fn empty() -> Self {
        Self { edges: Slab::new() }
    }

    /// Creates a empty [`PlanarMap`] with capacity for `capacity` number of half-edges.
    pub fn empty_with_capacity(capacity: usize) -> Self {
        Self {
            edges: Slab::with_capacity(capacity),
        }
    }

    /// Shrink the [`PlanarMap`] to use the minimal amount of memory.
    ///
    /// Note: this is likely not a wise thing to if new edges are added afterwards,
    /// as this means reallocation is necessary.
    pub fn compact(&mut self) {
        self.edges.compact(|_, _, _| false);
    }
}

impl PlanarMap {
    /// Creates a new full edge (two half-edges) to a planar map
    ///
    /// Note: This double edge is not connected to any previously existing edges of the planar map,
    /// so it should only be used for an empty planar map, to give a valid planar map.
    /// Returns the label of the first half-edge for convenience.
    fn new_edge(&mut self) -> usize {
        // TODO: First default and then edit value is not fully optimal
        let label1 = self.edges.insert(HalfEdge::default());
        let label2 = self.edges.insert(HalfEdge::default());

        let edge1 = &mut self.edges[label1];
        edge1.next = label2;
        edge1.previous = label2;
        edge1.adjacent = label2;

        let edge2 = &mut self.edges[label2];
        edge2.next = label1;
        edge2.previous = label1;
        edge2.adjacent = label1;

        label1
    }

    /// Adds a new full edge (two half-edges) to a planar map at the vertex before the
    /// half-edge given by `label`
    ///
    /// Returns the label of the first added half-edge for convenience.
    pub fn add_edge(&mut self, label: usize) -> usize {
        // TODO: First default and then edit value is not fully optimal
        let label1 = self.edges.insert(HalfEdge::default());
        let label2 = self.edges.insert(HalfEdge::default());

        let label_prev = self.edges[label].previous;
        self.edges[label].previous = label2;
        self.edges[label_prev].next = label1;

        let edge1 = &mut self.edges[label1];
        edge1.next = label2;
        edge1.previous = label_prev;
        edge1.adjacent = label2;

        let edge2 = &mut self.edges[label2];
        edge2.next = label;
        edge2.previous = label1;
        edge2.adjacent = label1;

        label1
    }

    /// Adds a new full edge (two half-edges) to a planar map between the vertices before the
    /// half-edges given by `start` and `end`
    ///
    /// Returns the label of the first added half-edge for convenience.
    pub fn add_edge_between(&mut self, start: usize, end: usize) -> usize {
        if start == end {
            return self.add_loop(start);
        }

        // TODO: First default and then edit value is not fully optimal
        let label1 = self.edges.insert(HalfEdge::default());
        let label2 = self.edges.insert(HalfEdge::default());

        let start_prev = self.edges[start].previous;
        self.edges[start].previous = label2;
        self.edges[start_prev].next = label1;

        let end_prev = self.edges[end].previous;
        self.edges[end].previous = label1;
        self.edges[end_prev].next = label2;

        let edge1 = &mut self.edges[label1];
        edge1.next = end;
        edge1.previous = start_prev;
        edge1.adjacent = label2;

        let edge2 = &mut self.edges[label2];
        edge2.next = start;
        edge2.previous = end_prev;
        edge2.adjacent = label1;

        label1
    }

    /// Adds a new full edge (two half-edges) to a planar map as a loop at the vertex before
    /// the half-edge given by `label`
    ///
    /// Returns the label of the first added half-edge for convenience, which is the outside
    /// edge of the loop.
    pub fn add_loop(&mut self, label: usize) -> usize {
        // TODO: First default and then edit value is not fully optimal
        let label1 = self.edges.insert(HalfEdge::default());
        let label2 = self.edges.insert(HalfEdge::default());

        let label_prev = self.edges[label].previous;
        self.edges[label].previous = label1;
        self.edges[label_prev].next = label1;

        let edge1 = &mut self.edges[label1];
        edge1.next = label;
        edge1.previous = label_prev;
        edge1.adjacent = label2;

        let edge2 = &mut self.edges[label2];
        edge2.next = label2;
        edge2.previous = label2;
        edge2.adjacent = label1;

        label1
    }

    /// Adds a number of full edges (two half-edges) to a planar map to create a cycle
    /// of length `len` of which `label` is a part, returning the first edge of the newly
    /// created edges.
    ///
    /// `len` must be larger than 1, as a cycle of length 0 does not exist and will cause
    /// the method to panic.
    pub fn add_cycle(&mut self, label: usize, len: usize) -> usize {
        assert!(len > 0, "A cycle must have at least length 1");
        if len == 1 {
            return self.add_loop(label);
        }
        let mut begin = label;
        let end = self.get_next(label);
        for _ in 0..(len - 2) {
            let new = self.add_edge(begin);
            begin = self.get_next(new);
        }
        self.add_edge_between(begin, end);

        self.get_adjacent(self.get_previous(label))
    }

    /// Adds a triangle, see [`PlanarMap::add_cycle()`] with `len = 3`.
    pub fn add_triangle(&mut self, label: usize) -> usize {
        self.add_cycle(label, 3)
    }

    /// Adds a square, see [`PlanarMap::add_cycle()`] with `len = 4`.
    pub fn add_square(&mut self, label: usize) -> usize {
        self.add_cycle(label, 4)
    }

    /// Glue two edges together by glueing half-edge `label1` and `label2`.
    ///
    /// Note: one can only glue edges belonging to the same face cycle. If other edges are
    /// glued the resulting structure is no longer a planar map and this function may return
    /// an invalid datastructure and unknown behaviour may occur.
    pub fn glue_edges(&mut self, label1: usize, label2: usize) {
        assert_ne!(label1, label2, "Cannot glue a half-edge to itself");
        // // This assertion should not be necessary if used in proper use cases
        // assert!(
        //     self.is_in_face(label1, label2),
        //     "Edges are not in the same face, cannot glue"
        // );
        let label1_prev = self.get_previous(label1);
        let label1_next = self.get_next(label1);
        let label1_adj = self.get_adjacent(label1);
        assert_ne!(
            label1_adj, label2,
            "Cannot glue a half-edge to its adjacent edge"
        );

        let label2_prev = self.get_previous(label2);
        let label2_next = self.get_next(label2);
        let label2_adj = self.get_adjacent(label2);

        self.edges[label1_next].previous = label2_prev;
        self.edges[label1_prev].next = label2_next;

        self.edges[label2_next].previous = label1_prev;
        self.edges[label2_prev].next = label1_next;

        self.edges[label1_adj].adjacent = label2_adj;
        self.edges[label2_adj].adjacent = label1_adj;

        self.edges.remove(label1);
        self.edges.remove(label2);
    }
}

impl PlanarMap {
    /// Returns if the edge `label` appears in the face cycle of `start`
    pub fn is_in_face(&self, start: usize, label: usize) -> bool {
        let mut current = start;
        loop {
            if current == label {
                return true;
            }
            current = self.get_next(current);
            if current == start {
                break;
            }
        }
        false
    }
}

impl PlanarMap {
    #[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 Default for PlanarMap {
    /// Creates an empty [`PlanarMap`]
    fn default() -> Self {
        Self::empty()
    }
}

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

impl PlanarMap {
    /// Construct the [`Triangulation2D`] represented by the [PlanarMap].
    ///
    /// # Important note
    /// A [Triangulation2D] is a [PlanarMap] where each face is a triangle.
    /// Hence the conversion will only be correct if the [PlanarMap] has only triangular faces.
    pub fn construct_triangulation(&self) -> Triangulation2D {
        let (vertices, edge_vertex_labels) = identify_vertices(self);
        // let vertices = vertices
        //     .into_iter()
        //     .map(|vertex| {
        //         let neighbours = vertex
        //             .into_iter()
        //             .map(|edge_label| {
        //                 let adjacent = self.get_adjacent(edge_label);
        //                 edge_vertex_labels[adjacent]
        //                     .expect("Each label should have been explored by construction")
        //             })
        //             .collect();
        //         Vertex { neighbours }
        //     })
        //     .collect();

        let (faces, edge_face_labels) = identify_faces(self);
        let triangles = faces
            .into_iter()
            .map(|face| {
                let (neighbours, vertices): (Vec<usize>, Vec<usize>) = face
                    .into_iter()
                    .map(|edge_label| {
                        let adjacent = self.get_adjacent(edge_label);
                        let neighbour = edge_face_labels[adjacent]
                            .expect("Each label should have been explored by construction");
                        let prev = self.get_previous(edge_label);
                        let vertex = edge_vertex_labels[prev]
                            .expect("Each label should have been explored by construction");
                        (neighbour, vertex)
                    })
                    .unzip();
                Triangle {
                    neighbours: neighbours
                        .try_into()
                        .expect("All faces should have exactly three edges"),
                    vertices: vertices
                        .try_into()
                        .expect("All faces should have exactly three vertices"),
                }
            })
            .collect();

        Triangulation2D {
            triangles,
            nvertices: vertices.len(),
        }
    }

    /// Construct the dual graph of the [PlanarMap]
    ///
    /// 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(|face| {
                let neighbours = face
                    .into_iter()
                    .map(|edge_label| {
                        let adjacent = self.get_adjacent(edge_label);
                        edge_face_labels[adjacent]
                            .expect("Each label should have been explored by construction")
                    })
                    .collect();
                Node::new(neighbours)
            })
            .collect();

        Graph::new(nodes)
    }

    /// Construct the vertex graph of the [PlanarMap]
    ///
    /// 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]
                            .expect("Each label should have been explored by construction")
                    })
                    .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: &PlanarMap) -> (Vec<Vec<usize>>, Vec<Option<usize>>) {
    let faces_len = map.len() / 3; // By Euler characteristic for a triangulation

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

    for (start_edge, _) in map.edges.iter() {
        // 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);
    }

    (faces, visited_edges)
}

/// Identify a face in the planar map by walking around the half-edges surrounding the face
fn identify_face(
    map: &PlanarMap,
    start_edge: usize,
    face_label: usize,
    visited_edges: &mut [Option<usize>],
) -> Vec<usize> {
    let mut face = Vec::with_capacity(3); // For a triangulaton
    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: &PlanarMap) -> (Vec<Vec<usize>>, Vec<Option<usize>>) {
    let vertex_len = map.len() / 3 + 2; // By Euler characteristic for 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.edges.capacity()];

    for (start_edge, _) in map.edges.iter() {
        // 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);
    }

    (vertices, visited_edges)
}

/// Identify a vertex in the PlanarMap by walking around its in- and outgoing edges.
///
/// You go to the half-edge on the opposite side of the edge and then the next half-edge.
/// Walking around like this you will return to the same half-edge, having cycled around a vertex.
///
/// Each outgoing edge is identified with that vertex
fn identify_vertex(
    map: &PlanarMap,
    start_edge: usize,
    vertex_label: usize,
    visited_edges: &mut [Option<usize>],
) -> Vec<usize> {
    let mut vertex = Vec::with_capacity(6);
    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
}

#[cfg(test)]
mod tests {

    use std::vec;

    use super::*;

    #[test]
    fn test_planar_map_creation() {
        let (mut map, root) = PlanarMap::new();
        println!("Root: {}", root);
        println!("{}", map);
        let mut current_edge = map.get_next(root);
        current_edge = map.add_triangle(current_edge);
        println!("active: {}", current_edge);
        println!("{}", map);
    }

    #[test]
    fn test_graph_creation() {
        let (mut map, root) = PlanarMap::new();
        let mut current_edge = map.get_next(root);
        current_edge = map.add_triangle(current_edge);
        current_edge = map.add_triangle(current_edge);
        let new_edge = map.get_next(current_edge);
        map.glue_edges(current_edge, map.get_previous(current_edge));
        map.glue_edges(new_edge, map.get_next(new_edge));

        let graph_dual = map.construct_dual_graph();
        assert_eq!(graph_dual.len(), 2);
        assert_eq!(graph_dual.get_neighbours(0), [1, 1, 1]);
        assert_eq!(graph_dual.get_neighbours(1), [0, 0, 0]);

        let graph_vertex = map.construct_vertex_graph();
        assert_eq!(graph_vertex.len(), 3);
        assert_eq!(graph_vertex.get_neighbours(0), [2, 1]);
        assert_eq!(graph_vertex.get_neighbours(1), [0, 2]);
        assert_eq!(graph_vertex.get_neighbours(2), [1, 0]);
    }

    #[test]
    fn test_triangulation_creation() {
        let (mut map, root) = PlanarMap::new();
        let current_edge = map.get_next(root);
        let next_edge = map.add_triangle(current_edge);
        map.add_triangle(next_edge);

        map.glue_edges(6, 8);
        map.glue_edges(0, 4);

        let triangulation = map.construct_triangulation();
        assert_eq!(
            triangulation,
            Triangulation2D {
                nvertices: 3,
                triangles: vec![
                    Triangle {
                        neighbours: [0, 0, 1],
                        vertices: [0, 0, 1],
                    },
                    Triangle {
                        neighbours: [0, 1, 1],
                        vertices: [2, 0, 0],
                    },
                ],
                // vertices: vec![
                //     Vertex {
                //         neighbours: vec![1, 0, 2, 0],
                //     },
                //     Vertex {
                //         neighbours: vec![0],
                //     },
                //     Vertex {
                //         neighbours: vec![0],
                //     },
                // ],
            }
        );
    }

    #[test]
    fn test_triangulation_creation_02() {
        let (mut map, root) = PlanarMap::new();
        let current_edge = map.get_next(root);
        let next_edge = map.add_triangle(current_edge);
        map.add_triangle(next_edge);

        map.glue_edges(0, 6);
        map.glue_edges(4, 8);

        let triangulation = map.construct_triangulation();
        assert_eq!(
            triangulation,
            Triangulation2D {
                nvertices: 3,
                triangles: vec![
                    Triangle {
                        neighbours: [1, 1, 1],
                        vertices: [1, 0, 2],
                    },
                    Triangle {
                        neighbours: [0, 0, 0],
                        vertices: [2, 0, 1],
                    },
                ],
                // vertices: vec![
                //     Vertex {
                //         neighbours: vec![2, 1],
                //     },
                //     Vertex {
                //         neighbours: vec![0, 2],
                //     },
                //     Vertex {
                //         neighbours: vec![1, 0],
                //     },
                // ],
            }
        );
    }
}
