sc: convert SequenceMapping O(n^2) algorithm to O(n log(n)) tdf#85548

Change-Id: Ie0c819ac3f8b0c0b165e95ae5e58405a12c38472
Reviewed-on: https://gerrit.libreoffice.org/20753
Reviewed-by: Markus Mohrhard <markus.mohrhard@googlemail.com>
Tested-by: Markus Mohrhard <markus.mohrhard@googlemail.com>

1 files changed, 35 insertions, 38 deletions

diff --git a/sc/source/ui/unoobj/chart2uno.cxx b/sc/source/ui/unoobj/chart2uno.cxx
index deb144f19c3c..51a159ee97fe 100644
--- a/sc/source/ui/unoobj/chart2uno.cxx
+++ b/sc/source/ui/unoobj/chart2uno.cxx
@@ -1762,6 +1762,18 @@ bool RangeAnalyzer::inSameSingleColumn( RangeAnalyzer& rOther )
     return false;
 }
 
+OUString constructKey(const uno::Reference< chart2::data::XLabeledDataSequence>& xNew)
+{
+    OUString key;
+    if( xNew->getLabel().is() )
+        key += xNew->getLabel()->getSourceRangeRepresentation();
+    key += "####";
+    if( xNew->getValues().is() )
+        key += xNew->getValues()->getSourceRangeRepresentation();
+    return key;
+}
+
+
 } //end anonymous namespace
 
 uno::Sequence< beans::PropertyValue > SAL_CALL ScChart2DataProvider::detectArguments(
@@ -1983,49 +1995,34 @@ uno::Sequence< beans::PropertyValue > SAL_CALL ScChart2DataProvider::detectArgum
 
         if( xDataSource.is() && xCompareDataSource.is() )
         {
-            uno::Sequence< uno::Reference< chart2::data::XLabeledDataSequence> > aOldSequences(
-                xCompareDataSource->getDataSequences() );
-            uno::Sequence< uno::Reference< chart2::data::XLabeledDataSequence > > aNewSequences(
-                xDataSource->getDataSequences());
-
-            OUString aOldLabel;
-            OUString aNewLabel;
-            OUString aOldValues;
-            OUString aNewValues;
+            const uno::Sequence< uno::Reference< chart2::data::XLabeledDataSequence> >& aOldSequences =
+                xCompareDataSource->getDataSequences();
+            const uno::Sequence< uno::Reference< chart2::data::XLabeledDataSequence> >& aNewSequences =
+                xDataSource->getDataSequences();
 
-            for( sal_Int32 nNewIndex = 0; nNewIndex < aNewSequences.getLength(); nNewIndex++ )
+            std::map<OUString,sal_Int32> aOldEntryToIndex;
+            for( sal_Int32 nIndex = 0; nIndex < aOldSequences.getLength(); nIndex++ )
             {
-                uno::Reference< chart2::data::XLabeledDataSequence> xNew( aNewSequences[nNewIndex] );
-                for( sal_Int32 nOldIndex = 0; nOldIndex < aOldSequences.getLength(); nOldIndex++ )
+                const uno::Reference< chart2::data::XLabeledDataSequence>& xOld( aOldSequences[nIndex] );
+                if( xOld.is() )
                 {
-                    uno::Reference< chart2::data::XLabeledDataSequence> xOld( aOldSequences[nOldIndex] );
-
-                    if( xOld.is() && xNew.is() )
-                    {
-                        aOldLabel.clear();
-                        aNewLabel.clear();
-                        aOldValues.clear();
-                        aNewValues.clear();
-                        if( xOld.is() && xOld->getLabel().is() )
-                            aOldLabel = xOld->getLabel()->getSourceRangeRepresentation();
-                        if( xNew.is() && xNew->getLabel().is() )
-                            aNewLabel = xNew->getLabel()->getSourceRangeRepresentation();
-                        if( xOld.is() && xOld->getValues().is() )
-                            aOldValues = xOld->getValues()->getSourceRangeRepresentation();
-                        if( xNew.is() && xNew->getValues().is() )
-                            aNewValues = xNew->getValues()->getSourceRangeRepresentation();
-
-                        if( aOldLabel.equals(aNewLabel)
-                            && ( aOldValues.equals(aNewValues) ) )
-                        {
-                            if( nOldIndex!=nNewIndex )
-                                bDifferentIndexes = true;
-                            aSequenceMappingVector.push_back(nOldIndex);
-                            break;
-                        }
-                    }
+                    OUString key = constructKey(xOld);
+                    aOldEntryToIndex[key] = nIndex;
                 }
             }
+            for( sal_Int32 nNewIndex = 0; nNewIndex < aNewSequences.getLength(); nNewIndex++ )
+            {
+                const uno::Reference< chart2::data::XLabeledDataSequence>& xNew( aNewSequences[nNewIndex] );
+                if( !xNew.is() )
+                    continue;
+                OUString key = constructKey(xNew);
+                if (aOldEntryToIndex.find(key) == aOldEntryToIndex.end())
+                    continue;
+                sal_Int32 nOldIndex = aOldEntryToIndex[key];
+                if( nOldIndex != nNewIndex )
+                    bDifferentIndexes = true;
+                aSequenceMappingVector.push_back(nOldIndex);
+            }
         }
 
         if( bDifferentIndexes && !aSequenceMappingVector.empty() )