[shotwell] Natural sorting of photo titles: Bug #717960

[Jim Nelson <jnelson src gnome org>]

commit 68f3f8f3730a4af55bc025dc8f5e192af2de84aa
Author: Tobia Tesan <tobia tesan gmail com>
Date:   Mon Nov 24 14:16:35 2014 -0800

    Natural sorting of photo titles: Bug #717960

 Makefile                      |    1 +
 src/MediaPage.vala            |   14 ++++
 src/NaturalCollate.vala       |   98 +++++++++++++++++++++++++++++
 src/Thumbnail.vala            |    3 +-
 test/.gitignore               |    1 +
 test/Makefile                 |    4 +
 test/NaturalCollate-Test.vala |  136 +++++++++++++++++++++++++++++++++++++++++
 7 files changed, 255 insertions(+), 2 deletions(-)
---
diff --git a/Makefile b/Makefile
index 15268fc..368bb73 100644
--- a/Makefile
+++ b/Makefile
@@ -61,6 +61,7 @@ UNUNITIZED_SRC_FILES = \
        main.vala \
        AppWindow.vala \
        CollectionPage.vala \
+       NaturalCollate.vala \
        Thumbnail.vala \
        ThumbnailCache.vala \
        CheckerboardLayout.vala \
diff --git a/src/MediaPage.vala b/src/MediaPage.vala
index 9f98466..3615e92 100644
--- a/src/MediaPage.vala
+++ b/src/MediaPage.vala
@@ -9,6 +9,7 @@ public class MediaSourceItem : CheckerboardItem {
     private static Gdk.Pixbuf current_sprocket_pixbuf = null;
 
     private bool enable_sprockets = false;
+    private string? natural_collation_key = null;
 
     // preserve the same constructor arguments and semantics as CheckerboardItem so that we're
     // a drop-in replacement
@@ -93,6 +94,19 @@ public class MediaSourceItem : CheckerboardItem {
     public void set_enable_sprockets(bool enable_sprockets) {
         this.enable_sprockets = enable_sprockets;
     }
+    
+    public new void set_title(string text, bool marked_up = false,
+        Pango.Alignment alignment = Pango.Alignment.LEFT) {
+        base.set_title(text, marked_up, alignment);
+        this.natural_collation_key = null;
+    }
+    
+    public string get_natural_collation_key() {
+        if (this.natural_collation_key == null) {
+            this.natural_collation_key = NaturalCollate.collate_key(this.get_title());
+        }
+        return this.natural_collation_key;
+    }
 }
 
 public abstract class MediaPage : CheckerboardPage {
diff --git a/src/NaturalCollate.vala b/src/NaturalCollate.vala
new file mode 100644
index 0000000..4adb027
--- /dev/null
+++ b/src/NaturalCollate.vala
@@ -0,0 +1,98 @@
+/**
+ * NaturalCollate
+ * Simple helper class for natural sorting in Vala.
+ *
+ * (c) Tobia Tesan <tobia tesan gmail com>, 2014
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the Lesser GNU General Public License
+ * as published by the Free Software Foundation; either version 2.1
+ * of the License, or (at your option) any later version.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program; see the file COPYING.  If not,
+ * see <http://www.gnu.org/licenses/>.
+ */
+
+namespace NaturalCollate {
+
+private const unichar SUPERDIGIT = ':';
+private const unichar NUM_SENTINEL = 0x2; // glib uses these, so do we
+private const string  COLLATION_SENTINEL = "\x01\x01\x01";
+
+private static int read_number(owned string s, ref int byte_index) {
+    /*
+     * Given a string in the form [numerals]*[everythingelse]*
+     * returns the int value of the first block and increments index
+     * by its length as a side effect.
+     * Notice that "numerals" is not just 0-9 but everything else 
+     * Unicode considers a numeral (see: string::isdigit())
+     */
+    int number = 0;
+
+    while (s.length != 0 && s.get_char(0).isdigit()) {
+        number = number*10;
+        number += s.get_char(0).digit_value();
+        int second_char = s.index_of_nth_char(1);
+        s = s.substring(second_char);
+        byte_index += second_char;
+    }
+    return number;
+}
+
+public static int compare(string str1, string str2) {
+    return strcmp(collate_key(str1), collate_key(str2));
+}
+
+public static string collate_key(owned string str) {
+    /*
+     * Computes a collate key.
+     * Has roughly the same effect as g_utf8_collate_key_for_file, except that it doesn't
+     * handle the dot as a special char.
+     */
+    assert (str.validate());
+    string result = "";
+    bool eos = (str.length == 0);
+
+    while (!eos) {
+        assert(str.validate());
+        int position = 0;
+        while (!(str.get_char(position).to_string() in "0123456789")) {
+            // We only care about plain old 0123456789, aping what g_utf8_collate_key_for_filename does
+            position++;
+        }
+
+        // (0... position( is a bunch of non-numerical chars, so we compute and append the collate key...
+        result = result + (str.substring(0, position).collate_key());
+
+        // ...then throw them away
+        str = str.substring(position);
+
+        eos = (str.length == 0);
+        position = 0;
+
+        if (!eos) {
+            // We have some numbers to handle in front of us
+            int number = read_number(str, ref position);
+            str = str.substring(position);
+            int number_of_superdigits = number.to_string().length;
+            string to_append = "";
+            for (int i = 1; i < number_of_superdigits; i++) {
+                // We append n - 1 superdigits where n is the number of digits
+                to_append = to_append + SUPERDIGIT.to_string();
+            }
+            to_append = to_append + (number.to_string()); // We append the actual number
+            result = result +
+                     COLLATION_SENTINEL +
+                     NUM_SENTINEL.to_string() +
+                     to_append;
+        }
+        eos = (str.length == 0);
+    }
+
+    result = result + NUM_SENTINEL.to_string();
+    // No specific reason except that glib does it
+
+    return result;
+}
+}
diff --git a/src/Thumbnail.vala b/src/Thumbnail.vala
index c33d43b..579b7c5 100644
--- a/src/Thumbnail.vala
+++ b/src/Thumbnail.vala
@@ -161,8 +161,7 @@ public class Thumbnail : MediaSourceItem {
     }
     
     public static int64 title_ascending_comparator(void *a, void *b) {
-        int64 result = strcmp(((Thumbnail *) a)->media.get_name(), ((Thumbnail *) b)->media.get_name());
-        
+        int64 result = strcmp(((Thumbnail *) a)->get_natural_collation_key(), ((Thumbnail *) 
b)->get_natural_collation_key());
         return (result != 0) ? result : photo_id_ascending_comparator(a, b);
     }
     
diff --git a/test/.gitignore b/test/.gitignore
new file mode 100644
index 0000000..bed7634
--- /dev/null
+++ b/test/.gitignore
@@ -0,0 +1 @@
+NaturalCollate-Test
diff --git a/test/Makefile b/test/Makefile
new file mode 100644
index 0000000..078ccea
--- /dev/null
+++ b/test/Makefile
@@ -0,0 +1,4 @@
+test: NaturalCollate-Test.vala ../src/NaturalCollate.vala
+       valac NaturalCollate-Test.vala ../src/NaturalCollate.vala && ./NaturalCollate-Test
+clean:
+       rm NaturalCollate-Test
diff --git a/test/NaturalCollate-Test.vala b/test/NaturalCollate-Test.vala
new file mode 100644
index 0000000..be26498
--- /dev/null
+++ b/test/NaturalCollate-Test.vala
@@ -0,0 +1,136 @@
+void add_trailing_numbers_tests () {
+    Test.add_func ("/vala/test", () => {
+            string a = "100foo";
+            string b = "100bar";
+            string coll_a = NaturalCollate.collate_key(a);
+            string coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a, coll_b) > 0);
+            assert(strcmp(a,b) > 0);
+            assert(NaturalCollate.compare(a,b) == strcmp(coll_a, coll_b));
+
+            string atrail = "00100foo";
+            string btrail = "0100bar";
+
+            string coll_atrail = NaturalCollate.collate_key(a);
+            string coll_btrail = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a, coll_atrail) == 0);
+            assert(strcmp(coll_b, coll_btrail) == 0);
+
+            assert(strcmp(coll_atrail, coll_btrail) > 0);
+            assert(strcmp(atrail,btrail) < 0);
+            assert(NaturalCollate.compare(atrail,btrail) == strcmp(coll_atrail, coll_btrail));
+
+        });
+}
+
+void add_numbers_tail_tests () {
+    Test.add_func ("/vala/test", () => {
+            string a = "aaa00100";
+            string b = "aaa02";
+            string coll_a = NaturalCollate.collate_key(a);
+            string coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a, coll_b) > 0);
+            assert(strcmp(a,b) < 0);
+            assert(NaturalCollate.compare(a,b) == strcmp(coll_a, coll_b));
+        });
+}
+
+void add_dots_tests () {
+    Test.add_func ("/vala/test", () => {
+            string sa = "Foo01.jpg";
+            string sb = "Foo2.jpg";
+            string sc = "Foo3.jpg";
+            string sd = "Foo10.jpg";
+
+            assert (strcmp(sa, sd) < 0);
+            assert (strcmp(sd, sb) < 0);
+            assert (strcmp(sb, sc) < 0);
+
+            string coll_sa = NaturalCollate.collate_key(sa);
+            string coll_sb = NaturalCollate.collate_key(sb);
+            string coll_sc = NaturalCollate.collate_key(sc);
+            string coll_sd = NaturalCollate.collate_key(sd);
+
+            assert (strcmp(coll_sa, coll_sb) < 0);
+            assert (strcmp(coll_sb, coll_sc) < 0);
+            assert (strcmp(coll_sc, coll_sd) < 0);
+        });
+}
+
+void add_bigger_as_strcmp_tests () {
+    Test.add_func ("/vala/test", () => {
+            string a = "foo";
+            string b = "bar";
+            string coll_a = NaturalCollate.collate_key(a);
+            string coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a,coll_b) > 0);
+            assert(strcmp(a,b) > 0);
+            assert(NaturalCollate.compare(a,b) == strcmp(coll_a, coll_b));
+
+            a = "foo0001";
+            b = "bar0000";
+            coll_a = NaturalCollate.collate_key(a);
+            coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a,coll_b) > 0);
+            assert(strcmp(a,b) > 0);
+            assert(NaturalCollate.compare(a,b) == strcmp(coll_a, coll_b));
+
+            a = "bar010";
+            b = "bar01";
+            coll_a = NaturalCollate.collate_key(a);
+            coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a,coll_b) > 0);
+            assert(strcmp(a,b) > 0);
+            assert(NaturalCollate.compare(a,b) == strcmp(coll_a, coll_b));
+        });
+}
+
+void add_numbers_tests() {
+    Test.add_func ("/vala/test", () => {
+            string a = "0";
+            string b = "1";
+            string coll_a = NaturalCollate.collate_key(a);
+            string coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a, coll_b) < 0);
+
+            a = "100";
+            b = "101";
+            coll_a = NaturalCollate.collate_key(a);
+            coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a, coll_b) < 0);
+
+            a = "2";
+            b = "10";
+            coll_a = NaturalCollate.collate_key(a);
+            coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a, coll_b) < 0);
+
+            a = "b20";
+            b = "b100";
+            coll_a = NaturalCollate.collate_key(a);
+            coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a, coll_b) < 0);
+        });
+}
+
+void add_ignore_leading_zeros_tests () {
+    Test.add_func ("/vala/test", () => {
+            string a = "bar0000010";
+            string b = "bar10";
+            string coll_a = NaturalCollate.collate_key(a);
+            string coll_b = NaturalCollate.collate_key(b);
+            assert(strcmp(coll_a,coll_b) == 0);
+        });
+}
+
+void main (string[] args) {
+    GLib.Intl.setlocale(GLib.LocaleCategory.ALL, "");
+    Test.init (ref args);
+    add_trailing_numbers_tests();
+    add_numbers_tail_tests();
+    add_bigger_as_strcmp_tests();
+    add_ignore_leading_zeros_tests();
+    add_numbers_tests();
+    add_dots_tests();
+    Test.run();
+}