1	/* gtkconstraintsolver.c: Constraint solver based on the Cassowary method
2	* Copyright 2019 GNOME Foundation
3	*
4	* SPDX-License-Identifier: LGPL-2.1-or-later
5	*
6	* This library is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU Lesser General Public
8	* License as published by the Free Software Foundation; either
9	* version 2.1 of the License, or (at your option) any later version.
10	*
11	* This library is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14	* Lesser General Public License for more details.
15	*
16	* You should have received a copy of the GNU Lesser General Public
17	* License along with this library. If not, see <http://www.gnu.org/licenses/>.
18	*
19	* Author: Emmanuele Bassi
20	*/
21
22	/*< private >
23	* GtkConstraintSolver
24	*
25	* GtkConstraintSolver is an object that encodes constraints into a tableau
26	* of linear equations and solves them, using an incremental optimization
27	* algorithm known as the "Cassowary Linear Arithmetic Constraint Solving
28	* Algorithm" (Badros, Borning & Stuckey 2001).
29	*
30	* Each constraint is expressed as a linear equation, whose terms are variables
31	* containing widget attributes like the width, height, or position; the simplex
32	* solver takes all the constraints and incrementally optimizes the tableau to
33	* replace known terms; additionally, the algorithm will try to assign a value
34	* to all remaining variables in order to satisfy the various constraints.
35	*
36	* Each constraint is given a "strength", which determines whether satisfying
37	* the constraint is required in order to solve the tableau or not.
38	*
39	* A typical example of GtkConstraintSolver use is solving the following
40	* system of constraints:
41	*
42	* - [required] right = left + 10
43	* - [required] right ≤ 100
44	* - [required] middle = left + right / 2
45	* - [required] left ≥ 0
46	*
47	* Once we create a GtkConstraintSolver instance, we need to create the
48	* various variables and expressions that represent the values we want to
49	* compute and the constraints we wish to impose on the solutions:
50	*
51	* |[
52	* GtkConstraintSolver *solver = gtk_constraint_solver_new ();
53	*
54	* // Our variables
55	* GtkConstraintVariable *left =
56	* gtk_constraint_solver_create_variable (solver, NULL, "left", 0.0);
57	* GtkConstraintVariable *middle =
58	* gtk_constraint_solver_create_variable (solver, NULL, "middle", 0.0);
59	* GtkConstraintVariable *right =
60	* gtk_constraint_solver_create_variable (solver, NULL, "right", 0.0);
61	*
62	* // Our constraints
63	* GtkConstraintExpressionBuilder builder;
64	* GtkConstraintExpression *e;
65	*
66	* // right = left + 10
67	* gtk_constraint_expression_builder_init (&builder, solver);
68	* gtk_constraint_expression_builder_term (&builder, left);
69	* gtk_constraint_expression_builder_plus (&builder);
70	* gtk_constraint_expression_builder_constant (&builder, 10.0);
71	* e = gtk_constraint_expression_builder_finish (&builder);
72	* gtk_constraint_solver_add_constraint (solver,
73	* right, GTK_CONSTRAINT_RELATION_EQ, e,
74	* GTK_CONSTRAINT_STRENGTH_REQUIRED);
75	*
76	* // right ≤ 100
77	* gtk_constraint_expression_builder_constant (&builder, 100.0);
78	* e = gtk_constraint_expression_builder_finish (&builder);
79	* gtk_constraint_solver_add_constraint (solver,
80	* right, GTK_CONSTRAINT_RELATION_LE, e,
81	* GTK_CONSTRAINT_STRENGTH_REQUIRED);
82	*
83	* // middle = (left + right) / 2
84	* gtk_constraint_expression_builder_term (&builder, left);
85	* gtk_constraint_expression_builder_plus (&builder)
86	* gtk_constraint_expression_builder_term (&builder, right);
87	* gtk_constraint_expression_builder_divide_by (&builder);
88	* gtk_constraint_expression_builder_constant (&builder, 2.0);
89	* e = gtk_constraint_expression_builder_finish (&builder);
90	* gtk_constraint_solver_add_constraint (solver
91	* middle, GTK_CONSTRAINT_RELATION_EQ, e,
92	* GTK_CONSTRAINT_STRENGTH_REQUIRED);
93	*
94	* // left ≥ 0
95	* gtk_constraint_expression_builder_constant (&builder, 0.0);
96	* e = gtk_constraint_expression_builder_finish (&builder);
97	* gtk_constraint_solver_add_constraint (solver,
98	* left, GTK_CONSTRAINT_RELATION_GE, e,
99	* GTK_CONSTRAINT_STRENGTH_REQUIRED);
100	* ]|
101	*
102	* Now that we have all our constraints in place, suppose we wish to find
103	* the values of `left` and `right` if we specify the value of `middle`. In
104	* order to do that, we need to add an additional "stay" constraint, i.e.
105	* a constraint that tells the solver to optimize for the solution that keeps
106	* the variable in place:
107	*
108	* |[
109	* // Set the value first
110	* gtk_constraint_variable_set_value (middle, 45.0);
111	* // and then add the stay constraint, with a weak strength
112	* gtk_constraint_solver_add_stay_variable (solver, middle, GTK_CONSTRAINT_STRENGTH_WEAK);
113	* ]|
114	*
115	* GtkConstraintSolver incrementally solves the system every time a constraint
116	* is added or removed, so it's possible to query the values of the variables
117	* immediately afterward:
118	*
119	* |[
120	* double left_val = gtk_constraint_variable_get_value (left);
121	* double right_val = gtk_constraint_variable_get_value (right);
122	* double middle_val = gtk_constraint_variable_get_value (middle);
123	*
124	* // These are the values computed by the solver:
125	* g_assert_cmpfloat_with_epsilon (left_val, 40.0, 0.001);
126	* g_assert_cmpfloat_with_epsilon (middle_val, 45.0, 0.001);
127	* g_assert_cmpfloat_with_epsilon (right_val, 50.0, 0.001);
128	* ]|
129	*
130	* As you can see:
131	*
132	* - the middle value hasn't changed
133	* - the left value is ≥ 0
134	* - the right value is ≤ 100
135	* - the right value is left + 10
136	* - the middle value is (left + right) / 2.0
137	*
138	* For more information about the Cassowary constraint solving algorithm and
139	* toolkit, see the following papers:
140	*
141	* - Badros G & Borning A, 1998, 'Cassowary Linear Arithmetic Constraint
142	* Solving Algorithm: Interface and Implementation', Technical Report
143	* UW-CSE-98-06-04, June 1998 (revised July 1999)
144	* https://constraints.cs.washington.edu/cassowary/cassowary-tr.pdf
145	* - Badros G, Borning A & Stuckey P, 2001, 'Cassowary Linear Arithmetic
146	* Constraint Solving Algorithm', ACM Transactions on Computer-Human
147	* Interaction, vol. 8 no. 4, December 2001, pages 267-306
148	* https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf
149	*
150	* The following implementation is based on these projects:
151	*
152	* - the original [C++ implementation](https://sourceforge.net/projects/cassowary/)
153	* - the JavaScript port [Cassowary.js](https://github.com/slightlyoff/cassowary.js)
154	* - the Python port [Cassowary](https://github.com/pybee/cassowary)
155	*/
156
157	#include "config.h"
158
159	#include "gtkconstraintsolverprivate.h"
160	#include "gtkconstraintexpressionprivate.h"
161
162	#include "gtkdebug.h"
163
164	#include <glib.h>
165	#include <string.h>
166	#include <math.h>
167	#include <float.h>
168
169	struct _GtkConstraintRef
170	{
171	/* The constraint's normal form inside the solver:
172	*
173	* x - (y × coefficient + constant) = 0
174	*
175	* We only use equalities, and replace inequalities with slack
176	* variables.
177	*/
178	GtkConstraintExpression *expression;
179
180	/* A constraint variable, only used by stay and edit constraints */
181	GtkConstraintVariable *variable;
182
183	/* The original relation used when creating the constraint */
184	GtkConstraintRelation relation;
185
186	/* The strength of the constraint; this value is used to strengthen
187	* or weaken a constraint weight in the tableau when coming to a
188	* solution
189	*/
190	int strength;
191
192	GtkConstraintSolver *solver;
193
194	guint is_edit : 1;
195	guint is_stay : 1;
196	};
197
198	typedef struct {
199	GtkConstraintRef *constraint;
200
201	GtkConstraintVariable *eplus;
202	GtkConstraintVariable *eminus;
203
204	double prev_constant;
205	} EditInfo;
206
207	typedef struct {
208	GtkConstraintRef *constraint;
209	} StayInfo;
210
211	struct _GtkConstraintSolver
212	{
213	GObject parent_instance;
214
215	/* HashTable<Variable, VariableSet>; owns keys and values */
216	GHashTable *columns;
217	/* HashTable<Variable, Expression>; owns keys and values */
218	GHashTable *rows;
219
220	/* Set<Variable>; does not own keys */
221	GHashTable *external_rows;
222	/* Set<Variable>; does not own keys */
223	GHashTable *external_parametric_vars;
224
225	/* Vec<Variable> */
226	GPtrArray *infeasible_rows;
227	/* Vec<VariablePair>; owns the pair */
228	GPtrArray *stay_error_vars;
229
230	/* HashTable<Constraint, VariableSet>; owns the set */
231	GHashTable *error_vars;
232	/* HashTable<Constraint, Variable> */
233	GHashTable *marker_vars;
234
235	/* HashTable<Variable, EditInfo>; does not own keys, but owns values */
236	GHashTable *edit_var_map;
237	/* HashTable<Variable, StayInfo>; does not own keys, but owns values */
238	GHashTable *stay_var_map;
239
240	GtkConstraintVariable *objective;
241
242	/* Set<Constraint>; owns the key */
243	GHashTable *constraints;
244
245	/* Counters */
246	int var_counter;
247	int slack_counter;
248	int artificial_counter;
249	int dummy_counter;
250	int optimize_count;
251	int freeze_count;
252
253	/* Bitfields; keep at the end */
254	guint auto_solve : 1;
255	guint needs_solving : 1;
256	guint in_edit_phase : 1;
257	};
258
259	static void gtk_constraint_ref_free (GtkConstraintRef *ref);
260	static void edit_info_free (gpointer data);
261
262	G_DEFINE_TYPE (GtkConstraintSolver, gtk_constraint_solver, G_TYPE_OBJECT)
263
264	static void
265	gtk_constraint_solver_finalize (GObject *gobject)
266	{
267	GtkConstraintSolver *self = GTK_CONSTRAINT_SOLVER (ptr: gobject);
268
269	g_hash_table_remove_all (hash_table: self->constraints);
270	g_clear_pointer (&self->constraints, g_hash_table_unref);
271
272	g_clear_pointer (&self->stay_error_vars, g_ptr_array_unref);
273	g_clear_pointer (&self->infeasible_rows, g_ptr_array_unref);
274
275	g_clear_pointer (&self->external_rows, g_hash_table_unref);
276	g_clear_pointer (&self->external_parametric_vars, g_hash_table_unref);
277	g_clear_pointer (&self->error_vars, g_hash_table_unref);
278	g_clear_pointer (&self->marker_vars, g_hash_table_unref);
279	g_clear_pointer (&self->edit_var_map, g_hash_table_unref);
280	g_clear_pointer (&self->stay_var_map, g_hash_table_unref);
281
282	g_clear_pointer (&self->rows, g_hash_table_unref);
283	g_clear_pointer (&self->columns, g_hash_table_unref);
284
285	G_OBJECT_CLASS (gtk_constraint_solver_parent_class)->finalize (gobject);
286	}
287
288	static void
289	gtk_constraint_solver_class_init (GtkConstraintSolverClass *klass)
290	{
291	GObjectClass *gobject_class = G_OBJECT_CLASS (klass);
292
293	gobject_class->finalize = gtk_constraint_solver_finalize;
294	}
295
296	static void
297	gtk_constraint_solver_init (GtkConstraintSolver *self)
298	{
299	self->columns =
300	g_hash_table_new_full (NULL, NULL,
301	key_destroy_func: (GDestroyNotify) gtk_constraint_variable_unref,
302	value_destroy_func: (GDestroyNotify) gtk_constraint_variable_set_free);
303
304	self->rows =
305	g_hash_table_new_full (NULL, NULL,
306	key_destroy_func: (GDestroyNotify) gtk_constraint_variable_unref,
307	value_destroy_func: (GDestroyNotify) gtk_constraint_expression_unref);
308
309	self->external_rows = g_hash_table_new (NULL, NULL);
310
311	self->external_parametric_vars = g_hash_table_new (NULL, NULL);
312
313	self->infeasible_rows = g_ptr_array_new ();
314
315	self->stay_error_vars =
316	g_ptr_array_new_with_free_func (element_free_func: (GDestroyNotify) gtk_constraint_variable_pair_free);
317
318	self->error_vars =
319	g_hash_table_new_full (NULL, NULL,
320	NULL,
321	value_destroy_func: (GDestroyNotify) gtk_constraint_variable_set_free);
322
323	self->marker_vars = g_hash_table_new (NULL, NULL);
324
325	self->edit_var_map = g_hash_table_new_full (NULL, NULL,
326	NULL,
327	value_destroy_func: edit_info_free);
328
329	self->stay_var_map = g_hash_table_new_full (NULL, NULL,
330	NULL,
331	value_destroy_func: g_free);
332
333	/* The rows table owns the objective variable */
334	self->objective = gtk_constraint_variable_new_objective (name: "Z");
335	g_hash_table_insert (hash_table: self->rows,
336	key: self->objective,
337	value: gtk_constraint_expression_new (constant: 0.0));
338
339	self->constraints =
340	g_hash_table_new_full (NULL, NULL,
341	key_destroy_func: (GDestroyNotify) gtk_constraint_ref_free,
342	NULL);
343
344	self->slack_counter = 0;
345	self->dummy_counter = 0;
346	self->artificial_counter = 0;
347	self->freeze_count = 0;
348
349	self->needs_solving = FALSE;
350	self->auto_solve = TRUE;
351	}
352
353	static void
354	gtk_constraint_ref_free (GtkConstraintRef *self)
355	{
356	gtk_constraint_solver_remove_constraint (solver: self->solver, reference: self);
357
358	gtk_constraint_expression_unref (expression: self->expression);
359
360	if (self->is_edit || self->is_stay)
361	{
362	g_assert (self->variable != NULL);
363	gtk_constraint_variable_unref (variable: self->variable);
364	}
365
366	g_free (mem: self);
367	}
368
369	static gboolean
370	gtk_constraint_ref_is_inequality (const GtkConstraintRef *self)
371	{
372	return self->relation != GTK_CONSTRAINT_RELATION_EQ;
373	}
374
375	static gboolean
376	gtk_constraint_ref_is_required (const GtkConstraintRef *self)
377	{
378	return self->strength == GTK_CONSTRAINT_STRENGTH_REQUIRED;
379	}
380
381	static const char *relations[] = {
382	"<=",
383	"==",
384	">=",
385	};
386
387	static const char *
388	relation_to_string (GtkConstraintRelation r)
389	{
390	return relations[r + 1];
391	}
392
393	static const char *
394	strength_to_string (int s)
395	{
396	if (s >= GTK_CONSTRAINT_STRENGTH_STRONG)
397	return "strong";
398
399	if (s >= GTK_CONSTRAINT_STRENGTH_MEDIUM)
400	return "medium";
401
402	return "weak";
403	}
404
405	static char *
406	gtk_constraint_ref_to_string (const GtkConstraintRef *self)
407	{
408	GString *buf = g_string_new (NULL);
409	char *str;
410
411	if (self->is_stay)
412	g_string_append (string: buf, val: "[stay]");
413	else if (self->is_edit)
414	g_string_append (string: buf, val: "[edit]");
415
416	str = gtk_constraint_expression_to_string (expression: self->expression);
417	g_string_append (string: buf, val: str);
418	g_free (mem: str);
419
420	g_string_append_c (buf, ' ');
421	g_string_append (string: buf, val: relation_to_string (r: self->relation));
422	g_string_append (string: buf, val: " 0.0");
423
424	if (gtk_constraint_ref_is_required (self))
425	g_string_append (string: buf, val: " [strength:required]");
426	else
427	g_string_append_printf (string: buf, format: " [strength:%d (%s)]",
428	self->strength,
429	strength_to_string (s: self->strength));
430
431	return g_string_free (string: buf, FALSE);
432	}
433
434	static GtkConstraintVariableSet *
435	gtk_constraint_solver_get_column_set (GtkConstraintSolver *self,
436	GtkConstraintVariable *param_var)
437	{
438	return g_hash_table_lookup (hash_table: self->columns, key: param_var);
439	}
440
441	static gboolean
442	gtk_constraint_solver_column_has_key (GtkConstraintSolver *self,
443	GtkConstraintVariable *subject)
444	{
445	return g_hash_table_contains (hash_table: self->columns, key: subject);
446	}
447
448	static void
449	gtk_constraint_solver_insert_column_variable (GtkConstraintSolver *self,
450	GtkConstraintVariable *param_var,
451	GtkConstraintVariable *row_var)
452	{
453	GtkConstraintVariableSet *cset = g_hash_table_lookup (hash_table: self->columns, key: param_var);
454
455	if (cset == NULL)
456	{
457	cset = gtk_constraint_variable_set_new ();
458	g_hash_table_insert (hash_table: self->columns, key: gtk_constraint_variable_ref (variable: param_var), value: cset);
459	}
460
461	if (row_var != NULL)
462	gtk_constraint_variable_set_add (set: cset, variable: row_var);
463	}
464
465	static void
466	gtk_constraint_solver_insert_error_variable (GtkConstraintSolver *self,
467	GtkConstraintRef *constraint,
468	GtkConstraintVariable *variable)
469	{
470	GtkConstraintVariableSet *cset = g_hash_table_lookup (hash_table: self->error_vars, key: constraint);
471
472	if (cset == NULL)
473	{
474	cset = gtk_constraint_variable_set_new ();
475	g_hash_table_insert (hash_table: self->error_vars, key: constraint, value: cset);
476	}
477
478	gtk_constraint_variable_set_add (set: cset, variable);
479	}
480
481	static void
482	gtk_constraint_solver_reset_stay_constants (GtkConstraintSolver *self)
483	{
484	int i;
485
486	for (i = 0; i < self->stay_error_vars->len; i++)
487	{
488	GtkConstraintVariablePair *pair = g_ptr_array_index (self->stay_error_vars, i);
489	GtkConstraintExpression *expression;
490
491	expression = g_hash_table_lookup (hash_table: self->rows, key: pair->first);
492
493	if (expression == NULL)
494	expression = g_hash_table_lookup (hash_table: self->rows, key: pair->second);
495
496	if (expression != NULL)
497	gtk_constraint_expression_set_constant (expression, constant: 0.0);
498	}
499	}
500
501	static void
502	gtk_constraint_solver_set_external_variables (GtkConstraintSolver *self)
503	{
504	GHashTableIter iter;
505	gpointer key_p;
506
507	g_hash_table_iter_init (iter: &iter, hash_table: self->external_parametric_vars);
508	while (g_hash_table_iter_next (iter: &iter, key: &key_p, NULL))
509	{
510	GtkConstraintVariable *variable = key_p;
511
512	if (g_hash_table_contains (hash_table: self->rows, key: variable))
513	continue;
514
515	gtk_constraint_variable_set_value (variable, value: 0.0);
516	}
517
518	g_hash_table_iter_init (iter: &iter, hash_table: self->external_rows);
519	while (g_hash_table_iter_next (iter: &iter, key: &key_p, NULL))
520	{
521	GtkConstraintVariable *variable = key_p;
522	GtkConstraintExpression *expression;
523	double constant;
524
525	expression = g_hash_table_lookup (hash_table: self->rows, key: variable);
526	constant = gtk_constraint_expression_get_constant (expression);
527
528	gtk_constraint_variable_set_value (variable, value: constant);
529	}
530
531	self->needs_solving = FALSE;
532	}
533
534	static void
535	gtk_constraint_solver_add_row (GtkConstraintSolver *self,
536	GtkConstraintVariable *variable,
537	GtkConstraintExpression *expression)
538	{
539	GtkConstraintExpressionIter iter;
540	GtkConstraintVariable *t_v;
541	double t_c;
542
543	g_hash_table_insert (hash_table: self->rows,
544	key: gtk_constraint_variable_ref (variable),
545	value: gtk_constraint_expression_ref (expression));
546
547	gtk_constraint_expression_iter_init (iter: &iter, equation: expression);
548	while (gtk_constraint_expression_iter_next (iter: &iter, variable: &t_v, coefficient: &t_c))
549	{
550	gtk_constraint_solver_insert_column_variable (self, param_var: t_v, row_var: variable);
551
552	if (gtk_constraint_variable_is_external (variable: t_v))
553	g_hash_table_add (hash_table: self->external_parametric_vars, key: t_v);
554	}
555
556	if (gtk_constraint_variable_is_external (variable))
557	g_hash_table_add (hash_table: self->external_rows, key: variable);
558	}
559
560	static void
561	gtk_constraint_solver_remove_column (GtkConstraintSolver *self,
562	GtkConstraintVariable *variable)
563	{
564	GtkConstraintVariable *v;
565	GtkConstraintVariableSetIter iter;
566	GtkConstraintVariableSet *cset;
567
568	/* Take a reference on the variable, as we're going to remove it
569	* from various maps and we want to guarantee the pointer is
570	* valid until we leave this function
571	*/
572	gtk_constraint_variable_ref (variable);
573
574	cset = g_hash_table_lookup (hash_table: self->columns, key: variable);
575	if (cset == NULL)
576	goto out;
577
578	gtk_constraint_variable_set_iter_init (iter: &iter, set: cset);
579	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &v))
580	{
581	GtkConstraintExpression *e = g_hash_table_lookup (hash_table: self->rows, key: v);
582
583	gtk_constraint_expression_remove_variable (expression: e, variable);
584	}
585
586	g_hash_table_remove (hash_table: self->columns, key: variable);
587
588	out:
589	if (gtk_constraint_variable_is_external (variable))
590	{
591	g_hash_table_remove (hash_table: self->external_rows, key: variable);
592	g_hash_table_remove (hash_table: self->external_parametric_vars, key: variable);
593	}
594
595	gtk_constraint_variable_unref (variable);
596	}
597
598	static GtkConstraintExpression *
599	gtk_constraint_solver_remove_row (GtkConstraintSolver *self,
600	GtkConstraintVariable *variable,
601	gboolean free_res)
602	{
603	GtkConstraintExpression *e;
604	GtkConstraintExpressionIter iter;
605	GtkConstraintVariable *t_v;
606	double t_c;
607
608	e = g_hash_table_lookup (hash_table: self->rows, key: variable);
609	g_assert (e != NULL);
610
611	gtk_constraint_expression_ref (expression: e);
612
613	gtk_constraint_expression_iter_init (iter: &iter, equation: e);
614	while (gtk_constraint_expression_iter_next (iter: &iter, variable: &t_v, coefficient: &t_c))
615	{
616	GtkConstraintVariableSet *cset = g_hash_table_lookup (hash_table: self->columns, key: t_v);
617
618	if (cset != NULL)
619	gtk_constraint_variable_set_remove (set: cset, variable);
620	}
621
622	g_ptr_array_remove (array: self->infeasible_rows, data: variable);
623
624	if (gtk_constraint_variable_is_external (variable))
625	g_hash_table_remove (hash_table: self->external_rows, key: variable);
626
627	g_hash_table_remove (hash_table: self->rows, key: variable);
628
629	if (free_res)
630	{
631	gtk_constraint_expression_unref (expression: e);
632	return NULL;
633	}
634
635	return e;
636	}
637
638	/*< private >
639	* gtk_constraint_solver_substitute_out:
640	* @self: a `GtkConstraintSolver`
641	* @old_variable: a `GtkConstraintVariable`
642	* @expression: a `GtkConstraintExpression`
643	*
644	* Replaces @old_variable in every row of the tableau with @expression.
645	*/
646	static void
647	gtk_constraint_solver_substitute_out (GtkConstraintSolver *self,
648	GtkConstraintVariable *old_variable,
649	GtkConstraintExpression *expression)
650	{
651	GtkConstraintVariableSet *cset = g_hash_table_lookup (hash_table: self->columns, key: old_variable);
652	if (cset != NULL)
653	{
654	GtkConstraintVariableSetIter iter;
655	GtkConstraintVariable *v;
656
657	gtk_constraint_variable_set_iter_init (iter: &iter, set: cset);
658	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &v))
659	{
660	GtkConstraintExpression *row = g_hash_table_lookup (hash_table: self->rows, key: v);
661
662	gtk_constraint_expression_substitute_out (expression: row, out_var: old_variable, expr: expression, subject: v, solver: self);
663
664	if (gtk_constraint_variable_is_restricted (variable: v) &&
665	gtk_constraint_expression_get_constant (expression: row) < 0)
666	g_ptr_array_add (array: self->infeasible_rows, data: v);
667	}
668	}
669
670	if (gtk_constraint_variable_is_external (variable: old_variable))
671	{
672	g_hash_table_add (hash_table: self->external_rows, key: old_variable);
673	g_hash_table_remove (hash_table: self->external_parametric_vars, key: old_variable);
674	}
675
676	g_hash_table_remove (hash_table: self->columns, key: old_variable);
677	}
678
679	/*< private >
680	* gtk_constraint_solver_pivot:
681	* @self: a `GtkConstraintSolver`
682	* @entry_var: a `GtkConstraintVariable`
683	* @exit_var: a `GtkConstraintVariable`
684	*
685	* Pivots the `GtkConstraintSolver`.
686	*
687	* This function will move @entry_var into the basis of the tableau,
688	* making it a basic variable; and move @exit_var out of the basis of
689	* the tableau, making it a parametric variable.
690	*/
691	static void
692	gtk_constraint_solver_pivot (GtkConstraintSolver *self,
693	GtkConstraintVariable *entry_var,
694	GtkConstraintVariable *exit_var)
695	{
696	GtkConstraintExpression *expr;
697
698	if (entry_var != NULL)
699	gtk_constraint_variable_ref (variable: entry_var);
700	else
701	g_critical ("INTERNAL: invalid entry variable during pivot");
702
703	if (exit_var != NULL)
704	gtk_constraint_variable_ref (variable: exit_var);
705	else
706	g_critical ("INTERNAL: invalid exit variable during pivot");
707
708	/* We keep a reference to the expression */
709	expr = gtk_constraint_solver_remove_row (self, variable: exit_var, FALSE);
710
711	gtk_constraint_expression_change_subject (expression: expr, old_subject: exit_var, new_subject: entry_var);
712	gtk_constraint_solver_substitute_out (self, old_variable: entry_var, expression: expr);
713
714	if (gtk_constraint_variable_is_external (variable: entry_var))
715	g_hash_table_remove (hash_table: self->external_parametric_vars, key: entry_var);
716
717	gtk_constraint_solver_add_row (self, variable: entry_var, expression: expr);
718
719	gtk_constraint_variable_unref (variable: entry_var);
720	gtk_constraint_variable_unref (variable: exit_var);
721	gtk_constraint_expression_unref (expression: expr);
722	}
723
724	static void
725	gtk_constraint_solver_optimize (GtkConstraintSolver *self,
726	GtkConstraintVariable *z)
727	{
728	GtkConstraintVariable *entry = NULL, *exit = NULL;
729	GtkConstraintExpression *z_row = g_hash_table_lookup (hash_table: self->rows, key: z);
730
731	#ifdef G_ENABLE_DEBUG
732	gint64 start_time = g_get_monotonic_time ();
733	#endif
734
735	g_assert (z_row != NULL);
736
737	self->optimize_count += 1;
738
739	#ifdef G_ENABLE_DEBUG
740	if (GTK_DEBUG_CHECK (CONSTRAINTS))
741	{
742	char *str = gtk_constraint_variable_to_string (variable: z);
743	g_message ("optimize: %s", str);
744	g_free (mem: str);
745	}
746	#endif
747
748	while (TRUE)
749	{
750	GtkConstraintVariableSet *column_vars;
751	GtkConstraintVariableSetIter viter;
752	GtkConstraintExpressionIter eiter;
753	GtkConstraintVariable *t_v, *v;
754	double t_c;
755	double objective_coefficient = 0.0;
756	double min_ratio;
757
758	gtk_constraint_expression_iter_init (iter: &eiter, equation: z_row);
759	while (gtk_constraint_expression_iter_prev (iter: &eiter, variable: &t_v, coefficient: &t_c))
760	{
761	if (gtk_constraint_variable_is_pivotable (variable: t_v) && t_c < objective_coefficient)
762	{
763	entry = t_v;
764	objective_coefficient = t_c;
765	break;
766	}
767	}
768
769	if (objective_coefficient >= -1e-8)
770	break;
771
772	min_ratio = DBL_MAX;
773
774	column_vars = gtk_constraint_solver_get_column_set (self, param_var: entry);
775	gtk_constraint_variable_set_iter_init (iter: &viter, set: column_vars);
776	while (gtk_constraint_variable_set_iter_next (iter: &viter, variable_p: &v))
777	{
778	if (gtk_constraint_variable_is_pivotable (variable: v))
779	{
780	GtkConstraintExpression *expr = g_hash_table_lookup (hash_table: self->rows, key: v);
781	double coeff = gtk_constraint_expression_get_coefficient (expression: expr, variable: entry);
782
783	if (coeff < 0.0)
784	{
785	double constant = gtk_constraint_expression_get_constant (expression: expr);
786
787	double r = -1.0 * constant / coeff;
788	if (r < min_ratio)
789	{
790	min_ratio = r;
791	exit = v;
792	}
793	}
794	}
795	}
796
797	if (min_ratio == DBL_MAX)
798	{
799	GTK_NOTE (CONSTRAINTS, g_message ("Unbounded objective variable during optimization"));
800	break;
801	}
802
803	#ifdef G_ENABLE_DEBUG
804	if (GTK_DEBUG_CHECK (CONSTRAINTS))
805	{
806	char *entry_s = gtk_constraint_variable_to_string (variable: entry);
807	char *exit_s = gtk_constraint_variable_to_string (variable: exit);
808	g_message ("pivot(entry: %s, exit: %s)", entry_s, exit_s);
809	g_free (mem: entry_s);
810	g_free (mem: exit_s);
811	}
812	#endif
813
814	gtk_constraint_solver_pivot (self, entry_var: entry, exit_var: exit);
815	}
816
817	GTK_NOTE (CONSTRAINTS,
818	g_message ("solver.optimize.time := %.3f ms (pass: %d)",
819	(float) (g_get_monotonic_time () - start_time) / 1000.f,
820	self->optimize_count));
821	}
822
823	/*< private >
824	* gtk_constraint_solver_new_expression:
825	* @self: a `GtkConstraintSolver`
826	* @constraint: a `GtkConstraintRef`
827	* @eplus_p: (out) (optional): the positive error variable
828	* @eminus_p: (out) (optional): the negative error variable
829	* @prev_constant_p: the constant part of the @constraint's expression
830	*
831	* Creates a new expression for the @constraint, replacing
832	* any basic variable with their expressions, and normalizing
833	* the terms to avoid a negative constant.
834	*
835	* If the @constraint is not required, this function will add
836	* error variables with the appropriate weight to the tableau.
837	*
838	* Returns: (transfer full): the new expression for the constraint
839	*/
840	static GtkConstraintExpression *
841	gtk_constraint_solver_new_expression (GtkConstraintSolver *self,
842	GtkConstraintRef *constraint,
843	GtkConstraintVariable **eplus_p,
844	GtkConstraintVariable **eminus_p,
845	double *prev_constant_p)
846	{
847	GtkConstraintExpression *cn_expr = constraint->expression;
848	GtkConstraintExpression *expr;
849	GtkConstraintExpressionIter eiter;
850	GtkConstraintVariable *t_v;
851	double t_c;
852
853	if (eplus_p != NULL)
854	*eplus_p = NULL;
855	if (eminus_p != NULL)
856	*eminus_p = NULL;
857	if (prev_constant_p != NULL)
858	*prev_constant_p = 0.0;
859
860	expr = gtk_constraint_expression_new (constant: gtk_constraint_expression_get_constant (expression: cn_expr));
861
862	gtk_constraint_expression_iter_init (iter: &eiter, equation: cn_expr);
863	while (gtk_constraint_expression_iter_next (iter: &eiter, variable: &t_v, coefficient: &t_c))
864	{
865	GtkConstraintExpression *e = g_hash_table_lookup (hash_table: self->rows, key: t_v);
866
867	if (e == NULL)
868	gtk_constraint_expression_add_variable (expression: expr, variable: t_v, coefficient: t_c, NULL, solver: self);
869	else
870	gtk_constraint_expression_add_expression (a_expr: expr, b_expr: e, n: t_c, NULL, solver: self);
871	}
872
873	if (gtk_constraint_ref_is_inequality (self: constraint))
874	{
875	GtkConstraintVariable *slack_var;
876
877	/* If the constraint is an inequality, we add a slack variable to
878	* turn it into an equality, e.g. from
879	*
880	* expr ≥ 0
881	*
882	* to
883	*
884	* expr - slack = 0
885	*
886	* Additionally, if the constraint is not required we add an
887	* error variable with the weight of the constraint:
888	*
889	* expr - slack + error = 0
890	*/
891	self->slack_counter += 1;
892
893	slack_var = gtk_constraint_variable_new_slack (name: "s");
894	gtk_constraint_expression_set_variable (expression: expr, variable: slack_var, coefficient: -1.0);
895	gtk_constraint_variable_unref (variable: slack_var);
896
897	g_hash_table_insert (hash_table: self->marker_vars, key: constraint, value: slack_var);
898
899	if (!gtk_constraint_ref_is_required (self: constraint))
900	{
901	GtkConstraintExpression *z_row;
902	GtkConstraintVariable *eminus;
903
904	self->slack_counter += 1;
905
906	eminus = gtk_constraint_variable_new_slack (name: "em");
907	gtk_constraint_expression_set_variable (expression: expr, variable: eminus, coefficient: 1.0);
908	gtk_constraint_variable_unref (variable: eminus);
909
910	z_row = g_hash_table_lookup (hash_table: self->rows, key: self->objective);
911	gtk_constraint_expression_set_variable (expression: z_row, variable: eminus, coefficient: constraint->strength);
912
913	gtk_constraint_solver_insert_error_variable (self, constraint, variable: eminus);
914	gtk_constraint_solver_note_added_variable (self, variable: eminus, subject: self->objective);
915	gtk_constraint_variable_unref (variable: eminus);
916	}
917	}
918	else
919	{
920	GtkConstraintVariable *dummy_var;
921
922	if (gtk_constraint_ref_is_required (self: constraint))
923	{
924	/* If the constraint is required, we use a dummy marker variable;
925	* the dummy won't be allowed to enter the basis of the tableau
926	* when pivoting.
927	*/
928	self->dummy_counter += 1;
929
930	dummy_var = gtk_constraint_variable_new_dummy (name: "dummy");
931
932	if (eplus_p != NULL)
933	*eplus_p = dummy_var;
934	if (eminus_p != NULL)
935	*eminus_p = dummy_var;
936	if (prev_constant_p != NULL)
937	*prev_constant_p = gtk_constraint_expression_get_constant (expression: cn_expr);
938
939	gtk_constraint_expression_set_variable (expression: expr, variable: dummy_var, coefficient: 1.0);
940	g_hash_table_insert (hash_table: self->marker_vars, key: constraint, value: dummy_var);
941
942	gtk_constraint_variable_unref (variable: dummy_var);
943	}
944	else
945	{
946	GtkConstraintVariable *eplus, *eminus;
947	GtkConstraintExpression *z_row;
948
949	/* Since the constraint is a non-required equality, we need to
950	* add error variables around it, i.e. turn it from:
951	*
952	* expr = 0
953	*
954	* to:
955	*
956	* expr - eplus + eminus = 0
957	*/
958	self->slack_counter += 1;
959
960	eplus = gtk_constraint_variable_new_slack (name: "ep");
961	eminus = gtk_constraint_variable_new_slack (name: "em");
962
963	gtk_constraint_expression_set_variable (expression: expr, variable: eplus, coefficient: -1.0);
964	gtk_constraint_expression_set_variable (expression: expr, variable: eminus, coefficient: 1.0);
965
966	g_hash_table_insert (hash_table: self->marker_vars, key: constraint, value: eplus);
967
968	z_row = g_hash_table_lookup (hash_table: self->rows, key: self->objective);
969
970	gtk_constraint_expression_set_variable (expression: z_row, variable: eplus, coefficient: constraint->strength);
971	gtk_constraint_expression_set_variable (expression: z_row, variable: eminus, coefficient: constraint->strength);
972	gtk_constraint_solver_note_added_variable (self, variable: eplus, subject: self->objective);
973	gtk_constraint_solver_note_added_variable (self, variable: eminus, subject: self->objective);
974
975	gtk_constraint_solver_insert_error_variable (self, constraint, variable: eplus);
976	gtk_constraint_solver_insert_error_variable (self, constraint, variable: eminus);
977
978	if (constraint->is_stay)
979	{
980	g_ptr_array_add (array: self->stay_error_vars, data: gtk_constraint_variable_pair_new (first: eplus, second: eminus));
981	}
982	else if (constraint->is_edit)
983	{
984	if (eplus_p != NULL)
985	*eplus_p = eplus;
986	if (eminus_p != NULL)
987	*eminus_p = eminus;
988	if (prev_constant_p != NULL)
989	*prev_constant_p = gtk_constraint_expression_get_constant (expression: cn_expr);
990	}
991
992	gtk_constraint_variable_unref (variable: eplus);
993	gtk_constraint_variable_unref (variable: eminus);
994	}
995	}
996
997	if (gtk_constraint_expression_get_constant (expression: expr) < 0.0)
998	gtk_constraint_expression_multiply_by (expression: expr, factor: -1.0);
999
1000	return expr;
1001	}
1002
1003	static void
1004	gtk_constraint_solver_dual_optimize (GtkConstraintSolver *self)
1005	{
1006	GtkConstraintExpression *z_row = g_hash_table_lookup (hash_table: self->rows, key: self->objective);
1007	#ifdef G_ENABLE_DEBUG
1008	gint64 start_time = g_get_monotonic_time ();
1009	#endif
1010
1011	/* We iterate until we don't have any more infeasible rows; the pivot()
1012	* at the end of the loop iteration may add or remove infeasible rows
1013	* as well
1014	*/
1015	while (self->infeasible_rows->len != 0)
1016	{
1017	GtkConstraintVariable *entry_var, *exit_var, *t_v;
1018	GtkConstraintExpressionIter eiter;
1019	GtkConstraintExpression *expr;
1020	double ratio, t_c;
1021
1022	/* Pop the last element of the array */
1023	exit_var = g_ptr_array_index (self->infeasible_rows, self->infeasible_rows->len - 1);
1024	g_ptr_array_set_size (array: self->infeasible_rows, length: self->infeasible_rows->len - 1);
1025
1026	expr = g_hash_table_lookup (hash_table: self->rows, key: exit_var);
1027	if (expr == NULL)
1028	continue;
1029
1030	if (gtk_constraint_expression_get_constant (expression: expr) >= 0.0)
1031	continue;
1032
1033	ratio = DBL_MAX;
1034	entry_var = NULL;
1035
1036	gtk_constraint_expression_iter_init (iter: &eiter, equation: expr);
1037	while (gtk_constraint_expression_iter_next (iter: &eiter, variable: &t_v, coefficient: &t_c))
1038	{
1039	if (t_c > 0.0 && gtk_constraint_variable_is_pivotable (variable: t_v))
1040	{
1041	double zc = gtk_constraint_expression_get_coefficient (expression: z_row, variable: t_v);
1042	double r = zc / t_c;
1043
1044	if (r < ratio)
1045	{
1046	entry_var = t_v;
1047	ratio = r;
1048	}
1049	}
1050	}
1051
1052	if (ratio == DBL_MAX)
1053	g_critical ("INTERNAL: ratio == DBL_MAX in dual_optimize");
1054
1055	gtk_constraint_solver_pivot (self, entry_var, exit_var);
1056	}
1057
1058	GTK_NOTE (CONSTRAINTS,
1059	g_message ("dual_optimize.time := %.3f ms",
1060	(float) (g_get_monotonic_time () - start_time) / 1000.f));
1061	}
1062
1063	static void
1064	gtk_constraint_solver_delta_edit_constant (GtkConstraintSolver *self,
1065	double delta,
1066	GtkConstraintVariable *plus_error_var,
1067	GtkConstraintVariable *minus_error_var)
1068	{
1069	GtkConstraintExpression *plus_expr, *minus_expr;
1070	GtkConstraintVariable *basic_var;
1071	GtkConstraintVariableSet *column_set;
1072	GtkConstraintVariableSetIter iter;
1073
1074	plus_expr = g_hash_table_lookup (hash_table: self->rows, key: plus_error_var);
1075	if (plus_expr != NULL)
1076	{
1077	double new_constant = gtk_constraint_expression_get_constant (expression: plus_expr) + delta;
1078
1079	gtk_constraint_expression_set_constant (expression: plus_expr, constant: new_constant);
1080
1081	if (new_constant < 0.0)
1082	g_ptr_array_add (array: self->infeasible_rows, data: plus_error_var);
1083
1084	return;
1085	}
1086
1087	minus_expr = g_hash_table_lookup (hash_table: self->rows, key: minus_error_var);
1088	if (minus_expr != NULL)
1089	{
1090	double new_constant = gtk_constraint_expression_get_constant (expression: minus_expr) - delta;
1091
1092	gtk_constraint_expression_set_constant (expression: minus_expr, constant: new_constant);
1093
1094	if (new_constant < 0.0)
1095	g_ptr_array_add (array: self->infeasible_rows, data: minus_error_var);
1096
1097	return;
1098	}
1099
1100	column_set = g_hash_table_lookup (hash_table: self->columns, key: minus_error_var);
1101	if (column_set == NULL)
1102	{
1103	g_critical ("INTERNAL: Columns are unset during delta edit");
1104	return;
1105	}
1106
1107	gtk_constraint_variable_set_iter_init (iter: &iter, set: column_set);
1108	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &basic_var))
1109	{
1110	GtkConstraintExpression *expr;
1111	double c, new_constant;
1112
1113	expr = g_hash_table_lookup (hash_table: self->rows, key: basic_var);
1114	c = gtk_constraint_expression_get_coefficient (expression: expr, variable: minus_error_var);
1115
1116	new_constant = gtk_constraint_expression_get_constant (expression: expr) + (c * delta);
1117	gtk_constraint_expression_set_constant (expression: expr, constant: new_constant);
1118
1119	if (gtk_constraint_variable_is_restricted (variable: basic_var) && new_constant < 0.0)
1120	g_ptr_array_add (array: self->infeasible_rows, data: basic_var);
1121	}
1122	}
1123
1124	static GtkConstraintVariable *
1125	gtk_constraint_solver_choose_subject (GtkConstraintSolver *self,
1126	GtkConstraintExpression *expression)
1127	{
1128	GtkConstraintExpressionIter eiter;
1129	GtkConstraintVariable *subject = NULL;
1130	GtkConstraintVariable *retval = NULL;
1131	GtkConstraintVariable *t_v;
1132	gboolean found_unrestricted = FALSE;
1133	gboolean found_new_restricted = FALSE;
1134	gboolean retval_found = FALSE;
1135	double coeff = 0.0;
1136	double t_c;
1137
1138	gtk_constraint_expression_iter_init (iter: &eiter, equation: expression);
1139	while (gtk_constraint_expression_iter_prev (iter: &eiter, variable: &t_v, coefficient: &t_c))
1140	{
1141	if (found_unrestricted)
1142	{
1143	if (!gtk_constraint_variable_is_restricted (variable: t_v))
1144	{
1145	if (!g_hash_table_contains (hash_table: self->columns, key: t_v))
1146	{
1147	retval_found = TRUE;
1148	retval = t_v;
1149	break;
1150	}
1151	}
1152	}
1153	else
1154	{
1155	if (gtk_constraint_variable_is_restricted (variable: t_v))
1156	{
1157	if (!found_new_restricted &&
1158	!gtk_constraint_variable_is_dummy (variable: t_v) &&
1159	t_c < 0.0)
1160	{
1161	GtkConstraintVariableSet *cset = g_hash_table_lookup (hash_table: self->columns, key: t_v);
1162
1163	if (cset == NULL ||
1164	(gtk_constraint_variable_set_is_singleton (set: cset) &&
1165	g_hash_table_contains (hash_table: self->columns, key: self->objective)))
1166	{
1167	subject = t_v;
1168	found_new_restricted = TRUE;
1169	}
1170	}
1171	}
1172	else
1173	{
1174	subject = t_v;
1175	found_unrestricted = TRUE;
1176	}
1177	}
1178	}
1179
1180	if (retval_found)
1181	return retval;
1182
1183	if (subject != NULL)
1184	return subject;
1185
1186	gtk_constraint_expression_iter_init (iter: &eiter, equation: expression);
1187	while (gtk_constraint_expression_iter_prev (iter: &eiter, variable: &t_v, coefficient: &t_c))
1188	{
1189	if (!gtk_constraint_variable_is_dummy (variable: t_v))
1190	return NULL;
1191
1192	if (!g_hash_table_contains (hash_table: self->columns, key: t_v))
1193	{
1194	subject = t_v;
1195	coeff = t_c;
1196	}
1197	}
1198
1199	if (!G_APPROX_VALUE (gtk_constraint_expression_get_constant (expression), 0.0, 0.001))
1200	{
1201	GTK_NOTE (CONSTRAINTS,
1202	g_message ("Unable to satisfy required constraint (choose_subject)"));
1203	return NULL;
1204	}
1205
1206	if (coeff > 0)
1207	gtk_constraint_expression_multiply_by (expression, factor: -1.0);
1208
1209	return subject;
1210	}
1211
1212	static gboolean
1213	gtk_constraint_solver_try_adding_directly (GtkConstraintSolver *self,
1214	GtkConstraintExpression *expression)
1215	{
1216	GtkConstraintVariable *subject;
1217
1218	subject = gtk_constraint_solver_choose_subject (self, expression);
1219	if (subject == NULL)
1220	return FALSE;
1221
1222	gtk_constraint_variable_ref (variable: subject);
1223
1224	gtk_constraint_expression_new_subject (expression, subject);
1225	if (gtk_constraint_solver_column_has_key (self, subject))
1226	gtk_constraint_solver_substitute_out (self, old_variable: subject, expression);
1227
1228	gtk_constraint_solver_add_row (self, variable: subject, expression);
1229
1230	gtk_constraint_variable_unref (variable: subject);
1231
1232	return TRUE;
1233	}
1234
1235	static void
1236	gtk_constraint_solver_add_with_artificial_variable (GtkConstraintSolver *self,
1237	GtkConstraintExpression *expression)
1238	{
1239	GtkConstraintVariable *av, *az;
1240	GtkConstraintExpression *az_row;
1241	GtkConstraintExpression *az_tableau_row;
1242	GtkConstraintExpression *e;
1243
1244	av = gtk_constraint_variable_new_slack (name: "a");
1245	self->artificial_counter += 1;
1246
1247	az = gtk_constraint_variable_new_objective (name: "az");
1248
1249	az_row = gtk_constraint_expression_clone (expression);
1250
1251	gtk_constraint_solver_add_row (self, variable: az, expression: az_row);
1252	gtk_constraint_solver_add_row (self, variable: av, expression);
1253
1254	gtk_constraint_expression_unref (expression: az_row);
1255	gtk_constraint_variable_unref (variable: av);
1256	gtk_constraint_variable_unref (variable: az);
1257
1258	gtk_constraint_solver_optimize (self, z: az);
1259
1260	az_tableau_row = g_hash_table_lookup (hash_table: self->rows, key: az);
1261	if (!G_APPROX_VALUE (gtk_constraint_expression_get_constant (az_tableau_row), 0.0, 0.001))
1262	{
1263	gtk_constraint_solver_remove_column (self, variable: av);
1264	gtk_constraint_solver_remove_row (self, variable: az, TRUE);
1265
1266	#ifdef G_ENABLE_DEBUG
1267	if (GTK_DEBUG_CHECK (CONSTRAINTS))
1268	{
1269	char *str = gtk_constraint_expression_to_string (expression);
1270	g_message ("Unable to satisfy a required constraint (add): %s", str);
1271	g_free (mem: str);
1272	}
1273	#endif
1274
1275	return;
1276	}
1277
1278	e = g_hash_table_lookup (hash_table: self->rows, key: av);
1279	if (e != NULL)
1280	{
1281	GtkConstraintVariable *entry_var;
1282
1283	if (gtk_constraint_expression_is_constant (expression: e))
1284	{
1285	gtk_constraint_solver_remove_row (self, variable: av, TRUE);
1286	gtk_constraint_solver_remove_row (self, variable: az, TRUE);
1287	return;
1288	}
1289
1290	entry_var = gtk_constraint_expression_get_pivotable_variable (expression: e);
1291	if (entry_var == NULL)
1292	return;
1293
1294	gtk_constraint_solver_pivot (self, entry_var, exit_var: av);
1295	}
1296
1297	g_assert (!g_hash_table_contains (self->rows, av));
1298
1299	gtk_constraint_solver_remove_column (self, variable: av);
1300	gtk_constraint_solver_remove_row (self, variable: az, TRUE);
1301	}
1302
1303	static void
1304	gtk_constraint_solver_add_constraint_internal (GtkConstraintSolver *self,
1305	GtkConstraintRef *constraint)
1306	{
1307	GtkConstraintExpression *expr;
1308	GtkConstraintVariable *eplus;
1309	GtkConstraintVariable *eminus;
1310	double prev_constant;
1311
1312	expr = gtk_constraint_solver_new_expression (self, constraint,
1313	eplus_p: &eplus,
1314	eminus_p: &eminus,
1315	prev_constant_p: &prev_constant);
1316
1317	#ifdef G_ENABLE_DEBUG
1318	if (GTK_DEBUG_CHECK (CONSTRAINTS))
1319	{
1320	char *expr_s = gtk_constraint_expression_to_string (expression: expr);
1321	char *ref_s = gtk_constraint_ref_to_string (self: constraint);
1322	g_message ("Adding constraint '%s' (normalized expression: '%s')", ref_s, expr_s);
1323	g_free (mem: ref_s);
1324	g_free (mem: expr_s);
1325	}
1326	#endif
1327
1328	if (constraint->is_stay)
1329	{
1330	StayInfo *si = g_new (StayInfo, 1);
1331
1332	si->constraint = constraint;
1333
1334	g_hash_table_insert (hash_table: self->stay_var_map, key: constraint->variable, value: si);
1335	}
1336	else if (constraint->is_edit)
1337	{
1338	EditInfo *ei = g_new (EditInfo, 1);
1339
1340	ei->constraint = constraint;
1341	ei->eplus = eplus;
1342	ei->eminus = eminus;
1343	ei->prev_constant = prev_constant;
1344
1345	g_hash_table_insert (hash_table: self->edit_var_map, key: constraint->variable, value: ei);
1346	}
1347
1348	if (!gtk_constraint_solver_try_adding_directly (self, expression: expr))
1349	gtk_constraint_solver_add_with_artificial_variable (self, expression: expr);
1350
1351	gtk_constraint_expression_unref (expression: expr);
1352
1353	self->needs_solving = TRUE;
1354
1355	if (self->auto_solve)
1356	{
1357	gtk_constraint_solver_optimize (self, z: self->objective);
1358	gtk_constraint_solver_set_external_variables (self);
1359	}
1360
1361	constraint->solver = self;
1362
1363	g_hash_table_add (hash_table: self->constraints, key: constraint);
1364	}
1365
1366	/*< private >
1367	* gtk_constraint_solver_new:
1368	*
1369	* Creates a new `GtkConstraintSolver` instance.
1370	*
1371	* Returns: the newly created `GtkConstraintSolver`
1372	*/
1373	GtkConstraintSolver *
1374	gtk_constraint_solver_new (void)
1375	{
1376	return g_object_new (GTK_TYPE_CONSTRAINT_SOLVER, NULL);
1377	}
1378
1379	/*< private >
1380	* gtk_constraint_solver_freeze:
1381	* @solver: a `GtkConstraintSolver`
1382	*
1383	* Freezes the solver; any constraint addition or removal will not
1384	* be automatically solved until gtk_constraint_solver_thaw() is
1385	* called.
1386	*/
1387	void
1388	gtk_constraint_solver_freeze (GtkConstraintSolver *solver)
1389	{
1390	g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
1391
1392	solver->freeze_count += 1;
1393
1394	if (solver->freeze_count > 0)
1395	solver->auto_solve = FALSE;
1396	}
1397
1398	/*< private >
1399	* gtk_constraint_solver_thaw:
1400	* @solver: a `GtkConstraintSolver`
1401	*
1402	* Thaws a frozen `GtkConstraintSolver`.
1403	*/
1404	void
1405	gtk_constraint_solver_thaw (GtkConstraintSolver *solver)
1406	{
1407	g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
1408	g_return_if_fail (solver->freeze_count > 0);
1409
1410	solver->freeze_count -= 1;
1411
1412	if (solver->freeze_count == 0)
1413	{
1414	solver->auto_solve = TRUE;
1415	gtk_constraint_solver_resolve (solver);
1416	}
1417	}
1418
1419	/*< private >
1420	* gtk_constraint_solver_note_added_variable:
1421	* @self: a `GtkConstraintSolver`
1422	* @variable: a `GtkConstraintVariable`
1423	* @subject: a `GtkConstraintVariable`
1424	*
1425	* Adds a new @variable into the tableau of a `GtkConstraintSolver`.
1426	*
1427	* This function is typically called by `GtkConstraintExpression`, and
1428	* should never be directly called.
1429	*/
1430	void
1431	gtk_constraint_solver_note_added_variable (GtkConstraintSolver *self,
1432	GtkConstraintVariable *variable,
1433	GtkConstraintVariable *subject)
1434	{
1435	if (subject != NULL)
1436	gtk_constraint_solver_insert_column_variable (self, param_var: variable, row_var: subject);
1437	}
1438
1439	/*< private >
1440	* gtk_constraint_solver_note_removed_variable:
1441	* @self: a `GtkConstraintSolver`
1442	* @variable: a `GtkConstraintVariable`
1443	* @subject: a `GtkConstraintVariable`
1444	*
1445	* Removes a @variable from the tableau of a `GtkConstraintSolver`.
1446	*
1447	* This function is typically called by `GtkConstraintExpression`, and
1448	* should never be directly called.
1449	*/
1450	void
1451	gtk_constraint_solver_note_removed_variable (GtkConstraintSolver *self,
1452	GtkConstraintVariable *variable,
1453	GtkConstraintVariable *subject)
1454	{
1455	GtkConstraintVariableSet *set;
1456
1457	set = g_hash_table_lookup (hash_table: self->columns, key: variable);
1458	if (set != NULL && subject != NULL)
1459	gtk_constraint_variable_set_remove (set, variable: subject);
1460	}
1461
1462	/*< private >
1463	* gtk_constraint_solver_create_variable:
1464	* @self: a `GtkConstraintSolver`
1465	* @prefix: (nullable): the prefix of the variable
1466	* @name: (nullable): the name of the variable
1467	* @value: the initial value of the variable
1468	*
1469	* Creates a new variable inside the @solver.
1470	*
1471	* Returns: (transfer full): the newly created variable
1472	*/
1473	GtkConstraintVariable *
1474	gtk_constraint_solver_create_variable (GtkConstraintSolver *self,
1475	const char *prefix,
1476	const char *name,
1477	double value)
1478	{
1479	GtkConstraintVariable *res;
1480
1481	res = gtk_constraint_variable_new (prefix, name);
1482	gtk_constraint_variable_set_value (variable: res, value);
1483
1484	self->var_counter++;
1485
1486	return res;
1487	}
1488
1489	/*< private >
1490	* gtk_constraint_solver_resolve:
1491	* @solver: a `GtkConstraintSolver`
1492	*
1493	* Resolves the constraints currently stored in @solver.
1494	*/
1495	void
1496	gtk_constraint_solver_resolve (GtkConstraintSolver *solver)
1497	{
1498	#ifdef G_ENABLE_DEBUG
1499	gint64 start_time = g_get_monotonic_time ();
1500	#endif
1501
1502	g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
1503
1504	gtk_constraint_solver_dual_optimize (self: solver);
1505	gtk_constraint_solver_set_external_variables (self: solver);
1506
1507	g_ptr_array_set_size (array: solver->infeasible_rows, length: 0);
1508
1509	gtk_constraint_solver_reset_stay_constants (self: solver);
1510
1511	GTK_NOTE (CONSTRAINTS,
1512	g_message ("resolve.time := %.3f ms",
1513	(float) (g_get_monotonic_time () - start_time) / 1000.f));
1514
1515	solver->needs_solving = FALSE;
1516	}
1517
1518	/*< private >
1519	* gtk_constraint_solver_add_constraint:
1520	* @self: a `GtkConstraintSolver`
1521	* @variable: the subject of the constraint
1522	* @relation: the relation of the constraint
1523	* @expression: the expression of the constraint
1524	* @strength: the strength of the constraint
1525	*
1526	* Adds a new constraint in the form of:
1527	*
1528	* |[
1529	* variable relation expression (strength)
1530	* |]
1531	*
1532	* into the `GtkConstraintSolver`.
1533	*
1534	* Returns: (transfer none): a reference to the newly created
1535	* constraint; you can use the reference to remove the
1536	* constraint from the solver
1537	*/
1538	GtkConstraintRef *
1539	gtk_constraint_solver_add_constraint (GtkConstraintSolver *self,
1540	GtkConstraintVariable *variable,
1541	GtkConstraintRelation relation,
1542	GtkConstraintExpression *expression,
1543	int strength)
1544	{
1545	GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
1546
1547	res->solver = self;
1548	res->strength = strength;
1549	res->is_edit = FALSE;
1550	res->is_stay = FALSE;
1551	res->relation = relation;
1552
1553	if (expression == NULL)
1554	res->expression = gtk_constraint_expression_new_from_variable (variable);
1555	else
1556	{
1557	res->expression = expression;
1558
1559	if (variable != NULL)
1560	{
1561	switch (res->relation)
1562	{
1563	case GTK_CONSTRAINT_RELATION_EQ:
1564	gtk_constraint_expression_add_variable (expression: res->expression,
1565	variable, coefficient: -1.0,
1566	NULL,
1567	solver: self);
1568	break;
1569
1570	case GTK_CONSTRAINT_RELATION_LE:
1571	gtk_constraint_expression_add_variable (expression: res->expression,
1572	variable, coefficient: -1.0,
1573	NULL,
1574	solver: self);
1575	break;
1576
1577	case GTK_CONSTRAINT_RELATION_GE:
1578	gtk_constraint_expression_multiply_by (expression: res->expression, factor: -1.0);
1579	gtk_constraint_expression_add_variable (expression: res->expression,
1580	variable, coefficient: 1.0,
1581	NULL,
1582	solver: self);
1583	break;
1584
1585	default:
1586	g_assert_not_reached ();
1587	}
1588	}
1589	}
1590
1591	gtk_constraint_solver_add_constraint_internal (self, constraint: res);
1592
1593	return res;
1594	}
1595
1596	/*< private >
1597	* gtk_constraint_solver_add_stay_variable:
1598	* @self: a `GtkConstraintSolver`
1599	* @variable: a stay `GtkConstraintVariable`
1600	* @strength: the strength of the constraint
1601	*
1602	* Adds a constraint on a stay @variable with the given @strength.
1603	*
1604	* A stay variable is an "anchor" in the system: a variable that is
1605	* supposed to stay at the same value.
1606	*
1607	* Returns: (transfer none): a reference to the newly created
1608	* constraint; you can use the reference to remove the
1609	* constraint from the solver
1610	*/
1611	GtkConstraintRef *
1612	gtk_constraint_solver_add_stay_variable (GtkConstraintSolver *self,
1613	GtkConstraintVariable *variable,
1614	int strength)
1615	{
1616	GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
1617
1618	res->solver = self;
1619	res->variable = gtk_constraint_variable_ref (variable);
1620	res->relation = GTK_CONSTRAINT_RELATION_EQ;
1621	res->strength = strength;
1622	res->is_stay = TRUE;
1623	res->is_edit = FALSE;
1624
1625	res->expression = gtk_constraint_expression_new (constant: gtk_constraint_variable_get_value (variable: res->variable));
1626	gtk_constraint_expression_add_variable (expression: res->expression,
1627	variable: res->variable, coefficient: -1.0,
1628	NULL,
1629	solver: self);
1630
1631	#ifdef G_ENABLE_DEBUG
1632	if (GTK_DEBUG_CHECK (CONSTRAINTS))
1633	{
1634	char *str = gtk_constraint_expression_to_string (expression: res->expression);
1635	g_message ("Adding stay variable: %s", str);
1636	g_free (mem: str);
1637	}
1638	#endif
1639
1640	gtk_constraint_solver_add_constraint_internal (self, constraint: res);
1641
1642	return res;
1643	}
1644
1645	/*< private >
1646	* gtk_constraint_solver_remove_stay_variable:
1647	* @self: a `GtkConstraintSolver`
1648	* @variable: a stay variable
1649	*
1650	* Removes the stay constraint associated to @variable.
1651	*
1652	* This is a convenience function for gtk_constraint_solver_remove_constraint().
1653	*/
1654	void
1655	gtk_constraint_solver_remove_stay_variable (GtkConstraintSolver *self,
1656	GtkConstraintVariable *variable)
1657	{
1658	StayInfo *si = g_hash_table_lookup (hash_table: self->stay_var_map, key: variable);
1659
1660	if (si == NULL)
1661	{
1662	char *str = gtk_constraint_variable_to_string (variable);
1663
1664	g_critical ("Unknown stay variable '%s'", str);
1665
1666	g_free (mem: str);
1667
1668	return;
1669	}
1670
1671	gtk_constraint_solver_remove_constraint (solver: self, reference: si->constraint);
1672	}
1673
1674	/*< private >
1675	* gtk_constraint_solver_add_edit_variable:
1676	* @self: a `GtkConstraintSolver`
1677	* @variable: an edit variable
1678	* @strength: the strength of the constraint
1679	*
1680	* Adds an editable constraint to the @solver.
1681	*
1682	* Editable constraints can be used to suggest values to a
1683	* `GtkConstraintSolver` inside an edit phase, for instance: if
1684	* you want to change the value of a variable without necessarily
1685	* insert a new constraint every time.
1686	*
1687	* See also: gtk_constraint_solver_suggest_value()
1688	*
1689	* Returns: (transfer none): a reference to the newly added constraint
1690	*/
1691	GtkConstraintRef *
1692	gtk_constraint_solver_add_edit_variable (GtkConstraintSolver *self,
1693	GtkConstraintVariable *variable,
1694	int strength)
1695	{
1696	GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
1697
1698	res->solver = self;
1699	res->variable = gtk_constraint_variable_ref (variable);
1700	res->relation = GTK_CONSTRAINT_RELATION_EQ;
1701	res->strength = strength;
1702	res->is_stay = FALSE;
1703	res->is_edit = TRUE;
1704
1705	res->expression = gtk_constraint_expression_new (constant: gtk_constraint_variable_get_value (variable));
1706	gtk_constraint_expression_add_variable (expression: res->expression,
1707	variable, coefficient: -1.0,
1708	NULL,
1709	solver: self);
1710
1711	gtk_constraint_solver_add_constraint_internal (self, constraint: res);
1712
1713	return res;
1714	}
1715
1716	/*< private >
1717	* gtk_constraint_solver_remove_edit_variable:
1718	* @self: a `GtkConstraintSolver`
1719	* @variable: an edit variable
1720	*
1721	* Removes the edit constraint associated to @variable.
1722	*
1723	* This is a convenience function around gtk_constraint_solver_remove_constraint().
1724	*/
1725	void
1726	gtk_constraint_solver_remove_edit_variable (GtkConstraintSolver *self,
1727	GtkConstraintVariable *variable)
1728	{
1729	EditInfo *ei = g_hash_table_lookup (hash_table: self->edit_var_map, key: variable);
1730
1731	if (ei == NULL)
1732	{
1733	char *str = gtk_constraint_variable_to_string (variable);
1734
1735	g_critical ("Unknown edit variable '%s'", str);
1736
1737	g_free (mem: str);
1738
1739	return;
1740	}
1741
1742	gtk_constraint_solver_remove_constraint (solver: self, reference: ei->constraint);
1743	}
1744
1745	/*< private >
1746	* gtk_constraint_solver_remove_constraint:
1747	* @self: a `GtkConstraintSolver`
1748	* @constraint: a constraint reference
1749	*
1750	* Removes a @constraint from the @solver.
1751	*/
1752	void
1753	gtk_constraint_solver_remove_constraint (GtkConstraintSolver *self,
1754	GtkConstraintRef *constraint)
1755	{
1756	GtkConstraintExpression *z_row;
1757	GtkConstraintVariable *marker;
1758	GtkConstraintVariableSet *error_vars;
1759	GtkConstraintVariableSetIter iter;
1760
1761	if (!g_hash_table_contains (hash_table: self->constraints, key: constraint))
1762	return;
1763
1764	self->needs_solving = TRUE;
1765
1766	gtk_constraint_solver_reset_stay_constants (self);
1767
1768	z_row = g_hash_table_lookup (hash_table: self->rows, key: self->objective);
1769	error_vars = g_hash_table_lookup (hash_table: self->error_vars, key: constraint);
1770
1771	if (error_vars != NULL)
1772	{
1773	GtkConstraintVariable *v;
1774
1775	gtk_constraint_variable_set_iter_init (iter: &iter, set: error_vars);
1776	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &v))
1777	{
1778	GtkConstraintExpression *e = g_hash_table_lookup (hash_table: self->rows, key: v);
1779
1780	if (e == NULL)
1781	{
1782	gtk_constraint_expression_add_variable (expression: z_row,
1783	variable: v,
1784	coefficient: constraint->strength,
1785	subject: self->objective,
1786	solver: self);
1787	}
1788	else
1789	{
1790	gtk_constraint_expression_add_expression (a_expr: z_row,
1791	b_expr: e,
1792	n: constraint->strength,
1793	subject: self->objective,
1794	solver: self);
1795	}
1796	}
1797	}
1798
1799	marker = g_hash_table_lookup (hash_table: self->marker_vars, key: constraint);
1800	if (marker == NULL)
1801	{
1802	g_critical ("Constraint %p not found", constraint);
1803	return;
1804	}
1805
1806	g_hash_table_remove (hash_table: self->marker_vars, key: constraint);
1807
1808	if (g_hash_table_lookup (hash_table: self->rows, key: marker) == NULL)
1809	{
1810	GtkConstraintVariableSet *set = g_hash_table_lookup (hash_table: self->columns, key: marker);
1811	GtkConstraintVariable *exit_var = NULL;
1812	GtkConstraintVariable *v;
1813	double min_ratio = 0;
1814
1815	if (set == NULL)
1816	goto no_columns;
1817
1818	gtk_constraint_variable_set_iter_init (iter: &iter, set);
1819	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &v))
1820	{
1821	if (gtk_constraint_variable_is_restricted (variable: v))
1822	{
1823	GtkConstraintExpression *e = g_hash_table_lookup (hash_table: self->rows, key: v);
1824	double coeff = gtk_constraint_expression_get_coefficient (expression: e, variable: marker);
1825
1826	if (coeff < 0.0)
1827	{
1828	double r = -gtk_constraint_expression_get_constant (expression: e) / coeff;
1829
1830	if (exit_var == NULL ||
1831	r < min_ratio ||
1832	G_APPROX_VALUE (r, min_ratio, 0.0001))
1833	{
1834	min_ratio = r;
1835	exit_var = v;
1836	}
1837	}
1838	}
1839	}
1840
1841	if (exit_var == NULL)
1842	{
1843	gtk_constraint_variable_set_iter_init (iter: &iter, set);
1844	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &v))
1845	{
1846	if (gtk_constraint_variable_is_restricted (variable: v))
1847	{
1848	GtkConstraintExpression *e = g_hash_table_lookup (hash_table: self->rows, key: v);
1849	double coeff = gtk_constraint_expression_get_coefficient (expression: e, variable: marker);
1850	double r = 0.0;
1851
1852	if (!G_APPROX_VALUE (coeff, 0.0, 0.0001))
1853	r = gtk_constraint_expression_get_constant (expression: e) / coeff;
1854
1855	if (exit_var == NULL || r < min_ratio)
1856	{
1857	min_ratio = r;
1858	exit_var = v;
1859	}
1860	}
1861	}
1862	}
1863
1864	if (exit_var == NULL)
1865	{
1866	if (gtk_constraint_variable_set_is_empty (set))
1867	gtk_constraint_solver_remove_column (self, variable: marker);
1868	else
1869	{
1870	gtk_constraint_variable_set_iter_init (iter: &iter, set);
1871	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &v))
1872	{
1873	if (v != self->objective)
1874	{
1875	exit_var = v;
1876	break;
1877	}
1878	}
1879	}
1880	}
1881
1882	if (exit_var != NULL)
1883	gtk_constraint_solver_pivot (self, entry_var: marker, exit_var);
1884	}
1885
1886	no_columns:
1887	if (g_hash_table_lookup (hash_table: self->rows, key: marker) != NULL)
1888	gtk_constraint_solver_remove_row (self, variable: marker, TRUE);
1889	else
1890	gtk_constraint_variable_unref (variable: marker);
1891
1892	if (error_vars != NULL)
1893	{
1894	GtkConstraintVariable *v;
1895
1896	gtk_constraint_variable_set_iter_init (iter: &iter, set: error_vars);
1897	while (gtk_constraint_variable_set_iter_next (iter: &iter, variable_p: &v))
1898	{
1899	if (v != marker)
1900	gtk_constraint_solver_remove_column (self, variable: v);
1901	}
1902	}
1903
1904	if (constraint->is_stay)
1905	{
1906	if (error_vars != NULL)
1907	{
1908	GPtrArray *remaining =
1909	g_ptr_array_new_with_free_func (element_free_func: (GDestroyNotify) gtk_constraint_variable_pair_free);
1910
1911	int i = 0;
1912
1913	for (i = 0; i < self->stay_error_vars->len; i++)
1914	{
1915	GtkConstraintVariablePair *pair = g_ptr_array_index (self->stay_error_vars, i);
1916	gboolean found = FALSE;
1917
1918	if (gtk_constraint_variable_set_remove (set: error_vars, variable: pair->first))
1919	found = TRUE;
1920
1921	if (gtk_constraint_variable_set_remove (set: error_vars, variable: pair->second))
1922	found = FALSE;
1923
1924	if (!found)
1925	g_ptr_array_add (array: remaining, data: gtk_constraint_variable_pair_new (first: pair->first, second: pair->second));
1926	}
1927
1928	g_clear_pointer (&self->stay_error_vars, g_ptr_array_unref);
1929	self->stay_error_vars = remaining;
1930	}
1931
1932	g_hash_table_remove (hash_table: self->stay_var_map, key: constraint->variable);
1933	}
1934	else if (constraint->is_edit)
1935	{
1936	EditInfo *ei = g_hash_table_lookup (hash_table: self->edit_var_map, key: constraint->variable);
1937
1938	gtk_constraint_solver_remove_column (self, variable: ei->eminus);
1939
1940	g_hash_table_remove (hash_table: self->edit_var_map, key: constraint->variable);
1941	}
1942
1943	if (error_vars != NULL)
1944	g_hash_table_remove (hash_table: self->error_vars, key: constraint);
1945
1946	if (self->auto_solve)
1947	{
1948	gtk_constraint_solver_optimize (self, z: self->objective);
1949	gtk_constraint_solver_set_external_variables (self);
1950	}
1951
1952	g_hash_table_remove (hash_table: self->constraints, key: constraint);
1953	}
1954
1955	/*< private >
1956	* gtk_constraint_solver_suggest_value:
1957	* @self: a `GtkConstraintSolver`
1958	* @variable: a `GtkConstraintVariable`
1959	* @value: the suggested value for @variable
1960	*
1961	* Suggests a new @value for an edit @variable.
1962	*
1963	* The @variable must be an edit variable, and the solver must be
1964	* in an edit phase.
1965	*/
1966	void
1967	gtk_constraint_solver_suggest_value (GtkConstraintSolver *self,
1968	GtkConstraintVariable *variable,
1969	double value)
1970	{
1971	EditInfo *ei = g_hash_table_lookup (hash_table: self->edit_var_map, key: variable);
1972	double delta;
1973	if (ei == NULL)
1974	{
1975	g_critical ("Suggesting value '%g' but variable %p is not editable",
1976	value, variable);
1977	return;
1978	}
1979
1980	if (!self->in_edit_phase)
1981	{
1982	g_critical ("Suggesting value '%g' for variable '%p' but solver is "
1983	"not in an edit phase",
1984	value, variable);
1985	return;
1986	}
1987
1988	delta = value - ei->prev_constant;
1989	ei->prev_constant = value;
1990
1991	gtk_constraint_solver_delta_edit_constant (self, delta, plus_error_var: ei->eplus, minus_error_var: ei->eminus);
1992	}
1993
1994	/*< private >
1995	* gtk_constraint_solver_has_stay_variable:
1996	* @solver: a `GtkConstraintSolver`
1997	* @variable: a `GtkConstraintVariable`
1998	*
1999	* Checks whether @variable is a stay variable.
2000	*
2001	* Returns: %TRUE if the variable is a stay variable
2002	*/
2003	gboolean
2004	gtk_constraint_solver_has_stay_variable (GtkConstraintSolver *solver,
2005	GtkConstraintVariable *variable)
2006	{
2007	g_return_val_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver), FALSE);
2008	g_return_val_if_fail (variable != NULL, FALSE);
2009
2010	return g_hash_table_contains (hash_table: solver->stay_var_map, key: variable);
2011	}
2012
2013	/*< private >
2014	* gtk_constraint_solver_has_edit_variable:
2015	* @solver: a `GtkConstraintSolver`
2016	* @variable: a `GtkConstraintVariable`
2017	*
2018	* Checks whether @variable is an edit variable.
2019	*
2020	* Returns: %TRUE if the variable is an edit variable
2021	*/
2022	gboolean
2023	gtk_constraint_solver_has_edit_variable (GtkConstraintSolver *solver,
2024	GtkConstraintVariable *variable)
2025	{
2026	g_return_val_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver), FALSE);
2027	g_return_val_if_fail (variable != NULL, FALSE);
2028
2029	return g_hash_table_contains (hash_table: solver->edit_var_map, key: variable);
2030	}
2031
2032	/*< private >
2033	* gtk_constraint_solver_begin_edit:
2034	* @solver: a `GtkConstraintSolver`
2035	*
2036	* Begins the edit phase for a constraint system.
2037	*
2038	* Typically, you need to add new edit constraints for a variable to the
2039	* system, using gtk_constraint_solver_add_edit_variable(); then you
2040	* call this function and suggest values for the edit variables, using
2041	* gtk_constraint_solver_suggest_value(). After you suggested a value
2042	* for all the variables you need to edit, you will need to call
2043	* gtk_constraint_solver_resolve() to solve the system, and get the value
2044	* of the various variables that you're interested in.
2045	*
2046	* Once you completed the edit phase, call gtk_constraint_solver_end_edit()
2047	* to remove all the edit variables.
2048	*/
2049	void
2050	gtk_constraint_solver_begin_edit (GtkConstraintSolver *solver)
2051	{
2052	g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
2053
2054	if (g_hash_table_size (hash_table: solver->edit_var_map) == 0)
2055	{
2056	g_critical ("Solver %p does not have editable variables.", solver);
2057	return;
2058	}
2059
2060	g_ptr_array_set_size (array: solver->infeasible_rows, length: 0);
2061	gtk_constraint_solver_reset_stay_constants (self: solver);
2062
2063	solver->in_edit_phase = TRUE;
2064	}
2065
2066	static void
2067	edit_info_free (gpointer data)
2068	{
2069	g_free (mem: data);
2070	}
2071
2072	/*< private >
2073	* gtk_constraint_solver_end_edit:
2074	* @solver: a `GtkConstraintSolver`
2075	*
2076	* Ends the edit phase for a constraint system, and clears
2077	* all the edit variables introduced.
2078	*/
2079	void
2080	gtk_constraint_solver_end_edit (GtkConstraintSolver *solver)
2081	{
2082	solver->in_edit_phase = FALSE;
2083
2084	gtk_constraint_solver_resolve (solver);
2085
2086	g_hash_table_remove_all (hash_table: solver->edit_var_map);
2087	}
2088
2089	void
2090	gtk_constraint_solver_clear (GtkConstraintSolver *solver)
2091	{
2092	g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
2093
2094	g_hash_table_remove_all (hash_table: solver->constraints);
2095	g_hash_table_remove_all (hash_table: solver->external_rows);
2096	g_hash_table_remove_all (hash_table: solver->external_parametric_vars);
2097	g_hash_table_remove_all (hash_table: solver->error_vars);
2098	g_hash_table_remove_all (hash_table: solver->marker_vars);
2099	g_hash_table_remove_all (hash_table: solver->edit_var_map);
2100	g_hash_table_remove_all (hash_table: solver->stay_var_map);
2101
2102	g_ptr_array_set_size (array: solver->infeasible_rows, length: 0);
2103	g_ptr_array_set_size (array: solver->stay_error_vars, length: 0);
2104
2105	g_hash_table_remove_all (hash_table: solver->rows);
2106	g_hash_table_remove_all (hash_table: solver->columns);
2107
2108	/* The rows table owns the objective variable */
2109	solver->objective = gtk_constraint_variable_new_objective (name: "Z");
2110	g_hash_table_insert (hash_table: solver->rows,
2111	key: solver->objective,
2112	value: gtk_constraint_expression_new (constant: 0.0));
2113
2114	solver->slack_counter = 0;
2115	solver->dummy_counter = 0;
2116	solver->artificial_counter = 0;
2117	solver->freeze_count = 0;
2118
2119	solver->needs_solving = FALSE;
2120	solver->auto_solve = TRUE;
2121	}
2122
2123	char *
2124	gtk_constraint_solver_to_string (GtkConstraintSolver *solver)
2125	{
2126	GString *buf = g_string_new (NULL);
2127
2128	g_string_append (string: buf, val: "Tableau info:\n");
2129	g_string_append_printf (string: buf, format: "Rows: %d (= %d constraints)\n",
2130	g_hash_table_size (hash_table: solver->rows),
2131	g_hash_table_size (hash_table: solver->rows) - 1);
2132	g_string_append_printf (string: buf, format: "Columns: %d\n",
2133	g_hash_table_size (hash_table: solver->columns));
2134	g_string_append_printf (string: buf, format: "Infeasible rows: %d\n",
2135	solver->infeasible_rows->len);
2136	g_string_append_printf (string: buf, format: "External basic variables: %d\n",
2137	g_hash_table_size (hash_table: solver->external_rows));
2138	g_string_append_printf (string: buf, format: "External parametric variables: %d\n",
2139	g_hash_table_size (hash_table: solver->external_parametric_vars));
2140
2141	g_string_append (string: buf, val: "Constraints:");
2142	if (g_hash_table_size (hash_table: solver->constraints) == 0)
2143	g_string_append (string: buf, val: " <empty>\n");
2144	else
2145	{
2146	GHashTableIter iter;
2147	gpointer key_p;
2148
2149	g_string_append (string: buf, val: "\n");
2150
2151	g_hash_table_iter_init (iter: &iter, hash_table: solver->constraints);
2152	while (g_hash_table_iter_next (iter: &iter, key: &key_p, NULL))
2153	{
2154	char *ref = gtk_constraint_ref_to_string (self: key_p);
2155
2156	g_string_append_printf (string: buf, format: " %s\n", ref);
2157
2158	g_free (mem: ref);
2159	}
2160	}
2161
2162	g_string_append (string: buf, val: "Stay error vars:");
2163	if (solver->stay_error_vars->len == 0)
2164	g_string_append (string: buf, val: " <empty>\n");
2165	else
2166	{
2167	g_string_append (string: buf, val: "\n");
2168
2169	for (int i = 0; i < solver->stay_error_vars->len; i++)
2170	{
2171	const GtkConstraintVariablePair *pair = g_ptr_array_index (solver->stay_error_vars, i);
2172	char *first_s = gtk_constraint_variable_to_string (variable: pair->first);
2173	char *second_s = gtk_constraint_variable_to_string (variable: pair->second);
2174
2175	g_string_append_printf (string: buf, format: " (%s, %s)\n", first_s, second_s);
2176
2177	g_free (mem: first_s);
2178	g_free (mem: second_s);
2179	}
2180	}
2181
2182	g_string_append (string: buf, val: "Edit var map:");
2183	if (g_hash_table_size (hash_table: solver->edit_var_map) == 0)
2184	g_string_append (string: buf, val: " <empty>\n");
2185	else
2186	{
2187	GHashTableIter iter;
2188	gpointer key_p, value_p;
2189
2190	g_string_append (string: buf, val: "\n");
2191
2192	g_hash_table_iter_init (iter: &iter, hash_table: solver->edit_var_map);
2193	while (g_hash_table_iter_next (iter: &iter, key: &key_p, value: &value_p))
2194	{
2195	char *var = gtk_constraint_variable_to_string (variable: key_p);
2196	const EditInfo *ei = value_p;
2197	char *c = gtk_constraint_ref_to_string (self: ei->constraint);
2198
2199	g_string_append_printf (string: buf, format: " %s => %s\n", var, c);
2200
2201	g_free (mem: var);
2202	g_free (mem: c);
2203	}
2204	}
2205
2206	return g_string_free (string: buf, FALSE);
2207	}
2208
2209	char *
2210	gtk_constraint_solver_statistics (GtkConstraintSolver *solver)
2211	{
2212	GString *buf = g_string_new (NULL);
2213
2214	g_string_append_printf (string: buf, format: "Variables: %d\n", solver->var_counter);
2215	g_string_append_printf (string: buf, format: "Slack vars: %d\n", solver->slack_counter);
2216	g_string_append_printf (string: buf, format: "Artificial vars: %d\n", solver->artificial_counter);
2217	g_string_append_printf (string: buf, format: "Dummy vars: %d\n", solver->dummy_counter);
2218	g_string_append_printf (string: buf, format: "Stay vars: %d\n", g_hash_table_size (hash_table: solver->stay_var_map));
2219	g_string_append_printf (string: buf, format: "Optimize count: %d\n", solver->optimize_count);
2220	g_string_append_printf (string: buf, format: "Rows: %d\n", g_hash_table_size (hash_table: solver->rows));
2221	g_string_append_printf (string: buf, format: "Columns: %d\n", g_hash_table_size (hash_table: solver->columns));
2222
2223	if (g_hash_table_size (hash_table: solver->columns) > 0)
2224	{
2225	GHashTableIter iter;
2226	gpointer val;
2227	double sum = 0;
2228
2229	g_hash_table_iter_init (iter: &iter, hash_table: solver->columns);
2230	while (g_hash_table_iter_next (iter: &iter, NULL, value: &val))
2231	{
2232	GtkConstraintVariableSet *set = val;
2233	sum += gtk_constraint_variable_set_size (set);
2234	}
2235	g_string_append_printf (string: buf, format: "Avg column size: %g\n", sum / g_hash_table_size (hash_table: solver->columns));
2236	}
2237
2238	g_string_append_printf (string: buf, format: "Infeasible rows: %d\n", solver->infeasible_rows->len);
2239	g_string_append_printf (string: buf, format: "External basic variables: %d\n", g_hash_table_size (hash_table: solver->external_rows));
2240	g_string_append_printf (string: buf, format: "External parametric variables: %d\n", g_hash_table_size (hash_table: solver->external_parametric_vars));
2241
2242	return g_string_free (string: buf, FALSE);
2243	}
2244