/*!
 * 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.
/// `Src` specifies the element index for which to determine connectivity.
/// `Via` specifies a secondary element index which identifies elements through which the
/// connectivity is determined.
pub trait Connectivity<Src: ElementIndex<usize>, Via: ElementIndex<usize>> {
    /// Additional topology that may aid in computing connectivity.
    ///
    /// This is computed with `precompute_topo` and used in `push_neighbours`.
    type Topo: Default;

    /// 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_topo(&self) -> Self::Topo {
        Default::default()
    }

    /// 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`.
    /// Additionally, topology data `topo` computed using `precomute_topo` and an
    /// optional `attribute` on the target topology is provided to help determine connectivity.
    fn push_neighbours<T: Default + PartialEq>(
        &self,
        index: Src,
        stack: &mut Vec<Src>,
        topo: &Self::Topo,
        attribute: Option<&[T]>,
    );

    /// 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) {
        self.connectivity_via_attrib_fn::<(), _>(|| None)
    }

    /// 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.
    ///
    /// This is a more general version of `connectivity` that accepts an optional attribute of type
    /// `T` on the target topology to determine connectivity.
    fn connectivity_via_attrib<T>(&self, attrib: Option<&str>) -> (Vec<usize>, usize)
    where
        Self: Attrib,
        Src: AttribIndex<Self>,
        T: Default + PartialEq + 'static,
    {
        self.connectivity_via_attrib_fn::<T, _>(|| {
            attrib.and_then(|name| self.attrib_as_slice::<T, Src>(name).ok())
        })
    }

    /// 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.
    ///
    /// This is the most general version of `connectivity` that accepts a function that providees
    /// attribute data of type `T` on the target topology to determine connectivity.
    /// Note that the provided slice must have the same length as the number of `Src` indices.
    fn connectivity_via_attrib_fn<'a, T, F>(&self, f: F) -> (Vec<usize>, usize)
    where
        T: Default + PartialEq + 'a,
        F: FnOnce() -> Option<&'a [T]>,
    {
        // The ID of the current connected component.
        let mut cur_component_id = 0;

        let mut stack: Vec<Src> = 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_topo();

        let attrib_data = f();

        // 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, attrib_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<VertexIndex, CellIndex> for M {
    type Topo = ();
    fn num_elements(&self) -> usize {
        self.num_vertices()
    }

    fn push_neighbours<T: Default + PartialEq>(
        &self,
        index: VertexIndex,
        stack: &mut Vec<VertexIndex>,
        _: &(),
        _: Option<&[T]>,
    ) {
        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<VertexIndex, FaceIndex> for M {
    type Topo = (Vec<usize>, Vec<usize>);
    fn precompute_topo(&self) -> Self::Topo {
        self.reverse_topo()
    }
    fn num_elements(&self) -> usize {
        self.num_vertices()
    }

    fn push_neighbours<T: Default + PartialEq>(
        &self,
        index: VertexIndex,
        stack: &mut Vec<VertexIndex>,
        topo: &Self::Topo,
        _: Option<&[T]>,
    ) {
        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);
                }
            }
        }
    }
}

/// Implement face vertex connectivity for face based meshes (e.g. PolyMesh, TriMesh and QuadMesh).
///
/// This can be useful for splitting meshes based on texture coordinates, so that they can be
/// exported in formats that don't support additional face-vertex topologies like glTF.
impl<M: FaceVertex + NumFaces + NumVertices> Connectivity<FaceVertexIndex, VertexIndex> for M {
    type Topo = (Vec<usize>, Vec<usize>);
    fn precompute_topo(&self) -> Self::Topo {
        self.reverse_source_topo() // vertex -> (face->vertex) topo
    }

    fn num_elements(&self) -> usize {
        self.num_face_vertices()
    }

    fn push_neighbours<T: Default + PartialEq>(
        &self,
        index: FaceVertexIndex,
        stack: &mut Vec<FaceVertexIndex>,
        topo: &Self::Topo,
        attrib: Option<&[T]>,
    ) {
        // For each vertex, topo contains a set of face-vertex indices.
        let (fv_indices, fv_offsets) = topo;

        let vtx_idx = usize::from(self.vertex(index));

        // Push all neighbours of a face-vertex based on the value of the given attribute.
        let idx = usize::from(index);

        // Attribute value of the primary face-vertex given by `index`.
        let def_val = T::default();
        let primary_attrib_val = attrib.map(|a| &a[idx]).unwrap_or_else(|| &def_val);

        for face_vertex in (fv_offsets[vtx_idx]..fv_offsets[vtx_idx + 1]).map(|i| fv_indices[i]) {
            let neigh_attrib_val = attrib.map(|a| &a[face_vertex]).unwrap_or_else(|| &def_val);
            if primary_attrib_val == neigh_attrib_val {
                stack.push(face_vertex.into());
            }
        }
    }
}

// Implement default connectivity shorthands on meshes to avoid having to specify index types for
// the Connectivity trait.

impl<T: Real> TriMesh<T> {
    pub fn vertex_connectivity(&self) -> (Vec<usize>, usize) {
        Connectivity::<VertexIndex, FaceIndex>::connectivity(self)
    }
}

impl<T: Real> PolyMesh<T> {
    pub fn vertex_connectivity(&self) -> (Vec<usize>, usize) {
        Connectivity::<VertexIndex, FaceIndex>::connectivity(self)
    }
}

impl<T: Real> TetMeshExt<T> {
    pub fn vertex_connectivity(&self) -> (Vec<usize>, usize) {
        Connectivity::<VertexIndex, CellIndex>::connectivity(self)
    }
}

/// Helper to split attributes based on the given connectivity info.
fn split_attributes<A: Clone, I: Into<Option<usize>>>(
    src_dict: &AttribDict<A>,
    num_components: usize,
    connectivity: impl Iterator<Item = I> + Clone,
) -> Vec<AttribDict<A>> {
    split_attributes_with(src_dict, num_components, |new_attribs, attrib| {
        // Get an iterator of typeless byte chunks for this attribute.
        let attrib_chunks = attrib.buffer_ref().byte_chunks();

        for (comp_id, bytes) in connectivity.clone().zip(attrib_chunks) {
            if let Some(valid_idx) = comp_id.into() {
                // Add bytes for this element to the appropriate component data.
                // This is safe since data_bufs was created with the same type as the attrib buf.
                unsafe {
                    new_attribs[valid_idx].buffer_mut().push_bytes(bytes);
                }
            }
        }
    })
}

/// Helper to split attributes using a given closure to transfer data from each source attribute to
/// the destination collection of individual empty component attributes.
///
/// It is safe to transfer data between attributes in the `transfer_data` function.
fn split_attributes_with<A: Clone>(
    src_dict: &AttribDict<A>,
    num_components: usize,
    mut transfer_data: impl FnMut(&mut [Attribute<A>], &Attribute<A>),
) -> Vec<AttribDict<A>> {
    let mut comp_attributes = vec![AttribDict::new(); num_components];
    for (name, attrib) in src_dict.iter() {
        // Create a new empty attributes with the same type as attrib.
        let mut new_attribs = vec![attrib.duplicate_empty(); num_components];

        transfer_data(&mut new_attribs, &attrib);

        // Save the new attributes to their corresponding attribute dictionaries.
        for (attrib_dict, new_attrib) in comp_attributes.iter_mut().zip(new_attribs.into_iter()) {
            attrib_dict.insert(name.to_string(), new_attrib);
        }
    }
    comp_attributes
}

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

pub trait SplitIntoConnectedComponents<Src, Via>
where
    Src: ElementIndex<usize>,
    Via: ElementIndex<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<VertexIndex, CellIndex> 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<VertexIndex, CellIndex> 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 comp_vertex_cell_attributes = split_attributes_with(
            &vertex_cell_attributes,
            num_components,
            |new_attribs, attrib| {
                // 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() {
                        // This is safe because new_attribs were created with the same element type as
                        // `attrib`.
                        unsafe {
                            new_attribs[comp_id].buffer_mut().push_bytes(bytes);
                        }
                    }
                }
            },
        );

        // Transfer vertex attributes
        let comp_vertex_attributes = split_attributes(
            &vertex_attributes,
            num_components,
            vertex_connectivity.iter().cloned(),
        );

        // Transfer cell attributes
        let comp_cell_attributes = split_attributes(
            &cell_attributes,
            num_components,
            cell_connectivity.iter().cloned(),
        );

        // Transfer cell vertex attributes
        let comp_cell_vertex_attributes = split_attributes(
            &cell_vertex_attributes,
            num_components,
            cell_connectivity
                .iter()
                .flat_map(|c| std::iter::repeat(c).take(4).cloned()),
        );

        // Transfer cell face attributes
        let comp_cell_face_attributes = split_attributes(
            &cell_face_attributes,
            num_components,
            cell_connectivity
                .iter()
                .flat_map(|c| std::iter::repeat(c).take(4).cloned()),
        );

        // 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<VertexIndex, FaceIndex> for PolyMesh<T> {
    fn split_into_connected_components(self) -> Vec<Self> {
        // First we partition the vertices.
        let (vertex_connectivity, num_components) =
            Connectivity::<VertexIndex, FaceIndex>::connectivity(&self);

        // 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 comp_vertex_attributes = split_attributes(
            &self.vertex_attributes,
            num_components,
            vertex_connectivity.iter().cloned(),
        );

        // Transfer face attributes
        let comp_face_attributes = split_attributes(
            &self.face_attributes,
            num_components,
            face_connectivity.iter().cloned(),
        );

        // Transfer face vertex attributes
        let comp_face_vertex_attributes = split_attributes(
            &self.face_vertex_attributes,
            num_components,
            face_connectivity.iter().enumerate().flat_map(|(fi, c)| {
                std::iter::repeat(c)
                    .take(self.num_vertices_at_face(fi))
                    .cloned()
            }),
        );

        // Transfer face edge attributes
        let comp_face_edge_attributes = split_attributes(
            &self.face_edge_attributes,
            num_components,
            face_connectivity.iter().enumerate().flat_map(|(fi, c)| {
                std::iter::repeat(c)
                    .take(self.num_edges_at_face(fi))
                    .cloned()
            }),
        );

        // 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()
    }
}

// TODO: Generalize split_vertices_by_attrib between the meshes.
//       This will involve converging on how to represent/access indices for rewiring meshes
//       through a trait.

impl<T: Real> TriMesh<T> {
    /// Split vertices by a given face-vertex attribute.
    ///
    /// If a pair of face-vertices have different values for the same vertex, then they will be
    /// split into distinct vertices. New vertex positions are appended at the end of the vertex
    /// position array.
    ///
    /// If the given attribute doesn't exist, then nothing is changed.
    pub fn split_vertices_by_attrib(&mut self, attrib: &str) {
        // For each vertex, topo contains a set of face-vertex indices.
        let (fv_indices, fv_offsets) = self.reverse_source_topo();

        // This function doesn't affect the number of faces or face-vertex topology.
        let TriMesh {
            vertex_positions,
            indices,
            vertex_attributes,
            face_vertex_attributes,
            // Other attributes remain unchanged.
            ..
        } = self;

        if let Some(attrib) = face_vertex_attributes.get(attrib) {
            let element_size = attrib.buffer_ref().element_size();
            let attrib_bytes = attrib.buffer_ref().as_bytes();

            // The partitioning of unique values in the neighbourhood of one vertex.
            let mut local_partition = Vec::new();

            // Remember which vertices were newly created so we can transfer vertex attributes.
            let mut new_vertices = Vec::new();

            for vtx_idx in 0..vertex_positions.len() {
                local_partition.clear();
                for face_vertex in
                    (fv_offsets[vtx_idx]..fv_offsets[vtx_idx + 1]).map(|i| fv_indices[i])
                {
                    local_partition.push((
                        face_vertex,
                        &attrib_bytes[element_size * face_vertex..element_size * (face_vertex + 1)],
                    ));
                }
                local_partition.sort_by_key(|a| a.1);
                let mut partition_iter = local_partition.iter();
                if let Some(mut prev) = partition_iter.next() {
                    // First element will have a unique vertex by definition.
                    while let Some(next) = partition_iter.next() {
                        if next.1 != prev.1 {
                            // Found a different face-vertex attribute. Split the vertex.
                            // Rewire appropriate vertex index to the new vertex.
                            let pos = vertex_positions[vtx_idx];
                            indices[next.0 / 3][next.0 % 3] = vertex_positions.len();
                            vertex_positions.as_mut_vec().push(pos);
                            new_vertices.push(vtx_idx);
                            prev = next;
                        } else {
                            // Same bucket but new vertices may have been created, so we must still
                            // rewire to the last newly created vertex.
                            indices[next.0 / 3][next.0 % 3] = indices[prev.0 / 3][prev.0 % 3];
                        }
                    }
                }
            }

            // Duplicate vertex attributes for newly created vertices.
            for (_, attrib) in vertex_attributes.iter_mut() {
                let element_size = attrib.buffer_ref().element_size();
                let num_bytes = attrib.buffer_ref().as_bytes().len();
                attrib.extend_by(new_vertices.len());

                // Split the extended attribute into original byte slice and and newly extended
                // uninitialized slice.
                let (old, new) =
                    unsafe { attrib.buffer_mut().as_bytes_mut().split_at_mut(num_bytes) };

                for (i, &vtx_idx) in new_vertices.iter().enumerate() {
                    // Initialize the extended part.
                    let bytes = &old[vtx_idx * element_size..(vtx_idx + 1) * element_size];
                    new[i * element_size..(i + 1) * element_size].copy_from_slice(bytes);
                }
            }
        }
    }
}

impl<T: Real> PolyMesh<T> {
    /// Split vertices by a given face-vertex attribute.
    ///
    /// If a pair of face-vertices have different values for the same vertex, then they will be
    /// split into distinct vertices. New vertex positions are appended at the end of the vertex
    /// position array.
    ///
    /// If the given attribute doesn't exist, then nothing is changed.
    pub fn split_vertices_by_attrib<U: PartialOrd + PartialEq + Copy + 'static>(
        &mut self,
        attrib: &str,
    ) {
        // For each vertex, topo contains a set of face-vertex indices.
        let (fv_indices, fv_offsets) = self.reverse_source_topo();

        // This function doesn't affect the number of faces or face-vertex topology.
        let PolyMesh {
            vertex_positions,
            indices,
            vertex_attributes,
            face_vertex_attributes,
            // Other attributes remain unchanged.
            ..
        } = self;

        if let Some(attrib) = face_vertex_attributes
            .get(attrib)
            .and_then(|a| a.as_slice::<U>().ok())
        {
            // The partitioning of unique values in the neighbourhood of one vertex.
            let mut local_partition = Vec::new();

            // Remember which vertices were newly created so we can transfer vertex attributes.
            let mut new_vertices = Vec::new();

            for vtx_idx in 0..vertex_positions.len() {
                local_partition.clear();
                for face_vertex in
                    (fv_offsets[vtx_idx]..fv_offsets[vtx_idx + 1]).map(|i| fv_indices[i])
                {
                    local_partition.push((face_vertex, &attrib[face_vertex]));
                }
                local_partition
                    .sort_by(|a, b| a.1.partial_cmp(b.1).unwrap_or(std::cmp::Ordering::Less));
                let mut partition_iter = local_partition.iter();
                if let Some(mut prev) = partition_iter.next() {
                    // First element will have a unique vertex by definition.
                    while let Some(next) = partition_iter.next() {
                        if next.1 != prev.1 {
                            // Found a different face-vertex attribute. Split the vertex.
                            // Rewire appropriate vertex index to the new vertex.
                            let pos = vertex_positions[vtx_idx];
                            indices[next.0] = vertex_positions.len();
                            vertex_positions.as_mut_vec().push(pos);
                            new_vertices.push(vtx_idx);
                            prev = next;
                        } else {
                            // Same bucket but new vertices may have been created, so we must still
                            // rewire to the last newly created vertex.
                            indices[next.0] = indices[prev.0];
                        }
                    }
                }
            }

            // Duplicate vertex attributes for newly created vertices.
            for (_, attrib) in vertex_attributes.iter_mut() {
                let element_size = attrib.buffer_ref().element_size();
                let num_bytes = attrib.buffer_ref().as_bytes().len();
                attrib.extend_by(new_vertices.len());

                // Split the extended attribute into original byte slice and and newly extended
                // uninitialized slice.
                let (old, new) =
                    unsafe { attrib.buffer_mut().as_bytes_mut().split_at_mut(num_bytes) };

                for (i, &vtx_idx) in new_vertices.iter().enumerate() {
                    // Initialize the extended part.
                    let bytes = &old[vtx_idx * element_size..(vtx_idx + 1) * element_size];
                    new[i * element_size..(i + 1) * element_size].copy_from_slice(bytes);
                }
            }
        }
    }
}

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

        // 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_vertex_indices = vec![Vec::new(); 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 = [
                    new_vertex_indices[face[0]],
                    new_vertex_indices[face[1]],
                    new_vertex_indices[face[2]],
                ];
                comp_vertex_indices[comp_id].push(new_face);
                *face_comp_id = Index::from(comp_id);
            }
        }

        // Transfer vertex attributes
        let comp_vertex_attributes = split_attributes(
            &self.vertex_attributes,
            num_components,
            vertex_connectivity.iter().cloned(),
        );

        // Transfer face attributes
        let comp_face_attributes = split_attributes(
            &self.face_attributes,
            num_components,
            face_connectivity.iter().cloned(),
        );

        // Transfer face vertex attributes
        let comp_face_vertex_attributes = split_attributes(
            &self.face_vertex_attributes,
            num_components,
            face_connectivity
                .iter()
                .flat_map(|f| std::iter::repeat(f).take(3).cloned()),
        );

        // Transfer face edge attributes
        let comp_face_edge_attributes = split_attributes(
            &self.face_edge_attributes,
            num_components,
            face_connectivity
                .iter()
                .flat_map(|f| std::iter::repeat(f).take(3).cloned()),
        );

        // Generate a Vec of meshes.
        comp_vertex_positions
            .into_iter()
            .zip(comp_vertex_indices.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), va), fa), fva), fea)| TriMesh {
                vertex_positions: vp.into(),
                indices: i.into(),
                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.vertex_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.vertex_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]);
    }

    #[test]
    fn polymesh_split_vertices_by_attrib() {
        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],
        ];

        // Two triangles connected at an edge, a quad, and two triangles connecting these
        // inbetweeen.
        let indices = vec![
            3, 0, 1, 2, 3, 2, 1, 3, 4, 4, 5, 7, 6, 3, 0, 1, 4, 3, 1, 5, 4,
        ];

        let mut polymesh = PolyMesh::new(verts, &indices);

        // Add an arbitrary vertex attribute
        polymesh
            .add_attrib_data::<usize, VertexIndex>("v", (0..polymesh.num_vertices()).collect())
            .unwrap();

        polymesh
            .add_attrib_data::<usize, FaceVertexIndex>(
                "no_split",
                vec![0, 1, 2, 2, 1, 3, 4, 5, 7, 6, 0, 1, 4, 1, 5, 4],
            )
            .unwrap();

        let mut no_split = polymesh.clone();
        no_split.split_vertices_by_attrib::<usize>("no_split");
        assert_eq!(no_split, polymesh);

        polymesh
            .add_attrib_data::<i32, FaceVertexIndex>(
                "vertex1_split",
                vec![0, 10, 2, 2, 11, 3, 4, 5, 7, 6, 0, 12, 4, 13, 5, 4],
            )
            .unwrap();

        let mut vertex1_split = polymesh.clone();
        vertex1_split.split_vertices_by_attrib::<i32>("vertex1_split");
        assert_eq!(vertex1_split.num_vertices(), polymesh.num_vertices() + 3);
        assert_eq!(
            vertex1_split.num_face_vertices(),
            polymesh.num_face_vertices()
        );
        assert_eq!(
            vertex1_split.attrib::<FaceVertexIndex>("vertex1_split"),
            polymesh.attrib::<FaceVertexIndex>("vertex1_split")
        );
        assert_eq!(
            vertex1_split.attrib_as_slice::<usize, VertexIndex>("v"),
            Ok(&[0, 1, 2, 3, 4, 5, 6, 7, 1, 1, 1][..])
        );

        polymesh
            .add_attrib_data::<usize, FaceVertexIndex>(
                "full_split",
                (0..polymesh.num_face_vertices()).collect(),
            )
            .unwrap();

        let mut full_split = polymesh.clone();
        full_split.split_vertices_by_attrib::<usize>("full_split");
        assert_eq!(full_split.num_vertices(), polymesh.num_face_vertices());
        assert_eq!(full_split.num_face_vertices(), polymesh.num_face_vertices());
        assert_eq!(
            full_split.attrib_as_slice::<usize, VertexIndex>("v"),
            Ok(&[0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 1, 1, 2, 4, 4, 5][..])
        );
    }

    #[test]
    fn trimesh_split_vertices_by_attrib() {
        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],
        ];

        let indices = vec![0, 1, 2, 2, 1, 3, 4, 5, 6, 6, 5, 7, 0, 1, 4, 1, 5, 4];

        let mut mesh = TriMesh::new(verts, indices);

        // Add an arbitrary vertex attribute
        mesh.add_attrib_data::<usize, VertexIndex>("v", (0..mesh.num_vertices()).collect())
            .unwrap();

        mesh.add_attrib_data::<usize, FaceVertexIndex>(
            "no_split",
            vec![0, 1, 2, 2, 1, 3, 4, 5, 6, 6, 5, 7, 0, 1, 4, 1, 5, 4],
        )
        .unwrap();

        let mut no_split = mesh.clone();
        no_split.split_vertices_by_attrib("no_split");
        assert_eq!(no_split, mesh);

        mesh.add_attrib_data::<f32, FaceVertexIndex>(
            "vertex1_split",
            vec![
                0.0f32,
                10.0 / 3.0,
                2.0,
                2.0,
                11.0,
                3.0,
                4.0,
                5.0,
                6.0 / 4.0,
                6.0 / 4.0,
                5.0,
                7.0,
                0.0,
                12.0,
                4.0,
                13.0,
                5.0,
                4.0,
            ],
        )
        .unwrap();

        let mut vertex1_split = mesh.clone();
        vertex1_split.split_vertices_by_attrib("vertex1_split");
        assert_eq!(vertex1_split.num_vertices(), mesh.num_vertices() + 3);
        assert_eq!(vertex1_split.num_face_vertices(), mesh.num_face_vertices());
        assert_eq!(
            vertex1_split.attrib::<FaceVertexIndex>("vertex1_split"),
            mesh.attrib::<FaceVertexIndex>("vertex1_split")
        );
        assert_eq!(
            vertex1_split.attrib_as_slice::<usize, VertexIndex>("v"),
            Ok(&[0, 1, 2, 3, 4, 5, 6, 7, 1, 1, 1][..])
        );

        mesh.add_attrib_data::<usize, FaceVertexIndex>(
            "full_split",
            (0..mesh.num_face_vertices()).collect(),
        )
        .unwrap();

        let mut full_split = mesh.clone();
        full_split.split_vertices_by_attrib("full_split");
        assert_eq!(full_split.num_vertices(), mesh.num_face_vertices());
        assert_eq!(full_split.num_face_vertices(), mesh.num_face_vertices());
        assert_eq!(
            full_split.attrib_as_slice::<usize, VertexIndex>("v"),
            Ok(&[0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 1, 1, 2, 4, 4, 5, 5, 6][..])
        );
    }

    /// This is a more complex regression test for splitting vertices.
    #[test]
    fn trimesh_split_vertices_by_attrib_and_promote_complex() {
        let verts = vec![
            [-0.520833, -0.5, 0.5],
            [-0.520833, 0.5, 0.5],
            [-0.520833, -0.5, -0.5],
            [-0.520833, 0.5, -0.5],
            [0.520833, -0.5, 0.5],
            [0.520833, 0.5, 0.5],
            [0.520833, -0.5, -0.5],
            [0.520833, 0.5, -0.5],
        ];

        let indices = vec![
            0, 1, 3, 4, 5, 7, 6, 7, 2, 5, 4, 1, 5, 0, 2, 1, 4, 6, 6, 3, 1, 2, 7, 5, 1, 0, 5, 2, 3,
            6, 7, 6, 4, 3, 2, 0,
        ];

        let mut mesh = TriMesh::new(verts, indices);

        // We split the vertices according to the following attribute and then test that
        // there are no more collisions.
        // This tests both functions: split_vertices_by_attrib and attrib_promote.

        mesh.add_attrib_data::<[f32; 2], FaceVertexIndex>(
            "uv",
            vec![
                [0.630043, 0.00107052],
                [0.370129, 0.00107052],
                [0.370129, 0.250588],
                [0.370129, 0.749623],
                [0.630043, 0.749623],
                [0.630043, 0.500105],
                [0.370129, 0.500105],
                [0.630043, 0.500105],
                [0.630043, 0.250588],
                [0.630043, 0.749623],
                [0.370129, 0.749623],
                [0.370129, 0.99914],
                [0.879561, 0.500105],
                [0.879561, 0.250588],
                [0.630043, 0.250588],
                [0.120612, 0.250588],
                [0.120612, 0.500105],
                [0.370129, 0.500105],
                [0.370129, 0.500105],
                [0.370129, 0.250588],
                [0.120612, 0.250588],
                [0.630043, 0.250588],
                [0.630043, 0.500105],
                [0.879561, 0.500105],
                [0.370129, 0.99914],
                [0.630043, 0.99914],
                [0.630043, 0.749623],
                [0.630043, 0.250588],
                [0.370129, 0.250588],
                [0.370129, 0.500105],
                [0.630043, 0.500105],
                [0.370129, 0.500105],
                [0.370129, 0.749623],
                [0.370129, 0.250588],
                [0.630043, 0.250588],
                [0.630043, 0.00107052],
            ],
        )
        .unwrap();

        mesh.split_vertices_by_attrib("uv");

        mesh.attrib_promote::<[f32; 2], _>("uv", |a, b| assert_eq!(a, b)).unwrap();
    }

    /// The same test for polymeshes.
    #[test]
    fn polymesh_split_vertices_by_attrib_and_promote_complex() {
        let verts = vec![
            [-0.520833, -0.5, 0.5],
            [-0.520833, 0.5, 0.5],
            [-0.520833, -0.5, -0.5],
            [-0.520833, 0.5, -0.5],
            [0.520833, -0.5, 0.5],
            [0.520833, 0.5, 0.5],
            [0.520833, -0.5, -0.5],
            [0.520833, 0.5, -0.5],
        ];

        let indices = vec![
            0, 1, 3, 2, 4, 5, 7, 6, 6, 7, 2, 3, 5, 4, 1, 0, 5, 0, 2, 7, 1, 4, 6, 3,
        ];

        let mut mesh = TriMesh::new(verts, indices);

        // We split the vertices according to the following attribute and then test that
        // there are no more collisions.
        // This tests both functions: split_vertices_by_attrib and attrib_promote.

        mesh.add_attrib_data::<[f32; 2], FaceVertexIndex>(
            "uv",
            vec![
                [0.630043, 0.00107052],
                [0.370129, 0.00107052],
                [0.370129, 0.250588],
                [0.630043, 0.250588],
                [0.370129, 0.749623],
                [0.630043, 0.749623],
                [0.630043, 0.500105],
                [0.370129, 0.500105],
                [0.370129, 0.500105],
                [0.630043, 0.500105],
                [0.630043, 0.250588],
                [0.370129, 0.250588],
                [0.630043, 0.749623],
                [0.370129, 0.749623],
                [0.370129, 0.99914],
                [0.630043, 0.99914],
                [0.879561, 0.500105],
                [0.879561, 0.250588],
                [0.630043, 0.250588],
                [0.630043, 0.500105],
                [0.120612, 0.250588],
                [0.120612, 0.500105],
                [0.370129, 0.500105],
                [0.370129, 0.250588],
            ],
        )
        .unwrap();

        mesh.split_vertices_by_attrib("uv");

        mesh.attrib_promote::<[f32; 2], _>("uv", |a, b| assert_eq!(a, b))
            .unwrap();
    }
}