[gtk+/filesystemmodel: 16/28] implement sorting

[Benjamin Otte <otte src gnome org>]

commit 5d4eb12db4069ae7ed8fd985aeafa5faf73fee28
Author: Benjamin Otte <otte gnome org>
Date:   Mon Jun 22 11:29:01 2009 +0200

    implement sorting

 gtk/gtkfilesystemmodel.c |  119 +++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 112 insertions(+), 7 deletions(-)
---
diff --git a/gtk/gtkfilesystemmodel.c b/gtk/gtkfilesystemmodel.c
index ef03b13..34d8396 100644
--- a/gtk/gtkfilesystemmodel.c
+++ b/gtk/gtkfilesystemmodel.c
@@ -40,7 +40,7 @@
 #define IO_PRIORITY G_PRIORITY_DEFAULT
 
 /* random number that everyone else seems to use, too */
-#define FILES_PER_QUERY 100
+#define FILES_PER_QUERY 100000
 
 typedef struct _FileModelNode           FileModelNode;
 typedef struct _GtkFileSystemModelClass GtkFileSystemModelClass;
@@ -118,15 +118,16 @@ struct _GtkFileSystemModelClass
 #define ITER_INDEX(iter) GPOINTER_TO_UINT((iter)->user_data2)
 #define ITER_IS_VALID(model, iter) ((model) == (iter)->user_data)
 #define ITER_INIT_FROM_INDEX(model, _iter, _index) G_STMT_START {\
-  g_assert (_index < model->files->len); \
-  (_iter)->user_data = model; \
+  g_assert (_index < (model)->files->len); \
+  (_iter)->user_data = (model); \
   (_iter)->user_data2 = GUINT_TO_POINTER (_index); \
 }G_STMT_END
 
 /*** FileModelNode ***/
 
-#define NODE_SIZE(_model) (sizeof (FileModelNode) + sizeof (GValue) * (MAX ((model)->n_columns, 1) - 1))
+#define NODE_SIZE(_model) (sizeof (FileModelNode) + sizeof (GValue) * (MAX ((_model)->n_columns, 1) - 1))
 #define get_node(_model, _index) ((FileModelNode *) (((guint8 *) (_model)->files->data) + (_index) * NODE_SIZE (_model)))
+#define node_index(_model, _node) (((guint8 *) (_node) - (guint8 *) (_model)->files->data) / NODE_SIZE (_model))
 
 static void
 node_validate_indexes (GtkFileSystemModel *model, guint min_index, guint min_visible)
@@ -300,7 +301,7 @@ gtk_file_system_model_iter_nth_child (GtkTreeModel *tree_model,
       if (node == NULL)
         return FALSE;
 
-      id = (node - model->files->data) / NODE_SIZE (model);
+      id = node_index (model, node);
       while (!get_node (model, id)->visible)
         id--;
     }
@@ -353,7 +354,6 @@ gtk_file_system_model_get_value (GtkTreeModel *tree_model,
   g_return_if_fail (ITER_IS_VALID (model, iter));
 
   node = get_node (model, ITER_INDEX (iter));
-  g_assert (node->visible);
   
   if (!G_VALUE_TYPE (&node->values[column]))
     {
@@ -463,20 +463,122 @@ gtk_file_system_model_iface_init (GtkTreeModelIface *iface)
 
 /*** GtkTreeSortable ***/
 
+typedef struct _SortData SortData;
+struct _SortData {
+  GtkFileSystemModel *    model;
+  GtkTreeIterCompareFunc  func;
+  gpointer                data;
+  int                     order;        /* -1 to invert sort order or 1 to keep it */
+};
+
+/* returns FALSE if no sort necessary */
+static gboolean
+sort_data_init (SortData *data, GtkFileSystemModel *model)
+{
+  GtkTreeDataSortHeader *header;
+
+  if (model->files->len <= 2)
+    return FALSE;
+
+  switch (model->sort_column_id)
+    {
+    case GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID:
+      if (!model->default_sort_func)
+        return FALSE;
+      data->func = model->default_sort_func;
+      data->data = model->default_sort_data;
+      break;
+    case GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID:
+      return FALSE;
+    default:
+      header = _gtk_tree_data_list_get_header (model->sort_list, model->sort_column_id);
+      if (header == NULL)
+        return FALSE;
+      data->func = header->func;
+      data->data = header->data;
+      break;
+    }
+
+  data->order = model->sort_order == GTK_SORT_DESCENDING ? -1 : 1;
+  data->model = model;
+  return TRUE;
+}
+
+static int
+compare_array_element (gconstpointer a, gconstpointer b, gpointer user_data)
+{
+  SortData *data = user_data;
+  GtkTreeIter itera, iterb;
+
+  ITER_INIT_FROM_INDEX (data->model, &itera, node_index (data->model, a));
+  ITER_INIT_FROM_INDEX (data->model, &iterb, node_index (data->model, b));
+  return data->func (GTK_TREE_MODEL (data->model), &itera, &iterb, data->data) * data->order;
+}
+
 static void
 gtk_file_system_model_sort (GtkFileSystemModel *model)
 {
+  SortData data;
+
   if (model->frozen)
     {
       model->sort_on_thaw = TRUE;
       return;
     }
 
-  g_warning ("sort not implemented");
+  if (sort_data_init (&data, model))
+    {
+      GtkTreePath *path;
+      guint i, j, n_elements;
+
+      node_validate_indexes (model, G_MAXUINT, G_MAXUINT);
+      n_elements = node_get_index (model, model->files->len - 1) + 1;
+      model->n_indexes_valid = 0;
+      g_qsort_with_data (get_node (model, 1),
+                         model->files->len - 1,
+                         NODE_SIZE (model),
+                         compare_array_element,
+                         &data);
+      g_assert (model->n_indexes_valid == 0);
+      if (n_elements)
+        {
+          int *new_order = g_new (int, n_elements);
+        
+          j = 0;
+          for (i = 0; i < model->files->len; i++)
+            {
+              FileModelNode *node = get_node (model, i);
+              if (!node->visible)
+                {
+                  node->index = j;
+                  continue;
+                }
+
+              new_order[j] = node->index;
+              j++;
+              node->index = j;
+            }
+          g_assert (j == n_elements);
+          path = gtk_tree_path_new ();
+          gtk_tree_model_rows_reordered (GTK_TREE_MODEL (model),
+                                         path,
+                                         NULL,
+                                         new_order);
+          gtk_tree_path_free (path);
+          g_free (new_order);
+        }
+    }
 
   model->sort_on_thaw = FALSE;
 }
 
+static void
+gtk_file_system_model_sort_node (GtkFileSystemModel *model, guint node)
+{
+  /* FIXME: improve */
+  gtk_file_system_model_sort (model);
+}
+
 static gboolean
 gtk_file_system_model_get_sort_column_id (GtkTreeSortable  *sortable,
                                           gint             *sort_column_id,
@@ -734,6 +836,7 @@ gtk_file_system_model_add_node (GtkFileSystemModel *model, GFile *file, GFileInf
   if (!model->frozen)
     node_set_visible (model, model->files->len -1,
                       node_should_be_visible (model, model->files->len - 1));
+  gtk_file_system_model_sort_node (model, model->files->len -1);
 }
 
 static void
@@ -743,6 +846,8 @@ _gtk_file_system_model_init (GtkFileSystemModel *model)
   model->show_folders = TRUE;
   model->show_hidden = FALSE;
 
+  model->sort_column_id = GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID;
+
   model->cancellable = g_cancellable_new ();
 }