add a natural sort algorithm

4 files changed, 103 insertions, 0 deletions

diff --git a/libs/pbd/pbd/natsort.h b/libs/pbd/pbd/natsort.h
new file mode 100644
index 0000000000..c50a6f288b
--- /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
index 0000000000..6e8d19b254
--- /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
index 0000000000..7dea79a2f1
--- /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 a996c1913c..31f4d5947e 100644
--- 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