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_get_model:
 326  * @tree_model: a #GtkTreeModelSort
 327  *
 328  * Returns the model the #GtkTreeModelSort is sorting.
 329  *
 330  * Return value: the "child model" being sorted
 331  **/
 332 GtkTreeModel*
 333 gtk_tree_model_sort_get_model (GtkTreeModelSort  *tree_model)
 334 {
 335   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
 336
 337   return tree_model->child_model;
 338 }
 339
 340 /**
 341  * gtk_tree_model_sort_convert_path:
 342  * @tree_model_sort: The #GtkTreeModelSort.
 343  * @child_path: A #GtkTreePath, relative to the child model.
 344  *
 345  * Converts the @child_path to a new path, relative to the sorted position.  In other
 346  * words, the value found in the @tree_model_sort ->child_model at the @child_path, is
 347  * identical to that found in the @tree_model_sort and the return value.
 348  *
 349  * Return value: A new path, or NULL if @child_path does not exist in @tree_model_sort
 350  * ->child_model.
 351  **/
 352 GtkTreePath *
 353 gtk_tree_model_sort_convert_path (GtkTreeModelSort *tree_model_sort,
 354                                   GtkTreePath      *child_path)
 355 {
 356   g_return_val_if_fail (tree_model_sort != NULL, NULL);
 357   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model_sort), NULL);
 358   g_return_val_if_fail (child_path != NULL, NULL);
 359
 360   return gtk_tree_model_sort_convert_path_real (tree_model_sort, child_path, TRUE);
 361 }
 362
 363 static void
 364 gtk_tree_model_sort_finalize (GObject *object)
 365 {
 366   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
 367
 368   if (tree_model_sort->root)
 369     gtk_tree_model_sort_free_level (tree_model_sort->root);
 370
 371   if (tree_model_sort->child_model)
 372     {
 373       g_object_unref (G_OBJECT (tree_model_sort->child_model));
 374       tree_model_sort->child_model = NULL;
 375     }
 376 }
 377
 378 static void
 379 gtk_tree_model_sort_changed (GtkTreeModel *s_model,
 380                              GtkTreePath  *s_path,
 381                              GtkTreeIter  *s_iter,
 382                              gpointer      data)
 383 {
 384   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 385   GtkTreePath *path;
 386   GtkTreeIter iter;
 387   SortElt *elt;
 388   GArray *array;
 389   gboolean free_s_path = FALSE;
 390   gint index;
 391
 392   g_return_if_fail (s_path != NULL || s_iter != NULL);
 393
 394   if (s_path == NULL)
 395     {
 396       free_s_path = TRUE;
 397       s_path = gtk_tree_model_get_path (s_model, s_iter);
 398     }
 399
 400   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_path, FALSE);
 401   if (path == NULL)
 402     {
 403       if (free_s_path)
 404         gtk_tree_path_free (s_path);
 405       return;
 406     }
 407
 408   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 409   elt = (SortElt *) iter.user_data;
 410   array = get_array (elt, tree_model_sort);
 411
 412   /* FIXME: as an optimization for when the column other then the one we're
 413    * sorting is changed, we can check the prev and next element to see if
 414    * they're different.
 415    */
 416
 417   /* Now we need to resort things. */
 418   index = gtk_tree_model_sort_array_find_insert (tree_model_sort,
 419                                                  array,
 420                                                  (GtkTreeIter *) elt,
 421                                                  TRUE);
 422   g_print ("index is %d\n", index);
 423   gtk_signal_emit_by_name (GTK_OBJECT (data), "changed", path, &iter);
 424
 425   gtk_tree_path_free (path);
 426   if (free_s_path)
 427     gtk_tree_path_free (s_path);
 428 }
 429
 430 /* FALSE if the value was inserted, TRUE otherwise */
 431 static gboolean
 432 gtk_tree_model_sort_insert_value (GtkTreeModelSort *sort,
 433                                   GtkTreePath      *s_path,
 434                                   GtkTreeIter      *s_iter)
 435 {
 436   GtkTreePath *tmp_path;
 437   GArray *array;
 438   gint index;
 439   GtkTreeIter iter;
 440   SortElt elt;
 441   gint offset;
 442   gint j;
 443   SortElt *tmp_elt;
 444   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
 445
 446   elt.iter = *s_iter;
 447   elt.ref = 0;
 448   elt.children = NULL;
 449   elt.offset = offset;
 450
 451   tmp_path = gtk_tree_path_copy (s_path);
 452
 453   if (gtk_tree_path_up (tmp_path))
 454     {
 455       GtkTreePath *parent_path;
 456
 457       parent_path = gtk_tree_model_sort_convert_path_real (sort, tmp_path, FALSE);
 458       if (parent_path == NULL)
 459         {
 460           gtk_tree_path_free (tmp_path);
 461           return FALSE;
 462         }
 463       gtk_tree_model_get_iter (GTK_TREE_MODEL (sort), &iter, parent_path);
 464       elt.parent = ((SortElt *) iter.user_data);
 465       array = ((SortElt *) iter.user_data)->children;
 466       gtk_tree_path_free (parent_path);
 467       if (array == NULL)
 468         {
 469           gtk_tree_path_free (tmp_path);
 470           return FALSE;
 471         }
 472     }
 473   else
 474     {
 475       if (sort->root == NULL)
 476         sort->root = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), 1);
 477       array = sort->root;
 478       elt.parent = NULL;
 479     }
 480   gtk_tree_path_free (tmp_path);
 481
 482   index = gtk_tree_model_sort_array_find_insert (sort, array, (GtkTreeIter *) &elt, FALSE);
 483
 484   g_array_insert_vals (array, index, &elt, 1);
 485
 486   /* update all the larger offsets */
 487   tmp_elt = (SortElt *) array->data;
 488   for (j = 0; j < array->len; j++, tmp_elt++)
 489         {
 490           if ((tmp_elt->offset >= offset) &&
 491               j != index)
 492             tmp_elt->offset ++;
 493         }
 494
 495   return TRUE;
 496 }
 497
 498 static void
 499 gtk_tree_model_sort_inserted (GtkTreeModel *s_model,
 500                               GtkTreePath  *s_path,
 501                               GtkTreeIter  *s_iter,
 502                               gpointer      data)
 503 {
 504   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 505   GtkTreePath *path;
 506   GtkTreeIter iter;
 507
 508   g_return_if_fail (s_path != NULL || s_iter != NULL);
 509
 510   if (s_path == NULL)
 511     s_path = gtk_tree_model_get_path (s_model, s_iter);
 512
 513   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 514     {
 515       gtk_tree_model_sort_free_level ((GArray *) tree_model_sort->root);
 516       tree_model_sort->root = NULL;
 517     }
 518   else
 519     {
 520       GtkTreeIter real_s_iter;
 521
 522       if (s_iter == NULL)
 523         gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
 524       else
 525         real_s_iter = (* s_iter);
 526
 527       if (!gtk_tree_model_sort_insert_value (tree_model_sort, s_path, &real_s_iter))
 528         return;
 529     }
 530
 531   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_path, FALSE);
 532   if (path == NULL)
 533     return;
 534
 535   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 536   gtk_signal_emit_by_name (GTK_OBJECT (data), "inserted", path, &iter);
 537   gtk_tree_path_free (path);
 538 }
 539
 540 static void
 541 gtk_tree_model_sort_child_toggled (GtkTreeModel *s_model,
 542                                    GtkTreePath  *s_path,
 543                                    GtkTreeIter  *s_iter,
 544                                    gpointer      data)
 545 {
 546   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 547   GtkTreePath *path;
 548   GtkTreeIter iter;
 549   gboolean free_s_path = FALSE;
 550
 551   g_return_if_fail (s_path != NULL || s_iter != NULL);
 552
 553   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 554     {
 555       gtk_tree_model_sort_free_level ((GArray *)tree_model_sort->root);
 556       tree_model_sort->root = NULL;
 557     }
 558
 559   if (s_path == NULL)
 560     {
 561       s_path = gtk_tree_model_get_path (s_model, s_iter);
 562       free_s_path = TRUE;
 563     }
 564
 565   path = gtk_tree_model_sort_convert_path_real (tree_model_sort, s_path, FALSE);
 566   if (path == NULL)
 567     return;
 568   gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
 569   gtk_signal_emit_by_name (GTK_OBJECT (data),
 570                            "child_toggled",
 571                            path, &iter);
 572   gtk_tree_path_free (path);
 573   if (free_s_path)
 574     gtk_tree_path_free (s_path);
 575 }
 576
 577 static void
 578 gtk_tree_model_sort_deleted (GtkTreeModel *s_model,
 579                              GtkTreePath  *s_path,
 580                              gpointer      data)
 581 {
 582   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
 583   GtkTreePath *path;
 584
 585   g_return_if_fail (s_path != NULL);
 586   path = gtk_tree_model_sort_convert_path (tree_model_sort, s_path);
 587   g_return_if_fail (path != NULL);
 588
 589   if (!(tree_model_sort->flags & GTK_TREE_MODEL_ITERS_PERSIST))
 590     {
 591       gtk_tree_model_sort_free_level ((GArray *)tree_model_sort->root);
 592       tree_model_sort->root = NULL;
 593     }
 594   else
 595     {
 596       GArray *array;
 597       GtkTreeIter iter;
 598       SortElt *elt;
 599       gint offset;
 600       gint i;
 601
 602       gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort), &iter, path);
 603       elt = (SortElt *) iter.user_data;
 604       offset = elt->offset;
 605       array = get_array (elt, tree_model_sort);
 606       if (array->len == 1)
 607         {
 608           if (((SortElt *)array->data)->parent == NULL)
 609             tree_model_sort->root = NULL;
 610           else
 611             (((SortElt *)array->data)->parent)->children = NULL;
 612           gtk_tree_model_sort_free_level (array);
 613         }
 614       else
 615         {
 616           g_array_remove_index (array, elt - ((SortElt *) array->data));
 617
 618           for (i = 0; i < array->len; i++)
 619             {
 620               elt = & (g_array_index (array, SortElt, i));
 621               if (elt->offset > offset)
 622                 elt->offset--;
 623             }
 624         }
 625     }
 626
 627   tree_model_sort->stamp++;
 628   gtk_signal_emit_by_name (GTK_OBJECT (data), "deleted", path);
 629   gtk_tree_path_free (path);
 630 }
 631
 632 static gint
 633 gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
 634 {
 635   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 636   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
 637
 638   return gtk_tree_model_get_n_columns (GTK_TREE_MODEL_SORT (tree_model)->child_model);
 639 }
 640
 641 static GType
 642 gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
 643                                      gint          index)
 644 {
 645   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
 646   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
 647
 648   return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
 649 }
 650
 651 static gboolean
 652 gtk_tree_model_sort_get_iter_helper (GtkTreeModelSort *tree_model_sort,
 653                                      GArray       *array,
 654                                      GtkTreeIter  *iter,
 655                                      gint          depth,
 656                                      GtkTreePath  *path)
 657 {
 658   SortElt *elt;
 659
 660   if (array == NULL)
 661     return FALSE;
 662
 663   if (gtk_tree_path_get_indices (path)[depth] > array->len)
 664     return FALSE;
 665
 666   elt = & (g_array_index (array, SortElt, gtk_tree_path_get_indices (path)[depth]));
 667
 668   if (depth == gtk_tree_path_get_depth (path) - 1)
 669     {
 670       iter->stamp = tree_model_sort->stamp;
 671       iter->user_data = elt;
 672       return TRUE;
 673     }
 674
 675   if (elt->children != NULL)
 676     return gtk_tree_model_sort_get_iter_helper (tree_model_sort,
 677                                                 elt->children,
 678                                                 iter,
 679                                                 depth + 1,
 680                                                 path);
 681
 682   if (gtk_tree_model_iter_has_child (tree_model_sort->child_model,
 683                                      &(elt->iter)))
 684
 685     gtk_tree_model_sort_build_level (tree_model_sort, elt);
 686
 687   return gtk_tree_model_sort_get_iter_helper (tree_model_sort,
 688                                               elt->children,
 689                                               iter,
 690                                               depth + 1,
 691                                               path);
 692 }
 693
 694 static gboolean
 695 gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
 696                               GtkTreeIter  *iter,
 697                               GtkTreePath  *path)
 698 {
 699   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 700   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 701
 702   if (GTK_TREE_MODEL_SORT (tree_model)->root == NULL)
 703     gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), NULL);
 704
 705   return gtk_tree_model_sort_get_iter_helper (GTK_TREE_MODEL_SORT (tree_model),
 706                                               GTK_TREE_MODEL_SORT (tree_model)->root,
 707                                               iter, 0, path);
 708 }
 709
 710 static GtkTreePath *
 711 gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
 712                               GtkTreeIter  *iter)
 713 {
 714   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
 715   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
 716
 717   return gtk_tree_model_get_path (GTK_TREE_MODEL_SORT (tree_model)->child_model, iter);
 718 }
 719
 720 static void
 721 gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
 722                                GtkTreeIter  *iter,
 723                                gint          column,
 724                                GValue        *value)
 725 {
 726   SortElt *elt;
 727
 728   g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
 729   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
 730   g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);
 731
 732   elt = iter->user_data;
 733
 734   gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt, column, value);
 735 }
 736
 737 static gboolean
 738 gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
 739                                GtkTreeIter  *iter)
 740 {
 741   GArray *array;
 742   SortElt *elt;
 743
 744   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 745   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 746   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
 747
 748   elt = iter->user_data;
 749   array = get_array (elt, tree_model);
 750
 751   if (elt - ((SortElt*) array->data) >=  array->len - 1)
 752     {
 753       iter->stamp = 0;
 754       return FALSE;
 755     }
 756   iter->user_data = elt + 1;
 757   return TRUE;
 758 }
 759
 760 static gboolean
 761 gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
 762                                    GtkTreeIter  *iter,
 763                                    GtkTreeIter  *parent)
 764 {
 765   SortElt *elt;
 766
 767   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 768   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 769
 770   if (parent)
 771     g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
 772
 773   if (parent)
 774     elt = parent->user_data;
 775   else
 776     elt = (SortElt *) ((GArray *)GTK_TREE_MODEL_SORT (tree_model)->root)->data;
 777
 778   if (elt == NULL)
 779     return FALSE;
 780
 781   if (elt->children == NULL &&
 782       gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt))
 783     gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), elt);
 784
 785   if (elt->children == NULL)
 786     return FALSE;
 787
 788   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 789   iter->user_data = elt->children->data;
 790
 791   return TRUE;
 792 }
 793
 794 static gboolean
 795 gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
 796                                     GtkTreeIter  *iter)
 797 {
 798   SortElt *elt;
 799
 800   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 801   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 802   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);
 803
 804   elt = iter->user_data;
 805   if (elt->children)
 806     return TRUE;
 807
 808   return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *) elt);
 809 }
 810
 811 static gint
 812 gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
 813                                      GtkTreeIter  *iter)
 814 {
 815   SortElt *elt;
 816
 817   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
 818   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
 819   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
 820
 821   elt = iter->user_data;
 822   if (elt->children)
 823     return elt->children->len;
 824
 825   return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *) elt);
 826 }
 827
 828
 829 static gboolean
 830 gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
 831                                     GtkTreeIter  *iter,
 832                                     GtkTreeIter  *parent,
 833                                     gint          n)
 834 {
 835   SortElt *elt;
 836
 837   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 838   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 839   if (parent)
 840     g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
 841
 842   elt = iter->user_data;
 843
 844
 845   if (elt->children == NULL)
 846     {
 847       if (gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, (GtkTreeIter *)elt))
 848         gtk_tree_model_sort_build_level (GTK_TREE_MODEL_SORT (tree_model), elt);
 849       else
 850         return FALSE;
 851     }
 852
 853   if (elt->children == NULL)
 854     return FALSE;
 855
 856   if (n >= elt->children->len)
 857     return FALSE;
 858
 859   iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 860   iter->user_data = &g_array_index (elt->children, SortElt, n);
 861
 862   return TRUE;
 863 }
 864
 865 static gboolean
 866 gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
 867                                  GtkTreeIter  *iter,
 868                                  GtkTreeIter  *child)
 869 {
 870   SortElt *elt;
 871
 872   g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
 873   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
 874   g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);
 875
 876   elt = iter->user_data;
 877   if (elt->parent)
 878     {
 879       iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
 880       iter->user_data = elt->parent;
 881
 882       return TRUE;
 883     }
 884   return FALSE;
 885 }
 886
 887 static void
 888 gtk_tree_model_sort_ref_iter (GtkTreeModel *tree_model,
 889                               GtkTreeIter  *iter)
 890 {
 891 }
 892
 893 static void
 894 gtk_tree_model_sort_unref_iter (GtkTreeModel *tree_model,
 895                                 GtkTreeIter  *iter)
 896 {
 897
 898 }
 899
 900 /* Internal functions */
 901
 902 static gint
 903 gtk_tree_model_sort_array_find_insert (GtkTreeModelSort *tree_model_sort,
 904                                        GArray           *array,
 905                                        GtkTreeIter      *iter,
 906                                        gboolean          skip_sort_elt)
 907 {
 908   gint middle;
 909   gint cmp;
 910   GValueCompareFunc func;
 911   GValue value = {0, };
 912   GValue tmp_value = {0, };
 913   SortElt *tmp_elt;
 914
 915   func = (GValueCompareFunc) gtk_tree_model_sort_get_func (tree_model_sort);
 916
 917   g_return_val_if_fail (func != NULL, 0);
 918
 919   gtk_tree_model_get_value (tree_model_sort->child_model, iter, tree_model_sort->sort_col, &value);
 920
 921   for (middle = 0; middle < array->len; middle++)
 922     {
 923       tmp_elt = &(g_array_index (array, SortElt, middle));
 924       if (!skip_sort_elt &&
 925           (SortElt *) iter == tmp_elt)
 926           continue;
 927       gtk_tree_model_get_value (tree_model_sort->child_model,
 928                                 (GtkTreeIter *) tmp_elt,
 929                                 tree_model_sort->sort_col,
 930                                 &tmp_value);
 931
 932       cmp = ((func) (&value, &tmp_value));
 933       g_value_unset (&tmp_value);
 934
 935       if (cmp >= 0)
 936         break;
 937     }
 938   return middle;
 939 }
 940
 941
 942 static GtkTreePath *
 943 gtk_tree_model_sort_convert_path_real (GtkTreeModelSort *tree_model_sort,
 944                                        GtkTreePath      *child_path,
 945                                        gboolean          build_children)
 946 {
 947   GtkTreePath *retval;
 948   GArray *array;
 949   gint *indices;
 950   gint i = 0;
 951
 952   if (tree_model_sort->root == NULL)
 953     {
 954       if (build_children)
 955         gtk_tree_model_sort_build_level (tree_model_sort, NULL);
 956       else
 957         return FALSE;
 958     }
 959
 960   retval = gtk_tree_path_new ();
 961   array = (GArray *) tree_model_sort->root;
 962   indices = gtk_tree_path_get_indices (child_path);
 963
 964   do
 965     {
 966       SortElt *elt;
 967       gboolean found = FALSE;
 968       gint j;
 969
 970       if ((array->len < indices[i]) || (array == NULL))
 971         {
 972           gtk_tree_path_free (retval);
 973           return NULL;
 974         }
 975
 976       elt = (SortElt *) array->data;
 977       for (j = 0; j < array->len; j++, elt++)
 978         {
 979           if (elt->offset == indices[i])
 980             {
 981               found = TRUE;
 982               break;
 983             }
 984         }
 985       if (! found)
 986         {
 987           gtk_tree_path_free (retval);
 988           return NULL;
 989         }
 990
 991       gtk_tree_path_prepend_index (retval, j);
 992
 993       i++;
 994
 995       if (i == gtk_tree_path_get_depth (child_path))
 996         break;
 997
 998       if (elt->children == NULL)
 999         {
1000           if (build_children)
1001             {
1002               gtk_tree_path_prepend_index (retval, j);
1003               gtk_tree_model_sort_build_level (tree_model_sort, elt);
1004             }
1005           else
1006             {
1007               gtk_tree_path_free (retval);
1008               return NULL;
1009             }
1010         }
1011     }
1012   while (TRUE);
1013
1014   return retval;
1015 }
1016
1017 static void
1018 gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
1019                                  SortElt          *place)
1020 {
1021   gint n, i = 0;
1022   GArray *children;
1023   GtkTreeIter *parent_iter = NULL;
1024   GtkTreeIter iter;
1025   SortElt elt;
1026   SortData sort_data;
1027
1028   if (place)
1029     parent_iter = & (place->iter);
1030
1031
1032   n = gtk_tree_model_iter_n_children (tree_model_sort->child_model, parent_iter);
1033
1034   if (n == 0)
1035     return;
1036
1037   children = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), n);
1038
1039   if (place)
1040     place->children = children;
1041   else
1042     tree_model_sort->root = children;
1043
1044   gtk_tree_model_iter_children (tree_model_sort->child_model,
1045                                 &iter,
1046                                 parent_iter);
1047
1048   do
1049     {
1050       elt.iter = iter;
1051       elt.parent = place;
1052       elt.children = NULL;
1053       elt.ref = 0;
1054       elt.offset = i;
1055
1056       g_array_append_vals (children, &elt, 1);
1057       i++;
1058     }
1059   while (gtk_tree_model_iter_next (tree_model_sort->child_model, &iter));
1060
1061   sort_data.func = (GValueCompareFunc) gtk_tree_model_sort_get_func (tree_model_sort);
1062   sort_data.model = tree_model_sort->child_model;
1063   sort_data.sort_col = tree_model_sort->sort_col;
1064
1065   g_array_sort_with_data (children, gtk_tree_model_sort_func, &sort_data);
1066 }
1067
1068 static void
1069 gtk_tree_model_sort_free_level (GArray *array)
1070 {
1071   gint i;
1072
1073   if (array == NULL)
1074     return;
1075
1076   for (i = 0; i < array->len; i++)
1077     {
1078       SortElt *elt;
1079
1080       elt = &g_array_index (array, SortElt, i);
1081       if (elt->children)
1082         gtk_tree_model_sort_free_level (array);
1083     }
1084
1085   g_array_free (array, TRUE);
1086 }
1087
1088 static GFunc
1089 gtk_tree_model_sort_get_func (GtkTreeModelSort *tree_model_sort)
1090 {
1091   GValueCompareFunc func;
1092   if (tree_model_sort->func)
1093     func = tree_model_sort->func;
1094   else
1095     {
1096       switch (gtk_tree_model_get_column_type (tree_model_sort->child_model,
1097                                               tree_model_sort->sort_col))
1098         {
1099         case G_TYPE_STRING:
1100           func = &g_value_string_compare_func;
1101           break;
1102         case G_TYPE_INT:
1103           func = &g_value_int_compare_func;
1104           break;
1105         default:
1106           g_warning ("No comparison function for row %d (Type %s)\n",
1107                      tree_model_sort->sort_col,
1108                      g_type_name (gtk_tree_model_get_column_type (tree_model_sort->child_model,
1109                                                                   tree_model_sort->sort_col)));
1110           return NULL;
1111         }
1112
1113     }
1114   return (GFunc) func;
1115 }
1116
1117 static gint
1118 gtk_tree_model_sort_func  (gconstpointer a,
1119                            gconstpointer b,
1120                            gpointer      user_data)
1121 {
1122   GValue value_a = {0, };
1123   GValue value_b = {0, };
1124   SortData *sort_data = user_data;
1125   gint retval;
1126
1127   gtk_tree_model_get_value (sort_data->model, (GtkTreeIter *) a, sort_data->sort_col, &value_a);
1128   gtk_tree_model_get_value (sort_data->model, (GtkTreeIter *) b, sort_data->sort_col, &value_b);
1129
1130   retval = (sort_data->func) (&value_a, &value_b);
1131
1132   g_value_unset (&value_a);
1133   g_value_unset (&value_b);
1134
1135   return retval;
1136 }
1137
1138
1139 static gint
1140 g_value_string_compare_func (const GValue *a,
1141                              const GValue *b)
1142 {
1143   gchar *a_str = g_value_get_string (a);
1144   gchar *b_str = g_value_get_string (b);
1145
1146   if (b_str == NULL)
1147     return a_str == NULL;
1148   if (a_str == NULL)
1149     return -1;
1150
1151   return strcmp (a_str, b_str);
1152 }
1153
1154 static gint
1155 g_value_int_compare_func (const GValue *a,
1156                           const GValue *b)
1157 {
1158   gint a_int = g_value_get_int (a);
1159   gint b_int = g_value_get_int (b);
1160
1161   if (a_int < b_int)
1162     return -1;
1163   else if (a_int > b_int)
1164     return 1;
1165   else
1166     return 0;
1167 }
1168
1169
1170 /* DEAD CODE */
1171
1172 #if 0
1173   /* FIXME: we can, as we are an array, do binary search to find the correct
1174    * location to insert the element.  However, I'd rather get it working.  The
1175    * below is quite wrong, but a step in the right direction.
1176    */
1177   low = 0;
1178   high = array->len;
1179   middle = (low + high)/2;
1180
1181   /* Insert the value into the array */
1182   while (low != high)
1183     {
1184       gint cmp;
1185       tmp_elt = &(g_array_index (array, SortElt, middle));
1186       gtk_tree_model_get_value (sort->child_model,
1187                                 (GtkTreeIter *) tmp_elt,
1188                                 sort->sort_col,
1189                                 &tmp_value);
1190
1191       cmp = ((func) (&tmp_value, &s_value));
1192       g_value_unset (&tmp_value);
1193
1194       if (cmp < 0)
1195         high = middle;
1196       else if (cmp > 0)
1197         low = middle;
1198       else if (cmp == 0)
1199         break;
1200       middle = (low + high)/2;
1201     }
1202 #endif