pintos-os.org Git - pspp/blob - src/language/stats/autorecode.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 1997-9, 2000, 2009, 2010, 2012, 2013, 2014 Free Software Foundation, Inc.
   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 3 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 <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18
  19 #include <float.h>
  20 #include <stdlib.h>
  21
  22 #include "data/case.h"
  23 #include "data/casereader.h"
  24 #include "data/dataset.h"
  25 #include "data/dictionary.h"
  26 #include "data/transformations.h"
  27 #include "data/variable.h"
  28 #include "language/command.h"
  29 #include "language/lexer/lexer.h"
  30 #include "language/lexer/variable-parser.h"
  31 #include "libpspp/array.h"
  32 #include "libpspp/compiler.h"
  33 #include "libpspp/hash-functions.h"
  34 #include "libpspp/hmap.h"
  35 #include "libpspp/i18n.h"
  36 #include "libpspp/message.h"
  37 #include "libpspp/pool.h"
  38 #include "libpspp/str.h"
  39
  40 #include "gl/xalloc.h"
  41 #include "gl/c-xvasprintf.h"
  42 #include "gl/mbiter.h"
  43 #include "gl/size_max.h"
  44
  45 #include "gettext.h"
  46 #define _(msgid) gettext (msgid)
  47
  48 /* FIXME: Implement PRINT subcommand. */
  49
  50 /* Explains how to recode one value. */
  51 struct arc_item
  52   {
  53     struct hmap_node hmap_node; /* Element in "struct arc_spec" hash table. */
  54     union value from;           /* Original value. */
  55     int width;                  /* Width of the original value */
  56     bool missing;               /* Is 'from' missing in its source varible? */
  57
  58     double to;                  /* Recoded value. */
  59   };
  60
  61 /* Explains how to recode an AUTORECODE variable. */
  62 struct arc_spec
  63   {
  64     int width;                  /* Variable width. */
  65     int src_idx;                /* Case index of source variable. */
  66     struct variable *dst;       /* Target variable. */
  67     struct missing_values mv;   /* Missing values of source variable. */
  68     struct rec_items *items;
  69   };
  70
  71 /* Descending or ascending sort order. */
  72 enum arc_direction
  73   {
  74     ASCENDING,
  75     DESCENDING
  76   };
  77
  78 struct rec_items
  79 {
  80   struct hmap ht;         /* Hash table of "struct arc_item"s. */
  81 };
  82
  83
  84
  85 /* AUTORECODE data. */
  86 struct autorecode_pgm
  87 {
  88   struct arc_spec *specs;
  89   size_t n_specs;
  90
  91   bool blank_valid;
  92 };
  93
  94 static trns_proc_func autorecode_trns_proc;
  95 static trns_free_func autorecode_trns_free;
  96
  97 static int compare_arc_items (const void *, const void *, const void *aux);
  98 static void arc_free (struct autorecode_pgm *);
  99 static struct arc_item *find_arc_item (
 100   const struct rec_items *, const union value *, int width,
 101   size_t hash);
 102
 103 /* Returns WIDTH with any trailing spaces in VALUE trimmed off (except that a
 104    minimum width of 1 is always returned because otherwise the width would
 105    indicate a numeric type). */
 106 static int
 107 value_trim_spaces (const union value *value, int width)
 108 {
 109   while (width > 1 && value->s[width - 1] == ' ')
 110     width--;
 111   return width;
 112 }
 113
 114 /* Performs the AUTORECODE procedure. */
 115 int
 116 cmd_autorecode (struct lexer *lexer, struct dataset *ds)
 117 {
 118   struct dictionary *dict = dataset_dict (ds);
 119
 120   const struct variable **src_vars = NULL;
 121   size_t n_srcs = 0;
 122
 123   char **dst_names = NULL;
 124   size_t n_dsts = 0;
 125
 126   enum arc_direction direction = ASCENDING;
 127
 128   /* Create procedure. */
 129   struct autorecode_pgm *arc = xzalloc (sizeof *arc);
 130   arc->blank_valid = true;
 131
 132   /* Parse variable lists. */
 133   lex_match_id (lexer, "VARIABLES");
 134   lex_match (lexer, T_EQUALS);
 135   if (!parse_variables_const (lexer, dict, &src_vars, &n_srcs,
 136                               PV_NO_DUPLICATE | PV_NO_SCRATCH))
 137     goto error;
 138   lex_match (lexer, T_SLASH);
 139   if (!lex_force_match_id (lexer, "INTO"))
 140     goto error;
 141   lex_match (lexer, T_EQUALS);
 142   if (!parse_DATA_LIST_vars (lexer, dict, &dst_names, &n_dsts,
 143                              PV_NO_DUPLICATE))
 144     goto error;
 145   if (n_dsts != n_srcs)
 146     {
 147       msg (SE, _("Source variable count (%zu) does not match "
 148                  "target variable count (%zu)."),
 149            n_srcs, n_dsts);
 150
 151       goto error;
 152     }
 153   for (size_t i = 0; i < n_dsts; i++)
 154     {
 155       const char *name = dst_names[i];
 156
 157       if (dict_lookup_var (dict, name) != NULL)
 158         {
 159           msg (SE, _("Target variable %s duplicates existing variable %s."),
 160                name, name);
 161           goto error;
 162         }
 163     }
 164
 165   /* Parse options. */
 166   bool group = false;
 167   while (lex_match (lexer, T_SLASH))
 168     {
 169       if (lex_match_id (lexer, "DESCENDING"))
 170         direction = DESCENDING;
 171       else if (lex_match_id (lexer, "PRINT"))
 172         {
 173           /* Not yet implemented. */
 174         }
 175       else if (lex_match_id (lexer, "GROUP"))
 176         group = true;
 177       else if (lex_match_id (lexer, "BLANK"))
 178         {
 179           lex_match (lexer, T_EQUALS);
 180           if (lex_match_id (lexer, "VALID"))
 181             {
 182               arc->blank_valid = true;
 183             }
 184           else if (lex_match_id (lexer, "MISSING"))
 185             {
 186               arc->blank_valid = false;
 187             }
 188           else
 189             {
 190               lex_error_expecting (lexer, "VALID", "MISSING");
 191               goto error;
 192             }
 193         }
 194       else
 195         {
 196           lex_error_expecting (lexer, "DESCENDING", "PRINT", "GROUP", "BLANK");
 197           goto error;
 198         }
 199     }
 200
 201   if (lex_token (lexer) != T_ENDCMD)
 202     {
 203       lex_error (lexer, _("expecting end of command"));
 204       goto error;
 205     }
 206
 207   /* If GROUP is specified, verify that the variables are all string or all
 208      numeric.  */
 209   if (group)
 210     {
 211       enum val_type type = var_get_type (src_vars[0]);
 212       for (size_t i = 1; i < n_dsts; i++)
 213         {
 214           if (var_get_type (src_vars[i]) != type)
 215             {
 216               size_t string_idx = type == VAL_STRING ? 0 : i;
 217               size_t numeric_idx = type == VAL_STRING ? i : 0;
 218               lex_error (lexer, _("With GROUP, variables may not mix string "
 219                                   "variables (such as %s) and numeric "
 220                                   "variables (such as %s)."),
 221                          var_get_name (src_vars[string_idx]),
 222                          var_get_name (src_vars[numeric_idx]));
 223               goto error;
 224             }
 225         }
 226     }
 227
 228   /* Allocate all the specs and the rec_items that they point to.
 229
 230      If GROUP is specified, there is only a single global rec_items, with the
 231      maximum width 'width', and all of the specs point to it; otherwise each
 232      spec has its own rec_items. */
 233   arc->specs = xmalloc (n_dsts * sizeof *arc->specs);
 234   arc->n_specs = n_dsts;
 235   for (size_t i = 0; i < n_dsts; i++)
 236     {
 237       struct arc_spec *spec = &arc->specs[i];
 238
 239       spec->width = var_get_width (src_vars[i]);
 240       spec->src_idx = var_get_case_index (src_vars[i]);
 241
 242       if (group && i > 0)
 243         spec->items = arc->specs[0].items;
 244       else
 245         {
 246           spec->items = xzalloc (sizeof (*spec->items));
 247           hmap_init (&spec->items->ht);
 248         }
 249     }
 250
 251   /* Initialize specs[*]->mv to the user-missing values for each
 252      source variable. */
 253   if (group)
 254     {
 255       /* Use the first source variable that has any user-missing values. */
 256       size_t mv_idx = 0;
 257       for (size_t i = 0; i < n_dsts; i++)
 258         if (var_has_missing_values (src_vars[i]))
 259           {
 260             mv_idx = i;
 261             break;
 262           }
 263
 264       for (size_t i = 0; i < n_dsts; i++)
 265         mv_copy (&arc->specs[i].mv, var_get_missing_values (src_vars[mv_idx]));
 266     }
 267   else
 268     {
 269       /* Each variable uses its own user-missing values. */
 270       for (size_t i = 0; i < n_dsts; i++)
 271         mv_copy (&arc->specs[i].mv, var_get_missing_values (src_vars[i]));
 272     }
 273
 274   /* Execute procedure. */
 275   struct casereader *input = proc_open (ds);
 276   struct ccase *c;
 277   for (; (c = casereader_read (input)) != NULL; case_unref (c))
 278     for (size_t i = 0; i < arc->n_specs; i++)
 279       {
 280         struct arc_spec *spec = &arc->specs[i];
 281         const union value *value = case_data_idx (c, spec->src_idx);
 282         if (spec->width == 0 && value->f == SYSMIS)
 283           {
 284             /* AUTORECODE never changes the system-missing value.
 285                (Leaving it out of the translation table has this
 286                effect automatically because values not found in the
 287                translation table get translated to system-missing.) */
 288             continue;
 289           }
 290
 291         int width = value_trim_spaces (value, spec->width);
 292         if (width == 1 && value->s[0] == ' ' && !arc->blank_valid)
 293           continue;
 294
 295         size_t hash = value_hash (value, width, 0);
 296         if (find_arc_item (spec->items, value, width, hash))
 297           continue;
 298
 299         struct arc_item *item = xmalloc (sizeof *item);
 300         item->width = width;
 301         value_clone (&item->from, value, width);
 302         item->missing = mv_is_value_missing_varwidth (&spec->mv, value, spec->width,
 303                                                       MV_ANY);
 304         hmap_insert (&spec->items->ht, &item->hmap_node, hash);
 305       }
 306   bool ok = casereader_destroy (input);
 307   ok = proc_commit (ds) && ok;
 308
 309   /* Re-fetch dictionary because it might have changed (if TEMPORARY was in
 310      use). */
 311   dict = dataset_dict (ds);
 312
 313   /* Create transformation. */
 314   for (size_t i = 0; i < arc->n_specs; i++)
 315     {
 316       struct arc_spec *spec = &arc->specs[i];
 317       struct arc_item **items;
 318       struct arc_item *item;
 319       size_t n_items;
 320       size_t j;
 321
 322       /* Create destination variable. */
 323       spec->dst = dict_create_var_assert (dict, dst_names[i], 0);
 324
 325       /* Create array of pointers to items. */
 326       n_items = hmap_count (&spec->items->ht);
 327       items = xmalloc (n_items * sizeof *items);
 328       j = 0;
 329       HMAP_FOR_EACH (item, struct arc_item, hmap_node, &spec->items->ht)
 330         items[j++] = item;
 331
 332       assert (j == n_items);
 333
 334       /* Sort array by value. */
 335       sort (items, n_items, sizeof *items, compare_arc_items, &direction);
 336
 337       /* Assign recoded values in sorted order. */
 338       for (j = 0; j < n_items; j++)
 339         items[j]->to = j + 1;
 340
 341       /* Assign user-missing values.
 342
 343          User-missing values in the source variable(s) must be marked
 344          as user-missing values in the destination variable.  There
 345          might be an arbitrary number of missing values, since the
 346          source variable might have a range.  Our sort function always
 347          puts missing values together at the top of the range, so that
 348          means that we can use a missing value range to cover all of
 349          the user-missing values in any case (but we avoid it unless
 350          necessary because user-missing value ranges are an obscure
 351          feature). */
 352       size_t n_missing = n_items;
 353       for (size_t k = 0; k < n_items; k++)
 354         if (!items[n_items - k - 1]->missing)
 355           {
 356             n_missing = k;
 357             break;
 358           }
 359       if (n_missing > 0)
 360         {
 361           size_t lo = n_items - (n_missing - 1);
 362           size_t hi = n_items;
 363
 364           struct missing_values mv;
 365           mv_init (&mv, 0);
 366           if (n_missing > 3)
 367             mv_add_range (&mv, lo, hi);
 368           else if (n_missing > 0)
 369             for (size_t k = 0; k < n_missing; k++)
 370               mv_add_num (&mv, lo + k);
 371           var_set_missing_values (spec->dst, &mv);
 372           mv_destroy (&mv);
 373         }
 374
 375       /* Add value labels to the destination variable which indicate
 376          the source value from whence the new value comes. */
 377       for (j = 0; j < n_items; j++)
 378         {
 379           const union value *from = &items[j]->from;
 380           const int src_width = items[j]->width;
 381           char *recoded_value;
 382           if (src_width > 0)
 383             {
 384               const char *str = CHAR_CAST_BUG (const char *, from->s);
 385
 386               recoded_value = recode_string (UTF8, dict_get_encoding (dict),
 387                                              str, src_width);
 388             }
 389           else
 390             recoded_value = c_xasprintf ("%.*g", DBL_DIG + 1, from->f);
 391
 392           /* Remove trailing whitespace. */
 393           size_t len = strlen (recoded_value);
 394           while (len > 0 && recoded_value[len - 1] == ' ')
 395             recoded_value[--len] = '\0';
 396
 397           /* Add value label, if it would be nonempty. */
 398           if (len)
 399             {
 400               union value to_val = { .f = items[j]->to };
 401               var_add_value_label (spec->dst, &to_val, recoded_value);
 402             }
 403           free (recoded_value);
 404         }
 405
 406       /* Free array. */
 407       free (items);
 408     }
 409   add_transformation (ds, autorecode_trns_proc, autorecode_trns_free, arc);
 410
 411   for (size_t i = 0; i < n_dsts; i++)
 412     free (dst_names[i]);
 413   free (dst_names);
 414   free (src_vars);
 415
 416   return ok ? CMD_SUCCESS : CMD_CASCADING_FAILURE;
 417
 418 error:
 419   for (size_t i = 0; i < n_dsts; i++)
 420     free (dst_names[i]);
 421   free (dst_names);
 422   free (src_vars);
 423   arc_free (arc);
 424   return CMD_CASCADING_FAILURE;
 425 }
 426
 427 static void
 428 arc_free (struct autorecode_pgm *arc)
 429 {
 430   if (arc != NULL)
 431     {
 432       for (size_t i = 0; i < arc->n_specs; i++)
 433         {
 434           struct arc_spec *spec = &arc->specs[i];
 435           struct arc_item *item, *next;
 436
 437           HMAP_FOR_EACH_SAFE (item, next, struct arc_item, hmap_node,
 438                               &spec->items->ht)
 439             {
 440               value_destroy (&item->from, item->width);
 441               hmap_delete (&spec->items->ht, &item->hmap_node);
 442               free (item);
 443             }
 444           mv_destroy (&spec->mv);
 445         }
 446
 447       size_t n_rec_items =
 448         (arc->n_specs == 1 || arc->specs[0].items == arc->specs[1].items
 449          ? 1
 450          : arc->n_specs);
 451       for (size_t i = 0; i < n_rec_items; i++)
 452         {
 453           struct arc_spec *spec = &arc->specs[i];
 454           hmap_destroy (&spec->items->ht);
 455           free (spec->items);
 456         }
 457
 458       free (arc->specs);
 459       free (arc);
 460     }
 461 }
 462
 463 static struct arc_item *
 464 find_arc_item (const struct rec_items *items,
 465                const union value *value, int width,
 466                size_t hash)
 467 {
 468   struct arc_item *item;
 469
 470   HMAP_FOR_EACH_WITH_HASH (item, struct arc_item, hmap_node, hash, &items->ht)
 471     if (item->width == width && value_equal (value, &item->from, width))
 472       return item;
 473   return NULL;
 474 }
 475
 476 static int
 477 compare_arc_items (const void *a_, const void *b_, const void *direction_)
 478 {
 479   const struct arc_item *const *ap = a_;
 480   const struct arc_item *const *bp = b_;
 481   const struct arc_item *a = *ap;
 482   const struct arc_item *b = *bp;
 483
 484   /* User-missing values always sort to the highest target values
 485      (regardless of sort direction). */
 486   if (a->missing != b->missing)
 487     return a->missing < b->missing ? -1 : 1;
 488
 489   /* Otherwise, compare the data. */
 490   int aw = a->width;
 491   int bw = b->width;
 492   int cmp;
 493   if (aw == bw)
 494     cmp = value_compare_3way (&a->from, &b->from, aw);
 495   else
 496     {
 497       assert (aw && bw);
 498       cmp = buf_compare_rpad (CHAR_CAST_BUG (const char *, a->from.s), aw,
 499                               CHAR_CAST_BUG (const char *, b->from.s), bw);
 500     }
 501
 502   /* Then apply sort direction. */
 503   const enum arc_direction *directionp = direction_;
 504   enum arc_direction direction = *directionp;
 505   return direction == ASCENDING ? cmp : -cmp;
 506 }
 507
 508 static int
 509 autorecode_trns_proc (void *arc_, struct ccase **c,
 510                       casenumber case_idx UNUSED)
 511 {
 512   struct autorecode_pgm *arc = arc_;
 513
 514   *c = case_unshare (*c);
 515   for (size_t i = 0; i < arc->n_specs; i++)
 516     {
 517       const struct arc_spec *spec = &arc->specs[i];
 518       const union value *value = case_data_idx (*c, spec->src_idx);
 519       int width = value_trim_spaces (value, spec->width);
 520       size_t hash = value_hash (value, width, 0);
 521       const struct arc_item *item = find_arc_item (spec->items, value, width,
 522                                                    hash);
 523       case_data_rw (*c, spec->dst)->f = item ? item->to : SYSMIS;
 524     }
 525
 526   return TRNS_CONTINUE;
 527 }
 528
 529 static bool
 530 autorecode_trns_free (void *arc_)
 531 {
 532   struct autorecode_pgm *arc = arc_;
 533
 534   arc_free (arc);
 535   return true;
 536 }