/* dia-solver.c
 * Copyright (C) 2001  Arjan Molenaar
 *
 * 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 "dia-solver.h"
#include "dia-canvas-i18n.h"

///#define D(msg) G_STMT_START { g_print (G_STRLOC": "); g_print msg; g_print ("\n"); } G_STMT_END
#define D(msg)

enum
{
	LAST_SIGNAL
};

static void dia_solver_init		(DiaSolver		*solver);
static void dia_solver_class_init	(DiaSolverClass		*klass);
static void dia_solver_finalize		(GObject		*object);
static void dia_solver_set_property	(GObject		*object,
					 guint			 property_id,
					 const GValue		*value,
					 GParamSpec		*pspec);
static void dia_solver_get_property	(GObject		*object,
					 guint			 property_id,
					 GValue			*value,
					 GParamSpec		*pspec);

static inline void mark_constraint	(DiaSolver		*solver,
					 DiaConstraint		*constraint);
static inline void unmark_constraint	(DiaSolver		*solver,
					 DiaConstraint		*constraint);
static void unmark_destroyed_constraint	(DiaSolver		*solver,
					 DiaConstraint		*constraint);
static inline void mark_variable	(DiaSolver		*solver,
					 DiaVariable		*var);
static inline void mark_variable_internal (DiaSolver		*solver,
					 DiaVariable		*var);
static inline void unmark_variable	(DiaSolver		*solver,
					 DiaVariable		*var);
static void unmark_destroyed_variable	(DiaSolver		*solver,
					 DiaVariable		*var);

static void need_resolve_cb		(DiaConstraint		*con,
					 DiaVariable		*var,
					 DiaSolver		*sol);

static GObjectClass *parent_class = NULL;
//static guint signals[LAST_SIGNAL] = { 0 };

GType
dia_solver_get_type (void)
{
	static GType object_type = 0;

	if (!object_type) {
		static const GTypeInfo object_info = {
			sizeof (DiaSolverClass),
			(GBaseInitFunc) NULL,
			(GBaseFinalizeFunc) NULL,
			(GClassInitFunc) dia_solver_class_init,
			(GClassFinalizeFunc) NULL,
			(gconstpointer) NULL, /* class_data */
			sizeof (DiaSolver),
			(guint16) 0, /* n_preallocs */
			(GInstanceInitFunc) dia_solver_init,
		};
		object_type = g_type_register_static (G_TYPE_OBJECT,
						      "DiaSolver",
						      &object_info,
						      0);
	}

	return object_type;
}


static void
dia_solver_class_init (DiaSolverClass *klass)
{
	GObjectClass *object_class;

	object_class = (GObjectClass*) klass;

	parent_class = g_type_class_peek_parent (klass);

	object_class->finalize = dia_solver_finalize;
	object_class->set_property = dia_solver_set_property;
	object_class->get_property = dia_solver_get_property;

	/*signals[CHANGED] = 
	  g_signal_new ("changed",
			G_TYPE_FROM_CLASS (klass),
			G_SIGNAL_RUN_LAST,
			G_STRUCT_OFFSET (DiaSolverClass, changed),
			NULL, NULL,
			dia_solver_marshal_VOID__VOID,
			G_TYPE_NONE, 0); */
}


static void
dia_solver_init (DiaSolver *solver)
{
	solver->constraints = NULL;

	solver->marked_cons = NULL;
	solver->marked_vars = NULL;
	solver->current_con = NULL;
}

static void
dia_solver_finalize (GObject *object)
{
	DiaSolver *solver = (DiaSolver*) object;

	while (solver->constraints)
		dia_solver_remove_constraint (solver, solver->constraints->data);

	while (solver->marked_cons)
		unmark_constraint (solver, solver->marked_cons->data);

	while (solver->marked_vars)
		unmark_variable (solver, solver->marked_vars->data);

	parent_class->finalize (object);
}

static void
dia_solver_set_property (GObject *object, guint property_id,
			 const GValue *value, GParamSpec *pspec)
{
	switch (property_id) {
	default:
		G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
		break;
	}
}

static void
dia_solver_get_property (GObject *object, guint property_id,
			 GValue *value, GParamSpec *pspec)
{
	switch (property_id) {
	default:
		G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
	}
}

/**
 * mark_constraint:
 * @solver: 
 * @con: 
 *
 * Add a constraint to the marked_cons list. It will be resolved.
 **/
static inline void
mark_constraint (DiaSolver *solver, DiaConstraint *con)
{
	if (g_slist_find (solver->marked_cons, con))
		return;

	solver->marked_cons = g_slist_append (solver->marked_cons, con);
	g_object_weak_ref (G_OBJECT (con),
			   (GWeakNotify) unmark_destroyed_constraint,
			   solver);
}

static inline void
unmark_constraint (DiaSolver *solver, DiaConstraint *con)
{
	solver->marked_cons = g_slist_remove (solver->marked_cons, con);
	g_object_weak_unref (G_OBJECT (con),
			     (GWeakNotify) unmark_destroyed_constraint,
			     solver);
}

static void
unmark_destroyed_constraint (DiaSolver *solver, DiaConstraint *con)
{
	solver->marked_cons = g_slist_remove (solver->marked_cons, con);
}

/**
 * mark_variable:
 * @solver: 
 * @var: 
 *
 * All variables that are edited (by the user and by the solver) are added to
 * a list, do they can fire the %changed signal when the solver is done.
 **/
static inline void
mark_variable (DiaSolver *solver, DiaVariable *var)
{
	if (g_slist_find (solver->marked_vars, var))
		return;

	solver->marked_vars = g_slist_append (solver->marked_vars, var);
	g_object_weak_ref (G_OBJECT (var),
			   (GWeakNotify) unmark_destroyed_variable,
			   solver);
}

static inline void
mark_variable_internal (DiaSolver *solver, DiaVariable *var)
{
	if (g_slist_find (solver->marked_vars, var))
		return;

	solver->marked_vars = g_slist_prepend (solver->marked_vars, var);
	g_object_weak_ref (G_OBJECT (var),
			   (GWeakNotify) unmark_destroyed_variable,
			   solver);
}

static inline void
unmark_variable (DiaSolver *solver, DiaVariable *var)
{
	solver->marked_vars = g_slist_remove (solver->marked_vars, var);
	g_object_weak_unref (G_OBJECT (var),
			     (GWeakNotify) unmark_destroyed_variable,
			     solver);
}

static void
unmark_destroyed_variable (DiaSolver *solver, DiaVariable *var)
{
	solver->marked_vars = g_slist_remove (solver->marked_vars, var);
}

static void
need_resolve_cb (DiaConstraint *con, DiaVariable *var, DiaSolver *sol)
{
	if (sol->current_con != con) {
		mark_constraint (sol, con);
		mark_variable (sol, var);
	}
}


/**
 * dia_solver_new:
 *
 * Create a new, empty constaint solver.
 *
 * Return value: A new constraint solver.
 **/
DiaSolver*
dia_solver_new (void)
{
	return g_object_new (DIA_TYPE_SOLVER, NULL);
}


static void
add_variable_to_marked_vars (DiaConstraint *con, DiaVariable *var, gdouble c,
			     gpointer solver)
{
	if (var)
		mark_variable (solver, var);
}

/**
 * dia_solver_add_constraint:
 * @solver: 
 * @constraint: 
 *
 * Add @constraint to @solver. The constraint is marked immutable.
 **/
void
dia_solver_add_constraint (DiaSolver *solver, DiaConstraint *constraint)
{
	g_return_if_fail (DIA_IS_SOLVER (solver));
	g_return_if_fail (DIA_IS_CONSTRAINT (constraint));
	g_return_if_fail (dia_constraint_has_variables (constraint));

	if (solver->constraints
	    && (g_list_find (solver->constraints, constraint) != NULL)) {
		g_warning (_("Tried to add a constraint multiple times to the solver."));
		return;
	}

	g_object_ref (constraint);
	dia_constraint_optimize (constraint);
	dia_constraint_freeze (constraint);
	
	solver->constraints = g_list_append (solver->constraints, constraint);
	mark_constraint (solver, constraint);
	
	dia_constraint_foreach (constraint, add_variable_to_marked_vars,
				solver);

	g_signal_connect (constraint, "need_resolve",
			  G_CALLBACK (need_resolve_cb), solver);
}

/**
 * dia_solver_remove_constraint:
 * @solver: 
 * @constraint: 
 *
 * Remove @constraint from the solver.
 **/
void
dia_solver_remove_constraint (DiaSolver *solver, DiaConstraint *constraint)
{
	g_return_if_fail (DIA_IS_SOLVER (solver));
	g_return_if_fail (DIA_IS_CONSTRAINT (constraint));
	g_return_if_fail (g_list_find (solver->constraints, constraint));
	
	solver->constraints = g_list_remove (solver->constraints, constraint);
	dia_constraint_thaw (constraint);

	if (g_slist_find (solver->marked_cons, constraint))
		unmark_constraint (solver, constraint);

	g_signal_handlers_disconnect_by_func (constraint,
					      G_CALLBACK (need_resolve_cb),
					      solver);
	g_object_unref (constraint);
}

/**
 * find_weakest_variable:
 * @solver: 
 * @con: 
 * @wvar: [OUT] weakest variable
 *
 * Find the weakest variable in a constraint. The variable with the weakest
 * priority will be put in @wvar. Variables that are also edited will have
 * a slightly increated strength over variables who have not been edited.
 * If more edited variables have been found with the same strength, the variable
 * that was first edited will be the weakest.
 * 
 * Note that only one variable is returned. This could lead to not so
 * nice solutions.  Maybe we should create a list of weakest variables.
 * 
 * Return value: TRUE if the weakest variable is in the marked_vars list,
 * 		 FALSE otherwise.
 **/
static gboolean
find_weakest_variable (DiaSolver *solver, DiaConstraint *con, DiaVariable **wvar)
{
	guint i;
	gint eindex = G_MAXINT;
	DiaVariable *nevar = NULL; /* Not edited variable */
	DiaVariable *evar = NULL; /* Edited variable */

	for (i = 0; i < con->expr->len; i++) {
		DiaVariable *v = con->expr->elem[i].variable;
		register gint index = g_slist_index (solver->marked_vars, v);

		if (!v)
			continue;

		/* Find the weakest non-edit variable. The weakest edited
		 * variable depends on its strength and the index in the
		 * solver->marked_vars list. */

		if ((index == -1) && ((nevar == NULL)
				      || (nevar->strength > v->strength))) {
			nevar = v;
		} else if ((evar == NULL)
			   || (evar->strength > v->strength)
			   || ((evar->strength == v->strength)
				&& (index < eindex))) {
			evar = v;
			eindex = index;
		}
	}

	if (nevar) {
		if (evar) {
			if (evar->strength < nevar->strength)
				*wvar = evar;
			else
				*wvar = nevar;
		} else
			*wvar = nevar;
	} else
		*wvar = evar;
	
	if (*wvar == NULL) {
		g_warning ("No editable variable found in constraint.");
		return FALSE;
	}

	if (*wvar == evar)
		return TRUE;

	return FALSE;
}

/**
 * dia_solver_resolve:
 * @solver: 
 *
 * Try to make all constraints true. 
 **/
void
dia_solver_resolve (DiaSolver *solver)
{
	static guint changed_signal = 0;
	DiaVariable *wvar = NULL;
	DiaConstraint *con;
	GSList *cyclic = NULL;
	gdouble new_val;

	if (!changed_signal)
		changed_signal = g_signal_lookup ("changed", DIA_TYPE_VARIABLE);

	/* foreach (infeasable constraint) {
	 * 1	remove the constraint from the marked_cons list
	 * 2	find  the weakest variable that is not in the
	 * 	solver->marked_vars list. If no such variable can be
	 * 	found, return the overall weakest and add the constraint to the
	 * 	cyclic list (so it will not be solved again).
	 * 	wvar = find_weakest_var (solver, constraint)
	 * 3	make constraint = 0, by changing wvar. signals
	 *	to constraint are blocked by using current_con.
	 *	solve_constraint (constraint, wvar);
	 * }
	 */

	while (solver->marked_cons) {
		con = solver->marked_cons->data;
		solver->current_con = con;

		/* remove from list */
		unmark_constraint (solver, con);

		/* Skip the constraint if it is already solved using an edited
		 * variable. */
		if (g_slist_find (cyclic, con))
			continue;

		if (find_weakest_variable (solver, con, &wvar))
			cyclic = g_slist_prepend (cyclic, con);

		if (wvar) {
			new_val = dia_constraint_solve (con, wvar);
			if (dia_variable_get_value (wvar) != new_val) {
				dia_variable_set_value (wvar, new_val);
				mark_variable_internal (solver, wvar);
			}
		}
	}
	
	/* Cleanup: */
	g_slist_free (cyclic);

	while (solver->marked_cons)
		unmark_constraint (solver, solver->marked_cons->data);

	while (solver->marked_vars) {
		g_signal_emit (solver->marked_vars->data, changed_signal, 0);
		unmark_variable (solver, solver->marked_vars->data);
	}

	solver->current_con = NULL;
}