/* gtktreemodelfilter.c

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

 * Copyright (C) 2001-2003  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.

 */

#include "config.h"

#include "gtktreemodelfilter.h"

#include "gtkintl.h"

#include "gtktreednd.h"

#include "gtkprivate.h"

#include "gtkalias.h"

#include <string.h>

/* ITER FORMAT:

 *

 * iter->stamp = filter->priv->stamp

 * iter->user_data = FilterLevel

 * iter->user_data2 = FilterElt

 */

/* all paths, iters, etc prefixed with c_ are paths, iters, etc relative to the

 * child model.

 */

/* A few notes:

 *  There are three model/views involved, so there are two mappings:

 *    * this model -> child model: mapped via offset in FilterElt.

 *    * this model -> parent model (or view): mapped via the array index

 *                                            of FilterElt.

 *

 *  Note that there are two kinds of paths relative to the filter model

 *  (those generated from the array indices): paths taking non-visible

 *  nodes into account, and paths which don't.  Paths which take

 *  non-visible nodes into account should only be used internally and

 *  NEVER be passed along with a signal emission.

 *

 *  The filter model has a reference on every node that is not in the root

 *  level and has a parent with ref_count > 1.  Exception is a virtual root

 *  level; all nodes in the virtual root level are referenced too.

 */

typedef struct _FilterElt FilterElt;

typedef struct _FilterLevel FilterLevel;

struct _FilterElt

{

  GtkTreeIter iter;

  FilterLevel *children;

  gint offset;

  gint ref_count;

  gint zero_ref_count;

  gboolean visible;

};

struct _FilterLevel

{

  GArray *array;

  gint ref_count;

  gint visible_nodes;

  gint parent_elt_index;

  FilterLevel *parent_level;

};

#define GTK_TREE_MODEL_FILTER_GET_PRIVATE(obj)  (G_TYPE_INSTANCE_GET_PRIVATE ((obj), GTK_TYPE_TREE_MODEL_FILTER, GtkTreeModelFilterPrivate))

struct _GtkTreeModelFilterPrivate

{

  gpointer root;

  gint stamp;

  guint child_flags;

  GtkTreeModel *child_model;

  gint zero_ref_count;

  GtkTreePath *virtual_root;

  GtkTreeModelFilterVisibleFunc visible_func;

  gpointer visible_data;

  GDestroyNotify visible_destroy;

  gint modify_n_columns;

  GType *modify_types;

  GtkTreeModelFilterModifyFunc modify_func;

  gpointer modify_data;

  GDestroyNotify modify_destroy;

  gint visible_column;

  gboolean visible_method_set;

  gboolean modify_func_set;

  gboolean in_row_deleted;

  gboolean virtual_root_deleted;

  /* signal ids */

  guint changed_id;

  guint inserted_id;

  guint has_child_toggled_id;

  guint deleted_id;

  guint reordered_id;

};

/* properties */

enum

{

  PROP_0,

  PROP_CHILD_MODEL,

  PROP_VIRTUAL_ROOT

};

#define GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS(filter) \

        (((GtkTreeModelFilter *)filter)->priv->child_flags & GTK_TREE_MODEL_ITERS_PERSIST)

#define FILTER_ELT(filter_elt) ((FilterElt *)filter_elt)

#define FILTER_LEVEL(filter_level) ((FilterLevel *)filter_level)

#define FILTER_LEVEL_PARENT_ELT(level) (&g_array_index (FILTER_LEVEL ((level))->parent_level->array, FilterElt, FILTER_LEVEL ((level))->parent_elt_index))

#define FILTER_LEVEL_ELT_INDEX(level, elt) (FILTER_ELT ((elt)) - FILTER_ELT (FILTER_LEVEL ((level))->array->data))

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

static void         gtk_tree_model_filter_tree_model_init                 (GtkTreeModelIface       *iface);

static void         gtk_tree_model_filter_drag_source_init                (GtkTreeDragSourceIface  *iface);

static void         gtk_tree_model_filter_finalize                        (GObject                 *object);

static void         gtk_tree_model_filter_set_property                    (GObject                 *object,

                                                                           guint                    prop_id,

                                                                           const GValue            *value,

                                                                           GParamSpec              *pspec);

static void         gtk_tree_model_filter_get_property                    (GObject                 *object,

                                                                           guint                    prop_id,

                                                                           GValue                 *value,

                                                                           GParamSpec             *pspec);

/* signal handlers */

static void         gtk_tree_model_filter_row_changed                     (GtkTreeModel           *c_model,

                                                                           GtkTreePath            *c_path,

                                                                           GtkTreeIter            *c_iter,

                                                                           gpointer                data);

static void         gtk_tree_model_filter_row_inserted                    (GtkTreeModel           *c_model,

                                                                           GtkTreePath            *c_path,

                                                                           GtkTreeIter            *c_iter,

                                                                           gpointer                data);

static void         gtk_tree_model_filter_row_has_child_toggled           (GtkTreeModel           *c_model,

                                                                           GtkTreePath            *c_path,

                                                                           GtkTreeIter            *c_iter,

                                                                           gpointer                data);

static void         gtk_tree_model_filter_row_deleted                     (GtkTreeModel           *c_model,

                                                                           GtkTreePath            *c_path,

                                                                           gpointer                data);

static void         gtk_tree_model_filter_rows_reordered                  (GtkTreeModel           *c_model,

                                                                           GtkTreePath            *c_path,

                                                                           GtkTreeIter            *c_iter,

                                                                           gint                   *new_order,

                                                                           gpointer                data);

/* GtkTreeModel interface */

static GtkTreeModelFlags gtk_tree_model_filter_get_flags                       (GtkTreeModel           *model);

static gint         gtk_tree_model_filter_get_n_columns                   (GtkTreeModel           *model);

static GType        gtk_tree_model_filter_get_column_type                 (GtkTreeModel           *model,

                                                                           gint                    index);

static gboolean     gtk_tree_model_filter_get_iter_full                   (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter,

                                                                           GtkTreePath            *path);

static gboolean     gtk_tree_model_filter_get_iter                        (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter,

                                                                           GtkTreePath            *path);

static GtkTreePath *gtk_tree_model_filter_get_path                        (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter);

static void         gtk_tree_model_filter_get_value                       (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter,

                                                                           gint                    column,

                                                                           GValue                 *value);

static gboolean     gtk_tree_model_filter_iter_next                       (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter);

static gboolean     gtk_tree_model_filter_iter_children                   (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter,

                                                                           GtkTreeIter            *parent);

static gboolean     gtk_tree_model_filter_iter_has_child                  (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter);

static gint         gtk_tree_model_filter_iter_n_children                 (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter);

static gboolean     gtk_tree_model_filter_iter_nth_child                  (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter,

                                                                           GtkTreeIter            *parent,

                                                                           gint                    n);

static gboolean     gtk_tree_model_filter_iter_parent                     (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter,

                                                                           GtkTreeIter            *child);

static void         gtk_tree_model_filter_ref_node                        (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter);

static void         gtk_tree_model_filter_unref_node                      (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter);

/* TreeDragSource interface */

static gboolean    gtk_tree_model_filter_row_draggable                    (GtkTreeDragSource      *drag_source,

                                                                           GtkTreePath            *path);

static gboolean    gtk_tree_model_filter_drag_data_get                    (GtkTreeDragSource      *drag_source,

                                                                           GtkTreePath            *path,

                                                                           GtkSelectionData       *selection_data);

static gboolean    gtk_tree_model_filter_drag_data_delete                 (GtkTreeDragSource      *drag_source,

                                                                           GtkTreePath            *path);

/* private functions */

static void        gtk_tree_model_filter_build_level                      (GtkTreeModelFilter     *filter,

                                                                           FilterLevel            *parent_level,

                                                                           gint                    parent_elt_index,

                                                                           gboolean                emit_inserted);

static void        gtk_tree_model_filter_free_level                       (GtkTreeModelFilter     *filter,

                                                                           FilterLevel            *filter_level);

static GtkTreePath *gtk_tree_model_filter_elt_get_path                    (FilterLevel            *level,

                                                                           FilterElt              *elt,

                                                                           GtkTreePath            *root);

static GtkTreePath *gtk_tree_model_filter_add_root                        (GtkTreePath            *src,

                                                                           GtkTreePath            *root);

static GtkTreePath *gtk_tree_model_filter_remove_root                     (GtkTreePath            *src,

                                                                           GtkTreePath            *root);

static void         gtk_tree_model_filter_increment_stamp                 (GtkTreeModelFilter     *filter);

static gboolean     gtk_tree_model_filter_visible                         (GtkTreeModelFilter     *filter,

                                                                           GtkTreeIter            *child_iter);

static void         gtk_tree_model_filter_clear_cache_helper              (GtkTreeModelFilter     *filter,

                                                                           FilterLevel            *level);

static void         gtk_tree_model_filter_real_unref_node                 (GtkTreeModel           *model,

                                                                           GtkTreeIter            *iter,

                                                                           gboolean                propagate_unref);

static void         gtk_tree_model_filter_set_model                       (GtkTreeModelFilter     *filter,

                                                                           GtkTreeModel           *child_model);

static void         gtk_tree_model_filter_ref_path                        (GtkTreeModelFilter     *filter,

                                                                           GtkTreePath            *path);

static void         gtk_tree_model_filter_unref_path                      (GtkTreeModelFilter     *filter,

                                                                           GtkTreePath            *path);

static void         gtk_tree_model_filter_set_root                        (GtkTreeModelFilter     *filter,

                                                                           GtkTreePath            *root);

static GtkTreePath *gtk_real_tree_model_filter_convert_child_path_to_path (GtkTreeModelFilter     *filter,

                                                                           GtkTreePath            *child_path,

                                                                           gboolean                build_levels,

                                                                           gboolean                fetch_children);

static FilterElt   *gtk_tree_model_filter_get_nth                         (GtkTreeModelFilter     *filter,

                                                                           FilterLevel            *level,

                                                                           int                     n);

static gboolean    gtk_tree_model_filter_elt_is_visible_in_target         (FilterLevel            *level,

                                                                           FilterElt              *elt);

static FilterElt   *gtk_tree_model_filter_get_nth_visible                 (GtkTreeModelFilter     *filter,

                                                                           FilterLevel            *level,

                                                                           int                     n);

static FilterElt   *gtk_tree_model_filter_fetch_child                     (GtkTreeModelFilter     *filter,

                                                                           FilterLevel            *level,

                                                                           gint                    offset,

                                                                           gint                   *index);

static void         gtk_tree_model_filter_remove_node                     (GtkTreeModelFilter     *filter,

                                                                           GtkTreeIter            *iter);

static void         gtk_tree_model_filter_update_children                 (GtkTreeModelFilter     *filter,

                                                                           FilterLevel            *level,

                                                                           FilterElt              *elt);

static FilterElt   *bsearch_elt_with_offset                               (GArray                 *array,

                                                                           gint                   offset,

                                                                           gint                  *index);

G_DEFINE_TYPE_WITH_CODE (GtkTreeModelFilter, gtk_tree_model_filter, G_TYPE_OBJECT,

			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,

						gtk_tree_model_filter_tree_model_init)

			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,

						gtk_tree_model_filter_drag_source_init))

static void

gtk_tree_model_filter_init (GtkTreeModelFilter *filter)

{

  filter->priv = GTK_TREE_MODEL_FILTER_GET_PRIVATE (filter);

  filter->priv->visible_column = -1;

  filter->priv->zero_ref_count = 0;

  filter->priv->visible_method_set = FALSE;

  filter->priv->modify_func_set = FALSE;

  filter->priv->in_row_deleted = FALSE;

  filter->priv->virtual_root_deleted = FALSE;

}

static void

gtk_tree_model_filter_class_init (GtkTreeModelFilterClass *filter_class)

{

  GObjectClass *object_class;

  object_class = (GObjectClass *) filter_class;

  object_class->set_property = gtk_tree_model_filter_set_property;

  object_class->get_property = gtk_tree_model_filter_get_property;

  object_class->finalize = gtk_tree_model_filter_finalize;

  /* Properties -- FIXME: disabled translations for now, until I can come up with a

   * better description

   */

  g_object_class_install_property (object_class,

                                   PROP_CHILD_MODEL,

                                   g_param_spec_object ("child-model",

                                                        ("The child model"),

                                                        ("The model for the filtermodel to filter"),

                                                        GTK_TYPE_TREE_MODEL,

                                                        GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));

  g_object_class_install_property (object_class,

                                   PROP_VIRTUAL_ROOT,

                                   g_param_spec_boxed ("virtual-root",

                                                       ("The virtual root"),

                                                       ("The virtual root (relative to the child model) for this filtermodel"),

                                                       GTK_TYPE_TREE_PATH,

                                                       GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));

  g_type_class_add_private (object_class, sizeof (GtkTreeModelFilterPrivate));

}

static void

gtk_tree_model_filter_tree_model_init (GtkTreeModelIface *iface)

{

  iface->get_flags = gtk_tree_model_filter_get_flags;

  iface->get_n_columns = gtk_tree_model_filter_get_n_columns;

  iface->get_column_type = gtk_tree_model_filter_get_column_type;

  iface->get_iter = gtk_tree_model_filter_get_iter;

  iface->get_path = gtk_tree_model_filter_get_path;

  iface->get_value = gtk_tree_model_filter_get_value;

  iface->iter_next = gtk_tree_model_filter_iter_next;

  iface->iter_children = gtk_tree_model_filter_iter_children;

  iface->iter_has_child = gtk_tree_model_filter_iter_has_child;

  iface->iter_n_children = gtk_tree_model_filter_iter_n_children;

  iface->iter_nth_child = gtk_tree_model_filter_iter_nth_child;

  iface->iter_parent = gtk_tree_model_filter_iter_parent;

  iface->ref_node = gtk_tree_model_filter_ref_node;

  iface->unref_node = gtk_tree_model_filter_unref_node;

}

static void

gtk_tree_model_filter_drag_source_init (GtkTreeDragSourceIface *iface)

{

  iface->row_draggable = gtk_tree_model_filter_row_draggable;

  iface->drag_data_delete = gtk_tree_model_filter_drag_data_delete;

  iface->drag_data_get = gtk_tree_model_filter_drag_data_get;

}

static void

gtk_tree_model_filter_finalize (GObject *object)

{

  GtkTreeModelFilter *filter = (GtkTreeModelFilter *) object;

  if (filter->priv->virtual_root && !filter->priv->virtual_root_deleted)

    {

      gtk_tree_model_filter_unref_path (filter, filter->priv->virtual_root);

      filter->priv->virtual_root_deleted = TRUE;

    }

  gtk_tree_model_filter_set_model (filter, NULL);

  if (filter->priv->virtual_root)

    gtk_tree_path_free (filter->priv->virtual_root);

  if (filter->priv->root)

    gtk_tree_model_filter_free_level (filter, filter->priv->root);

  g_free (filter->priv->modify_types);

  if (filter->priv->modify_destroy)

    filter->priv->modify_destroy (filter->priv->modify_data);

  if (filter->priv->visible_destroy)

    filter->priv->visible_destroy (filter->priv->visible_data);

  /* must chain up */

  G_OBJECT_CLASS (gtk_tree_model_filter_parent_class)->finalize (object);

}

static void

gtk_tree_model_filter_set_property (GObject      *object,

                                    guint         prop_id,

                                    const GValue *value,

                                    GParamSpec   *pspec)

{

  GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (object);

  switch (prop_id)

    {

      case PROP_CHILD_MODEL:

        gtk_tree_model_filter_set_model (filter, g_value_get_object (value));

        break;

      case PROP_VIRTUAL_ROOT:

        gtk_tree_model_filter_set_root (filter, g_value_get_boxed (value));

        break;

      default:

        G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);

        break;

    }

}

static void

gtk_tree_model_filter_get_property (GObject    *object,

                                    guint       prop_id,

                                    GValue     *value,

                                    GParamSpec *pspec)

{

  GtkTreeModelFilter *filter = GTK_TREE_MODEL_FILTER (object);

  switch (prop_id)

    {

      case PROP_CHILD_MODEL:

        g_value_set_object (value, filter->priv->child_model);

        break;

      case PROP_VIRTUAL_ROOT:

        g_value_set_boxed (value, filter->priv->virtual_root);

        break;

      default:

        G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);

        break;

    }

}

/* helpers */

static void

gtk_tree_model_filter_build_level (GtkTreeModelFilter *filter,

                                   FilterLevel        *parent_level,

                                   gint                parent_elt_index,

                                   gboolean            emit_inserted)

{

  GtkTreeIter iter;

  GtkTreeIter first_node;

  GtkTreeIter root;

  FilterElt *parent_elt = NULL;

  FilterLevel *new_level;

  gint length = 0;

  gint i;

  g_assert (filter->priv->child_model != NULL);

  if (filter->priv->in_row_deleted)

    return;

  if (!parent_level)

    {

      if (filter->priv->virtual_root)

        {

          if (gtk_tree_model_get_iter (filter->priv->child_model, &root, filter->priv->virtual_root) == FALSE)

            return;

          length = gtk_tree_model_iter_n_children (filter->priv->child_model, &root);

          if (gtk_tree_model_iter_children (filter->priv->child_model, &iter, &root) == FALSE)

            return;

        }

      else

        {

          if (!gtk_tree_model_get_iter_first (filter->priv->child_model, &iter))

            return;

          length = gtk_tree_model_iter_n_children (filter->priv->child_model, NULL);

        }

    }

  else

    {

      GtkTreeIter parent_iter;

      GtkTreeIter child_parent_iter;

      parent_elt = &g_array_index (parent_level->array, FilterElt, parent_elt_index);

      parent_iter.stamp = filter->priv->stamp;

      parent_iter.user_data = parent_level;

      parent_iter.user_data2 = parent_elt;

      gtk_tree_model_filter_convert_iter_to_child_iter (filter,

                                                        &child_parent_iter,

                                                        &parent_iter);

      if (gtk_tree_model_iter_children (filter->priv->child_model, &iter, &child_parent_iter) == FALSE)

        return;

      /* stamp may have changed */

      gtk_tree_model_filter_convert_iter_to_child_iter (filter,

                                                        &child_parent_iter,

                                                        &parent_iter);

      length = gtk_tree_model_iter_n_children (filter->priv->child_model, &child_parent_iter);

    }

  g_return_if_fail (length > 0);

  new_level = g_new (FilterLevel, 1);

  new_level->array = g_array_sized_new (FALSE, FALSE,

                                        sizeof (FilterElt),

                                        length);

  new_level->ref_count = 0;

  new_level->visible_nodes = 0;

  new_level->parent_elt_index = parent_elt_index;

  new_level->parent_level = parent_level;

  if (parent_elt_index >= 0)

    parent_elt->children = new_level;

  else

    filter->priv->root = new_level;

  /* increase the count of zero ref_counts */

  while (parent_level)

    {

      g_array_index (parent_level->array, FilterElt, parent_elt_index).zero_ref_count++;

      parent_elt_index = parent_level->parent_elt_index;

      parent_level = parent_level->parent_level;

    }

  if (new_level != filter->priv->root)

    filter->priv->zero_ref_count++;

  i = 0;

  first_node = iter;

  do

    {

      if (gtk_tree_model_filter_visible (filter, &iter))

        {

          GtkTreeIter f_iter;

          FilterElt filter_elt;

          filter_elt.offset = i;

          filter_elt.zero_ref_count = 0;

          filter_elt.ref_count = 0;

          filter_elt.children = NULL;

          filter_elt.visible = TRUE;

          if (GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))

            filter_elt.iter = iter;

          g_array_append_val (new_level->array, filter_elt);

          new_level->visible_nodes++;

          f_iter.stamp = filter->priv->stamp;

          f_iter.user_data = new_level;

          f_iter.user_data2 = &(g_array_index (new_level->array, FilterElt, new_level->array->len - 1));

          if (new_level->parent_level || filter->priv->virtual_root)

            gtk_tree_model_filter_ref_node (GTK_TREE_MODEL (filter), &f_iter);

          if (emit_inserted)

            {

              GtkTreePath *f_path;

              GtkTreeIter children;

              f_path = gtk_tree_model_get_path (GTK_TREE_MODEL (filter),

                                                &f_iter);

              gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter),

                                           f_path, &f_iter);

              gtk_tree_path_free (f_path);

              if (gtk_tree_model_iter_children (filter->priv->child_model,

                                                &children, &iter))

                gtk_tree_model_filter_update_children (filter,

                                                       new_level,

                                                       FILTER_ELT (f_iter.user_data2));

            }

        }

      i++;

    }

  while (gtk_tree_model_iter_next (filter->priv->child_model, &iter));

  if (new_level->array->len == 0

      && (new_level != filter->priv->root || filter->priv->virtual_root))

    {

      /* If none of the nodes are visible, we will just pull in the

       * first node of the level and keep a reference on it.  We need this

       * to make sure that we get all signals for this level.

       */

      FilterElt filter_elt;

      GtkTreeIter f_iter;

      filter_elt.offset = 0;

      filter_elt.zero_ref_count = 0;

      filter_elt.ref_count = 0;

      filter_elt.children = NULL;

      filter_elt.visible = FALSE;

      if (GTK_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))

        filter_elt.iter = first_node;

      g_array_append_val (new_level->array, filter_elt);

      f_iter.stamp = filter->priv->stamp;

      f_iter.user_data = new_level;

      f_iter.user_data2 = &(g_array_index (new_level->array, FilterElt, new_level->array->len - 1));

      gtk_tree_model_filter_ref_node (GTK_TREE_MODEL (filter), &f_iter);

    }

  else if (new_level->array->len == 0)

    gtk_tree_model_filter_free_level (filter, new_level);

}

static void

gtk_tree_model_filter_free_level (GtkTreeModelFilter *filter,

                                  FilterLevel        *filter_level)

{

  gint i;

  g_assert (filter_level);

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

    {

      if (g_array_index (filter_level->array, FilterElt, i).children)

        gtk_tree_model_filter_free_level (filter,

                                          FILTER_LEVEL (g_array_index (filter_level->array, FilterElt, i).children));

      if (filter_level->parent_level || filter->priv->virtual_root)

        {

          GtkTreeIter f_iter;

          f_iter.stamp = filter->priv->stamp;

          f_iter.user_data = filter_level;

          f_iter.user_data2 = &(g_array_index (filter_level->array, FilterElt, i));

          gtk_tree_model_filter_unref_node (GTK_TREE_MODEL (filter), &f_iter);

        }

    }

  if (filter_level->ref_count == 0)

    {

      FilterLevel *parent_level = filter_level->parent_level;

      gint parent_elt_index = filter_level->parent_elt_index;

      while (parent_level)

        {

	  g_array_index (parent_level->array, FilterElt, parent_elt_index).zero_ref_count--;

	  parent_elt_index = parent_level->parent_elt_index;

	  parent_level = parent_level->parent_level;

        }

      if (filter_level != filter->priv->root)

        filter->priv->zero_ref_count--;

    }

  if (filter_level->parent_elt_index >= 0)

    FILTER_LEVEL_PARENT_ELT (filter_level)->children = NULL;

  else

    filter->priv->root = NULL;

  g_array_free (filter_level->array, TRUE);

  filter_level->array = NULL;

  g_free (filter_level);

  filter_level = NULL;

}

/* Creates paths suitable for accessing the child model. */

static GtkTreePath *

gtk_tree_model_filter_elt_get_path (FilterLevel *level,

                                    FilterElt   *elt,

                                    GtkTreePath *root)

{

  FilterLevel *walker = level;

  FilterElt *walker2 = elt;

  GtkTreePath *path;

  GtkTreePath *real_path;

  g_return_val_if_fail (level != NULL, NULL);

  g_return_val_if_fail (elt != NULL, NULL);

  path = gtk_tree_path_new ();

  while (walker)

    {

      gtk_tree_path_prepend_index (path, walker2->offset);

      if (!walker->parent_level)

        break;

      walker2 = FILTER_LEVEL_PARENT_ELT (walker);

      walker = walker->parent_level;

    }

  if (root)

    {

      real_path = gtk_tree_model_filter_add_root (path, root);

      gtk_tree_path_free (path);

      return real_path;

    }

  return path;

}

static GtkTreePath *

gtk_tree_model_filter_add_root (GtkTreePath *src,

                                GtkTreePath *root)

{

  GtkTreePath *retval;

  gint i;

  retval = gtk_tree_path_copy (root);

  for (i = 0; i < gtk_tree_path_get_depth (src); i++)

    gtk_tree_path_append_index (retval, gtk_tree_path_get_indices (src)[i]);

  return retval;

}

static GtkTreePath *

gtk_tree_model_filter_remove_root (GtkTreePath *src,

                                   GtkTreePath *root)

{

  GtkTreePath *retval;

  gint i;

  gint depth;

  gint *indices;

  if (gtk_tree_path_get_depth (src) <= gtk_tree_path_get_depth (root))

    return NULL;

  depth = gtk_tree_path_get_depth (src);

  indices = gtk_tree_path_get_indices (src);

  for (i = 0; i < gtk_tree_path_get_depth (root); i++)

    if (indices[i] != gtk_tree_path_get_indices (root)[i])

      return NULL;

  retval = gtk_tree_path_new ();

  for (; i < depth; i++)

    gtk_tree_path_append_index (retval, indices[i]);

  return retval;

}

static void

gtk_tree_model_filter_increment_stamp (GtkTreeModelFilter *filter)

{

  do

    {

      filter->priv->stamp++;

    }

  while (filter->priv->stamp == 0);

  gtk_tree_model_filter_clear_cache (filter);

}

static gboolean

gtk_tree_model_filter_visible (GtkTreeModelFilter *filter,

                               GtkTreeIter        *child_iter)

{

  if (filter->priv->visible_func)

    {

      return filter->priv->visible_func (filter->priv->child_model,

					 child_iter,

					 filter->priv->visible_data)

	? TRUE : FALSE;

    }

  else if (filter->priv->visible_column >= 0)

   {

     GValue val = {0, };

     gtk_tree_model_get_value (filter->priv->child_model, child_iter,

                               filter->priv->visible_column, &val;;

     if (g_value_get_boolean (&val))

       {

         g_value_unset (&val;;

         return TRUE;

       }

     g_value_unset (&val;;

     return FALSE;

   }

  /* no visible function set, so always visible */

  return TRUE;

}

static void

gtk_tree_model_filter_clear_cache_helper (GtkTreeModelFilter *filter,

                                          FilterLevel        *level)

{

  gint i;

  g_assert (level);

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

    {

      if (g_array_index (level->array, FilterElt, i).zero_ref_count > 0)

        gtk_tree_model_filter_clear_cache_helper (filter, g_array_index (level->array, FilterElt, i).children);

     }

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

    {

      gtk_tree_model_filter_free_level (filter, level);

      return;

    }

}

static FilterElt *

gtk_tree_model_filter_get_nth (GtkTreeModelFilter *filter,

                               FilterLevel        *level,

                               int                 n)

{

  if (level->array->len <= n)

    return NULL;

  return &g_array_index (level->array, FilterElt, n);

}

static gboolean

gtk_tree_model_filter_elt_is_visible_in_target (FilterLevel *level,

                                                FilterElt   *elt)

{

  gint elt_index;

  if (!elt->visible)

    return FALSE;

  if (level->parent_elt_index == -1)

    return TRUE;

  do

    {

      elt_index = level->parent_elt_index;

      level = level->parent_level;

      if (elt_index >= 0

          && !g_array_index (level->array, FilterElt, elt_index).visible)

        return FALSE;

    }

  while (level);

  return TRUE;

}

static FilterElt *

gtk_tree_model_filter_get_nth_visible (GtkTreeModelFilter *filter,

                                       FilterLevel        *level,

                                       int                 n)

{

  int i = 0;

  FilterElt *elt;

  if (level->visible_nodes <= n)

    return NULL;

  elt = FILTER_ELT (level->array->data);

  while (!elt->visible)

    elt++;

  while (i < n)

    {

      if (elt->visible)

        i++;

      elt++;

    }

  while (!elt->visible)

    elt++;

  return elt;

}

static FilterElt *

gtk_tree_model_filter_fetch_child (GtkTreeModelFilter *filter,

                                   FilterLevel        *level,

                                   gint                offset,

                                   gint               *index)