optimize Replace() to use a linear algorithm (closes #9135)

git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@59420 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775

diff --git a/docs/changes.txt b/docs/changes.txt
index d0ef4c1da98bd23856607657f33acb4b82623cc8..d90c86629a04b53ef2fa4eb6590a6ded1ea97078 100644 (file)
--- a/docs/changes.txt
+++ b/docs/changes.txt
@@ -373,6 +373,7 @@ All:
 - Added wxLog::Log().
 - Added wxProtocolLog and use it in wxFTP.
 - Added wxXmlResource::GetResourceNode().
 - Added wxLog::Log().
 - Added wxProtocolLog and use it in wxFTP.
 - Added wxXmlResource::GetResourceNode().

+- Optimize wxString::Replace() to use an O(N) algorithm (Kuang-che Wu).

 
 All (Unix):
 
 
 All (Unix):
 

diff --git a/src/common/string.cpp b/src/common/string.cpp
index 56af51ae22c28dbe3e8306171f575729270236ac..e07b7eea8f74554e9350b0a402b5977528296c34 100644 (file)
--- a/src/common/string.cpp
+++ b/src/common/string.cpp
@@ -36,6 +36,7 @@
 #include <stdlib.h>
 
 #include "wx/hashmap.h"
 #include <stdlib.h>
 
 #include "wx/hashmap.h"

+#include "wx/vector.h"

 
 // string handling functions used by wxString:
 #if wxUSE_UNICODE_UTF8
 
 // string handling functions used by wxString:
 #if wxUSE_UNICODE_UTF8


@@ -1397,30 +1398,62 @@ size_t wxString::Replace(const wxString& strOld,
                 break;
         }
     }
                 break;
         }
     }

-    else // general case
+    else if ( !bReplaceAll)
+    {
+        size_t pos = m_impl.find(strOld, 0);
+        if ( pos != npos )
+        {
+            m_impl.replace(pos, strOld.m_impl.length(), strNew.m_impl);
+            uiCount = 1;
+        }
+    }
+    else // replace all occurrences

     {
         const size_t uiOldLen = strOld.m_impl.length();
         const size_t uiNewLen = strNew.m_impl.length();
 
     {
         const size_t uiOldLen = strOld.m_impl.length();
         const size_t uiNewLen = strNew.m_impl.length();
 

-        for ( size_t pos = 0; ; )
+        // first scan the string to find all positions at which the replacement
+        // should be made
+        wxVector<size_t> replacePositions;
+
+        size_t pos;
+        for ( pos = m_impl.find(strOld.m_impl, 0);
+              pos != npos;
+              pos = m_impl.find(strOld.m_impl, pos + uiOldLen))

         {
         {

-            pos = m_impl.find(strOld.m_impl, pos);
-            if ( pos == npos )
-                break;
+            replacePositions.push_back(pos);
+            ++uiCount;
+        }

 
 

-            // replace this occurrence of the old string with the new one
-            m_impl.replace(pos, uiOldLen, strNew.m_impl);
+        if ( !uiCount )
+            return 0;

 
 

-            // move up pos past the string that was replaced
-            pos += uiNewLen;
+        // allocate enough memory for the whole new string
+        wxString tmp;
+        tmp.m_impl.reserve(m_impl.length() + uiCount*(uiNewLen - uiOldLen));

 
 

-            // increase replace count
-            uiCount++;
+        // copy this string to tmp doing replacements on the fly
+        size_t replNum = 0;
+        for ( pos = 0; replNum < uiCount; replNum++ )
+        {
+            const size_t nextReplPos = replacePositions[replNum];

 
 

-            // stop after the first one?
-            if ( !bReplaceAll )
-                break;
+            if ( pos != nextReplPos )
+            {
+                tmp.m_impl.append(m_impl, pos, nextReplPos - pos);
+            }
+
+            tmp.m_impl.append(strNew.m_impl);
+            pos = nextReplPos + uiOldLen;

         }
         }

+
+        if ( pos != m_impl.length() )
+        {
+            // append the rest of the string unchanged
+            tmp.m_impl.append(m_impl, pos, m_impl.length() - pos);
+        }
+
+        swap(tmp);

     }
 
     return uiCount;
     }
 
     return uiCount;

diff --git a/tests/benchmarks/strings.cpp b/tests/benchmarks/strings.cpp
index 9449f49110065268b08dda3264e22f8026143cbe..cc09a35418c2d4882c65d4e888f7e7f928060495 100644 (file)
--- a/tests/benchmarks/strings.cpp
+++ b/tests/benchmarks/strings.cpp
@@ -281,6 +281,18 @@ BENCHMARK_FUNC(ReplaceAll)
     return str.Replace("x", "y") != 0;
 }
 
     return str.Replace("x", "y") != 0;
 }
 

+BENCHMARK_FUNC(ReplaceLonger)
+{
+    wxString str('x', ASCIISTR_LEN);
+    return str.Replace("x", "yy") != 0;
+}
+
+BENCHMARK_FUNC(ReplaceShorter)
+{
+    wxString str('x', ASCIISTR_LEN);
+    return str.Replace("xx", "y") != 0;
+}
+

 
 // ----------------------------------------------------------------------------
 // string buffers: wx[W]CharBuffer
 
 // ----------------------------------------------------------------------------
 // string buffers: wx[W]CharBuffer

diff --git a/tests/strings/strings.cpp b/tests/strings/strings.cpp
index 09686b11da5b493e6d854e7f2ec6cc4023a5d5a2..7fcc223c9cc41d1606c27e1d393876487dd1d4d2 100644 (file)
--- a/tests/strings/strings.cpp
+++ b/tests/strings/strings.cpp
@@ -318,7 +318,7 @@ void StringTestCase::Replace()
         { \
             wxString s(o,olen); \
             s.replace( pos , len , replacement ); \
         { \
             wxString s(o,olen); \
             s.replace( pos , len , replacement ); \

-            CPPUNIT_ASSERT( s == wxString(r,rlen) ); \
+            CPPUNIT_ASSERT_EQUAL( wxString(r,rlen), s ); \

         }
 
     TEST_NULLCHARREPLACE( _T("null\0char"), 9, 5, 1, _T("d"),
         }
 
     TEST_NULLCHARREPLACE( _T("null\0char"), 9, 5, 1, _T("d"),


@@ -328,7 +328,7 @@ void StringTestCase::Replace()
         { \
             wxString s(o,olen); \
             s.Replace( olds, news, all ); \
         { \
             wxString s(o,olen); \
             s.Replace( olds, news, all ); \

-            CPPUNIT_ASSERT( s == wxString(r,rlen) ); \
+            CPPUNIT_ASSERT_EQUAL( wxString(r,rlen), s ); \

         }
 
     TEST_WXREPLACE( _T("null\0char"), 9, _T("c"), _T("de"), true,
         }
 
     TEST_WXREPLACE( _T("null\0char"), 9, _T("c"), _T("de"), true,


@@ -338,6 +338,10 @@ void StringTestCase::Replace()
                           _T("null\0char"), 9 );
 
     TEST_WXREPLACE( "life", 4, "f", "", false, "lie", 3 );
                           _T("null\0char"), 9 );
 
     TEST_WXREPLACE( "life", 4, "f", "", false, "lie", 3 );

+    TEST_WXREPLACE( "life", 4, "f", "", true, "lie", 3 );
+    TEST_WXREPLACE( "life", 4, "fe", "ve", true, "live", 4 );
+    TEST_WXREPLACE( "xx", 2, "x", "yy", true, "yyyy", 4 );
+    TEST_WXREPLACE( "xxx", 3, "xx", "z", true, "zx", 2 );

 
     #undef TEST_WXREPLACE
     #undef TEST_NULLCHARREPLACE
 
     #undef TEST_WXREPLACE
     #undef TEST_NULLCHARREPLACE