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/render/src/morph_text.rs

@@ -76,12 +76,16 @@ fn tokens(l: &TextLayout, chars: bool) -> (Vec<Token>, Vec<(usize, usize)>) {
 
 /// For each token of `b`, the token of `a` with the same text, in reading order, each used once.
 fn matches(a: &[Token], b: &[Token]) -> Vec<Option<usize>> {
-    // Unused tokens of `a` by text, in reading order, so each lookup is a pop rather than a scan.
-    let mut free: std::collections::HashMap<&str, std::collections::VecDeque<usize>> = std::collections::HashMap::new();
-    for (i, ta) in a.iter().enumerate() {
-        free.entry(ta.key.as_str()).or_default().push_back(i);
-    }
-    b.iter().map(|tb| free.get_mut(tb.key.as_str())?.pop_front()).collect()
+    let mut used = vec![false; a.len()];
+    b.iter()
+        .map(|tb| {
+            let i = a.iter().enumerate().position(|(i, ta)| !used.get(i).copied().unwrap_or(true) && ta.key == tb.key)?;
+            if let Some(u) = used.get_mut(i) {
+                *u = true;
+            }
+            Some(i)
+        })
+        .collect()
 }
 
 fn layout(ctx: &Ctx, s: &Shape, x: Xfrm, fields: &dyn Fields) -> Option<TextLayout> {
@@ -224,19 +228,3 @@ pub(crate) fn draw(
 pub(crate) fn token_keys(l: &TextLayout, chars: bool) -> Vec<String> {
     tokens(l, chars).0.into_iter().map(|t| t.key).collect()
 }
-
-#[cfg(test)]
-mod match_tests {
-    use super::*;
-
-    fn tok(k: &str) -> Token {
-        Token { key: k.into(), glyphs: Vec::new(), origin: Point::ZERO, run: 0 }
-    }
-
-    #[test]
-    fn each_source_token_is_used_once_in_reading_order() {
-        let a: Vec<Token> = ["a", "b", "a"].map(tok).into();
-        let b: Vec<Token> = ["a", "a", "a", "b", "c"].map(tok).into();
-        assert_eq!(matches(&a, &b), vec![Some(0), Some(2), None, Some(1), None]);
-    }
-}

crates/text/src/run.rs

@@ -22,7 +22,7 @@ pub struct GlyphRun {
     pub link: bool,
     /// Opacity of the fill on top of `color`'s own alpha (0 for no fill).
     pub alpha: f64,
-    pub gradient: Option<std::sync::Arc<deckcraft_model::style::Gradient>>,
+    pub gradient: Option<deckcraft_model::style::Gradient>,
     /// Shadow and glow behind the glyphs (`a:rPr/a:effectLst`).
     pub effects: Option<RunEffects>,
     /// East Asian vertical text (`eaVert`): each glyph stands upright, turned a quarter turn

crates/text/src/style.rs

@@ -46,7 +46,7 @@ pub(crate) struct Style {
     pub(crate) highlight: Option<Rgba>,
     pub(crate) outline: Option<(Rgba, f64)>,
     pub(crate) link: bool,
-    pub(crate) gradient: Option<std::sync::Arc<deckcraft_model::style::Gradient>>,
+    pub(crate) gradient: Option<deckcraft_model::style::Gradient>,
     pub(crate) effects: Option<RunEffects>,
     /// "Regular", "Bold"… for the slot and fallback faces.
     pub(crate) style_name: &'static str,
@@ -136,7 +136,7 @@ pub(crate) fn make_style(ctx: &Ctx, r: &RunProps, scale: f64, prompt: Option<Rgb
             for s in &mut g.stops {
                 s.color = deckcraft_model::ColorRef::rgb(ctx.color(&s.color, None));
             }
-            (g.stops.first().map(|s| ctx.color(&s.color, None)).unwrap_or(Rgba::BLACK), 1.0, Some(std::sync::Arc::new(g)))
+            (g.stops.first().map(|s| ctx.color(&s.color, None)).unwrap_or(Rgba::BLACK), 1.0, Some(g))
         }
         Some(Fill::None) => (Rgba::TRANSPARENT, 0.0, None),
         _ => (resolve::text_color(ctx, r), 1.0, None),