polyhedron 0.1.3

use std::collections::HashSet;
use std::ops::Mul;

use crate::data_container::StorageBuffer;
use crate::prelude::{
    edge_handle::EdgeHandle,
    face_handle::FaceHandle,
    vert_handle::VertHandle,
};
use crate::{
    ArcId,
    EdgeId,
    EndpointList,
    FaceId,
    HalfEdgeId,
    MeshData,
    MeshStorage,
    TopoEdge,
    TopoFace,
    TopoHalfEdge,
    TopoVert,
    VertData,
    VertId,
};

/// Topological handle to a half edge.
pub struct HalfEdgeHandle<C: MeshStorage, const MANIFOLD: bool>
{
    pub(crate) mesh_data: *mut MeshData<C, MANIFOLD>,
    pub(crate) id: HalfEdgeId,
}

impl<C: MeshStorage, const MANIFOLD: bool> HalfEdgeHandle<C, MANIFOLD>
{
    /// Make a shallow copy of the handle.
    pub fn replicate(&self) -> Self
    {
        HalfEdgeHandle {
            mesh_data: self.mesh_data,
            id: self.id,
        }
    }

    /// Id to the handle.
    pub fn id(&self) -> HalfEdgeId { self.id }

    /// Handle to the vertex at the tail of the half edge.
    pub fn source(&self) -> VertHandle<C, MANIFOLD>
    {
        unsafe {
            let vert_id = (*self.mesh_data).half_edge_ref(self.id).source;

            VertHandle {
                mesh_data: self.mesh_data,
                id: vert_id,
            }
        }
    }

    /// Handle to the vertex at the head of the half edge.
    pub fn dest(&self) -> VertHandle<C, MANIFOLD> { self.face_next().source() }

    /// Handle to the next half edge in the face.
    pub fn face_next(&self) -> HalfEdgeHandle<C, MANIFOLD>
    {
        unsafe {
            let half_edge_id = (*self.mesh_data).half_edge_ref(self.id).face_next;

            HalfEdgeHandle {
                mesh_data: self.mesh_data,
                id: half_edge_id,
            }
        }
    }

    /// Handle to the previous half edge in the face.
    pub fn face_prev(&self) -> HalfEdgeHandle<C, MANIFOLD>
    {
        unsafe {
            let half_edge_id = (*self.mesh_data).half_edge_ref(self.id).face_prev;

            HalfEdgeHandle {
                mesh_data: self.mesh_data,
                id: half_edge_id,
            }
        }
    }

    /// Next half edge in the cycle orbitting the same edge (the twin in the
    /// manifold case).
    pub fn orbit_next(&self) -> HalfEdgeHandle<C, MANIFOLD>
    {
        unsafe {
            let half_edge_id = (*self.mesh_data).half_edge_ref(self.id).orbit_next;

            HalfEdgeHandle {
                mesh_data: self.mesh_data,
                id: half_edge_id,
            }
        }
    }

    /// Find, if present, a boundary half edge in the orbit of this edge (could
    /// be this same one).
    pub fn boundary_half_edge(&self) -> Option<HalfEdgeHandle<C, MANIFOLD>>
    {
        self.iter_orbit().find(|h| h.face().id().is_void())
    }

    /// Handle to the edge this half edge is parallel to.
    pub fn edge(&self) -> EdgeHandle<C, MANIFOLD>
    {
        assert!(!MANIFOLD);
        unsafe {
            let edge_id = (*self.mesh_data).half_edge_ref(self.id).edge;

            EdgeHandle {
                mesh_data: self.mesh_data,
                id: edge_id,
            }
        }
    }

    /// Handle to the face this half edge belongs to.
    pub fn face(&self) -> FaceHandle<C, MANIFOLD>
    {
        unsafe {
            let face_id = (*self.mesh_data).half_edge_ref(self.id).face;

            FaceHandle {
                mesh_data: self.mesh_data,
                id: face_id,
            }
        }
    }

    /// Iterator over all half edges that orbit parallel to the underlying edge.
    pub fn iter_orbit(&self) -> OrbitHalfEdgeIterator<C, MANIFOLD>
    {
        OrbitHalfEdgeIterator::new(self.replicate())
    }

    /// Iterator over all half edges that are in the same face as this half
    /// edge, in winding order.
    pub fn iter_face(&self) -> InFaceHalfEdgeIterator<C, MANIFOLD>
    {
        InFaceHalfEdgeIterator::new(self.replicate())
    }

    /// Is the underlying edge part of the boundary?
    pub fn is_in_boundary(&self) -> bool
    {
        for h in self.iter_orbit()
        {
            if h.face().id().is_void()
            {
                return true;
            }
        }
        false
    }

    /// Turn this edge handle into a unique index for the underlying edge.
    pub fn edge_index(&self) -> usize
    {
        if MANIFOLD
        {
            self.id().to_index() / 2
        }
        else
        {
            self.edge().id().to_index()
        }
    }

    /// Grab the vertex data of the two endpoints.
    pub fn vertices(&self) -> [VertData<C>; 2]
    {
        [
            self.source().read_data().clone(),
            self.face_next().source().read_data().clone(),
        ]
    }

    /// Grab the direction vector of this vertex.
    pub fn dir<S>(&self) -> VertData<C>
    where
        VertData<C>: linear_isomorphic::InnerSpace<S>,
        S: linear_isomorphic::RealField,
    {
        self.dest().read_data().clone() - self.source().read_data().clone()
    }

    /// Tests if collapsing the current edge would violate topology. If it
    /// returns true collapsing the edge is safe.
    pub fn can_collapse(&self) -> bool
    {
        let v1 = self.source();
        let v2 = self.dest();

        let v1_verts: Vec<VertId> = v1.iter_neighbours().map(|v| v.id()).collect();
        let count = v2
            .iter_neighbours()
            .filter(|v| v1_verts.contains(&v.id()))
            .count();

        if count > 2
        {
            return false;
        }

        // Imagine, for example a triangulated strip:
        // *---*
        // |\  |
        // | \ |
        // |  \|
        // *---* <---- Bad idea to collapse this edge.
        // |\  |
        // | \ |
        // |  \|
        // *---*
        // Collapsing the middle edge would create degenerate geometry.
        let both_endpoints_are_in_boundary = v1.is_in_boundary() && v2.is_in_boundary();

        self.is_in_boundary() || !both_endpoints_are_in_boundary
    }

    /// Tests if flipping the current edge would violate topology. If it returns
    /// true flipping the edge is safe.
    pub fn can_flip(&self) -> bool
    {
        let [v1, v2] = self.opposite_verts();

        let v1_set: HashSet<VertId> =
            HashSet::from_iter(v1.iter_neighbours().map(|v| v.id()));
        let v2_set: HashSet<VertId> =
            HashSet::from_iter(v2.iter_neighbours().map(|v| v.id()));

        !v1_set.contains(&v2.id()) && !v2_set.contains(&v1.id())
    }

    /// Grab the two vertices opposite to the half edge (Only use in triangle,
    /// manifold meshes).
    pub fn opposite_verts(&self) -> [VertHandle<C, MANIFOLD>; 2]
    {
        [
            self.face_prev().source(),
            self.orbit_next().face_prev().source(),
        ]
    }

    /// Topologically flip the edge.
    pub fn flip(&self)
    {
        let edge_id = if !MANIFOLD
        {
            self.edge().id()
        }
        else
        {
            EdgeId::default()
        };
        let hedge1 = self.id();
        let hedge2 = self.face_next().id();
        let hedge3 = self.face_prev().id();
        let hedge4 = self.orbit_next().id();
        let hedge5 = self.orbit_next().face_prev().id();
        let hedge6 = self.orbit_next().face_next().id();

        let vert1 = self.source().id();
        let vert2 = self.face_next().source().id();

        let trans1 = self.face_prev().source().id();
        let trans2 = self.orbit_next().face_prev().source().id();

        let face1 = self.face().id();
        let face2 = self.orbit_next().face().id();

        let vert1_safe_edge = self.source().find_distinct_edge(self.id()).unwrap().id();
        let vert2_safe_edge = self.dest().find_distinct_edge(self.id()).unwrap().id();

        let (trans1_edge, trans2_edge) = if !MANIFOLD
        {
            let trans1_edge =
                unsafe { (*self.mesh_data).vert_ref(trans1).arc.to_edge_id() };
            let trans2_edge =
                unsafe { (*self.mesh_data).vert_ref(trans2).arc.to_edge_id() };
            (trans1_edge, trans2_edge)
        }
        else
        {
            (EdgeId::default(), EdgeId::default())
        };
        if !MANIFOLD
        {
            self.edge().remove_from_cycles();
        }
        unsafe {
            (*self.mesh_data).half_edge_mut(hedge1).source = trans1;
            (*self.mesh_data).half_edge_mut(hedge4).source = trans2;
        }
        let topology_data = unsafe { &mut (*self.mesh_data).topology_data };
        crate::attach_face(topology_data, &[hedge1, hedge5, hedge2], face1);
        crate::attach_face(topology_data, &[hedge4, hedge3, hedge6], face2);
        // Store the safe edges.
        if MANIFOLD
        {
            unsafe {
                let topo_verts = &mut (*self.mesh_data).topology_data.topo_verts;
                topo_verts[vert1.to_index()].arc = ArcId::HalfEdge(vert1_safe_edge);
                topo_verts[vert2.to_index()].arc = ArcId::HalfEdge(vert2_safe_edge);
            }
        }
        else
        {
            unsafe {
                let edge1 = (*self.mesh_data).half_edge_ref(vert1_safe_edge).edge;
                let edge2 = (*self.mesh_data).half_edge_ref(vert2_safe_edge).edge;

                (*self.mesh_data).vert_mut(vert1).arc = ArcId::Edge(edge1);
                (*self.mesh_data).vert_mut(vert2).arc = ArcId::Edge(edge2);

                (*self.mesh_data).edge_mut(edge_id).endpoints = [trans1, trans2];
            }
        }
        if !MANIFOLD
        {
            unsafe {
                crate::EndpointList::join_at(
                    &mut (*self.mesh_data).topology_data.topo_edges,
                    trans1_edge,
                    edge_id,
                    trans1,
                );
                crate::EndpointList::join_at(
                    &mut (*self.mesh_data).topology_data.topo_edges,
                    trans2_edge,
                    edge_id,
                    trans2,
                );
                (*self.mesh_data).vert_mut(trans1).arc = ArcId::Edge(edge_id);
                (*self.mesh_data).vert_mut(trans2).arc = ArcId::Edge(edge_id);
            }
        }
    }

    /// Topologically split the edge. The existing edge becomes equivalent to
    /// the edge connecting [v1, vn] where vn is the new vertex created by
    /// the split.
    pub fn split<S>(self) -> VertId
    where
        VertData<C>: linear_isomorphic::InnerSpace<S>,
        S: linear_isomorphic::RealField + Mul<VertData<C>, Output = VertData<C>>,
    {
        // Get data based on the kind of topology.
        let (edge_id, edge_data) = if !MANIFOLD
        {
            let edge_data = self.edge().read_data().clone();
            (self.edge().id(), edge_data)
        }
        else
        {
            (EdgeId::default(), unsafe {
                (*self.mesh_data)
                    .geometry_data
                    .edge_data
                    .read(self.id().to_index() as u64 / 2)
                    .clone()
            })
        };

        // Add the new midpoint.
        let mid = (self.source().read_data().clone() + self.dest().read_data().clone())
            * S::from(0.5).unwrap();
        let vn = unsafe { (*self.mesh_data).add_vert(mid) };

        let v2 = self.dest().id();

        if !MANIFOLD
        {
            let vert2_safe_edge = self
                .dest()
                .find_distinct_edge(self.id())
                .map(|h| h.edge().id())
                .unwrap_or_default();

            unsafe {
                let edges = &mut (*self.mesh_data).topology_data.topo_edges;
                EndpointList::remove_edge(edges, edge_id, v2);

                (*self.mesh_data).vert_mut(vn).arc = ArcId::Edge(edge_id);
                (*self.mesh_data).vert_mut(v2).arc = ArcId::Edge(vert2_safe_edge);

                let edge = (*self.mesh_data).edge_mut(edge_id);

                if edge.endpoints[0] == v2
                {
                    edge.endpoints[0] = vn;
                }
                else
                {
                    edge.endpoints[1] = vn;
                }
            }
        }

        // Add a new edge connecting to the midpoint.
        let new_h1 = unsafe { (*self.mesh_data).add_edge(vn, v2, edge_data.clone()) };
        let new_h2 = unsafe { (*self.mesh_data).half_edge_ref(new_h1).orbit_next };

        // Set the vertex pointer at the old v2 vertex.
        unsafe {
            if MANIFOLD
            {
                (*self.mesh_data).vert_mut(v2).arc = ArcId::HalfEdge(new_h2);
            }
            else
            {
                let eid = (*self.mesh_data).half_edge_ref(new_h2).edge;
                (*self.mesh_data).vert_mut(v2).arc = ArcId::Edge(eid);
            }
        }

        let mut hedge_queue = vec![new_h2, new_h1];
        for h in self.iter_orbit()
        {
            let transversal = h.face_prev().source().id();
            let next_hedge = h.face_next().id();
            let prev_hedge = h.face_prev().id();

            // boundary half edges require different logic.
            let crossing_hedge = hedge_queue.pop().unwrap();
            let hid = h.id();
            if h.face().id().is_void()
            {
                unsafe {
                    let h1 = (*self.mesh_data).half_edge_mut(hid);
                    let h2 = (*self.mesh_data).half_edge_mut(next_hedge);
                    h1.attach_next_in_face(h2);

                    let h1 = (*self.mesh_data).half_edge_mut(prev_hedge);
                    let h2 = (*self.mesh_data).half_edge_mut(crossing_hedge);
                    h1.attach_next_in_face(h2);
                }

                continue;
            }

            let trans_hedge1 =
                unsafe { (*self.mesh_data).add_edge(vn, transversal, edge_data.clone()) };
            let trans_hedge2 =
                unsafe { (*self.mesh_data).half_edge_ref(trans_hedge1).orbit_next };

            let [cycle1, cycle2] = if h.source().id() == v2
            {
                unsafe {
                    (*self.mesh_data).half_edge_mut(h.id()).source = vn;
                }

                let f1 = [hid, next_hedge, trans_hedge2];
                let f2 = [crossing_hedge, trans_hedge1, prev_hedge];

                [f1, f2]
            }
            else
            {
                let f1 = [hid, trans_hedge1, prev_hedge];
                let f2 = [crossing_hedge, next_hedge, trans_hedge2];

                [f1, f2]
            };

            let mut face_id = FaceId::default();
            for i in 0..3
            {
                let h1 = cycle1[i];
                let h2 = cycle1[(i + 1) % 3];

                let h3 = cycle2[i];
                let h4 = cycle2[(i + 1) % 3];
                unsafe {
                    let h1 = (*self.mesh_data).half_edge_mut(h1);
                    let h2 = (*self.mesh_data).half_edge_mut(h2);
                    h1.attach_next_in_face(h2);
                    let f = if h1.face.is_void() { h2.face } else { h1.face };
                    h1.face = f;
                    h2.face = f;

                    (*self.mesh_data).face_mut(f).half_edge = h1.id;
                    face_id = f;

                    let h3 = (*self.mesh_data).half_edge_mut(h3);
                    let h4 = (*self.mesh_data).half_edge_mut(h4);
                    h3.attach_next_in_face(h4);
                    h3.face = FaceId::default();
                }
            }
            unsafe {
                let data = (*self.mesh_data)
                    .geometry_data
                    .face_data
                    .read(face_id.to_index() as u64)
                    .clone();
                (*self.mesh_data).geometry_data.face_data.append(data);

                let fid = if let Some(fid) =
                    (*self.mesh_data).topology_data.available_face_ids.pop()
                {
                    (*self.mesh_data).face_mut(fid).id = fid;
                    fid
                }
                else
                {
                    let fid =
                        FaceId::new((*self.mesh_data).topology_data.topo_faces.len());
                    (*self.mesh_data).topology_data.topo_faces.push(TopoFace {
                        id: fid,
                        ..Default::default()
                    });
                    fid
                };

                for i in 0..3
                {
                    let h = (*self.mesh_data).half_edge_mut(cycle2[i]);
                    h.face = fid;
                }

                (*self.mesh_data).face_mut(fid).half_edge = cycle2[0];
            };
        }

        vn
    }

    /// Iterate over the 6 half edges of an edge butterfly.
    pub fn iterate_butterfly(&self) -> impl Iterator<Item = HalfEdgeHandle<C, MANIFOLD>>
    {
        self.iter_face().chain(self.orbit_next().iter_face())
    }

    /// Collapse this edge and set the result to the midpoint.
    pub fn collapse_to_mid<S>(self) -> VertId
    where
        VertData<C>: linear_isomorphic::InnerSpace<S>,
        S: linear_isomorphic::RealField + Mul<VertData<C>, Output = VertData<C>>,
    {
        let mid = (self.source().read_data().clone() + self.dest().read_data().clone())
            * S::from(0.5).unwrap();

        let mesh_data = self.mesh_data;
        let vid = self.collapse();

        unsafe {
            (*mesh_data)
                .geometry_data
                .vert_data
                .update(vid.to_index() as u64, move |v| *v = mid.clone());
        }

        vid
    }

    /// Collapse this edge and set the result to one of the existing edge
    /// endpoint positions.
    pub fn collapse(self) -> VertId
    {
        let to_fix = self.iter_orbit().map(|h| h.face().id()).collect::<Vec<_>>();

        let vid = self.collapse_without_fixing();

        for f in to_fix
        {
            let f_handle = FaceHandle {
                id: f,
                mesh_data: self.mesh_data.clone(),
            };

            let hedge = f_handle
                .half_edge()
                .iter_face()
                .find(|h| h.source().id() == vid)
                .unwrap();

            let v1 = hedge.source().id();
            let v2 = hedge.dest().id();

            let to_delete = hedge.face_next();
            let pair = to_delete.orbit_next();
            let pp = pair.face_prev();
            let pn = pair.face_next();
            let face = pair.face();
            unsafe {
                let face_ref = (*self.mesh_data).face_mut(face.id());
                face_ref.half_edge = hedge.id();

                let h = (*self.mesh_data).half_edge_mut(hedge.id());
                let hp = (*self.mesh_data).half_edge_mut(pp.id());
                let hn = (*self.mesh_data).half_edge_mut(pn.id());

                h.face = face.id();
                h.attach_next_in_face(hn);
                hp.attach_next_in_face(h);

                if MANIFOLD
                {
                    (*self.mesh_data).vert_mut(h.source).arc = ArcId::HalfEdge(h.id);
                }
                else
                {
                    (*self.mesh_data).vert_mut(h.source).arc = ArcId::Edge(h.edge);
                }

                if MANIFOLD
                {
                    let safe_v1 = pair.source().find_distinct_edge(pair.id()).unwrap();
                    let safe_v2 = pair
                        .dest()
                        .find_distinct_edge(pair.orbit_next().id())
                        .unwrap();

                    (*self.mesh_data).vert_mut(v1).arc = ArcId::HalfEdge(safe_v1.id());
                    (*self.mesh_data).vert_mut(v2).arc = ArcId::HalfEdge(safe_v2.id());
                }
                else
                {
                    let safe_v1 = pair.source().find_distinct_edge(pair.id()).unwrap();
                    let safe_v2 = pair
                        .dest()
                        .find_distinct_edge(pair.orbit_next().id())
                        .unwrap();

                    (*self.mesh_data).vert_mut(v1).arc = ArcId::Edge(safe_v1.edge().id());
                    (*self.mesh_data).vert_mut(v2).arc = ArcId::Edge(safe_v2.edge().id());
                }

                if !MANIFOLD
                {
                    let eid = pair.edge().id();

                    let edges = &mut (*self.mesh_data).topology_data.topo_edges;
                    EndpointList::remove_edge(edges, eid, v1);
                    EndpointList::remove_edge(edges, eid, v2);

                    (*self.mesh_data).topology_data.available_edge_ids.push(eid);
                    (&mut (*self.mesh_data).topology_data.topo_edges)[eid.to_index()] =
                        TopoEdge::default();
                }

                (*self.mesh_data)
                    .topology_data
                    .available_half_edge_ids
                    .push(to_delete.id());
                (*self.mesh_data)
                    .topology_data
                    .available_half_edge_ids
                    .push(pair.id());
                (*self.mesh_data).topology_data.available_face_ids.push(f);

                (&mut (*self.mesh_data).topology_data.topo_half_edges)
                    [to_delete.id().to_index()] = TopoHalfEdge::default();
                (&mut (*self.mesh_data).topology_data.topo_half_edges)
                    [pair.id().to_index()] = TopoHalfEdge::default();
                (&mut (*self.mesh_data).topology_data.topo_faces)[f.to_index()] =
                    TopoFace::default();
            }
        }

        vid
    }

    /// Collapse this edge and set the result to one of the existing edge
    /// endpoint positions. Don't try to fix degenerate digons. Don't use on an
    /// edge with triangle faces unless you are certain you want that
    /// behaviour (you don't).
    pub fn collapse_without_fixing(&self) -> VertId
    {
        let edge_id = if !MANIFOLD
        {
            self.edge().id()
        }
        else
        {
            EdgeId::default()
        };

        let v1 = self.source().id();
        let v2 = self.dest().id();

        let to_update = self
            .dest()
            .iter_star_half_edges()
            .filter(|h| h.id() != self.id())
            .map(|h| h.id())
            .collect::<Vec<_>>();

        if MANIFOLD
        {
            let safe_v1 = self.source().find_distinct_edge(self.id()).unwrap();
            let safe_v2 = self
                .dest()
                .find_distinct_edge(self.orbit_next().id())
                .unwrap();
            unsafe {
                (*self.mesh_data).vert_mut(v1).arc = ArcId::HalfEdge(safe_v1.id());
                (*self.mesh_data).vert_mut(v2).arc = ArcId::HalfEdge(safe_v2.id());
            }
        }
        else
        {
            let safe_v1 = self.source().find_distinct_edge(self.id()).unwrap();
            let safe_v2 = self
                .dest()
                .find_distinct_edge(self.orbit_next().id())
                .unwrap();
            unsafe {
                (*self.mesh_data).vert_mut(v1).arc = ArcId::Edge(safe_v1.edge().id());
                (*self.mesh_data).vert_mut(v2).arc = ArcId::Edge(safe_v2.edge().id());
            }
        }

        if !MANIFOLD
        {
            unsafe {
                let safe = self
                    .source()
                    .find_distinct_edge(self.id())
                    .unwrap()
                    .edge()
                    .id();
                (*self.mesh_data).vert_mut(v1).arc = ArcId::Edge(safe);
                let edges = &mut (*self.mesh_data).topology_data.topo_edges;

                EndpointList::remove_edge(edges, edge_id, v1);
                EndpointList::remove_edge(edges, edge_id, v2);

                (*self.mesh_data)
                    .topology_data
                    .available_edge_ids
                    .push(edge_id);
                *(*self.mesh_data).edge_mut(edge_id) = TopoEdge::default();
            }
        }
        else
        {
            unsafe {
                let safe = self.source().find_distinct_edge(self.id()).unwrap().id();
                (*self.mesh_data).vert_mut(v1).arc = ArcId::HalfEdge(safe);
            }
        }

        let mut to_remove = Vec::new();
        for h in self.iter_orbit()
        {
            to_remove.push(h.id());
            let prev = h.face_prev();
            let next = h.face_next();

            if prev.source().id() == v2
            {
                unsafe {
                    (*self.mesh_data).half_edge_mut(prev.id()).source = v1;
                }
            }

            if next.source().id() == v2
            {
                unsafe {
                    (*self.mesh_data).half_edge_mut(next.id()).source = v1;
                }
            }

            unsafe {
                let h1 = (*self.mesh_data).half_edge_mut(prev.id());
                let h2 = (*self.mesh_data).half_edge_mut(next.id());

                h1.attach_next_in_face(h2);
                let fid = h1.face;
                let face = (*self.mesh_data).face_mut(fid);
                face.half_edge = h1.id;
            }
        }

        for id in to_remove
        {
            unsafe {
                (*self.mesh_data)
                    .topology_data
                    .available_half_edge_ids
                    .push(id);

                *(*self.mesh_data).half_edge_mut(id) = TopoHalfEdge::default();
            };
        }

        unsafe {
            (*self.mesh_data).topology_data.available_vert_ids.push(v2);
            *(*self.mesh_data).vert_mut(v2) = TopoVert::default();
        };

        let mut valid_updated_hedge = to_update[0];
        for hid in to_update
        {
            unsafe {
                let h = (*self.mesh_data).half_edge_mut(hid);

                if h.id.is_void()
                {
                    continue;
                }

                h.source = v1;
                valid_updated_hedge = h.id;

                let edge = (*self.mesh_data).edge_mut(h.edge);
                if edge.endpoints[0] == v2
                {
                    edge.endpoints[0] = v1;
                }
                else if edge.endpoints[1] == v2
                {
                    edge.endpoints[1] = v1;
                }
            }
        }

        if !MANIFOLD
        {
            unsafe {
                let other_edge = (*self.mesh_data).vert_ref(v1).arc.to_edge_id();
                let current_edge =
                    (*self.mesh_data).half_edge_ref(valid_updated_hedge).edge;
                let edges = &mut (*self.mesh_data).topology_data.topo_edges;
                EndpointList::join_at(edges, current_edge, other_edge, v1);
            }
        }

        v1
    }

    /// Delete this half edge and its pair without cleaning remaining
    /// non-incorrect elements.
    pub fn unclean_delete(self)
    {
        unsafe {
            let mut current_half_edge_id = self.id;
            let start_id = current_half_edge_id;
            loop
            {
                let fid = (*self.mesh_data).half_edge_ref(current_half_edge_id).face;

                if !fid.is_void()
                {
                    let f = FaceHandle {
                        mesh_data: self.mesh_data,
                        id: fid,
                    };
                    f.unclean_delete();
                }

                current_half_edge_id = (*self.mesh_data)
                    .half_edge_ref(current_half_edge_id)
                    .orbit_next;

                if current_half_edge_id == start_id
                {
                    break;
                }
            }

            let current_half_edge = (*self.mesh_data).half_edge_ref(self.id());
            let n2 = current_half_edge.face_next;
            let p1 = current_half_edge.face_prev;

            let p = current_half_edge.orbit_next;
            let pair_half_edge = (*self.mesh_data).half_edge_ref(p);

            let n1 = pair_half_edge.face_next;
            let p2 = pair_half_edge.face_prev;

            let hedge = HalfEdgeHandle {
                mesh_data: self.mesh_data,
                id: current_half_edge_id,
            };

            let safe1 = hedge
                .source()
                .find_distinct_edge(current_half_edge_id)
                .map(|h| h.id())
                .unwrap_or(HalfEdgeId::default());
            let safe2 = hedge
                .dest()
                .find_distinct_edge(p)
                .map(|h| h.id())
                .unwrap_or(HalfEdgeId::default());

            let v1 = hedge.source().id();
            let v2 = hedge.dest().id();

            if !MANIFOLD
            {
                let edge_id = current_half_edge.edge;

                let safe_hedge = hedge.orbit_next().orbit_next().id();
                let other_safe = hedge
                    .iter_orbit()
                    .last()
                    .map(|h| h.id())
                    .unwrap_or(HalfEdgeId::default());
                if other_safe.is_void()
                {
                    (*self.mesh_data).half_edge_mut(other_safe).orbit_next = other_safe;
                }
                else
                {
                    (*self.mesh_data).half_edge_mut(other_safe).orbit_next = safe_hedge;
                }

                (*self.mesh_data).edge_mut(edge_id).half_edge = safe_hedge;
            }
            else
            {
                (*self.mesh_data).vert_mut(v1).arc = ArcId::HalfEdge(safe1);
                (*self.mesh_data).vert_mut(v2).arc = ArcId::HalfEdge(safe2);
            }

            let h1 = (*self.mesh_data).half_edge_mut(p1);
            let h2 = (*self.mesh_data).half_edge_mut(n1);
            h1.attach_next_in_face(h2);

            let h1 = (*self.mesh_data).half_edge_mut(p2);
            let h2 = (*self.mesh_data).half_edge_mut(n2);
            h1.attach_next_in_face(h2);

            *(*self.mesh_data).half_edge_mut(current_half_edge_id) =
                TopoHalfEdge::default();
            *(*self.mesh_data).half_edge_mut(p) = TopoHalfEdge::default();

            (*self.mesh_data)
                .topology_data
                .available_half_edge_ids
                .push(current_half_edge_id);
            (*self.mesh_data)
                .topology_data
                .available_half_edge_ids
                .push(p);
        }
    }

    /// Delete this half edge and any remaining elements such as isolated
    /// points.
    pub fn delete(self)
    {
        let v1 = self.source().id();
        let v2 = self.dest().id();

        let edge_id = if !MANIFOLD
        {
            self.edge().id()
        }
        else
        {
            EdgeId::default()
        };

        let mesh_data = self.mesh_data;
        self.unclean_delete();

        if !edge_id.is_void() && !MANIFOLD
        {
            EdgeHandle {
                mesh_data,
                id: edge_id,
            }
            .unclean_delete();
        }

        let vert1 = VertHandle { mesh_data, id: v1 };
        let should_delete_v1 = vert1.iter_star_half_edges().count() == 0;
        if should_delete_v1
        {
            vert1.delete();
        }

        let vert2 = VertHandle { mesh_data, id: v2 };
        let should_delete_2 = vert2.iter_star_half_edges().count() == 0;
        if should_delete_2
        {
            vert2.delete();
        }
    }
}

impl<C: MeshStorage, const MANIFOLD: bool> Clone for HalfEdgeHandle<C, MANIFOLD>
{
    fn clone(&self) -> Self
    {
        Self {
            mesh_data: self.mesh_data,
            id: self.id,
        }
    }
}

/// Iterator over the orbit of an edge.
pub struct OrbitHalfEdgeIterator<C: MeshStorage, const MANIFOLD: bool>
{
    start: HalfEdgeId,
    current: HalfEdgeHandle<C, MANIFOLD>,
    finished: bool,
}

impl<C: MeshStorage, const MANIFOLD: bool> OrbitHalfEdgeIterator<C, MANIFOLD>
{
    pub(crate) fn new(edge: HalfEdgeHandle<C, MANIFOLD>) -> Self
    {
        Self {
            start: edge.id(),
            current: edge,
            finished: false,
        }
    }
}

impl<C: MeshStorage, const MANIFOLD: bool> Iterator for OrbitHalfEdgeIterator<C, MANIFOLD>
{
    type Item = HalfEdgeHandle<C, MANIFOLD>;

    fn next(&mut self) -> Option<Self::Item>
    {
        if self.finished || self.current.id().is_void()
        {
            return None;
        }

        let current_edge = self.current.replicate();

        self.current = self.current.orbit_next();

        if self.current.id() == self.start
        {
            self.finished = true;
        }

        Some(current_edge)
    }
}

/// Iterator over the edges of a face.
pub struct InFaceHalfEdgeIterator<C: MeshStorage, const MANIFOLD: bool>
{
    start: HalfEdgeId,
    current: HalfEdgeHandle<C, MANIFOLD>,
    finished: bool,
}

impl<C: MeshStorage, const MANIFOLD: bool> InFaceHalfEdgeIterator<C, MANIFOLD>
{
    pub(crate) fn new(edge: HalfEdgeHandle<C, MANIFOLD>) -> Self
    {
        Self {
            start: edge.id(),
            current: edge,
            finished: false,
        }
    }
}

impl<C: MeshStorage, const MANIFOLD: bool> Iterator
    for InFaceHalfEdgeIterator<C, MANIFOLD>
{
    type Item = HalfEdgeHandle<C, MANIFOLD>;

    fn next(&mut self) -> Option<Self::Item>
    {
        if self.finished || self.current.id().is_void()
        {
            return None;
        }

        let current_edge = self.current.replicate();

        self.current = self.current.face_next();

        if self.current.id() == self.start
        {
            self.finished = true;
        }

        Some(current_edge)
    }
}