5 files changed, 463 insertions, 28 deletions

diff --git a/src/depth_search_iterator.rs b/src/depth_search_iterator.rs
new file mode 100644
index 0000000..cc10df8
--- /dev/null
+++ b/src/depth_search_iterator.rs
@@ -0,0 +1,83 @@
+use crate::*;
+
+pub(crate) struct DepthSearchIterator<'tok, 'brand, 'arena, V> {
+    token: &'tok GhostToken<'brand>,
+    seen_vertices: Option<HashMap<usize, ptr!(Vertex)>>,
+    seen_edges: HashMap<usize, ptr!(Edge)>,
+    seen_faces: HashMap<usize, ptr!(Face)>,
+    edge_stack: Vec<ptr!(Edge)>,
+    face_stack: Vec<ptr!(Face)>,
+}
+
+impl<'tok, 'brand, 'arena, V> DepthSearchIterator<'tok, 'brand, 'arena, V> {
+    pub(crate) fn new(
+        edge: ptr!(Edge),
+        collect_vertices: bool,
+        token: &'tok impl ReflAsRef<GhostToken<'brand>>,
+    ) -> Self {
+        Self {
+            token: token.as_ref(),
+            seen_vertices: collect_vertices.then(|| HashMap::new()),
+            seen_edges: HashMap::from([(edge.id(token), edge)]),
+            seen_faces: HashMap::new(),
+            edge_stack: Vec::from([edge]),
+            face_stack: Vec::new(),
+        }
+    }
+
+    fn add_edge(&mut self, edge: ptr!(Edge)) {
+        if self.seen_edges.insert(edge.id(self.token), edge).is_none() {
+            self.edge_stack.push(edge);
+        }
+    }
+
+    pub(crate) fn collect_seen(
+        edge: ptr!(Edge),
+        token: &'tok impl ReflAsRef<GhostToken<'brand>>,
+    ) -> (
+        HashMap<usize, ptr!(Vertex)>,
+        HashMap<usize, ptr!(Edge)>,
+        HashMap<usize, ptr!(Face)>,
+    )
+    where
+        'brand: 'tok,
+    {
+        let mut x = Self::new(edge, true, token);
+        for _ in &mut x {}
+        (x.seen_vertices.unwrap(), x.seen_edges, x.seen_faces)
+    }
+}
+
+impl<'tok, 'brand, 'arena, V> Iterator for DepthSearchIterator<'tok, 'brand, 'arena, V> {
+    type Item = ptr!(Edge);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let Some(edge) = self.edge_stack.pop() else {
+            let face = self.face_stack.pop()?;
+
+            for loop_ in std::iter::once(face.lens(self.token).outer_loop())
+                .chain(face.iter_inner_loops(self.token))
+            {
+                self.add_edge(loop_.half_edges().edge().item);
+            }
+
+            return self.next();
+        };
+
+        for h in edge.half_edges(self.token) {
+            let face = h.loop_(self.token).face(self.token);
+            if self.seen_faces.insert(face.id(self.token), face).is_none() {
+                self.face_stack.push(face);
+            }
+
+            let origin = h.origin(self.token);
+            if let Some(seen_vertices) = self.seen_vertices.as_mut() {
+                seen_vertices.insert(origin.id(self.token), origin);
+            }
+
+            self.add_edge(h.next(self.token).edge(self.token));
+        }
+
+        Some(edge)
+    }
+}
diff --git a/src/entity.rs b/src/entity.rs
index 7cce82d..b3e3359 100644
--- a/src/entity.rs
+++ b/src/entity.rs
@@ -174,8 +174,9 @@ macro_rules! entity {
 
 						let last = item;
 						while {
+							let next_item = item.next(token);
 							f(item, token);
-							item = item.next(token);
+							item = next_item;
 							!item.eq(last, token)
 						} {}
 					}
diff --git a/src/main.rs b/src/main.rs
index ba345f8..2fcde6e 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -4,6 +4,7 @@ use core::ops::Deref;
 pub use ghost_cell::{GhostBorrow, GhostCell, GhostToken};
 use paste::paste;
 use std::{
+    collections::HashMap,
     convert::Infallible,
     fmt::{self, Debug, Display, Formatter},
     hash::{Hash, Hasher},
@@ -36,12 +37,24 @@ mod tests;
 mod mevvlfs;
 pub use mevvlfs::*;
 
+// mod mev;
+// pub use mev::*;
+
+// mod mve;
+// pub use mve::*;
+
+// mod melf;
+// pub use melf::*;
+
 mod mekh;
 pub use mekh::*;
 
 mod msev;
 pub use msev::*;
 
+mod mpkh;
+pub use mpkh::*;
+
 pub trait ReflAsRef<T> {
     fn as_ref(&self) -> &T;
 }
@@ -273,6 +286,12 @@ impl<'tok, 'brand, 'arena, T: PartialEq> PartialEq for lens_t!(T) {
 }
 impl<'tok, 'brand, 'arena, T: PartialEq> Eq for lens_t!(T) {}
 
+impl<'tok, 'brand, 'arena, T: Hash> Hash for lens_t!(T) {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.item.borrow(self.token).hash(state);
+    }
+}
+
 impl<'tok, 'brand, 'arena, T> ReflAsRef<GhostToken<'brand>> for lens_t!(T) {
     fn as_ref(&self) -> &GhostToken<'brand> {
         &self.token
@@ -992,6 +1011,22 @@ impl<'brand, 'arena, V> Dcel<'brand, 'arena, V> {
     ) -> Result<Msev<'brand, 'arena, V>, OperatorErr<Ksev<'brand, 'arena, V>, KsevError>> {
         Ksev::new(shell, loops, old_vertex, new_vertex, edge).apply(self)
     }
+
+    pub fn mpkh(
+        &mut self,
+        loop_: ptr!(Loop),
+    ) -> Result<Kpmh<'brand, 'arena, V>, OperatorErr<Mpkh<'brand, 'arena, V>, MpkhError>> {
+        Mpkh::new(loop_).apply(self)
+    }
+
+    pub fn kpmh(
+        &mut self,
+        new_shell: Option<own!(Shell)>,
+        old_face: ptr!(Face),
+        new_face: own!(Face),
+    ) -> Result<Mpkh<'brand, 'arena, V>, OperatorErr<Kpmh<'brand, 'arena, V>, KpmhError>> {
+        Kpmh::new(new_shell, old_face, new_face).apply(self)
+    }
 }
 
 use std::io::Write;
diff --git a/src/mpkh.rs b/src/mpkh.rs
new file mode 100644
index 0000000..e19bd42
--- /dev/null
+++ b/src/mpkh.rs
@@ -0,0 +1,226 @@
+use crate::*;
+
+fn maybe_split<'brand, 'arena, V>(
+    dcel: &mut Dcel<'brand, 'arena, V>,
+    old_shell: ptr!(Shell),
+    inside_edge: ptr!(Edge),
+    outside_edge: ptr!(Edge),
+) -> Option<own!(Shell)> {
+    let mut seen_vertices = HashMap::new();
+    let mut seen_edges = HashMap::new();
+    let mut seen_faces = HashMap::new();
+    let mut edge_stack = Vec::new();
+    let mut face_stack = Vec::<ptr!(Face)>::new();
+
+    let mut add_edge = |edge: ptr!(Edge), edge_stack: &mut Vec<ptr!(Edge)>| {
+        if edge.eq(inside_edge, dcel) {
+            return None;
+        }
+
+        if seen_edges.insert(edge.id(dcel), edge).is_none() {
+            edge_stack.push(edge);
+        }
+
+        Some(())
+    };
+
+    add_edge(outside_edge, &mut edge_stack)?;
+
+    loop {
+        let Some(edge) = edge_stack.pop() else {
+            let Some(face) = face_stack.pop() else {
+                break;
+            };
+
+            for loop_ in
+                std::iter::once(face.lens(dcel).outer_loop()).chain(face.iter_inner_loops(dcel))
+            {
+                add_edge(loop_.half_edges().edge().item, &mut edge_stack)?;
+            }
+
+            continue;
+        };
+
+        for h in edge.half_edges(dcel) {
+            let face = h.loop_(dcel).face(dcel);
+            if seen_faces.insert(face.id(dcel), face).is_none() {
+                face_stack.push(face);
+            }
+
+            let origin = h.origin(dcel);
+            seen_vertices.insert(origin.id(dcel), origin);
+
+            add_edge(h.next(dcel).edge(dcel), &mut edge_stack)?;
+        }
+    }
+
+    let new_shell = old_shell.body(dcel).add_new_shell(dcel);
+
+    for &v in seen_vertices.values() {
+        old_shell.remove_vertex(v, dcel);
+        new_shell.add_vertex(v, dcel);
+    }
+    for &e in seen_edges.values() {
+        old_shell.remove_edge(e, dcel);
+        new_shell.add_edge(e, dcel);
+    }
+    for &f in seen_faces.values() {
+        old_shell.remove_face(f, dcel);
+        new_shell.add_face(f, dcel);
+    }
+
+    Some(new_shell)
+}
+
+pub struct Mpkh<'brand, 'arena, V> {
+    pub loop_: ptr!(Loop),
+}
+
+impl<'brand, 'arena, V> Mpkh<'brand, 'arena, V> {
+    pub fn new(loop_: ptr!(Loop)) -> Self {
+        Self { loop_ }
+    }
+}
+
+#[derive(Debug, Error)]
+pub enum MpkhError {
+    #[error("loop is not an inner loop")]
+    LoopIsOuter,
+}
+
+impl<'brand, 'arena, V> Operator<'brand, 'arena, V> for Mpkh<'brand, 'arena, V> {
+    type Inverse = Kpmh<'brand, 'arena, V>;
+    type Error = MpkhError;
+    type Check = ();
+
+    fn check(&self, dcel: &Dcel<'brand, 'arena, V>) -> Result<Self::Check, Self::Error> {
+        use MpkhError::*;
+
+        or_err(!self.loop_.is_outer(dcel), LoopIsOuter)?;
+
+        Ok(())
+    }
+
+    fn apply(
+        self,
+        dcel: &mut Dcel<'brand, 'arena, V>,
+    ) -> Result<Self::Inverse, OperatorErr<Self, Self::Error>> {
+        try_check!(self, dcel);
+
+        let old_face = self.loop_.face(dcel);
+        let old_shell = old_face.shell(dcel);
+
+        let new_face = old_shell.add_new_face(dcel);
+
+        old_face.remove_inner_loop(self.loop_, dcel);
+        new_face.set_outer_loop(self.loop_, dcel);
+        self.loop_.set_face(*new_face, dcel);
+
+        let new_shell = maybe_split(
+            dcel,
+            old_shell,
+            old_face.outer_loop(dcel).half_edges(dcel).edge(dcel),
+            self.loop_.half_edges(dcel).edge(dcel),
+        );
+
+        Ok(Kpmh {
+            new_shell,
+            old_face,
+            new_face,
+        })
+    }
+}
+
+pub struct Kpmh<'brand, 'arena, V> {
+    pub new_shell: Option<own!(Shell)>,
+    pub old_face: ptr!(Face),
+    pub new_face: own!(Face),
+}
+
+#[derive(Error, Debug)]
+pub enum KpmhError {
+    #[error("face does not match shell")]
+    FaceShellMismatch,
+    #[error("shell passed in, but faces are already part of same shell")]
+    CannotMerge,
+    #[error("no shell passed in but faces are part of different shells")]
+    ShouldMerge,
+    #[error("face has inner loops")]
+    HasInnerLoops,
+    #[error("shells are part of different body")]
+    BodyMismatch,
+}
+
+impl<'brand, 'arena, V> Kpmh<'brand, 'arena, V> {
+    pub fn new(new_shell: Option<own!(Shell)>, old_face: ptr!(Face), new_face: own!(Face)) -> Self {
+        Self {
+            new_shell,
+            old_face,
+            new_face,
+        }
+    }
+}
+
+impl<'brand, 'arena, V> Operator<'brand, 'arena, V> for Kpmh<'brand, 'arena, V> {
+    type Inverse = Mpkh<'brand, 'arena, V>;
+    type Error = KpmhError;
+    type Check = ();
+
+    fn check(&self, dcel: &Dcel<'brand, 'arena, V>) -> Result<Self::Check, Self::Error> {
+        use KpmhError::*;
+
+        let Kpmh {
+            new_shell,
+            old_face,
+            new_face,
+        } = self;
+
+        let old_shell = old_face.shell(dcel);
+        let needs_merge = !new_face.shell(dcel).eq(old_shell, dcel);
+
+        if let Some(new_shell) = new_shell {
+            or_err(
+                new_face.shell(dcel).eq(**new_shell, dcel),
+                FaceShellMismatch,
+            )?;
+            or_err(needs_merge, CannotMerge)?;
+        } else {
+            or_err(!needs_merge, ShouldMerge)?;
+        }
+
+        or_err(new_face.maybe_inner_loops(dcel).is_none(), HasInnerLoops)?;
+
+        Ok(())
+    }
+
+    fn apply(
+        self,
+        dcel: &mut Dcel<'brand, 'arena, V>,
+    ) -> Result<Self::Inverse, OperatorErr<Self, Self::Error>> {
+        try_check!(self, dcel);
+
+        let Kpmh {
+            new_shell,
+            old_face,
+            new_face,
+        } = self;
+
+        let loop_ = new_face.outer_loop(dcel);
+        old_face.add_inner_loop(loop_, dcel);
+
+        new_face.shell(dcel).remove_face(*new_face, dcel);
+        new_face.free(dcel);
+
+        if let Some(new_shell) = new_shell {
+            let old_shell = old_face.shell(dcel);
+            new_shell.iter_mut_vertices(dcel, |x, dcel| old_shell.add_vertex(x, dcel));
+            new_shell.iter_mut_edges(dcel, |x, dcel| old_shell.add_edge(x, dcel));
+            new_shell.iter_mut_faces(dcel, |x, dcel| old_shell.add_face(x, dcel));
+
+            new_shell.body(dcel).remove_shell(*new_shell, dcel);
+            new_shell.free(dcel);
+        }
+
+        Ok(Mpkh { loop_ })
+    }
+}
diff --git a/src/tests.rs b/src/tests.rs
index a1ad5a4..52ec2cd 100644
--- a/src/tests.rs
+++ b/src/tests.rs
@@ -23,6 +23,60 @@ fn mev_cycle() {
     })
 }
 
+/*
+
+makes this shape:
+
+   O      O
+   |\    /|
+   | \__/ |
+   | O__O |
+   | /  \ |
+   |/    \|
+   O      O
+
+*/
+fn make_hourglass<'brand, 'arena, V>(
+    dcel: &mut Dcel<'brand, 'arena, V>,
+    data: [V; 6],
+) -> (own!(Shell), [own!(Loop); 3], own!(Edge), [own!(Vertex); 6]) {
+    let [d0, d1, d2, d3, d4, d5] = data;
+
+    let body = dcel.new_body();
+    let Kevvlfs {
+        shell,
+        loop_: loop_0,
+        vertices: [inner_0, inner_1],
+        ..
+    } = dcel.mevvlfs(*body, [d0, d1]).unwrap();
+
+    let inner_2 = dcel.mev(*shell, *loop_0, *inner_1, d2).new_vertex;
+    let mut outer_loop = dcel.melf(*shell, [*inner_0, *inner_2], *loop_0).new_loop;
+
+    let Mev {
+        new_vertex: outer_0,
+        edge,
+        ..
+    } = dcel.mev(*shell, *outer_loop, *inner_0, d3);
+
+    let outer_1 = dcel.mev(*shell, *outer_loop, *outer_0, d4).new_vertex;
+    let outer_2 = dcel.mev(*shell, *outer_loop, *outer_1, d5).new_vertex;
+
+    let mut loop_2 = dcel
+        .melf(*shell, [*outer_0, *outer_2], *outer_loop)
+        .new_loop;
+    if edge.lens(dcel).half_edges()[0].loop_().eq(*loop_2) {
+        [outer_loop, loop_2] = [loop_2, outer_loop];
+    }
+
+    (
+        shell,
+        [outer_loop, loop_0, loop_2],
+        edge,
+        [inner_0, inner_1, inner_2, outer_0, outer_1, outer_2],
+    )
+}
+
 #[test]
 fn kemh_mekh() {
     #[derive(Copy, Clone, Debug, Eq, PartialEq)]
@@ -56,33 +110,10 @@ fn kemh_mekh() {
     }
 
     Dcel::<Vert>::new(|mut dcel| {
-        let body = dcel.new_body();
-        let Kevvlfs {
-            shell,
-            loop_: loop_0,
-            vertices: [inner_0, inner_1],
-            ..
-        } = dcel.mevvlfs(*body, [Inner(0), Inner(1)]).unwrap();
-
-        let inner_2 = dcel.mev(*shell, *loop_0, *inner_1, Inner(2)).new_vertex;
-        let mut outer_loop = dcel.melf(*shell, [*inner_0, *inner_2], *loop_0).new_loop;
-
-        let Mev {
-            new_vertex: outer_0,
-            edge,
-            ..
-        } = dcel.mev(*shell, *outer_loop, *inner_0, Outer(0));
-
-        let outer_1 = dcel.mev(*shell, *outer_loop, *outer_0, Outer(1)).new_vertex;
-        let outer_2 = dcel.mev(*shell, *outer_loop, *outer_1, Outer(2)).new_vertex;
-
-        let loop_2 = dcel
-            .melf(*shell, [*outer_0, *outer_2], *outer_loop)
-            .new_loop;
-        if edge.lens(&dcel).half_edges()[0].loop_().eq(*loop_2) {
-            outer_loop = loop_2;
-        }
-
+        let (shell, [outer_loop, ..], edge, [inner_0, ..]) = make_hourglass(
+            &mut dcel,
+            [Inner(0), Inner(1), Inner(2), Outer(0), Outer(1), Outer(2)],
+        );
         let mut kemh = Kemh::new(*shell, edge, *outer_loop, *inner_0);
 
         for _ in 0..3 {
@@ -234,3 +265,62 @@ fn msev_ksev() {
         }
     })
 }
+
+#[test]
+fn mpkh_kpmh() {
+    Dcel::<()>::new(|mut dcel| {
+        let (shell, [outer_0, inner_1, outer_1], edge, [vert, ..]) =
+            make_hourglass(&mut dcel, [(); 6]);
+        let inner_0 = dcel.kemh(*shell, edge, *outer_0, *vert).unwrap().hole_loop;
+
+        let mut mpkh = Mpkh::new(*inner_0);
+
+        for _ in 0..4 {
+            use std::collections::HashSet;
+
+            {
+                mklens!(&dcel, shell, outer_0, outer_1, inner_0, inner_1);
+
+                assert_eq!(
+                    shell.iter_faces().collect::<HashSet<_>>(),
+                    HashSet::from([outer_0, outer_1, inner_0, inner_1].map(Lens::face))
+                );
+
+                assert_eq!(outer_0.face(), inner_0.face());
+                assert_eq!(outer_0.face().outer_loop(), outer_0);
+                assert_eq!(outer_0.face().inner_loops(), inner_0);
+                assert_eq!(inner_0.next(), inner_0);
+            }
+
+            let kpmh = mpkh.apply(&mut dcel).unwrap();
+
+            {
+                let new_face = &kpmh.new_face;
+                let new_shell = kpmh.new_shell.as_ref().unwrap();
+
+                mklens!(&dcel, shell, new_shell, new_face, outer_0, outer_1, inner_0, inner_1);
+
+                assert_eq!(new_face, inner_0.face());
+                assert_eq!(new_face.outer_loop(), inner_0);
+                assert!(new_face.iter_inner_loops().next().is_none());
+
+                assert_eq!(
+                    shell.body().iter_shells().collect::<HashSet<_>>(),
+                    HashSet::from([new_shell, shell])
+                );
+
+                assert_eq!(
+                    shell.iter_faces().collect::<HashSet<_>>(),
+                    HashSet::from([outer_0.face(), outer_1.face()])
+                );
+
+                assert_eq!(
+                    new_shell.iter_faces().collect::<HashSet<_>>(),
+                    HashSet::from([inner_0.face(), inner_1.face()])
+                );
+            }
+
+            mpkh = kpmh.apply(&mut dcel).unwrap();
+        }
+    })
+}