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
G_DEFINE_TYPE(GtkConstraintSolver,gtk_constraint_solver,G_TYPE_OBJECT)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 (gobject);
268
269 g_hash_table_remove_all (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
gtk_constraint_solver_class_init(GtkConstraintSolverClass * klass)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
gtk_constraint_solver_init(GtkConstraintSolver * self)297 gtk_constraint_solver_init (GtkConstraintSolver *self)
298 {
299 self->columns =
300 g_hash_table_new_full (NULL, NULL,
301 (GDestroyNotify) gtk_constraint_variable_unref,
302 (GDestroyNotify) gtk_constraint_variable_set_free);
303
304 self->rows =
305 g_hash_table_new_full (NULL, NULL,
306 (GDestroyNotify) gtk_constraint_variable_unref,
307 (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 ((GDestroyNotify) gtk_constraint_variable_pair_free);
317
318 self->error_vars =
319 g_hash_table_new_full (NULL, NULL,
320 NULL,
321 (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 edit_info_free);
328
329 self->stay_var_map = g_hash_table_new_full (NULL, NULL,
330 NULL,
331 g_free);
332
333 /* The rows table owns the objective variable */
334 self->objective = gtk_constraint_variable_new_objective ("Z");
335 g_hash_table_insert (self->rows,
336 self->objective,
337 gtk_constraint_expression_new (0.0));
338
339 self->constraints =
340 g_hash_table_new_full (NULL, NULL,
341 (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
gtk_constraint_ref_free(GtkConstraintRef * self)354 gtk_constraint_ref_free (GtkConstraintRef *self)
355 {
356 gtk_constraint_solver_remove_constraint (self->solver, self);
357
358 gtk_constraint_expression_unref (self->expression);
359
360 if (self->is_edit || self->is_stay)
361 {
362 g_assert (self->variable != NULL);
363 gtk_constraint_variable_unref (self->variable);
364 }
365
366 g_free (self);
367 }
368
369 static gboolean
gtk_constraint_ref_is_inequality(const GtkConstraintRef * self)370 gtk_constraint_ref_is_inequality (const GtkConstraintRef *self)
371 {
372 return self->relation != GTK_CONSTRAINT_RELATION_EQ;
373 }
374
375 static gboolean
gtk_constraint_ref_is_required(const GtkConstraintRef * self)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 *
relation_to_string(GtkConstraintRelation r)388 relation_to_string (GtkConstraintRelation r)
389 {
390 return relations[r + 1];
391 }
392
393 static const char *
strength_to_string(int s)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 *
gtk_constraint_ref_to_string(const GtkConstraintRef * self)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 (buf, "[stay]");
413 else if (self->is_edit)
414 g_string_append (buf, "[edit]");
415
416 str = gtk_constraint_expression_to_string (self->expression);
417 g_string_append (buf, str);
418 g_free (str);
419
420 g_string_append_c (buf, ' ');
421 g_string_append (buf, relation_to_string (self->relation));
422 g_string_append (buf, " 0.0");
423
424 if (gtk_constraint_ref_is_required (self))
425 g_string_append (buf, " [strength:required]");
426 else
427 g_string_append_printf (buf, " [strength:%d (%s)]",
428 self->strength,
429 strength_to_string (self->strength));
430
431 return g_string_free (buf, FALSE);
432 }
433
434 static GtkConstraintVariableSet *
gtk_constraint_solver_get_column_set(GtkConstraintSolver * self,GtkConstraintVariable * param_var)435 gtk_constraint_solver_get_column_set (GtkConstraintSolver *self,
436 GtkConstraintVariable *param_var)
437 {
438 return g_hash_table_lookup (self->columns, param_var);
439 }
440
441 static gboolean
gtk_constraint_solver_column_has_key(GtkConstraintSolver * self,GtkConstraintVariable * subject)442 gtk_constraint_solver_column_has_key (GtkConstraintSolver *self,
443 GtkConstraintVariable *subject)
444 {
445 return g_hash_table_contains (self->columns, subject);
446 }
447
448 static void
gtk_constraint_solver_insert_column_variable(GtkConstraintSolver * self,GtkConstraintVariable * param_var,GtkConstraintVariable * row_var)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 (self->columns, param_var);
454
455 if (cset == NULL)
456 {
457 cset = gtk_constraint_variable_set_new ();
458 g_hash_table_insert (self->columns, gtk_constraint_variable_ref (param_var), cset);
459 }
460
461 if (row_var != NULL)
462 gtk_constraint_variable_set_add (cset, row_var);
463 }
464
465 static void
gtk_constraint_solver_insert_error_variable(GtkConstraintSolver * self,GtkConstraintRef * constraint,GtkConstraintVariable * variable)466 gtk_constraint_solver_insert_error_variable (GtkConstraintSolver *self,
467 GtkConstraintRef *constraint,
468 GtkConstraintVariable *variable)
469 {
470 GtkConstraintVariableSet *cset = g_hash_table_lookup (self->error_vars, constraint);
471
472 if (cset == NULL)
473 {
474 cset = gtk_constraint_variable_set_new ();
475 g_hash_table_insert (self->error_vars, constraint, cset);
476 }
477
478 gtk_constraint_variable_set_add (cset, variable);
479 }
480
481 static void
gtk_constraint_solver_reset_stay_constants(GtkConstraintSolver * self)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 (self->rows, pair->first);
492
493 if (expression == NULL)
494 expression = g_hash_table_lookup (self->rows, pair->second);
495
496 if (expression != NULL)
497 gtk_constraint_expression_set_constant (expression, 0.0);
498 }
499 }
500
501 static void
gtk_constraint_solver_set_external_variables(GtkConstraintSolver * self)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, self->external_parametric_vars);
508 while (g_hash_table_iter_next (&iter, &key_p, NULL))
509 {
510 GtkConstraintVariable *variable = key_p;
511
512 if (g_hash_table_contains (self->rows, variable))
513 continue;
514
515 gtk_constraint_variable_set_value (variable, 0.0);
516 }
517
518 g_hash_table_iter_init (&iter, self->external_rows);
519 while (g_hash_table_iter_next (&iter, &key_p, NULL))
520 {
521 GtkConstraintVariable *variable = key_p;
522 GtkConstraintExpression *expression;
523 double constant;
524
525 expression = g_hash_table_lookup (self->rows, variable);
526 constant = gtk_constraint_expression_get_constant (expression);
527
528 gtk_constraint_variable_set_value (variable, constant);
529 }
530
531 self->needs_solving = FALSE;
532 }
533
534 static void
gtk_constraint_solver_add_row(GtkConstraintSolver * self,GtkConstraintVariable * variable,GtkConstraintExpression * expression)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 (self->rows,
544 gtk_constraint_variable_ref (variable),
545 gtk_constraint_expression_ref (expression));
546
547 gtk_constraint_expression_iter_init (&iter, expression);
548 while (gtk_constraint_expression_iter_next (&iter, &t_v, &t_c))
549 {
550 gtk_constraint_solver_insert_column_variable (self, t_v, variable);
551
552 if (gtk_constraint_variable_is_external (t_v))
553 g_hash_table_add (self->external_parametric_vars, t_v);
554 }
555
556 if (gtk_constraint_variable_is_external (variable))
557 g_hash_table_add (self->external_rows, variable);
558 }
559
560 static void
gtk_constraint_solver_remove_column(GtkConstraintSolver * self,GtkConstraintVariable * variable)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 (self->columns, variable);
575 if (cset == NULL)
576 goto out;
577
578 gtk_constraint_variable_set_iter_init (&iter, cset);
579 while (gtk_constraint_variable_set_iter_next (&iter, &v))
580 {
581 GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
582
583 gtk_constraint_expression_remove_variable (e, variable);
584 }
585
586 g_hash_table_remove (self->columns, variable);
587
588 out:
589 if (gtk_constraint_variable_is_external (variable))
590 {
591 g_hash_table_remove (self->external_rows, variable);
592 g_hash_table_remove (self->external_parametric_vars, variable);
593 }
594
595 gtk_constraint_variable_unref (variable);
596 }
597
598 static GtkConstraintExpression *
gtk_constraint_solver_remove_row(GtkConstraintSolver * self,GtkConstraintVariable * variable,gboolean free_res)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 (self->rows, variable);
609 g_assert (e != NULL);
610
611 gtk_constraint_expression_ref (e);
612
613 gtk_constraint_expression_iter_init (&iter, e);
614 while (gtk_constraint_expression_iter_next (&iter, &t_v, &t_c))
615 {
616 GtkConstraintVariableSet *cset = g_hash_table_lookup (self->columns, t_v);
617
618 if (cset != NULL)
619 gtk_constraint_variable_set_remove (cset, variable);
620 }
621
622 g_ptr_array_remove (self->infeasible_rows, variable);
623
624 if (gtk_constraint_variable_is_external (variable))
625 g_hash_table_remove (self->external_rows, variable);
626
627 g_hash_table_remove (self->rows, variable);
628
629 if (free_res)
630 {
631 gtk_constraint_expression_unref (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
gtk_constraint_solver_substitute_out(GtkConstraintSolver * self,GtkConstraintVariable * old_variable,GtkConstraintExpression * expression)647 gtk_constraint_solver_substitute_out (GtkConstraintSolver *self,
648 GtkConstraintVariable *old_variable,
649 GtkConstraintExpression *expression)
650 {
651 GtkConstraintVariableSet *cset = g_hash_table_lookup (self->columns, old_variable);
652 if (cset != NULL)
653 {
654 GtkConstraintVariableSetIter iter;
655 GtkConstraintVariable *v;
656
657 gtk_constraint_variable_set_iter_init (&iter, cset);
658 while (gtk_constraint_variable_set_iter_next (&iter, &v))
659 {
660 GtkConstraintExpression *row = g_hash_table_lookup (self->rows, v);
661
662 gtk_constraint_expression_substitute_out (row, old_variable, expression, v, self);
663
664 if (gtk_constraint_variable_is_restricted (v) &&
665 gtk_constraint_expression_get_constant (row) < 0)
666 g_ptr_array_add (self->infeasible_rows, v);
667 }
668 }
669
670 if (gtk_constraint_variable_is_external (old_variable))
671 {
672 g_hash_table_add (self->external_rows, old_variable);
673 g_hash_table_remove (self->external_parametric_vars, old_variable);
674 }
675
676 g_hash_table_remove (self->columns, 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
gtk_constraint_solver_pivot(GtkConstraintSolver * self,GtkConstraintVariable * entry_var,GtkConstraintVariable * exit_var)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 (entry_var);
700 else
701 g_critical ("INTERNAL: invalid entry variable during pivot");
702
703 if (exit_var != NULL)
704 gtk_constraint_variable_ref (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, exit_var, FALSE);
710
711 gtk_constraint_expression_change_subject (expr, exit_var, entry_var);
712 gtk_constraint_solver_substitute_out (self, entry_var, expr);
713
714 if (gtk_constraint_variable_is_external (entry_var))
715 g_hash_table_remove (self->external_parametric_vars, entry_var);
716
717 gtk_constraint_solver_add_row (self, entry_var, expr);
718
719 gtk_constraint_variable_unref (entry_var);
720 gtk_constraint_variable_unref (exit_var);
721 gtk_constraint_expression_unref (expr);
722 }
723
724 static void
gtk_constraint_solver_optimize(GtkConstraintSolver * self,GtkConstraintVariable * z)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 (self->rows, 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 (z);
743 g_message ("optimize: %s", str);
744 g_free (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 double r;
758
759 gtk_constraint_expression_iter_init (&eiter, z_row);
760 while (gtk_constraint_expression_iter_prev (&eiter, &t_v, &t_c))
761 {
762 if (gtk_constraint_variable_is_pivotable (t_v) && t_c < objective_coefficient)
763 {
764 entry = t_v;
765 objective_coefficient = t_c;
766 break;
767 }
768 }
769
770 if (objective_coefficient >= -1e-8)
771 break;
772
773 min_ratio = DBL_MAX;
774 r = 0;
775
776 column_vars = gtk_constraint_solver_get_column_set (self, entry);
777 gtk_constraint_variable_set_iter_init (&viter, column_vars);
778 while (gtk_constraint_variable_set_iter_next (&viter, &v))
779 {
780 if (gtk_constraint_variable_is_pivotable (v))
781 {
782 GtkConstraintExpression *expr = g_hash_table_lookup (self->rows, v);
783 double coeff = gtk_constraint_expression_get_coefficient (expr, entry);
784
785 if (coeff < 0.0)
786 {
787 double constant = gtk_constraint_expression_get_constant (expr);
788
789 r = -1.0 * constant / coeff;
790 if (r < min_ratio)
791 {
792 min_ratio = r;
793 exit = v;
794 }
795 }
796 }
797 }
798
799 if (min_ratio == DBL_MAX)
800 {
801 GTK_NOTE (CONSTRAINTS, g_message ("Unbounded objective variable during optimization"));
802 break;
803 }
804
805 #ifdef G_ENABLE_DEBUG
806 if (GTK_DEBUG_CHECK (CONSTRAINTS))
807 {
808 char *entry_s = gtk_constraint_variable_to_string (entry);
809 char *exit_s = gtk_constraint_variable_to_string (exit);
810 g_message ("pivot(entry: %s, exit: %s)", entry_s, exit_s);
811 g_free (entry_s);
812 g_free (exit_s);
813 }
814 #endif
815
816 gtk_constraint_solver_pivot (self, entry, exit);
817 }
818
819 GTK_NOTE (CONSTRAINTS,
820 g_message ("solver.optimize.time := %.3f ms (pass: %d)",
821 (float) (g_get_monotonic_time () - start_time) / 1000.f,
822 self->optimize_count));
823 }
824
825 /*< private >
826 * gtk_constraint_solver_new_expression:
827 * @self: a `GtkConstraintSolver`
828 * @constraint: a `GtkConstraintRef`
829 * @eplus_p: (out) (optional): the positive error variable
830 * @eminus_p: (out) (optional): the negative error variable
831 * @prev_constant_p: the constant part of the @constraint's expression
832 *
833 * Creates a new expression for the @constraint, replacing
834 * any basic variable with their expressions, and normalizing
835 * the terms to avoid a negative constant.
836 *
837 * If the @constraint is not required, this function will add
838 * error variables with the appropriate weight to the tableau.
839 *
840 * Returns: (transfer full): the new expression for the constraint
841 */
842 static GtkConstraintExpression *
gtk_constraint_solver_new_expression(GtkConstraintSolver * self,GtkConstraintRef * constraint,GtkConstraintVariable ** eplus_p,GtkConstraintVariable ** eminus_p,double * prev_constant_p)843 gtk_constraint_solver_new_expression (GtkConstraintSolver *self,
844 GtkConstraintRef *constraint,
845 GtkConstraintVariable **eplus_p,
846 GtkConstraintVariable **eminus_p,
847 double *prev_constant_p)
848 {
849 GtkConstraintExpression *cn_expr = constraint->expression;
850 GtkConstraintExpression *expr;
851 GtkConstraintExpressionIter eiter;
852 GtkConstraintVariable *t_v;
853 double t_c;
854
855 if (eplus_p != NULL)
856 *eplus_p = NULL;
857 if (eminus_p != NULL)
858 *eminus_p = NULL;
859 if (prev_constant_p != NULL)
860 *prev_constant_p = 0.0;
861
862 expr = gtk_constraint_expression_new (gtk_constraint_expression_get_constant (cn_expr));
863
864 gtk_constraint_expression_iter_init (&eiter, cn_expr);
865 while (gtk_constraint_expression_iter_next (&eiter, &t_v, &t_c))
866 {
867 GtkConstraintExpression *e = g_hash_table_lookup (self->rows, t_v);
868
869 if (e == NULL)
870 gtk_constraint_expression_add_variable (expr, t_v, t_c, NULL, self);
871 else
872 gtk_constraint_expression_add_expression (expr, e, t_c, NULL, self);
873 }
874
875 if (gtk_constraint_ref_is_inequality (constraint))
876 {
877 GtkConstraintVariable *slack_var;
878
879 /* If the constraint is an inequality, we add a slack variable to
880 * turn it into an equality, e.g. from
881 *
882 * expr ≥ 0
883 *
884 * to
885 *
886 * expr - slack = 0
887 *
888 * Additionally, if the constraint is not required we add an
889 * error variable with the weight of the constraint:
890 *
891 * expr - slack + error = 0
892 */
893 self->slack_counter += 1;
894
895 slack_var = gtk_constraint_variable_new_slack ("s");
896 gtk_constraint_expression_set_variable (expr, slack_var, -1.0);
897 gtk_constraint_variable_unref (slack_var);
898
899 g_hash_table_insert (self->marker_vars, constraint, slack_var);
900
901 if (!gtk_constraint_ref_is_required (constraint))
902 {
903 GtkConstraintExpression *z_row;
904 GtkConstraintVariable *eminus;
905
906 self->slack_counter += 1;
907
908 eminus = gtk_constraint_variable_new_slack ("em");
909 gtk_constraint_expression_set_variable (expr, eminus, 1.0);
910 gtk_constraint_variable_unref (eminus);
911
912 z_row = g_hash_table_lookup (self->rows, self->objective);
913 gtk_constraint_expression_set_variable (z_row, eminus, constraint->strength);
914
915 gtk_constraint_solver_insert_error_variable (self, constraint, eminus);
916 gtk_constraint_solver_note_added_variable (self, eminus, self->objective);
917 gtk_constraint_variable_unref (eminus);
918 }
919 }
920 else
921 {
922 GtkConstraintVariable *dummy_var;
923
924 if (gtk_constraint_ref_is_required (constraint))
925 {
926 /* If the constraint is required, we use a dummy marker variable;
927 * the dummy won't be allowed to enter the basis of the tableau
928 * when pivoting.
929 */
930 self->dummy_counter += 1;
931
932 dummy_var = gtk_constraint_variable_new_dummy ("dummy");
933
934 if (eplus_p != NULL)
935 *eplus_p = dummy_var;
936 if (eminus_p != NULL)
937 *eminus_p = dummy_var;
938 if (prev_constant_p != NULL)
939 *prev_constant_p = gtk_constraint_expression_get_constant (cn_expr);
940
941 gtk_constraint_expression_set_variable (expr, dummy_var, 1.0);
942 g_hash_table_insert (self->marker_vars, constraint, dummy_var);
943
944 gtk_constraint_variable_unref (dummy_var);
945 }
946 else
947 {
948 GtkConstraintVariable *eplus, *eminus;
949 GtkConstraintExpression *z_row;
950
951 /* Since the constraint is a non-required equality, we need to
952 * add error variables around it, i.e. turn it from:
953 *
954 * expr = 0
955 *
956 * to:
957 *
958 * expr - eplus + eminus = 0
959 */
960 self->slack_counter += 1;
961
962 eplus = gtk_constraint_variable_new_slack ("ep");
963 eminus = gtk_constraint_variable_new_slack ("em");
964
965 gtk_constraint_expression_set_variable (expr, eplus, -1.0);
966 gtk_constraint_expression_set_variable (expr, eminus, 1.0);
967
968 g_hash_table_insert (self->marker_vars, constraint, eplus);
969
970 z_row = g_hash_table_lookup (self->rows, self->objective);
971
972 gtk_constraint_expression_set_variable (z_row, eplus, constraint->strength);
973 gtk_constraint_expression_set_variable (z_row, eminus, constraint->strength);
974 gtk_constraint_solver_note_added_variable (self, eplus, self->objective);
975 gtk_constraint_solver_note_added_variable (self, eminus, self->objective);
976
977 gtk_constraint_solver_insert_error_variable (self, constraint, eplus);
978 gtk_constraint_solver_insert_error_variable (self, constraint, eminus);
979
980 if (constraint->is_stay)
981 {
982 g_ptr_array_add (self->stay_error_vars, gtk_constraint_variable_pair_new (eplus, eminus));
983 }
984 else if (constraint->is_edit)
985 {
986 if (eplus_p != NULL)
987 *eplus_p = eplus;
988 if (eminus_p != NULL)
989 *eminus_p = eminus;
990 if (prev_constant_p != NULL)
991 *prev_constant_p = gtk_constraint_expression_get_constant (cn_expr);
992 }
993
994 gtk_constraint_variable_unref (eplus);
995 gtk_constraint_variable_unref (eminus);
996 }
997 }
998
999 if (gtk_constraint_expression_get_constant (expr) < 0.0)
1000 gtk_constraint_expression_multiply_by (expr, -1.0);
1001
1002 return expr;
1003 }
1004
1005 static void
gtk_constraint_solver_dual_optimize(GtkConstraintSolver * self)1006 gtk_constraint_solver_dual_optimize (GtkConstraintSolver *self)
1007 {
1008 GtkConstraintExpression *z_row = g_hash_table_lookup (self->rows, self->objective);
1009 #ifdef G_ENABLE_DEBUG
1010 gint64 start_time = g_get_monotonic_time ();
1011 #endif
1012
1013 /* We iterate until we don't have any more infeasible rows; the pivot()
1014 * at the end of the loop iteration may add or remove infeasible rows
1015 * as well
1016 */
1017 while (self->infeasible_rows->len != 0)
1018 {
1019 GtkConstraintVariable *entry_var, *exit_var, *t_v;
1020 GtkConstraintExpressionIter eiter;
1021 GtkConstraintExpression *expr;
1022 double ratio, t_c;
1023
1024 /* Pop the last element of the array */
1025 exit_var = g_ptr_array_index (self->infeasible_rows, self->infeasible_rows->len - 1);
1026 g_ptr_array_set_size (self->infeasible_rows, self->infeasible_rows->len - 1);
1027
1028 expr = g_hash_table_lookup (self->rows, exit_var);
1029 if (expr == NULL)
1030 continue;
1031
1032 if (gtk_constraint_expression_get_constant (expr) >= 0.0)
1033 continue;
1034
1035 ratio = DBL_MAX;
1036 entry_var = NULL;
1037
1038 gtk_constraint_expression_iter_init (&eiter, expr);
1039 while (gtk_constraint_expression_iter_next (&eiter, &t_v, &t_c))
1040 {
1041 if (t_c > 0.0 && gtk_constraint_variable_is_pivotable (t_v))
1042 {
1043 double zc = gtk_constraint_expression_get_coefficient (z_row, t_v);
1044 double r = zc / t_c;
1045
1046 if (r < ratio)
1047 {
1048 entry_var = t_v;
1049 ratio = r;
1050 }
1051 }
1052 }
1053
1054 if (ratio == DBL_MAX)
1055 g_critical ("INTERNAL: ratio == DBL_MAX in dual_optimize");
1056
1057 gtk_constraint_solver_pivot (self, entry_var, exit_var);
1058 }
1059
1060 GTK_NOTE (CONSTRAINTS,
1061 g_message ("dual_optimize.time := %.3f ms",
1062 (float) (g_get_monotonic_time () - start_time) / 1000.f));
1063 }
1064
1065 static void
gtk_constraint_solver_delta_edit_constant(GtkConstraintSolver * self,double delta,GtkConstraintVariable * plus_error_var,GtkConstraintVariable * minus_error_var)1066 gtk_constraint_solver_delta_edit_constant (GtkConstraintSolver *self,
1067 double delta,
1068 GtkConstraintVariable *plus_error_var,
1069 GtkConstraintVariable *minus_error_var)
1070 {
1071 GtkConstraintExpression *plus_expr, *minus_expr;
1072 GtkConstraintVariable *basic_var;
1073 GtkConstraintVariableSet *column_set;
1074 GtkConstraintVariableSetIter iter;
1075
1076 plus_expr = g_hash_table_lookup (self->rows, plus_error_var);
1077 if (plus_expr != NULL)
1078 {
1079 double new_constant = gtk_constraint_expression_get_constant (plus_expr) + delta;
1080
1081 gtk_constraint_expression_set_constant (plus_expr, new_constant);
1082
1083 if (new_constant < 0.0)
1084 g_ptr_array_add (self->infeasible_rows, plus_error_var);
1085
1086 return;
1087 }
1088
1089 minus_expr = g_hash_table_lookup (self->rows, minus_error_var);
1090 if (minus_expr != NULL)
1091 {
1092 double new_constant = gtk_constraint_expression_get_constant (minus_expr) - delta;
1093
1094 gtk_constraint_expression_set_constant (minus_expr, new_constant);
1095
1096 if (new_constant < 0.0)
1097 g_ptr_array_add (self->infeasible_rows, minus_error_var);
1098
1099 return;
1100 }
1101
1102 column_set = g_hash_table_lookup (self->columns, minus_error_var);
1103 if (column_set == NULL)
1104 {
1105 g_critical ("INTERNAL: Columns are unset during delta edit");
1106 return;
1107 }
1108
1109 gtk_constraint_variable_set_iter_init (&iter, column_set);
1110 while (gtk_constraint_variable_set_iter_next (&iter, &basic_var))
1111 {
1112 GtkConstraintExpression *expr;
1113 double c, new_constant;
1114
1115 expr = g_hash_table_lookup (self->rows, basic_var);
1116 c = gtk_constraint_expression_get_coefficient (expr, minus_error_var);
1117
1118 new_constant = gtk_constraint_expression_get_constant (expr) + (c * delta);
1119 gtk_constraint_expression_set_constant (expr, new_constant);
1120
1121 if (gtk_constraint_variable_is_restricted (basic_var) && new_constant < 0.0)
1122 g_ptr_array_add (self->infeasible_rows, basic_var);
1123 }
1124 }
1125
1126 static GtkConstraintVariable *
gtk_constraint_solver_choose_subject(GtkConstraintSolver * self,GtkConstraintExpression * expression)1127 gtk_constraint_solver_choose_subject (GtkConstraintSolver *self,
1128 GtkConstraintExpression *expression)
1129 {
1130 GtkConstraintExpressionIter eiter;
1131 GtkConstraintVariable *subject = NULL;
1132 GtkConstraintVariable *retval = NULL;
1133 GtkConstraintVariable *t_v;
1134 gboolean found_unrestricted = FALSE;
1135 gboolean found_new_restricted = FALSE;
1136 gboolean retval_found = FALSE;
1137 double coeff = 0.0;
1138 double t_c;
1139
1140 gtk_constraint_expression_iter_init (&eiter, expression);
1141 while (gtk_constraint_expression_iter_prev (&eiter, &t_v, &t_c))
1142 {
1143 if (found_unrestricted)
1144 {
1145 if (!gtk_constraint_variable_is_restricted (t_v))
1146 {
1147 if (!g_hash_table_contains (self->columns, t_v))
1148 {
1149 retval_found = TRUE;
1150 retval = t_v;
1151 break;
1152 }
1153 }
1154 }
1155 else
1156 {
1157 if (gtk_constraint_variable_is_restricted (t_v))
1158 {
1159 if (!found_new_restricted &&
1160 !gtk_constraint_variable_is_dummy (t_v) &&
1161 t_c < 0.0)
1162 {
1163 GtkConstraintVariableSet *cset = g_hash_table_lookup (self->columns, t_v);
1164
1165 if (cset == NULL ||
1166 (gtk_constraint_variable_set_is_singleton (cset) &&
1167 g_hash_table_contains (self->columns, self->objective)))
1168 {
1169 subject = t_v;
1170 found_new_restricted = TRUE;
1171 }
1172 }
1173 }
1174 else
1175 {
1176 subject = t_v;
1177 found_unrestricted = TRUE;
1178 }
1179 }
1180 }
1181
1182 if (retval_found)
1183 return retval;
1184
1185 if (subject != NULL)
1186 return subject;
1187
1188 gtk_constraint_expression_iter_init (&eiter, expression);
1189 while (gtk_constraint_expression_iter_prev (&eiter, &t_v, &t_c))
1190 {
1191 if (!gtk_constraint_variable_is_dummy (t_v))
1192 return NULL;
1193
1194 if (!g_hash_table_contains (self->columns, t_v))
1195 {
1196 subject = t_v;
1197 coeff = t_c;
1198 }
1199 }
1200
1201 if (!G_APPROX_VALUE (gtk_constraint_expression_get_constant (expression), 0.0, 0.001))
1202 {
1203 GTK_NOTE (CONSTRAINTS,
1204 g_message ("Unable to satisfy required constraint (choose_subject)"));
1205 return NULL;
1206 }
1207
1208 if (coeff > 0)
1209 gtk_constraint_expression_multiply_by (expression, -1.0);
1210
1211 return subject;
1212 }
1213
1214 static gboolean
gtk_constraint_solver_try_adding_directly(GtkConstraintSolver * self,GtkConstraintExpression * expression)1215 gtk_constraint_solver_try_adding_directly (GtkConstraintSolver *self,
1216 GtkConstraintExpression *expression)
1217 {
1218 GtkConstraintVariable *subject;
1219
1220 subject = gtk_constraint_solver_choose_subject (self, expression);
1221 if (subject == NULL)
1222 return FALSE;
1223
1224 gtk_constraint_variable_ref (subject);
1225
1226 gtk_constraint_expression_new_subject (expression, subject);
1227 if (gtk_constraint_solver_column_has_key (self, subject))
1228 gtk_constraint_solver_substitute_out (self, subject, expression);
1229
1230 gtk_constraint_solver_add_row (self, subject, expression);
1231
1232 gtk_constraint_variable_unref (subject);
1233
1234 return TRUE;
1235 }
1236
1237 static void
gtk_constraint_solver_add_with_artificial_variable(GtkConstraintSolver * self,GtkConstraintExpression * expression)1238 gtk_constraint_solver_add_with_artificial_variable (GtkConstraintSolver *self,
1239 GtkConstraintExpression *expression)
1240 {
1241 GtkConstraintVariable *av, *az;
1242 GtkConstraintExpression *az_row;
1243 GtkConstraintExpression *az_tableau_row;
1244 GtkConstraintExpression *e;
1245
1246 av = gtk_constraint_variable_new_slack ("a");
1247 self->artificial_counter += 1;
1248
1249 az = gtk_constraint_variable_new_objective ("az");
1250
1251 az_row = gtk_constraint_expression_clone (expression);
1252
1253 gtk_constraint_solver_add_row (self, az, az_row);
1254 gtk_constraint_solver_add_row (self, av, expression);
1255
1256 gtk_constraint_expression_unref (az_row);
1257 gtk_constraint_variable_unref (av);
1258 gtk_constraint_variable_unref (az);
1259
1260 gtk_constraint_solver_optimize (self, az);
1261
1262 az_tableau_row = g_hash_table_lookup (self->rows, az);
1263 if (!G_APPROX_VALUE (gtk_constraint_expression_get_constant (az_tableau_row), 0.0, 0.001))
1264 {
1265 gtk_constraint_solver_remove_column (self, av);
1266 gtk_constraint_solver_remove_row (self, az, TRUE);
1267
1268 #ifdef G_ENABLE_DEBUG
1269 if (GTK_DEBUG_CHECK (CONSTRAINTS))
1270 {
1271 char *str = gtk_constraint_expression_to_string (expression);
1272 g_message ("Unable to satisfy a required constraint (add): %s", str);
1273 g_free (str);
1274 }
1275 #endif
1276
1277 return;
1278 }
1279
1280 e = g_hash_table_lookup (self->rows, av);
1281 if (e != NULL)
1282 {
1283 GtkConstraintVariable *entry_var;
1284
1285 if (gtk_constraint_expression_is_constant (e))
1286 {
1287 gtk_constraint_solver_remove_row (self, av, TRUE);
1288 gtk_constraint_solver_remove_row (self, az, TRUE);
1289 return;
1290 }
1291
1292 entry_var = gtk_constraint_expression_get_pivotable_variable (e);
1293 if (entry_var == NULL)
1294 return;
1295
1296 gtk_constraint_solver_pivot (self, entry_var, av);
1297 }
1298
1299 g_assert (!g_hash_table_contains (self->rows, av));
1300
1301 gtk_constraint_solver_remove_column (self, av);
1302 gtk_constraint_solver_remove_row (self, az, TRUE);
1303 }
1304
1305 static void
gtk_constraint_solver_add_constraint_internal(GtkConstraintSolver * self,GtkConstraintRef * constraint)1306 gtk_constraint_solver_add_constraint_internal (GtkConstraintSolver *self,
1307 GtkConstraintRef *constraint)
1308 {
1309 GtkConstraintExpression *expr;
1310 GtkConstraintVariable *eplus;
1311 GtkConstraintVariable *eminus;
1312 double prev_constant;
1313
1314 expr = gtk_constraint_solver_new_expression (self, constraint,
1315 &eplus,
1316 &eminus,
1317 &prev_constant);
1318
1319 #ifdef G_ENABLE_DEBUG
1320 if (GTK_DEBUG_CHECK (CONSTRAINTS))
1321 {
1322 char *expr_s = gtk_constraint_expression_to_string (expr);
1323 char *ref_s = gtk_constraint_ref_to_string (constraint);
1324 g_message ("Adding constraint '%s' (normalized expression: '%s')", ref_s, expr_s);
1325 g_free (ref_s);
1326 g_free (expr_s);
1327 }
1328 #endif
1329
1330 if (constraint->is_stay)
1331 {
1332 StayInfo *si = g_new (StayInfo, 1);
1333
1334 si->constraint = constraint;
1335
1336 g_hash_table_insert (self->stay_var_map, constraint->variable, si);
1337 }
1338 else if (constraint->is_edit)
1339 {
1340 EditInfo *ei = g_new (EditInfo, 1);
1341
1342 ei->constraint = constraint;
1343 ei->eplus = eplus;
1344 ei->eminus = eminus;
1345 ei->prev_constant = prev_constant;
1346
1347 g_hash_table_insert (self->edit_var_map, constraint->variable, ei);
1348 }
1349
1350 if (!gtk_constraint_solver_try_adding_directly (self, expr))
1351 gtk_constraint_solver_add_with_artificial_variable (self, expr);
1352
1353 gtk_constraint_expression_unref (expr);
1354
1355 self->needs_solving = TRUE;
1356
1357 if (self->auto_solve)
1358 {
1359 gtk_constraint_solver_optimize (self, self->objective);
1360 gtk_constraint_solver_set_external_variables (self);
1361 }
1362
1363 constraint->solver = self;
1364
1365 g_hash_table_add (self->constraints, constraint);
1366 }
1367
1368 /*< private >
1369 * gtk_constraint_solver_new:
1370 *
1371 * Creates a new `GtkConstraintSolver` instance.
1372 *
1373 * Returns: the newly created `GtkConstraintSolver`
1374 */
1375 GtkConstraintSolver *
gtk_constraint_solver_new(void)1376 gtk_constraint_solver_new (void)
1377 {
1378 return g_object_new (GTK_TYPE_CONSTRAINT_SOLVER, NULL);
1379 }
1380
1381 /*< private >
1382 * gtk_constraint_solver_freeze:
1383 * @solver: a `GtkConstraintSolver`
1384 *
1385 * Freezes the solver; any constraint addition or removal will not
1386 * be automatically solved until gtk_constraint_solver_thaw() is
1387 * called.
1388 */
1389 void
gtk_constraint_solver_freeze(GtkConstraintSolver * solver)1390 gtk_constraint_solver_freeze (GtkConstraintSolver *solver)
1391 {
1392 g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
1393
1394 solver->freeze_count += 1;
1395
1396 if (solver->freeze_count > 0)
1397 solver->auto_solve = FALSE;
1398 }
1399
1400 /*< private >
1401 * gtk_constraint_solver_thaw:
1402 * @solver: a `GtkConstraintSolver`
1403 *
1404 * Thaws a frozen `GtkConstraintSolver`.
1405 */
1406 void
gtk_constraint_solver_thaw(GtkConstraintSolver * solver)1407 gtk_constraint_solver_thaw (GtkConstraintSolver *solver)
1408 {
1409 g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
1410 g_return_if_fail (solver->freeze_count > 0);
1411
1412 solver->freeze_count -= 1;
1413
1414 if (solver->freeze_count == 0)
1415 {
1416 solver->auto_solve = TRUE;
1417 gtk_constraint_solver_resolve (solver);
1418 }
1419 }
1420
1421 /*< private >
1422 * gtk_constraint_solver_note_added_variable:
1423 * @self: a `GtkConstraintSolver`
1424 * @variable: a `GtkConstraintVariable`
1425 * @subject: a `GtkConstraintVariable`
1426 *
1427 * Adds a new @variable into the tableau of a `GtkConstraintSolver`.
1428 *
1429 * This function is typically called by `GtkConstraintExpression`, and
1430 * should never be directly called.
1431 */
1432 void
gtk_constraint_solver_note_added_variable(GtkConstraintSolver * self,GtkConstraintVariable * variable,GtkConstraintVariable * subject)1433 gtk_constraint_solver_note_added_variable (GtkConstraintSolver *self,
1434 GtkConstraintVariable *variable,
1435 GtkConstraintVariable *subject)
1436 {
1437 if (subject != NULL)
1438 gtk_constraint_solver_insert_column_variable (self, variable, subject);
1439 }
1440
1441 /*< private >
1442 * gtk_constraint_solver_note_removed_variable:
1443 * @self: a `GtkConstraintSolver`
1444 * @variable: a `GtkConstraintVariable`
1445 * @subject: a `GtkConstraintVariable`
1446 *
1447 * Removes a @variable from the tableau of a `GtkConstraintSolver`.
1448 *
1449 * This function is typically called by `GtkConstraintExpression`, and
1450 * should never be directly called.
1451 */
1452 void
gtk_constraint_solver_note_removed_variable(GtkConstraintSolver * self,GtkConstraintVariable * variable,GtkConstraintVariable * subject)1453 gtk_constraint_solver_note_removed_variable (GtkConstraintSolver *self,
1454 GtkConstraintVariable *variable,
1455 GtkConstraintVariable *subject)
1456 {
1457 GtkConstraintVariableSet *set;
1458
1459 set = g_hash_table_lookup (self->columns, variable);
1460 if (set != NULL && subject != NULL)
1461 gtk_constraint_variable_set_remove (set, subject);
1462 }
1463
1464 /*< private >
1465 * gtk_constraint_solver_create_variable:
1466 * @self: a `GtkConstraintSolver`
1467 * @prefix: (nullable): the prefix of the variable
1468 * @name: (nullable): the name of the variable
1469 * @value: the initial value of the variable
1470 *
1471 * Creates a new variable inside the @solver.
1472 *
1473 * Returns: (transfer full): the newly created variable
1474 */
1475 GtkConstraintVariable *
gtk_constraint_solver_create_variable(GtkConstraintSolver * self,const char * prefix,const char * name,double value)1476 gtk_constraint_solver_create_variable (GtkConstraintSolver *self,
1477 const char *prefix,
1478 const char *name,
1479 double value)
1480 {
1481 GtkConstraintVariable *res;
1482
1483 res = gtk_constraint_variable_new (prefix, name);
1484 gtk_constraint_variable_set_value (res, value);
1485
1486 self->var_counter++;
1487
1488 return res;
1489 }
1490
1491 /*< private >
1492 * gtk_constraint_solver_resolve:
1493 * @solver: a `GtkConstraintSolver`
1494 *
1495 * Resolves the constraints currently stored in @solver.
1496 */
1497 void
gtk_constraint_solver_resolve(GtkConstraintSolver * solver)1498 gtk_constraint_solver_resolve (GtkConstraintSolver *solver)
1499 {
1500 #ifdef G_ENABLE_DEBUG
1501 gint64 start_time = g_get_monotonic_time ();
1502 #endif
1503
1504 g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
1505
1506 gtk_constraint_solver_dual_optimize (solver);
1507 gtk_constraint_solver_set_external_variables (solver);
1508
1509 g_ptr_array_set_size (solver->infeasible_rows, 0);
1510
1511 gtk_constraint_solver_reset_stay_constants (solver);
1512
1513 GTK_NOTE (CONSTRAINTS,
1514 g_message ("resolve.time := %.3f ms",
1515 (float) (g_get_monotonic_time () - start_time) / 1000.f));
1516
1517 solver->needs_solving = FALSE;
1518 }
1519
1520 /*< private >
1521 * gtk_constraint_solver_add_constraint:
1522 * @self: a `GtkConstraintSolver`
1523 * @variable: the subject of the constraint
1524 * @relation: the relation of the constraint
1525 * @expression: the expression of the constraint
1526 * @strength: the strength of the constraint
1527 *
1528 * Adds a new constraint in the form of:
1529 *
1530 * |[
1531 * variable relation expression (strength)
1532 * |]
1533 *
1534 * into the `GtkConstraintSolver`.
1535 *
1536 * Returns: (transfer none): a reference to the newly created
1537 * constraint; you can use the reference to remove the
1538 * constraint from the solver
1539 */
1540 GtkConstraintRef *
gtk_constraint_solver_add_constraint(GtkConstraintSolver * self,GtkConstraintVariable * variable,GtkConstraintRelation relation,GtkConstraintExpression * expression,int strength)1541 gtk_constraint_solver_add_constraint (GtkConstraintSolver *self,
1542 GtkConstraintVariable *variable,
1543 GtkConstraintRelation relation,
1544 GtkConstraintExpression *expression,
1545 int strength)
1546 {
1547 GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
1548
1549 res->solver = self;
1550 res->strength = strength;
1551 res->is_edit = FALSE;
1552 res->is_stay = FALSE;
1553 res->relation = relation;
1554
1555 if (expression == NULL)
1556 res->expression = gtk_constraint_expression_new_from_variable (variable);
1557 else
1558 {
1559 res->expression = expression;
1560
1561 if (variable != NULL)
1562 {
1563 switch (res->relation)
1564 {
1565 case GTK_CONSTRAINT_RELATION_EQ:
1566 gtk_constraint_expression_add_variable (res->expression,
1567 variable, -1.0,
1568 NULL,
1569 self);
1570 break;
1571
1572 case GTK_CONSTRAINT_RELATION_LE:
1573 gtk_constraint_expression_add_variable (res->expression,
1574 variable, -1.0,
1575 NULL,
1576 self);
1577 break;
1578
1579 case GTK_CONSTRAINT_RELATION_GE:
1580 gtk_constraint_expression_multiply_by (res->expression, -1.0);
1581 gtk_constraint_expression_add_variable (res->expression,
1582 variable, 1.0,
1583 NULL,
1584 self);
1585 break;
1586
1587 default:
1588 g_assert_not_reached ();
1589 }
1590 }
1591 }
1592
1593 gtk_constraint_solver_add_constraint_internal (self, res);
1594
1595 return res;
1596 }
1597
1598 /*< private >
1599 * gtk_constraint_solver_add_stay_variable:
1600 * @self: a `GtkConstraintSolver`
1601 * @variable: a stay `GtkConstraintVariable`
1602 * @strength: the strength of the constraint
1603 *
1604 * Adds a constraint on a stay @variable with the given @strength.
1605 *
1606 * A stay variable is an "anchor" in the system: a variable that is
1607 * supposed to stay at the same value.
1608 *
1609 * Returns: (transfer none): a reference to the newly created
1610 * constraint; you can use the reference to remove the
1611 * constraint from the solver
1612 */
1613 GtkConstraintRef *
gtk_constraint_solver_add_stay_variable(GtkConstraintSolver * self,GtkConstraintVariable * variable,int strength)1614 gtk_constraint_solver_add_stay_variable (GtkConstraintSolver *self,
1615 GtkConstraintVariable *variable,
1616 int strength)
1617 {
1618 GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
1619
1620 res->solver = self;
1621 res->variable = gtk_constraint_variable_ref (variable);
1622 res->relation = GTK_CONSTRAINT_RELATION_EQ;
1623 res->strength = strength;
1624 res->is_stay = TRUE;
1625 res->is_edit = FALSE;
1626
1627 res->expression = gtk_constraint_expression_new (gtk_constraint_variable_get_value (res->variable));
1628 gtk_constraint_expression_add_variable (res->expression,
1629 res->variable, -1.0,
1630 NULL,
1631 self);
1632
1633 #ifdef G_ENABLE_DEBUG
1634 if (GTK_DEBUG_CHECK (CONSTRAINTS))
1635 {
1636 char *str = gtk_constraint_expression_to_string (res->expression);
1637 g_message ("Adding stay variable: %s", str);
1638 g_free (str);
1639 }
1640 #endif
1641
1642 gtk_constraint_solver_add_constraint_internal (self, res);
1643
1644 return res;
1645 }
1646
1647 /*< private >
1648 * gtk_constraint_solver_remove_stay_variable:
1649 * @self: a `GtkConstraintSolver`
1650 * @variable: a stay variable
1651 *
1652 * Removes the stay constraint associated to @variable.
1653 *
1654 * This is a convenience function for gtk_constraint_solver_remove_constraint().
1655 */
1656 void
gtk_constraint_solver_remove_stay_variable(GtkConstraintSolver * self,GtkConstraintVariable * variable)1657 gtk_constraint_solver_remove_stay_variable (GtkConstraintSolver *self,
1658 GtkConstraintVariable *variable)
1659 {
1660 StayInfo *si = g_hash_table_lookup (self->stay_var_map, variable);
1661
1662 if (si == NULL)
1663 {
1664 char *str = gtk_constraint_variable_to_string (variable);
1665
1666 g_critical ("Unknown stay variable '%s'", str);
1667
1668 g_free (str);
1669
1670 return;
1671 }
1672
1673 gtk_constraint_solver_remove_constraint (self, si->constraint);
1674 }
1675
1676 /*< private >
1677 * gtk_constraint_solver_add_edit_variable:
1678 * @self: a `GtkConstraintSolver`
1679 * @variable: an edit variable
1680 * @strength: the strength of the constraint
1681 *
1682 * Adds an editable constraint to the @solver.
1683 *
1684 * Editable constraints can be used to suggest values to a
1685 * `GtkConstraintSolver` inside an edit phase, for instance: if
1686 * you want to change the value of a variable without necessarily
1687 * insert a new constraint every time.
1688 *
1689 * See also: gtk_constraint_solver_suggest_value()
1690 *
1691 * Returns: (transfer none): a reference to the newly added constraint
1692 */
1693 GtkConstraintRef *
gtk_constraint_solver_add_edit_variable(GtkConstraintSolver * self,GtkConstraintVariable * variable,int strength)1694 gtk_constraint_solver_add_edit_variable (GtkConstraintSolver *self,
1695 GtkConstraintVariable *variable,
1696 int strength)
1697 {
1698 GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
1699
1700 res->solver = self;
1701 res->variable = gtk_constraint_variable_ref (variable);
1702 res->relation = GTK_CONSTRAINT_RELATION_EQ;
1703 res->strength = strength;
1704 res->is_stay = FALSE;
1705 res->is_edit = TRUE;
1706
1707 res->expression = gtk_constraint_expression_new (gtk_constraint_variable_get_value (variable));
1708 gtk_constraint_expression_add_variable (res->expression,
1709 variable, -1.0,
1710 NULL,
1711 self);
1712
1713 gtk_constraint_solver_add_constraint_internal (self, res);
1714
1715 return res;
1716 }
1717
1718 /*< private >
1719 * gtk_constraint_solver_remove_edit_variable:
1720 * @self: a `GtkConstraintSolver`
1721 * @variable: an edit variable
1722 *
1723 * Removes the edit constraint associated to @variable.
1724 *
1725 * This is a convenience function around gtk_constraint_solver_remove_constraint().
1726 */
1727 void
gtk_constraint_solver_remove_edit_variable(GtkConstraintSolver * self,GtkConstraintVariable * variable)1728 gtk_constraint_solver_remove_edit_variable (GtkConstraintSolver *self,
1729 GtkConstraintVariable *variable)
1730 {
1731 EditInfo *ei = g_hash_table_lookup (self->edit_var_map, variable);
1732
1733 if (ei == NULL)
1734 {
1735 char *str = gtk_constraint_variable_to_string (variable);
1736
1737 g_critical ("Unknown edit variable '%s'", str);
1738
1739 g_free (str);
1740
1741 return;
1742 }
1743
1744 gtk_constraint_solver_remove_constraint (self, ei->constraint);
1745 }
1746
1747 /*< private >
1748 * gtk_constraint_solver_remove_constraint:
1749 * @self: a `GtkConstraintSolver`
1750 * @constraint: a constraint reference
1751 *
1752 * Removes a @constraint from the @solver.
1753 */
1754 void
gtk_constraint_solver_remove_constraint(GtkConstraintSolver * self,GtkConstraintRef * constraint)1755 gtk_constraint_solver_remove_constraint (GtkConstraintSolver *self,
1756 GtkConstraintRef *constraint)
1757 {
1758 GtkConstraintExpression *z_row;
1759 GtkConstraintVariable *marker;
1760 GtkConstraintVariableSet *error_vars;
1761 GtkConstraintVariableSetIter iter;
1762
1763 if (!g_hash_table_contains (self->constraints, constraint))
1764 return;
1765
1766 self->needs_solving = TRUE;
1767
1768 gtk_constraint_solver_reset_stay_constants (self);
1769
1770 z_row = g_hash_table_lookup (self->rows, self->objective);
1771 error_vars = g_hash_table_lookup (self->error_vars, constraint);
1772
1773 if (error_vars != NULL)
1774 {
1775 GtkConstraintVariable *v;
1776
1777 gtk_constraint_variable_set_iter_init (&iter, error_vars);
1778 while (gtk_constraint_variable_set_iter_next (&iter, &v))
1779 {
1780 GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
1781
1782 if (e == NULL)
1783 {
1784 gtk_constraint_expression_add_variable (z_row,
1785 v,
1786 constraint->strength,
1787 self->objective,
1788 self);
1789 }
1790 else
1791 {
1792 gtk_constraint_expression_add_expression (z_row,
1793 e,
1794 constraint->strength,
1795 self->objective,
1796 self);
1797 }
1798 }
1799 }
1800
1801 marker = g_hash_table_lookup (self->marker_vars, constraint);
1802 if (marker == NULL)
1803 {
1804 g_critical ("Constraint %p not found", constraint);
1805 return;
1806 }
1807
1808 g_hash_table_remove (self->marker_vars, constraint);
1809
1810 if (g_hash_table_lookup (self->rows, marker) == NULL)
1811 {
1812 GtkConstraintVariableSet *set = g_hash_table_lookup (self->columns, marker);
1813 GtkConstraintVariable *exit_var = NULL;
1814 GtkConstraintVariable *v;
1815 double min_ratio = 0;
1816
1817 if (set == NULL)
1818 goto no_columns;
1819
1820 gtk_constraint_variable_set_iter_init (&iter, set);
1821 while (gtk_constraint_variable_set_iter_next (&iter, &v))
1822 {
1823 if (gtk_constraint_variable_is_restricted (v))
1824 {
1825 GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
1826 double coeff = gtk_constraint_expression_get_coefficient (e, marker);
1827
1828 if (coeff < 0.0)
1829 {
1830 double r = -gtk_constraint_expression_get_constant (e) / coeff;
1831
1832 if (exit_var == NULL ||
1833 r < min_ratio ||
1834 G_APPROX_VALUE (r, min_ratio, 0.0001))
1835 {
1836 min_ratio = r;
1837 exit_var = v;
1838 }
1839 }
1840 }
1841 }
1842
1843 if (exit_var == NULL)
1844 {
1845 gtk_constraint_variable_set_iter_init (&iter, set);
1846 while (gtk_constraint_variable_set_iter_next (&iter, &v))
1847 {
1848 if (gtk_constraint_variable_is_restricted (v))
1849 {
1850 GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
1851 double coeff = gtk_constraint_expression_get_coefficient (e, marker);
1852 double r = 0.0;
1853
1854 if (!G_APPROX_VALUE (coeff, 0.0, 0.0001))
1855 r = gtk_constraint_expression_get_constant (e) / coeff;
1856
1857 if (exit_var == NULL || r < min_ratio)
1858 {
1859 min_ratio = r;
1860 exit_var = v;
1861 }
1862 }
1863 }
1864 }
1865
1866 if (exit_var == NULL)
1867 {
1868 if (gtk_constraint_variable_set_is_empty (set))
1869 gtk_constraint_solver_remove_column (self, marker);
1870 else
1871 {
1872 gtk_constraint_variable_set_iter_init (&iter, set);
1873 while (gtk_constraint_variable_set_iter_next (&iter, &v))
1874 {
1875 if (v != self->objective)
1876 {
1877 exit_var = v;
1878 break;
1879 }
1880 }
1881 }
1882 }
1883
1884 if (exit_var != NULL)
1885 gtk_constraint_solver_pivot (self, marker, exit_var);
1886 }
1887
1888 no_columns:
1889 if (g_hash_table_lookup (self->rows, marker) != NULL)
1890 gtk_constraint_solver_remove_row (self, marker, TRUE);
1891 else
1892 gtk_constraint_variable_unref (marker);
1893
1894 if (error_vars != NULL)
1895 {
1896 GtkConstraintVariable *v;
1897
1898 gtk_constraint_variable_set_iter_init (&iter, error_vars);
1899 while (gtk_constraint_variable_set_iter_next (&iter, &v))
1900 {
1901 if (v != marker)
1902 gtk_constraint_solver_remove_column (self, v);
1903 }
1904 }
1905
1906 if (constraint->is_stay)
1907 {
1908 if (error_vars != NULL)
1909 {
1910 GPtrArray *remaining =
1911 g_ptr_array_new_with_free_func ((GDestroyNotify) gtk_constraint_variable_pair_free);
1912
1913 int i = 0;
1914
1915 for (i = 0; i < self->stay_error_vars->len; i++)
1916 {
1917 GtkConstraintVariablePair *pair = g_ptr_array_index (self->stay_error_vars, i);
1918 gboolean found = FALSE;
1919
1920 if (gtk_constraint_variable_set_remove (error_vars, pair->first))
1921 found = TRUE;
1922
1923 if (gtk_constraint_variable_set_remove (error_vars, pair->second))
1924 found = FALSE;
1925
1926 if (!found)
1927 g_ptr_array_add (remaining, gtk_constraint_variable_pair_new (pair->first, pair->second));
1928 }
1929
1930 g_clear_pointer (&self->stay_error_vars, g_ptr_array_unref);
1931 self->stay_error_vars = remaining;
1932 }
1933
1934 g_hash_table_remove (self->stay_var_map, constraint->variable);
1935 }
1936 else if (constraint->is_edit)
1937 {
1938 EditInfo *ei = g_hash_table_lookup (self->edit_var_map, constraint->variable);
1939
1940 gtk_constraint_solver_remove_column (self, ei->eminus);
1941
1942 g_hash_table_remove (self->edit_var_map, constraint->variable);
1943 }
1944
1945 if (error_vars != NULL)
1946 g_hash_table_remove (self->error_vars, constraint);
1947
1948 if (self->auto_solve)
1949 {
1950 gtk_constraint_solver_optimize (self, self->objective);
1951 gtk_constraint_solver_set_external_variables (self);
1952 }
1953
1954 g_hash_table_remove (self->constraints, constraint);
1955 }
1956
1957 /*< private >
1958 * gtk_constraint_solver_suggest_value:
1959 * @self: a `GtkConstraintSolver`
1960 * @variable: a `GtkConstraintVariable`
1961 * @value: the suggested value for @variable
1962 *
1963 * Suggests a new @value for an edit @variable.
1964 *
1965 * The @variable must be an edit variable, and the solver must be
1966 * in an edit phase.
1967 */
1968 void
gtk_constraint_solver_suggest_value(GtkConstraintSolver * self,GtkConstraintVariable * variable,double value)1969 gtk_constraint_solver_suggest_value (GtkConstraintSolver *self,
1970 GtkConstraintVariable *variable,
1971 double value)
1972 {
1973 EditInfo *ei = g_hash_table_lookup (self->edit_var_map, variable);
1974 double delta;
1975 if (ei == NULL)
1976 {
1977 g_critical ("Suggesting value '%g' but variable %p is not editable",
1978 value, variable);
1979 return;
1980 }
1981
1982 if (!self->in_edit_phase)
1983 {
1984 g_critical ("Suggesting value '%g' for variable '%p' but solver is "
1985 "not in an edit phase",
1986 value, variable);
1987 return;
1988 }
1989
1990 delta = value - ei->prev_constant;
1991 ei->prev_constant = value;
1992
1993 gtk_constraint_solver_delta_edit_constant (self, delta, ei->eplus, ei->eminus);
1994 }
1995
1996 /*< private >
1997 * gtk_constraint_solver_has_stay_variable:
1998 * @solver: a `GtkConstraintSolver`
1999 * @variable: a `GtkConstraintVariable`
2000 *
2001 * Checks whether @variable is a stay variable.
2002 *
2003 * Returns: %TRUE if the variable is a stay variable
2004 */
2005 gboolean
gtk_constraint_solver_has_stay_variable(GtkConstraintSolver * solver,GtkConstraintVariable * variable)2006 gtk_constraint_solver_has_stay_variable (GtkConstraintSolver *solver,
2007 GtkConstraintVariable *variable)
2008 {
2009 g_return_val_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver), FALSE);
2010 g_return_val_if_fail (variable != NULL, FALSE);
2011
2012 return g_hash_table_contains (solver->stay_var_map, variable);
2013 }
2014
2015 /*< private >
2016 * gtk_constraint_solver_has_edit_variable:
2017 * @solver: a `GtkConstraintSolver`
2018 * @variable: a `GtkConstraintVariable`
2019 *
2020 * Checks whether @variable is an edit variable.
2021 *
2022 * Returns: %TRUE if the variable is an edit variable
2023 */
2024 gboolean
gtk_constraint_solver_has_edit_variable(GtkConstraintSolver * solver,GtkConstraintVariable * variable)2025 gtk_constraint_solver_has_edit_variable (GtkConstraintSolver *solver,
2026 GtkConstraintVariable *variable)
2027 {
2028 g_return_val_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver), FALSE);
2029 g_return_val_if_fail (variable != NULL, FALSE);
2030
2031 return g_hash_table_contains (solver->edit_var_map, variable);
2032 }
2033
2034 /*< private >
2035 * gtk_constraint_solver_begin_edit:
2036 * @solver: a `GtkConstraintSolver`
2037 *
2038 * Begins the edit phase for a constraint system.
2039 *
2040 * Typically, you need to add new edit constraints for a variable to the
2041 * system, using gtk_constraint_solver_add_edit_variable(); then you
2042 * call this function and suggest values for the edit variables, using
2043 * gtk_constraint_solver_suggest_value(). After you suggested a value
2044 * for all the variables you need to edit, you will need to call
2045 * gtk_constraint_solver_resolve() to solve the system, and get the value
2046 * of the various variables that you're interested in.
2047 *
2048 * Once you completed the edit phase, call gtk_constraint_solver_end_edit()
2049 * to remove all the edit variables.
2050 */
2051 void
gtk_constraint_solver_begin_edit(GtkConstraintSolver * solver)2052 gtk_constraint_solver_begin_edit (GtkConstraintSolver *solver)
2053 {
2054 g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
2055
2056 if (g_hash_table_size (solver->edit_var_map) == 0)
2057 {
2058 g_critical ("Solver %p does not have editable variables.", solver);
2059 return;
2060 }
2061
2062 g_ptr_array_set_size (solver->infeasible_rows, 0);
2063 gtk_constraint_solver_reset_stay_constants (solver);
2064
2065 solver->in_edit_phase = TRUE;
2066 }
2067
2068 static void
edit_info_free(gpointer data)2069 edit_info_free (gpointer data)
2070 {
2071 g_free (data);
2072 }
2073
2074 /*< private >
2075 * gtk_constraint_solver_end_edit:
2076 * @solver: a `GtkConstraintSolver`
2077 *
2078 * Ends the edit phase for a constraint system, and clears
2079 * all the edit variables introduced.
2080 */
2081 void
gtk_constraint_solver_end_edit(GtkConstraintSolver * solver)2082 gtk_constraint_solver_end_edit (GtkConstraintSolver *solver)
2083 {
2084 solver->in_edit_phase = FALSE;
2085
2086 gtk_constraint_solver_resolve (solver);
2087
2088 g_hash_table_remove_all (solver->edit_var_map);
2089 }
2090
2091 void
gtk_constraint_solver_clear(GtkConstraintSolver * solver)2092 gtk_constraint_solver_clear (GtkConstraintSolver *solver)
2093 {
2094 g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
2095
2096 g_hash_table_remove_all (solver->constraints);
2097 g_hash_table_remove_all (solver->external_rows);
2098 g_hash_table_remove_all (solver->external_parametric_vars);
2099 g_hash_table_remove_all (solver->error_vars);
2100 g_hash_table_remove_all (solver->marker_vars);
2101 g_hash_table_remove_all (solver->edit_var_map);
2102 g_hash_table_remove_all (solver->stay_var_map);
2103
2104 g_ptr_array_set_size (solver->infeasible_rows, 0);
2105 g_ptr_array_set_size (solver->stay_error_vars, 0);
2106
2107 g_hash_table_remove_all (solver->rows);
2108 g_hash_table_remove_all (solver->columns);
2109
2110 /* The rows table owns the objective variable */
2111 solver->objective = gtk_constraint_variable_new_objective ("Z");
2112 g_hash_table_insert (solver->rows,
2113 solver->objective,
2114 gtk_constraint_expression_new (0.0));
2115
2116 solver->slack_counter = 0;
2117 solver->dummy_counter = 0;
2118 solver->artificial_counter = 0;
2119 solver->freeze_count = 0;
2120
2121 solver->needs_solving = FALSE;
2122 solver->auto_solve = TRUE;
2123 }
2124
2125 char *
gtk_constraint_solver_to_string(GtkConstraintSolver * solver)2126 gtk_constraint_solver_to_string (GtkConstraintSolver *solver)
2127 {
2128 GString *buf = g_string_new (NULL);
2129
2130 g_string_append (buf, "Tableau info:\n");
2131 g_string_append_printf (buf, "Rows: %d (= %d constraints)\n",
2132 g_hash_table_size (solver->rows),
2133 g_hash_table_size (solver->rows) - 1);
2134 g_string_append_printf (buf, "Columns: %d\n",
2135 g_hash_table_size (solver->columns));
2136 g_string_append_printf (buf, "Infeasible rows: %d\n",
2137 solver->infeasible_rows->len);
2138 g_string_append_printf (buf, "External basic variables: %d\n",
2139 g_hash_table_size (solver->external_rows));
2140 g_string_append_printf (buf, "External parametric variables: %d\n",
2141 g_hash_table_size (solver->external_parametric_vars));
2142
2143 g_string_append (buf, "Constraints:");
2144 if (g_hash_table_size (solver->constraints) == 0)
2145 g_string_append (buf, " <empty>\n");
2146 else
2147 {
2148 GHashTableIter iter;
2149 gpointer key_p;
2150
2151 g_string_append (buf, "\n");
2152
2153 g_hash_table_iter_init (&iter, solver->constraints);
2154 while (g_hash_table_iter_next (&iter, &key_p, NULL))
2155 {
2156 char *ref = gtk_constraint_ref_to_string (key_p);
2157
2158 g_string_append_printf (buf, " %s\n", ref);
2159
2160 g_free (ref);
2161 }
2162 }
2163
2164 g_string_append (buf, "Stay error vars:");
2165 if (solver->stay_error_vars->len == 0)
2166 g_string_append (buf, " <empty>\n");
2167 else
2168 {
2169 g_string_append (buf, "\n");
2170
2171 for (int i = 0; i < solver->stay_error_vars->len; i++)
2172 {
2173 const GtkConstraintVariablePair *pair = g_ptr_array_index (solver->stay_error_vars, i);
2174 char *first_s = gtk_constraint_variable_to_string (pair->first);
2175 char *second_s = gtk_constraint_variable_to_string (pair->second);
2176
2177 g_string_append_printf (buf, " (%s, %s)\n", first_s, second_s);
2178
2179 g_free (first_s);
2180 g_free (second_s);
2181 }
2182 }
2183
2184 g_string_append (buf, "Edit var map:");
2185 if (g_hash_table_size (solver->edit_var_map) == 0)
2186 g_string_append (buf, " <empty>\n");
2187 else
2188 {
2189 GHashTableIter iter;
2190 gpointer key_p, value_p;
2191
2192 g_string_append (buf, "\n");
2193
2194 g_hash_table_iter_init (&iter, solver->edit_var_map);
2195 while (g_hash_table_iter_next (&iter, &key_p, &value_p))
2196 {
2197 char *var = gtk_constraint_variable_to_string (key_p);
2198 const EditInfo *ei = value_p;
2199 char *c = gtk_constraint_ref_to_string (ei->constraint);
2200
2201 g_string_append_printf (buf, " %s => %s\n", var, c);
2202
2203 g_free (var);
2204 g_free (c);
2205 }
2206 }
2207
2208 return g_string_free (buf, FALSE);
2209 }
2210
2211 char *
gtk_constraint_solver_statistics(GtkConstraintSolver * solver)2212 gtk_constraint_solver_statistics (GtkConstraintSolver *solver)
2213 {
2214 GString *buf = g_string_new (NULL);
2215
2216 g_string_append_printf (buf, "Variables: %d\n", solver->var_counter);
2217 g_string_append_printf (buf, "Slack vars: %d\n", solver->slack_counter);
2218 g_string_append_printf (buf, "Artificial vars: %d\n", solver->artificial_counter);
2219 g_string_append_printf (buf, "Dummy vars: %d\n", solver->dummy_counter);
2220 g_string_append_printf (buf, "Stay vars: %d\n", g_hash_table_size (solver->stay_var_map));
2221 g_string_append_printf (buf, "Optimize count: %d\n", solver->optimize_count);
2222 g_string_append_printf (buf, "Rows: %d\n", g_hash_table_size (solver->rows));
2223 g_string_append_printf (buf, "Columns: %d\n", g_hash_table_size (solver->columns));
2224
2225 if (g_hash_table_size (solver->columns) > 0)
2226 {
2227 GHashTableIter iter;
2228 gpointer val;
2229 double sum = 0;
2230
2231 g_hash_table_iter_init (&iter, solver->columns);
2232 while (g_hash_table_iter_next (&iter, NULL, &val))
2233 {
2234 GtkConstraintVariableSet *set = val;
2235 sum += gtk_constraint_variable_set_size (set);
2236 }
2237 g_string_append_printf (buf, "Avg column size: %g\n", sum / g_hash_table_size (solver->columns));
2238 }
2239
2240 g_string_append_printf (buf, "Infeasible rows: %d\n", solver->infeasible_rows->len);
2241 g_string_append_printf (buf, "External basic variables: %d\n", g_hash_table_size (solver->external_rows));
2242 g_string_append_printf (buf, "External parametric variables: %d\n", g_hash_table_size (solver->external_parametric_vars));
2243
2244 return g_string_free (buf, FALSE);
2245 }
2246