Fix for https://bz.apache.org/bugzilla/show_bug.cgi?id=58466

ColumnHelper now preserves information on multiple changes to the same group, hopefully while preserving the faster implementation intended by the original patch.

NB changes to TestXSSFSheet: the behaviour of column group collapsing/expanding is now closer to what Excel does than before.

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

3 files changed, 192 insertions, 131 deletions

diff --git a/src/ooxml/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java b/src/ooxml/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java
index 74d9ef3994..285ff014a9 100644
--- a/src/ooxml/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java
+++ b/src/ooxml/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java
@@ -19,15 +19,13 @@ package org.apache.poi.xssf.usermodel.helpers;
 
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.HashSet;
-import java.util.Iterator;
 import java.util.List;
-import java.util.ListIterator;
-import java.util.Set;
+import java.util.NavigableSet;
 import java.util.TreeSet;
 
 import org.apache.poi.ss.usermodel.CellStyle;
 import org.apache.poi.xssf.util.CTColComparator;
+import org.apache.poi.xssf.util.NumericRanges;
 import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTCol;
 import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTCols;
 import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTWorksheet;
@@ -41,7 +39,6 @@ import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTWorksheet;
 public class ColumnHelper {
 
     private CTWorksheet worksheet;
-    private CTCols newCols;
 
     public ColumnHelper(CTWorksheet worksheet) {
         super();
@@ -51,107 +48,112 @@ public class ColumnHelper {
     
     @SuppressWarnings("deprecation")
     public void cleanColumns() {
-        this.newCols = CTCols.Factory.newInstance();
-
-        CTCols aggregateCols = CTCols.Factory.newInstance();
+        TreeSet<CTCol> trackedCols = new TreeSet<CTCol>(CTColComparator.BY_MIN_MAX);
+        CTCols newCols = CTCols.Factory.newInstance();
         CTCols[] colsArray = worksheet.getColsArray();
-        assert(colsArray != null);
-        
-        for (CTCols cols : colsArray) {
-            for (CTCol col : cols.getColArray()) {
-                cloneCol(aggregateCols, col);
+        int i = 0;
+        for (i = 0; i < colsArray.length; i++) {
+            CTCols cols = colsArray[i];
+            CTCol[] colArray = cols.getColArray();
+            for (CTCol col : colArray) {
+                addCleanColIntoCols(newCols, col, trackedCols);
             }
         }
-        
-        sortColumns(aggregateCols);
-        
-        CTCol[] colArray = aggregateCols.getColArray();
-        sweepCleanColumns(newCols, colArray, null);
-        
-        int i = colsArray.length;
         for (int y = i - 1; y >= 0; y--) {
             worksheet.removeCols(y);
         }
+        
+        newCols.setColArray(trackedCols.toArray(new CTCol[trackedCols.size()]));
         worksheet.addNewCols();
         worksheet.setColsArray(0, newCols);
     }
 
-    /**
-     * @see <a href="http://en.wikipedia.org/wiki/Sweep_line_algorithm">Sweep line algorithm</a>
-     */
-    private void sweepCleanColumns(CTCols cols, CTCol[] flattenedColsArray, CTCol overrideColumn) {
-        List<CTCol> flattenedCols = new ArrayList<CTCol>(Arrays.asList(flattenedColsArray));
-        TreeSet<CTCol> currentElements = new TreeSet<CTCol>(CTColComparator.BY_MAX);
-        ListIterator<CTCol> flIter = flattenedCols.listIterator();
-        CTCol haveOverrideColumn = null;
-        long lastMaxIndex = 0;
-        long currentMax = 0;
-        while (flIter.hasNext()) {
-            CTCol col = flIter.next();
-            long currentIndex = col.getMin();
-            long colMax = col.getMax();
-            long nextIndex = (colMax > currentMax) ? colMax : currentMax;
-            if (flIter.hasNext()) {
-                nextIndex = flIter.next().getMin();
-                flIter.previous();
+    public CTCols addCleanColIntoCols(CTCols cols, CTCol newCol) {
+        // Performance issue. If we encapsulated management of min/max in this
+        // class then we could keep trackedCols as state,
+        // making this log(N) rather than Nlog(N). We do this for the initial
+        // read above.
+        TreeSet<CTCol> trackedCols = new TreeSet<CTCol>(
+                CTColComparator.BY_MIN_MAX);
+        trackedCols.addAll(cols.getColList());
+        addCleanColIntoCols(cols, newCol, trackedCols);
+        cols.setColArray(trackedCols.toArray(new CTCol[0]));
+        return cols;
+    }
+
+    private void addCleanColIntoCols(final CTCols cols, final CTCol newCol, final TreeSet<CTCol> trackedCols) {
+        List<CTCol> overlapping = getOverlappingCols(newCol, trackedCols);
+        if (overlapping.isEmpty()) {
+            trackedCols.add(cloneCol(cols, newCol));
+            return;
+        }
+
+        trackedCols.removeAll(overlapping);
+        for (CTCol existing : overlapping) {
+            // We add up to three columns for each existing one: non-overlap
+            // before, overlap, non-overlap after.
+            long[] overlap = getOverlap(newCol, existing);
+
+            CTCol overlapCol = cloneCol(cols, existing, overlap);
+            setColumnAttributes(newCol, overlapCol);
+            trackedCols.add(overlapCol);
+
+            CTCol beforeCol = existing.getMin() < newCol.getMin() ? existing
+                    : newCol;
+            long[] before = new long[] {
+                    Math.min(existing.getMin(), newCol.getMin()),
+                    overlap[0] - 1 };
+            if (before[0] <= before[1]) {
+                trackedCols.add(cloneCol(cols, beforeCol, before));
             }
-            Iterator<CTCol> iter = currentElements.iterator();
-            while (iter.hasNext()) {
-                CTCol elem = iter.next();
-                if (currentIndex <= elem.getMax()) break; // all passed elements have been purged
-                iter.remove();
+
+            CTCol afterCol = existing.getMax() > newCol.getMax() ? existing
+                    : newCol;
+            long[] after = new long[] { overlap[1] + 1,
+                    Math.max(existing.getMax(), newCol.getMax()) };
+            if (after[0] <= after[1]) {
+                trackedCols.add(cloneCol(cols, afterCol, after));
             }
-            if (!currentElements.isEmpty() && lastMaxIndex < currentIndex) {
-                // we need to process previous elements first
-                insertCol(cols, lastMaxIndex, currentIndex - 1, currentElements.toArray(new CTCol[currentElements.size()]), true, haveOverrideColumn);
+        }
+    }
+
+    private CTCol cloneCol(final CTCols cols, final CTCol col, final long[] newRange) {
+        CTCol cloneCol = cloneCol(cols, col);
+        cloneCol.setMin(newRange[0]);
+        cloneCol.setMax(newRange[1]);
+        return cloneCol;
+    }
+
+    private long[] getOverlap(final CTCol col1, final CTCol col2) {
+        return getOverlappingRange(col1, col2);
+    }
+
+    private List<CTCol> getOverlappingCols(final CTCol newCol, final TreeSet<CTCol> trackedCols) {
+        CTCol lower = trackedCols.lower(newCol);
+        NavigableSet<CTCol> potentiallyOverlapping = lower == null ? trackedCols : trackedCols.tailSet(lower, overlaps(lower, newCol));
+        List<CTCol> overlapping = new ArrayList<CTCol>();
+        for (CTCol existing : potentiallyOverlapping) {
+            if (overlaps(newCol, existing)) {
+                overlapping.add(existing);
+            } else {
+                break;
             }
-            currentElements.add(col);
-            if (colMax > currentMax) currentMax = colMax;
-            if (col.equals(overrideColumn)) haveOverrideColumn = overrideColumn;
-            while (currentIndex <= nextIndex && !currentElements.isEmpty()) {
-                Set<CTCol> currentIndexElements = new HashSet<CTCol>();
-                long currentElemIndex;
-                
-                {
-                    // narrow scope of currentElem
-                    CTCol currentElem = currentElements.first();
-                    currentElemIndex = currentElem.getMax();
-                    currentIndexElements.add(currentElem);
-
-                    while (true) {
-                        CTCol higherElem = currentElements.higher(currentElem);
-                        if (higherElem == null || higherElem.getMax() != currentElemIndex)
-                            break;
-                        currentElem = higherElem;
-                        currentIndexElements.add(currentElem);
-                        if (colMax > currentMax) currentMax = colMax;
-                        if (col.equals(overrideColumn)) haveOverrideColumn = overrideColumn;
-                    }
-                }
-                
-                
-                if (currentElemIndex < nextIndex || !flIter.hasNext()) {
-                    insertCol(cols, currentIndex, currentElemIndex, currentElements.toArray(new CTCol[currentElements.size()]), true, haveOverrideColumn);
-                    if (flIter.hasNext()) {
-                        if (nextIndex > currentElemIndex) {
-                            currentElements.removeAll(currentIndexElements);
-                            if (currentIndexElements.contains(overrideColumn)) haveOverrideColumn = null;
-                        }
-                    } else {
-                        currentElements.removeAll(currentIndexElements);
-                        if (currentIndexElements.contains(overrideColumn)) haveOverrideColumn = null;
-                    }
-                    lastMaxIndex = currentIndex = currentElemIndex + 1;
-                } else {
-                    lastMaxIndex = currentIndex;
-                    currentIndex = nextIndex + 1;
-                }
-                
-            }        
         }
-        sortColumns(cols);
+        return overlapping;
+    }
+
+    private boolean overlaps(final CTCol col1, final CTCol col2) {
+        return NumericRanges.getOverlappingType(toRange(col1), toRange(col2)) != NumericRanges.NO_OVERLAPS;
     }
 
+    private long[] getOverlappingRange(final CTCol col1, final CTCol col2) {
+        return NumericRanges.getOverlappingRange(toRange(col1), toRange(col2));
+    }
+
+    private long[] toRange(final CTCol col) {
+        return new long[] { col.getMin(), col.getMax() };
+    }
+    
     @SuppressWarnings("deprecation")
     public static void sortColumns(CTCols newCols) {
         CTCol[] colArray = newCols.getColArray();
@@ -208,22 +210,6 @@ public class ColumnHelper {
         return null;
     }
 
-    @SuppressWarnings("deprecation")
-    public CTCols addCleanColIntoCols(CTCols cols, CTCol col) {
-        CTCols newCols = CTCols.Factory.newInstance();
-        for (CTCol c : cols.getColArray()) {
-            cloneCol(newCols, c);
-        }
-        cloneCol(newCols, col);
-        sortColumns(newCols);
-        CTCol[] colArray = newCols.getColArray();
-        CTCols returnCols = CTCols.Factory.newInstance();
-        sweepCleanColumns(returnCols, colArray, col);
-        colArray = returnCols.getColArray();
-        cols.setColArray(colArray);
-        return returnCols;
-    }
-
     /*
      * Insert a new CTCol at position 0 into cols, setting min=min, max=max and
      * copying all the colsWithAttributes array cols attributes into newCol
diff --git a/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java b/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java
index fdbde2c4f9..a3de1b2e51 100644
--- a/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java
+++ b/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java
@@ -528,7 +528,7 @@ public final class TestXSSFSheet extends BaseTestSheet {
         assertEquals(5, cols.getColArray(0).getMin()); // 1 based
         assertEquals(8, cols.getColArray(0).getMax()); // 1 based
         assertEquals(false,cols.getColArray(1).isSetHidden());
-        assertEquals(true,cols.getColArray(1).isSetCollapsed());
+        assertEquals(false,cols.getColArray(1).isSetCollapsed());
         assertEquals(9, cols.getColArray(1).getMin()); // 1 based
         assertEquals(9, cols.getColArray(1).getMax()); // 1 based
         assertEquals(true, cols.getColArray(2).isSetHidden());
@@ -563,7 +563,7 @@ public final class TestXSSFSheet extends BaseTestSheet {
         assertEquals(5, cols.getColArray(0).getMin()); // 1 based
         assertEquals(8, cols.getColArray(0).getMax()); // 1 based
         assertEquals(false,cols.getColArray(1).isSetHidden());
-        assertEquals(true,cols.getColArray(1).isSetCollapsed());
+        assertEquals(false,cols.getColArray(1).isSetCollapsed());
         assertEquals(9, cols.getColArray(1).getMin()); // 1 based
         assertEquals(9, cols.getColArray(1).getMax()); // 1 based
         assertEquals(false,cols.getColArray(2).isSetHidden());
@@ -592,7 +592,7 @@ public final class TestXSSFSheet extends BaseTestSheet {
         assertEquals(5, cols.getColArray(0).getMin()); // 1 based
         assertEquals(8, cols.getColArray(0).getMax()); // 1 based
         assertEquals(false,cols.getColArray(1).isSetHidden());
-        assertEquals(true,cols.getColArray(1).isSetCollapsed());
+        assertEquals(false,cols.getColArray(1).isSetCollapsed());
         assertEquals(9, cols.getColArray(1).getMin()); // 1 based
         assertEquals(9, cols.getColArray(1).getMax()); // 1 based
         assertEquals(false,cols.getColArray(2).isSetHidden());
@@ -631,7 +631,7 @@ public final class TestXSSFSheet extends BaseTestSheet {
         assertEquals(5, cols.getColArray(0).getMin()); // 1 based
         assertEquals(8, cols.getColArray(0).getMax()); // 1 based
         assertEquals(false,cols.getColArray(1).isSetHidden());
-        assertEquals(true,cols.getColArray(1).isSetCollapsed());
+        assertEquals(false,cols.getColArray(1).isSetCollapsed());
         assertEquals(9, cols.getColArray(1).getMin()); // 1 based
         assertEquals(9, cols.getColArray(1).getMax()); // 1 based
         assertEquals(false,cols.getColArray(2).isSetHidden());
diff --git a/src/ooxml/testcases/org/apache/poi/xssf/usermodel/helpers/TestColumnHelper.java b/src/ooxml/testcases/org/apache/poi/xssf/usermodel/helpers/TestColumnHelper.java
index b4ab2834e2..1ca8fb8bea 100644
--- a/src/ooxml/testcases/org/apache/poi/xssf/usermodel/helpers/TestColumnHelper.java
+++ b/src/ooxml/testcases/org/apache/poi/xssf/usermodel/helpers/TestColumnHelper.java
@@ -68,9 +68,6 @@ public final class TestColumnHelper extends TestCase {
     }
 
     public void testSortColumns() {
-        CTWorksheet worksheet = CTWorksheet.Factory.newInstance();
-        ColumnHelper helper = new ColumnHelper(worksheet);
-
         CTCols cols1 = CTCols.Factory.newInstance();
         CTCol col1 = cols1.addNewCol();
         col1.setMin(1);
@@ -154,36 +151,28 @@ public final class TestColumnHelper extends TestCase {
         col4.setMax(9);
         assertEquals(4, cols1.sizeOfColArray());
 
-        CTCol col5 = CTCol.Factory.newInstance();
-        col5.setMin(4);
-        col5.setMax(5);
-        helper.addCleanColIntoCols(cols1, col5);
+        // No overlap
+        helper.addCleanColIntoCols(cols1, createCol(4, 5));
         assertEquals(5, cols1.sizeOfColArray());
 
-        CTCol col6 = CTCol.Factory.newInstance();
-        col6.setMin(8);
-        col6.setMax(11);
+        // Overlaps with 8 - 9 (overlap and after replacements required)
+        CTCol col6 = createCol(8, 11);
         col6.setHidden(true);
         helper.addCleanColIntoCols(cols1, col6);
         assertEquals(6, cols1.sizeOfColArray());
 
-        CTCol col7 = CTCol.Factory.newInstance();
-        col7.setMin(6);
-        col7.setMax(8);
+        // Overlaps with 8 - 9 (before and overlap replacements required)
+        CTCol col7 = createCol(6, 8);
         col7.setWidth(17.0);
         helper.addCleanColIntoCols(cols1, col7);
         assertEquals(8, cols1.sizeOfColArray());
 
-        CTCol col8 = CTCol.Factory.newInstance();
-        col8.setMin(20);
-        col8.setMax(30);
-        helper.addCleanColIntoCols(cols1, col8);
+        // Overlaps with 13 - 16750 (before, overlap and after replacements required)
+        helper.addCleanColIntoCols(cols1, createCol(20, 30));
         assertEquals(10, cols1.sizeOfColArray());
 
-        CTCol col9 = CTCol.Factory.newInstance();
-        col9.setMin(25);
-        col9.setMax(27);
-        helper.addCleanColIntoCols(cols1, col9);
+        // Overlaps with 20 - 30 (before, overlap and after replacements required)
+        helper.addCleanColIntoCols(cols1, createCol(25, 27));
 
         // TODO - assert something interesting
         assertEquals(12, cols1.sizeOfColArray());
@@ -191,6 +180,92 @@ public final class TestColumnHelper extends TestCase {
         assertEquals(16750, cols1.getColArray(11).getMax());
     }
 
+    public void testAddCleanColIntoColsExactOverlap() throws Exception {
+        CTCols cols = createHiddenAndBestFitColsWithHelper(1, 1, 1, 1);
+        assertEquals(1, cols.sizeOfColArray());
+        assertMinMaxHiddenBestFit(cols, 0, 1, 1, true, true);
+    }
+
+    public void testAddCleanColIntoColsOverlapsOverhangingBothSides() throws Exception {
+        CTCols cols = createHiddenAndBestFitColsWithHelper(2, 2, 1, 3);
+        assertEquals(3, cols.sizeOfColArray());
+        assertMinMaxHiddenBestFit(cols, 0, 1, 1, false, true);
+        assertMinMaxHiddenBestFit(cols, 1, 2, 2, true, true);
+        assertMinMaxHiddenBestFit(cols, 2, 3, 3, false, true);
+    }
+
+    public void testAddCleanColIntoColsOverlapsCompletelyNested() throws Exception {
+        CTCols cols = createHiddenAndBestFitColsWithHelper(1, 3, 2, 2);
+        assertEquals(3, cols.sizeOfColArray());
+        assertMinMaxHiddenBestFit(cols, 0, 1, 1, true, false);
+        assertMinMaxHiddenBestFit(cols, 1, 2, 2, true, true);
+        assertMinMaxHiddenBestFit(cols, 2, 3, 3, true, false);
+    }
+
+    public void testAddCleanColIntoColsNewOverlapsOverhangingLeftNotRightExactRight() throws Exception {
+        CTCols cols = createHiddenAndBestFitColsWithHelper(2, 3, 1, 3);
+        assertEquals(2, cols.sizeOfColArray());
+        assertMinMaxHiddenBestFit(cols, 0, 1, 1, false, true);
+        assertMinMaxHiddenBestFit(cols, 1, 2, 3, true, true);
+    }
+
+    public void testAddCleanColIntoColsNewOverlapsOverhangingRightNotLeftExactLeft() throws Exception {
+        CTCols cols = createHiddenAndBestFitColsWithHelper(1, 2, 1, 3);
+        assertEquals(2, cols.sizeOfColArray());
+        assertMinMaxHiddenBestFit(cols, 0, 1, 2, true, true);
+        assertMinMaxHiddenBestFit(cols, 1, 3, 3, false, true);
+    }
+
+    public void testAddCleanColIntoColsNewOverlapsOverhangingLeftNotRight() throws Exception {
+        CTCols cols = createHiddenAndBestFitColsWithHelper(2, 3, 1, 2);
+        assertEquals(3, cols.sizeOfColArray());
+        assertMinMaxHiddenBestFit(cols, 0, 1, 1, false, true);
+        assertMinMaxHiddenBestFit(cols, 1, 2, 2, true, true);
+        assertMinMaxHiddenBestFit(cols, 2, 3, 3, true, false);
+    }
+
+    public void testAddCleanColIntoColsNewOverlapsOverhangingRightNotLeft() throws Exception {
+        CTCols cols = createHiddenAndBestFitColsWithHelper(1, 2, 2, 3);
+        assertEquals(3, cols.sizeOfColArray());
+        assertMinMaxHiddenBestFit(cols, 0, 1, 1, true, false);
+        assertMinMaxHiddenBestFit(cols, 1, 2, 2, true, true);
+        assertMinMaxHiddenBestFit(cols, 2, 3, 3, false, true);
+    }
+
+    /**
+     * Creates and adds a hidden column and then a best fit column with the given min/max pairs.
+     * Suitable for testing handling of overlap. 
+     */
+    private CTCols createHiddenAndBestFitColsWithHelper(int hiddenMin, int hiddenMax, int bestFitMin, int bestFitMax) {
+        CTWorksheet worksheet = CTWorksheet.Factory.newInstance();
+        ColumnHelper helper = new ColumnHelper(worksheet);
+        CTCols cols = worksheet.getColsArray(0);
+
+        CTCol hidden = createCol(hiddenMin, hiddenMax);
+        hidden.setHidden(true);
+        helper.addCleanColIntoCols(cols, hidden);
+
+        CTCol bestFit = createCol(bestFitMin, bestFitMax);
+        bestFit.setBestFit(true);
+        helper.addCleanColIntoCols(cols, bestFit);
+        return cols;
+    }
+
+    private void assertMinMaxHiddenBestFit(CTCols cols, int index, int min, int max, boolean hidden, boolean bestFit) {
+        CTCol col = cols.getColArray(index);
+        assertEquals(min, col.getMin());
+        assertEquals(max, col.getMax());
+        assertEquals(hidden, col.getHidden());
+        assertEquals(bestFit, col.getBestFit());
+    }
+
+    private CTCol createCol(int min, int max) {
+        CTCol col = CTCol.Factory.newInstance();
+        col.setMin(min);
+        col.setMax(max);
+        return col;
+    }
+
     public void testGetColumn() {
         CTWorksheet worksheet = CTWorksheet.Factory.newInstance();