/*!
 * This module defines routines for dealing with meshes composed of multiple connected components.
 */

use crate::index::*;
use crate::mesh::topology::*;

/// A trait defining the primary method for determining connectivity in a mesh.
pub trait Connectivity<I: TopoIndex<usize>> {
    /// An optional function that allows implementers to precompute topology information to help
    /// with the implementation of `push_neighbours` when the mesh doesn't already support a
    /// certain type of topology.
    fn precompute_reverse_topo(&self) -> (Vec<usize>, Vec<usize>) {
        (Vec::new(), Vec::new())
    }
    /// Get a list of indices for the elements which are considered for connectivity (e.g.
    /// triangles in triangle meshes or tets in a tetmesh).
    fn num_elements(&self) -> usize;
    /// Push all neighbours of the element at the given index to the given stack.
    fn push_neighbours(
        &self,
        index: I::SrcIndex,
        stack: &mut Vec<I::SrcIndex>,
        topo: &(Vec<usize>, Vec<usize>),
    );

    /// Determine the connectivity of a set of meshes. Return a `Vec` with the size of
    /// `self.indices().len()` indicating a unique ID of the connected component each element
    /// belongs to. For instance, if two triangles in a triangle mesh blong to the same connected
    /// component, they will have the same ID. Also return the total number of components generated.
    fn connectivity(&self) -> (Vec<usize>, usize) {
        // The ID of the current connected component.
        let mut cur_component_id = 0;

        let mut stack: Vec<I::SrcIndex> = Vec::new();

        let num_element_indices = self.num_elements();

        // The vector of component ids (one for each element).
        let mut component_ids = vec![Index::INVALID; num_element_indices];

        let data = self.precompute_reverse_topo();

        // Perform a depth first search through the mesh topology to determine connected components.
        for elem in 0..num_element_indices {
            if component_ids[elem].is_valid() {
                continue;
            }

            // elem is the representative element for the current connected component.
            stack.push(elem.into());

            while let Some(elem) = stack.pop() {
                let elem_idx: usize = elem.into();
                if !component_ids[elem_idx].is_valid() {
                    // Process element if it hasn't been seen before.
                    component_ids[elem_idx] = cur_component_id.into();
                    self.push_neighbours(elem, &mut stack, &data);
                }
            }

            // Finished with the current component, no more connected elements.
            cur_component_id += 1;
        }

        // Ensure that all ids are valid before we reinterpret the vector.
        debug_assert!(component_ids.iter().all(|&x| x.is_valid()));
        (
            crate::index_vec_into_usize(component_ids),
            cur_component_id,
        )
    }
}

// The default connectivity for standard meshes (PolyMesh, TriMesh, QuadMesh and TetMesh) is taken
// to be vertex connectivity. This means that two vertices are in the same connected component iff
// there is a path between them along a set of edges. Other types of connectivity may be
// implemented, but this type allows meshes to be split and rejoined without changing the number of
// total vertices and possibly their order.

/// Implement vertex connectivity for cell based meshes (e.g. TetMesh).
impl<M: VertexCell + CellVertex + NumVertices> Connectivity<VertexCellIndex> for M {
    fn num_elements(&self) -> usize {
        self.num_vertices()
    }

    fn push_neighbours(
        &self,
        index: VertexIndex,
        stack: &mut Vec<VertexIndex>,
        _: &(Vec<usize>, Vec<usize>),
    ) {
        for which_cell in 0..self.num_cells_at_vertex(index) {
            let cell = self.vertex_to_cell(index, which_cell).unwrap();
            for which_vtx in 0..self.num_vertices_at_cell(cell) {
                let neigh_vtx = self.cell_to_vertex(cell, which_vtx).unwrap();
                if neigh_vtx != index {
                    stack.push(neigh_vtx);
                }
            }
        }
    }
}

/// Implement vertex connectivity for face based meshes (e.g. PolyMesh, TriMesh and QuadMesh).
impl<M: FaceVertex + NumVertices + NumFaces> Connectivity<VertexFaceIndex> for M {
    fn precompute_reverse_topo(&self) -> (Vec<usize>, Vec<usize>) {
        self.reverse_topo()
    }
    fn num_elements(&self) -> usize {
        self.num_vertices()
    }

    fn push_neighbours(
        &self,
        index: VertexIndex,
        stack: &mut Vec<VertexIndex>,
        topo: &(Vec<usize>, Vec<usize>),
    ) {
        let (face_indices, face_offsets) = topo;
        let idx = usize::from(index);
        for face in (face_offsets[idx]..face_offsets[idx + 1]).map(|i| face_indices[i]) {
            for which_vtx in 0..self.num_vertices_at_face(face) {
                let neigh_vtx = self.face_to_vertex(face, which_vtx).unwrap();
                if neigh_vtx != index {
                    stack.push(neigh_vtx);
                }
            }
        }
    }
}

use crate::mesh::{attrib::*, PolyMesh, TetMesh, TetMeshExt};
use crate::Real;
use buffer::DataBuffer;
use reinterpret::reinterpret_vec;

pub trait SplitIntoConnectedComponents<TI>
where
    TI: TopoIndex<usize>,
    Self: Sized,
{
    fn split_into_connected_components(self) -> Vec<Self>;
}

// TODO: Refactor the below two implementations by extracting common patterns. This can also be
// combined with implementations conversions between meshes.

impl<T: Real> SplitIntoConnectedComponents<VertexCellIndex> for TetMesh<T> {
    fn split_into_connected_components(self) -> Vec<Self> {
        let tetmesh_ext = TetMeshExt::from(self);
        tetmesh_ext.split_into_connected_components().into_iter()
            .map(|tetmesh_ext| TetMesh::from(tetmesh_ext)).collect()
    }
}

impl<T: Real> SplitIntoConnectedComponents<VertexCellIndex> for TetMeshExt<T> {
    fn split_into_connected_components(self) -> Vec<Self> {
        // First we partition the vertices.
        let (vertex_connectivity, num_components) = self.connectivity();

        // Fast path, when everything is connected.
        if num_components == 1 {
            return vec![self];
        }

        // Deconstruct the original mesh.
        let TetMeshExt {
            tetmesh: TetMesh {
                vertex_positions,
                indices,
                vertex_attributes,
                cell_attributes,
                cell_vertex_attributes,
                cell_face_attributes,
            },
            cell_offsets,
            cell_indices,
            vertex_cell_attributes,
            ..
        } = self;

        // Record where the new vertices end up (just the index within their respective
        // components). The component ids themselves are recorded separately.
        let mut new_vertex_indices = vec![Index::INVALID; vertex_positions.len()];

        // Transfer vertex positions
        let mut comp_vertex_positions = vec![Vec::new(); num_components];
        for (vidx, &comp_id) in vertex_connectivity.iter().enumerate() {
            new_vertex_indices[vidx] = comp_vertex_positions[comp_id].len().into();
            comp_vertex_positions[comp_id].push(vertex_positions[vidx]);
        }

        // Validate that all vertices have been properly mapped.
        debug_assert!(new_vertex_indices.iter().all(|&idx| idx.is_valid()));
        let new_vertex_indices: Vec<usize> = unsafe { reinterpret_vec(new_vertex_indices) };

        // Record cell connectivity. Note that if cells have vertices on different components,
        // they will be ignored in the output and their connectivity will be "invalid".
        let mut cell_connectivity = vec![Index::INVALID; indices.len()];
        let mut new_cell_indices = vec![Index::INVALID; indices.len()];

        // Transfer cells
        let mut comp_vertex_indices = vec![Vec::new(); num_components];
        for (cell_idx, &cell) in indices.iter().enumerate() {
            let comp_id = vertex_connectivity[cell[0]];
            if cell.iter().all(|&i| vertex_connectivity[i] == comp_id) {
                let new_cell = [
                    new_vertex_indices[cell[0]],
                    new_vertex_indices[cell[1]],
                    new_vertex_indices[cell[2]],
                    new_vertex_indices[cell[3]],
                ];
                new_cell_indices[cell_idx] = comp_vertex_indices[comp_id].len().into();
                comp_vertex_indices[comp_id].push(new_cell);
                cell_connectivity[cell_idx] = Index::from(comp_id);
            }
        }

        // Transfer vertex to cell topology
        let mut comp_cell_indices = vec![Vec::new(); num_components];
        let mut comp_cell_offsets = vec![vec![0]; num_components];
        for (vidx, &comp_id) in vertex_connectivity.iter().enumerate() {
            let off = cell_offsets[vidx];
            for i in off..cell_offsets[vidx + 1] {
                let cell_idx = cell_indices[i];
                new_cell_indices[cell_idx]
                    .if_valid(|new_cidx| comp_cell_indices[comp_id].push(new_cidx));
            }
            comp_cell_offsets[comp_id].push(comp_cell_indices[comp_id].len());
        }

        // Transfer vertex-cell attributes
        let mut comp_vertex_cell_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in vertex_cell_attributes.iter() {
            // Create a new data buffer with the same type.
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            // Get an iterator of typeless byte chunks for this attribute.
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            let mut vtx_idx = 0;
            for (i, bytes) in attrib_chunks.enumerate() {
                // Determine the vertex index here using offsets
                let off = cell_offsets[vtx_idx + 1];
                if i == off {
                    vtx_idx += 1;
                }
                let comp_id = vertex_connectivity[vtx_idx];
                let cell_idx = cell_indices[i];

                // Add bytes for this vertex to the appropriate component data.
                if new_cell_indices[cell_idx].is_valid() {
                    data_bufs[comp_id].push_bytes(bytes);
                }
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_vertex_cell_attributes
                .iter_mut()
                .zip(data_bufs.into_iter())
            {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Transfer vertex attributes
        let mut comp_vertex_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in vertex_attributes.iter() {
            // Create a new data buffer with the same type.
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            // Get an iterator of typeless byte chunks for this attribute.
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (&comp_id, bytes) in vertex_connectivity.iter().zip(attrib_chunks) {
                // Add bytes for this vertex to the appropriate component data.
                data_bufs[comp_id].push_bytes(bytes);
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_vertex_attributes.iter_mut().zip(data_bufs.into_iter())
            {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Transfer cell attributes
        let mut comp_cell_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in cell_attributes.iter() {
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (&comp_id, bytes) in cell_connectivity.iter().zip(attrib_chunks) {
                comp_id.if_valid(|comp_id| {
                    // Add bytes for this cell to the appropriate component data.
                    data_bufs[comp_id].push_bytes(bytes);
                });
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_cell_attributes.iter_mut().zip(data_bufs.into_iter()) {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Transfer cell vertex attributes
        let mut comp_cell_vertex_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in cell_vertex_attributes.iter() {
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (comp_id, bytes) in cell_connectivity
                .iter()
                .flat_map(|c| std::iter::repeat(c).take(4))
                .zip(attrib_chunks)
            {
                comp_id.if_valid(|comp_id| {
                    // Add bytes for this cell vertex to the appropriate component data.
                    data_bufs[comp_id].push_bytes(bytes);
                });
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_cell_vertex_attributes
                .iter_mut()
                .zip(data_bufs.into_iter())
            {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Transfer cell face attributes
        let mut comp_cell_face_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in cell_face_attributes.iter() {
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (comp_id, bytes) in cell_connectivity
                .iter()
                .flat_map(|c| std::iter::repeat(c).take(4))
                .zip(attrib_chunks)
            {
                comp_id.if_valid(|comp_id| {
                    // Add bytes for this cell vertex to the appropriate component data.
                    data_bufs[comp_id].push_bytes(bytes);
                });
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_cell_face_attributes
                .iter_mut()
                .zip(data_bufs.into_iter())
            {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Generate a Vec of meshes.
        comp_vertex_positions
            .into_iter()
            .zip(comp_vertex_indices.into_iter())
            .zip(comp_cell_indices.into_iter())
            .zip(comp_cell_offsets.into_iter())
            .zip(comp_vertex_attributes.into_iter())
            .zip(comp_cell_attributes.into_iter())
            .zip(comp_cell_vertex_attributes.into_iter())
            .zip(comp_cell_face_attributes.into_iter())
            .zip(comp_vertex_cell_attributes.into_iter())
            .map(
                |((((((((vp, vi), ci), co), va), ca), cva), cfa), vca)| TetMeshExt {
                    tetmesh: TetMesh {
                        vertex_positions: vp.into(),
                        indices: vi.into(),
                        vertex_attributes: va,
                        cell_attributes: ca,
                        cell_vertex_attributes: cva,
                        cell_face_attributes: cfa,
                    },
                    cell_indices: ci,
                    cell_offsets: co,
                    vertex_cell_attributes: vca,
                },
            )
            .collect()
    }
}

impl<T: Real> SplitIntoConnectedComponents<VertexFaceIndex> for PolyMesh<T> {
    fn split_into_connected_components(self) -> Vec<Self> {
        // First we partition the vertices.
        let (vertex_connectivity, num_components) = self.connectivity();

        // Fast path, when everything is connected.
        if num_components == 1 {
            return vec![self];
        }

        // Record where the new vertices end up (just the index within their respective
        // components). The component ids themselves are recorded separately.
        let mut new_vertex_indices = vec![Index::INVALID; self.vertex_positions.len()];

        // Transfer vertex positions
        let mut comp_vertex_positions = vec![Vec::new(); num_components];
        for (vidx, &comp_id) in vertex_connectivity.iter().enumerate() {
            new_vertex_indices[vidx] = comp_vertex_positions[comp_id].len().into();
            comp_vertex_positions[comp_id].push(self.vertex_positions[vidx]);
        }

        // Validate that all vertices have been properly mapped.
        debug_assert!(new_vertex_indices.iter().all(|&idx| idx.is_valid()));
        let new_vertex_indices = crate::index_vec_into_usize(new_vertex_indices);

        // Record face connectivity. Note that if faces have vertices on different components,
        // they will be ignored in the output and their connectivity will be "invalid".
        let mut face_connectivity = vec![Index::INVALID; self.num_faces()];

        // Transfer faces
        let mut comp_indices = vec![Vec::new(); num_components];
        let mut comp_offsets = vec![vec![0]; num_components];
        for (face, face_comp_id) in self.face_iter().zip(face_connectivity.iter_mut()) {
            let comp_id = vertex_connectivity[face[0]];
            if face.iter().all(|&i| vertex_connectivity[i] == comp_id) {
                let new_face_vtx_iter = face.iter().map(|&vi| new_vertex_indices[vi]);
                comp_indices[comp_id].extend(new_face_vtx_iter);
                comp_offsets[comp_id].push(comp_indices[comp_id].len());
                *face_comp_id = Index::from(comp_id);
            }
        }

        // Transfer vertex attributes
        let mut comp_vertex_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in self.vertex_attributes.iter() {
            // Create a new data buffer with the same type.
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            // Get an iterator of typeless byte chunks for this attribute.
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (&comp_id, bytes) in vertex_connectivity.iter().zip(attrib_chunks) {
                // Add bytes for this vertex to the appropriate component data.
                data_bufs[comp_id].push_bytes(bytes);
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_vertex_attributes.iter_mut().zip(data_bufs.into_iter())
            {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Transfer face attributes
        let mut comp_face_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in self.face_attributes.iter() {
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (&comp_id, bytes) in face_connectivity.iter().zip(attrib_chunks) {
                comp_id.if_valid(|comp_id| {
                    // Add bytes for this face to the appropriate component data.
                    data_bufs[comp_id].push_bytes(bytes);
                });
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_face_attributes.iter_mut().zip(data_bufs.into_iter()) {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Transfer face vertex attributes
        let mut comp_face_vertex_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in self.face_vertex_attributes.iter() {
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (comp_id, bytes) in face_connectivity
                .iter()
                .enumerate()
                .flat_map(|(fi, c)| std::iter::repeat(c).take(self.num_vertices_at_face(fi)))
                .zip(attrib_chunks)
            {
                comp_id.if_valid(|comp_id| {
                    // Add bytes for this cell vertex to the appropriate component data.
                    data_bufs[comp_id].push_bytes(bytes);
                });
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_face_vertex_attributes
                .iter_mut()
                .zip(data_bufs.into_iter())
            {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Transfer face edge attributes
        let mut comp_face_edge_attributes = vec![AttribDict::new(); num_components];
        for (name, attrib) in self.face_edge_attributes.iter() {
            let mut data_bufs =
                vec![DataBuffer::with_buffer_type(attrib.buffer_ref()); num_components];
            let attrib_chunks = attrib.buffer_ref().byte_chunks();

            for (comp_id, bytes) in face_connectivity
                .iter()
                .enumerate()
                .flat_map(|(fi, c)| std::iter::repeat(c).take(self.num_edges_at_face(fi)))
                .zip(attrib_chunks)
            {
                comp_id.if_valid(|comp_id| {
                    // Add bytes for this cell vertex to the appropriate component data.
                    data_bufs[comp_id].push_bytes(bytes);
                });
            }

            // Save the new attributes to their corresponding attribute dictionaries.
            for (attrib_dict, data) in comp_face_edge_attributes
                .iter_mut()
                .zip(data_bufs.into_iter())
            {
                attrib_dict.insert(
                    name.to_string(),
                    Attribute::from_data_buffer(data, attrib.default_bytes()),
                );
            }
        }

        // Generate a Vec of meshes.
        comp_vertex_positions
            .into_iter()
            .zip(comp_indices.into_iter())
            .zip(comp_offsets.into_iter())
            .zip(comp_vertex_attributes.into_iter())
            .zip(comp_face_attributes.into_iter())
            .zip(comp_face_vertex_attributes.into_iter())
            .zip(comp_face_edge_attributes.into_iter())
            .map(|((((((vp, i), o), va), fa), fva), fea)| PolyMesh {
                vertex_positions: vp.into(),
                indices: i,
                offsets: o,
                vertex_attributes: va,
                face_attributes: fa,
                face_vertex_attributes: fva,
                face_edge_attributes: fea,
            })
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::algo::test_utils::*;
    use crate::mesh::{TetMeshExt, TriMesh};

    #[test]
    fn tetmesh_connectivity() {
        // The vertex positions are actually unimportant here.
        let verts = vec![[0.0; 3]; 12];

        // One connected component consisting of two tets connected at a face, and another
        // consisting of two tets connected at a single vertex.
        let indices = vec![0, 1, 2, 3, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 11];

        let tetmesh = TetMeshExt::new(verts, indices);

        assert_eq!(
            tetmesh.connectivity(),
            (vec![0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1], 2)
        );
    }

    #[test]
    fn trimesh_connectivity() {
        // The vertex positions are actually unimportant here.
        let verts = vec![[0.0; 3]; 7];

        // One component with two connected triangles at an edge and another with a single triangle
        // that is disconnected
        let indices = vec![0, 1, 2, 1, 2, 3, 4, 5, 6];

        let trimesh = TriMesh::new(verts, indices);

        assert_eq!(trimesh.connectivity(), (vec![0, 0, 0, 0, 1, 1, 1], 2));
    }

    fn build_tetmesh_sample() -> (TetMeshExt<f64>, TetMeshExt<f64>, TetMeshExt<f64>) {
        let verts = vec![
            [0.0, 0.0, 0.0],
            [0.0, 0.0, 1.0],
            [0.0, 1.0, 0.0],
            [0.0, 1.0, 1.0],
            [1.0, 0.0, 0.0],
            [1.0, 0.0, 1.0],
            [1.0, 1.0, 0.0],
            [1.0, 1.0, 1.0],
            [0.5, 0.0, 0.5],
        ];

        // One connected component consisting of two tets connected at a face, and another
        // consisting of a single tet.
        let indices = vec![7, 6, 2, 4, 5, 7, 2, 4, 0, 1, 3, 8];

        let tetmesh = TetMeshExt::new(verts, indices);
        let comp1 = TetMeshExt::new(
            vec![
                [0.0, 0.0, 0.0],
                [0.0, 0.0, 1.0],
                [0.0, 1.0, 1.0],
                [0.5, 0.0, 0.5],
            ],
            vec![0, 1, 2, 3],
        );
        let comp2 = TetMeshExt::new(
            vec![
                [0.0, 1.0, 0.0],
                [1.0, 0.0, 0.0],
                [1.0, 0.0, 1.0],
                [1.0, 1.0, 0.0],
                [1.0, 1.0, 1.0],
            ],
            vec![4, 3, 0, 1, 2, 4, 0, 1],
        );
        (tetmesh, comp1, comp2)
    }

    #[test]
    fn tetmesh_split() {
        let (tetmesh, comp1, comp2) = build_tetmesh_sample();

        // First lets verify the vertex partitioning.
        assert_eq!(tetmesh.connectivity(), (vec![0, 0, 1, 0, 1, 1, 1, 1, 0], 2));

        let res = tetmesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn tetmesh_split_with_vertex_attributes() {
        let (mut tetmesh, mut comp1, mut comp2) = build_tetmesh_sample();
        tetmesh
            .add_attrib_data::<usize, VertexIndex>("v", (0..tetmesh.num_vertices()).collect())
            .unwrap();
        comp1
            .add_attrib_data::<usize, VertexIndex>("v", vec![0, 1, 3, 8])
            .unwrap();
        comp2
            .add_attrib_data::<usize, VertexIndex>("v", vec![2, 4, 5, 6, 7])
            .unwrap();
        let res = tetmesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn tetmesh_split_with_cell_attributes() {
        let (mut tetmesh, mut comp1, mut comp2) = build_tetmesh_sample();
        tetmesh
            .add_attrib_data::<usize, CellIndex>("c", (0..tetmesh.num_cells()).collect())
            .unwrap();
        comp1
            .add_attrib_data::<usize, CellIndex>("c", vec![2])
            .unwrap();
        comp2
            .add_attrib_data::<usize, CellIndex>("c", vec![0, 1])
            .unwrap();
        let res = tetmesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn tetmesh_split_with_cell_vertex_attributes() {
        let (mut tetmesh, mut comp1, mut comp2) = build_tetmesh_sample();
        tetmesh
            .add_attrib_data::<usize, CellVertexIndex>("cv", (0..tetmesh.num_cells() * 4).collect())
            .unwrap();

        comp1
            .add_attrib_data::<usize, CellVertexIndex>("cv", vec![8, 9, 10, 11])
            .unwrap();
        comp2
            .add_attrib_data::<usize, CellVertexIndex>("cv", vec![0, 1, 2, 3, 4, 5, 6, 7])
            .unwrap();
        let res = tetmesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn tetmesh_split_with_cell_face_attributes() {
        let (mut tetmesh, mut comp1, mut comp2) = build_tetmesh_sample();
        tetmesh
            .add_attrib_data::<usize, CellFaceIndex>("cf", (0..tetmesh.num_cells() * 4).collect())
            .unwrap();

        comp1
            .add_attrib_data::<usize, CellFaceIndex>("cf", vec![8, 9, 10, 11])
            .unwrap();
        comp2
            .add_attrib_data::<usize, CellFaceIndex>("cf", vec![0, 1, 2, 3, 4, 5, 6, 7])
            .unwrap();
        let res = tetmesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn tetmesh_split_with_vertex_cell_attributes() {
        let (mut tetmesh, mut comp1, mut comp2) = build_tetmesh_sample();
        tetmesh
            .add_attrib_data::<usize, VertexCellIndex>("vc", (0..tetmesh.num_cells() * 4).collect())
            .unwrap();

        comp1
            .add_attrib_data::<usize, VertexCellIndex>("vc", vec![0, 1, 4, 11])
            .unwrap();
        comp2
            .add_attrib_data::<usize, VertexCellIndex>("vc", vec![2, 3, 5, 6, 7, 8, 9, 10])
            .unwrap();
        let res = tetmesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn tetmesh_split_with_all_attributes() {
        let (mut tetmesh, mut comp1, mut comp2) = build_tetmesh_sample();
        tetmesh
            .add_attrib_data::<usize, VertexIndex>("v", (0..tetmesh.num_vertices()).collect())
            .unwrap();
        tetmesh
            .add_attrib_data::<usize, CellIndex>("c", (0..tetmesh.num_cells()).collect())
            .unwrap();
        tetmesh
            .add_attrib_data::<usize, CellVertexIndex>("cv", (0..tetmesh.num_cells() * 4).collect())
            .unwrap();
        tetmesh
            .add_attrib_data::<usize, CellFaceIndex>("cf", (0..tetmesh.num_cells() * 4).collect())
            .unwrap();
        tetmesh
            .add_attrib_data::<usize, VertexCellIndex>("vc", (0..tetmesh.num_cells() * 4).collect())
            .unwrap();
        comp1
            .add_attrib_data::<usize, VertexIndex>("v", vec![0, 1, 3, 8])
            .unwrap();
        comp1
            .add_attrib_data::<usize, CellIndex>("c", vec![2])
            .unwrap();
        comp1
            .add_attrib_data::<usize, CellVertexIndex>("cv", vec![8, 9, 10, 11])
            .unwrap();
        comp1
            .add_attrib_data::<usize, CellFaceIndex>("cf", vec![8, 9, 10, 11])
            .unwrap();
        comp1
            .add_attrib_data::<usize, VertexCellIndex>("vc", vec![0, 1, 4, 11])
            .unwrap();

        comp2
            .add_attrib_data::<usize, VertexIndex>("v", vec![2, 4, 5, 6, 7])
            .unwrap();
        comp2
            .add_attrib_data::<usize, CellIndex>("c", vec![0, 1])
            .unwrap();
        comp2
            .add_attrib_data::<usize, CellVertexIndex>("cv", vec![0, 1, 2, 3, 4, 5, 6, 7])
            .unwrap();
        comp2
            .add_attrib_data::<usize, CellFaceIndex>("cf", vec![0, 1, 2, 3, 4, 5, 6, 7])
            .unwrap();
        comp2
            .add_attrib_data::<usize, VertexCellIndex>("vc", vec![2, 3, 5, 6, 7, 8, 9, 10])
            .unwrap();
        let res = tetmesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn polymesh_split() {
        let (mesh, comp1, comp2) = build_polymesh_sample();

        // First lets verify the vertex partitioning.
        assert_eq!(mesh.connectivity(), (vec![0, 0, 0, 0, 1, 1, 1, 1], 2));

        let res = mesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }

    #[test]
    fn polymesh_split_with_attributes() {
        let mut sample = build_polymesh_sample();
        add_attribs_to_polymeshes(&mut sample);
        let (mesh, comp1, comp2) = sample;
        let res = mesh.split_into_connected_components();
        assert_eq!(res, vec![comp1, comp2]);
    }
}