Fix assertion for proper Huffman merge pattern: 0 == 1 modulo 1.
[pspp] / src / modify-vars.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3    Written by Ben Pfaff <blp@gnu.org>.
4
5    This program is free software; you can redistribute it and/or
6    modify it under the terms of the GNU General Public License as
7    published by the Free Software Foundation; either version 2 of the
8    License, or (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful, but
11    WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
18    02111-1307, USA. */
19
20 #include <config.h>
21 #include <stdlib.h>
22 #include "error.h"
23 #include "algorithm.h"
24 #include "alloc.h"
25 #include "bitvector.h"
26 #include "command.h"
27 #include "dictionary.h"
28 #include "error.h"
29 #include "hash.h"
30 #include "lexer.h"
31 #include "misc.h"
32 #include "str.h"
33 #include "var.h"
34 #include "vfm.h"
35
36 /* FIXME: should change weighting variable, etc. */
37 /* These control the ordering produced by
38    compare_variables_given_ordering(). */
39 struct ordering
40   {
41     int forward;                /* 1=FORWARD, 0=BACKWARD. */
42     int positional;             /* 1=POSITIONAL, 0=ALPHA. */
43   };
44
45 /* Increasing order of variable index. */
46 static struct ordering forward_positional_ordering = {1, 1};
47
48 static int compare_variables_given_ordering (const void *, const void *,
49                                              void *ordering);
50
51 /* Explains how to modify the variables in a dictionary. */
52 struct var_modification
53   {
54     /* New variable ordering. */
55     struct variable **reorder_vars;
56     size_t reorder_cnt;
57
58     /* DROP/KEEP information. */
59     struct variable **drop_vars;
60     size_t drop_cnt;
61
62     /* New variable names. */
63     struct variable **rename_vars;
64     char **new_names;
65     size_t rename_cnt;
66   };
67
68 static int rearrange_dict (struct dictionary *d,
69                            const struct var_modification *vm);
70
71 /* Performs MODIFY VARS command. */
72 int
73 cmd_modify_vars (void)
74 {
75   /* Bits indicated whether we've already encountered a subcommand of
76      this type. */
77   unsigned already_encountered = 0;
78
79   /* What we're gonna do to the active file. */
80   struct var_modification vm;
81
82   /* Return code. */
83   int ret_code = CMD_FAILURE;
84
85   size_t i;
86
87   if (temporary != 0)
88     {
89       msg (SE, _("MODIFY VARS may not be used after TEMPORARY.  "
90                  "Temporary transformations will be made permanent."));
91       cancel_temporary (); 
92     }
93
94   vm.reorder_vars = NULL;
95   vm.reorder_cnt = 0;
96   vm.rename_vars = NULL;
97   vm.new_names = NULL;
98   vm.rename_cnt = 0;
99   vm.drop_vars = NULL;
100   vm.drop_cnt = 0;
101
102   /* Parse each subcommand. */
103   lex_match ('/');
104   for (;;)
105     {
106       if (lex_match_id ("REORDER"))
107         {
108           struct variable **v = NULL;
109           int nv = 0;
110
111           if (already_encountered & 1)
112             {
113               msg (SE, _("REORDER subcommand may be given at most once."));
114               goto done;
115             }
116           already_encountered |= 1;
117
118           lex_match ('=');
119           do
120             {
121               struct ordering ordering;
122               int prev_nv = nv;
123
124               ordering.forward = ordering.positional = 1;
125               if (lex_match_id ("FORWARD"));
126               else if (lex_match_id ("BACKWARD"))
127                 ordering.forward = 0;
128               if (lex_match_id ("POSITIONAL"));
129               else if (lex_match_id ("ALPHA"))
130                 ordering.positional = 0;
131
132               if (lex_match (T_ALL) || token == '/' || token == '.')
133                 {
134                   if (prev_nv != 0)
135                     {
136                       msg (SE, _("Cannot specify ALL after specifying a set "
137                            "of variables."));
138                       goto done;
139                     }
140                   dict_get_vars (default_dict, &v, &nv, 1u << DC_SYSTEM);
141                 }
142               else
143                 {
144                   if (!lex_match ('('))
145                     {
146                       msg (SE, _("`(' expected on REORDER subcommand."));
147                       free (v);
148                       goto done;
149                     }
150                   if (!parse_variables (default_dict, &v, &nv,
151                                         PV_APPEND | PV_NO_DUPLICATE))
152                     {
153                       free (v);
154                       goto done;
155                     }
156                   if (!lex_match (')'))
157                     {
158                       msg (SE, _("`)' expected following variable names on "
159                            "REORDER subcommand."));
160                       free (v);
161                       goto done;
162                     }
163                 }
164               sort (&v[prev_nv], nv - prev_nv, sizeof *v,
165                     compare_variables_given_ordering, &ordering);
166             }
167           while (token != '/' && token != '.');
168
169           vm.reorder_vars = v;
170           vm.reorder_cnt = nv;
171         }
172       else if (lex_match_id ("RENAME"))
173         {
174           if (already_encountered & 2)
175             {
176               msg (SE, _("RENAME subcommand may be given at most once."));
177               goto done;
178             }
179           already_encountered |= 2;
180
181           lex_match ('=');
182           do
183             {
184               int prev_nv_1 = vm.rename_cnt;
185               int prev_nv_2 = vm.rename_cnt;
186
187               if (!lex_match ('('))
188                 {
189                   msg (SE, _("`(' expected on RENAME subcommand."));
190                   goto done;
191                 }
192               if (!parse_variables (default_dict, &vm.rename_vars, &vm.rename_cnt,
193                                     PV_APPEND | PV_NO_DUPLICATE))
194                 goto done;
195               if (!lex_match ('='))
196                 {
197                   msg (SE, _("`=' expected between lists of new and old variable "
198                        "names on RENAME subcommand."));
199                   goto done;
200                 }
201               if (!parse_DATA_LIST_vars (&vm.new_names, &prev_nv_1, PV_APPEND))
202                 goto done;
203               if (prev_nv_1 != vm.rename_cnt)
204                 {
205                   msg (SE, _("Differing number of variables in old name list "
206                        "(%d) and in new name list (%d)."),
207                        vm.rename_cnt - prev_nv_2, prev_nv_1 - prev_nv_2);
208                   for (i = 0; i < prev_nv_1; i++)
209                     free (vm.new_names[i]);
210                   free (vm.new_names);
211                   vm.new_names = NULL;
212                   goto done;
213                 }
214               if (!lex_match (')'))
215                 {
216                   msg (SE, _("`)' expected after variable lists on RENAME "
217                        "subcommand."));
218                   goto done;
219                 }
220             }
221           while (token != '.' && token != '/');
222         }
223       else if (lex_match_id ("KEEP"))
224         {
225           struct variable **keep_vars, **all_vars, **drop_vars;
226           int keep_cnt, all_cnt, drop_cnt;
227
228           if (already_encountered & 4)
229             {
230               msg (SE, _("KEEP subcommand may be given at most once.  It may not"
231                    "be given in conjunction with the DROP subcommand."));
232               goto done;
233             }
234           already_encountered |= 4;
235
236           lex_match ('=');
237           if (!parse_variables (default_dict, &keep_vars, &keep_cnt, PV_NONE))
238             goto done;
239
240           /* Transform the list of variables to keep into a list of
241              variables to drop.  First sort the keep list, then figure
242              out which variables are missing. */
243           sort (keep_vars, keep_cnt, sizeof *keep_vars,
244                 compare_variables_given_ordering, &forward_positional_ordering);
245
246           dict_get_vars (default_dict, &all_vars, &all_cnt, 0);
247
248           drop_cnt = all_cnt - keep_cnt;
249           drop_vars = xmalloc (drop_cnt * sizeof *keep_vars);
250           if (set_difference (all_vars, all_cnt,
251                               keep_vars, keep_cnt,
252                               sizeof *all_vars,
253                               drop_vars,
254                               compare_variables_given_ordering,
255                               &forward_positional_ordering)
256               != drop_cnt)
257             assert (0);
258
259           free (keep_vars);
260           free (all_vars);
261
262           vm.drop_vars = drop_vars;
263           vm.drop_cnt = drop_cnt;
264         }
265       else if (lex_match_id ("DROP"))
266         {
267           struct variable **drop_vars;
268           int drop_cnt;
269
270           if (already_encountered & 4)
271             {
272               msg (SE, _("DROP subcommand may be given at most once.  It may "
273                          "not be given in conjunction with the KEEP "
274                          "subcommand."));
275               goto done;
276             }
277           already_encountered |= 4;
278
279           lex_match ('=');
280           if (!parse_variables (default_dict, &drop_vars, &drop_cnt, PV_NONE))
281             goto done;
282           vm.drop_vars = drop_vars;
283           vm.drop_cnt = drop_cnt;
284         }
285       else if (lex_match_id ("MAP"))
286         {
287           struct dictionary *temp = dict_clone (default_dict);
288           int success = rearrange_dict (temp, &vm);
289           if (success) 
290             {
291               /* FIXME: display new dictionary. */ 
292             }
293           dict_destroy (temp);
294         }
295       else
296         {
297           if (token == T_ID)
298             msg (SE, _("Unrecognized subcommand name `%s'."), tokid);
299           else
300             msg (SE, _("Subcommand name expected."));
301           goto done;
302         }
303
304       if (token == '.')
305         break;
306       if (token != '/')
307         {
308           msg (SE, _("`/' or `.' expected."));
309           goto done;
310         }
311       lex_get ();
312     }
313
314   if (already_encountered & (1 | 4))
315     {
316       /* Read the data. */
317       procedure (NULL, NULL);
318     }
319
320   if (!rearrange_dict (default_dict, &vm))
321     goto done; 
322
323   ret_code = CMD_SUCCESS;
324
325 done:
326   free (vm.reorder_vars);
327   free (vm.rename_vars);
328   for (i = 0; i < vm.rename_cnt; i++)
329     free (vm.new_names[i]);
330   free (vm.new_names);
331   free (vm.drop_vars);
332   return ret_code;
333 }
334
335 /* Compares A and B according to the settings in
336    ORDERING, returning a strcmp()-type result. */
337 static int
338 compare_variables_given_ordering (const void *a_, const void *b_,
339                                   void *ordering_)
340 {
341   struct variable *const *pa = a_;
342   struct variable *const *pb = b_;
343   const struct variable *a = *pa;
344   const struct variable *b = *pb;
345   const struct ordering *ordering = ordering_;
346
347   int result;
348   if (ordering->positional)
349     result = a->index < b->index ? -1 : a->index > b->index;
350   else
351     result = strcmp (a->name, b->name);
352   if (!ordering->forward)
353     result = -result;
354   return result;
355 }
356
357 /* Pairs a variable with a new name. */
358 struct var_renaming
359   {
360     struct variable *var;
361     char new_name[9];
362   };
363
364 /* A algo_compare_func that compares new_name members in struct
365    var_renaming structures A and B. */
366 static int
367 compare_var_renaming_by_new_name (const void *a_, const void *b_,
368                                   void *foo UNUSED) 
369 {
370   const struct var_renaming *a = a_;
371   const struct var_renaming *b = b_;
372
373   return strcmp (a->new_name, b->new_name);
374 }
375
376 /* Returns true if performing VM on dictionary D would not cause
377    problems such as duplicate variable names.  Returns false
378    otherwise, and issues an error message. */
379 static int
380 validate_var_modification (const struct dictionary *d,
381                            const struct var_modification *vm) 
382 {
383   /* Variable reordering can't be a problem, so we don't simulate
384      it.  Variable renaming can cause duplicate names, but
385      dropping variables can eliminate them, so we simulate both
386      of those. */
387   struct variable **all_vars;
388   struct variable **keep_vars;
389   struct variable **drop_vars;
390   size_t all_cnt, keep_cnt, drop_cnt;
391
392   struct var_renaming *var_renaming;
393   int valid;
394   size_t i;
395
396   /* All variables, in index order. */
397   dict_get_vars (d, &all_vars, &all_cnt, 0);
398
399   /* Drop variables, in index order. */
400   drop_cnt = vm->drop_cnt;
401   drop_vars = xmalloc (drop_cnt * sizeof *drop_vars);
402   memcpy (drop_vars, vm->drop_vars, drop_cnt * sizeof *drop_vars);
403   sort (drop_vars, drop_cnt, sizeof *drop_vars,
404         compare_variables_given_ordering, &forward_positional_ordering);
405
406   /* Keep variables, in index order. */
407   keep_cnt = all_cnt - drop_cnt;
408   keep_vars = xmalloc (keep_cnt * sizeof *keep_vars);
409   if (set_difference (all_vars, all_cnt,
410                       drop_vars, drop_cnt,
411                       sizeof *all_vars,
412                       keep_vars,
413                       compare_variables_given_ordering,
414                       &forward_positional_ordering) != keep_cnt)
415     assert (0);
416
417   /* Copy variables into var_renaming array. */
418   var_renaming = xmalloc (keep_cnt * sizeof *var_renaming);
419   for (i = 0; i < keep_cnt; i++) 
420     {
421       var_renaming[i].var = keep_vars[i];
422       strcpy (var_renaming[i].new_name, keep_vars[i]->name);
423     }
424   
425   /* Rename variables in var_renaming array. */
426   for (i = 0; i < vm->rename_cnt; i++) 
427     {
428       struct variable *const *kv;
429       struct var_renaming *vr;
430
431       /* Get the var_renaming element. */
432       kv = binary_search (keep_vars, keep_cnt, sizeof *keep_vars,
433                           &vm->rename_vars[i],
434                           compare_variables_given_ordering,
435                           &forward_positional_ordering);
436       if (kv == NULL)
437         continue;
438       vr = var_renaming + (kv - keep_vars);
439
440       strcpy (vr->new_name, vm->new_names[i]);
441     }
442
443   /* Sort var_renaming array by new names and check for
444      duplicates. */
445   sort (var_renaming, keep_cnt, sizeof *var_renaming,
446         compare_var_renaming_by_new_name, NULL);
447   valid = adjacent_find_equal (var_renaming, keep_cnt, sizeof *var_renaming,
448                                compare_var_renaming_by_new_name, NULL) == NULL;
449
450   /* Clean up. */
451   free (all_vars);
452   free (keep_vars);
453   free (drop_vars);
454   free (var_renaming);
455
456   return valid;
457 }
458
459 /* Reoders, removes, and renames variables in dictionary D
460    according to VM.  Returns nonzero if successful, zero if there
461    would have been duplicate variable names if the modifications
462    had been carried out.  In the latter case, the dictionary is
463    not modified. */
464 static int
465 rearrange_dict (struct dictionary *d, const struct var_modification *vm)
466 {
467   char **rename_old_names;
468
469   struct variable **rename_vars;
470   char **rename_new_names;
471   size_t rename_cnt;
472
473   size_t i;
474
475   /* Check whether the modifications will cause duplicate
476      names. */
477   if (!validate_var_modification (d, vm))
478     return 0;
479
480   /* Record the old names of variables to rename.  After
481      variables are deleted, we can't depend on the variables to
482      still exist, but we can still look them up by name. */
483   rename_old_names = xmalloc (vm->rename_cnt * sizeof *rename_old_names);
484   for (i = 0; i < vm->rename_cnt; i++)
485     rename_old_names[i] = xstrdup (vm->rename_vars[i]->name);
486
487   /* Reorder and delete variables. */
488   dict_reorder_vars (d, vm->reorder_vars, vm->reorder_cnt);
489   dict_delete_vars (d, vm->drop_vars, vm->drop_cnt);
490
491   /* Compose lists of variables to rename and their new names. */
492   rename_vars = xmalloc (vm->rename_cnt * sizeof *rename_vars);
493   rename_new_names = xmalloc (vm->rename_cnt * sizeof *rename_new_names);
494   rename_cnt = 0;
495   for (i = 0; i < vm->rename_cnt; i++)
496     {
497       struct variable *var = dict_lookup_var (d, rename_old_names[i]);
498       if (var == NULL)
499         continue;
500       
501       rename_vars[rename_cnt] = var;
502       rename_new_names[rename_cnt] = vm->new_names[i];
503       rename_cnt++;
504     }
505
506   /* Do renaming. */
507   if (dict_rename_vars (d, rename_vars, rename_new_names, rename_cnt,
508                         NULL) == 0)
509     assert (0);
510
511   /* Clean up. */
512   for (i = 0; i < vm->rename_cnt; i++)
513     free (rename_old_names[i]);
514   free (rename_old_names);
515   free (rename_vars);
516   free (rename_new_names);
517
518   return 1;
519 }