gtktreemodelsort.c 84 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
 *
 * 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
Javier Jardón's avatar
Javier Jardón committed
16
 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
17 18
 */

19
#include "config.h"
Manish Singh's avatar
Manish Singh committed
20 21
#include <string.h>

22
#include "gtktreemodelsort.h"
23
#include "gtktreesortable.h"
24
#include "gtktreestore.h"
25
#include "gtktreedatalist.h"
26
#include "gtkintl.h"
27
#include "gtkprivate.h"
28
#include "gtktreednd.h"
29

30

31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 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
/**
 * 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>
 */


138 139 140 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 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
/* Notes on this implementation of GtkTreeModelSort
 * ================================================
 *
 * Warnings
 * --------
 *
 * In this code there is a potential for confusion as to whether an iter,
 * path or value refers to the GtkTreeModelSort model, or to the child model
 * that has been set. As a convention, variables referencing the child model
 * will have an s_ prefix before them (ie. s_iter, s_value, s_path);
 * Conversion of iterators and paths between GtkTreeModelSort and the child
 * model is done through the various gtk_tree_model_sort_convert_* functions.
 *
 * Iterator format
 * ---------------
 *
 * The iterator format of iterators handed out by GtkTreeModelSort is as
 * follows:
 *
 *    iter->stamp = tree_model_sort->stamp
 *    iter->user_data = SortLevel
 *    iter->user_data2 = SortElt
 *
 * Internal data structure
 * -----------------------
 *
 * Using SortLevel and SortElt, GtkTreeModelSort maintains a "cache" of
 * the mapping from GtkTreeModelSort nodes to nodes in the child model.
 * This is to avoid sorting a level each time an operation is requested
 * on GtkTreeModelSort, such as get iter, get path, get value.
 *
 * A SortElt corresponds to a single node. A node and its siblings are
 * stored in a SortLevel. The SortLevel keeps a reference to the parent
 * SortElt and its SortLevel (if any). The SortElt can have a "children"
 * pointer set, which points at a child level (a sub level).
 *
 * In a SortLevel, nodes are stored in a GSequence. The GSequence
 * allows for fast additions and removals, and supports sorting
 * the level of SortElt nodes.
 *
 * It is important to recognize the two different mappings that play
 * a part in this code:
 *   I.  The mapping from the client to this model. The order in which
 *       nodes are stored in the GSequence is the order in which the
 *       nodes are exposed to clients of the GtkTreeModelSort.
 *   II. The mapping from this model to its child model. Each SortElt
 *       contains an "offset" field which is the offset of the
 *       corresponding node in the child model.
 *
 * Reference counting
 * ------------------
 *
 * GtkTreeModelSort forwards all reference and unreference operations
 * to the corresponding node in the child model. The reference count
 * of each node is also maintained internally, in the "ref_count"
 * fields in SortElt and SortLevel. For each ref and unref operation on
 * a SortElt, the "ref_count" of the SortLevel is updated accordingly.
 * In addition, if a SortLevel has a parent, a reference is taken on
 * this parent. This happens in gtk_tree_model_sort_build_level() and
 * the reference is released again in gtk_tree_model_sort_free_level().
 * This ensures that when GtkTreeModelSort takes a reference on a node
 * (for example during sorting), all parent nodes are referenced
 * according to reference counting rule 1, see the GtkTreeModel
 * documentation.
 *
 * When a level has a reference count of zero, which means that
 * none of the nodes in the level is referenced, the level has
 * a "zero ref count" on all its parents. As soon as the level
 * reaches a reference count of zero, the zero ref count value is
 * incremented by one on all parents of this level. Similarly, as
 * soon as the reference count of a level changes from zero, the
 * zero ref count value is decremented by one on all parents.
 *
 * The zero ref count value is used to clear unused portions of
 * the cache. If a SortElt has a zero ref count of one, then
 * its child level is unused and can be removed from the cache.
 * If the zero ref count value is higher than one, then the
 * child level contains sublevels which are unused as well.
 * gtk_tree_model_sort_clear_cache() uses this to not recurse
 * into levels which have a zero ref count of zero.
 */

220
typedef struct _SortElt SortElt;
221 222 223
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;

224 225
struct _SortElt
{
226 227 228 229 230 231 232
  GtkTreeIter    iter;
  SortLevel     *children;
  gint           offset;
  gint           ref_count;
  gint           zero_ref_count;
  GSequenceIter *siter; /* iter into seq */
  gint           old_index; /* used while sorting */
233 234 235 236
};

struct _SortLevel
{
237
  GSequence *seq;
238
  gint       ref_count;
239
  SortElt   *parent_elt;
240
  SortLevel *parent_level;
241 242
};

Jonathan Blandford's avatar
Jonathan Blandford committed
243 244
struct _SortData
{
245
  GtkTreeModelSort *tree_model_sort;
246 247
  GtkTreeIterCompareFunc sort_func;
  gpointer sort_data;
Jonathan Blandford's avatar
Jonathan Blandford committed
248

249 250 251
  GtkTreePath *parent_path;
  gint parent_path_depth;
  gint *parent_path_indices;
252
};
253

254 255 256 257 258 259 260 261
/* Properties */
enum {
  PROP_0,
  /* Construct args */
  PROP_MODEL
};


262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287
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;
};

288 289 290 291 292 293 294
/* Set this to 0 to disable caching of child iterators.  This
 * allows for more stringent testing.  It is recommended to set this
 * to one when refactoring this code and running the unit tests to
 * catch more errors.
 */
#if 1
#  define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
295
	(((GtkTreeModelSort *)tree_model_sort)->priv->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
296 297 298 299
#else
#  define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) (FALSE)
#endif

300 301
#define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
#define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)
302
#define GET_ELT(siter) ((SortElt *) (siter ? g_sequence_get (siter) : NULL))
303

304

Matthias Clasen's avatar
Matthias Clasen committed
305
#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));
306

307 308
#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)

309
#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
310

311
/* general (object/interface init, etc) */
312 313
static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
314
static void gtk_tree_model_sort_drag_source_init      (GtkTreeDragSourceIface*iface);
315
static void gtk_tree_model_sort_finalize              (GObject               *object);
316 317 318 319 320 321 322 323
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);
324

325
/* our signal handlers */
326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
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);
346 347

/* TreeModel interface */
348
static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
349 350 351 352 353 354 355 356 357 358 359 360 361 362
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);
363 364
static gboolean     gtk_tree_model_sort_iter_previous      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380
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);
381 382 383
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
384 385 386
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

387 388 389 390 391 392 393 394 395
/* 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);

396
/* TreeSortable interface */
397 398 399 400 401 402 403 404 405 406
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,
407
							       GDestroyNotify          destroy);
408 409 410
static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
411
							       GDestroyNotify          destroy);
412
static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
413

414
/* Private functions (sort funcs, level handling and other utils) */
415 416
static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *parent_level,
417
                                                           SortElt          *parent_elt);
418
static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
419 420
							   SortLevel        *sort_level,
                                                           gboolean          unref);
421 422 423 424 425 426
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);
427
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
428
							   SortLevel        *level,
429 430
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
431 432 433 434
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);
435 436 437
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
438

439 440 441 442 443 444 445 446 447
static gint         gtk_tree_model_sort_compare_func        (gconstpointer     a,
                                                             gconstpointer     b,
                                                             gpointer          user_data);
static gint         gtk_tree_model_sort_offset_compare_func (gconstpointer     a,
                                                             gconstpointer     b,
                                                             gpointer          user_data);
static void         gtk_tree_model_sort_clear_cache_helper  (GtkTreeModelSort *tree_model_sort,
                                                             SortLevel        *level);

448

Matthias Clasen's avatar
Matthias Clasen committed
449 450 451 452 453 454
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
455
						gtk_tree_model_sort_drag_source_init))
456 457

static void
458 459
gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
{
460 461 462 463 464 465 466 467 468 469 470
  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;
471 472 473 474
}

static void
gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
475 476 477
{
  GObjectClass *object_class;

478
  object_class = (GObjectClass *) class;
479

480 481 482
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

483
  object_class->finalize = gtk_tree_model_sort_finalize;
484 485 486 487 488

  /* Properties */
  g_object_class_install_property (object_class,
                                   PROP_MODEL,
                                   g_param_spec_object ("model",
489 490
							P_("TreeModelSort Model"),
							P_("The model for the TreeModelSort to sort"),
491
							GTK_TYPE_TREE_MODEL,
492
							GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
493 494

  g_type_class_add_private (class, sizeof (GtkTreeModelSortPrivate));
495 496 497 498 499
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
500
  iface->get_flags = gtk_tree_model_sort_get_flags;
501 502 503 504 505 506
  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;
507
  iface->iter_previous = gtk_tree_model_sort_iter_previous;
508 509 510 511 512
  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;
513 514
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
515 516
}

517 518 519 520 521
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;
522
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
523 524
  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;
525 526
}

527 528 529 530 531 532 533 534
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;
}

535 536 537 538
/**
 * gtk_tree_model_sort_new_with_model:
 * @child_model: A #GtkTreeModel
 *
Matthias Clasen's avatar
Matthias Clasen committed
539
 * Creates a new #GtkTreeModel, with @child_model as the child model.
540
 *
541
 * Return value: (transfer full): A new #GtkTreeModel.
542
 */
543
GtkTreeModel *
544
gtk_tree_model_sort_new_with_model (GtkTreeModel *child_model)
545 546 547
{
  GtkTreeModel *retval;

548 549
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

Manish Singh's avatar
Manish Singh committed
550
  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
551

552
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
553 554 555 556

  return retval;
}

557 558 559
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
560
{
561
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
562
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
563

564 565
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

566
  if (priv->root)
567
    gtk_tree_model_sort_free_level (tree_model_sort, priv->root, TRUE);
568

569
  if (priv->sort_list)
570
    {
571 572
      _gtk_tree_data_list_header_free (priv->sort_list);
      priv->sort_list = NULL;
573
    }
574

575
  if (priv->default_sort_destroy)
576
    {
577 578 579
      priv->default_sort_destroy (priv->default_sort_data);
      priv->default_sort_destroy = NULL;
      priv->default_sort_data = NULL;
580 581 582
    }


583
  /* must chain up */
Matthias Clasen's avatar
Matthias Clasen committed
584
  G_OBJECT_CLASS (gtk_tree_model_sort_parent_class)->finalize (object);
585 586
}

587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616
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:
617
      g_value_set_object (value, gtk_tree_model_sort_get_model (tree_model_sort));
618 619 620 621 622 623 624
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 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 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740
/* helpers */
static SortElt *
sort_elt_new (void)
{
  return g_slice_new (SortElt);
}

static void
sort_elt_free (gpointer elt)
{
  g_slice_free (SortElt, elt);
}

static void
increase_offset_iter (gpointer data,
                      gpointer user_data)
{
  SortElt *elt = data;
  gint offset = GPOINTER_TO_INT (user_data);

  if (elt->offset >= offset)
    elt->offset++;
}

static void
decrease_offset_iter (gpointer data,
                      gpointer user_data)
{
  SortElt *elt = data;
  gint offset = GPOINTER_TO_INT (user_data);

  if (elt->offset > offset)
    elt->offset--;
}

static void
fill_sort_data (SortData         *data,
                GtkTreeModelSort *tree_model_sort,
                SortLevel        *level)
{
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;

  data->tree_model_sort = tree_model_sort;

  if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
    {
      GtkTreeDataSortHeader *header;
      
      header = _gtk_tree_data_list_get_header (priv->sort_list,
					       priv->sort_column_id);
      
      g_return_if_fail (header != NULL);
      g_return_if_fail (header->func != NULL);
      
      data->sort_func = header->func;
      data->sort_data = header->data;
    }
  else
    {
      /* absolutely SHOULD NOT happen: */
      g_return_if_fail (priv->default_sort_func != NULL);

      data->sort_func = priv->default_sort_func;
      data->sort_data = priv->default_sort_data;
    }

  if (level->parent_elt)
    {
      data->parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
                                                            level->parent_elt);
      gtk_tree_path_append_index (data->parent_path, 0);
    }
  else
    {
      data->parent_path = gtk_tree_path_new_first ();
    }
  data->parent_path_depth = gtk_tree_path_get_depth (data->parent_path);
  data->parent_path_indices = gtk_tree_path_get_indices (data->parent_path);
}

static void
free_sort_data (SortData *data)
{
  gtk_tree_path_free (data->parent_path);
}

static SortElt *
lookup_elt_with_offset (GtkTreeModelSort *tree_model_sort,
                        SortLevel        *level,
                        gint              offset,
                        GSequenceIter   **ret_siter)
{
  GSequenceIter *siter, *end_siter;

  /* FIXME: We have to do a search like this, because the sequence is not
   * (always) sorted on offset order.  Perhaps we should introduce a
   * second sequence which is sorted on offset order.
   */
  end_siter = g_sequence_get_end_iter (level->seq);
  for (siter = g_sequence_get_begin_iter (level->seq);
       siter != end_siter;
       siter = g_sequence_iter_next (siter))
    {
      SortElt *elt = g_sequence_get (siter);

      if (elt->offset == offset)
        break;
    }

  if (ret_siter)
    *ret_siter = siter;

  return GET_ELT (siter);
}


741
static void
742
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
743 744
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
745
				 gpointer      data)
746 747
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
748
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
749
  GtkTreePath *path = NULL;
750
  GtkTreeIter iter;
751
  GtkTreeIter tmpiter;
752

753 754
  SortElt *elt;
  SortLevel *level;
755
  SortData sort_data;
756

757 758
  gboolean free_s_path = FALSE;

759
  gint index = 0, old_index;
760 761

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

763
  if (!start_s_path)
764 765
    {
      free_s_path = TRUE;
766
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
767
    }
768

769 770 771
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
772
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
773 774
    {
      if (free_s_path)
775
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
776 777
      return;
    }
Jonathan Blandford's avatar
Jonathan Blandford committed
778

779
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
780
  gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (data), &iter);
781

782 783
  level = iter.user_data;
  elt = iter.user_data2;
784

785
  if (g_sequence_get_length (level->seq) < 2 ||
786 787
      (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
       priv->default_sort_func == NO_SORT_FUNC))
788 789
    {
      if (free_s_path)
790
	gtk_tree_path_free (start_s_path);
791

792
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
793
      gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
794

795
      gtk_tree_path_free (path);
796

797 798
      return;
    }
799

800
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
801
    tmpiter = elt->iter;
802
  else
803 804
    gtk_tree_model_get_iter (priv->child_model,
                             &tmpiter, start_s_path);
805

806 807 808 809 810 811 812
  old_index = g_sequence_iter_get_position (elt->siter);

  fill_sort_data (&sort_data, tree_model_sort, level);
  g_sequence_sort_changed (elt->siter,
                           gtk_tree_model_sort_compare_func,
                           &sort_data);
  free_sort_data (&sort_data);
813

814
  index = g_sequence_iter_get_position (elt->siter);
815

816
  /* Prepare the path for signal emission */
817 818
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
819

820
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
821

822 823 824 825 826 827 828 829
  /* if the item moved, then emit rows_reordered */
  if (old_index != index)
    {
      gint *new_order;
      gint j;

      GtkTreePath *tmppath;

830
      new_order = g_new (gint, g_sequence_get_length (level->seq));
831

832
      for (j = 0; j < g_sequence_get_length (level->seq); j++)
833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854
        {
	  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 */
	}

855
      if (level->parent_elt)
856
        {
857
	  iter.stamp = priv->stamp;
858
	  iter.user_data = level->parent_level;
859
	  iter.user_data2 = level->parent_elt;
860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880

	  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);
881
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
882
  gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);
883

884 885
  gtk_tree_path_free (path);
  if (free_s_path)
886
    gtk_tree_path_free (start_s_path);
887 888
}

889 890 891 892 893
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
894
{
895
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
896
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
897
  GtkTreePath *path;
898
  GtkTreeIter iter;
899 900 901 902 903 904 905 906 907 908
  GtkTreeIter real_s_iter;

  gint i = 0;

  gboolean free_s_path = FALSE;

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

909
  parent_level = level = SORT_LEVEL (priv->root);
910

911
  g_return_if_fail (s_path != NULL || s_iter != NULL);
912

913
  if (!s_path)
914
    {
915 916
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
917
    }
918

919 920
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
921
  else
922
    real_s_iter = *s_iter;
923

924
  if (!priv->root)
925
    {
926
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
927

928 929
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
930

931
      goto done_and_submit;
932
    }
933

934 935 936 937 938 939 940 941
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
942

943
      if (g_sequence_get_length (level->seq) < gtk_tree_path_get_indices (s_path)[i])
944
	{
945
	  g_warning ("%s: A node was inserted with a parent that's not in the tree.\n"
946
		     "This possibly means that a GtkTreeModel inserted a child node\n"
947 948
		     "before the parent was inserted.",
		     G_STRLOC);
949 950
	  goto done;
	}
951

952 953 954
      elt = lookup_elt_with_offset (tree_model_sort, level,
                                    gtk_tree_path_get_indices (s_path)[i],
                                    NULL);
955 956

      g_return_if_fail (elt != NULL);
957 958 959 960 961 962 963 964 965 966 967

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

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

969
  if (!parent_level)
970
    goto done;
971

972
  if (level->ref_count == 0 && level != priv->root)
973
    {
974
      gtk_tree_model_sort_free_level (tree_model_sort, level, TRUE);
975 976 977
      goto done;
    }

978 979 980 981 982
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
983

984
 done_and_submit:
985 986 987
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
988

989
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
990
    return;
991

992
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
993

994
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
995
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
996
  gtk_tree_path_free (path);
997

998
 done:
999 1000
  if (free_s_path)
    gtk_tree_path_free (s_path);
1001

1002
  return;
1003 1004 1005
}

static void
1006 1007 1008 1009
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
1010 1011
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1012 1013
  GtkTreePath *path;
  GtkTreeIter iter;
1014

1015
  g_return_if_fail (s_path != NULL && s_iter != NULL);
1016

1017 1018
  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
1019
    return;
1020

1021
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
1022
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
1023

1024
  gtk_tree_path_free (path);
1025 1026 1027
}

static void
1028 1029 1030
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
1031 1032
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1033
  GtkTreePath *path = NULL;
1034 1035 1036 1037
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
1038

1039
  g_return_if_fail (s_path != NULL);
1040

1041 1042
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
1043 1044
    return;

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

1047 1048 1049 1050
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

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

1053
  while (elt->ref_count > 0)
1054
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
1055

1056 1057 1058 1059 1060 1061 1062 1063
  /* If this node has children, we free the level (recursively) here
   * and specify that unref may not be used, because parent and its
   * children have been removed by now.
   */
  if (elt->children)
    gtk_tree_model_sort_free_level (tree_model_sort,
                                    elt->children, FALSE);

1064
  if (level->ref_count == 0)
1065
    {
1066
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
1067
      gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
1068
      gtk_tree_path_free (path);
1069

1070
      if (level == tree_model_sort->priv->root)
1071
	{
1072 1073 1074
	  gtk_tree_model_sort_free_level (tree_model_sort,
					  tree_model_sort->priv->root,
                                          TRUE);
1075
	  tree_model_sort->priv->root = NULL;
1076
	}
1077 1078
      return;
    }
1079

1080 1081
  g_sequence_remove (elt->siter);
  elt = NULL;
1082

1083 1084 1085 1086 1087
  /* The sequence is not ordered on offset, so we traverse the entire
   * sequence.
   */
  g_sequence_foreach (level->seq, decrease_offset_iter,
                      GINT_TO_POINTER (offset));
1088

1089 1090 1091
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

1092
  gtk_tree_path_free (path);
1093 1094
}

1095
static void
1096 1097 1098 1099 1100
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
1101
{
1102 1103
  SortElt *elt;
  SortLevel *level;
1104 1105
  GtkTreeIter iter;
  gint *tmp_array;
1106
  int i, length;
1107
  GtkTreePath *path;
1108
  GSequenceIter *siter, *end_siter;
1109
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
1110
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1111

1112
  g_return_if_fail (new_order != NULL);
1113

Matthias Clasen's avatar
Matthias Clasen committed
1114
  if (s_path == NULL || gtk_tree_path_get_depth (s_path) == 0)
1115
    {
1116
      if (priv->root == NULL)
Jonathan Blandford's avatar
Jonathan Blandford committed
1117
	return;
1118
      path = gtk_tree_path_new ();
1119
      level = SORT_LEVEL (priv->root);
1120 1121
    }
  else
1122
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
1123 1124 1125 1126
      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);
1127

1128
      elt = SORT_ELT (iter.user_data2);
1129 1130

      if (!elt->children)
1131 1132 1133 1134
	{
	  gtk_tree_path_free (path);
	  return;
	}
1135

1136 1137 1138
      level = elt->children;
    }

1139 1140
  length = g_sequence_get_length (level->seq);
  if (length < 2)
1141
    {
1142 1143 1144
      gtk_tree_path_free (path);
      return;
    }
1145

1146 1147 1148 1149 1150 1151 1152 1153 1154 1155
  tmp_array = g_new (int, length);

  /* FIXME: I need to think about whether this can be done in a more
   * efficient way?
   */
  i = 0;
  end_siter = g_sequence_get_end_iter (level->seq);
  for (siter = g_sequence_get_begin_iter (level->seq);
       siter != end_siter;
       siter = g_sequence_iter_next (siter))
1156
    {
1157 1158 1159 1160
      gint j;
      SortElt *elt = g_sequence_get (siter);

      for (j = 0; j < length; j++)
1161
	{
1162
	  if (elt->offset == new_order[j])
1163 1164
	    tmp_array[i] = j;
	}
1165 1166

      i++;
1167 1168
    }

1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182
  /* This loop cannot be merged with the above loop nest, because that
   * would introduce duplicate offsets.
   */
  i = 0;
  end_siter = g_sequence_get_end_iter (level->seq);
  for (siter = g_sequence_get_begin_iter (level->seq);
       siter != end_siter;
       siter = g_sequence_iter_next (siter))
    {
      SortElt *elt = g_sequence_get (siter);

      elt->offset = tmp_array[i];
      i++;
    }
1183
  g_free (tmp_array);
1184

1185 1186
  if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
      priv->default_sort_func == NO_SORT_FUNC)
1187
    {
1188 1189
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
1190
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
1191

1192
      if (gtk_tree_path_get_depth (path))
1193
	{
1194 1195 1196 1197 1198
	  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);
1199
	}
1200
      else
1201 1202 1203 1204
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
1205 1206
    }

1207
  gtk_tree_path_free (path);
1208 1209 1210
}

/* Fulfill our model requirements */
1211
static GtkTreeModelFlags
1212 1213
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
Matthias Clasen's avatar
Matthias Clasen committed
1214
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1215 1216
  GtkTreeModelFlags flags;

1217
  g_return_val_if_fail (tree_model_sort->priv->child_model != NULL, 0);
1218

1219
  flags = gtk_tree_model_get_flags (tree_model_sort->priv->child_model);
1220 1221 1222

  if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
    return GTK_TREE_MODEL_LIST_ONLY;
1223 1224

  return 0;
1225 1226
}

1227 1228 1229
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
1230 1231
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

1232
  if (tree_model_sort->priv->child_model == 0)
1233
    return 0;
1234

1235
  return gtk_tree_model_get_n_columns (tree_model_sort->priv->child_model);
1236 1237 1238 1239
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
1240
                                     gint          index)
1241
{
Matthias Clasen's avatar
Matthias Clasen committed
1242
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1243

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

1246
  return gtk_tree_model_get_column_type (tree_model_sort->priv->child_model, index);
1247 1248 1249
}

static gboolean
1250 1251 1252
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
1253
{
Matthias Clasen's avatar
Matthias Clasen committed
1254
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1255
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1256
  gint *indices;
1257
  SortElt *elt;
1258 1259
  SortLevel *level;
  gint depth, i;
1260
  GSequenceIter *siter;
1261

1262
  g_return_val_if_fail (priv->child_model != NULL, FALSE);
1263

1264 1265
  indices = gtk_tree_path_get_indices (path);

1266
  if (priv->root == NULL)
1267
    gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
1268
  level = SORT_LEVEL (priv->root);
1269 1270 1271

  depth = gtk_tree_path_get_depth (path);
  if (depth == 0)
1272 1273 1274 1275
    {
      iter->stamp = 0;
      return FALSE;
    }
1276

1277
  for (i = 0; i < depth - 1; i++)
1278
    {
1279
      if ((level == NULL) ||
1280
	  (indices[i] >= g_sequence_get_length (level->seq)))
1281 1282 1283 1284
        {
          iter->stamp = 0;
          return FALSE;
        }
1285

1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297
      siter = g_sequence_get_iter_at_pos (level->seq, indices[i]);
      if (g_sequence_iter_is_end (siter))
        {
          iter->stamp = 0;
          return FALSE;
        }

      elt = GET_ELT (siter);
      if (elt->children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, level, elt);

      level = elt->children;
1298 1299
    }

1300
  if (!level || indices[i] >= g_sequence_get_length (level->seq))
1301 1302 1303 1304 1305
    {
      iter->stamp = 0;
      return FALSE;
    }

1306
  iter->stamp = priv->stamp;
1307
  iter->user_data = level;
1308 1309 1310 1311 1312 1313 1314 1315

  siter = g_sequence_get_iter_at_pos (level->seq, indices[depth - 1]);
  if (g_sequence_iter_is_end (siter))
    {
      iter->stamp = 0;
      return FALSE;
    }
  iter->user_data2 = GET_ELT (siter);
1316

1317
  return TRUE;
1318 1319 1320 1321
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1322
			      GtkTreeIter  *iter)
1323
{
Matthias Clasen's avatar
Matthias Clasen committed
1324
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1325
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1326 1327
  GtkTreePath *retval;
  SortLevel *level;
1328
  SortElt *elt;
1329

1330 1331
  g_return_val_if_fail (priv->child_model != NULL, NULL);
  g_return_val_if_fail (priv->stamp == iter->stamp, NULL);
1332

1333
  retval = gtk_tree_path_new ();
1334 1335

  level = SORT_LEVEL (iter->user_data);
1336
  elt = SORT_ELT (iter->user_data2);
1337 1338

  while (level)
1339
    {
1340 1341 1342 1343
      gint index;

      index = g_sequence_iter_get_position (elt->siter);
      gtk_tree_path_prepend_index (retval, index);
1344

1345
      elt = level->parent_elt;
1346
      level = level->parent_level;
1347
    }
1348 1349

  return retval;
1350 1351 1352 1353
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1354 1355 1356
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
1357
{
Matthias Clasen's avatar
Matthias Clasen committed
1358
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1359
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1360
  GtkTreeIter child_iter;
1361

1362
  g_return_if_fail (priv->child_model != NULL);
Matthias Clasen's avatar
Matthias Clasen committed
1363
  g_return_if_fail (VALID_ITER (iter, tree_model_sort));
1364

Matthias Clasen's avatar
Matthias Clasen committed
1365
  GET_CHILD_ITER (tree_model_sort, &child_iter, iter);
1366
  gtk_tree_model_get_value (priv->child_model,
1367
			    &child_iter, column, value);
1368 1369 1370 1371
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1372
			       GtkTreeIter  *iter)
1373
{
Matthias Clasen's avatar
Matthias Clasen committed
1374
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1375
  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
1376
  SortElt *elt;
1377
  GSequenceIter *siter;
1378

1379 1380
  g_return_val_if_fail (priv->child_model != NULL, FALSE);
  g_return_val_if_fail (priv->stamp == iter->stamp, FALSE);
1381

1382
  elt = iter->user_data2;
1383

1384 1385
  siter = g_sequence_iter_next (elt->siter);
  if (g_sequence_iter_is_end (siter))
1386 1387 1388 <