[gnome-todo] list-model-sort: Introduce sorting model

[Georges Basile Stavracas Neto <gbsneto src gnome org>]

commit 92e8e9afa0d313ba16c97560f7d831c6fc2ed926
Author: Georges Basile Stavracas Neto <georges stavracas gmail com>
Date:   Wed Sep 12 13:48:03 2018 -0300

    list-model-sort: Introduce sorting model
    
    This is a work of art. It contains all the regular model
    optimizations like O(1) sequential g_list_model_get_item(),
    almost no O(n*log n) scenarios, etc.

 meson.build                          |   1 +
 src/contrib/gtd-list-model-sort.c    | 504 +++++++++++++++++++++++++++++++++++
 src/contrib/gtd-list-model-sort.h    |  46 ++++
 src/gnome-todo.h                     |   3 +
 src/meson.build                      |   7 +
 tests/interactive/test-filter-sort.c | 289 ++++++++++++++++++++
 tests/meson.build                    |   2 +
 tests/test-model-sort.c              | 143 ++++++++++
 8 files changed, 995 insertions(+)
---
diff --git a/meson.build b/meson.build
index e0ba184..b35a7b2 100644
--- a/meson.build
+++ b/meson.build
@@ -163,6 +163,7 @@ pkg = import('pkgconfig')
 top_inc = include_directories('.')
 src_inc = include_directories(
   'src',
+  'src/contrib',
   'src/engine',
   'src/interfaces',
   'src/notification',
diff --git a/src/contrib/gtd-list-model-sort.c b/src/contrib/gtd-list-model-sort.c
new file mode 100644
index 0000000..f859df0
--- /dev/null
+++ b/src/contrib/gtd-list-model-sort.c
@@ -0,0 +1,504 @@
+/* gtd-list-model-sort.c
+ *
+ * Copyright 2018 Georges Basile Stavracas Neto <georges stavracas gmail com>
+ *
+ * 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 3 of the License, 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, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#define G_LOG_DOMAIN "GtdListModelSort"
+
+#include "gtd-debug.h"
+#include "gtd-list-model-sort.h"
+#include "gtd-task.h"
+#include "gtd-task-list.h"
+
+struct _GtdListModelSort
+{
+  GObject             parent;
+
+  GListModel         *child_model;
+
+  GSequence          *child_seq;
+  GSequence          *sort_seq;
+
+  GtdListModelCompareFunc compare_func;
+  gpointer            compare_func_data;
+  GDestroyNotify      compare_func_data_destroy;
+
+  gboolean            supress_items_changed : 1;
+
+  /* cache */
+  guint               length;
+  guint               last_position;
+  GSequenceIter      *last_iter;
+};
+
+static void list_model_iface_init (GListModelInterface *iface);
+
+G_DEFINE_TYPE_WITH_CODE (GtdListModelSort, gtd_list_model_sort, G_TYPE_OBJECT,
+                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, list_model_iface_init))
+
+enum
+{
+  PROP_0,
+  PROP_CHILD_MODEL,
+  N_PROPS
+};
+
+static GParamSpec *properties [N_PROPS];
+
+static void
+gtd_list_model_sort_item_free (gpointer data)
+{
+  GSequenceIter *iter = data;
+
+  g_clear_pointer (&iter, g_sequence_remove);
+}
+
+static gint
+seq_compare_func (gconstpointer a,
+                  gconstpointer b,
+                  gpointer      user_data)
+{
+  GtdListModelSort *self = (GtdListModelSort*) user_data;
+
+  return self->compare_func (G_OBJECT (a), G_OBJECT (b), self->compare_func_data);
+}
+
+static gint
+default_compare_func (GObject  *a,
+                      GObject  *b,
+                      gpointer  user_data)
+{
+  return 0;
+}
+
+
+static void
+invalidate_cache (GtdListModelSort *self)
+{
+  GTD_TRACE_MSG ("Invalidating cache");
+
+  self->last_iter = NULL;
+  self->last_position = -1u;
+}
+
+static void
+emit_items_changed (GtdListModelSort *self,
+                    guint             position,
+                    guint             n_removed,
+                    guint             n_added)
+{
+  if (position <= self->last_position)
+    invalidate_cache (self);
+
+  self->length += n_added;
+  self->length -= n_removed;
+
+  GTD_TRACE_MSG ("Emitting items-changed(%u, %u, %u)", position, n_removed, n_added);
+
+  g_list_model_items_changed (G_LIST_MODEL (self), position, n_removed, n_added);
+}
+
+
+static void
+child_model_items_changed (GtdListModelSort *self,
+                           guint             position,
+                           guint             n_removed,
+                           guint             n_added,
+                           GListModel       *child_model)
+{
+  guint i;
+
+  GTD_ENTRY;
+
+  g_assert (GTD_IS_LIST_MODEL_SORT (self));
+  g_assert (G_IS_LIST_MODEL (child_model));
+  g_assert (self->child_model == child_model);
+  g_assert (position <= (guint)g_sequence_get_length (self->child_seq));
+  g_assert (g_sequence_get_length (self->child_seq) - n_removed + n_added == g_list_model_get_n_items 
(child_model));
+
+  GTD_TRACE_MSG ("Received items-changed(%u, %u, %u)", position, n_removed, n_added);
+
+  /* check if the iter cache may have been invalidated */
+  if (position <= self->last_position)
+    invalidate_cache (self);
+
+  if (n_removed > 0)
+    {
+      GSequenceIter *iter;
+      guint previous_sort_position = -1u;
+      guint first_position = -1u;
+      guint counter = 0;
+
+      /* Small shortcut when all items are removed */
+      if (n_removed == (guint)g_sequence_get_length (self->child_seq))
+        {
+          g_sequence_remove_range (g_sequence_get_begin_iter (self->child_seq),
+                                   g_sequence_get_end_iter (self->child_seq));
+
+          g_assert (g_sequence_is_empty (self->child_seq));
+          g_assert (g_sequence_is_empty (self->sort_seq));
+
+          emit_items_changed (self, 0, n_removed, 0);
+
+          goto add_new_items;
+        }
+
+      iter = g_sequence_get_iter_at_pos (self->child_seq, position);
+      g_assert (!g_sequence_iter_is_end (iter));
+
+      for (i = 0; i < n_removed; i++)
+        {
+          GSequenceIter *sort_iter = g_sequence_get (iter);
+          GSequenceIter *to_remove = iter;
+          guint sort_position;
+
+          g_assert (g_sequence_iter_get_sequence (sort_iter) == self->sort_seq);
+
+          sort_position = g_sequence_iter_get_position (sort_iter);
+
+          /* Fetch the next while the iter is still valid */
+          iter = g_sequence_iter_next (iter);
+
+          /* Cascades into also removing from sort_seq. */
+          g_sequence_remove (to_remove);
+
+          if (first_position == -1u)
+            first_position = sort_position;
+
+          /*
+           * This happens when the position in the sorted sequence is different
+           * from the position in the child sequence. We try to accumulate as many
+           * items-changed() signals as possible, but we can't do that when the
+           * order doesn't match.
+           */
+          if (previous_sort_position != -1u && sort_position != previous_sort_position + 1)
+            {
+              emit_items_changed (self, first_position, 0, counter);
+
+              first_position = sort_position;
+              counter = 0;
+            }
+
+          previous_sort_position = sort_position;
+          counter++;
+        }
+
+      /*
+       * Last items-changed() - if the child model is already sorted,
+       * only this one will be fired.
+       */
+      if (counter > 0)
+        emit_items_changed (self, first_position, counter, 0);
+    }
+
+add_new_items:
+
+  if (n_added > 0)
+    {
+      GSequenceIter *iter = g_sequence_get_iter_at_pos (self->child_seq, position);
+      guint previous_sort_position = -1u;
+      guint first_position = -1u;
+      guint counter = 0;
+
+      for (i = 0; i < n_added; i++)
+        {
+          g_autoptr (GObject) instance = NULL;
+          GSequenceIter *sort_iter;
+          guint new_sort_position;
+
+          instance = g_list_model_get_item (child_model, position + i);
+          g_assert (G_IS_OBJECT (instance));
+
+          sort_iter = g_sequence_insert_sorted (self->sort_seq,
+                                                g_steal_pointer (&instance),
+                                                seq_compare_func,
+                                                self);
+
+          new_sort_position = g_sequence_iter_get_position (sort_iter);
+
+          /* Insert next item before this */
+          iter = g_sequence_insert_before (iter, sort_iter);
+          iter = g_sequence_iter_next (iter);
+
+          if (first_position == -1u)
+            first_position = new_sort_position;
+
+          /*
+           * This happens when the position in the sorted sequence is different
+           * from the position in the child sequence. We try to accumulate as many
+           * items-changed() signals as possible, but we can't do that when the
+           * order doesn't match.
+           */
+          if (previous_sort_position != -1u && new_sort_position != previous_sort_position + 1)
+            {
+              emit_items_changed (self, first_position, 0, counter);
+
+              first_position = new_sort_position;
+              counter = 0;
+            }
+
+          previous_sort_position = new_sort_position;
+          counter++;
+        }
+
+      /*
+       * Last items-changed() - if the child model is already sorted,
+       * only this one will be fired.
+       */
+      if (counter > 0)
+        emit_items_changed (self, first_position, 0, counter);
+    }
+
+  g_assert ((guint)g_sequence_get_length (self->child_seq) == g_list_model_get_n_items (child_model));
+  g_assert ((guint)g_sequence_get_length (self->sort_seq) == g_list_model_get_n_items (child_model));
+
+  GTD_EXIT;
+}
+
+
+/*
+ * GListModel iface
+ */
+
+static GType
+gtd_list_model_sort_get_item_type (GListModel *model)
+{
+  GtdListModelSort *self = (GtdListModelSort*) model;
+
+  g_assert (GTD_IS_LIST_MODEL_SORT (self));
+
+  return g_list_model_get_item_type (self->child_model);
+}
+
+static guint
+gtd_list_model_sort_get_n_items (GListModel *model)
+{
+  GtdListModelSort *self = (GtdListModelSort*) model;
+
+  g_assert (GTD_IS_LIST_MODEL_SORT (self));
+  g_assert (self->sort_seq != NULL);
+
+  return self->length;
+}
+
+static gpointer
+gtd_list_model_sort_get_item (GListModel *model,
+                              guint       position)
+{
+  GtdListModelSort *self;
+  GSequenceIter *iter;
+  gpointer item;
+
+  g_assert (GTD_IS_LIST_MODEL_SORT (model));
+
+  self = (GtdListModelSort*) model;
+  iter = NULL;
+
+  if (self->last_position != -1u)
+    {
+      if (self->last_position == position + 1)
+        iter = g_sequence_iter_prev (self->last_iter);
+      else if (self->last_position == position - 1)
+        iter = g_sequence_iter_next (self->last_iter);
+      else if (self->last_position == position)
+        iter = self->last_iter;
+    }
+
+  if (!iter)
+    iter = g_sequence_get_iter_at_pos (self->sort_seq, position);
+
+  if (g_sequence_iter_is_end (iter))
+    return NULL;
+
+  self->last_iter = iter;
+  self->last_position = position;
+
+  item = g_sequence_get (iter);
+  g_assert (item != NULL);
+
+  return g_object_ref (G_OBJECT (item));
+}
+
+static void
+list_model_iface_init (GListModelInterface *iface)
+{
+  iface->get_item_type = gtd_list_model_sort_get_item_type;
+  iface->get_n_items = gtd_list_model_sort_get_n_items;
+  iface->get_item = gtd_list_model_sort_get_item;
+}
+
+
+/*
+ * GObject overrides
+ */
+
+static void
+gtd_list_model_sort_finalize (GObject *object)
+{
+  GtdListModelSort *self = (GtdListModelSort*) object;
+
+  g_clear_pointer (&self->child_seq, g_sequence_free);
+  g_clear_pointer (&self->sort_seq, g_sequence_free);
+
+  if (self->compare_func_data_destroy)
+    {
+      g_clear_pointer (&self->compare_func_data, self->compare_func_data_destroy);
+      self->compare_func_data_destroy = NULL;
+    }
+
+  g_clear_object (&self->child_model);
+
+  G_OBJECT_CLASS (gtd_list_model_sort_parent_class)->finalize (object);
+}
+
+static void
+gtd_list_model_sort_get_property (GObject    *object,
+                                    guint       prop_id,
+                                    GValue     *value,
+                                    GParamSpec *pspec)
+{
+  GtdListModelSort *self = GTD_LIST_MODEL_SORT (object);
+
+  switch (prop_id)
+    {
+    case PROP_CHILD_MODEL:
+      g_value_set_object (value, gtd_list_model_sort_get_child_model (self));
+      break;
+
+    default:
+      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+    }
+}
+
+static void
+gtd_list_model_sort_class_init (GtdListModelSortClass *klass)
+{
+  GObjectClass *object_class = G_OBJECT_CLASS (klass);
+
+  object_class->finalize = gtd_list_model_sort_finalize;
+  object_class->get_property = gtd_list_model_sort_get_property;
+
+  properties [PROP_CHILD_MODEL] = g_param_spec_object ("child-model",
+                                                       "Child Model",
+                                                       "The child model being sorted.",
+                                                       G_TYPE_LIST_MODEL,
+                                                       G_PARAM_READABLE | G_PARAM_STATIC_STRINGS);
+
+  g_object_class_install_properties (object_class, N_PROPS, properties);
+}
+
+static void
+gtd_list_model_sort_init (GtdListModelSort *self)
+{
+  self->compare_func = default_compare_func;
+  self->child_seq = g_sequence_new (gtd_list_model_sort_item_free);
+  self->sort_seq = g_sequence_new (g_object_unref);
+  self->last_position = -1u;
+}
+
+GtdListModelSort *
+gtd_list_model_sort_new (GListModel *child_model)
+{
+  GtdListModelSort *self;
+
+  g_return_val_if_fail (G_IS_LIST_MODEL (child_model), NULL);
+
+  self = g_object_new (GTD_TYPE_LIST_MODEL_SORT, NULL);
+  self->child_model = g_object_ref (child_model);
+
+  g_signal_connect_object (child_model,
+                           "items-changed",
+                           G_CALLBACK (child_model_items_changed),
+                           self,
+                           G_CONNECT_SWAPPED);
+
+  child_model_items_changed (self, 0, 0, g_list_model_get_n_items (child_model), child_model);
+
+  return self;
+}
+
+/**
+ * gtd_list_model_sort_get_child_model:
+ * @self: A #GtdListModelSort
+ *
+ * Gets the child model that is being sorted.
+ *
+ * Returns: (transfer none): A #GListModel.
+ */
+GListModel *
+gtd_list_model_sort_get_child_model (GtdListModelSort *self)
+{
+  g_return_val_if_fail (GTD_IS_LIST_MODEL_SORT (self), NULL);
+
+  return self->child_model;
+}
+
+void
+gtd_list_model_sort_invalidate (GtdListModelSort *self)
+{
+  guint n_items;
+
+  g_return_if_fail (GTD_IS_LIST_MODEL_SORT (self));
+
+  /* First determine how many items we need to synthesize as a removal */
+  n_items = g_sequence_get_length (self->child_seq);
+
+  g_assert (G_IS_LIST_MODEL (self->child_model));
+
+  invalidate_cache (self);
+
+  g_sequence_sort (self->sort_seq, seq_compare_func, self);
+
+  g_assert ((guint)g_sequence_get_length (self->child_seq) == n_items);
+  g_assert ((guint)g_sequence_get_length (self->sort_seq) == n_items);
+
+  if (n_items > 0)
+    emit_items_changed (self, 0, n_items, n_items);
+}
+
+void
+gtd_list_model_sort_set_sort_func (GtdListModelSort        *self,
+                                   GtdListModelCompareFunc  compare_func,
+                                   gpointer                 compare_func_data,
+                                   GDestroyNotify           compare_func_data_destroy)
+{
+  g_return_if_fail (GTD_IS_LIST_MODEL_SORT (self));
+  g_return_if_fail (compare_func || (!compare_func_data && !compare_func_data_destroy));
+
+  GTD_ENTRY;
+
+  if (self->compare_func_data_destroy != NULL)
+    g_clear_pointer (&self->compare_func_data, self->compare_func_data_destroy);
+
+  if (compare_func != NULL)
+    {
+      self->compare_func = compare_func;
+      self->compare_func_data = compare_func_data;
+      self->compare_func_data_destroy = compare_func_data_destroy;
+    }
+  else
+    {
+      self->compare_func = default_compare_func;
+      self->compare_func_data = NULL;
+      self->compare_func_data_destroy = NULL;
+    }
+
+  gtd_list_model_sort_invalidate (self);
+
+  GTD_EXIT;
+}
diff --git a/src/contrib/gtd-list-model-sort.h b/src/contrib/gtd-list-model-sort.h
new file mode 100644
index 0000000..c95db29
--- /dev/null
+++ b/src/contrib/gtd-list-model-sort.h
@@ -0,0 +1,46 @@
+/* gtd-list-model-sort.h
+ *
+ * Copyright 2018 Georges Basile Stavracas Neto <georges stavracas gmail com>
+ *
+ * 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 3 of the License, 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, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include <gio/gio.h>
+
+G_BEGIN_DECLS
+
+#define GTD_TYPE_LIST_MODEL_SORT (gtd_list_model_sort_get_type())
+
+typedef gboolean (*GtdListModelCompareFunc) (GObject  *a,
+                                             GObject  *b,
+                                             gpointer  user_data);
+
+G_DECLARE_FINAL_TYPE (GtdListModelSort, gtd_list_model_sort, GTD, LIST_MODEL_SORT, GObject)
+
+GtdListModelSort*    gtd_list_model_sort_new                     (GListModel         *child_model);
+
+GListModel*          gtd_list_model_sort_get_child_model         (GtdListModelSort   *self);
+
+void                 gtd_list_model_sort_invalidate              (GtdListModelSort   *self);
+
+void                 gtd_list_model_sort_set_sort_func           (GtdListModelSort        *self,
+                                                                  GtdListModelCompareFunc  compare_func,
+                                                                  gpointer                 compare_func_data,
+                                                                  GDestroyNotify           
compare_func_data_destroy);
+
+G_END_DECLS
diff --git a/src/gnome-todo.h b/src/gnome-todo.h
index 3709737..f09ac26 100644
--- a/src/gnome-todo.h
+++ b/src/gnome-todo.h
@@ -21,6 +21,9 @@
 
 #include "gtd-activatable.h"
 #include "gtd-enums.h"
+#include "gtd-list-model-filter.h"
+#include "gtd-list-model-sort.h"
+#include "gtd-list-store.h"
 #include "gtd-manager.h"
 #include "gtd-notification.h"
 #include "gtd-object.h"
diff --git a/src/meson.build b/src/meson.build
index c610f69..6948cec 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -6,6 +6,8 @@
 enum_headers = files('gtd-enums.h')
 
 headers = enum_headers + files(
+  'contrib/gtd-list-model-filter.h',
+  'contrib/gtd-list-store.h',
   'engine/gtd-manager.h',
   'interfaces/gtd-activatable.h',
   'interfaces/gtd-panel.h',
@@ -31,6 +33,7 @@ install_headers(headers, subdir: meson.project_name())
 
 sources = files(
   'contrib/gtd-list-model-filter.c',
+  'contrib/gtd-list-model-sort.c',
   'contrib/gtd-list-store.c',
   'contrib/gtd-task-model.c',
   'engine/gtd-manager.c',
@@ -195,6 +198,10 @@ pkg.generate(
 
 if get_option('introspection')
   gir_sources = files(
+    'contrib/gtd-list-model-filter.c',
+    'contrib/gtd-list-model-filter.h',
+    'contrib/gtd-list-store.c',
+    'contrib/gtd-list-store.h',
     'engine/gtd-manager.c',
     'engine/gtd-manager.h',
     'interfaces/gtd-activatable.c',
diff --git a/tests/interactive/test-filter-sort.c b/tests/interactive/test-filter-sort.c
new file mode 100644
index 0000000..355dfee
--- /dev/null
+++ b/tests/interactive/test-filter-sort.c
@@ -0,0 +1,289 @@
+/* test-filter-sort.c
+ *
+ * Copyright 2018 Georges Basile Stavracas Neto <georges stavracas gmail com>
+ *
+ * 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 3 of the License, 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, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+
+#include <gtk/gtk.h>
+
+#include "contrib/gtd-list-model-filter.h"
+#include "contrib/gtd-list-model-sort.h"
+#include "contrib/gtd-task-model.h"
+#include "contrib/gtd-task-model-private.h"
+#include "logging/gtd-log.h"
+#include "dummy-provider.h"
+#include "gtd-manager.h"
+#include "gtd-manager-protected.h"
+#include "gtd-provider.h"
+#include "gtd-task.h"
+#include "gtd-task-list.h"
+#include "gtd-utils.h"
+
+
+/*
+ * Auxiliary methods
+ */
+
+static GtkWidget*
+create_bold_label_for_task_row (GtkListBoxRow *row)
+{
+  g_autofree gchar *markup = NULL;
+  GtdTask *task;
+
+  task = g_object_get_data (G_OBJECT (row), "task");
+  markup = g_strdup_printf ("<big><b>%s</b></big>", gtd_task_list_get_name (gtd_task_get_list (task)));
+
+  return g_object_new (GTK_TYPE_LABEL,
+                       "margin", 6,
+                       "margin-top", 18,
+                       "use-markup", TRUE,
+                       "label", markup,
+                       "xalign", 0.0,
+                       NULL);
+}
+
+static GtkWidget*
+create_label_for_string (const gchar *string)
+{
+  return g_object_new (GTK_TYPE_LABEL,
+                       "label", string,
+                       "hexpand", TRUE,
+                       "xalign", 0.0,
+                       "margin", 6,
+                       "margin-start", 18,
+                       NULL);
+}
+
+
+/*
+ * Callbacks
+ */
+
+static void
+header_func (GtkListBoxRow *row,
+             GtkListBoxRow *before,
+             gpointer       user_data)
+{
+  GtkWidget *header = NULL;
+
+  if (!before)
+    {
+      header = create_bold_label_for_task_row (row);
+    }
+  else
+    {
+      GtdTask *before_task;
+      GtdTask *task;
+
+      before_task = g_object_get_data (G_OBJECT (before), "task");
+      task = g_object_get_data (G_OBJECT (row), "task");
+
+      if (gtd_task_get_list (task) != gtd_task_get_list (before_task))
+        header = create_bold_label_for_task_row (row);
+    }
+
+  gtk_list_box_row_set_header (row, header);
+}
+
+static gboolean
+filter_func (GObject *item,
+             gpointer user_data)
+{
+  g_autofree gchar *normalized_entry_text = NULL;
+  g_autofree gchar *normalized_task_name = NULL;
+  GtkEntry *entry;
+  GtdTask *task;
+
+  task = (GtdTask*) item;
+  entry = (GtkEntry*) user_data;
+
+  normalized_entry_text = gtd_normalize_casefold_and_unaccent (gtk_entry_get_text (entry));
+  normalized_task_name = gtd_normalize_casefold_and_unaccent (gtd_task_get_title (task));
+
+  return strstr (normalized_task_name, normalized_entry_text) != NULL;
+}
+
+static GtkWidget*
+create_task_cb (gpointer item,
+                gpointer user_data)
+{
+  GtkWidget *row;
+  GtkWidget *box;
+  GtdTask *task;
+
+  task = item;
+
+  box = gtk_box_new (GTK_ORIENTATION_HORIZONTAL, 16);
+
+  gtk_container_add (GTK_CONTAINER (box), create_label_for_string (gtd_task_get_title (task)));
+
+  row = gtk_list_box_row_new ();
+  gtk_container_add (GTK_CONTAINER (row), box);
+
+  g_object_set_data (G_OBJECT (row), "task", task);
+
+  return row;
+}
+
+static gint
+sort_func (GObject  *a,
+           GObject  *b,
+           gpointer  user_data)
+{
+  GtkToggleButton *check;
+  GtdTask *task_a;
+  GtdTask *task_b;
+
+  check = (GtkToggleButton*) user_data;
+
+  if (gtk_toggle_button_get_active (check))
+    {
+      task_a = GTD_TASK (a);
+      task_b = GTD_TASK (b);
+    }
+  else
+    {
+      task_a = GTD_TASK (b);
+      task_b = GTD_TASK (a);
+    }
+
+  if (gtd_task_get_list (task_a) == gtd_task_get_list (task_b))
+    {
+      return gtd_task_compare (task_b, task_a);
+    }
+  else
+    {
+      GtdTaskList *list_a = gtd_task_get_list (task_a);
+      GtdTaskList *list_b = gtd_task_get_list (task_b);
+
+      return g_strcmp0 (gtd_task_list_get_name (list_b), gtd_task_list_get_name (list_a));
+    }
+}
+
+static void
+on_check_active_changed_cb (GtkToggleButton  *check,
+                            GParamSpec       *pspec,
+                            GtdListModelSort *sort)
+{
+  gtd_list_model_sort_invalidate (sort);
+}
+
+static void
+on_remove_button_clicked_cb (GtkButton     *button,
+                             DummyProvider *provider)
+{
+  dummy_provider_randomly_remove_task (provider);
+}
+
+static void
+on_search_text_changed_cb (GtkEntry           *entry,
+                           GParamSpec         *pspec,
+                           GtdListModelFilter *filter)
+{
+  gtd_list_model_filter_invalidate (filter);
+}
+
+gint
+main (gint   argc,
+      gchar *argv[])
+{
+  g_autoptr (GtdListModelFilter) filter = NULL;
+  g_autoptr (GtdListModelSort) sort = NULL;
+  g_autoptr (DummyProvider) dummy_provider = NULL;
+  GtdTaskModel *model = NULL;
+  GtkWidget *scrolledwindow = NULL;
+  GtkWidget *search_entry = NULL;
+  GtkWindow *window = NULL;
+  GtkWidget *listbox = NULL;
+  GtkWidget *button = NULL;
+  GtkWidget *check = NULL;
+  GtkWidget *hbox = NULL;
+  GtkWidget *vbox = NULL;
+
+  g_set_prgname ("test-filter-sort");
+  g_set_application_name ("GNOME To Do | Filter & Sort Test");
+
+  gtk_init ();
+  gtd_log_init ();
+
+  /* Create a DumbProvider and pre-populate it */
+  dummy_provider = dummy_provider_new ();
+  dummy_provider_generate_task_lists (dummy_provider);
+  dummy_provider_generate_task_lists (dummy_provider);
+  _gtd_manager_inject_provider (gtd_manager_get_default (), GTD_PROVIDER (dummy_provider));
+
+  /* Models */
+  model = _gtd_task_model_new (gtd_manager_get_default ());
+  filter = gtd_list_model_filter_new (G_LIST_MODEL (model));
+  sort = gtd_list_model_sort_new (G_LIST_MODEL (filter));
+
+  /* Listbox */
+  listbox = gtk_list_box_new ();
+  gtk_list_box_bind_model (GTK_LIST_BOX (listbox),
+                           G_LIST_MODEL (sort),
+                           create_task_cb,
+                           NULL,
+                           NULL);
+
+  gtk_list_box_set_header_func (GTK_LIST_BOX (listbox), header_func, NULL, NULL);
+
+  /* Scrolled window */
+  scrolledwindow = g_object_new (GTK_TYPE_SCROLLED_WINDOW,
+                                 "propagate-natural-height", TRUE,
+                                 "max-content-height", 600,
+                                 "hscrollbar-policy", GTK_POLICY_NEVER,
+                                 NULL);
+  gtk_container_add (GTK_CONTAINER (scrolledwindow), listbox);
+
+  /* Search entry */
+  search_entry = gtk_search_entry_new ();
+  gtd_list_model_filter_set_filter_func (filter, filter_func, search_entry, NULL);
+
+  g_signal_connect_object (search_entry, "notify::text", G_CALLBACK (on_search_text_changed_cb), filter, 0);
+
+  /* Reverse order checkbox */
+  check = gtk_check_button_new_with_label ("Reverse Order");
+  gtd_list_model_sort_set_sort_func (sort, sort_func, check, NULL);
+
+  g_signal_connect_object (check, "notify::active", G_CALLBACK (on_check_active_changed_cb), sort, 0);
+
+  /* Remove Tasks button */
+  button = gtk_button_new_with_label ("Randomly Remove Tasks");
+  g_signal_connect_object (button, "clicked", G_CALLBACK (on_remove_button_clicked_cb), dummy_provider, 0);
+
+  /* Horizontal box */
+  hbox = gtk_box_new (GTK_ORIENTATION_HORIZONTAL, 12);
+  gtk_container_add (GTK_CONTAINER (hbox), search_entry);
+  gtk_container_add (GTK_CONTAINER (hbox), check);
+  gtk_container_add (GTK_CONTAINER (hbox), button);
+
+  /* Box */
+  vbox = gtk_box_new (GTK_ORIENTATION_VERTICAL, 12);
+  gtk_container_add (GTK_CONTAINER (vbox), hbox);
+  gtk_container_add (GTK_CONTAINER (vbox), scrolledwindow);
+
+  /* Window */
+  window = GTK_WINDOW (gtk_window_new (GTK_WINDOW_TOPLEVEL));
+  gtk_window_set_default_size (window, 800, 600);
+  gtk_container_add (GTK_CONTAINER (window), vbox);
+  gtk_window_present (window);
+
+  gtk_main ();
+
+  return 0;
+}
diff --git a/tests/meson.build b/tests/meson.build
index 33e0307..223aac6 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -50,6 +50,7 @@ static_test_link_args = ['-fPIC']
 
 static_tests = [
   'test-model-filter',
+  'test-model-sort',
   'test-task-model',
 ]
 
@@ -78,6 +79,7 @@ endforeach
 
 interactive_tests = [
   'test-colorbutton',
+  'test-filter-sort',
   'test-task-model',
 ]
 
diff --git a/tests/test-model-sort.c b/tests/test-model-sort.c
new file mode 100644
index 0000000..e4426fc
--- /dev/null
+++ b/tests/test-model-sort.c
@@ -0,0 +1,143 @@
+/* test-model-sort.c
+ *
+ * Copyright 2018 Georges Basile Stavracas Neto <georges stavracas gmail com>
+ *
+ * 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 3 of the License, 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, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "contrib/gtd-list-model-sort.h"
+
+#include <math.h>
+#include <string.h>
+
+#define TEST_TYPE_ITEM (test_item_get_type())
+
+struct _TestItem
+{
+  GObject p;
+  guint n;
+};
+
+G_DECLARE_FINAL_TYPE (TestItem, test_item, TEST, ITEM, GObject)
+G_DEFINE_TYPE (TestItem, test_item, G_TYPE_OBJECT)
+
+static void
+test_item_class_init (TestItemClass *klass)
+{
+}
+
+static void
+test_item_init (TestItem *self)
+{
+}
+
+static TestItem *
+test_item_new (guint n)
+{
+  TestItem *item;
+
+  item = g_object_new (TEST_TYPE_ITEM, NULL);
+  item->n = n;
+
+  return item;
+}
+
+static gint
+sort_func1 (GObject  *a,
+            GObject  *b,
+            gpointer  user_data)
+{
+  return TEST_ITEM (a)->n - TEST_ITEM (b)->n;
+}
+
+static gint
+sort_func2 (GObject  *a,
+            GObject  *b,
+            gpointer  user_data)
+{
+  return (TEST_ITEM (a)->n & 1) - (TEST_ITEM (b)->n & 1);
+}
+
+static void
+test_basic (void)
+{
+  GtdListModelSort *sort;
+  GListStore *model;
+  guint i;
+
+  model = g_list_store_new (TEST_TYPE_ITEM);
+  g_assert (model);
+
+  sort = gtd_list_model_sort_new (G_LIST_MODEL (model));
+  g_assert (sort);
+
+  /* Test requesting past boundary */
+  g_assert_null (g_list_model_get_item (G_LIST_MODEL (sort), 0));
+  g_assert_null (g_list_model_get_item (G_LIST_MODEL (sort), 1));
+
+  for (i = 0; i < 1000; i++)
+    {
+      g_autoptr (TestItem) val = test_item_new (1000 - i);
+      g_list_store_append (model, val);
+    }
+
+  /* Test requesting past boundary */
+  g_assert_null (g_list_model_get_item (G_LIST_MODEL (sort), 1000));
+
+  /* Ascendent sorting */
+  gtd_list_model_sort_set_sort_func (sort, sort_func1, NULL, NULL);
+
+  g_assert_cmpint (1000, ==, g_list_model_get_n_items (G_LIST_MODEL (model)));
+  g_assert_cmpint (1000, ==, g_list_model_get_n_items (G_LIST_MODEL (sort)));
+
+  for (i = 1; i < 1000; i++)
+    {
+      g_autoptr (TestItem) current = g_list_model_get_item (G_LIST_MODEL (sort), i);
+      g_autoptr (TestItem) previous = g_list_model_get_item (G_LIST_MODEL (sort), i - 1);
+
+      g_assert_cmpint (previous->n, <, current->n);
+    }
+
+  /* Odd/Even sorting */
+  gtd_list_model_sort_set_sort_func (sort, sort_func2, NULL, NULL);
+
+  g_assert_cmpint (1000, ==, g_list_model_get_n_items (G_LIST_MODEL (model)));
+  g_assert_cmpint (1000, ==, g_list_model_get_n_items (G_LIST_MODEL (sort)));
+
+  for (i = 0; i < 1000; i++)
+    {
+      g_autoptr (TestItem) current = g_list_model_get_item (G_LIST_MODEL (sort), i);
+
+      if (i < 500)
+        g_assert_cmpint (current->n % 2, ==, 0);
+      else
+        g_assert_cmpint (current->n % 2, ==, 1);
+    }
+
+  g_clear_object (&model);
+  g_clear_object (&sort);
+}
+
+gint
+main (gint argc,
+      gchar *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+
+  g_test_add_func ("/contrib/model-sort/basic", test_basic);
+
+  return g_test_run ();
+}