add a natural sort algorithm

diff --git a/libs/pbd/pbd/natsort.h b/libs/pbd/pbd/natsort.h
new file mode 100644 (file)
index 0000000..c50a6f2
--- /dev/null
+++ b/libs/pbd/pbd/natsort.h
@@ -0,0 +1,67 @@
+/*
+ * Copyright 2016 Robin Gareus <robin@gareus.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#ifndef PBD_NATSORT
+#define PBD_NATSORT
+
+#include <ctype.h>
+#include <stdlib.h>
+
+namespace PBD {
+
+bool
+naturally_less (const char* a, const char* b)
+{
+       const char* d_a = NULL;
+       const char* d_b = NULL;
+
+       for (;*a && *b; ++a, ++b) {
+               if (isdigit (*a) && isdigit (*b) && !d_a) {
+                       d_a = a; d_b = b;
+                       continue;
+               }
+               if (d_a) {
+                       const int ia = atoi (d_a);
+                       const int ib = atoi (d_b);
+                       if (ia != ib) {
+                               return ia < ib;
+                       }
+               }
+               d_a = d_b = NULL;
+               if (*a == *b) {
+                       continue;
+               }                                                                                                                                                                                          
+               return *a < *b;
+       }
+
+       if (d_a) {
+               return atoi (d_a) < atoi (d_b);
+       }
+
+       /* if we reach here, either strings are same length and equal
+        * or one is longer than the other.
+        */
+
+       if (*a) { return false; }
+       if (*b) { return true; }
+       return false; // equal
+}
+
+} // namespace PBD
+
+#endif // PBD_NATSORT

diff --git a/libs/pbd/test/natsort_test.cc b/libs/pbd/test/natsort_test.cc
new file mode 100644 (file)
index 0000000..6e8d19b
--- /dev/null
+++ b/libs/pbd/test/natsort_test.cc
@@ -0,0 +1,20 @@
+#include "natsort_test.h"
+#include "pbd/natsort.h"
+
+CPPUNIT_TEST_SUITE_REGISTRATION (NatSortTest);
+
+using namespace std;
+
+
+void
+NatSortTest::testBasic ()
+{
+       CPPUNIT_ASSERT (!PBD::naturally_less ("a32", "a4"));
+       CPPUNIT_ASSERT (!PBD::naturally_less ("a32", "a04"));
+       CPPUNIT_ASSERT ( PBD::naturally_less ("a32", "a40"));
+       CPPUNIT_ASSERT ( PBD::naturally_less ("a32a", "a32b"));
+       CPPUNIT_ASSERT (!PBD::naturally_less ("a32b", "a32a"));
+       CPPUNIT_ASSERT (!PBD::naturally_less ("abcd", "abc"));
+       CPPUNIT_ASSERT ( PBD::naturally_less ("abc", "abcd"));
+       CPPUNIT_ASSERT (!PBD::naturally_less ("abc", "abc"));
+}

diff --git a/libs/pbd/test/natsort_test.h b/libs/pbd/test/natsort_test.h
new file mode 100644 (file)
index 0000000..7dea79a
--- /dev/null
+++ b/libs/pbd/test/natsort_test.h
@@ -0,0 +1,15 @@
+#include <cppunit/TestFixture.h>
+#include <cppunit/extensions/HelperMacros.h>
+
+class NatSortTest : public CppUnit::TestFixture
+{
+       CPPUNIT_TEST_SUITE (NatSortTest);
+       CPPUNIT_TEST (testBasic);
+       CPPUNIT_TEST_SUITE_END ();
+
+public:
+       NatSortTest () { }
+       void testBasic ();
+
+private:
+};

diff --git a/libs/pbd/wscript b/libs/pbd/wscript
index a996c1913cae436a7fc103af4f29cd20c60f0c3e..31f4d5947e0cccaa45d212ed5c6acc1709d80ec0 100644 (file)
--- a/libs/pbd/wscript
+++ b/libs/pbd/wscript
@@ -163,6 +163,7 @@ def build(bld):
                 test/signals_test.cc
                 test/convert_test.cc
                 test/filesystem_test.cc
+                test/natsort_test.cc
                 test/reallocpool_test.cc
                 test/xml_test.cc
                 test/test_common.cc