?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update Spanish translation
[gnumeric.git] / plugins / mps / mps.c
blobb4fc3b295e3908e043e9acb2354d257e15abee16
1 /*
2 * Copyright (C) 2009 Morten Welinder (terra@gnome.org)
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see <https://www.gnu.org/licenses/>.
16 */
17
18 #include <gnumeric-config.h>
19 #include <goffice/goffice.h>
20 #include <glib/gi18n-lib.h>
21 #include <gsf/gsf-input-textline.h>
22
23 #include <gnm-plugin.h>
24 #include <gutils.h>
25 #include <workbook-view.h>
26 #include <workbook.h>
27 #include <sheet.h>
28 #include <value.h>
29 #include <mstyle.h>
30 #include <sheet-style.h>
31 #include <cell.h>
32 #include <ranges.h>
33 #include <expr.h>
34 #include <tools/gnm-solver.h>
35
36 #include <string.h>
37
38 GNM_PLUGIN_MODULE_HEADER;
39
40 typedef struct {
41 char *name;
42 GnmSolverConstraintType type;
43 GnmExpr const *expr;
44 gnm_float rhs;
45 gnm_float range;
46 } MpsRow;
47
48 typedef struct {
49 GOIOContext *io_context;
50
51 GsfInputTextline *input;
52 char *line;
53 GPtrArray *split;
54
55 GPtrArray *rows;
56 GHashTable *row_hash;
57
58 GHashTable *col_hash;
59
60 Workbook *wb;
61 Sheet *sheet;
62 GnmSolverParameters *param;
63 } MpsState;
64
65 /* ------------------------------------------------------------------------- */
66
67 /* Vertical */
68 enum { CONSTR_BASE_COL = 3 };
69 enum { CONSTR_BASE_ROW = 8 };
70
71 /* Vertical */
72 enum { VAR_BASE_COL = 0 };
73 enum { VAR_BASE_ROW = 8 };
74
75 /* Horizontal */
76 enum { OBJ_BASE_COL = 0 };
77 enum { OBJ_BASE_ROW = 4 };
78
79
80 static void
81 mps_set_cell (MpsState *state, int col, int row, const gchar *str)
82 {
83 GnmCell *cell = sheet_cell_fetch (state->sheet, col, row);
84 gnm_cell_set_value (cell, value_new_string (str));
85 }
86
87 static void
88 mps_set_expr (MpsState *state, int col, int row, GnmExpr const *expr)
89 {
90 GnmCell *cell = sheet_cell_fetch (state->sheet, col, row);
91 GnmExprTop const *texpr = gnm_expr_top_new (expr);
92 gnm_cell_set_expr (cell, texpr);
93 gnm_expr_top_unref (texpr);
94 }
95
96 static void
97 mps_set_cell_float (MpsState *state, int col, int row, const gnm_float f)
98 {
99 GnmCell *cell = sheet_cell_fetch (state->sheet, col, row);
100 gnm_cell_set_value (cell, value_new_float (f));
101 }
102
103 static void
104 mps_set_style (MpsState *state, int c1, int r1, int c2, int r2,
105 gboolean italic, gboolean bold, gboolean ulined)
106 {
107 GnmStyle *mstyle = gnm_style_new ();
108 GnmRange range;
109
110 range_init (&range, c1, r1, c2, r2);
111 gnm_style_set_font_italic (mstyle, italic);
112 gnm_style_set_font_bold (mstyle, bold);
113 gnm_style_set_font_uline (mstyle, ulined);
114 sheet_style_apply_range (state->sheet, &range, mstyle);
115 }
116
117 /* ------------------------------------------------------------------------- */
118
119 static gboolean
120 readline (MpsState *state)
121 {
122 do {
123 char *line = state->line =
124 gsf_input_textline_utf8_gets (state->input);
125
126 if (!line)
127 return FALSE;
128 if (line[0] == '*' || line[0] == 0)
129 continue;
130
131 return g_ascii_isspace (line[0]);
132 } while (1);
133 }
134
135 static gboolean
136 splitline (MpsState *state)
137 {
138 char *s;
139
140 if (!readline (state))
141 return FALSE;
142
143 g_ptr_array_set_size (state->split, 0);
144 s = state->line;
145 do {
146 while (g_ascii_isspace (*s))
147 s++;
148 if (!*s)
149 break;
150 g_ptr_array_add (state->split, s);
151 while (*s && !g_ascii_isspace (*s))
152 s++;
153 if (!*s)
154 break;
155 *s++ = 0;
156 } while (1);
157
158 return TRUE;
159 }
160
161 static void
162 ignore_section (MpsState *state)
163 {
164 while (readline (state))
165 ; /* Nothing */
166 }
167
168 /* ------------------------------------------------------------------------- */
169
170 static void
171 mps_mark_error (MpsState *state, const char *fmt, ...)
172 {
173 GOErrorInfo *error;
174 va_list args;
175
176 if (go_io_error_occurred (state->io_context))
177 return;
178
179 va_start (args, fmt);
180 error = go_error_info_new_vprintf (GO_ERROR, fmt, args);
181 va_end (args);
182
183 go_io_error_info_set (state->io_context, error);
184 }
185
186 static void
187 mps_parse_name (MpsState *state)
188 {
189 const char *s;
190
191 mps_set_cell (state, 0, 0, _("Program Name"));
192 mps_set_style (state, 0, 0, 0, 0, FALSE, TRUE, FALSE);
193
194 s = state->line + 4;
195 while (g_ascii_isspace (*s))
196 s++;
197 if (*s) {
198 mps_set_cell (state, 0, 1, s);
199 }
200
201 ignore_section (state);
202 }
203
204 static void
205 mps_parse_rows (MpsState *state)
206 {
207 gboolean seen_objfunc = FALSE;
208
209 g_ptr_array_add (state->rows, NULL);
210
211 while (splitline (state)) {
212 GPtrArray *split = state->split;
213 const char *type;
214 const char *name;
215 MpsRow *row;
216 gboolean is_objfunc = FALSE;
217
218 if (split->len < 2) {
219 mps_mark_error (state,
220 _("Invalid line in ROWS section"));
221 ignore_section (state);
222 return;
223 }
224 type = g_ptr_array_index (split, 0);
225 name = g_ptr_array_index (split, 1);
226
227 if (g_hash_table_lookup (state->row_hash, name)) {
228 mps_mark_error (state,
229 _("Duplicate rows name %s"),
230 name);
231 ignore_section (state);
232 return;
233 }
234
235 if (strcmp (type, "E") == 0) {
236 row = g_new0 (MpsRow, 1);
237 row->type = GNM_SOLVER_EQ;
238 } else if (strcmp (type, "L") == 0) {
239 row = g_new0 (MpsRow, 1);
240 row->type = GNM_SOLVER_LE;
241 } else if (strcmp (type, "G") == 0) {
242 row = g_new0 (MpsRow, 1);
243 row->type = GNM_SOLVER_GE;
244 } else if (strcmp (type, "N") == 0) {
245 if (seen_objfunc) {
246 mps_mark_error (state,
247 _("Duplicate objective row"));
248 ignore_section (state);
249 return;
250 }
251 row = g_new0 (MpsRow, 1);
252 is_objfunc = TRUE;
253 seen_objfunc = TRUE;
254 g_ptr_array_index (state->rows, 0) = row;
255 } else {
256 mps_mark_error (state,
257 _("Invalid row type %s"),
258 type);
259 ignore_section (state);
260 return;
261 }
262
263 row->name = g_strdup (name);
264 g_hash_table_insert (state->row_hash, row->name, row);
265 if (!is_objfunc)
266 g_ptr_array_add (state->rows, row);
267 }
268
269 if (!seen_objfunc) {
270 mps_mark_error (state,
271 _("Missing objective row"));
272 return;
273 }
274 }
275
276 static void
277 mps_parse_columns (MpsState *state)
278 {
279 gboolean integer = FALSE;
280 GnmCell *cell = NULL;
281
282 while (splitline (state)) {
283 GPtrArray *split = state->split;
284 const char *colname;
285 unsigned ui;
286
287 if (split->len == 3 &&
288 strcmp (g_ptr_array_index (split, 1), "'MARKER'") == 0) {
289 const char *marker = g_ptr_array_index (split, 2);
290 if (strcmp (marker, "'INTORG'") == 0)
291 integer = TRUE;
292 else if (strcmp (marker, "'INTEND'") == 0)
293 integer = FALSE;
294 else {
295 mps_mark_error (state,
296 _("Invalid marker"));
297 }
298 continue;
299 }
300
301 if (split->len % 2 == 0) {
302 colname = NULL;
303 /* Re-use cell */
304 } else {
305 colname = g_ptr_array_index (split, 0);
306 cell = g_hash_table_lookup (state->col_hash, colname);
307 }
308
309 if (!cell) {
310 int x = VAR_BASE_COL;
311 int y = VAR_BASE_ROW + 1 + g_hash_table_size (state->col_hash);
312 cell = sheet_cell_fetch (state->sheet, x + 1, y);
313 if (colname) {
314 g_hash_table_insert (state->col_hash,
315 g_strdup (colname),
316 cell);
317 mps_set_cell (state, x, y, colname);
318 }
319
320 if (integer) {
321 MpsRow *row = g_new0 (MpsRow, 1);
322 GnmCellRef cr;
323
324 gnm_cellref_init (&cr, NULL,
325 cell->pos.col, cell->pos.row,
326 FALSE);
327 row->name = g_strdup (colname);
328 row->type = GNM_SOLVER_INTEGER;
329 row->expr = gnm_expr_new_cellref (&cr);
330 g_ptr_array_add (state->rows, row);
331 }
332 }
333
334 for (ui = split->len % 2; ui < split->len; ui += 2) {
335 const char *rowname = g_ptr_array_index (split, ui);
336 const char *valtxt = g_ptr_array_index (split, ui + 1);
337 gnm_float val = gnm_strto (valtxt, NULL);
338 gboolean neg = (val < 0);
339 MpsRow *row = g_hash_table_lookup (state->row_hash,
340 rowname);
341 GnmCellRef cr;
342 GnmExpr const *expr;
343
344 if (!row) {
345 mps_mark_error (state,
346 _("Invalid row name, %s, in columns"),
347 rowname);
348 continue;
349 }
350 if (val == 0)
351 continue;
352
353 if (row->expr) {
354 val = gnm_abs (val);
355 }
356
357 gnm_cellref_init (&cr, NULL,
358 cell->pos.col, cell->pos.row,
359 FALSE);
360 expr = gnm_expr_new_cellref (&cr);
361 if (gnm_abs (val) != 1) {
362 expr = gnm_expr_new_binary
363 (gnm_expr_new_constant (value_new_float (val)),
364 GNM_EXPR_OP_MULT,
365 expr);
366 } else if (neg && row->expr == NULL)
367 expr = gnm_expr_new_unary
368 (GNM_EXPR_OP_UNARY_NEG,
369 expr);
370
371 if (row->expr) {
372 expr = gnm_expr_new_binary
373 (row->expr,
374 neg ? GNM_EXPR_OP_SUB : GNM_EXPR_OP_ADD,
375 expr);
376 }
377
378 row->expr = expr;
379 }
380 }
381 }
382
383 static void
384 mps_parse_bounds (MpsState *state)
385 {
386 while (splitline (state)) {
387 GPtrArray *split = state->split;
388 const char *bt = split->len
389 ? g_ptr_array_index (split, 0)
390 : "?";
391 GnmSolverConstraintType type;
392 gboolean integer = FALSE;
393 unsigned ui;
394
395 if (strcmp (bt, "UP") == 0 || strcmp (bt, "UI") == 0) {
396 type = GNM_SOLVER_LE;
397 integer = (bt[1] == 'I');
398 } else if (strcmp (bt, "LO") == 0 ||
399 strcmp (bt, "LI") == 0) {
400 type = GNM_SOLVER_GE;
401 integer = (bt[1] == 'I');
402 } else if (strcmp (bt, "FX") == 0)
403 type = GNM_SOLVER_EQ;
404 else if (strcmp (bt, "FR") == 0 ||
405 strcmp (bt, "PL") == 0 ||
406 strcmp (bt, "MI") == 0)
407 continue;
408 else if (strcmp (bt, "BV") == 0) {
409 type = GNM_SOLVER_BOOLEAN;
410 integer = TRUE;
411 } else {
412 mps_mark_error (state,
413 _("Invalid bounds type %s"),
414 bt);
415 continue;
416 }
417
418 for (ui = 2 - split->len % 2; ui < split->len; ui += 2) {
419 const char *colname = g_ptr_array_index (split, ui);
420 MpsRow *row;
421 GnmCell *cell = g_hash_table_lookup (state->col_hash,
422 colname);
423 const char *valtxt = g_ptr_array_index (split, ui + 1);
424 gnm_float val = gnm_strto (valtxt, NULL);
425 GnmCellRef cr;
426
427 if (!cell) {
428 mps_mark_error (state,
429 _("Invalid column name, %s, in bounds"),
430 colname);
431 continue;
432 }
433
434 gnm_cellref_init (&cr, NULL,
435 cell->pos.col, cell->pos.row,
436 FALSE);
437
438 row = g_new0 (MpsRow, 1);
439 row->name = g_strdup (colname);
440 row->type = type;
441 row->rhs = val;
442 row->expr = gnm_expr_new_cellref (&cr);
443 g_ptr_array_add (state->rows, row);
444
445 if (integer) {
446 row = g_new0 (MpsRow, 1);
447 row->name = g_strdup (colname);
448 row->type = GNM_SOLVER_INTEGER;
449 row->expr = gnm_expr_new_cellref (&cr);
450 g_ptr_array_add (state->rows, row);
451 }
452 }
453 }
454 }
455
456 static void
457 mps_parse_rhs (MpsState *state, gboolean is_rhs)
458 {
459 while (splitline (state)) {
460 GPtrArray *split = state->split;
461 unsigned ui;
462
463 /* The name column is optional. */
464 for (ui = split->len % 2; ui < split->len; ui += 2) {
465 const char *rowname = g_ptr_array_index (split, ui);
466 const char *valtxt = g_ptr_array_index (split, ui + 1);
467 gnm_float val = gnm_strto (valtxt, NULL);
468 MpsRow *row = g_hash_table_lookup (state->row_hash,
469 rowname);
470
471 if (!row) {
472 mps_mark_error (state,
473 _("Invalid row name, %s, in rhs/ranges section"),
474 rowname);
475 continue;
476 }
477
478 if (is_rhs)
479 row->rhs += val;
480 else
481 row->range += val;
482 }
483 }
484 }
485
486 static void
487 mps_parse_file (MpsState *state)
488 {
489 gboolean done = FALSE;
490 readline (state);
491
492 while (!done) {
493 char *line = state->line;
494 char *section;
495 unsigned ui;
496
497 if (!line) {
498 /* Ignore missing end marker. */
499 break;
500 }
501
502 ui = 0;
503 while (g_ascii_isalnum (line[ui]))
504 ui++;
505 section = g_strndup (line, ui);
506
507 if (strcmp (section, "ENDATA") == 0)
508 done = TRUE;
509 else if (strcmp (section, "NAME") == 0)
510 mps_parse_name (state);
511 else if (strcmp (section, "ROWS") == 0)
512 mps_parse_rows (state);
513 else if (strcmp (section, "COLUMNS") == 0)
514 mps_parse_columns (state);
515 else if (strcmp (section, "BOUNDS") == 0)
516 mps_parse_bounds (state);
517 else if (strcmp (section, "RHS") == 0)
518 mps_parse_rhs (state, TRUE);
519 else if (strcmp (section, "RANGES") == 0)
520 mps_parse_rhs (state, FALSE);
521 else {
522 g_warning ("Invalid section %s\n", section);
523 ignore_section (state);
524 }
525 g_free (section);
526 }
527 }
528
529 /* ------------------------------------------------------------------------- */
530
531 static void
532 make_constraint (MpsState *state, int x, int y, MpsRow *row,
533 GnmSolverConstraintType type, gnm_float rhs)
534 {
535 GnmSolverParameters *param = state->param;
536 GnmSolverConstraint *c = gnm_solver_constraint_new (state->sheet);
537 GnmRange r;
538 const char * const type_str[] = {
539 "\xe2\x89\xa4" /* "<=" */,
540 "\xe2\x89\xa5" /* ">=" */,
541 "=", "Int", "Bool"
542 };
543
544 c->type = type;
545 if (gnm_solver_constraint_has_rhs (c)) {
546 range_init (&r, x + 1, y, x + 1, y);
547 gnm_solver_constraint_set_lhs
548 (c,
549 value_new_cellrange_r (NULL, &r));
550 range_init (&r, x + 3, y, x + 3, y);
551 gnm_solver_constraint_set_rhs
552 (c,
553 value_new_cellrange_r (NULL, &r));
554
555 mps_set_cell_float (state, x + 3, y, rhs);
556 } else {
557 /* Refer directly to the variable. */
558 gnm_solver_constraint_set_lhs
559 (c,
560 gnm_expr_get_range (row->expr));
561 }
562
563 if (row->name)
564 mps_set_cell (state, x, y, row->name);
565 if (row->expr) {
566 GnmCellRef cr;
567 mps_set_expr (state, x + 1, y, row->expr);
568 gnm_cellref_init (&cr, NULL, 0, -1, TRUE);
569 row->expr = gnm_expr_new_cellref (&cr);
570 } else
571 mps_set_cell_float (state, x + 1, y, 0);
572
573 mps_set_cell (state, x + 2, y, type_str[type]);
574
575 param->constraints = g_slist_append (param->constraints, c);
576 }
577
578
579
580 static void
581 mps_fill_sheet (MpsState *state)
582 {
583 unsigned ui;
584 GnmSolverParameters *param = state->param;
585 int x = CONSTR_BASE_COL;
586 int y = CONSTR_BASE_ROW;
587
588 /* ---------------------------------------- */
589
590 mps_set_cell (state, x, y, _("Constraint"));
591 mps_set_cell (state, x + 1, y, _("Value"));
592 mps_set_cell (state, x + 2, y, _("Type"));
593 mps_set_cell (state, x + 3, y, _("Limit"));
594 mps_set_style (state, x, y, x + 3, y, FALSE, TRUE, FALSE);
595
596 /* Zeroth row is objective function. */
597 for (ui = 1; ui < state->rows->len; ui++) {
598 MpsRow *row = g_ptr_array_index (state->rows, ui);
599
600 y++;
601
602 switch (row->type) {
603 case GNM_SOLVER_LE:
604 if (row->range != 0)
605 make_constraint (state, x, y++, row,
606 GNM_SOLVER_GE,
607 row->rhs - gnm_abs (row->range));
608 make_constraint (state, x, y, row, row->type, row->rhs);
609 break;
610 case GNM_SOLVER_GE:
611 make_constraint (state, x, y, row, row->type, row->rhs);
612 if (row->range != 0)
613 make_constraint (state, x, ++y, row,
614 GNM_SOLVER_LE,
615 row->rhs + gnm_abs (row->range));
616 break;
617 case GNM_SOLVER_EQ:
618 if (row->range == 0)
619 make_constraint (state, x, y, row,
620 row->type, row->rhs);
621 else if (row->range > 0) {
622 make_constraint (state, x, y, row,
623 GNM_SOLVER_GE, row->rhs);
624 make_constraint (state, x, y, row,
625 GNM_SOLVER_LE,
626 row->rhs + gnm_abs (row->range));
627 } else {
628 make_constraint (state, x, y, row,
629 GNM_SOLVER_GE,
630 row->rhs - gnm_abs (row->range));
631 make_constraint (state, x, y, row,
632 GNM_SOLVER_LE, row->rhs);
633 }
634 break;
635 case GNM_SOLVER_INTEGER:
636 case GNM_SOLVER_BOOLEAN:
637 make_constraint (state, x, y, row, row->type, 0);
638 break;
639 default:
640 g_assert_not_reached ();
641 }
642 }
643
644 /* ---------------------------------------- */
645
646 {
647 GnmRange r;
648 GnmValue *vinput;
649
650 mps_set_cell (state, VAR_BASE_COL, VAR_BASE_ROW,
651 _("Variable"));
652 mps_set_cell (state, VAR_BASE_COL + 1, VAR_BASE_ROW,
653 _("Value"));
654 mps_set_style (state, VAR_BASE_COL, VAR_BASE_ROW,
655 VAR_BASE_COL + 1, VAR_BASE_ROW,
656 FALSE, TRUE, FALSE);
657
658 range_init (&r,
659 VAR_BASE_COL + 1, VAR_BASE_ROW + 1,
660 VAR_BASE_COL + 1, VAR_BASE_ROW + g_hash_table_size (state->col_hash));
661 vinput = value_new_cellrange_r (NULL, &r);
662 gnm_solver_param_set_input (param, vinput);
663 }
664
665 /* ---------------------------------------- */
666
667 if (state->rows->len > 0) {
668 int x = OBJ_BASE_COL;
669 int y = OBJ_BASE_ROW;
670 MpsRow *row = g_ptr_array_index (state->rows, 0);
671 GnmCellRef cr;
672
673 mps_set_cell (state, x, y, _("Objective function"));
674 mps_set_style (state, x, y, x, y, FALSE, TRUE, FALSE);
675
676 if (row->expr) {
677 mps_set_expr (state, x + 1, y, row->expr);
678 row->expr = NULL;
679 } else
680 mps_set_cell_float (state, x + 1, y, 0);
681
682 param->problem_type = GNM_SOLVER_MINIMIZE;
683
684 gnm_cellref_init (&cr, NULL, x + 1, y, FALSE);
685 gnm_solver_param_set_target (param, &cr);
686 }
687 }
688
689 /* ------------------------------------------------------------------------- */
690
691 void
692 mps_file_open (GOFileOpener const *fo, GOIOContext *io_context,
693 WorkbookView *wbv, GsfInput *input);
694
695 void
696 mps_file_open (GOFileOpener const *fo, GOIOContext *io_context,
697 WorkbookView *wbv, GsfInput *input)
698 {
699 MpsState state;
700 GnmLocale *locale;
701 unsigned ui;
702
703 memset (&state, 0, sizeof (state));
704 state.io_context = io_context;
705 state.wb = wb_view_get_workbook (wbv);
706 state.input = GSF_INPUT_TEXTLINE (gsf_input_textline_new (input));
707 state.sheet = workbook_sheet_add (state.wb, -1,
708 GNM_DEFAULT_COLS, GNM_DEFAULT_ROWS);
709 state.param = state.sheet->solver_parameters;
710 state.split = g_ptr_array_new ();
711 state.rows = g_ptr_array_new ();
712 state.row_hash = g_hash_table_new (g_str_hash, g_str_equal);
713 state.col_hash = g_hash_table_new_full (g_str_hash, g_str_equal,
714 g_free, NULL);
715
716 locale = gnm_push_C_locale ();
717 mps_parse_file (&state);
718 gnm_pop_C_locale (locale);
719
720 if (go_io_error_occurred (io_context)) {
721 go_io_error_push (io_context, go_error_info_new_str
722 (_("Error while reading MPS file.")));
723 } else {
724 mps_fill_sheet (&state);
725 workbook_recalc_all (state.wb);
726 }
727
728 g_hash_table_destroy (state.row_hash);
729 for (ui = 0; ui < state.rows->len; ui++) {
730 MpsRow *row = g_ptr_array_index (state.rows, ui);
731 if (!row)
732 continue;
733 g_free (row->name);
734 if (row->expr)
735 gnm_expr_free (row->expr);
736 g_free (row);
737 }
738 g_ptr_array_free (state.rows, TRUE);
739
740 g_hash_table_destroy (state.col_hash);
741
742 g_ptr_array_free (state.split, TRUE);
743 g_object_unref (state.input);
744 }
gnumeric mirror