move this (cool) natural sort into comphelper

3 files changed, 157 insertions, 4 deletions

diff --git a/comphelper/inc/comphelper/string.hxx b/comphelper/inc/comphelper/string.hxx
index 85b1a2e4efe1..9ef4ec657bbb 100644
--- a/comphelper/inc/comphelper/string.hxx
+++ b/comphelper/inc/comphelper/string.hxx
@@ -131,6 +131,44 @@ COMPHELPER_DLLPUBLIC ::rtl::OUString convertCommaSeparated(
 COMPHELPER_DLLPUBLIC ::com::sun::star::uno::Sequence< ::rtl::OUString >
     convertCommaSeparated( ::rtl::OUString const & i_rString );
 
+/**
+  Compares two strings using natural order.
+
+  For non digit characters, the comparison use the same algorithm as
+  rtl_str_compare. When a number is encountered during the comparison,
+  natural order is used. Thus, Heading 10 will be considered as greater
+  than Heading 2. Numerical comparison is done using decimal representation.
+
+  Beware that "MyString 001" and "MyString 1" will be considered as equal
+  since leading 0 are meaningless.
+
+  @param    str         the object to be compared.
+  @return   0 - if both strings are equal
+            < 0 - if this string is less than the string argument
+            > 0 - if this string is greater than the string argument
+*/
+COMPHELPER_DLLPUBLIC sal_Int32 compareNatural( const ::rtl::OUString &rLHS, const ::rtl::OUString &rRHS )
+    SAL_THROW(());
+
+/**
+  Compares two strings using natural order.
+
+  For non digit characters, the comparison use the same algorithm as
+  rtl_str_compare. When a number is encountered during the comparison,
+  natural order is used. Thus, Heading 10 will be considered as greater
+  than Heading 2. Numerical comparison is done using decimal representation.
+
+  Beware that "MyString 001" and "MyString 1" will be considered as equal
+  since leading 0 are meaningless.
+
+  @param    str         the object to be compared.
+  @return   0 - if both strings are equal
+            < 0 - if this string is less than the string argument
+            > 0 - if this string is greater than the string argument
+ */
+COMPHELPER_DLLPUBLIC sal_Int32 compareNatural( const ::rtl::OString &rLHS, const ::rtl::OString &rRHS )
+    SAL_THROW(());
+
 } }
 
 #endif
diff --git a/comphelper/qa/test_string.cxx b/comphelper/qa/test_string.cxx
index 7f15e96a42f5..ab13c8814b38 100644
--- a/comphelper/qa/test_string.cxx
+++ b/comphelper/qa/test_string.cxx
@@ -42,16 +42,20 @@
 
 namespace {
 
-class TestString: public CppUnit::TestFixture {
+class TestString: public CppUnit::TestFixture
+{
 public:
     void test();
+    void testNatural();
 
     CPPUNIT_TEST_SUITE(TestString);
     CPPUNIT_TEST(test);
+    CPPUNIT_TEST(testNatural);
     CPPUNIT_TEST_SUITE_END();
 };
 
-void TestString::test() {
+void TestString::test()
+{
     rtl::OUString s1(RTL_CONSTASCII_USTRINGPARAM("foobarbar"));
     sal_Int32 n1;
     rtl::OUString s2(
@@ -80,10 +84,66 @@ void TestString::test() {
     CPPUNIT_ASSERT(n3 == -1);
 }
 
-CPPUNIT_TEST_SUITE_REGISTRATION(TestString);
-
+void TestString::testNatural()
+{
+    using namespace comphelper::string;
+// --- Some generic tests to ensure we do not alter original behavior
+// outside what we want
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("ABC"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("ABC")))) == 0
+    );
+    // Case sensitivity
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("ABC"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc")))) < 0
+    );
+    // Reverse
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("ABC")))) > 0
+    );
+    // First shorter
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("alongstring"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("alongerstring")))) > 0
+    );
+    // Second shorter
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("alongerstring"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("alongstring")))) < 0
+    );
+// -- Here we go on natural order, each one is followed by classic compare and the reverse comparison
+    // That's why we originally made the patch
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("Heading 9"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("Heading 10")))) < 0
+    );
+    // Original behavior
+    CPPUNIT_ASSERT(
+        rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("Heading 9"))).compareTo(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("Heading 10")))) > 0
+    );
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("Heading 10"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("Heading 9")))) > 0
+    );
+    // Harder
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("July, the 4th"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("July, the 10th")))) < 0
+    );
+    CPPUNIT_ASSERT(
+        rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("July, the 4th"))).compareTo(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("July, the 10th")))) > 0
+    );
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("July, the 10th"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("July, the 4th")))) > 0
+    );
+    // Hardest
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc08"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc010")))) < 0
+    );
+    CPPUNIT_ASSERT(
+        rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc08"))).compareTo(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc010")))) > 0
+    );
+    CPPUNIT_ASSERT(
+        compareNatural(rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc010"))), rtl::OUString(RTL_CONSTASCII_USTRINGPARAM(("abc08")))) > 0
+    );
 }
 
+CPPUNIT_TEST_SUITE_REGISTRATION(TestString);
 
+}
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/comphelper/source/misc/string.cxx b/comphelper/source/misc/string.cxx
index 66cb8f984182..7e7ddf511799 100644
--- a/comphelper/source/misc/string.cxx
+++ b/comphelper/source/misc/string.cxx
@@ -123,6 +123,61 @@ rtl::OUString searchAndReplaceAsciiL(
     return kws;
 }
 
+#define IS_DIGIT(CHAR) (((CHAR) >= 48) && ((CHAR <= 57)))
+
+template<typename IMPL_RTL_STRCODE, typename IMPL_RTL_USTRCODE>
+    sal_Int32 SAL_CALL compareNaturalImpl(const IMPL_RTL_STRCODE* pStr1, const IMPL_RTL_STRCODE* pStr2)
+{
+    sal_Int32 nRet;
+    do {
+        while ( ((nRet = ((sal_Int32)(IMPL_RTL_USTRCODE(*pStr1)))-
+                         ((sal_Int32)(IMPL_RTL_USTRCODE(*pStr2)))) == 0) &&
+                *pStr2 )
+        {
+            pStr1++;
+            pStr2++;
+        }
+
+        if(*pStr1 && *pStr2)
+        {
+            IMPL_RTL_STRCODE   c1 = (sal_Int32)IMPL_RTL_USTRCODE( *pStr1 );
+            IMPL_RTL_STRCODE   c2 = (sal_Int32)IMPL_RTL_USTRCODE( *pStr2 );
+            sal_Int64   number1 = 0;
+            sal_Int64   number2 = 0;
+            if(IS_DIGIT(c1) && IS_DIGIT(c2))
+            {
+              do
+              {
+                number1 = number1 * 10 + (c1 - '0');
+                pStr1++;
+                c1 = (sal_Int32)IMPL_RTL_USTRCODE( *pStr1 );
+              } while(IS_DIGIT(c1));
+
+              do
+              {
+                number2 = number2 * 10 + (c2 - '0');
+                pStr2++;
+                c2 = (sal_Int32)IMPL_RTL_USTRCODE( *pStr2 );
+              } while(IS_DIGIT(c2));
+
+              nRet = number1 - number2;
+            }
+        }
+    } while(nRet == 0 && *pStr1 && *pStr2);
+
+    return nRet;
+}
+
+sal_Int32 compareNatural( const ::rtl::OUString & rLHS, const ::rtl::OUString & rRHS ) SAL_THROW(())
+{
+    return compareNaturalImpl<sal_Unicode, sal_Unicode>(rLHS.pData->buffer, rRHS.pData->buffer);
+}
+
+sal_Int32 compareNatural( const ::rtl::OString & rLHS, const ::rtl::OString & rRHS ) SAL_THROW(())
+{
+    return compareNaturalImpl<sal_Char, unsigned char>(rLHS.pData->buffer, rRHS.pData->buffer);
+}
+
 } }
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */