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]