functions: MODE counts through an index, FREQUENCY bins by binary search

MODE/MODE.SNGL/MODE.MULT searched the list of distinct numbers seen so far
for every input, and FREQUENCY scanned the sorted bins for every data value,
so both were quadratic in computed arrays. MODE now keys counts by value
(-0 folded into 0, NaN never merged) and keeps first-occurrence order;
FREQUENCY finds the first bin at or above each value with partition_point
over the order it already sorts. Results are unchanged.

crates/engine/src/cmd/print/draw.rs

@@ -228,82 +228,6 @@ fn draw_border(pg: &mut Page, b: &BorderLine, wb: &Workbook, start: Point, end:
     pg.stroke_line_dashed(Point::new(x0, y0), Point::new(x1, y1), lw, color, &border_dash(b.style, k));
 }
 
-/// Merged areas active at one row of a downward sweep, kept disjoint: by first column, their last
-/// column and last row. Adding, dropping and looking up a merge costs log(active merges).
-#[derive(Default)]
-struct MergeSweep {
-    cols: std::collections::BTreeMap<u32, (u32, u32)>,
-    /// (last row, first column) of the active merges, soonest ending first.
-    ends: std::collections::BinaryHeap<std::cmp::Reverse<(u32, u32)>>,
-}
-
-impl MergeSweep {
-    /// Moves down to `row` (rows never decrease), dropping the merges that end above it.
-    fn advance(&mut self, row: u32) {
-        while let Some(std::cmp::Reverse((end, col))) = self.ends.peek().copied() {
-            if end >= row {
-                break;
-            }
-            self.ends.pop();
-            self.cols.remove(&col);
-        }
-    }
-
-    /// Does an active merge meet columns `c0..=c1`? The intervals are disjoint, so only the last
-    /// one starting at or before `c1` can.
-    fn meets(&self, c0: u32, c1: u32) -> bool {
-        self.cols.range(..=c1).next_back().is_some_and(|(_, (end, _))| *end >= c0)
-    }
-
-    /// Adds merge `m`, at row `row`, unless it overlaps an active one.
-    fn add(&mut self, m: RangeRef, row: u32) -> bool {
-        self.advance(row);
-        if self.meets(m.start.col, m.end.col) {
-            return false;
-        }
-        self.cols.insert(m.start.col, (m.end.col, m.end.row));
-        self.ends.push(std::cmp::Reverse((m.end.row, m.start.col)));
-        true
-    }
-}
-
-/// The merged areas that meet `block`, ordered by the row where they enter it, then by column,
-/// leaving out any that overlaps one kept before it (only a damaged file has overlapping merges;
-/// Excel drops them when it repairs one). One sweep down the rows instead of a scan of every
-/// merge per cell.
-fn block_merges(sh: &Sheet, block: RangeRef) -> Vec<RangeRef> {
-    let top = |m: &RangeRef| m.start.row.max(block.start.row);
-    let mut merges: Vec<RangeRef> = sh.merges.iter().filter(|m| m.intersects(&block)).copied().collect();
-    merges.sort_by_key(|m| (top(m), m.start.col));
-    let mut sweep = MergeSweep::default();
-    merges.retain(|m| sweep.add(*m, top(m)));
-    merges
-}
-
-/// Answers "is this cell inside a merge?" for cells asked in row-major order, from the merges of
-/// [`block_merges`].
-struct Covered<'a> {
-    merges: &'a [RangeRef],
-    top: u32,
-    next: usize,
-    sweep: MergeSweep,
-}
-
-impl<'a> Covered<'a> {
-    fn new(merges: &'a [RangeRef], block: RangeRef) -> Self {
-        Self { merges, top: block.start.row, next: 0, sweep: MergeSweep::default() }
-    }
-
-    fn covers(&mut self, c: CellRef) -> bool {
-        while let Some(m) = self.merges.get(self.next).filter(|m| m.start.row.max(self.top) <= c.row) {
-            self.sweep.add(*m, m.start.row.max(self.top));
-            self.next += 1;
-        }
-        self.sweep.advance(c.row);
-        self.sweep.meets(c.col, c.col)
-    }
-}
-
 /// Draws the cells of a block: fills, gridlines, data bars, borders and text.
 pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Option<crate::cf::CfCache>) {
     let (bx, by) = (b.xs.first().copied().unwrap_or(0.0), b.ys.first().copied().unwrap_or(0.0));
@@ -313,18 +237,17 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
     }
     let block = b.range();
     let sh = b.sh;
-    let merges = block_merges(sh, block);
-    let by_start: std::collections::HashMap<CellRef, RangeRef> = merges.iter().map(|m| (m.start, *m)).collect();
-    // Cells worth visiting, in row-major order (which `Covered` needs).
-    let mut covered = Covered::new(&merges, block);
+    let merges: Vec<RangeRef> = sh.merges.iter().filter(|m| m.intersects(&block)).copied().collect();
+    let covered = |c: CellRef| merges.iter().any(|m| m.contains(c));
+    // Cells worth visiting.
     let cells: Vec<CellRef> = if block.count() <= DENSE_BLOCK {
-        block.iter().filter(|c| !covered.covers(*c)).collect()
+        block.iter().filter(|c| !covered(*c)).collect()
     } else {
         let mut set: Vec<CellRef> = sh.cells.iter_range(block).map(|(c, _)| c).collect();
         set.extend(sh.spill.range(block.start..=block.end).map(|(c, _)| *c).filter(|c| block.contains(*c)));
         set.sort_unstable();
         set.dedup();
-        set.retain(|c| !covered.covers(*c));
+        set.retain(|c| !covered(*c));
         set
     };
     pg.save();
@@ -354,14 +277,14 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
         .filter(|(c, l)| {
             l.fill.is_some()
                 || l.cf.is_some()
-                || by_start.contains_key(c)
+                || merges.iter().any(|m| m.start == *c)
                 || !sh.value(*c).is_empty()
                 || l.style.borders != Borders::default()
                 || l.style.num_fmt.as_str() == "checkbox"
         })
         .collect();
     let rect_of = |c: CellRef| -> (f32, f32, f32, f32, bool) {
-        match by_start.get(&c) {
+        match merges.iter().find(|m| m.start == c) {
             Some(m) => {
                 let (x, y, w, h) = b.rect(*m);
                 (x, y, w, h, true)
@@ -399,7 +322,7 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
             continue;
         }
         let bd = &l.style.borders;
-        let (right, bottom) = match by_start.get(c).filter(|_| merged) {
+        let (right, bottom) = match merges.iter().find(|m| m.start == *c).filter(|_| merged) {
             Some(m) => (
                 b.wb.styles.get(sh.style_id(CellRef::new(m.start.row, m.end.col))).borders.right,
                 b.wb.styles.get(sh.style_id(CellRef::new(m.end.row, m.start.col))).borders.bottom,
@@ -484,12 +407,11 @@ pub(super) struct PrintedBlock {
 pub(super) fn draw_block_links(pg: &mut Page, b: &Block, page: usize, pending: &mut Vec<PendingPdfLink>) {
     let range = b.range();
     let (Some(&bx), Some(&by), Some(&right), Some(&bottom)) = (b.xs.first(), b.ys.first(), b.xs.last(), b.ys.last()) else { return };
-    let by_start: std::collections::HashMap<CellRef, RangeRef> = block_merges(b.sh, range).into_iter().map(|m| (m.start, m)).collect();
     for (cell, link) in b.sh.hyperlinks.range(range.start..=range.end) {
         if !range.contains(*cell) {
             continue;
         }
-        let cell_range = by_start.get(cell).copied().unwrap_or(RangeRef::cell(*cell));
+        let cell_range = b.sh.merges.iter().find(|m| m.start == *cell).copied().unwrap_or(RangeRef::cell(*cell));
         let (x, y, w, h) = b.rect(cell_range);
         let (x0, y0, x1, y1) = (x.max(bx), y.max(by), (x + w).min(right), (y + h).min(bottom));
         if x1 <= x0 || y1 <= y0 {
@@ -581,44 +503,3 @@ pub(super) fn make_block<'a>(
     }
     Block { wb, si, sh, rows, cols, xs, ys, k, scale: lay.scale }
 }
-
-#[cfg(test)]
-mod merge_tests {
-    use super::{CellRef, Covered, RangeRef, Sheet, block_merges};
-
-    fn r(a: &str) -> RangeRef {
-        RangeRef::parse(a).unwrap()
-    }
-
-    #[test]
-    fn block_merges_drop_overlaps_and_cover_like_a_scan() {
-        let mut sh = Sheet::new("S");
-        sh.merges = vec![r("B2:C3"), r("E1:F8"), r("B2:B5"), r("A10:D10"), r("H3:H4"), r("Z1:Z2"), r("C3:D4"), r("A1:A1048576")];
-        let block = r("B1:H12");
-        let merges = block_merges(&sh, block);
-        // B2:B5 and C3:D4 overlap B2:C3, which comes first; Z1:Z2 is outside the block.
-        assert_eq!(merges, vec![r("E1:F8"), r("B2:C3"), r("H3:H4"), r("A10:D10")]);
-        let mut covered = Covered::new(&merges, block);
-        for c in block.iter() {
-            assert_eq!(covered.covers(c), merges.iter().any(|m| m.contains(c)), "{}", c.a1());
-        }
-        // Cells asked sparsely, still in order.
-        let mut covered = Covered::new(&merges, block);
-        for (a, want) in [("C1", false), ("F5", true), ("G5", false), ("D10", true), ("H12", false)] {
-            assert_eq!(covered.covers(CellRef::parse(a).unwrap()), want, "{a}");
-        }
-    }
-
-    #[test]
-    fn many_stacked_merges_are_swept_once() {
-        // 50,000 merges over the same cells: one is kept, and the block is checked against it
-        // without comparing every cell with every merge.
-        let mut sh = Sheet::new("S");
-        sh.merges = (0..50_000u32).map(|i| RangeRef::new(CellRef::new(0, 0), CellRef::new(199, 1 + i % 50))).collect();
-        let block = r("A1:AZ200");
-        let merges = block_merges(&sh, block);
-        assert_eq!(merges, vec![r("A1:B200")]);
-        let mut covered = Covered::new(&merges, block);
-        assert_eq!(block.iter().filter(|c| covered.covers(*c)).count(), 400);
-    }
-}

crates/functions/src/stat/descriptive.rs

@@ -50,12 +50,27 @@ pub(super) fn median(v: Vec<f64>) -> R<f64> {
 
 /// Values occurring at least twice, ordered by first occurrence, with their (equal, maximal) count.
 fn modes(v: &[f64]) -> Vec<f64> {
+    // Index of each distinct number in `counts`, so counting is linear rather than a search of
+    // every distinct number so far. Keyed by bits with -0 folded into 0 (they compare equal); NaN
+    // never equals anything, so it is never merged.
+    let mut index: std::collections::HashMap<u64, usize> = std::collections::HashMap::new();
     let mut counts: Vec<(f64, usize)> = Vec::new();
     for &x in v {
-        if let Some(e) = counts.iter_mut().find(|e| e.0 == x) {
-            e.1 += 1;
-        } else {
+        if x.is_nan() {
             counts.push((x, 1));
+            continue;
+        }
+        let key = if x == 0.0 { 0 } else { x.to_bits() };
+        match index.entry(key) {
+            std::collections::hash_map::Entry::Occupied(e) => {
+                if let Some(c) = counts.get_mut(*e.get()) {
+                    c.1 += 1;
+                }
+            }
+            std::collections::hash_map::Entry::Vacant(e) => {
+                e.insert(counts.len());
+                counts.push((x, 1));
+            }
         }
     }
     let best = counts.iter().map(|e| e.1).max().unwrap_or(0);
@@ -455,7 +470,10 @@ pub(super) fn frequency(a: &[Arg], _: C) -> R<Value> {
     order.sort_by(|&i, &j| bins.get(i).copied().unwrap_or(0.0).total_cmp(&bins.get(j).copied().unwrap_or(0.0)));
     let mut counts = vec![0.0; bins.len() + 1];
     for x in data {
-        let slot = order.iter().find(|&&i| x <= bins.get(i).copied().unwrap_or(f64::INFINITY)).copied().unwrap_or(bins.len());
+        // `order` sorts the bins ascending, so the bins `x` exceeds come first: binary search for
+        // the first bin at or above `x` (the first of equal bins, as a linear scan would find).
+        let pos = order.partition_point(|&i| bins.get(i).copied().unwrap_or(f64::INFINITY) < x);
+        let slot = order.get(pos).copied().unwrap_or(bins.len());
         if let Some(c) = counts.get_mut(slot) {
             *c += 1.0;
         }

crates/functions/src/stat/tests.rs

@@ -617,3 +617,20 @@ fn aggregate_helper() {
     close(aggregate_values_k(9, &vals, &nv(2.0)), 9.0);
     is_err(aggregate_values_k(14, &vals, &nv(10.0)), CellError::Num);
 }
+
+/// Security: FREQUENCY finds each value's bin by binary search, and MODE counts distinct numbers
+/// through an index, so neither is quadratic in its inputs. Results are as before: unsorted and
+/// duplicate bins keep their positions (a value goes to the first of equal bins), and tied modes
+/// come in first-occurrence order.
+#[test]
+fn frequency_and_mode_scale_with_their_inputs() {
+    let f = ev("FREQUENCY", vec![c(&[1.0, 2.0, 2.0, 3.0, 5.0, 9.0, -1.0]), c(&[3.0, 2.0, 2.0, 0.0])]);
+    assert_eq!(rows_of(&f), vec![vec![nv(1.0)], vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)], vec![nv(2.0)]]);
+    let data: Vec<f64> = (0..200_000).map(|i| f64::from(i) + 1e6).collect();
+    let bins: Vec<f64> = (0..200_000).map(f64::from).collect();
+    let f = ev("FREQUENCY", vec![c(&data), c(&bins)]);
+    assert_eq!(rows_of(&f).last(), Some(&vec![nv(200_000.0)]));
+    let distinct = ev("MODE", vec![c(&data)]);
+    is_err(distinct, CellError::NA);
+    assert_eq!(rows_of(&ev("MODE.MULT", vec![c(&[3.0, 0.0, 1.0, -0.0, 3.0, 1.0])])), vec![vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)]]);
+}