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