poi-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From cen...@apache.org
Subject svn commit: r1513225 - in /poi/trunk/src: java/org/apache/poi/hssf/record/cf/ java/org/apache/poi/ss/util/ testcases/org/apache/poi/hssf/record/cf/ testcases/org/apache/poi/ss/usermodel/
Date Mon, 12 Aug 2013 19:13:10 GMT
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: commits-unsubscribe@poi.apache.org
For additional commands, e-mail: commits-help@poi.apache.org


Mime
View raw message