Pileus Git - ~andy/gtk/blob - gtk/gtktreemodelsort.c

   1 /* gtktreemodelsort.c
   2  * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20
  21 /* NOTE: There is a potential for confusion in this code as to whether an iter,
  22  * path or value refers to the GtkTreeModelSort model, or the child model being
  23  * sorted.  As a convention, variables referencing the child model will have an
  24  * s_ prefix before them (ie. s_iter, s_value, s_path);
  25  */
  26
  27 #include "gtktreemodelsort.h"
  28 #include "gtktreesortable.h"
  29 #include "gtksignal.h"
  30 #include "gtktreedatalist.h"
  31 #include <string.h>
  32
  33
  34
  35 typedef struct _SortElt SortElt;
  36 struct _SortElt
  37 {
  38   GtkTreeIter iter;
  39   SortElt *parent;
  40   GArray *children;
  41   gint ref;
  42   gint offset;
  43 };
  44
  45 typedef struct _SortData SortData;
  46 struct _SortData
  47 {
  48   GtkTreeModel *model;
  49   gint sort_col;
  50   GValueCompareFunc func;
  51 };
  52
  53
  54 #define get_array(e,t) ((GArray *)((e)->parent?(e)->parent->children:GTK_TREE_MODEL_SORT(t)->root))
  55
  56
  57 static void         gtk_tree_model_sort_init            (GtkTreeModelSort      *tree_model_sort);
  58 static void         gtk_tree_model_sort_class_init      (GtkTreeModelSortClass *tree_model_sort_class);
  59 static void         gtk_tree_model_sort_tree_model_init (GtkTreeModelIface     *iface);
  60 static void         gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface   *iface);
  61 static void         gtk_tree_model_sort_finalize        (GObject               *object);
  62 static void         gtk_tree_model_sort_range_changed   (GtkTreeModel          *model,
  63                                                          GtkTreePath           *start_path,
  64                                                          GtkTreeIter           *start_iter,
  65                                                          GtkTreePath           *end_path,
  66                                                          GtkTreeIter           *end_iter,
  67                                                          gpointer               data);
  68 static void         gtk_tree_model_sort_inserted        (GtkTreeModel          *model,
  69                                                          GtkTreePath           *path,
  70                                                          GtkTreeIter           *iter,
  71                                                          gpointer               data);
  72 static void         gtk_tree_model_sort_has_child_toggled   (GtkTreeModel          *model,
  73                                                              GtkTreePath           *path,
  74                                                              GtkTreeIter           *iter,
  75                                                              gpointer               data);
  76 static void         gtk_tree_model_sort_deleted         (GtkTreeModel          *model,
  77                                                          GtkTreePath           *path,
  78                                                          gpointer               data);
  79 static gint         gtk_tree_model_sort_get_n_columns   (GtkTreeModel          *tree_model);
  80 static GType        gtk_tree_model_sort_get_column_type (GtkTreeModel          *tree_model,
  81                                                          gint                   index);
  82 static gboolean     gtk_tree_model_sort_get_iter        (GtkTreeModel          *tree_model,
  83                                                          GtkTreeIter           *iter,
  84                                                          GtkTreePath           *path);
  85 static GtkTreePath *gtk_tree_model_sort_get_path        (GtkTreeModel          *tree_model,
  86                                                          GtkTreeIter           *iter);
  87 static void         gtk_tree_model_sort_get_value       (GtkTreeModel          *tree_model,
  88                                                          GtkTreeIter           *iter,
  89                                                          gint                   column,
  90                                                          GValue                *value);
  91 static gboolean     gtk_tree_model_sort_iter_next       (GtkTreeModel          *tree_model,
  92                                                          GtkTreeIter           *iter);
  93 static gboolean     gtk_tree_model_sort_iter_children   (GtkTreeModel          *tree_model,
  94                                                          GtkTreeIter           *iter,
  95                                                          GtkTreeIter           *parent);
  96 static gboolean     gtk_tree_model_sort_iter_has_child  (GtkTreeModel          *tree_model,
  97                                                          GtkTreeIter           *iter);
  98 static gint         gtk_tree_model_sort_iter_n_children (GtkTreeModel          *tree_model,
  99                                                          GtkTreeIter           *iter);
 100 static gboolean     gtk_tree_model_sort_iter_nth_child  (GtkTreeModel          *tree_model,
 101                                                          GtkTreeIter           *iter,
 102                                                          GtkTreeIter           *parent,
 103                                                          gint                   n);
 104 static gboolean     gtk_tree_model_sort_iter_parent     (GtkTreeModel          *tree_model,
 105                                                          GtkTreeIter           *iter,
 106                                                          GtkTreeIter           *child);
 107 static void         gtk_tree_model_sort_ref_node        (GtkTreeModel          *tree_model,
 108                                                          GtkTreeIter           *iter);
 109 static void         gtk_tree_model_sort_unref_node      (GtkTreeModel          *tree_model,
 110                                                          GtkTreeIter           *iter);
 111
 112 /* sortable */
 113 static gboolean gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable        *sortable,
 114                                                         gint                   *sort_column_id,
 115                                                         GtkTreeSortOrder       *order);
 116 static void     gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable        *sortable,
 117                                                         gint                    sort_column_id,
 118                                                         GtkTreeSortOrder        order);
 119 static void     gtk_tree_model_sort_set_sort_func      (GtkTreeSortable        *sortable,
 120                                                         gint                    sort_column_id,
 121                                                         GtkTreeIterCompareFunc  func,
 122                                                         gpointer                data,
 123                                                         GtkDestroyNotify        destroy);
 124
 125 /* Internal functions */
 126 static gint         gtk_tree_model_sort_array_find_insert (GtkTreeModelSort *tree_model_sort,
 127                                                            GArray           *array,
 128                                                            GtkTreeIter      *iter,
 129                                                            gboolean          skip_sort_elt);
 130 static GtkTreePath *gtk_tree_model_sort_convert_path_real (GtkTreeModelSort *tree_model_sort,
 131                                                            GtkTreePath      *child_path,
 132                                                            gboolean          build_children);
 133 static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
 134                                                            SortElt          *place);
 135 static void         gtk_tree_model_sort_free_level        (GArray           *array);
 136
 137
 138
 139 GType
 140 gtk_tree_model_sort_get_type (void)
 141 {
 142   static GType tree_model_sort_type = 0;
 143
 144   if (!tree_model_sort_type)
 145     {
 146       static const GTypeInfo tree_model_sort_info =
 147       {
 148         sizeof (GtkTreeModelSortClass),
 149         NULL,           /* base_init */
 150         NULL,           /* base_finalize */
 151         (GClassInitFunc) gtk_tree_model_sort_class_init,
 152         NULL,           /* class_finalize */
 153         NULL,           /* class_data */
 154         sizeof (GtkTreeModelSort),
 155         0,              /* n_preallocs */
 156         (GInstanceInitFunc) gtk_tree_model_sort_init
 157       };
 158
 159       static const GInterfaceInfo tree_model_info =
 160       {
 161         (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
 162         NULL,
 163         NULL
 164       };
 165
 166       static const GInterfaceInfo sortable_info =
 167       {
 168         (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
 169         NULL,
 170         NULL
 171       };
 172
 173       tree_model_sort_type = g_type_register_static (G_TYPE_OBJECT, "GtkTreeModelSort", &tree_model_sort_info, 0);
 174       g_type_add_interface_static (tree_model_sort_type,
 175                                    GTK_TYPE_TREE_MODEL,
 176                                    &tree_model_info);
 177
 178       g_type_add_interface_static (tree_model_sort_type,
 179                                    GTK_TYPE_TREE_SORTABLE,
 180                                    &sortable_info);
 181     }
 182
 183   return tree_model_sort_type;
 184 }
 185
 186 static void
 187 gtk_tree_model_sort_class_init (GtkTreeModelSortClass *tree_model_sort_class)
 188 {
 189   GObjectClass *object_class;
 190
 191   object_class = (GObjectClass *) tree_model_sort_class;
 192
 193   object_class->finalize = gtk_tree_model_sort_finalize;
 194 }
 195
 196 static void
 197 gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
 198 {
 199   iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
 200   iface->get_column_type = gtk_tree_model_sort_get_column_type;
 201   iface->get_iter = gtk_tree_model_sort_get_iter;
 202   iface->get_path = gtk_tree_model_sort_get_path;
 203   iface->get_value = gtk_tree_model_sort_get_value;
 204   iface->iter_next = gtk_tree_model_sort_iter_next;
 205   iface->iter_children = gtk_tree_model_sort_iter_children;
 206   iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
 207   iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
 208   iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
 209   iface->iter_parent = gtk_tree_model_sort_iter_parent;
 210   iface->ref_node = gtk_tree_model_sort_ref_node;
 211   iface->unref_node = gtk_tree_model_sort_unref_node;
 212 }
 213
 214 static void
 215 gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
 216 {
 217   iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
 218   iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
 219   iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
 220 }
 221
 222 static void
 223 gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
 224 {
 225   tree_model_sort->sort_column_id = -1;
 226   tree_model_sort->stamp = g_random_int ();
 227 }
 228
 229 GtkTreeModel *
 230 gtk_tree_model_sort_new (void)
 231 {
 232   return GTK_TREE_MODEL (g_object_new (gtk_tree_model_sort_get_type (), NULL));
 233 }
 234
 235 GtkTreeModel *
 236 gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
 237 {
 238   GtkTreeModel *retval;
 239
 240   retval = gtk_tree_model_sort_new ();
 241   gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
 242
 243   return retval;
 244 }
 245
 246 /**
 247  * gtk_tree_model_sort_set_model:
 248  * @tree_model_sort: The #GtkTreeModelSort.
 249  * @child_model: A #GtkTreeModel, or NULL.
 250  *
 251  * Sets the model of @tree_model_sort to be @model.  If @model is NULL, then the
 252  * old model is unset.
 253  **/
 254 void
 255 gtk_tree_model_sort_set_model (GtkTreeModelSort *tree_model_sort,
 256                                GtkTreeModel     *child_model)
 257 {
 258   g_return_if_fail (tree_model_sort != NULL);
 259   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort));
 260
 261   if (child_model)
 262     g_object_ref (G_OBJECT (child_model));
 263
 264   if (tree_model_sort->child_model)
 265     {
 266       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 267                                    tree_model_sort->changed_id);
 268       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 269                                    tree_model_sort->inserted_id);
 270       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 271                                    tree_model_sort->has_child_toggled_id);
 272       g_signal_handler_disconnect (G_OBJECT (tree_model_sort->child_model),
 273                                    tree_model_sort->deleted_id);
 274
 275       g_object_unref (G_OBJECT (tree_model_sort->child_model));
 276     }
 277
 278   if (tree_model_sort->root)
 279     {
 280       gtk_tree_model_sort_free_level (tree_model_sort->root);
 281       tree_model_sort->root;
 282     }
 283
 284   if (tree_model_sort->sort_list)
 285     {
 286       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
 287       tree_model_sort->sort_list = NULL;
 288     }
 289
 290   tree_model_sort->child_model = child_model;
 291   if (child_model)
 292     {
 293       GType *types;
 294       gint i, n_columns;
 295
 296       tree_model_sort->changed_id =
 297         g_signal_connectc (child_model,
 298                            "range_changed",
 299                            G_CALLBACK (gtk_tree_model_sort_range_changed),
 300                            tree_model_sort,
 301                            FALSE);
 302       tree_model_sort->inserted_id =
 303         g_signal_connectc (child_model,
 304                            "inserted",
 305                            G_CALLBACK (gtk_tree_model_sort_inserted),
 306                            tree_model_sort,
 307                            FALSE);
 308       tree_model_sort->has_child_toggled_id =
 309         g_signal_connectc (child_model,
 310                            "has_child_toggled",
 311                            G_CALLBACK (gtk_tree_model_sort_has_child_toggled),
 312                            tree_model_sort,
 313                            FALSE);
 314       tree_model_sort->deleted_id =
 315         g_signal_connectc (child_model,
 316                            "deleted",
 317                            G_CALLBACK (gtk_tree_model_sort_deleted),
 318                            tree_model_sort,
 319                            FALSE);
 320
 321       tree_model_sort->flags = gtk_tree_model_get_flags (child_model);
 322       n_columns = gtk_tree_model_get_n_columns (child_model);
 323       types = g_new (GType, n_columns);
 324       for (i = 0; i < n_columns; i++)
 325         types[i] = gtk_tree_model_get_column_type (child_model, i);
 326       tree_model_sort->sort_list = _gtk_tree_data_list_header_new (n_columns, types);
 327       g_free (types);
 328     }
 329 }
 330
 331 /**
 332  * gtk_tree_model_sort_get_model:
 333  * @tree_model: a #GtkTreeModelSort
 334  *
 335  * Returns the model the #GtkTreeModelSort is sorting.
 336  *
 337  * Return value: the "child model" being sorted
 338  **/
 339 GtkTreeModel*
 340 gtk_tree_model_sort_get_model (GtkTreeModelSort  *tree_model)
 341 {
 342   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
 343
 344   return tree_model->child_model;
 345 }
 346
 347 /**
 348  * gtk_tree_model_sort_convert_path:
 349  * @tree_model_sort: The #GtkTreeModelSort.
 350  * @child_path: A #GtkTreePath, relative to the child model.
 351  *
 352  * Converts the @child_path to a new path, relative to the sorted position.  In other
 353  * words, the value found in the @tree_model_sort ->child_model at the @child_path, is
 354  * identical to that found in the @tree_model_sort and the return value.
 355  *
 356  * Return value: A new path, or NULL if @child_path does not exist in @tree_model_sort
 357  * ->child_model.
 358  **/
 359 GtkTreePath *
 360 gtk_tree_model_sort_convert_path (GtkTreeModelSort *tree_model_sort,
 361                                   GtkTreePath      *child_path)
 362 {
 363   g_return_val_if_fail (tree_model_sort != NULL, NULL);
 364   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
 365   g_return_val_if_fail (child_path != NULL, NULL);
 366
 367   return gtk_tree_model_sort_convert_path_real (tree_model_sort, child_path, TRUE);
 368 }
 369
 370 static void
 371 gtk_tree_model_sort_finalize (GObject *object)
 372 {
 373   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
 374
 375   if (tree_model_sort->root)
 376     gtk_tree_model_sort_free_level (tree_model_sort->root);
 377
 378   if (tree_model_sort->child_model)
 379     {
 380       g_object_unref (G_OBJECT (tree_model_sort->child_model));
 381       tree_model_sort->child_model = NULL;
 382     }
 383   if (tree_model_sort->sort_list)
 384     {
 385       _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
 386       tree_model_sort->sort_list = NULL;
 387     }
 388 }
 389
 390 static void
 391 gtk_tree_model_sort_range_changed (GtkTreeModel *s_model,
 392                                    GtkTreePath  *s_start_path,
 393                                    GtkTreeIter  *s_start_iter,
 394                                    GtkTreePath  *s_end_path,
 395                                    GtkTreeIter  *s_end_iter,
 396                                    gpointer      data)
 397 {
 398   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 399   GtkTreePath *path;
 400   GtkTreeIter iter;
 401   SortElt *elt;
 402   GArray *array;
 403   gboolean free_s_path = FALSE;
 404   gint index;
 405
 406   g_return_if_fail (s_start_path != NULL || s_start_iter != NULL);
 407
 408   if (s_start_path == NULL)
 409     {
 410       free_s_path = TRUE;
 411       s_start_path = gtk_tree_model_get_path (s_model, s_start_iter);
 412     }
 413
 414   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_start_path, FALSE);
 415   if (path == NULL)
 416     {
 417       if (free_s_path)
 418         gtk_tree_path_free (s_start_path);
 419       return;
 420     }
 421
 422   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 423   elt = (SortElt *) iter.user_data;
 424   array = get_array (elt, tree_model_sort);
 425
 426   /* FIXME: as an optimization for when the column other then the one we're
 427    * sorting is changed, we can check the prev and next element to see if
 428    * they're different.
 429    */
 430
 431   /* Now we need to resort things. */
 432   index = gtk_tree_model_sort_array_find_insert (tree_model_sort,
 433                                                  array,
 434                                                  (GtkTreeIter *) elt,
 435                                                  TRUE);
 436
 437   gtk_tree_model_range_changed (GTK_TREE_MODEL (data), path, &iter, path, &iter);
 438
 439   gtk_tree_path_free (path);
 440   if (free_s_path)
 441     gtk_tree_path_free (s_start_path);
 442 }
 443
 444 /* FALSE if the value was inserted, TRUE otherwise */
 445 static gboolean
 446 gtk_tree_model_sort_insert_value (GtkTreeModelSort *sort,
 447                                   GtkTreePath      *s_path,
 448                                   GtkTreeIter      *s_iter)
 449 {
 450   GtkTreePath *tmp_path;
 451   GArray *array;
 452   gint index;
 453   GtkTreeIter iter;
 454   SortElt elt;
 455   gint offset;
 456   gint j;
 457   SortElt *tmp_elt;
 458   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
 459
 460   elt.iter = *s_iter;
 461   elt.ref = 0;
 462   elt.children = NULL;
 463   elt.offset = offset;
 464
 465   tmp_path = gtk_tree_path_copy (s_path);
 466
 467   if (gtk_tree_path_up (tmp_path))
 468     {
 469       GtkTreePath *parent_path;
 470
 471       parent_path = gtk_tree_model_sort_convert_path_real (sort, tmp_path, FALSE);
 472       if (parent_path == NULL)
 473         {
 474           gtk_tree_path_free (tmp_path);
 475           return FALSE;
 476         }
 477       gtk_tree_model_get_iter (GTK_TREE_MODEL (sort), &iter, parent_path);
 478       elt.parent = ((SortElt *) iter.user_data);
 479       array = ((SortElt *) iter.user_data)->children;
 480       gtk_tree_path_free (parent_path);
 481       if (array == NULL)
 482         {
 483           gtk_tree_path_free (tmp_path);
 484           return FALSE;
 485         }
 486     }
 487   else
 488     {
 489       if (sort->root == NULL)
 490         sort->root = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), 1);
 491       array = sort->root;
 492       elt.parent = NULL;
 493     }
 494   gtk_tree_path_free (tmp_path);
 495
 496   index = gtk_tree_model_sort_array_find_insert (sort, array, (GtkTreeIter *) &elt, FALSE);
 497
 498   g_array_insert_vals (array, index, &elt, 1);
 499
 500   /* update all the larger offsets */
 501   tmp_elt = (SortElt *) array->data;
 502   for (j = 0; j < array->len; j++, tmp_elt++)
 503         {
 504           if ((tmp_elt->offset >= offset) &&
 505               j != index)
 506             tmp_elt->offset ++;
 507         }
 508
 509   return TRUE;
 510 }
 511
 512 static void
 513 gtk_tree_model_sort_inserted (GtkTreeModel *s_model,
 514                               GtkTreePath  *s_path,
 515                               GtkTreeIter  *s_iter,
 516                               gpointer      data)
 517 {
 518   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 519   GtkTreePath *path;
 520   GtkTreeIter iter;
 521
 522   g_return_if_fail (s_path != NULL || s_iter != NULL);
 523
 524   if (s_path == NULL)
 525     s_path = gtk_tree_model_get_path (s_model, s_iter);
 526
 527   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 528     {
 529       gtk_tree_model_sort_free_level ((GArray *) tree_model_sort->root);
 530       tree_model_sort->root = NULL;
 531     }
 532   else
 533     {
 534       GtkTreeIter real_s_iter;
 535
 536       if (s_iter == NULL)
 537         gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
 538       else
 539         real_s_iter = (* s_iter);
 540
 541       if (!gtk_tree_model_sort_insert_value (tree_model_sort, s_path, &real_s_iter))
 542         return;
 543     }
 544
 545   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_path, FALSE);
 546   if (path == NULL)
 547     return;
 548
 549   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 550   g_signal_emit_by_name (G_OBJECT (data), "inserted", path, &iter);
 551   gtk_tree_path_free (path);
 552 }
 553
 554 static void
 555 gtk_tree_model_sort_has_child_toggled (GtkTreeModel *s_model,
 556                                        GtkTreePath  *s_path,
 557                                        GtkTreeIter  *s_iter,
 558                                        gpointer      data)
 559 {
 560   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 561   GtkTreePath *path;
 562   GtkTreeIter iter;
 563   gboolean free_s_path = FALSE;
 564
 565   g_return_if_fail (s_path != NULL || s_iter != NULL);
 566
 567   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 568     {
 569       gtk_tree_model_sort_free_level ((GArray *)tree_model_sort->root);
 570       tree_model_sort->root = NULL;
 571     }
 572
 573   if (s_path == NULL)
 574     {
 575       s_path = gtk_tree_model_get_path (s_model, s_iter);
 576       free_s_path = TRUE;
 577     }
 578
 579   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_path, FALSE);
 580   if (path == NULL)
 581     return;
 582   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 583   g_signal_emit_by_name (G_OBJECT (data),
 584                            "has_child_toggled",
 585                            path, &iter);
 586   gtk_tree_path_free (path);
 587   if (free_s_path)
 588     gtk_tree_path_free (s_path);
 589 }
 590
 591 static void
 592 gtk_tree_model_sort_deleted (GtkTreeModel *s_model,
 593                              GtkTreePath  *s_path,
 594                              gpointer      data)
 595 {
 596   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 597   GtkTreePath *path;
 598
 599   g_return_if_fail (s_path != NULL);
 600   path = gtk_tree_model_sort_convert_path (tree_model_sort, s_path);
 601   g_return_if_fail (path != NULL);
 602
 603   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 604     {
 605       gtk_tree_model_sort_free_level ((GArray *)tree_model_sort->root);
 606       tree_model_sort->root = NULL;
 607     }
 608   else
 609     {
 610       GArray *array;
 611       GtkTreeIter iter;
 612       SortElt *elt;
 613       gint offset;
 614       gint i;
 615
 616       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort), &iter, path);
 617       elt = (SortElt *) iter.user_data;
 618       offset = elt->offset;
 619       array = get_array (elt, tree_model_sort);
 620       if (array->len == 1)
 621         {
 622           if (((SortElt *)array->data)->parent == NULL)
 623             tree_model_sort->root = NULL;
 624           else
 625             (((SortElt *)array->data)->parent)->children = NULL;
 626           gtk_tree_model_sort_free_level (array);
 627         }
 628       else
 629         {
 630           g_array_remove_index (array, elt - ((SortElt *) array->data));
 631
 632           for (i = 0; i < array->len; i++)
 633             {
 634               elt = & (g_array_index (array, SortElt, i));
 635               if (elt->offset > offset)
 636                 elt->offset--;
 637             }
 638         }
 639     }
 640
 641   tree_model_sort->stamp++;
 642   g_signal_emit_by_name (G_OBJECT (data), "deleted", path);
 643   gtk_tree_path_free (path);
 644 }
 645
 646 static gint
 647 gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
 648 {
 649   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
 650
 651   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 652
 653   if (tree_model_sort->child_model == 0)
 654     return 0;
 655
 656   return gtk_tree_model_get_n_columns (GTK_TREE_MODEL_SORT (tree_model)->child_model);
 657 }
 658
 659 static GType
 660 gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
 661                                      gint          index)
 662 {
 663   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
 664   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
 665
 666   return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
 667 }
 668
 669 static gboolean
 670 gtk_tree_model_sort_get_iter_helper (GtkTreeModelSort *tree_model_sort,
 671                                      GArray       *array,
 672                                      GtkTreeIter  *iter,
 673                                      gint          depth,
 674                                      GtkTreePath  *path)
 675 {
 676   SortElt *elt;
 677
 678   if (array == NULL)
 679     return FALSE;
 680
 681   if (gtk_tree_path_get_indices (path)[depth] > array->len)
 682     return FALSE;
 683
 684   elt = & (g_array_index (array, SortElt, gtk_tree_path_get_indices (path)[depth]));
 685
 686   if (depth == gtk_tree_path_get_depth (path) - 1)
 687     {
 688       iter->stamp = tree_model_sort->stamp;
 689       iter->user_data = elt;
 690       return TRUE;
 691     }
 692
 693   if (elt->children != NULL)
 694     return gtk_tree_model_sort_get_iter_helper (tree_model_sort,
 695                                                 elt->children,
 696                                                 iter,
 697                                                 depth + 1,
 698                                                 path);
 699
 700   if (gtk_tree_model_iter_has_child (tree_model_sort->child_model,
 701                                      &(elt->iter)))
 702
 703     gtk_tree_model_sort_build_level (tree_model_sort, elt);
 704
 705   return gtk_tree_model_sort_get_iter_helper (tree_model_sort,
 706                                               elt->children,
 707                                               iter,
 708                                               depth + 1,
 709                                               path);
 710 }
 711
 712 static gboolean
 713 gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
 714                               GtkTreeIter  *iter,
 715                               GtkTreePath  *path)
 716 {
 717   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 718   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 719
 720   if (GTK_TREE_MODEL_SORT (tree_model)->root == NULL)
 721     gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), NULL);
 722
 723   return gtk_tree_model_sort_get_iter_helper (GTK_TREE_MODEL_SORT (tree_model),
 724                                               GTK_TREE_MODEL_SORT (tree_model)->root,
 725                                               iter, 0, path);
 726 }
 727
 728 static GtkTreePath *
 729 gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
 730                               GtkTreeIter  *iter)
 731 {
 732   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
 733   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
 734
 735   return gtk_tree_model_get_path (GTK_TREE_MODEL_SORT (tree_model)->child_model, iter);
 736 }
 737
 738 static void
 739 gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
 740                                GtkTreeIter  *iter,
 741                                gint          column,
 742                                GValue        *value)
 743 {
 744   SortElt *elt;
 745
 746   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
 747   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
 748   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
 749
 750   elt = iter->user_data;
 751
 752   gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt, column, value);
 753 }
 754
 755 static gboolean
 756 gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
 757                                GtkTreeIter  *iter)
 758 {
 759   GArray *array;
 760   SortElt *elt;
 761
 762   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 763   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 764   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
 765
 766   elt = iter->user_data;
 767   array = get_array (elt, tree_model);
 768
 769   if (elt - ((SortElt*) array->data) >=  array->len - 1)
 770     {
 771       iter->stamp = 0;
 772       return FALSE;
 773     }
 774   iter->user_data = elt + 1;
 775   return TRUE;
 776 }
 777
 778 static gboolean
 779 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
 780                                    GtkTreeIter  *iter,
 781                                    GtkTreeIter  *parent)
 782 {
 783   SortElt *elt;
 784
 785   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 786   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 787
 788   if (parent)
 789     g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
 790
 791   if (parent)
 792     elt = parent->user_data;
 793   else
 794     elt = (SortElt *) ((GArray *)GTK_TREE_MODEL_SORT (tree_model)->root)->data;
 795
 796   if (elt == NULL)
 797     return FALSE;
 798
 799   if (elt->children == NULL &&
 800       gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt))
 801     gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), elt);
 802
 803   if (elt->children == NULL)
 804     return FALSE;
 805
 806   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 807   iter->user_data = elt->children->data;
 808
 809   return TRUE;
 810 }
 811
 812 static gboolean
 813 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
 814                                     GtkTreeIter  *iter)
 815 {
 816   SortElt *elt;
 817
 818   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 819   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 820   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
 821
 822   elt = iter->user_data;
 823   if (elt->children)
 824     return TRUE;
 825
 826   return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *) elt);
 827 }
 828
 829 static gint
 830 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
 831                                      GtkTreeIter  *iter)
 832 {
 833   SortElt *elt;
 834
 835   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 836   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
 837   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
 838
 839   elt = iter->user_data;
 840   if (elt->children)
 841     return elt->children->len;
 842
 843   return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *) elt);
 844 }
 845
 846
 847 static gboolean
 848 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
 849                                     GtkTreeIter  *iter,
 850                                     GtkTreeIter  *parent,
 851                                     gint          n)
 852 {
 853   SortElt *elt;
 854
 855   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 856   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 857   if (parent)
 858     g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
 859
 860   elt = iter->user_data;
 861
 862
 863   if (elt->children == NULL)
 864     {
 865       if (gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt))
 866         gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), elt);
 867       else
 868         return FALSE;
 869     }
 870
 871   if (elt->children == NULL)
 872     return FALSE;
 873
 874   if (n >= elt->children->len)
 875     return FALSE;
 876
 877   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 878   iter->user_data = &g_array_index (elt->children, SortElt, n);
 879
 880   return TRUE;
 881 }
 882
 883 static gboolean
 884 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
 885                                  GtkTreeIter  *iter,
 886                                  GtkTreeIter  *child)
 887 {
 888   SortElt *elt;
 889
 890   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 891   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 892   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);
 893
 894   elt = iter->user_data;
 895   if (elt->parent)
 896     {
 897       iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 898       iter->user_data = elt->parent;
 899
 900       return TRUE;
 901     }
 902   return FALSE;
 903 }
 904
 905 static void
 906 gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
 907                               GtkTreeIter  *iter)
 908 {
 909 }
 910
 911 static void
 912 gtk_tree_model_sort_unref_node (GtkTreeModel *tree_model,
 913                                 GtkTreeIter  *iter)
 914 {
 915
 916
 917 }
 918
 919 static gboolean
 920 gtk_tree_model_sort_get_sort_column_id (GtkTreeSortable  *sortable,
 921                                         gint             *sort_column_id,
 922                                         GtkTreeSortOrder *order)
 923 {
 924   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
 925
 926   g_return_val_if_fail (sortable != NULL, FALSE);
 927   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (sortable), FALSE);
 928
 929   if (tree_model_sort->sort_column_id == -1)
 930     return FALSE;
 931
 932   if (sort_column_id)
 933     *sort_column_id = tree_model_sort->sort_column_id;
 934   if (order)
 935     *order = tree_model_sort->order;
 936
 937   return TRUE;
 938 }
 939
 940 static void
 941 gtk_tree_model_sort_set_sort_column_id (GtkTreeSortable  *sortable,
 942                                          gint              sort_column_id,
 943                                          GtkTreeSortOrder  order)
 944 {
 945   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
 946   GList *list;
 947
 948   g_return_if_fail (sortable != NULL);
 949   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
 950
 951   for (list = tree_model_sort->sort_list; list; list = list->next)
 952     {
 953       GtkTreeDataSortHeader *header = (GtkTreeDataSortHeader*) list->data;
 954       if (header->sort_column_id == sort_column_id)
 955         break;
 956     }
 957   g_return_if_fail (list != NULL);
 958
 959   if ((tree_model_sort->sort_column_id == sort_column_id) &&
 960       (tree_model_sort->order == order))
 961     return;
 962
 963   tree_model_sort->sort_column_id = sort_column_id;
 964   tree_model_sort->order = order;
 965
 966   /*  if (tree_model_sort->sort_column_id >= 0)
 967       gtk_list_store_sort (tree_model_sort);*/
 968
 969   gtk_tree_sortable_sort_column_changed (sortable);
 970
 971 }
 972
 973 static void
 974 gtk_tree_model_sort_set_sort_func (GtkTreeSortable        *sortable,
 975                                    gint                    sort_column_id,
 976                                    GtkTreeIterCompareFunc  func,
 977                                    gpointer                data,
 978                                    GtkDestroyNotify        destroy)
 979 {
 980   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) sortable;
 981   GtkTreeDataSortHeader *header = NULL;
 982   GList *list;
 983
 984   g_return_if_fail (sortable != NULL);
 985   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (sortable));
 986   g_return_if_fail (func != NULL);
 987
 988   for (list = tree_model_sort->sort_list; list; list = list->next)
 989     {
 990       header = (GtkTreeDataSortHeader*) list->data;
 991       if (header->sort_column_id == sort_column_id)
 992         break;
 993     }
 994
 995   if (header == NULL)
 996     {
 997       header = g_new0 (GtkTreeDataSortHeader, 1);
 998       header->sort_column_id = sort_column_id;
 999       tree_model_sort->sort_list = g_list_append (tree_model_sort->sort_list, header);
1000     }
1001
1002   if (header->destroy)
1003     (* header->destroy) (header->data);
1004
1005   header->func = func;
1006   header->data = data;
1007   header->destroy = destroy;
1008 }
1009
1010 /* Internal functions */
1011
1012 static gint
1013 gtk_tree_model_sort_array_find_insert (GtkTreeModelSort *tree_model_sort,
1014                                        GArray           *array,
1015                                        GtkTreeIter      *iter,
1016                                        gboolean          skip_sort_elt)
1017 {
1018   gint middle;
1019   gint cmp;
1020   GValueCompareFunc func;
1021   GValue value = {0, };
1022   GValue tmp_value = {0, };
1023   SortElt *tmp_elt;
1024
1025   func = NULL; //(GValueCompareFunc) gtk_tree_model_sort_get_func (tree_model_sort);
1026
1027   g_return_val_if_fail (func != NULL, 0);
1028
1029   gtk_tree_model_get_value (tree_model_sort->child_model, iter, tree_model_sort->sort_column_id, &value);
1030
1031   for (middle = 0; middle < array->len; middle++)
1032     {
1033       tmp_elt = &(g_array_index (array, SortElt, middle));
1034       if (!skip_sort_elt &&
1035           (SortElt *) iter == tmp_elt)
1036           continue;
1037       gtk_tree_model_get_value (tree_model_sort->child_model,
1038                                 (GtkTreeIter *) tmp_elt,
1039                                 tree_model_sort->sort_column_id,
1040                                 &tmp_value);
1041
1042       cmp = ((func) (&value, &tmp_value));
1043       g_value_unset (&tmp_value);
1044
1045       if (cmp >= 0)
1046         break;
1047     }
1048   return middle;
1049 }
1050
1051
1052 static GtkTreePath *
1053 gtk_tree_model_sort_convert_path_real (GtkTreeModelSort *tree_model_sort,
1054                                        GtkTreePath      *child_path,
1055                                        gboolean          build_children)
1056 {
1057   GtkTreePath *retval;
1058   GArray *array;
1059   gint *indices;
1060   gint i = 0;
1061
1062   if (tree_model_sort->root == NULL)
1063     {
1064       if (build_children)
1065         gtk_tree_model_sort_build_level (tree_model_sort, NULL);
1066       else
1067         return FALSE;
1068     }
1069
1070   retval = gtk_tree_path_new ();
1071   array = (GArray *) tree_model_sort->root;
1072   indices = gtk_tree_path_get_indices (child_path);
1073
1074   do
1075     {
1076       SortElt *elt;
1077       gboolean found = FALSE;
1078       gint j;
1079
1080       if ((array->len < indices[i]) || (array == NULL))
1081         {
1082           gtk_tree_path_free (retval);
1083           return NULL;
1084         }
1085
1086       elt = (SortElt *) array->data;
1087       for (j = 0; j < array->len; j++, elt++)
1088         {
1089           if (elt->offset == indices[i])
1090             {
1091               found = TRUE;
1092               break;
1093             }
1094         }
1095       if (! found)
1096         {
1097           gtk_tree_path_free (retval);
1098           return NULL;
1099         }
1100
1101       gtk_tree_path_prepend_index (retval, j);
1102
1103       i++;
1104
1105       if (i == gtk_tree_path_get_depth (child_path))
1106         break;
1107
1108       if (elt->children == NULL)
1109         {
1110           if (build_children)
1111             {
1112               gtk_tree_path_prepend_index (retval, j);
1113               gtk_tree_model_sort_build_level (tree_model_sort, elt);
1114             }
1115           else
1116             {
1117               gtk_tree_path_free (retval);
1118               return NULL;
1119             }
1120         }
1121     }
1122   while (TRUE);
1123
1124   return retval;
1125 }
1126
1127 static void
1128 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
1129                                  SortElt          *place)
1130 {
1131   gint n, i = 0;
1132   GArray *children;
1133   GtkTreeIter *parent_iter = NULL;
1134   GtkTreeIter iter;
1135   SortElt elt;
1136   SortData sort_data;
1137
1138   if (place)
1139     parent_iter = & (place->iter);
1140
1141
1142   n = gtk_tree_model_iter_n_children (tree_model_sort->child_model, parent_iter);
1143
1144   if (n == 0)
1145     return;
1146
1147   children = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), n);
1148
1149   if (place)
1150     place->children = children;
1151   else
1152     tree_model_sort->root = children;
1153
1154   gtk_tree_model_iter_children (tree_model_sort->child_model,
1155                                 &iter,
1156                                 parent_iter);
1157
1158   do
1159     {
1160       elt.iter = iter;
1161       elt.parent = place;
1162       elt.children = NULL;
1163       elt.ref = 0;
1164       elt.offset = i;
1165
1166       g_array_append_vals (children, &elt, 1);
1167       i++;
1168     }
1169   while (gtk_tree_model_iter_next (tree_model_sort->child_model, &iter));
1170 }
1171
1172 static void
1173 gtk_tree_model_sort_free_level (GArray *array)
1174 {
1175   gint i;
1176
1177   if (array == NULL)
1178     return;
1179
1180   for (i = 0; i < array->len; i++)
1181     {
1182       SortElt *elt;
1183
1184       elt = &g_array_index (array, SortElt, i);
1185       if (elt->children)
1186         gtk_tree_model_sort_free_level (array);
1187     }
1188
1189   g_array_free (array, TRUE);
1190 }
1191
1192 /* DEAD CODE */
1193
1194 #if 0
1195   /* FIXME: we can, as we are an array, do binary search to find the correct
1196    * location to insert the element.  However, I'd rather get it working.  The
1197    * below is quite wrong, but a step in the right direction.
1198    */
1199   low = 0;
1200   high = array->len;
1201   middle = (low + high)/2;
1202
1203   /* Insert the value into the array */
1204   while (low != high)
1205     {
1206       gint cmp;
1207       tmp_elt = &(g_array_index (array, SortElt, middle));
1208       gtk_tree_model_get_value (sort->child_model,
1209                                 (GtkTreeIter *) tmp_elt,
1210                                 sort->sort_column_id,
1211                                 &tmp_value);
1212
1213       cmp = ((func) (&tmp_value, &s_value));
1214       g_value_unset (&tmp_value);
1215
1216       if (cmp < 0)
1217         high = middle;
1218       else if (cmp > 0)
1219         low = middle;
1220       else if (cmp == 0)
1221         break;
1222       middle = (low + high)/2;
1223     }
1224 #endif