/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) version 3.
 *
 * This program 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with the program; if not, see <http://www.gnu.org/licenses/>
 *
 *
 * Authors:
 *		Chris Lahey <clahey@ximian.com>
 *		Chris Toshok <toshok@ximian.com>
 *
 * Adapted from the gtree code and ETableModel.
 *
 * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
 *
 */

/* FIXME: Overall e-tree-sorted.c needs to be made more efficient. */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#include <libxml/parser.h>
#include <libxml/xmlmemory.h>

#include "e-util/e-util.h"
#include "e-util/e-xml-utils.h"

#include "e-table-sorting-utils.h"
#include "e-tree-sorted.h"

/* maximum insertions between an idle event that we will do without scheduling an idle sort */
#define ETS_INSERT_MAX (4)

#define d(x)

#define E_TREE_SORTED_GET_PRIVATE(obj) \
	(G_TYPE_INSTANCE_GET_PRIVATE \
	((obj), E_TYPE_TREE_SORTED, ETreeSortedPrivate))

G_DEFINE_TYPE (ETreeSorted, e_tree_sorted, E_TYPE_TREE_MODEL)

enum {
	NODE_RESORTED,
	LAST_SIGNAL
};

static guint signals[LAST_SIGNAL] = {0, };

typedef struct ETreeSortedPath ETreeSortedPath;

struct ETreeSortedPath {
	ETreePath         corresponding;

	/* parent/child/sibling pointers */
	ETreeSortedPath  *parent;
	gint              num_children;
	ETreeSortedPath **children;
	gint               position;
	gint               orig_position;

	guint             needs_resort : 1;
	guint             child_needs_resort : 1;
	guint             resort_all_children : 1;
	guint             needs_regen_to_sort : 1;
};

struct _ETreeSortedPrivate {
	ETreeModel      *source;
	ETreeSortedPath *root;

	ETableSortInfo   *sort_info;
	ETableHeader     *full_header;

	ETreeSortedPath  *last_access;

	gint          tree_model_pre_change_id;
	gint          tree_model_no_change_id;
	gint          tree_model_node_changed_id;
	gint          tree_model_node_data_changed_id;
	gint          tree_model_node_col_changed_id;
	gint          tree_model_node_inserted_id;
	gint          tree_model_node_removed_id;
	gint          tree_model_node_deleted_id;
	gint          tree_model_node_request_collapse_id;

	gint          sort_info_changed_id;
	gint          sort_idle_id;
	gint          insert_idle_id;
	gint          insert_count;

	guint        in_resort_idle : 1;
	guint        nested_resort_idle : 1;
};

enum {
	ARG_0,

	ARG_SORT_INFO
};

static void ets_sort_info_changed (ETableSortInfo *sort_info, ETreeSorted *ets);
static void resort_node (ETreeSorted *ets, ETreeSortedPath *path, gboolean resort_all_children, gboolean needs_regen, gboolean send_signals);
static void mark_path_needs_resort (ETreeSorted *ets, ETreeSortedPath *path, gboolean needs_rebuild, gboolean resort_all_children);
static void schedule_resort (ETreeSorted *ets, ETreeSortedPath *path, gboolean needs_regen, gboolean resort_all_children);
static void free_path (ETreeSortedPath *path);
static void generate_children (ETreeSorted *ets, ETreeSortedPath *path);
static void regenerate_children (ETreeSorted *ets, ETreeSortedPath *path);

/* idle callbacks */

static gboolean
ets_sort_idle (gpointer user_data)
{
	ETreeSorted *ets = user_data;
	if (ets->priv->in_resort_idle) {
		ets->priv->nested_resort_idle = TRUE;
		return FALSE;
	}
	ets->priv->in_resort_idle = TRUE;
	if (ets->priv->root) {
		do {
			ets->priv->nested_resort_idle = FALSE;
			resort_node (ets, ets->priv->root, FALSE, FALSE, TRUE);
		} while (ets->priv->nested_resort_idle);
	}
	ets->priv->in_resort_idle = FALSE;
	ets->priv->sort_idle_id = 0;
	return FALSE;
}

#define ETS_SORT_IDLE_ACTIVATED(ets) ((ets)->priv->sort_idle_id != 0)

inline static void
ets_stop_sort_idle (ETreeSorted *ets)
{
	if (ets->priv->sort_idle_id) {
		g_source_remove (ets->priv->sort_idle_id);
		ets->priv->sort_idle_id = 0;
	}
}

static gboolean
ets_insert_idle (ETreeSorted *ets)
{
	ets->priv->insert_count = 0;
	ets->priv->insert_idle_id = 0;
	return FALSE;
}

/* Helper functions */

#define CHECK_AROUND_LAST_ACCESS

static inline ETreeSortedPath *
check_last_access (ETreeSorted *ets,
                   ETreePath corresponding)
{
#ifdef CHECK_AROUND_LAST_ACCESS
	ETreeSortedPath *parent;
#endif

	if (ets->priv->last_access == NULL)
		return NULL;

	if (ets->priv->last_access == corresponding) {
		d(g_print("Found last access %p at %p.", ets->priv->last_access, ets->priv->last_access));
		return ets->priv->last_access;
	}

#ifdef CHECK_AROUND_LAST_ACCESS
	parent = ets->priv->last_access->parent;
	if (parent && parent->children) {
		gint position = ets->priv->last_access->position;
		gint end = MIN (parent->num_children, position + 10);
		gint start = MAX (0, position - 10);
		gint initial = MAX (MIN (position, end), start);
		gint i;

		for (i = initial; i < end; i++) {
			if (parent->children[i] && parent->children[i]->corresponding == corresponding) {
				d(g_print("Found last access %p at %p.", ets->priv->last_access, parent->children[i]));
				return parent->children[i];
			}
		}

		for (i = initial - 1; i >= start; i--) {
			if (parent->children[i] && parent->children[i]->corresponding == corresponding) {
				d(g_print("Found last access %p at %p.", ets->priv->last_access, parent->children[i]));
				return parent->children[i];
			}
		}
	}
#endif
	return NULL;
}

static ETreeSortedPath *
find_path (ETreeSorted *ets,
           ETreePath corresponding)
{
	gint depth;
	ETreePath *sequence;
	gint i;
	ETreeSortedPath *path;
	ETreeSortedPath *check_last;

	if (corresponding == NULL)
		return NULL;

	check_last = check_last_access (ets, corresponding);
	if (check_last) {
		d(g_print(" (find_path)\n"));
		return check_last;
	}

	depth = e_tree_model_node_depth (ets->priv->source, corresponding);

	sequence = g_new (ETreePath, depth + 1);

	sequence[0] = corresponding;

	for (i = 0; i < depth; i++)
		sequence[i + 1] = e_tree_model_node_get_parent (ets->priv->source, sequence[i]);

	path = ets->priv->root;

	for (i = depth - 1; i >= 0 && path != NULL; i--) {
		gint j;

		if (path->num_children == -1) {
			path = NULL;
			break;
		}

		for (j = 0; j < path->num_children; j++) {
			if (path->children[j]->corresponding == sequence[i]) {
				break;
			}
		}

		if (j < path->num_children) {
			path = path->children[j];
		} else {
			path = NULL;
		}
	}
	g_free (sequence);

	d(g_print("Didn't find last access %p.  Setting to %p. (find_path)\n", ets->priv->last_access, path));
	ets->priv->last_access = path;

	return path;
}

static ETreeSortedPath *
find_child_path (ETreeSorted *ets,
                 ETreeSortedPath *parent,
                 ETreePath corresponding)
{
	gint i;

	if (corresponding == NULL)
		return NULL;

	if (parent->num_children == -1) {
		return NULL;
	}

	for (i = 0; i < parent->num_children; i++)
		if (parent->children[i]->corresponding == corresponding)
			return parent->children[i];

	return NULL;
}

static ETreeSortedPath *
find_or_create_path (ETreeSorted *ets,
                     ETreePath corresponding)
{
	gint depth;
	ETreePath *sequence;
	gint i;
	ETreeSortedPath *path;
	ETreeSortedPath *check_last;

	if (corresponding == NULL)
		return NULL;

	check_last = check_last_access (ets, corresponding);
	if (check_last) {
		d(g_print(" (find_or_create_path)\n"));
		return check_last;
	}

	depth = e_tree_model_node_depth (ets->priv->source, corresponding);

	sequence = g_new (ETreePath, depth + 1);

	sequence[0] = corresponding;

	for (i = 0; i < depth; i++)
		sequence[i + 1] = e_tree_model_node_get_parent (ets->priv->source, sequence[i]);

	path = ets->priv->root;

	for (i = depth - 1; i >= 0 && path != NULL; i--) {
		gint j;

		if (path->num_children == -1) {
			generate_children (ets, path);
		}

		for (j = 0; j < path->num_children; j++) {
			if (path->children[j]->corresponding == sequence[i]) {
				break;
			}
		}

		if (j < path->num_children) {
			path = path->children[j];
		} else {
			path = NULL;
		}
	}
	g_free (sequence);

	d(g_print("Didn't find last access %p.  Setting to %p. (find_or_create_path)\n", ets->priv->last_access, path));
	ets->priv->last_access = path;

	return path;
}

static void
free_children (ETreeSortedPath *path)
{
	gint i;

	if (path == NULL)
		return;

	for (i = 0; i < path->num_children; i++) {
		free_path (path->children[i]);
	}

	g_free (path->children);
	path->children = NULL;
	path->num_children = -1;
}

static void
free_path (ETreeSortedPath *path)
{
	free_children (path);
	g_slice_free (ETreeSortedPath, path);
}

static ETreeSortedPath *
new_path (ETreeSortedPath *parent,
          ETreePath corresponding)
{
	ETreeSortedPath *path;

	path = g_slice_new0 (ETreeSortedPath);

	path->corresponding = corresponding;
	path->parent = parent;
	path->num_children = -1;
	path->children = NULL;
	path->position = -1;
	path->orig_position = -1;
	path->child_needs_resort = 0;
	path->resort_all_children = 0;
	path->needs_resort = 0;
	path->needs_regen_to_sort = 0;

	return path;
}

static gboolean
reposition_path (ETreeSorted *ets,
                 ETreeSortedPath *path)
{
	gint new_index;
	gint old_index = path->position;
	ETreeSortedPath *parent = path->parent;
	gboolean changed = FALSE;
	if (parent) {
		if (ets->priv->sort_idle_id == 0) {
			if (ets->priv->insert_count > ETS_INSERT_MAX) {
				/* schedule a sort, and append instead */
				schedule_resort (ets, parent, TRUE, FALSE);
			} else {
				/* make sure we have an idle handler to reset the count every now and then */
				if (ets->priv->insert_idle_id == 0) {
					ets->priv->insert_idle_id = g_idle_add_full (40, (GSourceFunc) ets_insert_idle, ets, NULL);
				}

				new_index = e_table_sorting_utils_tree_check_position
					(E_TREE_MODEL (ets),
					 ets->priv->sort_info,
					 ets->priv->full_header,
					 (ETreePath *) parent->children,
					 parent->num_children,
					 old_index);

				if (new_index > old_index) {
					gint i;
					ets->priv->insert_count++;
					memmove (parent->children + old_index, parent->children + old_index + 1, sizeof (ETreePath) * (new_index - old_index));
					parent->children[new_index] = path;
					for (i = old_index; i <= new_index; i++)
						parent->children[i]->position = i;
					changed = TRUE;
					e_tree_model_node_changed (E_TREE_MODEL (ets), parent);
					e_tree_sorted_node_resorted (ets, parent);
				} else if (new_index < old_index) {
					gint i;
					ets->priv->insert_count++;
					memmove (parent->children + new_index + 1, parent->children + new_index, sizeof (ETreePath) * (old_index - new_index));
					parent->children[new_index] = path;
					for (i = new_index; i <= old_index; i++)
						parent->children[i]->position = i;
					changed = TRUE;
					e_tree_model_node_changed (E_TREE_MODEL (ets), parent);
					e_tree_sorted_node_resorted (ets, parent);
				}
			}
		} else
			mark_path_needs_resort (ets, parent, TRUE, FALSE);
	}
	return changed;
}

static void
regenerate_children (ETreeSorted *ets,
                     ETreeSortedPath *path)
{
	ETreeSortedPath **children;
	gint i;

	children = g_new (ETreeSortedPath *, path->num_children);
	for (i = 0; i < path->num_children; i++)
		children[path->children[i]->orig_position] = path->children[i];
	g_free (path->children);
	path->children = children;
}

static void
generate_children (ETreeSorted *ets,
                   ETreeSortedPath *path)
{
	ETreePath child;
	gint i;
	gint count;

	free_children (path);

	count = 0;
	for (child = e_tree_model_node_get_first_child (ets->priv->source, path->corresponding);
	     child;
	     child = e_tree_model_node_get_next (ets->priv->source, child)) {
		count++;
	}

	path->num_children = count;
	path->children = g_new (ETreeSortedPath *, count);
	for (child = e_tree_model_node_get_first_child (ets->priv->source, path->corresponding), i = 0;
	     child;
	     child = e_tree_model_node_get_next (ets->priv->source, child), i++) {
		path->children[i] = new_path (path, child);
		path->children[i]->position = i;
		path->children[i]->orig_position = i;
	}
	if (path->num_children > 0)
		schedule_resort (ets, path, FALSE, TRUE);
}

static void
resort_node (ETreeSorted *ets,
             ETreeSortedPath *path,
             gboolean resort_all_children,
             gboolean needs_regen,
             gboolean send_signals)
{
	gboolean needs_resort;
	if (path) {
		needs_resort = path->needs_resort || resort_all_children;
		needs_regen = path->needs_regen_to_sort || needs_regen;
		if (path->num_children > 0) {
			if (needs_resort && send_signals)
				e_tree_model_pre_change (E_TREE_MODEL (ets));
			if (needs_resort) {
				gint i;
				d(g_print("Start sort of node %p\n", path));
				if (needs_regen)
					regenerate_children (ets, path);
				d(g_print("Regened sort of node %p\n", path));
				e_table_sorting_utils_tree_sort (E_TREE_MODEL (ets),
								 ets->priv->sort_info,
								 ets->priv->full_header,
								 (ETreePath *) path->children,
								 path->num_children);
				d(g_print("Renumbering sort of node %p\n", path));
				for (i = 0; i < path->num_children; i++) {
					path->children[i]->position = i;
				}
				d(g_print("End sort of node %p\n", path));
			}
			if (path->resort_all_children)
				resort_all_children = TRUE;
			if ((resort_all_children || path->child_needs_resort) && path->num_children >= 0) {
				gint i;
				for (i = 0; i < path->num_children; i++) {
					resort_node (ets, path->children[i], resort_all_children, needs_regen, send_signals && !needs_resort);
				}
				path->child_needs_resort = 0;
			}
		}
		path->needs_resort = 0;
		path->child_needs_resort = 0;
		path->needs_regen_to_sort = 0;
		path->resort_all_children = 0;
		if (needs_resort && send_signals && path->num_children > 0) {
			e_tree_model_node_changed (E_TREE_MODEL (ets), path);
			e_tree_sorted_node_resorted (ets, path);
		}
	}
}

static void
mark_path_child_needs_resort (ETreeSorted *ets,
                              ETreeSortedPath *path)
{
	if (path == NULL)
		return;
	if (!path->child_needs_resort) {
		path->child_needs_resort = 1;
		mark_path_child_needs_resort (ets, path->parent);
	}
}

static void
mark_path_needs_resort (ETreeSorted *ets,
                        ETreeSortedPath *path,
                        gboolean needs_regen,
                        gboolean resort_all_children)
{
	if (path == NULL)
		return;
	if (path->num_children == 0)
		return;
	path->needs_resort = 1;
	path->needs_regen_to_sort = needs_regen;
	path->resort_all_children = resort_all_children;
	mark_path_child_needs_resort (ets, path->parent);
}

static void
schedule_resort (ETreeSorted *ets,
                 ETreeSortedPath *path,
                 gboolean needs_regen,
                 gboolean resort_all_children)
{
	ets->priv->insert_count = 0;
	if (ets->priv->insert_idle_id != 0) {
		g_source_remove (ets->priv->insert_idle_id);
		ets->priv->insert_idle_id = 0;
	}

	if (path == NULL)
		return;
	if (path->num_children == 0)
		return;

	mark_path_needs_resort (ets, path, needs_regen, resort_all_children);
	if (ets->priv->sort_idle_id == 0) {
		ets->priv->sort_idle_id = g_idle_add_full (50, (GSourceFunc) ets_sort_idle, ets, NULL);
	} else if (ets->priv->in_resort_idle) {
		ets->priv->nested_resort_idle = TRUE;
	}
}

/* virtual methods */

static void
ets_dispose (GObject *object)
{
	ETreeSortedPrivate *priv;

	priv = E_TREE_SORTED_GET_PRIVATE (object);

	if (priv->source) {
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_pre_change_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_no_change_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_node_changed_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_node_data_changed_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_node_col_changed_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_node_inserted_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_node_removed_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_node_deleted_id);
		g_signal_handler_disconnect (
			priv->source, priv->tree_model_node_request_collapse_id);

		g_object_unref (priv->source);
		priv->source = NULL;

		priv->tree_model_pre_change_id = 0;
		priv->tree_model_no_change_id = 0;
		priv->tree_model_node_changed_id = 0;
		priv->tree_model_node_data_changed_id = 0;
		priv->tree_model_node_col_changed_id = 0;
		priv->tree_model_node_inserted_id = 0;
		priv->tree_model_node_removed_id = 0;
		priv->tree_model_node_deleted_id = 0;
		priv->tree_model_node_request_collapse_id = 0;
	}

	if (priv->sort_info) {
		g_signal_handler_disconnect (
			priv->sort_info, priv->sort_info_changed_id);
		priv->sort_info_changed_id = 0;

		g_object_unref (priv->sort_info);
		priv->sort_info = NULL;
	}

	ets_stop_sort_idle (E_TREE_SORTED (object));

	if (priv->insert_idle_id) {
		g_source_remove (priv->insert_idle_id);
		priv->insert_idle_id = 0;
	}

	if (priv->full_header) {
		g_object_unref (priv->full_header);
		priv->full_header = NULL;
	}

	/* Chain up to parent's dispose() method. */
	G_OBJECT_CLASS (e_tree_sorted_parent_class)->dispose (object);
}

static void
ets_finalize (GObject *object)
{
	ETreeSortedPrivate *priv;

	priv = E_TREE_SORTED_GET_PRIVATE (object);

	if (priv->root)
		free_path (priv->root);

	/* Chain up to parent's finalize() method. */
	G_OBJECT_CLASS (e_tree_sorted_parent_class)->finalize (object);
}

static ETreePath
ets_get_root (ETreeModel *etm)
{
	ETreeSortedPrivate *priv = E_TREE_SORTED (etm)->priv;
	if (priv->root == NULL) {
		ETreeSorted *ets = E_TREE_SORTED (etm);
		ETreePath corresponding = e_tree_model_get_root (ets->priv->source);

		if (corresponding) {
			priv->root = new_path (NULL, corresponding);
		}
	}
	if (priv->root && priv->root->num_children == -1) {
		generate_children (E_TREE_SORTED (etm), priv->root);
	}

	return priv->root;
}

static ETreePath
ets_get_parent (ETreeModel *etm,
                ETreePath node)
{
	ETreeSortedPath *path = node;
	return path->parent;
}

static ETreePath
ets_get_first_child (ETreeModel *etm,
                     ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSorted *ets = E_TREE_SORTED (etm);

	if (path->num_children == -1)
		generate_children (ets, path);

	if (path->num_children > 0)
		return path->children[0];
	else
		return NULL;
}

static ETreePath
ets_get_last_child (ETreeModel *etm,
                    ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSorted *ets = E_TREE_SORTED (etm);

	if (path->num_children == -1)
		generate_children (ets, path);

	if (path->num_children > 0)
		return path->children[path->num_children - 1];
	else
		return NULL;
}

static ETreePath
ets_get_next (ETreeModel *etm,
              ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSortedPath *parent = path->parent;
	if (parent) {
		if (parent->num_children > path->position + 1)
			return parent->children[path->position + 1];
		else
			return NULL;
	} else
		  return NULL;
}

static ETreePath
ets_get_prev (ETreeModel *etm,
              ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSortedPath *parent = path->parent;
	if (parent) {
		if (path->position - 1 >= 0)
			return parent->children[path->position - 1];
		else
			return NULL;
	} else
		  return NULL;
}

static gboolean
ets_is_root (ETreeModel *etm,
             ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_node_is_root (ets->priv->source, path->corresponding);
}

static gboolean
ets_is_expandable (ETreeModel *etm,
                   ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSorted *ets = E_TREE_SORTED (etm);
	gboolean expandable = e_tree_model_node_is_expandable (ets->priv->source, path->corresponding);

	if (path->num_children == -1) {
		generate_children (ets, node);
	}

	return expandable;
}

static guint
ets_get_children (ETreeModel *etm,
                  ETreePath node,
                  ETreePath **nodes)
{
	ETreeSortedPath *path = node;
	guint n_children;

	if (path->num_children == -1) {
		generate_children (E_TREE_SORTED (etm), node);
	}

	n_children = path->num_children;

	if (nodes) {
		gint i;

		(*nodes) = g_malloc (sizeof (ETreePath) * n_children);
		for (i = 0; i < n_children; i++) {
			(*nodes)[i] = path->children[i];
		}
	}

	return n_children;
}

static guint
ets_depth (ETreeModel *etm,
           ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_node_depth (ets->priv->source, path->corresponding);
}

static GdkPixbuf *
ets_icon_at (ETreeModel *etm,
             ETreePath node)
{
	ETreeSortedPath *path = node;
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_icon_at (ets->priv->source, path->corresponding);
}

static gboolean
ets_get_expanded_default (ETreeModel *etm)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_get_expanded_default (ets->priv->source);
}

static gint
ets_column_count (ETreeModel *etm)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_column_count (ets->priv->source);
}

static gboolean
ets_has_save_id (ETreeModel *etm)
{
	return TRUE;
}

static gchar *
ets_get_save_id (ETreeModel *etm,
                 ETreePath node)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);
	ETreeSortedPath *path = node;

	if (e_tree_model_has_save_id (ets->priv->source))
		return e_tree_model_get_save_id (ets->priv->source, path->corresponding);
	else
		return g_strdup_printf("%p", path->corresponding);
}

static gboolean
ets_has_get_node_by_id (ETreeModel *etm)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);
	return e_tree_model_has_get_node_by_id (ets->priv->source);
}

static ETreePath
ets_get_node_by_id (ETreeModel *etm,
                    const gchar *save_id)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);
	ETreePath node;

	node = e_tree_model_get_node_by_id (ets->priv->source, save_id);

	return find_path (ets, node);
}

static gboolean
ets_has_change_pending (ETreeModel *etm)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return ets->priv->sort_idle_id != 0;
}

static gpointer
ets_value_at (ETreeModel *etm,
              ETreePath node,
              gint col)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);
	ETreeSortedPath *path = node;

	return e_tree_model_value_at (ets->priv->source, path->corresponding, col);
}

static void
ets_set_value_at (ETreeModel *etm,
                  ETreePath node,
                  gint col,
                  gconstpointer val)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);
	ETreeSortedPath *path = node;

	e_tree_model_set_value_at (ets->priv->source, path->corresponding, col, val);
}

static gboolean
ets_is_editable (ETreeModel *etm,
                 ETreePath node,
                 gint col)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);
	ETreeSortedPath *path = node;

	return e_tree_model_node_is_editable (ets->priv->source, path->corresponding, col);
}

/* The default for ets_duplicate_value is to return the raw value. */
static gpointer
ets_duplicate_value (ETreeModel *etm,
                     gint col,
                     gconstpointer value)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_duplicate_value (ets->priv->source, col, value);
}

static void
ets_free_value (ETreeModel *etm,
                gint col,
                gpointer value)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	e_tree_model_free_value (ets->priv->source, col, value);
}

static gpointer
ets_initialize_value (ETreeModel *etm,
                      gint col)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_initialize_value (ets->priv->source, col);
}

static gboolean
ets_value_is_empty (ETreeModel *etm,
                    gint col,
                    gconstpointer value)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_value_is_empty (ets->priv->source, col, value);
}

static gchar *
ets_value_to_string (ETreeModel *etm,
                     gint col,
                     gconstpointer value)
{
	ETreeSorted *ets = E_TREE_SORTED (etm);

	return e_tree_model_value_to_string (ets->priv->source, col, value);
}

/* Proxy functions */

static void
ets_proxy_pre_change (ETreeModel *etm,
                      ETreeSorted *ets)
{
	e_tree_model_pre_change (E_TREE_MODEL (ets));
}

static void
ets_proxy_no_change (ETreeModel *etm,
                     ETreeSorted *ets)
{
	e_tree_model_no_change (E_TREE_MODEL (ets));
}

static void
ets_proxy_node_changed (ETreeModel *etm,
                        ETreePath node,
                        ETreeSorted *ets)
{
	ets->priv->last_access = NULL;
	d(g_print("Setting last access %p. (ets_proxy_node_changed)\n", ets->priv->last_access));

	if (e_tree_model_node_is_root (ets->priv->source, node)) {
		ets_stop_sort_idle (ets);

		if (ets->priv->root) {
			free_path (ets->priv->root);
		}
		ets->priv->root = new_path (NULL, node);
		e_tree_model_node_changed (E_TREE_MODEL (ets), ets->priv->root);
		return;
	} else {
		ETreeSortedPath *path = find_path (ets, node);

		if (path) {
			free_children (path);
			if (!reposition_path (ets, path)) {
				e_tree_model_node_changed (E_TREE_MODEL (ets), path);
			} else {
				e_tree_model_no_change (E_TREE_MODEL (ets));
			}
		} else {
			e_tree_model_no_change (E_TREE_MODEL (ets));
		}
	}
}

static void
ets_proxy_node_data_changed (ETreeModel *etm,
                             ETreePath node,
                             ETreeSorted *ets)
{
	ETreeSortedPath *path = find_path (ets, node);

	if (path) {
		if (!reposition_path (ets, path))
			e_tree_model_node_data_changed (E_TREE_MODEL (ets), path);
		else
			e_tree_model_no_change (E_TREE_MODEL (ets));
	} else
		e_tree_model_no_change (E_TREE_MODEL (ets));
}

static void
ets_proxy_node_col_changed (ETreeModel *etm,
                            ETreePath node,
                            gint col,
                            ETreeSorted *ets)
{
	ETreeSortedPath *path = find_path (ets, node);

	if (path) {
		gboolean changed = FALSE;
		if (e_table_sorting_utils_affects_sort (ets->priv->sort_info, ets->priv->full_header, col))
			changed = reposition_path (ets, path);
		if (!changed)
			e_tree_model_node_col_changed (E_TREE_MODEL (ets), path, col);
		else
			e_tree_model_no_change (E_TREE_MODEL (ets));
	} else
		e_tree_model_no_change (E_TREE_MODEL (ets));
}

static void
ets_proxy_node_inserted (ETreeModel *etm,
                         ETreePath parent,
                         ETreePath child,
                         ETreeSorted *ets)
{
	ETreeSortedPath *parent_path = find_path (ets, parent);

	if (parent_path && parent_path->num_children != -1) {
		gint i;
		gint j;
		ETreeSortedPath *path;
		gint position = parent_path->num_children;
		ETreePath counter;

		for (counter = e_tree_model_node_get_next (etm, child);
		     counter;
		     counter = e_tree_model_node_get_next (etm, counter))
			position--;

		if (position != parent_path->num_children) {
			for (i = 0; i < parent_path->num_children; i++) {
				if (parent_path->children[i]->orig_position >= position)
					parent_path->children[i]->orig_position++;
			}
		}

		i = parent_path->num_children;
		path = new_path (parent_path, child);
		path->orig_position = position;
		if (!ETS_SORT_IDLE_ACTIVATED (ets)) {
			ets->priv->insert_count++;
			if (ets->priv->insert_count > ETS_INSERT_MAX) {
				/* schedule a sort, and append instead */
				schedule_resort (ets, parent_path, TRUE, FALSE);
			} else {
				/* make sure we have an idle handler to reset the count every now and then */
				if (ets->priv->insert_idle_id == 0) {
					ets->priv->insert_idle_id = g_idle_add_full (40, (GSourceFunc) ets_insert_idle, ets, NULL);
				}
				i = e_table_sorting_utils_tree_insert
					(ets->priv->source,
					 ets->priv->sort_info,
					 ets->priv->full_header,
					 (ETreePath *) parent_path->children,
					 parent_path->num_children,
					 path);
			}
		} else {
			mark_path_needs_resort (ets, parent_path, TRUE, FALSE);
		}
		parent_path->num_children++;
		parent_path->children = g_renew (ETreeSortedPath *, parent_path->children, parent_path->num_children);
		memmove (parent_path->children + i + 1, parent_path->children + i, (parent_path->num_children - 1 - i) * sizeof (gint));
		parent_path->children[i] = path;
		for (j = i; j < parent_path->num_children; j++) {
			parent_path->children[j]->position = j;
		}
		e_tree_model_node_inserted (E_TREE_MODEL (ets), parent_path, parent_path->children[i]);
	} else if (ets->priv->root == NULL && parent == NULL) {
		if (child) {
			ets->priv->root = new_path (NULL, child);
			e_tree_model_node_inserted (E_TREE_MODEL (ets), NULL, ets->priv->root);
		} else {
			e_tree_model_no_change (E_TREE_MODEL (ets));
		}
	} else {
		e_tree_model_no_change (E_TREE_MODEL (ets));
	}
}

static void
ets_proxy_node_removed (ETreeModel *etm,
                        ETreePath parent,
                        ETreePath child,
                        gint old_position,
                        ETreeSorted *ets)
{
	ETreeSortedPath *parent_path = find_path (ets, parent);
	ETreeSortedPath *path;

	if (parent_path)
		path = find_child_path (ets, parent_path, child);
	else
		path = find_path (ets, child);

	d(g_print("Setting last access %p. (ets_proxy_node_removed)\n ", ets->priv->last_access));
	ets->priv->last_access = NULL;

	if (path && parent_path && parent_path->num_children != -1) {
		gint i;
		for (i = 0; i < parent_path->num_children; i++) {
			if (parent_path->children[i]->orig_position > old_position)
				parent_path->children[i]->orig_position--;
		}

		i = path->position;

		parent_path->num_children--;
		memmove (parent_path->children + i, parent_path->children + i + 1, sizeof (ETreeSortedPath *) * (parent_path->num_children - i));
		for (; i < parent_path->num_children; i++) {
			parent_path->children[i]->position = i;
		}
		e_tree_model_node_removed (E_TREE_MODEL (ets), parent_path, path, path->position);
		free_path (path);
	} else if (path && path == ets->priv->root) {
		ets->priv->root = NULL;
		e_tree_model_node_removed (E_TREE_MODEL (ets), NULL, path, -1);
		free_path (path);
	}
}

static void
ets_proxy_node_deleted (ETreeModel *etm,
                        ETreePath child,
                        ETreeSorted *ets)
{
	e_tree_model_node_deleted (E_TREE_MODEL (ets), NULL);
}

static void
ets_proxy_node_request_collapse (ETreeModel *etm,
                                 ETreePath node,
                                 ETreeSorted *ets)
{
	ETreeSortedPath *path = find_path (ets, node);
	if (path) {
		e_tree_model_node_request_collapse (E_TREE_MODEL (ets), path);
	}
}

static void
ets_sort_info_changed (ETableSortInfo *sort_info,
                       ETreeSorted *ets)
{
	schedule_resort (ets, ets->priv->root, TRUE, TRUE);
}

/* Initialization and creation */

static void
e_tree_sorted_class_init (ETreeSortedClass *class)
{
	GObjectClass *object_class;
	ETreeModelClass *tree_model_class;

	g_type_class_add_private (class, sizeof (ETreeSortedPrivate));

	object_class = G_OBJECT_CLASS (class);
	object_class->dispose = ets_dispose;
	object_class->finalize = ets_finalize;

	tree_model_class = E_TREE_MODEL_CLASS (class);
	tree_model_class->get_root = ets_get_root;
	tree_model_class->get_parent = ets_get_parent;
	tree_model_class->get_first_child = ets_get_first_child;
	tree_model_class->get_last_child = ets_get_last_child;
	tree_model_class->get_prev = ets_get_prev;
	tree_model_class->get_next = ets_get_next;

	tree_model_class->is_root = ets_is_root;
	tree_model_class->is_expandable = ets_is_expandable;
	tree_model_class->get_children = ets_get_children;
	tree_model_class->depth = ets_depth;

	tree_model_class->icon_at = ets_icon_at;

	tree_model_class->get_expanded_default = ets_get_expanded_default;
	tree_model_class->column_count = ets_column_count;

	tree_model_class->has_save_id = ets_has_save_id;
	tree_model_class->get_save_id = ets_get_save_id;

	tree_model_class->has_get_node_by_id = ets_has_get_node_by_id;
	tree_model_class->get_node_by_id = ets_get_node_by_id;

	tree_model_class->has_change_pending = ets_has_change_pending;

	tree_model_class->value_at = ets_value_at;
	tree_model_class->set_value_at = ets_set_value_at;
	tree_model_class->is_editable = ets_is_editable;

	tree_model_class->duplicate_value = ets_duplicate_value;
	tree_model_class->free_value = ets_free_value;
	tree_model_class->initialize_value = ets_initialize_value;
	tree_model_class->value_is_empty = ets_value_is_empty;
	tree_model_class->value_to_string = ets_value_to_string;

	signals[NODE_RESORTED] =
		g_signal_new ("node_resorted",
			      G_TYPE_FROM_CLASS (object_class),
			      G_SIGNAL_RUN_LAST,
			      G_STRUCT_OFFSET (ETreeSortedClass, node_resorted),
			      (GSignalAccumulator) NULL, NULL,
			      g_cclosure_marshal_VOID__POINTER,
			      G_TYPE_NONE, 1, G_TYPE_POINTER);
}

static void
e_tree_sorted_init (ETreeSorted *ets)
{
	ets->priv = E_TREE_SORTED_GET_PRIVATE (ets);
}

/**
 * e_tree_sorted_construct:
 * @etree:
 *
 *
 **/
void
e_tree_sorted_construct (ETreeSorted *ets,
                         ETreeModel *source,
                         ETableHeader *full_header,
                         ETableSortInfo *sort_info)
{
	ets->priv->source                              = source;
	if (source)
		g_object_ref (source);

	ets->priv->full_header                         = full_header;
	if (full_header)
		g_object_ref (full_header);

	e_tree_sorted_set_sort_info (ets, sort_info);

	ets->priv->tree_model_pre_change_id = g_signal_connect (
		source, "pre_change",
		G_CALLBACK (ets_proxy_pre_change), ets);
	ets->priv->tree_model_no_change_id = g_signal_connect (
		source, "no_change",
		G_CALLBACK (ets_proxy_no_change), ets);
	ets->priv->tree_model_node_changed_id = g_signal_connect (
		source, "node_changed",
		G_CALLBACK (ets_proxy_node_changed), ets);
	ets->priv->tree_model_node_data_changed_id = g_signal_connect (
		source, "node_data_changed",
		G_CALLBACK (ets_proxy_node_data_changed), ets);
	ets->priv->tree_model_node_col_changed_id = g_signal_connect (
		source, "node_col_changed",
		G_CALLBACK (ets_proxy_node_col_changed), ets);
	ets->priv->tree_model_node_inserted_id = g_signal_connect (
		source, "node_inserted",
		G_CALLBACK (ets_proxy_node_inserted), ets);
	ets->priv->tree_model_node_removed_id = g_signal_connect (
		source, "node_removed",
		G_CALLBACK (ets_proxy_node_removed), ets);
	ets->priv->tree_model_node_deleted_id = g_signal_connect (
		source, "node_deleted",
		G_CALLBACK (ets_proxy_node_deleted), ets);
	ets->priv->tree_model_node_request_collapse_id = g_signal_connect (
		source, "node_request_collapse",
		G_CALLBACK (ets_proxy_node_request_collapse), ets);

}

/**
 * e_tree_sorted_new
 *
 * FIXME docs here.
 *
 * return values: a newly constructed ETreeSorted.
 */
ETreeSorted *
e_tree_sorted_new (ETreeModel *source,
                   ETableHeader *full_header,
                   ETableSortInfo *sort_info)
{
	ETreeSorted *ets = g_object_new (E_TYPE_TREE_SORTED, NULL);

	e_tree_sorted_construct (ets, source, full_header, sort_info);

	return ets;
}

ETreePath
e_tree_sorted_view_to_model_path (ETreeSorted *ets,
                                  ETreePath view_path)
{
	ETreeSortedPath *path = view_path;
	if (path) {
		ets->priv->last_access = path;
		d(g_print("Setting last access %p. (e_tree_sorted_view_to_model_path)\n", ets->priv->last_access));
		return path->corresponding;
	} else
		return NULL;
}

ETreePath
e_tree_sorted_model_to_view_path (ETreeSorted *ets,
                                  ETreePath model_path)
{
	return find_or_create_path (ets, model_path);
}

gint
e_tree_sorted_orig_position (ETreeSorted *ets,
                             ETreePath path)
{
	ETreeSortedPath *sorted_path = path;
	return sorted_path->orig_position;
}

gint
e_tree_sorted_node_num_children (ETreeSorted *ets,
                                 ETreePath path)
{
	ETreeSortedPath *sorted_path = path;

	if (sorted_path->num_children == -1) {
		generate_children (ets, sorted_path);
	}

	return sorted_path->num_children;
}

void
e_tree_sorted_node_resorted (ETreeSorted *sorted,
                             ETreePath node)
{
	g_return_if_fail (sorted != NULL);
	g_return_if_fail (E_IS_TREE_SORTED (sorted));

	g_signal_emit (G_OBJECT (sorted), signals[NODE_RESORTED], 0, node);
}

void
e_tree_sorted_set_sort_info (ETreeSorted *ets,
                             ETableSortInfo *sort_info)
{

	g_return_if_fail (ets != NULL);

	if (ets->priv->sort_info) {
		if (ets->priv->sort_info_changed_id != 0)
			g_signal_handler_disconnect (G_OBJECT (ets->priv->sort_info),
						     ets->priv->sort_info_changed_id);
		ets->priv->sort_info_changed_id = 0;
		g_object_unref (ets->priv->sort_info);
	}

	ets->priv->sort_info = sort_info;
	if (sort_info) {
		g_object_ref (sort_info);
		ets->priv->sort_info_changed_id = g_signal_connect (
			ets->priv->sort_info, "sort_info_changed",
			G_CALLBACK (ets_sort_info_changed), ets);
	}

	if (ets->priv->root)
		schedule_resort (ets, ets->priv->root, TRUE, TRUE);
}

ETableSortInfo *
e_tree_sorted_get_sort_info (ETreeSorted *ets)
{
	return ets->priv->sort_info;
}