/* gtktreemodelsort.c

 * Copyright (C) 2000,2001  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>

 * Copyright (C) 2001,2002  Kristian Rietveld <kris@gtk.org>

 *

 * 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.

 */

/* NOTE: There is a potential for confusion in this code as to whether an iter,

 * 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

 * s_ prefix before them (ie. s_iter, s_value, s_path);

 */

/* ITER FORMAT:

 *

 * iter->stamp = tree_model_sort->stamp

 * iter->user_data = SortLevel

 * iter->user_data2 = SortElt

 */

/* 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.

 */

#include "config.h"

#include <string.h>

#include "gtktreemodelsort.h"

#include "gtktreesortable.h"

#include "gtktreestore.h"

#include "gtktreedatalist.h"

#include "gtkintl.h"

#include "gtkprivate.h"

#include "gtktreednd.h"

#include "gtkalias.h"

typedef struct _SortElt SortElt;

typedef struct _SortLevel SortLevel;

typedef struct _SortData SortData;

typedef struct _SortTuple SortTuple;

struct _SortElt

{

  GtkTreeIter  iter;

  SortLevel   *children;

  gint         offset;

  gint         ref_count;

  gint         zero_ref_count;

};

struct _SortLevel

{

  GArray    *array;

  gint       ref_count;

  gint       parent_elt_index;

  SortLevel *parent_level;

};

struct _SortData

{

  GtkTreeModelSort *tree_model_sort;

  GtkTreePath *parent_path;

  gint parent_path_depth;

  gint *parent_path_indices;

  GtkTreeIterCompareFunc sort_func;

  gpointer sort_data;

};

struct _SortTuple

{

  SortElt   *elt;

  gint       offset;

};

/* Properties */

enum {

  PROP_0,

  /* Construct args */

  PROP_MODEL

};

#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 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))

#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));

#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)

#define VALID_ITER(iter, tree_model_sort) ((iter) != NULL && (iter)->user_data != NULL && (iter)->user_data2 != NULL && (tree_model_sort)->stamp == (iter)->stamp)

/* general (object/interface init, etc) */

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_drag_source_init      (GtkTreeDragSourceIface*iface);

static void gtk_tree_model_sort_finalize              (GObject               *object);

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);

/* our signal handlers */

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);

/* TreeModel interface */

static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);

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_real_unref_node    (GtkTreeModel          *tree_model,

                                                            GtkTreeIter           *iter,

							    gboolean               propagate_unref);

static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,

                                                            GtkTreeIter           *iter);

/* 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);

/* TreeSortable interface */

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,

							       GDestroyNotify          destroy);

static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,

							       GtkTreeIterCompareFunc  func,

							       gpointer                data,

							       GDestroyNotify          destroy);

static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);

/* Private functions (sort funcs, level handling and other utils) */

static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,

							   SortLevel        *parent_level,

							   gint              parent_elt_index);

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);

static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,

							   SortLevel        *level,

							   GtkTreeIter      *iter,

							   gint             skip_index);

static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,

							   SortLevel        *level,

							   GtkTreePath      *s_path,

							   GtkTreeIter      *s_iter);

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);

static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,

									 GtkTreePath      *child_path,

									 gboolean          build_levels);

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,

						gtk_tree_model_sort_drag_source_init))

static void

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)

{

  GObjectClass *object_class;

  object_class = (GObjectClass *) class;

  object_class->set_property = gtk_tree_model_sort_set_property;

  object_class->get_property = gtk_tree_model_sort_get_property;

  object_class->finalize = gtk_tree_model_sort_finalize;

  /* Properties */

  g_object_class_install_property (object_class,

                                   PROP_MODEL,

                                   g_param_spec_object ("model",

							P_("TreeModelSort Model"),

							P_("The model for the TreeModelSort to sort"),

							GTK_TYPE_TREE_MODEL,

							GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));

}

static void

gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)

{

  iface->get_flags = gtk_tree_model_sort_get_flags;

  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;

  iface->ref_node = gtk_tree_model_sort_ref_node;

  iface->unref_node = gtk_tree_model_sort_unref_node;

}

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;

  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;

  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;

}

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;

}

/**

 * gtk_tree_model_sort_new_with_model:

 * @child_model: A #GtkTreeModel

 *

 * Creates a new #GtkTreeModel, with @child_model as the child model.

 *

 * Return value: (transfer full): A new #GtkTreeModel.

 */

GtkTreeModel *

gtk_tree_model_sort_new_with_model (GtkTreeModel *child_model)

{

  GtkTreeModel *retval;

  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);

  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);

  return retval;

}

/* GObject callbacks */

static void

gtk_tree_model_sort_finalize (GObject *object)

{

  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;

  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

  if (tree_model_sort->root)

    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);

  if (tree_model_sort->sort_list)

    {

      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);

      tree_model_sort->sort_list = NULL;

    }

  if (tree_model_sort->default_sort_destroy)

    {

      tree_model_sort->default_sort_destroy (tree_model_sort->default_sort_data);

      tree_model_sort->default_sort_destroy = NULL;

      tree_model_sort->default_sort_data = NULL;

    }

  /* must chain up */

  G_OBJECT_CLASS (gtk_tree_model_sort_parent_class)->finalize (object);

}

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;

    }

}

static void

gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,

				 GtkTreePath  *start_s_path,

				 GtkTreeIter  *start_s_iter,

				 gpointer      data)

{

  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);

  GtkTreePath *path = NULL;

  GtkTreeIter iter;

  GtkTreeIter tmpiter;

  SortElt tmp;

  SortElt *elt;

  SortLevel *level;

  gboolean free_s_path = FALSE;

  gint index = 0, old_index, i;

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

  if (!start_s_path)

    {

      free_s_path = TRUE;

      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);

    }

  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,

							      start_s_path,

							      FALSE);

  if (!path)

    {

      if (free_s_path)

	gtk_tree_path_free (start_s_path);

      return;

    }

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

  gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (data), &iter);

  level = iter.user_data;

  elt = iter.user_data2;

  if (level->array->len < 2 ||

      (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&

       tree_model_sort->default_sort_func == NO_SORT_FUNC))

    {

      if (free_s_path)

	gtk_tree_path_free (start_s_path);

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

      gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);

      gtk_tree_path_free (path);

      return;

    }

  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))

    {

      gtk_tree_model_get_iter (tree_model_sort->child_model,

			       &tmpiter, start_s_path);

    }

  old_index = elt - SORT_ELT (level->array->data);

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

  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))

    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,

						   level,

						   &tmp.iter,

						   old_index);

  else

    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,

						   level,

						   &tmpiter,

						   old_index);

  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));

  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_index = i;

  gtk_tree_path_up (path);

  gtk_tree_path_append_index (path, index);

  gtk_tree_model_sort_increment_stamp (tree_model_sort);

  /* 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 */

	}

      if (level->parent_elt_index >= 0)

        {

	  iter.stamp = tree_model_sort->stamp;

	  iter.user_data = level->parent_level;

	  iter.user_data2 = SORT_LEVEL_PARENT_ELT (level);

	  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);

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

  gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (data), &iter);

  gtk_tree_path_free (path);

  if (free_s_path)

    gtk_tree_path_free (start_s_path);

}

static void

gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,

				  GtkTreePath           *s_path,

				  GtkTreeIter           *s_iter,

				  gpointer               data)

{

  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);

  GtkTreePath *path;

  GtkTreeIter iter;

  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);

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

  if (!s_path)

    {

      s_path = gtk_tree_model_get_path (s_model, s_iter);

      free_s_path = TRUE;

    }

  if (!s_iter)

    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);

  else

    real_s_iter = *s_iter;

  if (!tree_model_sort->root)

    {

      gtk_tree_model_sort_build_level (tree_model_sort, NULL, -1);

      /* the build level already put the inserted iter in the level,

	 so no need to handle this signal anymore */

      goto done_and_submit;

    }

  /* find the parent level */

  while (i < gtk_tree_path_get_depth (s_path) - 1)

    {

      gint j;

      if (!level)

	{

	  /* level not yet build, we won't cover this signal */

	  goto done;

	}

      if (level->array->len < gtk_tree_path_get_indices (s_path)[i])

	{

	  g_warning ("%s: 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.",

		     G_STRLOC);

	  goto done;

	}

      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);

      if (!elt->children)

	{

	  /* not covering this signal */

	  goto done;

	}

      level = elt->children;

      parent_level = level;

      i++;

    }

  if (!parent_level)

    goto done;

  if (level->ref_count == 0 && level != tree_model_sort->root)

    {

      gtk_tree_model_sort_free_level (tree_model_sort, level);

      goto done;

    }

  if (!gtk_tree_model_sort_insert_value (tree_model_sort,

					 parent_level,

					 s_path,

					 &real_s_iter))

    goto done;

 done_and_submit:

  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,

							      s_path,

							      FALSE);

  if (!path)

    return;

  gtk_tree_model_sort_increment_stamp (tree_model_sort);

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

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

  gtk_tree_path_free (path);

 done:

  if (free_s_path)

    gtk_tree_path_free (s_path);

  return;

}

static void

gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,

					   GtkTreePath  *s_path,

					   GtkTreeIter  *s_iter,

					   gpointer      data)

{

  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);

  GtkTreePath *path;

  GtkTreeIter iter;

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

  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);

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

  gtk_tree_path_free (path);

}

static void

gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,

				 GtkTreePath  *s_path,

				 gpointer      data)

{

  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);

  GtkTreePath *path = NULL;

  SortElt *elt;

  SortLevel *level;

  GtkTreeIter iter;

  gint offset;

  gint i;

  g_return_if_fail (s_path != NULL);

  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);

  level = SORT_LEVEL (iter.user_data);

  elt = SORT_ELT (iter.user_data2);

  offset = elt->offset;

  /* 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);

  while (elt->ref_count > 0)

    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);

  if (level->ref_count == 0)

    {

      /* 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.

       */

      gtk_tree_model_sort_increment_stamp (tree_model_sort);

      gtk_tree_path_free (path);

      if (level == tree_model_sort->root)

	{

	  gtk_tree_model_sort_free_level (tree_model_sort, 

					  tree_model_sort->root);

	  tree_model_sort->root = NULL;

	}

      return;

    }

  gtk_tree_model_sort_increment_stamp (tree_model_sort);

  /* 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);

  /* 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--;

      if (elt->children)

	elt->children->parent_elt_index = i;

    }

  gtk_tree_path_free (path);

}

static void

gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,

				    GtkTreePath  *s_path,

				    GtkTreeIter  *s_iter,

				    gint         *new_order,

				    gpointer      data)

{

  SortElt *elt;

  SortLevel *level;

  GtkTreeIter iter;

  gint *tmp_array;

  int i, j;

  GtkTreePath *path;

  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);

  g_return_if_fail (new_order != NULL);

  if (s_path == NULL || gtk_tree_path_get_depth (s_path) == 0)

    {

      if (tree_model_sort->root == NULL)

	return;

      path = gtk_tree_path_new ();

      level = SORT_LEVEL (tree_model_sort->root);

    }

  else

    {

      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);

      level = SORT_LEVEL (iter.user_data);

      elt = SORT_ELT (iter.user_data2);

      if (!elt->children)

	{

	  gtk_tree_path_free (path);

	  return;

	}

      level = elt->children;

    }

  if (level->array->len < 2)

    {

      gtk_tree_path_free (path);

      return;

    }

  tmp_array = g_new (int, level->array->len);

  for (i = 0; i < level->array->len; i++)

    {

      for (j = 0; j < level->array->len; j++)

	{

	  if (g_array_index (level->array, SortElt, i).offset == new_order[j])

	    tmp_array[i] = j;

	}

    }

  for (i = 0; i < level->array->len; i++)

    g_array_index (level->array, SortElt, i).offset = tmp_array[i];

  g_free (tmp_array);

  if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&

      tree_model_sort->default_sort_func == NO_SORT_FUNC)

    {

      gtk_tree_model_sort_sort_level (tree_model_sort, level,

				      FALSE, FALSE);

      gtk_tree_model_sort_increment_stamp (tree_model_sort);

      if (gtk_tree_path_get_depth (path))

	{

	  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);

	}

      else

	{

	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),

					 path, NULL, new_order);