speed-up shape import if shapes need z-order rearranging

setting z-order individually on each shape and broadcasting is
O(n^2) (remaining shapes also need reordering) and this is bad
bad bad for performance

Change-Id: Ic9c9137a097f6ff524192693910f221885f77cc4
Reviewed-on: https://gerrit.libreoffice.org/75055
Tested-by: Jenkins
Reviewed-by: Michael Stahl <michael.stahl@cib.de>

2 files changed, 103 insertions, 0 deletions

diff --git a/svx/source/svdraw/svdpage.cxx b/svx/source/svdraw/svdpage.cxx
index ae0a0c3cc1e3..8794c2355dd0 100644
--- a/svx/source/svdraw/svdpage.cxx
+++ b/svx/source/svdraw/svdpage.cxx
@@ -57,6 +57,8 @@
 #include <rtl/strbuf.hxx>
 #include <libxml/xmlwriter.h>
 
+#include <com/sun/star/lang/IllegalArgumentException.hpp>
+
 using namespace ::com::sun::star;
 
 class SdrObjList::WeakSdrObjectContainerType
@@ -556,6 +558,100 @@ SdrObject* SdrObjList::SetObjectOrdNum(size_t nOldObjNum, size_t nNewObjNum)
     return pObj;
 }
 
+void SdrObjList::sort( std::vector<sal_Int32>& sortOrder)
+{
+    // no negative indexes and indexes larger than maList size are allowed
+    auto it = std::find_if( sortOrder.begin(), sortOrder.end(), [this](const sal_Int32& rIt)
+         { return ( rIt < 0 || static_cast<size_t>(rIt) >= maList.size() ); } );
+    if ( it != sortOrder.end())
+        throw css::lang::IllegalArgumentException("negative index of shape", nullptr, 1);
+
+    // no duplicates
+    std::vector<bool> aNoDuplicates(sortOrder.size(), false);
+    for (size_t i = 0; i < sortOrder.size(); ++i )
+    {
+        size_t idx =  static_cast<size_t>( sortOrder[i] );
+
+        if ( aNoDuplicates[idx] )
+            throw css::lang::IllegalArgumentException("duplicate index of shape", nullptr, 2);
+
+        aNoDuplicates[idx] = true;
+    }
+
+    // example sortOrder [2 0 1]
+    // example maList [T T S T T] ( T T = shape with textbox, S = just a shape )
+    // (shapes at positions 0 and 2 have a textbox)
+
+    std::vector<SdrObject*> aNewList(maList.size());
+    std::set<sal_Int32> aShapesWithTextbox;
+    std::vector<sal_Int32> aIncrements;
+    std::vector<sal_Int32> aDuplicates;
+
+    if ( maList.size() > 1)
+    {
+        for (size_t i = 1; i< maList.size(); ++i)
+        {
+            // if this shape is a textbox, then look at its left neighbour
+            // (shape this textbox is in)
+            // and insert the number of textboxes to the left of it
+            if (maList[i]->IsTextBox())
+              aShapesWithTextbox.insert( i - 1 - aShapesWithTextbox.size() );
+        }
+        // example aShapesWithTextbox [0 2]
+    }
+
+    aIncrements.push_back(0);
+    aDuplicates.push_back(sortOrder[0]);
+
+    // corner case: 1st shape is a textbox, add it twice
+    // otherwise sortOrder loop below will skip it
+    if (aShapesWithTextbox.count(sortOrder[0]) > 0)
+        aDuplicates.push_back(sortOrder[0]);
+
+    for (size_t i = 1; i< sortOrder.size(); ++i)
+    {
+         aDuplicates.push_back(sortOrder[i]);
+
+         if (aShapesWithTextbox.count(sortOrder[i]) > 0)
+         {
+             aIncrements.push_back(aIncrements[i-1] + 1 );
+             aDuplicates.push_back(sortOrder[i]);
+         }
+         else
+         {
+             aIncrements.push_back(aIncrements[i-1]);
+         }
+
+         // example aDuplicates [2 2 0 0 1]
+         // example aIncrements [0 1 1]
+    }
+
+    std::vector<sal_Int32> aNewSortOrder(maList.size());
+    sal_Int32 nPrev = -1;
+    for (size_t i = 0; i< aDuplicates.size(); ++i)
+    {
+        if (nPrev != aDuplicates[i])
+            aNewSortOrder[i] = aDuplicates[i] + aIncrements[aDuplicates[i]];
+        else
+            aNewSortOrder[i] = aNewSortOrder[i-1] + 1;
+
+        nPrev = aDuplicates[i];
+
+        // example aNewSortOrder [3 4 0 1 2]
+    }
+
+    if ( aNewSortOrder.size() !=  maList.size())
+        throw css::lang::IllegalArgumentException("mismatch of no. of shapes", nullptr, 0);
+
+    for (size_t i = 0; i < aNewSortOrder.size(); ++i)
+    {
+        aNewList[i] = maList[ sortOrder[i] ];
+        aNewList[i]->SetOrdNum(i);
+    }
+
+    std::swap(aNewList, maList);
+}
+
 const tools::Rectangle& SdrObjList::GetAllObjSnapRect() const
 {
     if (mbRectsDirty) {
diff --git a/svx/source/unodraw/unopage.cxx b/svx/source/unodraw/unopage.cxx
index 5fca5403d042..28082f35e75f 100644
--- a/svx/source/unodraw/unopage.cxx
+++ b/svx/source/unodraw/unopage.cxx
@@ -27,6 +27,7 @@
 #include <osl/mutex.hxx>
 #include <sfx2/dispatch.hxx>
 #include <comphelper/classids.hxx>
+#include <comphelper/sequence.hxx>
 #include <cppuhelper/supportsservice.hxx>
 
 #include <sfx2/objsh.hxx>
@@ -330,6 +331,12 @@ void SAL_CALL SvxDrawPage::remove( const Reference< drawing::XShape >& xShape )
     mpModel->SetChanged();
 }
 
+void SvxDrawPage::sort( const css::uno::Sequence< sal_Int32 >& sortOrder )
+{
+    auto newOrder = comphelper::sequenceToContainer<std::vector<sal_Int32>>(sortOrder);
+    mpPage->sort(newOrder);
+}
+
 // css::container::XIndexAccess
 sal_Int32 SAL_CALL SvxDrawPage::getCount()
 {