[geary] Replace uses of Gee.TreeSet where used for sorting

[Michael Gratton <mjog src gnome org>]

commit 89642c52832a57f8354383d5c13ba1e67c867624
Author: Michael Gratton <mike vee net>
Date:   Wed Nov 20 12:46:36 2019 +1100

    Replace uses of Gee.TreeSet where used for sorting
    
    Add new Geary.Iterable::to_sorted_list method that should be more
    performant than adding elements to a sorted set and sorting one-by-one,
    use that instead of a TreeSet.

 .../conversation-list/conversation-list-store.vala | 10 ++++----
 src/engine/imap/command/imap-message-set.vala      |  6 ++---
 src/engine/rfc822/rfc822-mailbox-addresses.vala    | 28 +++++++++++++--------
 src/engine/util/util-iterable.vala                 | 13 ++++++++++
 test/engine/rfc822-mailbox-addresses-test.vala     | 29 ++++++++++++++++++++++
 5 files changed, 67 insertions(+), 19 deletions(-)
---
diff --git a/src/client/conversation-list/conversation-list-store.vala 
b/src/client/conversation-list/conversation-list-store.vala
index a4542867..814e0231 100644
--- a/src/client/conversation-list/conversation-list-store.vala
+++ b/src/client/conversation-list/conversation-list-store.vala
@@ -226,11 +226,11 @@ public class ConversationListStore : Gtk.ListStore {
 
         // sort the conversations so the previews are fetched from the newest to the oldest, matching
         // the user experience
-        Gee.TreeSet<Geary.App.Conversation> sorted_conversations =
-            new Gee.TreeSet<Geary.App.Conversation>(
-                Util.Email.compare_conversation_descending
-            );
-        sorted_conversations.add_all(this.conversations.read_only_view);
+        var sorted_conversations = Geary.traverse(
+            this.conversations.read_only_view
+        ).to_sorted_list(
+            Util.Email.compare_conversation_descending
+        );
         foreach (Geary.App.Conversation conversation in sorted_conversations) {
             // find oldest unread message for the preview
             Geary.Email? need_preview = null;
diff --git a/src/engine/imap/command/imap-message-set.vala b/src/engine/imap/command/imap-message-set.vala
index d47292a7..37903619 100644
--- a/src/engine/imap/command/imap-message-set.vala
+++ b/src/engine/imap/command/imap-message-set.vala
@@ -328,8 +328,7 @@ public class Geary.Imap.MessageSet : BaseObject {
 
     private static int64[] seq_array_to_int64(Gee.Collection<SequenceNumber> seq_nums) {
         // guarantee sorted (to maximum finding runs in build_sparse_range())
-        Gee.TreeSet<SequenceNumber> sorted = new Gee.TreeSet<SequenceNumber>();
-        sorted.add_all(seq_nums);
+        var sorted = traverse(seq_nums).to_sorted_list((a,b) => a.compare_to(b));
 
         // build sorted array
         int64[] ret = new int64[sorted.size];
@@ -342,8 +341,7 @@ public class Geary.Imap.MessageSet : BaseObject {
 
     private static int64[] uid_array_to_int64(Gee.Collection<UID> msg_uids) {
         // guarantee sorted (to maximize finding runs in build_sparse_range())
-        Gee.TreeSet<UID> sorted = new Gee.TreeSet<UID>();
-        sorted.add_all(msg_uids);
+        var sorted = traverse(msg_uids).to_sorted_list((a,b) => a.compare_to(b));
 
         // build sorted array
         int64[] ret = new int64[sorted.size];
diff --git a/src/engine/rfc822/rfc822-mailbox-addresses.vala b/src/engine/rfc822/rfc822-mailbox-addresses.vala
index 616c28ab..8ebf79de 100644
--- a/src/engine/rfc822/rfc822-mailbox-addresses.vala
+++ b/src/engine/rfc822/rfc822-mailbox-addresses.vala
@@ -59,6 +59,9 @@ public class Geary.RFC822.MailboxAddresses :
 
     private Gee.List<MailboxAddress> addrs = new Gee.ArrayList<MailboxAddress>();
 
+    private bool hash_cached = false;
+    private uint hash_value = 0;
+
 
     public MailboxAddresses(Gee.Collection<MailboxAddress>? addrs = null) {
         if (addrs != null) {
@@ -170,17 +173,22 @@ public class Geary.RFC822.MailboxAddresses :
     }
 
     public uint hash() {
-        // create sorted set to ensure ordering no matter the list's order
-        Gee.TreeSet<string> sorted_addresses = traverse<RFC822.MailboxAddress>(addrs)
-            .map<string>(m => m.address)
-            .to_tree_set(String.stri_cmp);
-
-        // xor all strings in sorted order
-        uint xor = 0;
-        foreach (string address in sorted_addresses)
-            xor ^= address.hash();
+        if (!this.hash_cached) {
+            // Sort the addresses to ensure a stable hash
+            var sorted_addresses = traverse<RFC822.MailboxAddress>(addrs)
+                .map<string>(m => m.address)
+                .to_sorted_list(String.stri_cmp);
+
+            // xor all strings in sorted order
+            uint xor = 0;
+            foreach (string address in sorted_addresses) {
+                xor ^= address.hash();
+            }
+            this.hash_value = xor;
+            this.hash_cached = true;
+        }
 
-        return xor;
+        return this.hash_value;
     }
 
     public bool equal_to(MailboxAddresses other) {
diff --git a/src/engine/util/util-iterable.vala b/src/engine/util/util-iterable.vala
index 29ff8e27..aa54e549 100644
--- a/src/engine/util/util-iterable.vala
+++ b/src/engine/util/util-iterable.vala
@@ -225,6 +225,19 @@ public class Geary.Iterable<G> : BaseObject {
         return (Gee.ArrayList<G>) add_all_to(new Gee.ArrayList<G>((owned) equal_func));
     }
 
+    /**
+     * Returns a new list containing all elements, sorted.
+     *
+     * The ordering is applied after adding all elements to the list,
+     * so as to minimise computational overhead.
+     */
+    public Gee.ArrayList<G> to_sorted_list(owned GLib.CompareDataFunc<G> comparator,
+                                           owned Gee.EqualDataFunc<G>? equal_func = null) {
+        var list = to_array_list((owned) equal_func);
+        list.sort((owned) comparator);
+        return list;
+    }
+
     /** Returns a new linked list containing all elements. */
     public Gee.LinkedList<G> to_linked_list(owned Gee.EqualDataFunc<G>? equal_func = null) {
         return (Gee.LinkedList<G>) add_all_to(new Gee.LinkedList<G>((owned) equal_func));
diff --git a/test/engine/rfc822-mailbox-addresses-test.vala b/test/engine/rfc822-mailbox-addresses-test.vala
index a9b2415e..70e535d5 100644
--- a/test/engine/rfc822-mailbox-addresses-test.vala
+++ b/test/engine/rfc822-mailbox-addresses-test.vala
@@ -13,6 +13,7 @@ class Geary.RFC822.MailboxAddressesTest : TestCase {
         add_test("from_rfc822_string_quoted", from_rfc822_string_quoted);
         add_test("to_rfc822_string", to_rfc822_string);
         add_test("equal_to", equal_to);
+        add_test("hash", hash);
     }
 
     public void from_rfc822_string_encoded() throws Error {
@@ -82,6 +83,34 @@ class Geary.RFC822.MailboxAddressesTest : TestCase {
         );
     }
 
+    public void hash() throws Error {
+        var mailboxes_a = new_addreses({ "test1 example com" });
+        var mailboxes_b = new_addreses({ "test1 example com" });
+        var mailboxes_c = new_addreses({ "test2 example com" });
+
+        assert_true(mailboxes_a.hash() == mailboxes_a.hash());
+        assert_true(mailboxes_a.hash() == mailboxes_b.hash());
+        assert_false(mailboxes_a.hash() == mailboxes_c.hash());
+
+        assert_true(
+            new_addreses({ "test1 example com", "test2 example com" }).hash() ==
+            new_addreses({ "test1 example com", "test2 example com" }).hash()
+        );
+        assert_true(
+            new_addreses({ "test1 example com", "test2 example com" }).hash() ==
+            new_addreses({ "test2 example com", "test1 example com" }).hash()
+        );
+
+        assert_false(
+            new_addreses({ "test1 example com", "test2 example com" }).hash() ==
+            new_addreses({ "test1 example com" }).hash()
+        );
+        assert_false(
+            new_addreses({ "test1 example com", "test2 example com" }).hash() ==
+            new_addreses({ "test1 example com", "test3 example com" }).hash()
+        );
+    }
+
     private MailboxAddresses new_addreses(string[] address_strings) {
         Gee.List<MailboxAddress> addresses = new Gee.LinkedList<MailboxAddress>();
         foreach (string address in address_strings) {