gtktreemodelsort.c 80.8 KB
Newer Older
1
/* gtktreemodelsort.c
2
 * Copyright (C) 2000,2001  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
3
 * Copyright (C) 2001,2002  Kristian Rietveld <kris@gtk.org>
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

21
/* NOTE: There is a potential for confusion in this code as to whether an iter,
22 23
 * path or value refers to the GtkTreeModelSort model, or the child model being
 * sorted.  As a convention, variables referencing the child model will have an
24 25 26
 * s_ prefix before them (ie. s_iter, s_value, s_path);
 */

27 28 29 30 31 32 33
/* ITER FORMAT:
 *
 * iter->stamp = tree_model_sort->stamp
 * iter->user_data = SortLevel
 * iter->user_data2 = SortElt
 */

34 35 36 37 38 39
/* WARNING: this code is dangerous, can cause sleepless nights,
 * can cause your dog to die among other bad things
 *
 * we warned you and we're not liable for any head injuries.
 */

40
#include "config.h"
Manish Singh's avatar
Manish Singh committed
41 42
#include <string.h>

43
#include "gtktreemodelsort.h"
44
#include "gtktreesortable.h"
45
#include "gtktreestore.h"
46
#include "gtktreedatalist.h"
47
#include "gtkintl.h"
48
#include "gtkprivate.h"
49
#include "gtktreednd.h"
50

51

52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
/**
 * SECTION:gtktreemodelsort
 * @Short_description: A GtkTreeModel which makes an underlying tree model sortable
 * @Title: GtkTreeModelSort
 * @See_also: #GtkTreeModel, #GtkListStore, #GtkTreeStore, #GtkTreeSortable, #GtkTreeModelFilter
 *
 * The #GtkTreeModelSort is a model which implements the #GtkTreeSortable
 * interface.  It does not hold any data itself, but rather is created with
 * a child model and proxies its data.  It has identical column types to
 * this child model, and the changes in the child are propagated.  The
 * primary purpose of this model is to provide a way to sort a different
 * model without modifying it. Note that the sort function used by
 * #GtkTreeModelSort is not guaranteed to be stable.
 *
 * The use of this is best demonstrated through an example.  In the
 * following sample code we create two #GtkTreeView widgets each with a
 * view of the same data.  As the model is wrapped here by a
 * #GtkTreeModelSort, the two #GtkTreeView<!-- -->s can each sort their
 * view of the data without affecting the other.  By contrast, if we
 * simply put the same model in each widget, then sorting the first would
 * sort the second.
 *
 * <example>
 * <title>Using a <structname>GtkTreeModelSort</structname></title>
 * <programlisting>
 * {
 *   GtkTreeView *tree_view1;
 *   GtkTreeView *tree_view2;
 *   GtkTreeModel *sort_model1;
 *   GtkTreeModel *sort_model2;
 *   GtkTreeModel *child_model;
 *
 *   // get the child model
 *   child_model = get_my_model ();
 *
 *   // Create the first tree
 *   sort_model1 = gtk_tree_model_sort_new_with_model (child_model);
 *   tree_view1 = gtk_tree_view_new_with_model (sort_model1);
 *
 *   // Create the second tree
 *   sort_model2 = gtk_tree_model_sort_new_with_model (child_model);
 *   tree_view2 = gtk_tree_view_new_with_model (sort_model2);
 *
 *   // Now we can sort the two models independently
 *   gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model1),
 *                                         COLUMN_1, GTK_SORT_ASCENDING);
 *   gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model2),
 *                                         COLUMN_1, GTK_SORT_DESCENDING);
 * }
 * </programlisting>
 * </example>
 *
 * To demonstrate how to access the underlying child model from the sort
 * model, the next example will be a callback for the #GtkTreeSelection
 * #GtkTreeSelection::changed signal.  In this callback, we get a string
 * from COLUMN_1 of the model.  We then modify the string, find the same
 * selected row on the child model, and change the row there.
 *
 * <example>
 * <title>Accessing the child model of in a selection changed callback</title>
 * <programlisting>
 * void
 * selection_changed (GtkTreeSelection *selection, gpointer data)
 * {
 *   GtkTreeModel *sort_model = NULL;
 *   GtkTreeModel *child_model;
 *   GtkTreeIter sort_iter;
 *   GtkTreeIter child_iter;
 *   char *some_data = NULL;
 *   char *modified_data;
 *
 *   // Get the current selected row and the model.
 *   if (! gtk_tree_selection_get_selected (selection,
 *                                          &sort_model,
 *                                          &sort_iter))
 *     return;
 *
 *   /<!---->* Look up the current value on the selected row and get a new value
 *    * to change it to.
 *    *<!---->/
 *   gtk_tree_model_get (GTK_TREE_MODEL (sort_model), &sort_iter,
 *                       COLUMN_1, &some_data,
 *                       -1);
 *
 *   modified_data = change_the_data (some_data);
 *   g_free (some_data);
 *
 *   // Get an iterator on the child model, instead of the sort model.
 *   gtk_tree_model_sort_convert_iter_to_child_iter (GTK_TREE_MODEL_SORT (sort_model),
 *                                                   &child_iter,
 *                                                   &sort_iter);
 *
 *   /<!---->* Get the child model and change the value of the row.  In this
 *    * example, the child model is a GtkListStore.  It could be any other
 *    * type of model, though.
 *    *<!---->/
 *   child_model = gtk_tree_model_sort_get_model (GTK_TREE_MODEL_SORT (sort_model));
 *   gtk_list_store_set (GTK_LIST_STORE (child_model), &child_iter,
 *                       COLUMN_1, &modified_data,
 *                       -1);
 *   g_free (modified_data);
 * }
 * </programlisting>
 * </example>
 */


159
typedef struct _SortElt SortElt;
160 161 162 163
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;
typedef struct _SortTuple SortTuple;

164 165
struct _SortElt
{
166 167 168 169 170 171 172 173 174 175 176
  GtkTreeIter  iter;
  SortLevel   *children;
  gint         offset;
  gint         ref_count;
  gint         zero_ref_count;
};

struct _SortLevel
{
  GArray    *array;
  gint       ref_count;
177
  gint       parent_elt_index;
178
  SortLevel *parent_level;
179 180
};

Jonathan Blandford's avatar
Jonathan Blandford committed
181 182
struct _SortData
{
183
  GtkTreeModelSort *tree_model_sort;
184 185 186 187 188
  GtkTreePath *parent_path;
  gint parent_path_depth;
  gint *parent_path_indices;
  GtkTreeIterCompareFunc sort_func;
  gpointer sort_data;
Jonathan Blandford's avatar
Jonathan Blandford committed
189 190
};

191 192 193
struct _SortTuple
{
  SortElt   *elt;
194
  gint       offset;
195
};
196

197 198 199 200 201 202 203 204
/* Properties */
enum {
  PROP_0,
  /* Construct args */
  PROP_MODEL
};


205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
struct _GtkTreeModelSortPrivate
{
  gpointer root;
  gint stamp;
  guint child_flags;
  GtkTreeModel *child_model;
  gint zero_ref_count;

  /* sort information */
  GList *sort_list;
  gint sort_column_id;
  GtkSortType order;

  /* default sort */
  GtkTreeIterCompareFunc default_sort_func;
  gpointer default_sort_data;
  GDestroyNotify default_sort_destroy;

  /* signal ids */
  gulong changed_id;
  gulong inserted_id;
  gulong has_child_toggled_id;
  gulong deleted_id;
  gulong reordered_id;
};

231

232
#define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
233
	(((GtkTreeModelSort *)tree_model_sort)->priv->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
234 235 236
#define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
#define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)

237 238 239 240
#define SORT_LEVEL_PARENT_ELT(level) (&g_array_index (SORT_LEVEL ((level))->parent_level->array, SortElt, SORT_LEVEL ((level))->parent_elt_index))
#define SORT_LEVEL_ELT_INDEX(level, elt) (SORT_ELT ((elt)) - SORT_ELT (SORT_LEVEL ((level))->array->data))


Matthias Clasen's avatar
Matthias Clasen committed
241
#define GET_CHILD_ITER(tree_model_sort,ch_iter,so_iter) gtk_tree_model_sort_convert_iter_to_child_iter((GtkTreeModelSort*)(tree_model_sort), (ch_iter), (so_iter));
242

243 244
#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)

245
#define VALID_ITER(iter, tree_model_sort) ((iter) != NULL && (iter)->user_data != NULL && (iter)->user_data2 != NULL && (tree_model_sort)->priv->stamp == (iter)->stamp)
Kristian Rietveld's avatar
Kristian Rietveld committed
246

247
/* general (object/interface init, etc) */
248 249
static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
250
static void gtk_tree_model_sort_drag_source_init      (GtkTreeDragSourceIface*iface);
251
static void gtk_tree_model_sort_finalize              (GObject               *object);
252 253 254 255 256 257 258 259
static void gtk_tree_model_sort_set_property          (GObject               *object,
						       guint                  prop_id,
						       const GValue          *value,
						       GParamSpec            *pspec);
static void gtk_tree_model_sort_get_property          (GObject               *object,
						       guint                  prop_id,
						       GValue                *value,
						       GParamSpec            *pspec);
260

261
/* our signal handlers */
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
static void gtk_tree_model_sort_row_changed           (GtkTreeModel          *model,
						       GtkTreePath           *start_path,
						       GtkTreeIter           *start_iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_inserted          (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_deleted           (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       gpointer               data);
static void gtk_tree_model_sort_rows_reordered        (GtkTreeModel          *s_model,
						       GtkTreePath           *s_path,
						       GtkTreeIter           *s_iter,
						       gint                  *new_order,
						       gpointer               data);
282 283

/* TreeModel interface */
284
static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
285 286 287 288 289 290 291 292 293 294 295 296 297 298
static gint         gtk_tree_model_sort_get_n_columns      (GtkTreeModel          *tree_model);
static GType        gtk_tree_model_sort_get_column_type    (GtkTreeModel          *tree_model,
                                                            gint                   index);
static gboolean     gtk_tree_model_sort_get_iter           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreePath           *path);
static GtkTreePath *gtk_tree_model_sort_get_path           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static void         gtk_tree_model_sort_get_value          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            gint                   column,
                                                            GValue                *value);
static gboolean     gtk_tree_model_sort_iter_next          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
299 300
static gboolean     gtk_tree_model_sort_iter_previous      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
static gboolean     gtk_tree_model_sort_iter_children      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent);
static gboolean     gtk_tree_model_sort_iter_has_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gint         gtk_tree_model_sort_iter_n_children    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_nth_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent,
                                                            gint                   n);
static gboolean     gtk_tree_model_sort_iter_parent        (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *child);
static void         gtk_tree_model_sort_ref_node           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
317 318 319
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
320 321 322
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

323 324 325 326 327 328 329 330 331
/* TreeDragSource interface */
static gboolean     gtk_tree_model_sort_row_draggable         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);
static gboolean     gtk_tree_model_sort_drag_data_get         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path,
							       GtkSelectionData       *selection_data);
static gboolean     gtk_tree_model_sort_drag_data_delete      (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);

332
/* TreeSortable interface */
333 334 335 336 337 338 339 340 341 342
static gboolean     gtk_tree_model_sort_get_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                   *sort_column_id,
							       GtkSortType            *order);
static void         gtk_tree_model_sort_set_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkSortType        order);
static void         gtk_tree_model_sort_set_sort_func         (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
343
							       GDestroyNotify          destroy);
344 345 346
static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
347
							       GDestroyNotify          destroy);
348
static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
349

350
/* Private functions (sort funcs, level handling and other utils) */
351 352
static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *parent_level,
353
							   gint              parent_elt_index);
354 355 356 357 358 359 360 361
static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *sort_level);
static void         gtk_tree_model_sort_increment_stamp   (GtkTreeModelSort *tree_model_sort);
static void         gtk_tree_model_sort_sort_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   gboolean          recurse,
							   gboolean          emit_reordered);
static void         gtk_tree_model_sort_sort              (GtkTreeModelSort *tree_model_sort);
362 363 364
static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   GtkTreeIter      *iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
365
							   gint             skip_index);
366
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
367
							   SortLevel        *level,
368 369
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
370 371 372 373
static GtkTreePath *gtk_tree_model_sort_elt_get_path      (SortLevel        *level,
							   SortElt          *elt);
static void         gtk_tree_model_sort_set_model         (GtkTreeModelSort *tree_model_sort,
							   GtkTreeModel     *child_model);
374 375 376
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
377 378


Matthias Clasen's avatar
Matthias Clasen committed
379 380 381 382 383 384
G_DEFINE_TYPE_WITH_CODE (GtkTreeModelSort, gtk_tree_model_sort, G_TYPE_OBJECT,
			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
						gtk_tree_model_sort_tree_model_init)
			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_SORTABLE,
						gtk_tree_model_sort_tree_sortable_init)
			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
Matthias Clasen's avatar
Matthias Clasen committed
385
						gtk_tree_model_sort_drag_source_init))
386 387

static void
388 389
gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
{
390 391 392 393 394 395 396 397 398 399 400
  GtkTreeModelSortPrivate *priv;

  priv = G_TYPE_INSTANCE_GET_PRIVATE (tree_model_sort,
                                      GTK_TYPE_TREE_MODEL_SORT,
                                      GtkTreeModelSortPrivate);
  tree_model_sort->priv = priv;
  priv->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
  priv->stamp = 0;
  priv->zero_ref_count = 0;
  priv->root = NULL;
  priv->sort_list = NULL;
401 402 403 404
}

static void
gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
405 406 407
{
  GObjectClass *object_class;

408
  object_class = (GObjectClass *) class;
409

410 411 412
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

413
  object_class->finalize = gtk_tree_model_sort_finalize;
414 415 416 417 418

  /* Properties */
  g_object_class_install_property (object_class,
                                   PROP_MODEL,
                                   g_param_spec_object ("model",
419 420
							P_("TreeModelSort Model"),
							P_("The model for the TreeModelSort to sort"),
421
							GTK_TYPE_TREE_MODEL,
422
							GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
423 424

  g_type_class_add_private (class, sizeof (GtkTreeModelSortPrivate));
425 426 427 428 429
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
430
  iface->get_flags = gtk_tree_model_sort_get_flags;
431 432 433 434 435 436
  iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
  iface->get_column_type = gtk_tree_model_sort_get_column_type;
  iface->get_iter = gtk_tree_model_sort_get_iter;
  iface->get_path = gtk_tree_model_sort_get_path;
  iface->get_value = gtk_tree_model_sort_get_value;
  iface->iter_next = gtk_tree_model_sort_iter_next;
437
  iface->iter_previous = gtk_tree_model_sort_iter_previous;
438 439 440 441 442
  iface->iter_children = gtk_tree_model_sort_iter_children;
  iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
  iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
  iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
  iface->iter_parent = gtk_tree_model_sort_iter_parent;
443 444
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
445 446
}

447 448 449 450 451
static void
gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
{
  iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
  iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
452
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
453 454
  iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
  iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
455 456
}

457 458 459 460 461 462 463 464
static void
gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface *iface)
{
  iface->row_draggable = gtk_tree_model_sort_row_draggable;
  iface->drag_data_delete = gtk_tree_model_sort_drag_data_delete;
  iface->drag_data_get = gtk_tree_model_sort_drag_data_get;
}

465 466 467 468
/**
 * gtk_tree_model_sort_new_with_model:
 * @child_model: A #GtkTreeModel
 *
Matthias Clasen's avatar
Matthias Clasen committed
469
 * Creates a new #GtkTreeModel, with @child_model as the child model.
470
 *
471
 * Return value: (transfer full): A new #GtkTreeModel.
472
 */
473
GtkTreeModel *
474
gtk_tree_model_sort_new_with_model (GtkTreeModel *child_model)
475 476 477
{
  GtkTreeModel *retval;

478 479
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

Manish Singh's avatar
Manish Singh committed
480
  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
481

482
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
483 484 485 486

  return retval;
}

487 488 489
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
490
{
491
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
492
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
493

494 495
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

496 497
  if (priv->root)
    gtk_tree_model_sort_free_level (tree_model_sort, priv->root);
498

499
  if (priv->sort_list)
500
    {
501 502
      _gtk_tree_data_list_header_free (priv->sort_list);
      priv->sort_list = NULL;
503
    }
504

505
  if (priv->default_sort_destroy)
506
    {
507 508 509
      priv->default_sort_destroy (priv->default_sort_data);
      priv->default_sort_destroy = NULL;
      priv->default_sort_data = NULL;
510 511 512
    }


513
  /* must chain up */
Matthias Clasen's avatar
Matthias Clasen committed
514
  G_OBJECT_CLASS (gtk_tree_model_sort_parent_class)->finalize (object);
515 516
}

517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546
static void
gtk_tree_model_sort_set_property (GObject      *object,
				  guint         prop_id,
				  const GValue *value,
				  GParamSpec   *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
      gtk_tree_model_sort_set_model (tree_model_sort, g_value_get_object (value));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

static void
gtk_tree_model_sort_get_property (GObject    *object,
				  guint       prop_id,
				  GValue     *value,
				  GParamSpec *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
547
      g_value_set_object (value, gtk_tree_model_sort_get_model (tree_model_sort));
548 549 550 551 552 553 554
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

555
static void
556
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
557 558
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
559
				 gpointer      data)
560 561
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
562
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
563
  GtkTreePath *path = NULL;
564
  GtkTreeIter iter;
565
  GtkTreeIter tmpiter;
566

567
  SortElt tmp;
568 569
  SortElt *elt;
  SortLevel *level;
570

571 572
  gboolean free_s_path = FALSE;

Kristian Rietveld's avatar
Kristian Rietveld committed
573
  gint index = 0, old_index, i;
574 575

  g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
576

577
  if (!start_s_path)
578 579
    {
      free_s_path = TRUE;
580
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
581
    }
582

583 584 585
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
586
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
587 588
    {
      if (free_s_path)
589
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
590 591
      return;
    }
Jonathan Blandford's avatar
sync  
Jonathan Blandford committed
592

593
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
594
  gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (data), &iter);
595

596 597
  level = iter.user_data;
  elt = iter.user_data2;
598

599
  if (level->array->len < 2 ||
600 601
      (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
       priv->default_sort_func == NO_SORT_FUNC))
602 603
    {
      if (free_s_path)
604
	gtk_tree_path_free (start_s_path);
605

606
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
607
      gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
608

609
      gtk_tree_path_free (path);
610

611 612
      return;
    }
613
  
614
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
615
    {
616
      gtk_tree_model_get_iter (priv->child_model,
617 618
			       &tmpiter, start_s_path);
    }
619

Kristian Rietveld's avatar
Kristian Rietveld committed
620
  old_index = elt - SORT_ELT (level->array->data);
621

622
  memcpy (&tmp, elt, sizeof (SortElt));
623

624 625 626
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
627
						   &tmp.iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
628
						   old_index);
629
  else
630 631
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
632
						   &tmpiter,
Kristian Rietveld's avatar
Kristian Rietveld committed
633
						   old_index);
634

635 636 637 638 639 640 641 642 643 644 645 646 647 648
  if (index < old_index)
    {
      g_memmove (level->array->data + ((index + 1)*sizeof (SortElt)),
		 level->array->data + ((index)*sizeof (SortElt)),
		 (old_index - index)* sizeof(SortElt));
    }
  else if (index > old_index)
    {
      g_memmove (level->array->data + ((old_index)*sizeof (SortElt)),
		 level->array->data + ((old_index + 1)*sizeof (SortElt)),
		 (index - old_index)* sizeof(SortElt));
    }
  memcpy (level->array->data + ((index)*sizeof (SortElt)),
	  &tmp, sizeof (SortElt));
649

650 651
  for (i = 0; i < level->array->len; i++)
    if (g_array_index (level->array, SortElt, i).children)
652
      g_array_index (level->array, SortElt, i).children->parent_elt_index = i;
653

654 655
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
656

657
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
658

659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691
  /* if the item moved, then emit rows_reordered */
  if (old_index != index)
    {
      gint *new_order;
      gint j;

      GtkTreePath *tmppath;

      new_order = g_new (gint, level->array->len);

      for (j = 0; j < level->array->len; j++)
        {
	  if (index > old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j >= old_index && j < index)
		new_order[j] = j + 1;
	      else
		new_order[j] = j;
	    }
	  else if (index < old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j > index && j <= old_index)
		new_order[j] = j - 1;
	      else
		new_order[j] = j;
	    }
	  /* else? shouldn't really happen */
	}

692
      if (level->parent_elt_index >= 0)
693
        {
694
	  iter.stamp = priv->stamp;
695
	  iter.user_data = level->parent_level;
696
	  iter.user_data2 = SORT_LEVEL_PARENT_ELT (level);
697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717

	  tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort), &iter);

	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
	                                 tmppath, &iter, new_order);
	}
      else
        {
	  /* toplevel */
	  tmppath = gtk_tree_path_new ();

          gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), tmppath,
	                                 NULL, new_order);
	}

      gtk_tree_path_free (tmppath);
      g_free (new_order);
    }

  /* emit row_changed signal (at new location) */
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
718
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
719
  gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
720

721 722
  gtk_tree_path_free (path);
  if (free_s_path)
723
    gtk_tree_path_free (start_s_path);
724 725
}

726 727 728 729 730
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
731
{
732
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
733
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
734
  GtkTreePath *path;
735
  GtkTreeIter iter;
736 737 738 739 740 741 742 743 744 745
  GtkTreeIter real_s_iter;

  gint i = 0;

  gboolean free_s_path = FALSE;

  SortElt *elt;
  SortLevel *level;
  SortLevel *parent_level = NULL;

746
  parent_level = level = SORT_LEVEL (priv->root);
747

748
  g_return_if_fail (s_path != NULL || s_iter != NULL);
749

750
  if (!s_path)
751
    {
752 753
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
754
    }
755

756 757
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
758
  else
759
    real_s_iter = *s_iter;
760

761
  if (!priv->root)
762
    {
763
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, -1);
764

765 766
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
767

768
      goto done_and_submit;
769
    }
770

771 772 773
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
774 775
      gint j;

776 777 778 779 780
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
781

782 783
      if (level->array->len < gtk_tree_path_get_indices (s_path)[i])
	{
784
	  g_warning ("%s: A node was inserted with a parent that's not in the tree.\n"
785
		     "This possibly means that a GtkTreeModel inserted a child node\n"
786 787
		     "before the parent was inserted.",
		     G_STRLOC);
788 789
	  goto done;
	}
790

791 792 793 794 795 796 797 798 799
      elt = NULL;
      for (j = 0; j < level->array->len; j++)
	if (g_array_index (level->array, SortElt, j).offset == gtk_tree_path_get_indices (s_path)[i])
	  {
	    elt = &g_array_index (level->array, SortElt, j);
	    break;
	  }

      g_return_if_fail (elt != NULL);
800 801 802 803 804 805 806 807 808 809 810

      if (!elt->children)
	{
	  /* not covering this signal */
	  goto done;
	}

      level = elt->children;
      parent_level = level;
      i++;
    }
811

812
  if (!parent_level)
813
    goto done;
814

815
  if (level->ref_count == 0 && level != priv->root)
816 817 818 819 820
    {
      gtk_tree_model_sort_free_level (tree_model_sort, level);
      goto done;
    }

821 822 823 824 825
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
826

827
 done_and_submit:
828 829 830
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
831

832
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
833
    return;
834

835
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
836

837
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
838
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
839
  gtk_tree_path_free (path);
840

841
 done:
842 843
  if (free_s_path)
    gtk_tree_path_free (s_path);
844

845
  return;
846 847 848
}

static void
849 850 851 852
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
853 854
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
855 856
  GtkTreePath *path;
  GtkTreeIter iter;
857

858
  g_return_if_fail (s_path != NULL && s_iter != NULL);
859

860 861
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
Jonathan Blandford's avatar
Jonathan Blandford committed
862
    return;
863

864
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
865
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
866

867
  gtk_tree_path_free (path);
868 869 870
}

static void
871 872 873
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
874 875
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
876
  GtkTreePath *path = NULL;
877 878 879 880 881
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
882

883
  g_return_if_fail (s_path != NULL);
884

885 886
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
887 888
    return;

889
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
890

891 892 893 894
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

895 896 897 898 899 900 901 902
  /* we _need_ to emit ::row_deleted before we start unreffing the node
   * itself. This is because of the row refs, which start unreffing nodes
   * when we emit ::row_deleted
   */
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);

903
  while (elt->ref_count > 0)
904
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
905

906
  if (level->ref_count == 0)
907
    {
908 909 910 911
      /* This will prune the level, so I can just emit the signal and 
       * not worry about cleaning this level up. 
       * Careful, root level is not cleaned up in increment stamp.
       */
912
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
913
      gtk_tree_path_free (path);
914
      if (level == tree_model_sort->priv->root)
915 916
	{
	  gtk_tree_model_sort_free_level (tree_model_sort, 
917 918
					  tree_model_sort->priv->root);
	  tree_model_sort->priv->root = NULL;
919
	}
920 921
      return;
    }
922

923 924
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

925 926 927 928 929 930
  /* Remove the row */
  for (i = 0; i < level->array->len; i++)
    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
      break;

  g_array_remove_index (level->array, i);
931

932 933 934 935 936 937
  /* update all offsets */
  for (i = 0; i < level->array->len; i++)
    {
      elt = & (g_array_index (level->array, SortElt, i));
      if (elt->offset > offset)
	elt->offset--;
938
      if (elt->children)
939
	elt->children->parent_elt_index = i;
940
    }
941 942

  gtk_tree_path_free (path);
943 944
}

945
static void
946 947 948 949 950
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
951
{
952 953
  SortElt *elt;
  SortLevel *level;
Jonathan Blandford's avatar
Jonathan Blandford committed
954 955
  GtkTreeIter iter;
  gint *tmp_array;
956
  int i, j;
957
  GtkTreePath *path;
958
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
959
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
960

961
  g_return_if_fail (new_order != NULL);
962

Matthias Clasen's avatar
Matthias Clasen committed
963
  if (s_path == NULL || gtk_tree_path_get_depth (s_path) == 0)
964
    {
965
      if (priv->root == NULL)
Jonathan Blandford's avatar
Jonathan Blandford committed
966
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
967
      path = gtk_tree_path_new ();
968
      level = SORT_LEVEL (priv->root);
969 970
    }
  else
971
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
972 973 974 975
      path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
      if (path == NULL)
	return;
      gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
976

977 978
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
979 980

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
981 982 983 984
	{
	  gtk_tree_path_free (path);
	  return;
	}
985

986 987 988
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
989
  if (level->array->len < 2)
990
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
991 992 993
      gtk_tree_path_free (path);
      return;
    }
994

Jonathan Blandford's avatar
Jonathan Blandford committed
995 996
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
997 998 999 1000 1001 1002 1003 1004
    {
      for (j = 0; j < level->array->len; j++)
	{
	  if (g_array_index (level->array, SortElt, i).offset == new_order[j])
	    tmp_array[i] = j;
	}
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
1005 1006 1007
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
1008

1009 1010
  if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
      priv->default_sort_func == NO_SORT_FUNC)
Jonathan Blandford's avatar
Jonathan Blandford committed
1011
    {
1012

1013 1014
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Owen Taylor's avatar
Owen Taylor committed
1015
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
1016

1017
      if (gtk_tree_path_get_depth (path))
1018
	{
1019 1020 1021 1022 1023
	  gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
				   &iter,
				   path);
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, &iter, new_order);
1024
	}
1025
      else
1026 1027 1028 1029
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
1030 1031
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
1032
  gtk_tree_path_free (path);
1033 1034 1035
}

/* Fulfill our model requirements */
1036
static GtkTreeModelFlags
1037 1038
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
Matthias Clasen's avatar
Matthias Clasen committed
1039
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1040 1041
  GtkTreeModelFlags flags;

1042
  g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, 0);
1043

1044
  flags = gtk_tree_model_get_flags (tree_model_sort->priv->child_model);
1045 1046 1047

  if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
    return GTK_TREE_MODEL_LIST_ONLY;
1048 1049

  return 0;
1050 1051
}

1052 1053 1054
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
1055 1056
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

1057
  if (tree_model_sort->priv->child_model == 0)
1058
    return 0;
1059

1060
  return gtk_tree_model_get_n_columns (tree_model_sort->priv->child_model);
1061 1062 1063 1064
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
1065
                                     gint          index)
1066
{
Matthias Clasen's avatar
Matthias Clasen committed
1067
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1068

1069
  g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, G_TYPE_INVALID);
Matthias Clasen's avatar
Matthias Clasen committed
1070

1071
  return gtk_tree_model_get_column_type (tree_model_sort->priv->child_model, index);
1072 1073 1074
}

static gboolean
1075 1076 1077
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
1078
{
Matthias Clasen's avatar
Matthias Clasen committed
1079
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1080
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1081 1082 1083
  gint *indices;
  SortLevel *level;
  gint depth, i;
1084

1085
  g_return_val_if_fail (priv->child_model != NULL, FALSE);
1086

1087 1088
  indices = gtk_tree_path_get_indices (path);

1089
  if (priv->root == NULL)
1090
    gtk_tree_model_sort_build_level (tree_model_sort, NULL, -1);
1091
  level = SORT_LEVEL (priv->root);
1092 1093 1094

  depth = gtk_tree_path_get_depth (path);
  if (depth == 0)
1095
    return FALSE;
1096

1097
  for (i = 0; i < depth - 1; i++)
1098
    {
1099
      if ((level == NULL) ||
1100
	  (indices[i] >= level->array->len))
1101
	return FALSE;
1102

1103
      if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
1104
	gtk_tree_model_sort_build_level (tree_model_sort, level, indices[i]);
1105
      level = g_array_index (level->array, SortElt, indices[i]).children;
1106 1107
    }

1108 1109 1110 1111 1112 1113
  if (!level || indices[i] >= level->array->len)
    {
      iter->stamp = 0;
      return FALSE;
    }

1114
  iter->stamp = priv->stamp;
1115 1116
  iter->user_data = level;
  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
1117

1118
  return TRUE;
1119 1120 1121 1122
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,