3 files changed, 317 insertions, 54 deletions

diff --git a/src/main.rs b/src/main.rs
index a1f968b..ba345f8 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -39,6 +39,9 @@ pub use mevvlfs::*;
 mod mekh;
 pub use mekh::*;
 
+mod msev;
+pub use msev::*;
+
 pub trait ReflAsRef<T> {
     fn as_ref(&self) -> &T;
 }
@@ -919,7 +922,7 @@ impl<'brand, 'arena, V> Dcel<'brand, 'arena, V> {
         let [v1, v2] = old_edge.vertices(self);
 
         let mut a3 = a1.next(self);
-        let mut b3 = b2.prev(self);
+        let mut b3 = b1.prev(self);
 
         if a3.eq(b1, self) {
             a3 = b2;
@@ -937,6 +940,9 @@ impl<'brand, 'arena, V> Dcel<'brand, 'arena, V> {
         self.follow(b3, b2);
         self.follow(b2, b1);
 
+        a2.set_loop_(a1.loop_(self), self);
+        b2.set_loop_(b1.loop_(self), self);
+
         Mve {
             shell,
             old_edge,
@@ -966,44 +972,26 @@ impl<'brand, 'arena, V> Dcel<'brand, 'arena, V> {
         Kemh::new(shell, edge, loop_, hole_vertex).apply(self)
     }
 
-    /* pub fn mekh(
+    pub fn msev(
         &mut self,
-    ) -> Result<Mekh<'arena, 'brand, V>, MekhError> {
-        let face = loops[0].0.face(self);
-        assert!(loops[1].0.lens(self).face().eq(face));
-
-        let outer = loops.map(|(l, _)| face.lens(self).outer_loop().eq(l));
-        if outer[0] && outer[1] {
-            panic!("cannot connect outer loops");
-        }
-        if outer[1] {
-            loops = [loops[1], loops[0]];
-        }
-
-        let [b0, a2] = loops.map(|(l, v)| v.find_outgoing(l, self).unwrap());
-
-        let (edge, [a1, b1]) = self.new_edge(shell);
-
-        let a0 = b0.prev(self);
-        let b2 = a2.prev(self);
-
-        self.origin(loops[0].1, a1);
-        self.follow(a0, a1);
-        self.follow(a1, a2);
-
-        self.origin(loops[1].1, b1);
-        self.follow(b2, b1);
-        self.follow(b1, b0);
-
-        loops[0]
-            .0
-            .iter_mut_half_edges(self, |x, dcel| x.set_loop_(loops[0].0, dcel));
-
-        face.remove_inner_loop(loops[1].0, self);
-        from_loop.free(self);
+        shell: ptr!(Shell),
+        vertex: ptr!(Vertex),
+        loops: [ptr!(Loop); 2],
+        data: V,
+    ) -> Result<Ksev<'brand, 'arena, V>, OperatorErr<Msev<'brand, 'arena, V>, MsevError>> {
+        Msev::new(shell, vertex, loops, data).apply(self)
+    }
 
-        Ok(Mekh { shell })
-    } */
+    pub fn ksev(
+        &mut self,
+        shell: ptr!(Shell),
+        loops: [ptr!(Loop); 2],
+        old_vertex: ptr!(Vertex),
+        new_vertex: own!(Vertex),
+        edge: own!(Edge),
+    ) -> Result<Msev<'brand, 'arena, V>, OperatorErr<Ksev<'brand, 'arena, V>, KsevError>> {
+        Ksev::new(shell, loops, old_vertex, new_vertex, edge).apply(self)
+    }
 }
 
 use std::io::Write;
diff --git a/src/msev.rs b/src/msev.rs
new file mode 100644
index 0000000..9abc5a4
--- /dev/null
+++ b/src/msev.rs
@@ -0,0 +1,186 @@
+// Make Split Edge Vertex
+
+use crate::*;
+
+pub struct Msev<'brand, 'arena, V> {
+    pub shell: ptr!(Shell),
+    pub vertex: ptr!(Vertex),
+    pub loops: [ptr!(Loop); 2],
+    pub data: V,
+}
+
+impl<'brand, 'arena, V> Msev<'brand, 'arena, V> {
+    pub fn new(shell: ptr!(Shell), vertex: ptr!(Vertex), loops: [ptr!(Loop); 2], data: V) -> Self {
+        Self {
+            shell,
+            vertex,
+            loops,
+            data,
+        }
+    }
+}
+
+#[derive(Debug, Error)]
+pub enum MsevError {
+    #[error("vertex is not part of loop")]
+    VertexLoopMismatch,
+}
+
+impl<'brand, 'arena, V> Operator<'brand, 'arena, V> for Msev<'brand, 'arena, V> {
+    type Inverse = Ksev<'brand, 'arena, V>;
+    type Error = MsevError;
+    type Check = [ptr!(HalfEdge); 2];
+
+    fn check(&self, dcel: &Dcel<'brand, 'arena, V>) -> Result<Self::Check, Self::Error> {
+        use MsevError::*;
+
+        let a = self
+            .vertex
+            .find_outgoing(self.loops[0], dcel)
+            .ok_or(VertexLoopMismatch)?;
+        let b = self
+            .vertex
+            .find_outgoing(self.loops[1], dcel)
+            .ok_or(VertexLoopMismatch)?;
+
+        Ok([a, b])
+    }
+
+    fn apply(
+        self,
+        dcel: &mut Dcel<'brand, 'arena, V>,
+    ) -> Result<Self::Inverse, OperatorErr<Self, Self::Error>> {
+        let [a2, b0] = try_check!(self, dcel);
+        let a0 = a2.prev(dcel);
+        let b2 = b0.prev(dcel);
+
+        let (edge, [a1, b1]) = Edge::create(self.shell, dcel);
+        let v = self.shell.add_new_vertex(self.data, dcel);
+
+        a1.update_origin(self.vertex, dcel);
+        b2.twin(dcel).update_origin(*v, dcel);
+        b1.update_origin(*v, dcel);
+        a2.update_origin(*v, dcel);
+
+        dcel.follow(a0, a1);
+        dcel.follow(a1, a2);
+
+        dcel.follow(b2, b1);
+        dcel.follow(b1, b0);
+
+        a1.set_loop_(self.loops[0], dcel);
+        b1.set_loop_(self.loops[1], dcel);
+
+        Ok(Ksev {
+            shell: self.shell,
+            loops: self.loops,
+            old_vertex: self.vertex,
+            new_vertex: v,
+            edge,
+        })
+    }
+}
+
+pub struct Ksev<'brand, 'arena, V> {
+    pub shell: ptr!(Shell),
+    pub loops: [ptr!(Loop); 2],
+    pub old_vertex: ptr!(Vertex),
+    pub new_vertex: own!(Vertex),
+    pub edge: own!(Edge),
+}
+
+impl<'brand, 'arena, V> Ksev<'brand, 'arena, V> {
+    pub fn new(
+        shell: ptr!(Shell),
+        loops: [ptr!(Loop); 2],
+        old_vertex: ptr!(Vertex),
+        new_vertex: own!(Vertex),
+        edge: own!(Edge),
+    ) -> Self {
+        Self {
+            shell,
+            loops,
+            old_vertex,
+            new_vertex,
+            edge,
+        }
+    }
+}
+
+#[derive(Debug, Error)]
+pub enum KsevError {
+    #[error("edge does not match vertices")]
+    EdgeVertexMismatch,
+    #[error("edge does not match loops")]
+    EdgeLoopMismatch,
+}
+
+impl<'brand, 'arena, V> Operator<'brand, 'arena, V> for Ksev<'brand, 'arena, V> {
+    type Inverse = Msev<'brand, 'arena, V>;
+    type Error = KsevError;
+    type Check = [ptr!(HalfEdge); 2];
+
+    fn check(&self, dcel: &Dcel<'brand, 'arena, V>) -> Result<Self::Check, Self::Error> {
+        use KsevError::*;
+
+        let [mut a, mut b] = self.edge.lens(dcel).half_edges();
+        if a.origin().eq(*self.new_vertex) {
+            [a, b] = [b, a];
+        }
+
+        or_err(
+            a.origin().eq(self.old_vertex) && b.origin().eq(*self.new_vertex),
+            EdgeVertexMismatch,
+        )?;
+
+        or_err(
+            (a.loop_().eq(self.loops[0]) && b.loop_().eq(self.loops[1]))
+                || (a.loop_().eq(self.loops[1]) && b.loop_().eq(self.loops[0])),
+            EdgeLoopMismatch,
+        )?;
+
+        Ok([a.item, b.item])
+    }
+
+    fn apply(
+        self,
+        dcel: &mut Dcel<'brand, 'arena, V>,
+    ) -> Result<Self::Inverse, OperatorErr<Self, Self::Error>> {
+        let [a1, b1] = try_check!(self, dcel);
+
+        let Ksev {
+            shell,
+            old_vertex,
+            new_vertex,
+            edge,
+            ..
+        } = self;
+
+        let loops = [a1.loop_(dcel), b1.loop_(dcel)];
+
+        let a0 = a1.prev(dcel);
+        let a2 = a1.next(dcel);
+
+        let b0 = b1.next(dcel);
+        let b2 = b1.prev(dcel);
+
+        dcel.follow(a0, a2);
+        dcel.follow(b2, b0);
+
+        a2.update_origin(old_vertex, dcel);
+        b2.twin(dcel).update_origin(old_vertex, dcel);
+
+        loops[0].set_half_edges(a0, dcel);
+        loops[1].set_half_edges(b0, dcel);
+
+        edge.destroy(dcel);
+        let data = new_vertex.destroy(dcel);
+
+        Ok(Msev {
+            shell,
+            vertex: old_vertex,
+            loops,
+            data,
+        })
+    }
+}
diff --git a/src/tests.rs b/src/tests.rs
index 5132223..a1ad5a4 100644
--- a/src/tests.rs
+++ b/src/tests.rs
@@ -85,16 +85,9 @@ fn kemh_mekh() {
 
         let mut kemh = Kemh::new(*shell, edge, *outer_loop, *inner_0);
 
-        for i in 0..10 {
-            struct State {
-                seen: u8,
-                last: Option<Vert>,
-            }
-
-            let mut st = State {
-                seen: 0,
-                last: None,
-            };
+        for _ in 0..3 {
+            let mut seen = 0;
+            let mut last = None::<Vert>;
 
             for v in outer_loop
                 .iter_half_edges(&dcel)
@@ -104,15 +97,15 @@ fn kemh_mekh() {
                 if v.is_outer() {
                     s <<= 4;
                 }
-                if st.seen & s == 0 {
-                    st.seen |= s;
+                if seen & s == 0 {
+                    seen |= s;
                 } else {
                     assert_eq!(v.either(), 0);
-                    assert_eq!(st.seen & (s << 3), 0);
-                    st.seen |= s << 3;
+                    assert_eq!(seen & (s << 3), 0);
+                    seen |= s << 3;
                 }
 
-                if let Some(last) = st.last {
+                if let Some(last) = last {
                     if v.either() == 0 {
                         assert!(
                             last == v.flip()
@@ -123,10 +116,10 @@ fn kemh_mekh() {
                     }
                 }
 
-                st.last = Some(v);
+                last = Some(v);
             }
 
-            assert_eq!(st.seen, 255);
+            assert_eq!(seen, 255);
 
             let mekh = kemh.apply(&mut dcel).unwrap();
 
@@ -145,3 +138,99 @@ fn kemh_mekh() {
         }
     })
 }
+
+#[test]
+fn msev_ksev() {
+    Dcel::<u32>::new(|mut dcel| {
+        let body = dcel.new_body();
+
+        let Kevvlfs {
+            shell,
+            loop_: mut loop_0,
+            vertices: [out_0, out_1],
+            ..
+        } = dcel.mevvlfs(*body, [0, 1]).unwrap();
+
+        let out_2 = dcel.mev(*shell, *loop_0, *out_1, 2).new_vertex;
+        let out_3 = dcel.mev(*shell, *loop_0, *out_2, 3).new_vertex;
+        dcel.melf(*shell, [*out_0, *out_3], *loop_0);
+
+        let Melf {
+            new_loop: mut loop_2,
+            edge,
+            ..
+        } = dcel.melf(*shell, [*out_0, *out_2], *loop_0);
+        if out_1.find_outgoing(*loop_0, &dcel).is_none() {
+            [loop_0, loop_2] = [loop_2, loop_0];
+        }
+
+        let in_0 = dcel.mve(*shell, *edge, 4).vertex;
+
+        let mut loop_1 = dcel.melf(*shell, [*out_1, *in_0], *loop_0).new_loop;
+        if out_0.find_outgoing(*loop_0, &dcel).is_none() {
+            [loop_0, loop_1] = [loop_1, loop_0];
+        }
+
+        let mut loop_3 = dcel.melf(*shell, [*out_3, *in_0], *loop_2).new_loop;
+        if out_2.find_outgoing(*loop_2, &dcel).is_none() {
+            [loop_2, loop_3] = [loop_3, loop_2];
+        }
+
+        fn test_integrity<'brand, 'arena>(
+            debug: &'static str,
+            dcel: &Dcel<'brand, 'arena, u32>,
+            loops: &[(ptr_t!(Loop<'brand, 'arena, u32>), &[u32])],
+        ) {
+            for (i, (l, want)) in loops.iter().enumerate() {
+                let mut got = l
+                    .iter_half_edges(dcel)
+                    .map(|x| *x.origin().data())
+                    .collect::<Vec<_>>();
+
+                assert!(
+                    (0..want.len()).any(|_| {
+                        let x = got.remove(0);
+                        got.push(x);
+                        want == &got
+                    }),
+                    "{debug} loop = {i} want = {want:?} got = {got:?}"
+                );
+            }
+        }
+
+        let mut msev = Msev::new(*shell, *in_0, [*loop_0, *loop_2], 5);
+
+        for i in 0..4 {
+            test_integrity(
+                "before msev:",
+                &dcel,
+                &[
+                    (*loop_0, &[0, 4, 1]),
+                    (*loop_1, &[1, 4, 2]),
+                    (*loop_2, &[2, 4, 3]),
+                    (*loop_3, &[3, 4, 0]),
+                ],
+            );
+
+            let mut ksev = msev.apply(&mut dcel).unwrap();
+
+            if i % 2 == 0 {
+                // ksev should be able to fix the order of the loops
+                [ksev.loops[0], ksev.loops[1]] = [ksev.loops[1], ksev.loops[0]];
+            }
+
+            test_integrity(
+                "after msev:",
+                &dcel,
+                &[
+                    (*loop_0, &[0, 4, 5, 1]),
+                    (*loop_1, &[1, 5, 2]),
+                    (*loop_2, &[2, 5, 4, 3]),
+                    (*loop_3, &[3, 4, 0]),
+                ],
+            );
+
+            msev = ksev.apply(&mut dcel).unwrap();
+        }
+    })
+}