Morph: pick the next curve to split from a heap, not a full scan

crates/geom/src/morph.rs

@@ -126,6 +126,21 @@ fn split_curve(c: &[Point], n: usize, out: &mut Vec<Point>) {
     out.extend([p1, p2, p3]);
 }
 
+/// A piece length ordered totally, so it can sit in a heap.
+#[derive(PartialEq)]
+struct Share(f64);
+impl Eq for Share {}
+impl PartialOrd for Share {
+    fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> {
+        Some(self.cmp(o))
+    }
+}
+impl Ord for Share {
+    fn cmp(&self, o: &Self) -> std::cmp::Ordering {
+        self.0.total_cmp(&o.0)
+    }
+}
+
 /// Brings a contour to `n` curves. Unlike manim (which splits every curve equally often), the extra
 /// splits go to the longest pieces, so a long side gets more points than a short one.
 fn refine(c: &Contour, n: usize) -> Contour {
@@ -136,11 +151,15 @@ fn refine(c: &Contour, n: usize) -> Contour {
     let curves: Vec<&[Point]> = (0..have).filter_map(|k| c.pts.get(3 * k..3 * k + 4)).collect();
     let len: Vec<f64> = curves.iter().map(|q| curve_length(q) + 1e-9).collect();
     let mut parts = vec![1usize; curves.len()];
+    // The curve with the longest piece gets the next split (the lowest index on a tie); a heap keeps
+    // this O(n log n) instead of rescanning every curve for each split.
+    let mut heap: std::collections::BinaryHeap<(Share, std::cmp::Reverse<usize>)> =
+        len.iter().enumerate().map(|(k, l)| (Share(*l), std::cmp::Reverse(k))).collect();
     for _ in 0..n - have {
-        let share = |k: usize| len.get(k).copied().unwrap_or(0.0) / parts.get(k).copied().unwrap_or(1) as f64;
-        let best = (1..curves.len()).fold(0, |b, k| if share(k) > share(b) { k } else { b });
+        let Some((_, std::cmp::Reverse(best))) = heap.pop() else { break };
         if let Some(p) = parts.get_mut(best) {
             *p += 1;
+            heap.push((Share(len.get(best).copied().unwrap_or(0.0) / *p as f64), std::cmp::Reverse(best)));
         }
     }
     let mut out = Vec::with_capacity(1 + 3 * n);
@@ -420,6 +439,16 @@ mod tests {
         assert_eq!(contours(&to_path(&cs)), cs);
     }
 
+    #[test]
+    fn refine_many_curves_finishes_at_the_asked_count() {
+        let mut c = Contour { closed: false, pts: vec![Point::ZERO] };
+        for i in 1..=20_000 {
+            line_to(&mut c.pts, Point::new(f64::from(i), f64::from(i % 7)));
+        }
+        let r = refine(&c, 40_000);
+        assert_eq!(r.curves(), 40_000);
+    }
+
     #[test]
     fn refine_splits_the_longest_curves_and_keeps_the_shape() {
         let c = Contour { closed: false, pts: vec![Point::ZERO, Point::new(1.0, 0.0), Point::new(2.0, 0.0), Point::new(3.0, 0.0)] };

crates/model/src/edit.rs

@@ -78,57 +78,45 @@ pub fn insert(body: &mut TextBody, pos: Pos, text: &str, props: Option<RunProps>
     if body.paragraphs.is_empty() {
         body.paragraphs.push(Paragraph::default());
     }
-    let (pi0, mut ch) = clamp(body, pos);
-    let props = props.unwrap_or_else(|| props_at(body, (pi0, ch)));
+    let (mut pi, mut ch) = clamp(body, pos);
+    let props = props.unwrap_or_else(|| props_at(body, (pi, ch)));
     let text = text.replace("\r\n", "\n").replace('\r', "\n");
-    // Work on the paragraph being edited apart from the body, so each new paragraph is pushed to a
-    // list and the body's vector is spliced once instead of shifted for every `\n`.
-    let Some(slot) = body.paragraphs.get_mut(pi0) else { return (pi0, ch) };
-    let mut cur = std::mem::take(slot);
-    let mut done: Vec<Paragraph> = Vec::new();
     let mut first = true;
     for part in text.split('\n') {
         if !first {
-            // Split the current paragraph at ch.
-            let idx = split_at(&mut cur, ch);
-            let tail: Vec<Run> = cur.runs.drain(idx..).collect();
-            let newp = Paragraph {
-                level: cur.level,
-                props: cur.props.clone(),
-                runs: tail,
-                def_props: cur.def_props.clone(),
-                end_props: cur.end_props.clone(),
-            };
-            cur.end_props = props.clone();
-            done.push(std::mem::replace(&mut cur, newp));
+            // Split paragraph pi at ch.
+            let Some(p) = body.paragraphs.get_mut(pi) else { break };
+            let idx = split_at(p, ch);
+            let tail: Vec<Run> = p.runs.drain(idx..).collect();
+            let newp =
+                Paragraph { level: p.level, props: p.props.clone(), runs: tail, def_props: p.def_props.clone(), end_props: p.end_props.clone() };
+            p.end_props = props.clone();
+            body.paragraphs.insert(pi + 1, newp);
+            pi += 1;
             ch = 0;
         }
         first = false;
-        // The run index just after the last insertion: the next one lands there with no rescan.
-        let mut next: Option<usize> = None;
         for (k, seg) in part.split('\u{b}').enumerate() {
+            let Some(p) = body.paragraphs.get_mut(pi) else { break };
             if k > 0 {
-                let idx = next.unwrap_or_else(|| split_at(&mut cur, ch));
-                cur.runs.insert(idx, Run { text: String::new(), props: props.clone(), kind: RunKind::Break });
+                let idx = split_at(p, ch);
+                p.runs.insert(idx, Run { text: String::new(), props: props.clone(), kind: RunKind::Break });
                 ch += 1;
-                next = Some(idx + 1);
             }
             if seg.is_empty() {
                 continue;
             }
-            let idx = next.unwrap_or_else(|| split_at(&mut cur, ch));
-            cur.runs.insert(idx, Run::with(seg, props.clone()));
+            let idx = split_at(p, ch);
+            p.runs.insert(idx, Run::with(seg, props.clone()));
             ch += seg.chars().count();
-            next = Some(idx + 1);
         }
-        cur.normalize();
-        if cur.runs.is_empty() {
-            cur.end_props = props.clone();
+        if let Some(p) = body.paragraphs.get_mut(pi) {
+            p.normalize();
+            if p.runs.is_empty() {
+                p.end_props = props.clone();
+            }
         }
     }
-    let pi = pi0 + done.len();
-    done.push(cur);
-    body.paragraphs.splice(pi0..=pi0, done);
     (pi, ch)
 }
 
@@ -264,16 +252,8 @@ pub fn slice(body: &TextBody, a: Pos, b: Pos) -> TextBody {
 /// Insert a formatted body at `pos` (paste): first paragraph merges into the current one.
 pub fn insert_body(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
     let mut caret = clamp(body, pos);
-    // Plain text runs go straight in at the run index after the previous one and the paragraph is
-    // normalized once, not rescanned and merged for every source run.
-    let mut next: Option<usize> = None;
-    let mut dirty = false;
     for (k, sp) in src.paragraphs.iter().enumerate() {
         if k > 0 {
-            if let (true, Some(p)) = (dirty, body.paragraphs.get_mut(caret.0)) {
-                p.normalize();
-            }
-            (next, dirty) = (None, false);
             caret = insert(body, caret, "\n", None);
             if let Some(p) = body.paragraphs.get_mut(caret.0) {
                 p.level = sp.level;
@@ -281,22 +261,6 @@ pub fn insert_body(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
             }
         }
         for r in &sp.runs {
-            if r.kind == RunKind::Text
-                && !r.text.is_empty()
-                && !r.text.contains(['\n', '\r', '\u{b}'])
-                && let Some(p) = body.paragraphs.get_mut(caret.0)
-            {
-                let idx = next.unwrap_or_else(|| split_at(p, caret.1));
-                p.runs.insert(idx, Run::with(&r.text, r.props.clone()));
-                caret.1 += r.text.chars().count();
-                (next, dirty) = (Some(idx + 1), true);
-                continue;
-            }
-            // Anything else takes the general path, after the pending runs are merged.
-            if let (true, Some(p)) = (dirty, body.paragraphs.get_mut(caret.0)) {
-                p.normalize();
-            }
-            (next, dirty) = (None, false);
             match r.kind {
                 RunKind::Text => caret = insert(body, caret, &r.text, Some(r.props.clone())),
                 RunKind::Break => caret = insert(body, caret, "\u{b}", Some(r.props.clone())),
@@ -310,9 +274,6 @@ pub fn insert_body(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
             }
         }
     }
-    if let (true, Some(p)) = (dirty, body.paragraphs.get_mut(caret.0)) {
-        p.normalize();
-    }
     caret
 }
 
@@ -607,74 +568,6 @@ mod tests {
         assert_eq!(caret, (0, 5));
     }
 
-    /// The paste as it ran before the fast path: one `insert` (and normalize) per source run.
-    fn insert_body_by_runs(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
-        let mut caret = clamp(body, pos);
-        for (k, sp) in src.paragraphs.iter().enumerate() {
-            if k > 0 {
-                caret = insert(body, caret, "\n", None);
-                if let Some(p) = body.paragraphs.get_mut(caret.0) {
-                    p.level = sp.level;
-                    p.props = sp.props.clone();
-                }
-            }
-            for r in &sp.runs {
-                match r.kind {
-                    RunKind::Text => caret = insert(body, caret, &r.text, Some(r.props.clone())),
-                    RunKind::Break => caret = insert(body, caret, "\u{b}", Some(r.props.clone())),
-                    _ => {
-                        if let Some(p) = body.paragraphs.get_mut(caret.0) {
-                            let idx = split_at(p, caret.1);
-                            p.runs.insert(idx, r.clone());
-                            caret.1 += r.char_len();
-                        }
-                    }
-                }
-            }
-        }
-        caret
-    }
-
-    #[test]
-    fn paste_matches_inserting_run_by_run() {
-        let bold = |t: &str| Run::with(t, RunProps { bold: Some(true), ..Default::default() });
-        let mut src = body("");
-        src.paragraphs = vec![
-            Paragraph {
-                runs: vec![Run::with("ab", RunProps::default()), Run::with("cd", RunProps::default()), bold("ef"), bold("g")],
-                ..Default::default()
-            },
-            Paragraph {
-                runs: vec![
-                    bold("h"),
-                    Run { text: String::new(), props: RunProps::default(), kind: RunKind::Break },
-                    Run::with("i", RunProps::default()),
-                ],
-                level: 1,
-                ..Default::default()
-            },
-            Paragraph { runs: vec![Run::with("jk", RunProps::default())], ..Default::default() },
-        ];
-        for at in [0, 1, 3, 6] {
-            let mut dest = body("XYZabc");
-            format(&mut dest, (0, 2), (0, 4), &|p| p.italic = Some(true));
-            let mut want = dest.clone();
-            let want_caret = insert_body_by_runs(&mut want, (0, at), &src);
-            let caret = insert_body(&mut dest, (0, at), &src);
-            assert_eq!(caret, want_caret, "caret at {at}");
-            assert_eq!(format!("{:?}", dest.paragraphs), format!("{:?}", want.paragraphs), "paste at {at}");
-        }
-    }
-
-    #[test]
-    fn multiline_insert_splits_into_paragraphs() {
-        let mut b = body("abcd");
-        let c = insert(&mut b, (0, 2), "x\ny\u{b}z\n\nw", None);
-        assert_eq!(c, (3, 1));
-        let texts: Vec<String> = b.paragraphs.iter().map(Paragraph::text).collect();
-        assert_eq!(texts, ["abx", "y\u{b}z", "", "wcd"]);
-    }
-
     #[test]
     fn words_and_moves() {
         let b = body("Hello brave world");