/* world-tree.c -
 *
 * Copyright 2007-2008 OpenMoko, Inc.
 * Authored by Chia-I Wu <olv@openmoko.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#include <glib.h>
#include <diversity-object.h>
#include <diversity-viewport.h>
#include <diversity-utils.h>
#include "world-tree.h"

struct _WorldTree {
	GNode *root;
	gint node_size;
	gint max_depth;

	GSList *viewports;
};

typedef struct _DiversityNode {
	DiversityRectangle rect;
	GSList *objects;
} DiversityNode;

typedef struct _TraversePicker {
	DiversityObject *picker;
	WorldTreePickFunc func;
} TraversePicker;

static GQuark world_tree_node_quark = 0;

inline static gboolean node_fit(GNode *n, DiversityObject *obj)
{
	DiversityNode *dn = n->data;
	DiversityRectangle rect;

	diversity_object_geometry_get(obj, &rect.x, &rect.y, &rect.width, &rect.height);

	return DIVERSITY_RECTANGLE_CONTAIN(&dn->rect, &rect);
}

static void node_grow(GNode *parent)
{
	DiversityNode *parent_dn, *dn;
	GSList *tmp_list;
	gdouble w, h;
	gint i, j;

	if (!G_NODE_IS_LEAF(parent))
		return;

	parent_dn = parent->data;
	w = parent_dn->rect.width / 2;
	h = parent_dn->rect.height / 2;

	for (i = 0; i < 2; i++) {
		for (j = 0;  j < 2; j++) {
			dn = g_slice_new(DiversityNode);
			dn->rect.x = parent_dn->rect.x + w * i;
			dn->rect.y = parent_dn->rect.y + h * j;
			dn->rect.width = w;
			dn->rect.height = h;
			dn->objects = NULL;

			g_node_append_data(parent, dn);
		}
	}

	tmp_list = parent_dn->objects;
	while (tmp_list) {
		DiversityObject *obj;
		
		obj = tmp_list->data;
		tmp_list = g_slist_next(tmp_list);

		for (i = 0; i < 4; i++) {
			GNode *n = g_node_nth_child(parent, i);

			if (node_fit(n, obj)) {
				dn = n->data;
				dn->objects = g_slist_prepend(dn->objects, obj);
				g_object_set_qdata(G_OBJECT(obj), world_tree_node_quark, n);

				parent_dn->objects = g_slist_remove(parent_dn->objects, obj);

				break;
			}
		}
	}
}

static GNode *node_pose(GNode *root, DiversityObject *obj)
{
	gint i;

	if (!g_node_n_children(root))
		return root;

	for (i = 0; i < 4; i++) {
		GNode *n = g_node_nth_child(root, i);

		if (node_fit(n, obj))
			return node_pose(n, obj);
	}

	return root;
}

WorldTree *world_tree_new(gint node_size, gint max_depth)
{
	WorldTree *tree;
	DiversityNode *dn;

	if (!world_tree_node_quark) {
		world_tree_node_quark =
			g_quark_from_static_string("world_tree_node_quark");
	}

	tree = g_new0(WorldTree, 1);

	tree->node_size = node_size;
	tree->max_depth = max_depth;
	tree->root = g_node_new(NULL);

	dn = g_slice_new0(DiversityNode);
	dn->rect.x = -180.0;
	dn->rect.y = -90.0;
	dn->rect.width = 360.0;
	dn->rect.height = 180.0;

	tree->root->data = dn;

	return tree;
}

static void diversity_node_free(DiversityNode *dn)
{
	while (dn->objects) {
		g_object_unref(dn->objects->data);
		dn->objects = g_slist_delete_link(dn->objects, dn->objects);
	}

	g_slice_free(DiversityNode, dn);
}

static gboolean node_traverse(GNode *node, gpointer data)
{
	diversity_node_free(node->data);

	return FALSE;
}

void world_tree_free(WorldTree *tree)
{
	GSList *tmp_list;

	g_node_traverse(tree->root, G_IN_ORDER, G_TRAVERSE_ALL, -1, node_traverse, tree);
	g_node_destroy(tree->root);

	tmp_list = tree->viewports;
	while (tmp_list) {
		g_object_unref(tmp_list->data);
		tmp_list = tmp_list->next;
	}
	g_slist_free(tree->viewports);

	g_free(tree);
}

static void _world_tree_view(WorldTree *tree, DiversityObject *obj)
{
	GSList *tmp_list;

	tmp_list = tree->viewports;
	while (tmp_list) {
		DiversityViewport *view = tmp_list->data;

		diversity_viewport_add_object(view, obj);

		tmp_list = tmp_list->next;
	}
}

static void _world_tree_unview(WorldTree *tree, DiversityObject *obj)
{
	GSList *tmp_list;

	tmp_list = tree->viewports;
	while (tmp_list) {
		DiversityViewport *view = tmp_list->data;

		if (diversity_object_intersect(DIVERSITY_OBJECT(view), obj))
			diversity_viewport_remove_object(view, obj);

		tmp_list = tmp_list->next;
	}
}

static void on_object_geometry_changed(DiversityObject *obj, gdouble lon, gdouble lat, gdouble width, gdouble height, gpointer data)
{
	WorldTree *tree = data;
	GNode *cur, *n;
	DiversityNode *dn;

	g_return_if_fail(node_fit(tree->root, obj));

	cur = g_object_get_qdata(G_OBJECT(obj), world_tree_node_quark);
	if (!cur)
		return;

	n = node_pose(tree->root, obj);

	if (cur != n) {
		dn = cur->data;
		dn->objects = g_slist_remove(dn->objects, obj);

		dn = n->data;
		dn->objects = g_slist_prepend(dn->objects, obj);

		g_object_set_qdata(G_OBJECT(obj), world_tree_node_quark, n);

		if (G_NODE_IS_LEAF(n) && g_node_depth(n) < tree->max_depth &&
		    g_slist_length(dn->objects) > tree->node_size)
			node_grow(n);
	}

	_world_tree_view(tree, obj);
}

gboolean world_tree_add(WorldTree *tree, DiversityObject *obj)
{
	GNode *n;
	DiversityNode *dn;

	g_return_val_if_fail(node_fit(tree->root, obj), FALSE);

	n = node_pose(tree->root, obj);
	dn = n->data;

	dn->objects = g_slist_prepend(dn->objects, obj); 
	g_object_ref_sink(obj);

	g_object_set_qdata(G_OBJECT(obj), world_tree_node_quark, n);
	g_signal_connect(obj, "geometry_changed",
			 G_CALLBACK(on_object_geometry_changed), tree);

	if (G_NODE_IS_LEAF(n) && g_node_depth(n) < tree->max_depth &&
	    g_slist_length(dn->objects) > tree->node_size)
		node_grow(n);

	_world_tree_view(tree, obj);

	return TRUE;
}

gboolean world_tree_remove(WorldTree *tree, DiversityObject *obj)
{
	GNode *n;
	DiversityNode *dn;
	GSList *tmp;

	n = g_object_get_qdata(G_OBJECT(obj), world_tree_node_quark);
	if (!n)
		return FALSE;

	dn = n->data;

	tmp = g_slist_find(dn->objects, obj);
	g_return_val_if_fail(tmp, FALSE);

	_world_tree_unview(tree, obj);

	g_object_set_qdata(G_OBJECT(obj), world_tree_node_quark, NULL);
	g_signal_handlers_disconnect_by_func(obj,
			on_object_geometry_changed, tree);

	dn->objects = g_slist_delete_link(dn->objects, tmp);
	g_object_unref(obj);

	return TRUE;
}

static void viewport_pick(DiversityObject *picker, DiversityObject *obj)
{
	diversity_viewport_add_object(DIVERSITY_VIEWPORT(picker), obj);
}

static void on_viewport_enabled(DiversityViewport *view, gboolean enabled, gpointer data)
{
	WorldTree *tree = data;

	if (enabled)
		world_tree_pick(tree, DIVERSITY_OBJECT(view), viewport_pick);
}

static void on_viewport_geometry_changed(DiversityViewport *view, gdouble lon, gdouble lat, gdouble width, gdouble height, gpointer data)
{
	WorldTree *tree = data;

	if (diversity_viewport_get_enabled(view))
		world_tree_pick(tree, DIVERSITY_OBJECT(view), viewport_pick);
}

static void on_viewport_filter_changed(DiversityViewport *view, gpointer data)
{
	WorldTree *tree = data;

	if (diversity_viewport_get_enabled(view))
		world_tree_pick(tree, DIVERSITY_OBJECT(view), viewport_pick);
}

gboolean world_tree_add_viewport(WorldTree *tree, DiversityViewport *view)
{
	tree->viewports = g_slist_prepend(tree->viewports, view);
	g_signal_connect(view, "enabled",
			 G_CALLBACK(on_viewport_enabled), tree);
	g_signal_connect(view, "geometry_changed",
			 G_CALLBACK(on_viewport_geometry_changed), tree);
	g_signal_connect(view, "filter_changed",
			 G_CALLBACK(on_viewport_filter_changed), tree);
	g_object_ref_sink(view);

	if (diversity_viewport_get_enabled(view))
		world_tree_pick(tree, DIVERSITY_OBJECT(view), viewport_pick);

	return TRUE;
}

gboolean world_tree_remove_viewport(WorldTree *tree, DiversityViewport *view)
{
	GSList *tmp;

	tmp = g_slist_find(tree->viewports, view);
	g_return_val_if_fail(tmp, FALSE);

	g_signal_handlers_disconnect_by_func(view,
			on_viewport_filter_changed, tree);
	g_signal_handlers_disconnect_by_func(view,
			on_viewport_geometry_changed, tree);
	g_signal_handlers_disconnect_by_func(view,
			on_viewport_enabled, tree);

	tree->viewports = g_slist_delete_link(tree->viewports, tmp);
	diversity_viewport_clear_objects(view);
	g_object_unref(view);

	return TRUE;
}

static gboolean tree_traverse(GNode *n, gpointer data)
{
	TraversePicker *tp = data;
	DiversityNode *dn = n->data;
	GSList *tmp_list;

	tmp_list = dn->objects;
	while (tmp_list) {
		DiversityObject *obj = tmp_list->data;
		
		if (tp->picker->ubiquitous ||
		    diversity_object_intersect(tp->picker, obj))
			tp->func(tp->picker, obj);

		tmp_list = g_slist_next(tmp_list);
	}

	return FALSE;
}

void world_tree_pick(WorldTree *tree, DiversityObject *picker, WorldTreePickFunc func)
{
	TraversePicker tp;
	GNode *n;

	tp.picker = picker;
	tp.func = func;

	n = node_pose(tree->root, picker);
	g_node_traverse(n, G_IN_ORDER, G_TRAVERSE_ALL, -1, tree_traverse, &tp);

	n = n->parent;
	while (n) {
		tree_traverse(n, &tp);
		n = n->parent;
	}
}

#ifdef WORLD_TREE_DEBUG
static gboolean node_dump(GNode *n, gpointer data)
{
	DiversityNode *dn = n->data;
	gchar indent[32 + 1];
	guint depth;

	depth = g_node_depth(n);
	if (!depth || depth > 32)
		return FALSE;

	indent[depth] = '\0';
	while (depth--)
		indent[depth] = '\t';

	g_print("%sNODE(%.2f, %.2f, %.2f, %.2f) has %d object(s)\n",
			indent,
			dn->rect.x, dn->rect.y,
			dn->rect.width, dn->rect.height,
			g_slist_length(dn->objects));

	return FALSE;
}

void world_tree_dump(WorldTree *tree)
{
	GSList *tmp_list;

	g_node_traverse(tree->root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, node_dump, NULL);

	tmp_list = tree->viewports;
	while (tmp_list) {
		DiversityViewport *view = tmp_list->data;
		DiversityRectangle rect;

		diversity_object_geometry_get(DIVERSITY_OBJECT(view), &rect.x, &rect.y, &rect.width, &rect.height);
		
		g_print("\tVIEW(%.2f, %.2f, %.2f, %.2f) has %d object(s)\n",
				rect.x, rect.y,
				rect.width, rect.height,
				diversity_viewport_count_objects(view));

		tmp_list = g_slist_next(tmp_list);
	}
}
#endif /* WORLD_TREE_DEBUG */