src/criteria.c

   1 #include "criteria.h"
   2
   3 typedef enum { CRIT_NULL, CRIT_FLOAT, CRIT_WRONGTYPE, CRIT_STRING } CritType;
   4
   5 static CritType
   6 criteria_inspect_values (GnmValue const *x, gnm_float *xr, gnm_float *yr,
   7                          GnmCriteria *crit, gboolean coerce_to_float)
   8 {
   9         GnmValue const *y = crit->x;
  10
  11         if (x == NULL || y == NULL)
  12                 return CRIT_NULL;
  13
  14         switch (y->v_any.type) {
  15         case VALUE_BOOLEAN:
  16                 /* If we're searching for a bool -- even one that is
  17                    from a string search value -- we match only bools.  */
  18                 if (!VALUE_IS_BOOLEAN (x))
  19                         return CRIT_WRONGTYPE;
  20                 *xr = value_get_as_float (x);
  21                 *yr = value_get_as_float (y);
  22                 return CRIT_FLOAT;
  23
  24         case VALUE_EMPTY:
  25                 return CRIT_WRONGTYPE;
  26
  27         case VALUE_STRING:
  28                 if (!VALUE_IS_STRING (x))
  29                         return CRIT_WRONGTYPE;
  30                 return CRIT_STRING;
  31
  32         default:
  33                 g_warning ("This should not happen.  Please report.");
  34                 return CRIT_WRONGTYPE;
  35
  36         case VALUE_FLOAT: {
  37                 GnmValue *vx;
  38                 *yr = value_get_as_float (y);
  39
  40                 if (VALUE_IS_BOOLEAN (x) || VALUE_IS_ERROR (x))
  41                         return CRIT_WRONGTYPE;
  42                 else if (VALUE_IS_FLOAT (x)) {
  43                         *xr = value_get_as_float (x);
  44                         return CRIT_FLOAT;
  45                 }
  46
  47                 if (!coerce_to_float)
  48                         return CRIT_WRONGTYPE;
  49
  50                 vx = format_match (value_peek_string (x), NULL, crit->date_conv);
  51                 if (VALUE_IS_EMPTY (vx) ||
  52                     VALUE_IS_BOOLEAN (y) != VALUE_IS_BOOLEAN (vx)) {
  53                         value_release (vx);
  54                         return CRIT_WRONGTYPE;
  55                 }
  56
  57                 *xr = value_get_as_float (vx);
  58                 value_release (vx);
  59                 return CRIT_FLOAT;
  60         }
  61         }
  62 }
  63
  64
  65 static gboolean
  66 criteria_test_equal (GnmValue const *x, GnmCriteria *crit)
  67 {
  68         gnm_float xf, yf;
  69         GnmValue const *y = crit->x;
  70
  71         switch (criteria_inspect_values (x, &xf, &yf, crit, TRUE)) {
  72         default:
  73                 g_assert_not_reached ();
  74         case CRIT_NULL:
  75         case CRIT_WRONGTYPE:
  76                 return FALSE;
  77         case CRIT_FLOAT:
  78                 return xf == yf;
  79         case CRIT_STRING:
  80                 /* FIXME: _ascii_??? */
  81                 return g_ascii_strcasecmp (value_peek_string (x),
  82                                            value_peek_string (y)) == 0;
  83         }
  84 }
  85
  86 static gboolean
  87 criteria_test_unequal (GnmValue const *x, GnmCriteria *crit)
  88 {
  89         gnm_float xf, yf;
  90
  91         switch (criteria_inspect_values (x, &xf, &yf, crit, FALSE)) {
  92         default:
  93                 g_assert_not_reached ();
  94         case CRIT_NULL:
  95         case CRIT_WRONGTYPE:
  96                 return TRUE;
  97         case CRIT_FLOAT:
  98                 return xf != yf;
  99         case CRIT_STRING:
 100                 /* FIXME: _ascii_??? */
 101                 return g_ascii_strcasecmp (value_peek_string (x),
 102                                            value_peek_string (crit->x)) != 0;
 103         }
 104 }
 105
 106 static gboolean
 107 criteria_test_less (GnmValue const *x, GnmCriteria *crit)
 108 {
 109         gnm_float xf, yf;
 110         GnmValue const *y = crit->x;
 111
 112         switch (criteria_inspect_values (x, &xf, &yf, crit, FALSE)) {
 113         default:
 114                 g_assert_not_reached ();
 115         case CRIT_NULL:
 116         case CRIT_WRONGTYPE:
 117                 return FALSE;
 118         case CRIT_STRING:
 119                 return go_utf8_collate_casefold (value_peek_string (x),
 120                                                  value_peek_string (y)) < 0;
 121         case CRIT_FLOAT:
 122                 return xf < yf;
 123         }
 124 }
 125
 126 static gboolean
 127 criteria_test_greater (GnmValue const *x, GnmCriteria *crit)
 128 {
 129         gnm_float xf, yf;
 130         GnmValue const *y = crit->x;
 131
 132         switch (criteria_inspect_values (x, &xf, &yf, crit, FALSE)) {
 133         default:
 134                 g_assert_not_reached ();
 135         case CRIT_NULL:
 136         case CRIT_WRONGTYPE:
 137                 return FALSE;
 138         case CRIT_STRING:
 139                 return go_utf8_collate_casefold (value_peek_string (x),
 140                                                  value_peek_string (y)) > 0;
 141         case CRIT_FLOAT:
 142                 return xf > yf;
 143         }
 144 }
 145
 146 static gboolean
 147 criteria_test_less_or_equal (GnmValue const *x, GnmCriteria *crit)
 148 {
 149         gnm_float xf, yf;
 150         GnmValue const *y = crit->x;
 151
 152         switch (criteria_inspect_values (x, &xf, &yf, crit, FALSE)) {
 153         default:
 154                 g_assert_not_reached ();
 155         case CRIT_NULL:
 156         case CRIT_WRONGTYPE:
 157                 return FALSE;
 158         case CRIT_STRING:
 159                 return go_utf8_collate_casefold (value_peek_string (x),
 160                                                  value_peek_string (y)) <= 0;
 161         case CRIT_FLOAT:
 162                 return xf <= yf;
 163         }
 164 }
 165
 166 static gboolean
 167 criteria_test_greater_or_equal (GnmValue const *x, GnmCriteria *crit)
 168 {
 169         gnm_float xf, yf;
 170         GnmValue const *y = crit->x;
 171
 172         switch (criteria_inspect_values (x, &xf, &yf, crit, FALSE)) {
 173         default:
 174                 g_assert_not_reached ();
 175         case CRIT_NULL:
 176         case CRIT_WRONGTYPE:
 177                 return FALSE;
 178         case CRIT_STRING:
 179                 return go_utf8_collate_casefold (value_peek_string (x),
 180                                                  value_peek_string (y)) >= 0;
 181         case CRIT_FLOAT:
 182                 return xf >= yf;
 183         }
 184 }
 185
 186 static gboolean
 187 criteria_test_match (GnmValue const *x, GnmCriteria *crit)
 188 {
 189         if (!crit->has_rx)
 190                 return FALSE;
 191
 192         // Only strings are matched
 193         if (!VALUE_IS_STRING (x))
 194                 return FALSE;
 195
 196         return go_regexec (&crit->rx, value_peek_string (x), 0, NULL, 0) ==
 197                 GO_REG_OK;
 198 }
 199
 200 static gboolean
 201 criteria_test_empty (GnmValue const *x, GnmCriteria *crit)
 202 {
 203         return VALUE_IS_EMPTY (x);
 204 }
 205
 206 static gboolean
 207 criteria_test_nonempty (GnmValue const *x, GnmCriteria *crit)
 208 {
 209         return !VALUE_IS_EMPTY (x);
 210 }
 211
 212 /*
 213  * Finds a column index of a field.
 214  */
 215 int
 216 find_column_of_field (GnmEvalPos const *ep,
 217                       GnmValue const *database, GnmValue const *field)
 218 {
 219         Sheet *sheet;
 220         GnmCell  *cell;
 221         gchar *field_name;
 222         int   begin_col, end_col, row, n, column;
 223         int   offset;
 224
 225         // I'm not certain we should demand this, but the code clearly wants
 226         // it.
 227         if (!VALUE_IS_CELLRANGE (database))
 228                 return -1;
 229
 230         offset = database->v_range.cell.a.col;
 231
 232         if (VALUE_IS_FLOAT (field))
 233                 return value_get_as_int (field) + offset - 1;
 234
 235         if (!VALUE_IS_STRING (field))
 236                 return -1;
 237
 238         sheet = eval_sheet (database->v_range.cell.a.sheet, ep->sheet);
 239         field_name = value_get_as_string (field);
 240         column = -1;
 241
 242         /* find the column that is labeled after `field_name' */
 243         begin_col = database->v_range.cell.a.col;
 244         end_col = database->v_range.cell.b.col;
 245         row = database->v_range.cell.a.row;
 246
 247         for (n = begin_col; n <= end_col; n++) {
 248                 char const *txt;
 249                 gboolean match;
 250
 251                 cell = sheet_cell_get (sheet, n, row);
 252                 if (cell == NULL)
 253                         continue;
 254                 gnm_cell_eval (cell);
 255
 256                 txt = cell->value
 257                         ? value_peek_string (cell->value)
 258                         : "";
 259                 match = (g_ascii_strcasecmp (field_name, txt) == 0);
 260                 if (match) {
 261                         column = n;
 262                         break;
 263                 }
 264         }
 265
 266         g_free (field_name);
 267         return column;
 268 }
 269
 270 void
 271 free_criteria (GnmCriteria *criteria)
 272 {
 273         if (!criteria || criteria->ref_count-- > 1)
 274                 return;
 275         value_release (criteria->x);
 276         if (criteria->has_rx)
 277                 go_regfree (&criteria->rx);
 278         g_free (criteria);
 279 }
 280
 281 static GnmCriteria *
 282 gnm_criteria_ref (GnmCriteria *criteria)
 283 {
 284         criteria->ref_count++;
 285         return criteria;
 286 }
 287
 288 GType
 289 gnm_criteria_get_type (void)
 290 {
 291         static GType t = 0;
 292
 293         if (t == 0) {
 294                 t = g_boxed_type_register_static ("GnmCriteria",
 295                          (GBoxedCopyFunc)gnm_criteria_ref,
 296                          (GBoxedFreeFunc)free_criteria);
 297         }
 298         return t;
 299 }
 300
 301 /**
 302  * free_criterias:
 303  * @criterias: (element-type GnmCriteria) (transfer full): the criteria to be
 304  * freed.
 305  * Frees the allocated memory.
 306  */
 307 void
 308 free_criterias (GSList *criterias)
 309 {
 310         GSList *list = criterias;
 311
 312         while (criterias != NULL) {
 313                 GnmDBCriteria *criteria = criterias->data;
 314                 g_slist_free_full (criteria->conditions,
 315                                       (GFreeFunc)free_criteria);
 316                 g_free (criteria);
 317                 criterias = criterias->next;
 318         }
 319         g_slist_free (list);
 320 }
 321
 322 /**
 323  * parse_criteria:
 324  * @crit_val: #GnmValue
 325  * @date_conv: #GODateConventions
 326  *
 327  * Returns: (transfer full): GnmCriteria which caller must free.
 328  *
 329  * ">=value"
 330  * "<=value"
 331  * "<>value"
 332  * "<value"
 333  * ">value"
 334  * "=value"
 335  * "pattern"
 336  **/
 337 GnmCriteria *
 338 parse_criteria (GnmValue const *crit_val, GODateConventions const *date_conv,
 339                 gboolean anchor_end)
 340 {
 341         int len;
 342         char const *criteria;
 343         GnmCriteria *res = g_new0 (GnmCriteria, 1);
 344         GnmValue *empty;
 345
 346         res->iter_flags = CELL_ITER_IGNORE_BLANK;
 347         res->date_conv = date_conv;
 348
 349         if (VALUE_IS_NUMBER (crit_val)) {
 350                 res->fun = criteria_test_equal;
 351                 res->x = value_dup (crit_val);
 352                 return res;
 353         }
 354
 355         criteria = value_peek_string (crit_val);
 356         if (strncmp (criteria, "<=", 2) == 0) {
 357                 res->fun = criteria_test_less_or_equal;
 358                 len = 2;
 359         } else if (strncmp (criteria, ">=", 2) == 0) {
 360                 res->fun = criteria_test_greater_or_equal;
 361                 len = 2;
 362         } else if (strncmp (criteria, "<>", 2) == 0) {
 363                 /* "<>" by itself is special: */
 364                 res->fun = (criteria[2] == 0) ? criteria_test_nonempty : criteria_test_unequal;
 365                 len = 2;
 366         } else if (*criteria == '<') {
 367                 res->fun = criteria_test_less;
 368                 len = 1;
 369         } else if (*criteria == '=') {
 370                 /* "=" by itself is special: */
 371                 res->fun = (criteria[1] == 0) ? criteria_test_empty : criteria_test_equal;
 372                 len = 1;
 373         } else if (*criteria == '>') {
 374                 res->fun = criteria_test_greater;
 375                 len = 1;
 376         } else {
 377                 res->fun = criteria_test_match;
 378                 res->has_rx = (gnm_regcomp_XL (&res->rx, criteria, GO_REG_ICASE, TRUE, anchor_end) == GO_REG_OK);
 379                 len = 0;
 380         }
 381
 382         res->x = format_match_number (criteria + len, NULL, date_conv);
 383         if (res->x == NULL)
 384                 res->x = value_new_string (criteria + len);
 385         else if (len == 0 && VALUE_IS_NUMBER (res->x))
 386                 res->fun = criteria_test_equal;
 387
 388         empty = value_new_empty ();
 389         if (res->fun (empty, res))
 390                 res->iter_flags &= ~CELL_ITER_IGNORE_BLANK;
 391         value_release (empty);
 392         res->ref_count = 1;
 393
 394         return res;
 395 }
 396
 397
 398 static GSList *
 399 parse_criteria_range (Sheet *sheet, int b_col, int b_row, int e_col, int e_row,
 400                       int   *field_ind, gboolean anchor_end)
 401 {
 402         GSList *criterias = NULL;
 403         GODateConventions const *date_conv =
 404                 workbook_date_conv (sheet->workbook);
 405         int i, j;
 406
 407         for (i = b_row; i <= e_row; i++) {
 408                 GnmDBCriteria *new_criteria = g_new (GnmDBCriteria, 1);
 409                 GSList *conditions = NULL;
 410
 411                 for (j = b_col; j <= e_col; j++) {
 412                         GnmCriteria *cond;
 413                         GnmCell *cell = sheet_cell_get (sheet, j, i);
 414                         if (cell != NULL)
 415                                 gnm_cell_eval (cell);
 416                         if (gnm_cell_is_empty (cell))
 417                                 continue;
 418
 419                         cond = parse_criteria (cell->value, date_conv,
 420                                                anchor_end);
 421                         cond->column = (field_ind != NULL)
 422                                 ? field_ind[j - b_col]
 423                                 : j - b_col;
 424                         conditions = g_slist_prepend (conditions, cond);
 425                 }
 426
 427                 new_criteria->conditions = g_slist_reverse (conditions);
 428                 criterias = g_slist_prepend (criterias, new_criteria);
 429         }
 430
 431         return g_slist_reverse (criterias);
 432 }
 433
 434 /**
 435  * parse_database_criteria:
 436  * @ep: #GnmEvalPos
 437  * @database: #GnmValue
 438  * @criteria: #GnmValue
 439  *
 440  * Parses the criteria cell range.
 441  * Returns: (element-type GnmDBCriteria) (transfer full):
 442  */
 443 GSList *
 444 parse_database_criteria (GnmEvalPos const *ep, GnmValue const *database, GnmValue const *criteria)
 445 {
 446         Sheet   *sheet;
 447         GnmCell *cell;
 448         int   i;
 449         int   b_col, b_row, e_col, e_row;
 450         int   *field_ind;
 451         GSList *res;
 452
 453         g_return_val_if_fail (VALUE_IS_CELLRANGE (criteria), NULL);
 454
 455         sheet = eval_sheet (criteria->v_range.cell.a.sheet, ep->sheet);
 456         b_col = criteria->v_range.cell.a.col;
 457         b_row = criteria->v_range.cell.a.row;
 458         e_col = criteria->v_range.cell.b.col;
 459         e_row = criteria->v_range.cell.b.row;
 460
 461         if (e_col < b_col) {
 462                 int tmp = b_col;
 463                 b_col = e_col;
 464                 e_col = tmp;
 465         }
 466
 467         /* Find the index numbers for the columns of criterias */
 468         field_ind = g_new (int, e_col - b_col + 1);
 469         for (i = b_col; i <= e_col; i++) {
 470                 cell = sheet_cell_get (sheet, i, b_row);
 471                 if (cell == NULL)
 472                         continue;
 473                 gnm_cell_eval (cell);
 474                 if (gnm_cell_is_empty (cell))
 475                         continue;
 476                 field_ind[i - b_col] =
 477                         find_column_of_field (ep, database, cell->value);
 478                 if (field_ind[i - b_col] == -1) {
 479                         g_free (field_ind);
 480                         return NULL;
 481                 }
 482         }
 483
 484         res = parse_criteria_range (sheet, b_col, b_row + 1,
 485                                     e_col, e_row, field_ind,
 486                                     FALSE);
 487         g_free (field_ind);
 488         return res;
 489 }
 490
 491 /**
 492  * find_rows_that_match:
 493  * @sheet: #Sheet
 494  * @first_col: first column.
 495  * @first_row: first row.
 496  * @last_col: last column.
 497  * @last_row: laset row.
 498  * @criterias: (element-type GnmDBCriteria): the criteria to use.
 499  * @unique_only:
 500  *
 501  * Finds the rows from the given database that match the criteria.
 502  * Returns: (element-type int) (transfer full): the list of matching rows.
 503  **/
 504 GSList *
 505 find_rows_that_match (Sheet *sheet, int first_col, int first_row,
 506                       int last_col, int last_row,
 507                       GSList *criterias, gboolean unique_only)
 508 {
 509         GSList       *rows = NULL;
 510         GSList const *crit_ptr, *cond_ptr;
 511         int        row;
 512         gboolean   add_flag;
 513         char const *t1, *t2;
 514         GnmCell   *test_cell;
 515         GnmValue const *empty = value_new_empty ();
 516
 517         for (row = first_row; row <= last_row; row++) {
 518                 add_flag = TRUE;
 519                 for (crit_ptr = criterias; crit_ptr; crit_ptr = crit_ptr->next) {
 520                         GnmDBCriteria const *crit = crit_ptr->data;
 521                         add_flag = TRUE;
 522                         for (cond_ptr = crit->conditions;
 523                              cond_ptr != NULL ; cond_ptr = cond_ptr->next) {
 524                                 GnmCriteria *cond = cond_ptr->data;
 525                                 test_cell = sheet_cell_get (sheet, cond->column, row);
 526                                 if (test_cell != NULL)
 527                                         gnm_cell_eval (test_cell);
 528                                 if (!cond->fun (test_cell ? test_cell->value : empty, cond)) {
 529                                         add_flag = FALSE;
 530                                         break;
 531                                 }
 532                         }
 533
 534                         if (add_flag)
 535                                 break;
 536                 }
 537                 if (add_flag) {
 538                         gint *p;
 539
 540                         if (unique_only) {
 541                                 GSList *c;
 542                                 GnmCell   *cell;
 543                                 gint    i, trow;
 544
 545                                 for (c = rows; c != NULL; c = c->next) {
 546                                         trow = *((gint *) c->data);
 547                                         for (i = first_col; i <= last_col; i++) {
 548                                                 test_cell = sheet_cell_get (sheet, i, trow);
 549                                                 cell = sheet_cell_get (sheet, i, row);
 550
 551                                                 /* FIXME: this is probably not right, but crashing is more wrong.  */
 552                                                 if (test_cell == NULL || cell == NULL)
 553                                                         continue;
 554
 555                                                 t1 = cell->value
 556                                                         ? value_peek_string (cell->value)
 557                                                         : "";
 558                                                 t2 = test_cell->value
 559                                                         ? value_peek_string (test_cell->value)
 560                                                         : "";
 561                                                 if (strcmp (t1, t2) != 0)
 562                                                         goto row_ok;
 563                                         }
 564                                         goto filter_row;
 565 row_ok:
 566                                         ;
 567                                 }
 568                         }
 569                         p = g_new (gint, 1);
 570                         *p = row;
 571                         rows = g_slist_prepend (rows, (gpointer) p);
 572 filter_row:
 573                         ;
 574                 }
 575         }
 576
 577         return g_slist_reverse (rows);
 578 }
 579
 580 /****************************************************************************/
 581
 582 /**
 583  * gnm_ifs_func:
 584  * @data: (element-type GnmValue):
 585  * @crits: (element-type GnmCriteria): criteria
 586  * @vals:
 587  * @fun: (scope call): function to evaluate on filtered data
 588  * @err: error value in case @fun fails.
 589  * @ep: evaluation position
 590  * @flags:
 591  */
 592
 593 GnmValue *
 594 gnm_ifs_func (GPtrArray *data, GPtrArray *crits, GnmValue const *vals,
 595               float_range_function_t fun, GnmStdError err,
 596               GnmEvalPos const *ep, CollectFlags flags)
 597 {
 598         int sx, sy, x, y;
 599         unsigned ui, N = 0, nalloc = 0;
 600         gnm_float *xs = NULL;
 601         GnmValue *res = NULL;
 602         gnm_float fres;
 603
 604         g_return_val_if_fail (data->len == crits->len, NULL);
 605
 606         if (flags & ~(COLLECT_IGNORE_STRINGS |
 607                       COLLECT_IGNORE_BOOLS |
 608                       COLLECT_IGNORE_BLANKS |
 609                       COLLECT_IGNORE_ERRORS)) {
 610                 g_warning ("unsupported flags in gnm_ifs_func %x", flags);
 611         }
 612
 613         sx = value_area_get_width (vals, ep);
 614         sy = value_area_get_height (vals, ep);
 615         for (ui = 0; ui < data->len; ui++) {
 616                 GnmValue const *datai = g_ptr_array_index (data, ui);
 617                 if (value_area_get_width (datai, ep) != sx ||
 618                     value_area_get_height (datai, ep) != sy)
 619                         return value_new_error_VALUE (ep);
 620         }
 621
 622         for (y = 0; y < sy; y++) {
 623                 for (x = 0; x < sx; x++) {
 624                         GnmValue const *v;
 625                         gboolean match = TRUE;
 626
 627                         for (ui = 0; match && ui < crits->len; ui++) {
 628                                 GnmCriteria *crit = g_ptr_array_index (crits, ui);
 629                                 GnmValue const *datai = g_ptr_array_index (data, ui);
 630                                 v = value_area_get_x_y (datai, x, y, ep);
 631
 632                                 match = crit->fun (v, crit);
 633                         }
 634                         if (!match)
 635                                 continue;
 636
 637                         // Match.  Maybe collect the data point.
 638
 639                         v = value_area_get_x_y (vals, x, y, ep);
 640                         if ((flags & COLLECT_IGNORE_STRINGS) && VALUE_IS_STRING (v))
 641                                 continue;
 642                         if ((flags & COLLECT_IGNORE_BOOLS) && VALUE_IS_BOOLEAN (v))
 643                                 continue;
 644                         if ((flags & COLLECT_IGNORE_BLANKS) && VALUE_IS_EMPTY (v))
 645                                 continue;
 646                         if ((flags & COLLECT_IGNORE_ERRORS) && VALUE_IS_ERROR (v))
 647                                 continue;
 648
 649                         if (VALUE_IS_ERROR (v)) {
 650                                 res = value_dup (v);
 651                                 goto out;
 652                         }
 653
 654                         if (N >= nalloc) {
 655                                 nalloc = (2 * nalloc) + 100;
 656                                 xs = g_renew (gnm_float, xs, nalloc);
 657                         }
 658                         xs[N++] = value_get_as_float (v);
 659                 }
 660         }
 661
 662         if (fun (xs, N, &fres)) {
 663                 res = value_new_error_std (ep, err);
 664         } else
 665                 res = value_new_float (fres);
 666
 667 out:
 668         g_free (xs);
 669         return res;
 670 }
 671
 672 /****************************************************************************/