This is an automated email from the ASF dual-hosted git repository.

pjfanning pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/poi.git


The following commit(s) were added to refs/heads/trunk by this push:
     new b29564a38b XSSFSheet: index array formula ranges by row block (#1508)
b29564a38b is described below

commit b29564a38b5450510c939d19e1d24fe5b6ea1187
Author: PJ Fanning <[email protected]>
AuthorDate: Thu Oct 29 19:54:32 2026 +0000

    XSSFSheet: index array formula ranges by row block (#1508)
    
    XSSFSheet: index array formula ranges by row block (#1506)
    
    isCellInArrayFormulaContext, getFirstCellInArrayFormula and
    removeArrayFormula scanned every array formula in the sheet, and
    setArrayFormula did a linear contains() check. isFormulaCell() calls
    isCellInArrayFormulaContext, so getCellType() and friends cost
    O(array formulas) per cell, which is quadratic over a sheet with
    many array formulas.
    
    The ranges now live in ArrayFormulaRanges, which registers each range
    against the 64-row blocks it spans and checks only the ranges in the
    cell's block. Indexing per block rather than per cell keeps a large
    array formula from costing one map entry per covered cell. Ranges are
    copied on add so a caller mutating its CellRangeAddress afterwards
    can't corrupt the index.
    
    Co-authored-by: Claude Opus 5.5 <[email protected]>
---
 .../poi/xssf/usermodel/ArrayFormulaRanges.java     | 97 ++++++++++++++++++++++
 .../org/apache/poi/xssf/usermodel/XSSFSheet.java   | 44 ++++------
 .../poi/xssf/usermodel/TestArrayFormulaRanges.java | 97 ++++++++++++++++++++++
 .../TestXSSFSheetUpdateArrayFormulas.java          | 32 +++++++
 4 files changed, 240 insertions(+), 30 deletions(-)

diff --git 
a/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/ArrayFormulaRanges.java 
b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/ArrayFormulaRanges.java
new file mode 100644
index 0000000000..52028b98ea
--- /dev/null
+++ 
b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/ArrayFormulaRanges.java
@@ -0,0 +1,97 @@
+/* ====================================================================
+   Licensed to the Apache Software Foundation (ASF) under one or more
+   contributor license agreements.  See the NOTICE file distributed with
+   this work for additional information regarding copyright ownership.
+   The ASF licenses this file to You under the Apache License, Version 2.0
+   (the "License"); you may not use this file except in compliance with
+   the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+==================================================================== */
+
+package org.apache.poi.xssf.usermodel;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.poi.ss.util.CellRangeAddress;
+
+/**
+ * The ranges of the array formulas in a sheet, indexed so that finding the 
range holding a cell
+ * doesn't need to check every array formula in the sheet.
+ * <p>
+ * Each range is registered against every block of 64 rows that it spans, so a 
lookup only checks
+ * the ranges that share the cell's row block. Indexing by row block rather 
than by cell keeps a
+ * large array formula from costing one entry per cell it covers.
+ */
+final class ArrayFormulaRanges {
+    private static final int ROW_BLOCK_SHIFT = 6;
+
+    private final Set<CellRangeAddress> ranges = new HashSet<>();
+    private final Map<Integer, List<CellRangeAddress>> rowBlocks = new 
HashMap<>();
+
+    /**
+     * Records {@code range}. Does nothing if an equal range is already 
recorded.
+     */
+    void add(CellRangeAddress range) {
+        // copy, so that a caller changing its range later doesn't corrupt the 
index
+        CellRangeAddress copy = range.copy();
+        if (!ranges.add(copy)) {
+            return;
+        }
+        for (int block = firstBlock(copy); block <= lastBlock(copy); block++) {
+            rowBlocks.computeIfAbsent(block, k -> new ArrayList<>()).add(copy);
+        }
+    }
+
+    /**
+     * Forgets {@code range}, which must be one returned by {@link #find(int, 
int)}.
+     */
+    void remove(CellRangeAddress range) {
+        if (!ranges.remove(range)) {
+            return;
+        }
+        for (int block = firstBlock(range); block <= lastBlock(range); 
block++) {
+            List<CellRangeAddress> inBlock = rowBlocks.get(block);
+            if (inBlock != null) {
+                inBlock.remove(range);
+                if (inBlock.isEmpty()) {
+                    rowBlocks.remove(block);
+                }
+            }
+        }
+    }
+
+    /**
+     * @return the earliest recorded range holding the cell, or {@code null} 
if none does
+     */
+    CellRangeAddress find(int rowIndex, int columnIndex) {
+        List<CellRangeAddress> inBlock = rowBlocks.get(rowIndex >> 
ROW_BLOCK_SHIFT);
+        if (inBlock != null) {
+            for (CellRangeAddress range : inBlock) {
+                if (range.isInRange(rowIndex, columnIndex)) {
+                    return range;
+                }
+            }
+        }
+        return null;
+    }
+
+    private static int firstBlock(CellRangeAddress range) {
+        return range.getFirstRow() >> ROW_BLOCK_SHIFT;
+    }
+
+    private static int lastBlock(CellRangeAddress range) {
+        return range.getLastRow() >> ROW_BLOCK_SHIFT;
+    }
+}
diff --git 
a/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFSheet.java 
b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFSheet.java
index 6148e9976c..5b67ff1011 100644
--- a/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFSheet.java
+++ b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFSheet.java
@@ -101,7 +101,7 @@ public class XSSFSheet extends POIXMLDocumentPart 
implements Sheet, OoxmlSheetEx
      */
     private Map<Integer, CTCellFormula> sharedFormulas;
     private SortedMap<String,XSSFTable> tables;
-    private List<CellRangeAddress> arrayFormulas;
+    private ArrayFormulaRanges arrayFormulas;
     private final XSSFDataValidationHelper dataValidationHelper;
     private XSSFVMLDrawing xssfvmlDrawing;
     private CellRangeAddress dimensionOverride;
@@ -200,7 +200,7 @@ public class XSSFSheet extends POIXMLDocumentPart 
implements Sheet, OoxmlSheetEx
         _rows.clear();
         tables = new TreeMap<>();
         sharedFormulas = new HashMap<>();
-        arrayFormulas = new ArrayList<>();
+        arrayFormulas = new ArrayFormulaRanges();
         for (CTRow row : worksheetParam.getSheetData().getRowArray()) {
             XSSFRow r = new XSSFRow(row, this);
             // Performance optimization: explicit boxing is slightly faster 
than auto-unboxing, though may use more memory
@@ -4298,25 +4298,12 @@ public class XSSFSheet extends POIXMLDocumentPart 
implements Sheet, OoxmlSheetEx
     }
 
     /* package */ boolean isCellInArrayFormulaContext(XSSFCell cell) {
-        final int rowIndex = cell.getRowIndex();
-        final int columnIndex = cell.getColumnIndex();
-        for (CellRangeAddress range : arrayFormulas) {
-            if (range.isInRange(rowIndex, columnIndex)) {
-                return true;
-            }
-        }
-        return false;
+        return arrayFormulas.find(cell.getRowIndex(), cell.getColumnIndex()) 
!= null;
     }
 
     /* package */ XSSFCell getFirstCellInArrayFormula(XSSFCell cell) {
-        final int rowIndex = cell.getRowIndex();
-        final int columnIndex = cell.getColumnIndex();
-        for (CellRangeAddress range : arrayFormulas) {
-            if (range.isInRange(rowIndex, columnIndex)) {
-                return 
getRow(range.getFirstRow()).getCell(range.getFirstColumn());
-            }
-        }
-        return null;
+        CellRangeAddress range = arrayFormulas.find(cell.getRowIndex(), 
cell.getColumnIndex());
+        return range == null ? null : 
getRow(range.getFirstRow()).getCell(range.getFirstColumn());
     }
 
     /**
@@ -4352,10 +4339,8 @@ public class XSSFSheet extends POIXMLDocumentPart 
implements Sheet, OoxmlSheetEx
 
         XSSFCell mainArrayFormulaCell = cr.getTopLeftCell();
         mainArrayFormulaCell.setCellArrayFormula(formula, range);
-        // re-entering an array formula over its range replaces it, so don't 
record the range twice
-        if (!arrayFormulas.contains(range)) {
-            arrayFormulas.add(range);
-        }
+        // re-entering an array formula over its range replaces it; add() 
doesn't record the range twice
+        arrayFormulas.add(range);
         return cr;
     }
 
@@ -4364,15 +4349,14 @@ public class XSSFSheet extends POIXMLDocumentPart 
implements Sheet, OoxmlSheetEx
         if (cell.getSheet() != this) {
             throw new IllegalArgumentException("Specified cell does not belong 
to this sheet.");
         }
-        for (CellRangeAddress range : arrayFormulas) {
-            if (range.isInRange(cell)) {
-                arrayFormulas.remove(range);
-                CellRange<XSSFCell> cr = getCellRange(range);
-                for (XSSFCell c : cr) {
-                    c.setBlank();
-                }
-                return cr;
+        CellRangeAddress range = arrayFormulas.find(cell.getRowIndex(), 
cell.getColumnIndex());
+        if (range != null) {
+            arrayFormulas.remove(range);
+            CellRange<XSSFCell> cr = getCellRange(range);
+            for (XSSFCell c : cr) {
+                c.setBlank();
             }
+            return cr;
         }
         String ref = new CellReference(cell).formatAsString();
         throw new IllegalArgumentException("Cell " + ref + " is not part of an 
array formula.");
diff --git 
a/poi-ooxml/src/test/java/org/apache/poi/xssf/usermodel/TestArrayFormulaRanges.java
 
b/poi-ooxml/src/test/java/org/apache/poi/xssf/usermodel/TestArrayFormulaRanges.java
new file mode 100644
index 0000000000..85f26df420
--- /dev/null
+++ 
b/poi-ooxml/src/test/java/org/apache/poi/xssf/usermodel/TestArrayFormulaRanges.java
@@ -0,0 +1,97 @@
+/* ====================================================================
+   Licensed to the Apache Software Foundation (ASF) under one or more
+   contributor license agreements.  See the NOTICE file distributed with
+   this work for additional information regarding copyright ownership.
+   The ASF licenses this file to You under the Apache License, Version 2.0
+   (the "License"); you may not use this file except in compliance with
+   the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+==================================================================== */
+
+package org.apache.poi.xssf.usermodel;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+
+import org.apache.poi.ss.util.CellRangeAddress;
+import org.junit.jupiter.api.Test;
+
+final class TestArrayFormulaRanges {
+
+    @Test
+    void findsRangeHoldingCell() {
+        ArrayFormulaRanges ranges = new ArrayFormulaRanges();
+        ranges.add(CellRangeAddress.valueOf("B2:C3"));
+        ranges.add(CellRangeAddress.valueOf("E2"));
+
+        assertEquals(CellRangeAddress.valueOf("B2:C3"), ranges.find(1, 1));
+        assertEquals(CellRangeAddress.valueOf("B2:C3"), ranges.find(2, 2));
+        assertEquals(CellRangeAddress.valueOf("E2"), ranges.find(1, 4));
+        assertNull(ranges.find(0, 1), "row above the range");
+        assertNull(ranges.find(1, 3), "column between the ranges");
+        assertNull(ranges.find(3, 1), "row below the range");
+    }
+
+    @Test
+    void findsRangeSpanningRowBlocks() {
+        ArrayFormulaRanges ranges = new ArrayFormulaRanges();
+        // rows 50 to 300 cross several 64-row blocks
+        CellRangeAddress tall = CellRangeAddress.valueOf("A51:B301");
+        ranges.add(tall);
+
+        for (int row = 50; row <= 300; row++) {
+            assertEquals(tall, ranges.find(row, 0));
+            assertEquals(tall, ranges.find(row, 1));
+        }
+        assertNull(ranges.find(49, 0));
+        assertNull(ranges.find(301, 0));
+        assertNull(ranges.find(100, 2));
+
+        ranges.remove(tall);
+        for (int row = 50; row <= 300; row++) {
+            assertNull(ranges.find(row, 0));
+        }
+    }
+
+    @Test
+    void removeOnlyForgetsThatRange() {
+        ArrayFormulaRanges ranges = new ArrayFormulaRanges();
+        ranges.add(CellRangeAddress.valueOf("A1:A100"));
+        ranges.add(CellRangeAddress.valueOf("B10:B20"));
+
+        ranges.remove(ranges.find(15, 0));
+
+        assertNull(ranges.find(15, 0));
+        assertEquals(CellRangeAddress.valueOf("B10:B20"), ranges.find(15, 1));
+    }
+
+    @Test
+    void addingAnEqualRangeTwiceRecordsItOnce() {
+        ArrayFormulaRanges ranges = new ArrayFormulaRanges();
+        ranges.add(CellRangeAddress.valueOf("A1:A2"));
+        ranges.add(CellRangeAddress.valueOf("A1:A2"));
+
+        ranges.remove(CellRangeAddress.valueOf("A1:A2"));
+
+        assertNull(ranges.find(0, 0));
+    }
+
+    @Test
+    void laterChangesToTheAddedRangeAreIgnored() {
+        ArrayFormulaRanges ranges = new ArrayFormulaRanges();
+        CellRangeAddress range = CellRangeAddress.valueOf("A1:A2");
+        ranges.add(range);
+
+        range.setLastRow(500);
+
+        assertEquals(CellRangeAddress.valueOf("A1:A2"), ranges.find(1, 0));
+        assertNull(ranges.find(400, 0));
+    }
+}
diff --git 
a/poi-ooxml/src/test/java/org/apache/poi/xssf/usermodel/TestXSSFSheetUpdateArrayFormulas.java
 
b/poi-ooxml/src/test/java/org/apache/poi/xssf/usermodel/TestXSSFSheetUpdateArrayFormulas.java
index 9217a2f431..2bcbc3700d 100644
--- 
a/poi-ooxml/src/test/java/org/apache/poi/xssf/usermodel/TestXSSFSheetUpdateArrayFormulas.java
+++ 
b/poi-ooxml/src/test/java/org/apache/poi/xssf/usermodel/TestXSSFSheetUpdateArrayFormulas.java
@@ -22,6 +22,7 @@ import static org.junit.jupiter.api.Assertions.assertFalse;
 import static org.junit.jupiter.api.Assertions.assertNotNull;
 import static org.junit.jupiter.api.Assertions.assertNull;
 import static org.junit.jupiter.api.Assertions.assertSame;
+import static org.junit.jupiter.api.Assertions.assertTrue;
 
 import java.io.IOException;
 
@@ -29,6 +30,7 @@ import 
org.apache.poi.ss.usermodel.BaseTestSheetUpdateArrayFormulas;
 import org.apache.poi.ss.usermodel.CellRange;
 import org.apache.poi.ss.util.CellRangeAddress;
 import org.apache.poi.xssf.XSSFITestDataProvider;
+import org.apache.poi.xssf.XSSFTestDataSamples;
 import org.junit.jupiter.api.Test;
 import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTCell;
 import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTCellFormula;
@@ -96,6 +98,36 @@ public final class TestXSSFSheetUpdateArrayFormulas extends 
BaseTestSheetUpdateA
         workbook.close();
     }
 
+    @Test
+    void testManyArrayFormulas() throws IOException {
+        try (XSSFWorkbook workbook = new XSSFWorkbook()) {
+            XSSFSheet sheet = workbook.createSheet();
+            // one 2-row array formula per pair of rows in column B, plus a 
tall one in column D
+            for (int row = 0; row < 1000; row += 2) {
+                sheet.setArrayFormula("1", new CellRangeAddress(row, row + 1, 
1, 1));
+            }
+            sheet.setArrayFormula("2", CellRangeAddress.valueOf("D1:D1000"));
+
+            try (XSSFWorkbook read = 
XSSFTestDataSamples.writeOutAndReadBack(workbook)) {
+                XSSFSheet readSheet = read.getSheetAt(0);
+                for (int row = 0; row < 1000; row++) {
+                    XSSFCell cell = readSheet.getRow(row).getCell(1);
+                    assertTrue(cell.isPartOfArrayFormulaGroup());
+                    int firstRow = row - row % 2;
+                    assertEquals(new CellRangeAddress(firstRow, firstRow + 1, 
1, 1), cell.getArrayFormulaRange());
+                    assertEquals("D1:D1000", 
readSheet.getRow(row).getCell(3).getArrayFormulaRange().formatAsString());
+                }
+                
assertFalse(readSheet.getRow(500).createCell(2).isPartOfArrayFormulaGroup());
+
+                readSheet.removeArrayFormula(readSheet.getRow(501).getCell(1));
+                
assertFalse(readSheet.getRow(500).getCell(1).isPartOfArrayFormulaGroup());
+                
assertFalse(readSheet.getRow(501).getCell(1).isPartOfArrayFormulaGroup());
+                
assertTrue(readSheet.getRow(502).getCell(1).isPartOfArrayFormulaGroup());
+                
assertTrue(readSheet.getRow(501).getCell(3).isPartOfArrayFormulaGroup());
+            }
+        }
+    }
+
     private static void confirmArrayFormulaCell(XSSFCell c, String cellRef) {
         confirmArrayFormulaCell(c, cellRef, null, null);
     }


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to