gtktreemodelsort.c 65.1 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 "gtktreemodelsort.h"
41
#include "gtktreesortable.h"
42
#include "gtktreestore.h"
43
#include "gtksignal.h"
44
#include "gtktreedatalist.h"
45
#include <string.h>
46
#include "gtkintl.h"
47
48

typedef struct _SortElt SortElt;
49
50
51
52
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;
typedef struct _SortTuple SortTuple;

53
54
struct _SortElt
{
55
56
57
58
59
60
61
62
63
64
65
66
67
  GtkTreeIter  iter;
  SortLevel   *children;
  gint         offset;
  gint         ref_count;
  gint         zero_ref_count;
};

struct _SortLevel
{
  GArray    *array;
  gint       ref_count;
  SortElt   *parent_elt;
  SortLevel *parent_level;
68
69
};

Jonathan Blandford's avatar
Jonathan Blandford committed
70
71
struct _SortData
{
72
  GtkTreeModelSort *tree_model_sort;
73
74
75
76
77
  GtkTreePath *parent_path;
  gint parent_path_depth;
  gint *parent_path_indices;
  GtkTreeIterCompareFunc sort_func;
  gpointer sort_data;
Jonathan Blandford's avatar
Jonathan Blandford committed
78
79
};

80
81
82
struct _SortTuple
{
  SortElt   *elt;
83
  gint       offset;
84
};
85

86
87
88
89
90
91
92
93
94
/* Properties */
enum {
  PROP_0,
  /* Construct args */
  PROP_MODEL
};



95
96
97
98
99
100
#define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
	(((GtkTreeModelSort *)tree_model_sort)->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
#define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
#define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)

#define GET_CHILD_ITER(tree_model_sort,child_iter,sort_iter) gtk_tree_model_sort_convert_iter_to_child_iter(GTK_TREE_MODEL_SORT (tree_model_sort), child_iter, sort_iter);
101

102
/* general (object/interface init, etc) */
103
104
105
106
107
static void gtk_tree_model_sort_init                  (GtkTreeModelSort      *tree_model_sort);
static void gtk_tree_model_sort_class_init            (GtkTreeModelSortClass *tree_model_sort_class);
static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
static void gtk_tree_model_sort_finalize              (GObject               *object);
108
109
110
111
112
113
114
115
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);
116

117
/* our signal handlers */
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
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);
138
139

/* TreeModel interface */
140
static guint        gtk_tree_model_sort_get_flags          (GtkTreeModel          *tree_model);
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
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);
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);
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

/* TreeSortable interface */
175
176
177
178
179
180
181
182
183
184
185
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,
							       GtkDestroyNotify        destroy);
186
187
188
189
190
static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
							       GtkDestroyNotify        destroy);
static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
191

192
/* Private functions (sort funcs, level handling and other utils) */
193
194
195
196
197
198
199
200
201
202
203
static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *parent_level,
							   SortElt          *parent_elt);
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);
204
205
206
207
208
static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   GtkTreeIter      *iter,
							   gboolean          skip_sort_elt);
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
209
							   SortLevel        *level,
210
211
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
212
213
214
215
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);
216
217
218
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
219

220
static GObjectClass *parent_class = NULL;
221

222
GType
223
224
gtk_tree_model_sort_get_type (void)
{
225
  static GType tree_model_sort_type = 0;
226

227
228
229
230
231
  if (!tree_model_sort_type)
    {
      static const GTypeInfo tree_model_sort_info =
      {
        sizeof (GtkTreeModelSortClass),
232
233
        NULL,           /* base_init */
        NULL,           /* base_finalize */
234
        (GClassInitFunc) gtk_tree_model_sort_class_init,
235
236
        NULL,           /* class_finalize */
        NULL,           /* class_data */
237
        sizeof (GtkTreeModelSort),
238
        0,              /* n_preallocs */
239
240
241
242
243
        (GInstanceInitFunc) gtk_tree_model_sort_init
      };

      static const GInterfaceInfo tree_model_info =
      {
244
245
246
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
        NULL,
        NULL
247
248
      };

249
250
      static const GInterfaceInfo sortable_info =
      {
251
252
253
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
        NULL,
        NULL
254
255
      };

256
257
258
      tree_model_sort_type = g_type_register_static (G_TYPE_OBJECT,
						     "GtkTreeModelSort",
						     &tree_model_sort_info, 0);
259
      g_type_add_interface_static (tree_model_sort_type,
260
261
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
262

263
      g_type_add_interface_static (tree_model_sort_type,
264
265
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
266
267
268
269
270
271
    }

  return tree_model_sort_type;
}

static void
272
273
274
275
276
277
278
279
280
281
282
gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
{
  tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
  tree_model_sort->stamp = 0;
  tree_model_sort->zero_ref_count = 0;
  tree_model_sort->root = NULL;
  tree_model_sort->sort_list = NULL;
}

static void
gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
283
284
285
{
  GObjectClass *object_class;

286
  object_class = (GObjectClass *) class;
287
  parent_class = g_type_class_peek_parent (class);
288

289
290
291
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

292
  object_class->finalize = gtk_tree_model_sort_finalize;
293
294
295
296
297
298
299
300
301

  /* Properties */
  g_object_class_install_property (object_class,
                                   PROP_MODEL,
                                   g_param_spec_object ("model",
							_("TreeModelSort Model"),
							_("The model for the TreeModelSort to sort"),
							GTK_TYPE_TREE_MODEL,
							G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
302
303
304
305
306
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
307
  iface->get_flags = gtk_tree_model_sort_get_flags;
308
309
310
311
312
313
314
315
316
317
318
  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;
  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;
319
320
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
321
322
}

323
324
325
326
327
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;
328
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
329
330
  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;
331
332
}

333
334
335
336
337
338
339
340
/**
 * gtk_tree_model_sort_new_with_model:
 * @child_model: A #GtkTreeModel
 *
 * Creates a new #GtkTreeModel, with @child_model as the child_model.
 *
 * Return value: A new #GtkTreeModel.
 */
341
GtkTreeModel *
342
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
343
344
345
{
  GtkTreeModel *retval;

346
347
348
349
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

  retval = GTK_TREE_MODEL (g_object_new (gtk_tree_model_sort_get_type (), NULL));

350
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
351
352
353
354

  return retval;
}

355
356
357
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
358
{
359
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
360

361
362
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

363
  if (tree_model_sort->root)
364
    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
365
366
367
368
369
370

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
371
372
373

  /* must chain up */
  parent_class->finalize (object);
374
375
}

376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
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:
      g_value_set_object (value, gtk_tree_model_sort_get_model(tree_model_sort));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

414
static void
415
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
416
417
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
418
				 gpointer      data)
419
420
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
421
  GtkTreePath *path = NULL;
422
  GtkTreeIter iter;
423
  GtkTreeIter tmpiter;
424

425
  SortElt tmp;
426
427
  SortElt *elt;
  SortLevel *level;
428

429
430
431
  gboolean free_s_path = FALSE;

  gint offset, index = 0, i;
432
433

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

435
436
437
438
#ifdef VERBOSE
  g_print ("::row_changed run\n");
#endif

439
  if (!start_s_path)
440
441
    {
      free_s_path = TRUE;
442
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
443
    }
444

445
446
447
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
448
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
449
450
    {
      if (free_s_path)
451
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
452
453
      return;
    }
Jonathan Blandford's avatar
sync    
Jonathan Blandford committed
454

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

457
458
  level = iter.user_data;
  elt = iter.user_data2;
459

460
  if (level->array->len < 2 || tree_model_sort->sort_column_id == -1)
461
462
    {
      if (free_s_path)
463
	gtk_tree_path_free (start_s_path);
464

465
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
466

467
      gtk_tree_path_free (path);
468

469
470
471
      return;
    }

472
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
473
474
475
476
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
477

478
479
480
481
482
  offset = elt->offset;

  for (i = 0; i < level->array->len; i++)
    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
      index = i;
483

484
  memcpy (&tmp, elt, sizeof (SortElt));
485
  g_array_remove_index (level->array, index);
486

487
488
489
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
490
491
492
						   &tmp.iter,
						   TRUE);
  else
493
494
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
495
496
						   &tmpiter,
						   TRUE);
497

498
  g_array_insert_val (level->array, index, tmp);
499

500
501
502
  for (i = 0; i < level->array->len; i++)
    if (g_array_index (level->array, SortElt, i).children)
      g_array_index (level->array, SortElt, i).children->parent_elt = &g_array_index (level->array, SortElt, i);
503

504
505
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
506

507
508
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
509

510
511
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

512
513
  gtk_tree_path_free (path);
  if (free_s_path)
514
    gtk_tree_path_free (start_s_path);
515
516
}

517
518
519
520
521
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
522
{
523
524
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
525
  GtkTreeIter iter;
526
527
528
529
530
531
532
533
534
535
536
  GtkTreeIter real_s_iter;

  gint i = 0;

  gboolean free_s_path = FALSE;

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

  parent_level = level = SORT_LEVEL (tree_model_sort->root);
537

538
539
540
541
#ifdef VERBOSE
  g_print ("::row_inserted\n");
#endif

542
  g_return_if_fail (s_path != NULL || s_iter != NULL);
543

544
  if (!s_path)
545
    {
546
547
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
548
    }
549

550
551
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
552
  else
553
    real_s_iter = *s_iter;
554

555
556
557
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
558

559
560
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
561

562
      goto done_and_submit;
563
    }
564

565
566
567
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
568
569
      gint j;

570
571
572
573
574
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
575

576
577
578
579
580
581
582
      if (level->array->len < gtk_tree_path_get_indices (s_path)[i])
	{
	  g_warning ("A node was inserted with a parent that's not in the tree.\n"
		     "This possibly means that a GtkTreeModel inserted a child node\n"
		     "before the parent was inserted.");
	  goto done;
	}
583

584
585
586
587
588
589
590
591
592
      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);
593
594
595
596
597

      if (!elt->children)
	{
	  GtkTreePath *tmppath;
	  GtkTreeIter  tmpiter;
598

599
600
601
602
603
604
605
606
607
608
	  tmppath = gtk_tree_model_sort_elt_get_path (level, elt);
	  if (tmppath)
	    {
	      gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &tmpiter,
				       tmppath);
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
609

610
611
612
613
614
615
616
617
	  /* not covering this signal */
	  goto done;
	}

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

619
  if (!parent_level)
620
    goto done;
621

622
623
624
625
626
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
627

628
 done_and_submit:
629
630
631
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
632

633
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
634
    return;
635

636
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
637

638
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
639
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
640
  gtk_tree_path_free (path);
641

642
 done:
643
644
  if (free_s_path)
    gtk_tree_path_free (s_path);
645

646
  return;
647
648
649
}

static void
650
651
652
653
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
654
655
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
656
657
  GtkTreePath *path;
  GtkTreeIter iter;
658

659
  g_return_if_fail (s_path != NULL && s_iter != NULL);
660

661
662
  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
663
    return;
664

665
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
666
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
667

668
  gtk_tree_path_free (path);
669
670
}

671
/* FIXME: I still have doubts if this works */
672
static void
673
674
675
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
676
677
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
678
  GtkTreePath *path = NULL;
679
680
681
682
683
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
684

685
  g_return_if_fail (s_path != NULL);
686

687
688
689
690
#ifdef VERBOSE
  g_print ("::row_deleted\n");
#endif

691
692
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
693
694
    return;

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

697
698
699
700
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

701
702
703
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

704
705
706
  while (elt->ref_count > 0)
    gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);

707
  if (level->ref_count == 0 && level != tree_model_sort->root)
708
    {
709
710
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */
711
712
713
#ifdef VERBOSE
      g_print ("ref_count == 0, prune level\n");
#endif
714
715

      gtk_tree_path_free (path);
716
717
      return;
    }
718

719
720
721
722
723
724
  /* 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);
725

726
727
728
729
730
731
  /* 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--;
732
733
      if (elt->children)
	elt->children->parent_elt = elt;
734
    }
735
736

  gtk_tree_path_free (path);
737
738
}

739
static void
740
741
742
743
744
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
745
{
746
747
  SortElt *elt;
  SortLevel *level;
Jonathan Blandford's avatar
Jonathan Blandford committed
748
749
  GtkTreeIter iter;
  gint *tmp_array;
750
  int i, j;
751
  GtkTreePath *path;
752
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
753

754
  g_return_if_fail (new_order != NULL);
755

Jonathan Blandford's avatar
Jonathan Blandford committed
756
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
757
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
758
759
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
760
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
761
      level = SORT_LEVEL (tree_model_sort->root);
762
763
    }
  else
764
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
765
766
767
768
      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);
769

770
771
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
772
773

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
774
775
776
777
	{
	  gtk_tree_path_free (path);
	  return;
	}
778

779
780
781
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
782
  if (level->array->len < 2)
783
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
784
785
786
      gtk_tree_path_free (path);
      return;
    }
787

Jonathan Blandford's avatar
Jonathan Blandford committed
788
789
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
790
791
792
793
794
795
796
797
    {
      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
798
799
800
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
801

Jonathan Blandford's avatar
Jonathan Blandford committed
802
803
804
  if (tree_model_sort->sort_column_id == -1 &&
      tree_model_sort->default_sort_func == (GtkTreeIterCompareFunc) 0x1)
    {
805

806
807
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Jonathan Blandford's avatar
Jonathan Blandford committed
808
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
809

810
      if (gtk_tree_path_get_depth (path))
811
	{
812
813
814
815
816
	  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);
817
	}
818
      else
819
820
821
822
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
823
824
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
825
  gtk_tree_path_free (path);
826
827
828
829
830
831
832
833
834
}

/* Fulfill our model requirements */
static guint
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);

  return 0;
835
836
}

837
838
839
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
840
841
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

842
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
843
844
845

  if (tree_model_sort->child_model == 0)
    return 0;
846

847
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
848
849
850
851
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
852
                                     gint          index)
853
854
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
855
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
856

857
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
858
859
860
}

static gboolean
861
862
863
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
864
{
865
866
867
868
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
869

870
871
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
872

873
874
875
876
877
878
879
880
881
  tree_model_sort = (GtkTreeModelSort *) tree_model;
  indices = gtk_tree_path_get_indices (path);

  if (tree_model_sort->root == NULL)
    gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
  level = SORT_LEVEL (tree_model_sort->root);

  depth = gtk_tree_path_get_depth (path);
  if (depth == 0)
882
    return FALSE;
883

884
  for (i = 0; i < depth - 1; i++)
885
    {
886
887
888
      if ((level == NULL) ||
	  (level->array->len < indices[i]))
	return FALSE;
889

890
891
892
      if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, indices[i]));
      level = g_array_index (level->array, SortElt, indices[i]).children;
893
894
    }

895
896
897
898
899
  if (level == NULL)
    return FALSE;
  iter->stamp = tree_model_sort->stamp;
  iter->user_data = level;
  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
900

901
  return TRUE;
902
903
904
905
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
906
			      GtkTreeIter  *iter)
907
{
908
909
910
911
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

912
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
913
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
914
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
915

916
917
918
919
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
920
    {
921
922
923
924
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
925
    }
926
927

  return retval;
928
929
930
931
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
932
933
934
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
935
{
936
  GtkTreeIter child_iter;
937
938

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
939
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
940
941
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);

942
  GET_CHILD_ITER (tree_model, &child_iter, iter);
943
944
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
945
946
947
948
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
949
			       GtkTreeIter  *iter)
950
{
951
  SortLevel *level;
952
953
954
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
955
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
956
957
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

958
959
  level = iter->user_data;
  elt = iter->user_data2;
960

961
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
962
963
964
965
    {
      iter->stamp = 0;
      return FALSE;
    }
966
  iter->user_data2 = elt + 1;
967

968
969
970
971
972
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
973
974
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
975
{
976
977
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
978

979
  iter->stamp = 0;
980
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
981
982
  g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
  if (parent) g_return_val_if_fail (tree_model_sort->stamp == parent->stamp, FALSE);
Jonathan Blandford's avatar
Jonathan Blandford committed
983

984
985
986
987
988
989
  if (parent == NULL)
    {
      if (tree_model_sort->root == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
      if (tree_model_sort->root == NULL)
	return FALSE;
990

991
992
993
994
995
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
996
  else
997
    {
998
999
1000
1001
1002
      if (((SortElt *)parent->user_data2)->children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort,
					 (SortLevel *)parent->user_data,
					 (SortElt *)parent->user_data2);
      if (((SortElt *)parent->user_data2)->children == NULL)
1003
	return FALSE;
1004
1005
1006
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1007
    }
1008

1009
1010
1011
1012
1013
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1014
				    GtkTreeIter  *iter)
1015
{
1016
  GtkTreeIter child_iter;
1017
1018

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1019
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1020
1021
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1022
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1023

1024
  return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1025
1026
1027
1028
1029
1030
}

static gint
gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
				     GtkTreeIter  *iter)
{
1031
  GtkTreeIter child_iter;
1032
1033

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1034
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1035
  if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1036

1037
1038
  if (iter == NULL)
    return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1039

1040
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1041

1042
  return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1043
}
1044
1045
1046

static gboolean