remove ShapeList::getNextShape(SdrObject* pObj)

The getNextShape(pObj) method is just used for iterating over the complete
ShapeList. But the complexity for this operation is exponential.
When using getNextShape() iterating over the list have linear complexity.
In short: it is much faster.

Change-Id: I3896af2247f348153d62f2bcdd207c5a75239689
Reviewed-on: https://gerrit.libreoffice.org/4132
Reviewed-by: Thorsten Behrens <tbehrens@suse.com>
Tested-by: Thorsten Behrens <tbehrens@suse.com>

6 files changed, 23 insertions, 43 deletions

diff --git a/sd/inc/shapelist.hxx b/sd/inc/shapelist.hxx
index f3c779e2b184..f828ebc61d31 100644
--- a/sd/inc/shapelist.hxx
+++ b/sd/inc/shapelist.hxx
@@ -48,16 +48,12 @@ namespace sd
         /** @return true if given shape is part of this list */
         bool hasShape( SdrObject& rObject ) const;
 
-        /** returns the shape following the given shape in the list or 0
-            returns the first shape if pObj is 0 */
-        SdrObject* getNextShape(SdrObject* pObj) const;
-
-        /**
-        */
+        /** returns the shape the internal iterator points to, or 0 if
+         * the list end is reached. moves the internal iterator to the
+         * next shape. */
         SdrObject* getNextShape();
 
-        /**
-        */
+        /** Sets the internal iterator to the shape at given index. */
         void seekShape( sal_uInt32 nIndex );
 
         /**
diff --git a/sd/source/core/drawdoc.cxx b/sd/source/core/drawdoc.cxx
index 2d294eb5e11c..aca4996aadae 100644
--- a/sd/source/core/drawdoc.cxx
+++ b/sd/source/core/drawdoc.cxx
@@ -694,7 +694,7 @@ void SdDrawDocument::UpdateAllLinks()
 */
 void SdDrawDocument::NewOrLoadCompleted( SdPage* pPage, SdStyleSheetPool* pSPool )
 {
-    const sd::ShapeList& rPresentationShapes( pPage->GetPresentationShapeList() );
+    sd::ShapeList& rPresentationShapes( pPage->GetPresentationShapeList() );
     if(!rPresentationShapes.isEmpty())
     {
         // Create lists of title and outline styles
@@ -706,11 +706,12 @@ void SdDrawDocument::NewOrLoadCompleted( SdPage* pPage, SdStyleSheetPool* pSPool
 
         SfxStyleSheet* pTitleSheet = (SfxStyleSheet*)pSPool->GetTitleSheet(aName);
 
-        SdrObject* pObj = rPresentationShapes.getNextShape(0);
+        SdrObject* pObj = 0;
+        rPresentationShapes.seekShape(0);
 
         // Now look for title and outline text objects, then make those objects
         // listeners.
-        while(pObj)
+        while( (pObj = rPresentationShapes.getNextShape()) )
         {
             if (pObj->GetObjInventor() == SdrInventor)
             {
@@ -761,8 +762,6 @@ void SdDrawDocument::NewOrLoadCompleted( SdPage* pPage, SdStyleSheetPool* pSPool
                     }
                 }
             }
-
-            pObj = rPresentationShapes.getNextShape(pObj);
         }
     }
 }
diff --git a/sd/source/core/sdpage.cxx b/sd/source/core/sdpage.cxx
index 6c4faf33d39d..71d407b615c3 100644
--- a/sd/source/core/sdpage.cxx
+++ b/sd/source/core/sdpage.cxx
@@ -156,7 +156,9 @@ SdrObject* SdPage::GetPresObj(PresObjKind eObjKind, int nIndex, bool bFuzzySearc
     std::vector< SdrObject* > aMatches;
 
     SdrObject* pObj = 0;
-    while( (pObj = maPresentationShapeList.getNextShape(pObj)) != 0 )
+    maPresentationShapeList.seekShape(0);
+
+    while( (pObj = maPresentationShapeList.getNextShape()) )
     {
         SdAnimationInfo* pInfo = SdDrawDocument::GetShapeUserData(*pObj);
         if( pInfo )
@@ -1572,11 +1574,11 @@ void SdPage::SetAutoLayout(AutoLayout eLayout, sal_Bool bInit, sal_Bool bCreate
     // now delete all empty presentation objects that are no longer used by the new layout
     if( bInit )
     {
-        SdrObject* pObj = maPresentationShapeList.getNextShape(0);
+        SdrObject* pObj = 0;
+        maPresentationShapeList.seekShape(0);
 
-        while( pObj )
+        while( (pObj = maPresentationShapeList.getNextShape()) )
         {
-            SdrObject* pNext = maPresentationShapeList.getNextShape(pObj);
             if( aUsedPresentationObjects.count(pObj) == 0 )
             {
 
@@ -1592,7 +1594,6 @@ void SdPage::SetAutoLayout(AutoLayout eLayout, sal_Bool bInit, sal_Bool bCreate
                 }
 /* #i108541# keep non empty pres obj as pres obj even if they are not part of the current layout */
             }
-            pObj = pNext;
         }
     }
 }
diff --git a/sd/source/core/sdpage2.cxx b/sd/source/core/sdpage2.cxx
index 95d9e3a8dcc9..1b4f9ab7fec9 100644
--- a/sd/source/core/sdpage2.cxx
+++ b/sd/source/core/sdpage2.cxx
@@ -379,9 +379,14 @@ SdPage::SdPage(const SdPage& rSrcPage)
     mePageKind           = rSrcPage.mePageKind;
     meAutoLayout         = rSrcPage.meAutoLayout;
 
-    SdrObject* pObj = 0;
-    while((pObj = rSrcPage.maPresentationShapeList.getNextShape(pObj)) != 0)
+    // use shape list directly to preserve constness of rSrcPage
+    const std::list< SdrObject* >& rShapeList = rSrcPage.maPresentationShapeList.getList();
+    for( std::list< SdrObject* >::const_iterator aIter = rShapeList.begin();
+         aIter != rShapeList.end(); ++aIter )
+    {
+        SdrObject* pObj = *aIter;
         InsertPresObj(GetObj(pObj->GetOrdNum()), rSrcPage.GetPresObjKind(pObj));
+    }
 
     mbSelected           = sal_False;
     mnTransitionType    = rSrcPage.mnTransitionType;
diff --git a/sd/source/core/shapelist.cxx b/sd/source/core/shapelist.cxx
index aa223ed940f4..a265e9c93eff 100644
--- a/sd/source/core/shapelist.cxx
+++ b/sd/source/core/shapelist.cxx
@@ -99,28 +99,6 @@ bool ShapeList::hasShape( SdrObject& rObject ) const
     return std::find( maShapeList.begin(), maShapeList.end(), &rObject )  != maShapeList.end();
 }
 
-SdrObject* ShapeList::getNextShape(SdrObject* pObj) const
-{
-    if( pObj )
-    {
-        ListImpl::const_iterator aIter( std::find( maShapeList.begin(), maShapeList.end(), pObj ) );
-        if( aIter != maShapeList.end() )
-        {
-            ++aIter;
-            if( aIter != maShapeList.end() )
-            {
-                return (*aIter);
-            }
-        }
-    }
-    else if( !maShapeList.empty() )
-    {
-        return (*maShapeList.begin());
-    }
-
-    return 0;
-}
-
 void ShapeList::ObjectInDestruction(const SdrObject& rObject)
 {
     ListImpl::iterator aIter( std::find( maShapeList.begin(), maShapeList.end(), &rObject ) );
diff --git a/sd/source/ui/view/drviews1.cxx b/sd/source/ui/view/drviews1.cxx
index 26ad764b4fbe..fe0f1dd598d8 100644
--- a/sd/source/ui/view/drviews1.cxx
+++ b/sd/source/ui/view/drviews1.cxx
@@ -1060,8 +1060,9 @@ sal_Bool DrawViewShell::SwitchPage(sal_uInt16 nSelectedPage)
                 // set pages for all available handout presentation objects
                 sd::ShapeList& rShapeList = pMaster->GetPresentationShapeList();
                 SdrObject* pObj = 0;
+                rShapeList.seekShape(0);
 
-                while( (pObj = rShapeList.getNextShape(pObj)) != 0 )
+                while( (pObj = rShapeList.getNextShape()) )
                 {
                     if( pMaster->GetPresObjKind(pObj) == PRESOBJ_HANDOUT )
                     {