//! Contains functionality to create geodesic polyhedra and goldberg polyhedra.
use petgraph::graph::EdgeIndex;
use petgraph::graph::NodeIndex;
use std::collections::HashMap;

use crate::geometry::*;
use crate::platonic_solids::make_icosahedron;
use crate::Polyhedron;

/// Helper struct to create Geodesic polyhedra.
#[derive(Debug)]
struct GeodesicBuilder {
    polyhedron: Polyhedron,
    m: u64,
    n: u64,
}

type EdgeReplacementMap = HashMap<EdgeIndex, NodeIndex>;

impl GeodesicBuilder {
    pub fn subdivide(&mut self) {
        debug_assert_eq!(
            self.polyhedron.assert_consistency(),
            Ok(()),
            "Failed consistency before subdivide"
        );

        let mut faces_new = Vec::new();

        let edge_replacement_map = self.create_vertices_for_edges();

        let faces_old = self.polyhedron.faces.clone();
        for face_old in &faces_old {
            self.subdivide_face(&face_old, &edge_replacement_map, &mut faces_new)
        }
        for face_old in &faces_old {
            self.remove_face_edges(&face_old)
        }

        self.polyhedron.faces = faces_new;

        self.m *= 2;

        debug_assert_eq!(
            self.polyhedron.assert_consistency(),
            Ok(()),
            "Failed consistency after subdivide"
        );
    }

    fn create_vertices_for_edges(&mut self) -> EdgeReplacementMap {
        // The result structure
        let mut edge_to_vertex: EdgeReplacementMap = HashMap::new();

        // Shorthand for our graph. Will receive new nodes.
        let graph = &mut self.polyhedron.graph;

        // Collect edges, as iterating and modifying is bad
        let mut edges: Vec<EdgeIndex> = Vec::new();
        edges.extend(graph.edge_indices());

        // Create a new node in the center of each edge.
        for edge in &edges {
            let vertex_position = {
                let (node_a, node_b) = graph.edge_endpoints(*edge).expect("Illegal edge access");

                let wa = WeightedValue {
                    value: graph.node_weight(node_a).expect("Illegal vertex lookup"),
                    weight: 1.0,
                };
                let wb = WeightedValue {
                    value: graph.node_weight(node_b).expect("Illegal vertex lookup"),
                    weight: 1.0,
                };

                weighted_centroid(&[wa, wb])
            };
            let vertex = graph.add_node(vertex_position);
            edge_to_vertex.insert(*edge, vertex);
        }

        edge_to_vertex
    }

    fn subdivide_face(
        &mut self,
        face: &Face,
        edge_to_vertex: &EdgeReplacementMap,
        new_faces: &mut Vec<Face>,
    ) {
        {
            let graph = &mut self.polyhedron.graph;

            let v0 = face.nodes[0].ix;
            let v1 = face.nodes[1].ix;
            let v2 = face.nodes[2].ix;

            let vertex_pairs = [(v0, v1), (v1, v2), (v2, v0)];

            let mid_nodes = {
                let get_mid_node = |(node_a, node_b): (NodeIndex, NodeIndex)| -> NodeIndex {
                    let edge = graph.find_edge(node_a, node_b);
                    let edge = edge.expect("Illegal node pair");

                    edge_to_vertex[&edge]
                };

                [
                    get_mid_node(vertex_pairs[0]),
                    get_mid_node(vertex_pairs[1]),
                    get_mid_node(vertex_pairs[2]),
                ]
            };

            for (i, (node_a, node_b)) in vertex_pairs.iter().enumerate() {
                let node_mid = mid_nodes[i];

                graph.update_edge(*node_a, node_mid, ());
                graph.update_edge(*node_b, node_mid, ());
            }

            graph.update_edge(mid_nodes[0], mid_nodes[1], ());
            graph.update_edge(mid_nodes[0], mid_nodes[2], ());
            graph.update_edge(mid_nodes[1], mid_nodes[2], ());

            new_faces.push(Face::new_triangle(&[
                VertexHandle::new(mid_nodes[0]),
                VertexHandle::new(mid_nodes[1]),
                VertexHandle::new(mid_nodes[2]),
            ]));

            new_faces.push(Face::new_triangle(&[
                VertexHandle::new(v0),
                VertexHandle::new(mid_nodes[0]),
                VertexHandle::new(mid_nodes[2]),
            ]));
            new_faces.push(Face::new_triangle(&[
                VertexHandle::new(v1),
                VertexHandle::new(mid_nodes[0]),
                VertexHandle::new(mid_nodes[1]),
            ]));
            new_faces.push(Face::new_triangle(&[
                VertexHandle::new(v2),
                VertexHandle::new(mid_nodes[1]),
                VertexHandle::new(mid_nodes[2]),
            ]));
        }
    }

    fn remove_face_edges(&mut self, face: &Face) {
        let graph = &mut self.polyhedron.graph;

        let v0 = face.nodes[0];
        let v1 = face.nodes[1];
        let v2 = face.nodes[2];

        let vertex_pairs = [(v0, v1), (v1, v2), (v2, v0)];

        for (node_a, node_b) in &vertex_pairs {
            let edge = graph.find_edge(node_a.ix, node_b.ix);
            if let Some(edge) = edge {
                graph.remove_edge(edge);
            }
        }
    }

    /// GeodesicToGoldberg returns the goldberg Polyhedron that corresponds to the given geodesic Polyhedron.
    /// This is achieved by replacing all faces with vertices and adding edges between vertices that corresponded to neighbouring faces.
    fn to_goldberg(&self) -> Polyhedron {
        debug_assert!(self.polyhedron.assert_consistency().is_ok());

        let mut graph_new = VertexGraph::default();

        // For each face create a new vertex
        let vertex_map: HashMap<&Face, NodeIndex> = {
            let mut vertex_map = HashMap::new();
            for face in &self.polyhedron.faces {
                let node_pos = face.center(&self.polyhedron.graph);
                let node = graph_new.add_node(node_pos);
                vertex_map.insert(face, node);
            }
            vertex_map
        };

        // Create edges between nodes from adjacent faces.
        for (_, (face_a, face_b)) in get_edge_face_map(&self.polyhedron) {
            let node_a = vertex_map[face_a];
            let node_b = vertex_map[face_b];
            graph_new.add_edge(node_a, node_b, ());
        }

        let faces_new = {
            // Prepare a closure that will help to sort vertices within a face to preserver
            // their adjacency.
            let sort_vertices = |vertices: &mut Vec<NodeIndex>| {
                // Arrange vertices so that neighboring vertices correspond to neighbouring faces
                for i in 0..vertices.len() {
                    let v1 = vertices[i];
                    for j in (i + 1)..vertices.len() {
                        let v2 = vertices[j];
                        // If v2 corresponds to a face next to v1's face, we put it next to v1
                        // Otherwise we keep looking
                        if graph_new.find_edge(v1, v2).is_some() {
                            vertices.swap(j, i + 1);
                            break;
                        }
                    }
                }
            };

            // Turn adjacent vertices into faces
            make_node_face_map(&self.polyhedron)
                .iter()
                .map(|(_, faces)| {
                    let mut vertices: Vec<NodeIndex> =
                        faces.iter().map(|f| vertex_map[f]).collect();

                    // Arrange vertices so that neighboring vertices correspond to neighbouring faces
                    sort_vertices(&mut vertices);

                    let f = Face::from_node_index(&vertices);

                    {
                        let contains_edge = |(v1, v2): (VertexHandle, VertexHandle)| {
                            graph_new.find_edge_undirected(v1.ix, v2.ix).is_some()
                        };

                        debug_assert!(
                            f.edges().into_iter().all(contains_edge),
                            "Created face {:?} with edges that are not in graph {:?}",
                            f,
                            graph_new
                        );
                    };
                    f
                })
                .collect()
        };
        let result = Polyhedron {
            graph: graph_new,
            faces: faces_new,
        };
        debug_assert_eq!(
            result.assert_consistency(),
            Ok(()),
            "Failed consistency after in goldberg conversion"
        );
        result
    }
}

/// Return a HashMap of all edges to their adjacent faces.
fn get_edge_face_map<'a>(polyhedron: &'a Polyhedron) -> HashMap<EdgeIndex, (&'a Face, &'a Face)> {
    let mut map: HashMap<EdgeIndex, Vec<&Face>> = HashMap::new();
    {
        // We know we will get two faces overall, but first we need to collect the faces in
        // a vector. This function pushed the given face into the vector corresponding
        // to the given edge (or initialises it, if there hasn't been one yet).
        let mut insert_face = |key: EdgeIndex, value: &'a Face| {
            let vec = map.entry(key).or_insert_with(Vec::new);
            // We also need to check the face has not been added yet
            if !vec.contains(&value) {
                vec.push(value);
            }
        };

        // For each face...
        for face in &polyhedron.faces {
            // ...we look at each edge...
            for (node_a, node_b) in face.edges() {
                let edge = polyhedron.graph.find_edge(node_a.ix, node_b.ix);
                let edge = edge.expect("Illegal edge access.");
                // ...and add the face to the corresponding edge vector.
                insert_face(edge, face)
            }
        }
    }
    // We discard the vectors and just extract the two faces
    map.iter()
        .map(|(k, v)| {
            assert_eq!(
                v.len(),
                2,
                "Found edge with {} adjacent faces. Expected 2.",
                v.len()
            );
            (*k, (v[0], v[1]))
        })
        .collect()
}

/// Return a HashMap of all nodes to their adjacent faces.
fn make_node_face_map<'a>(polyhedron: &'a Polyhedron) -> HashMap<NodeIndex, Vec<&'a Face>> {
    let mut map: HashMap<NodeIndex, Vec<&Face>> = HashMap::new();
    {
        // Push the given value to the vector for the given node.
        // In case there is no vector yet, create it.
        let mut insert = |key: NodeIndex, value: &'a Face| {
            let vec = map.entry(key).or_insert_with(Vec::new);
            vec.push(value);
        };

        // For each face go through all its nodes and add the face to the vector.
        for face in &polyhedron.faces {
            for node in face.nodes() {
                insert(node.ix, face);
            }
        }
    }
    map
}

/// Create a icosahedral geodesic with the given numbers of subdivisions.
/// For more information see https://en.wikipedia.org/wiki/Geodesic_polyhedron
pub fn build_icosahedral_geodesic(subdivisions: u64) -> Polyhedron {
    let mut geo = GeodesicBuilder {
        polyhedron: make_icosahedron(),
        m: 1,
        n: 0,
    };
    for _ in 0..subdivisions {
        geo.subdivide();
    }
    geo.polyhedron
}

/// Create an icosahedral Goldberg polyhedron with the given numbers of subdivisions.
/// For more information see https://en.wikipedia.org/wiki/Goldberg_polyhedron
pub fn build_icosahedral_goldberg(subdivisions: u64) -> Polyhedron {
    let mut geo = GeodesicBuilder {
        polyhedron: make_icosahedron(),
        m: 1,
        n: 0,
    };
    for _ in 0..subdivisions {
        geo.subdivide();
    }
    geo.to_goldberg()
}

#[cfg(test)]
mod tests {

    use super::*;
    use crate::topology::Tiling;
    use std::time::Instant;

    fn check_subdivision(m: u64) {
        let gg = build_icosahedral_geodesic(m);

        let n = 0_u64;
        let m = 2_u64.pow(m as u32);
        let t = n * m + n * n + m * m;

        let face_count = gg.faces.len() as u64;

        if face_count != (t * 20) {
            panic!("Number of faces is {} instead of {}.", face_count, 20 * t)
        }

        let edge_count = gg.graph.edge_count() as u64;
        if edge_count != (t * 30) {
            panic!("Number of edges is {} instead of {}.", edge_count, 30 * t)
        }

        let vertex_count = gg.graph.node_count() as u64;
        if vertex_count != (t * 10 + 2) {
            panic!(
                "Number of vertices is {} instead of {}.",
                vertex_count,
                10 * t + 3
            )
        }
    }

    #[test]
    fn test_subdivision() {
        let start = Instant::now();
        for n in 0..5 {
            check_subdivision(n);
        }
        let end = Instant::now();
        println!("{} seconds for whatever you did.", (end - start).as_secs());
    }

    #[test]
    fn test_goldberg_polyhedron() {
        for i in 0..5 {
            let start = Instant::now();
            let igp = build_icosahedral_goldberg(i);
            let end = Instant::now();
            println!(
                "{} seconds for creating a {} subdivision Goldberg Polyhedron.",
                (end - start).as_secs(),
                i
            );

            let n = 0;
            let m = 2_i32.pow(i as u32);
            let t = (m * n + m * m + n * n) as usize;

            println!("with {} nodes", igp.graph.node_count());
            assert_eq!(igp.faces.len(), 10 * t + 2);
            assert_eq!(igp.graph.node_count(), 20 * t);
            assert_eq!(igp.graph.edge_count(), 30 * t);
        }
    }

    #[test]
    fn test_goldberg_edge_validity() {
        for i in 0..5 {
            let igp = build_icosahedral_goldberg(i);

            for face in igp.faces.iter() {
                for (v1, v2) in face.edges() {
                    assert_ne!(
                        None,
                        igp.graph.find_edge(v1.ix, v2.ix),
                        "Found edge in face ({:?}, {:?}) that is missing from graph {:?}",
                        v1,
                        v2,
                        igp.graph
                    )
                }
            }
        }
    }

    #[test]
    fn test_geodesic_consistency() {
        for i in 0..5 {
            println!("Checking subdivision {}.", i);
            let ic = build_icosahedral_geodesic(i);

            for face in ic.faces() {
                for (v1, v2) in face.edges() {
                    assert_ne!(
                        ic.graph.find_edge_undirected(v1.ix, v2.ix),
                        None,
                        "Found invalid edge: ({:?}, {:?}) in face",
                        v1,
                        v2
                    );
                }
            }
        }
    }

    #[test]
    fn test_geodesic_map_consistency() {
        for i in 0..5 {
            let ic = build_icosahedral_geodesic(i);
            let edge_face_map = get_edge_face_map(&ic);
            let node_face_map = make_node_face_map(&ic);

            // If a face is edge adjacent, it should also be node adjacent to both nodes in the edge
            for (edge, edge_faces) in edge_face_map {
                let (v1, v2) = ic.graph.edge_endpoints(edge).unwrap();
                let faces_v1 = &node_face_map[&v1];
                assert!(faces_v1.contains(&edge_faces.0));
                assert!(faces_v1.contains(&edge_faces.1));

                let faces_v2 = &node_face_map[&v2];
                assert!(faces_v2.contains(&edge_faces.0));
                assert!(faces_v2.contains(&edge_faces.1));
            }
        }
    }

    #[test]
    fn test_get_node_face_map() {
        for i in 0..5 {
            println!("Checking subdivision {}.", i);
            let ic = build_icosahedral_geodesic(i);

            let nfm = make_node_face_map(&ic);
            for (node, faces) in nfm {
                assert!(
                    faces.len() == 5 || faces.len() == 6,
                    "Expected there to be 5 or 6 adjacent faces adjacent to {:?}, but found {:?}",
                    node,
                    faces.len()
                );

                assert!(ic.graph.contains_node(node));
                for face in &faces {
                    for (v1, v2) in face.edges() {
                        assert!(ic.graph.find_edge(v1.ix, v2.ix).is_some())
                    }
                }
            }
        }
    }

    #[test]
    fn test_goldberg_tiling() {
        for i in 0..5 {
            println!("Checking subdivision {}.", i);
            let igp = build_icosahedral_goldberg(i);

            for node in igp.iter() {
                for (boundary, neighbour) in igp.adjacent(node) {
                    assert_ne!(
                        neighbour, None,
                        "Found unconnected edge: ({:?}, {:?})",
                        boundary, neighbour
                    );
                }
            }
        }
    }

    #[test]
    fn test_goldberg_polyhedron_node_degrees() {
        for i in 0..5 {
            let igp = build_icosahedral_goldberg(i);
            let graph: VertexGraph = igp.into();
            graph.node_indices().for_each(|n_ix| {
                let nc = graph.neighbors(n_ix).count();
                assert_eq!(nc, 3, "Found node with {} neighbors. Expected 3.", nc);
            })
        }
    }
}