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.

git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@1513225 13f79535-47bb-0310-9956-ffa450edef68

4 files changed, 129 insertions, 142 deletions

diff --git a/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java b/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java
index b795d02288..d1532a94d6 100644
--- a/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java
+++ b/src/java/org/apache/poi/hssf/record/cf/CellRangeUtil.java
@@ -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)
+
+	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;
 
-		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;
-			}
-		}
-		
+            // 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.
diff --git a/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java b/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java
index 12aaa6f629..ffb6e530bb 100644
--- a/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java
+++ b/src/java/org/apache/poi/ss/util/CellRangeAddressBase.java
@@ -152,7 +152,8 @@ public abstract class CellRangeAddressBase {
 		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() +"]";
diff --git a/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java b/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java
index b13c6fd249..f01a2a3912 100644
--- a/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java
+++ b/src/testcases/org/apache/poi/hssf/record/cf/TestCellRange.java
@@ -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 TestCase
 		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 TestCase
 	}
 
     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());
diff --git a/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java b/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java
index 550dd03c13..5c6af7b261 100644
--- a/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java
+++ b/src/testcases/org/apache/poi/ss/usermodel/BaseTestConditionalFormatting.java
@@ -686,6 +686,15 @@ public abstract class BaseTestConditionalFormatting extends TestCase {
         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);        

     }

 }