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 | |