[Libreoffice-commits] core.git: sc/source

[Maarten Bosmans]

 sc/source/filter/oox/sheetdatabuffer.cxx |   59 ++++++++++++-------------------
 1 file changed, 24 insertions(+), 35 deletions(-)

New commits:
commit 4a63c145dcce8411c5707f6b99877cc87a4f6c5d
Author: Maarten Bosmans <mkbosmans at gmail.com>
Date:   Wed Aug 24 21:14:57 2016 +0200

    Resolves tdf#100709 Optimize SheetDataBuffer::addColXfStyle
    
    The insertion of RowRanges into the sorted set was done by iterating through the
    set until the correct insertion point was found.  By using set.lower_bound(),
    the complexity goes from O(N) to (log N) for a single insert.
    
    Regarding tdf#100709: the import time for the attached example document reduces by 12x.
    
    Change-Id: Ifb03d58a0e46a936ab61a5f0b512e956c87e5e2b
    Reviewed-on: https://gerrit.libreoffice.org/28510
    Reviewed-by: Eike Rathke <erack at redhat.com>
    Tested-by: Jenkins <ci at libreoffice.org>

diff --git a/sc/source/filter/oox/sheetdatabuffer.cxx b/sc/source/filter/oox/sheetdatabuffer.cxx
index d5f29af..1ebf76c 100644
--- a/sc/source/filter/oox/sheetdatabuffer.cxx
+++ b/sc/source/filter/oox/sheetdatabuffer.cxx
@@ -370,59 +370,48 @@ void SheetDataBuffer::addColXfStyle( sal_Int32 nXfId, sal_Int32 nFormatId, const
             maStylesPerColumn[ nCol ].insert( aStyleRows );
         else
         {
-            RowStyles& rRowStyles =  maStylesPerColumn[ nCol ];
+            RowStyles& rRowStyles = maStylesPerColumn[ nCol ];
             // Reset row range for each column
             aStyleRows.mnStartRow = rAddress.StartRow;
             aStyleRows.mnEndRow = rAddress.EndRow;
 
-            // If the rowrange style includes rows already
-            // allocated to a style then we need to split
-            // the range style Rows into sections ( to
-            // occupy only rows that have no style definition )
+            // If aStyleRows includes rows already allocated to a style
+            // in rRowStyles, then we need to split it into parts.
+            // ( to occupy only rows that have no style definition)
 
-            // We don't want to set any rowstyle 'rows'
-            // for rows where there is an existing 'style' )
-            std::vector< RowRangeStyle > aRangeRowsSplits;
-
-            RowStyles::iterator rows_it = rRowStyles.begin();
+            // Start iterating at the first element that is not completely before aStyleRows
+            RowStyles::iterator rows_it = rRowStyles.lower_bound(aStyleRows);
             RowStyles::iterator rows_end = rRowStyles.end();
             bool bAddRange = true;
             for ( ; rows_it != rows_end; ++rows_it )
             {
                 const RowRangeStyle& r = *rows_it;
-                // if row is completely within existing style, discard it
-                if ( aStyleRows.mnStartRow >= r.mnStartRow && aStyleRows.mnEndRow <= r.mnEndRow )
-                    bAddRange = false;
-                else if ( aStyleRows.mnStartRow <= r.mnStartRow )
+
+                // Add the part of aStyleRows that does not overlap with r
+                if ( aStyleRows.mnStartRow < r.mnStartRow )
+                {
+                    RowRangeStyle aSplit = aStyleRows;
+                    aSplit.mnEndRow = std::min(aStyleRows.mnEndRow, r.mnStartRow - 1);
+                    // Insert with hint that aSplit comes directly before the current position
+                    rRowStyles.insert( rows_it, aSplit );
+                }
+
+                // Done if no part of aStyleRows extends beyond r
+                if ( aStyleRows.mnEndRow <= r.mnEndRow )
                 {
-                    // not intersecting at all?, if so finish as none left
-                    // to check ( row ranges are in ascending order
-                    if ( aStyleRows.mnEndRow < r.mnStartRow )
-                        break;
-                    else if ( aStyleRows.mnEndRow <= r.mnEndRow )
-                    {
-                        aStyleRows.mnEndRow = r.mnStartRow - 1;
-                        break;
-                    }
-                    if ( aStyleRows.mnStartRow < r.mnStartRow )
-                    {
-                        RowRangeStyle aSplit = aStyleRows;
-                        aSplit.mnEndRow = r.mnStartRow - 1;
-                        aRangeRowsSplits.push_back( aSplit );
-                    }
+                    bAddRange = false;
+                    break;
                 }
-                if ( aStyleRows.mnStartRow <= r.mnEndRow && r.mnEndRow < aStyleRows.mnEndRow )
-                    aStyleRows.mnStartRow = r.mnEndRow + 1;
+
+                // Cut off the part aStyleRows that was handled above
+                aStyleRows.mnStartRow = r.mnEndRow + 1;
             }
-            std::vector< RowRangeStyle >::iterator splits_it = aRangeRowsSplits.begin();
-            std::vector< RowRangeStyle >::iterator splits_end = aRangeRowsSplits.end();
-            for ( ; splits_it != splits_end; ++splits_it )
-                rRowStyles.insert( *splits_it );
             if ( bAddRange )
                 rRowStyles.insert( aStyleRows );
         }
     }
 }
+
 void SheetDataBuffer::finalizeImport()
 {
     // create all array formulas