Author: centic
Date: Mon Aug 12 19:13:10 2013
New Revision: 1513225
URL: http://svn.apache.org/r1513225
Log:
Bug 55380: Fix endless loop in CellRangeUtil.mergeCellRanges() by not trying to
merge overlapping regions any more, the implementation is buggy and even tagged
TODO - unit test missing. The code is hard to understand and bug-free-ness is
better than catching all possible merges imho.
Also add many cases to the unit tests and reformat code slightly as well
as fixing some Generics-Warnings.
Modified:
poi/trunk/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java
poi/trunk/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java
poi/trunk/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java
poi/trunk/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java
Modified: poi/trunk/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java
URL:
http://svn.apache.org/viewvc/poi/trunk/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java?rev=1513225&r1=1513224&r2=1513225&view=diff
==============================================================================
--- poi/trunk/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java
(original)
+++ poi/trunk/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java Mon Aug
12 19:13:10 2013
@@ -97,45 +97,47 @@ public final class CellRangeUtil
}
List<CellRangeAddress> lst = new ArrayList<CellRangeAddress>();
- for(CellRangeAddress cr : cellRanges) lst.add(cr);
- List temp = mergeCellRanges(lst);
+ for(CellRangeAddress cr : cellRanges) {
+ lst.add(cr);
+ }
+ List<CellRangeAddress> temp = mergeCellRanges(lst);
return toArray(temp);
}
- private static List mergeCellRanges(List cellRangeList)
- {
- while(cellRangeList.size() > 1)
- {
- boolean somethingGotMerged = false;
-
- for( int i=0; i<cellRangeList.size(); i++)
- {
- CellRangeAddress range1 =
(CellRangeAddress)cellRangeList.get(i);
- for( int j=i+1; j<cellRangeList.size(); j++)
- {
- CellRangeAddress range2 =
(CellRangeAddress)cellRangeList.get(j);
-
- CellRangeAddress[] mergeResult =
mergeRanges(range1, range2);
- if(mergeResult == null) {
- continue;
- }
- somethingGotMerged = true;
- // overwrite range1 with first result
- cellRangeList.set(i, mergeResult[0]);
- // remove range2
- cellRangeList.remove(j--);
- // add any extra results beyond the
first
- for(int k=1; k<mergeResult.length; k++)
{
- j++;
- cellRangeList.add(j,
mergeResult[k]);
- }
- }
- }
- if(!somethingGotMerged) {
- break;
- }
- }
-
+ private static List<CellRangeAddress>
mergeCellRanges(List<CellRangeAddress> cellRangeList)
+ {
+ // loop until either only one item is left or we did not merge
anything any more
+ while (cellRangeList.size() > 1) {
+ boolean somethingGotMerged = false;
+
+ // look at all cell-ranges
+ for (int i = 0; i < cellRangeList.size(); i++) {
+ CellRangeAddress range1 = cellRangeList.get(i);
+
+ // compare each cell range to all other cell-ranges
+ for (int j = i + 1; j < cellRangeList.size(); j++) {
+ CellRangeAddress range2 = cellRangeList.get(j);
+
+ CellRangeAddress[] mergeResult = mergeRanges(range1,
range2);
+ if (mergeResult == null) {
+ continue;
+ }
+ somethingGotMerged = true;
+ // overwrite range1 with first result
+ cellRangeList.set(i, mergeResult[0]);
+ // remove range2
+ cellRangeList.remove(j--);
+ // add any extra results beyond the first
+ for (int k = 1; k < mergeResult.length; k++) {
+ j++;
+ cellRangeList.add(j, mergeResult[k]);
+ }
+ }
+ }
+ if (!somethingGotMerged) {
+ break;
+ }
+ }
return cellRangeList;
}
@@ -144,122 +146,33 @@ public final class CellRangeUtil
* @return the new range(s) to replace the supplied ones.
<code>null</code> if no merge is possible
*/
private static CellRangeAddress[] mergeRanges(CellRangeAddress range1,
CellRangeAddress range2) {
-
int x = intersect(range1, range2);
switch(x)
{
case CellRangeUtil.NO_INTERSECTION:
+ // nothing in common: at most they could be
adjacent to each other and thus form a single bigger area
if(hasExactSharedBorder(range1, range2)) {
return new CellRangeAddress[] {
createEnclosingCellRange(range1, range2), };
}
// else - No intersection and no shared border:
do nothing
return null;
case CellRangeUtil.OVERLAP:
- return resolveRangeOverlap(range1, range2);
+ // commented out the cells overlap implementation,
it caused endless loops, see Bug 55380
+ // disabled for now, the algorithm will not detect
some border cases this way currently!
+ //return resolveRangeOverlap(range1, range2);
+ return null;
case CellRangeUtil.INSIDE:
// Remove range2, since it is completely inside
of range1
- return new CellRangeAddress[] { range1, };
+ return new CellRangeAddress[] { range1 };
case CellRangeUtil.ENCLOSES:
// range2 encloses range1, so replace it with
the enclosing one
- return new CellRangeAddress[] { range2, };
+ return new CellRangeAddress[] { range2 };
}
throw new RuntimeException("unexpected intersection result (" +
x + ")");
}
-
- // TODO - write junit test for this
- static CellRangeAddress[] resolveRangeOverlap(CellRangeAddress rangeA,
CellRangeAddress rangeB) {
-
- if(rangeA.isFullColumnRange()) {
- if(rangeA.isFullRowRange()) {
- // Excel seems to leave these unresolved
- return null;
- }
- return sliceUp(rangeA, rangeB);
- }
- if(rangeA.isFullRowRange()) {
- if(rangeB.isFullColumnRange()) {
- // Excel seems to leave these unresolved
- return null;
- }
- return sliceUp(rangeA, rangeB);
- }
- if(rangeB.isFullColumnRange()) {
- return sliceUp(rangeB, rangeA);
- }
- if(rangeB.isFullRowRange()) {
- return sliceUp(rangeB, rangeA);
- }
- return sliceUp(rangeA, rangeB);
- }
- /**
- * @param crB never a full row or full column range
- * @return an array including <b>this</b> <tt>CellRange</tt> and all
parts of <tt>range</tt>
- * outside of this range
- */
- private static CellRangeAddress[] sliceUp(CellRangeAddress crA,
CellRangeAddress crB) {
-
- List temp = new ArrayList();
-
- // Chop up range horizontally and vertically
- temp.add(crB);
- if(!crA.isFullColumnRange()) {
- temp = cutHorizontally(crA.getFirstRow(), temp);
- temp = cutHorizontally(crA.getLastRow()+1, temp);
- }
- if(!crA.isFullRowRange()) {
- temp = cutVertically(crA.getFirstColumn(), temp);
- temp = cutVertically(crA.getLastColumn()+1, temp);
- }
- CellRangeAddress[] crParts = toArray(temp);
-
- // form result array
- temp.clear();
- temp.add(crA);
-
- for (int i = 0; i < crParts.length; i++) {
- CellRangeAddress crPart = crParts[i];
- // only include parts that are not enclosed by this
- if(intersect(crA, crPart) != ENCLOSES) {
- temp.add(crPart);
- }
- }
- return toArray(temp);
- }
-
- private static List cutHorizontally(int cutRow, List input) {
-
- List result = new ArrayList();
- CellRangeAddress[] crs = toArray(input);
- for (int i = 0; i < crs.length; i++) {
- CellRangeAddress cr = crs[i];
- if(cr.getFirstRow() < cutRow && cutRow <
cr.getLastRow()) {
- result.add(new
CellRangeAddress(cr.getFirstRow(), cutRow, cr.getFirstColumn(),
cr.getLastColumn()));
- result.add(new CellRangeAddress(cutRow+1,
cr.getLastRow(), cr.getFirstColumn(), cr.getLastColumn()));
- } else {
- result.add(cr);
- }
- }
- return result;
- }
- private static List cutVertically(int cutColumn, List input) {
-
- List result = new ArrayList();
- CellRangeAddress[] crs = toArray(input);
- for (int i = 0; i < crs.length; i++) {
- CellRangeAddress cr = crs[i];
- if(cr.getFirstColumn() < cutColumn && cutColumn <
cr.getLastColumn()) {
- result.add(new
CellRangeAddress(cr.getFirstRow(), cr.getLastRow(), cr.getFirstColumn(),
cutColumn));
- result.add(new
CellRangeAddress(cr.getFirstRow(), cr.getLastRow(), cutColumn+1,
cr.getLastColumn()));
- } else {
- result.add(cr);
- }
- }
- return result;
- }
-
-
- private static CellRangeAddress[] toArray(List temp) {
+
+ private static CellRangeAddress[] toArray(List<CellRangeAddress> temp) {
CellRangeAddress[] result = new CellRangeAddress[temp.size()];
temp.toArray(result);
return result;
@@ -284,7 +197,7 @@ public final class CellRangeUtil
}
/**
- * Check if the specified cell range has a shared border with the
current range.
+ * Check if the two cell ranges have a shared border.
*
* @return <code>true</code> if the ranges have a complete shared border
(i.e.
* the two ranges together make a simple rectangular region.
Modified: poi/trunk/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java
URL:
http://svn.apache.org/viewvc/poi/trunk/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java?rev=1513225&r1=1513224&r2=1513225&view=diff
==============================================================================
--- poi/trunk/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java
(original)
+++ poi/trunk/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java Mon Aug
12 19:13:10 2013
@@ -152,7 +152,8 @@ public abstract class CellRangeAddressBa
return (_lastRow - _firstRow + 1) * (_lastCol - _firstCol + 1);
}
- public final String toString() {
+ @Override
+ public final String toString() {
CellReference crA = new CellReference(_firstRow, _firstCol);
CellReference crB = new CellReference(_lastRow, _lastCol);
return getClass().getName() + " [" + crA.formatAsString() + ":"
+ crB.formatAsString() +"]";
Modified:
poi/trunk/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java
URL:
http://svn.apache.org/viewvc/poi/trunk/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java?rev=1513225&r1=1513224&r2=1513225&view=diff
==============================================================================
--- poi/trunk/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java
(original)
+++ poi/trunk/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java
Mon Aug 12 19:13:10 2013
@@ -17,11 +17,13 @@ limitations under the License.
package org.apache.poi.hssf.record.cf;
-import org.apache.poi.ss.util.CellRangeAddress;
+import java.util.Arrays;
import junit.framework.AssertionFailedError;
import junit.framework.TestCase;
+import org.apache.poi.ss.util.CellRangeAddress;
+
/**
* Tests CellRange operations.
*/
@@ -150,6 +152,10 @@ public final class TestCellRange extends
assertEquals(CellRangeUtil.OVERLAP,
CellRangeUtil.intersect(tenthRow, tenthColumn));
assertEquals(CellRangeUtil.INSIDE,
CellRangeUtil.intersect(tenthColumn, tenthColumn));
assertEquals(CellRangeUtil.INSIDE,
CellRangeUtil.intersect(tenthRow, tenthRow));
+
+ // Bug 55380
+ assertEquals(CellRangeUtil.OVERLAP, CellRangeUtil.intersect(
+ CellRangeAddress.valueOf("C1:D2"),
CellRangeAddress.valueOf("C2:C3")));
}
/**
@@ -186,13 +192,71 @@ public final class TestCellRange extends
}
public void testMergeCellRanges() {
- CellRangeAddress cr1 = CellRangeAddress.valueOf("A1:B1");
- CellRangeAddress cr2 = CellRangeAddress.valueOf("A2:B2");
- CellRangeAddress[] cr3 = CellRangeUtil.mergeCellRanges(new
CellRangeAddress[]{cr1, cr2});
- assertEquals(1, cr3.length);
- assertEquals("A1:B2", cr3[0].formatAsString());
+ // no result on empty
+ cellRangeTest(new String[]{ });
+
+ // various cases with two ranges
+ cellRangeTest(new String[]{"A1:B1", "A2:B2"}, "A1:B2");
+ cellRangeTest(new String[]{"A1:B1" }, "A1:B1");
+ cellRangeTest(new String[]{"A1:B2", "A2:B2"}, "A1:B2");
+ cellRangeTest(new String[]{"A1:B3", "A2:B2"}, "A1:B3");
+ cellRangeTest(new String[]{"A1:C1", "A2:B2"}, new String[] {"A1:C1",
"A2:B2"});
+
+ // cases with three ranges
+ cellRangeTest(new String[]{"A1:A1", "A2:B2", "A1:C1"}, new String[]
{"A1:C1", "A2:B2"});
+ cellRangeTest(new String[]{"A1:C1", "A2:B2", "A1:A1"}, new String[]
{"A1:C1", "A2:B2"});
+
+ // "standard" cases
+ // enclose
+ cellRangeTest(new String[]{"A1:D4", "B2:C3"}, new String[] {"A1:D4"});
+ // inside
+ cellRangeTest(new String[]{"B2:C3", "A1:D4"}, new String[] {"A1:D4"});
+ cellRangeTest(new String[]{"B2:C3", "A1:D4"}, new String[] {"A1:D4"});
+ // disjunct
+ cellRangeTest(new String[]{"A1:B2", "C3:D4"}, new String[] {"A1:B2",
"C3:D4"});
+ cellRangeTest(new String[]{"A1:B2", "A3:D4"}, new String[] {"A1:B2",
"A3:D4"});
+ // overlap that cannot be merged
+ cellRangeTest(new String[]{"C1:D2", "C2:C3"}, new String[] {"C1:D2",
"C2:C3"});
+ // overlap which could theoretically be merged, but isn't because the
implementation was buggy and therefore was removed
+ cellRangeTest(new String[]{"A1:C3", "B1:D3"}, new String[] {"A1:C3",
"B1:D3"}); // could be one region "A1:D3"
+ cellRangeTest(new String[]{"A1:C3", "B1:D1"}, new String[] {"A1:C3",
"B1:D1"}); // could be one region "A1:D3"
}
+ public void testMergeCellRanges55380() {
+ cellRangeTest(new String[]{"C1:D2", "C2:C3"}, new String[] {"C1:D2",
"C2:C3"});
+ cellRangeTest(new String[]{"A1:C3", "B2:D2"}, new String[] {"A1:C3",
"B2:D2"});
+ cellRangeTest(new String[]{"C9:D30", "C7:C31"}, new String[]
{"C9:D30", "C7:C31"});
+ }
+
+// public void testResolveRangeOverlap() {
+// resolveRangeOverlapTest("C1:D2", "C2:C3");
+// }
+
+ private void cellRangeTest(String[] input, String... expectedOutput) {
+ CellRangeAddress[] inputArr = new CellRangeAddress[input.length];
+ for(int i = 0;i < input.length;i++) {
+ inputArr[i] = CellRangeAddress.valueOf(input[i]);
+ }
+ CellRangeAddress[] result = CellRangeUtil.mergeCellRanges(inputArr);
+ verifyExpectedResult(result, expectedOutput);
+ }
+
+// private void resolveRangeOverlapTest(String a, String b,
String...expectedOutput) {
+// CellRangeAddress rangeA = CellRangeAddress.valueOf(a);
+// CellRangeAddress rangeB = CellRangeAddress.valueOf(b);
+// CellRangeAddress[] result =
CellRangeUtil.resolveRangeOverlap(rangeA, rangeB);
+// verifyExpectedResult(result, expectedOutput);
+// }
+
+ private void verifyExpectedResult(CellRangeAddress[] result, String...
expectedOutput) {
+ assertEquals("\nExpected: " + Arrays.toString(expectedOutput) +
"\nHad: " + Arrays.toString(result),
+ expectedOutput.length, result.length);
+ for(int i = 0;i < expectedOutput.length;i++) {
+ assertEquals("\nExpected: " + Arrays.toString(expectedOutput) +
"\nHad: " + Arrays.toString(result),
+ expectedOutput[i], result[i].formatAsString());
+ }
+ }
+
public void testValueOf() {
CellRangeAddress cr1 = CellRangeAddress.valueOf("A1:B1");
assertEquals(0, cr1.getFirstColumn());
Modified:
poi/trunk/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java
URL:
http://svn.apache.org/viewvc/poi/trunk/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java?rev=1513225&r1=1513224&r2=1513225&view=diff
==============================================================================
---
poi/trunk/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java
(original)
+++
poi/trunk/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java
Mon Aug 12 19:13:10 2013
@@ -686,6 +686,15 @@ public abstract class BaseTestConditiona
assertEquals(BorderFormatting.BORDER_THICK, r1fp.getBorderTop());
assertEquals(BorderFormatting.BORDER_THIN, r1fp.getBorderLeft());
assertEquals(BorderFormatting.BORDER_HAIR, r1fp.getBorderRight());
-
+ }
+
+ public void testBug55380() {
+ Workbook wb = _testDataProvider.createWorkbook();
+ Sheet sheet = wb.createSheet();
+ CellRangeAddress[] ranges = new CellRangeAddress[] {
+ CellRangeAddress.valueOf("C9:D30"),
CellRangeAddress.valueOf("C7:C31")
+ };
+ ConditionalFormattingRule rule =
sheet.getSheetConditionalFormatting().createConditionalFormattingRule("$A$1>0");
+ sheet.getSheetConditionalFormatting().addConditionalFormatting(ranges,
rule);
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
