Fix assertion for proper Huffman merge pattern: 0 == 1 modulo 1.
[pspp] / src / autorecode.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 "error.h"
22 #include <stdlib.h>
23 #include "alloc.h"
24 #include "case.h"
25 #include "command.h"
26 #include "dictionary.h"
27 #include "error.h"
28 #include "hash.h"
29 #include "lexer.h"
30 #include "pool.h"
31 #include "str.h"
32 #include "var.h"
33 #include "vfm.h"
34
35 /* FIXME: Implement PRINT subcommand. */
36
37 /* Explains how to recode one value.  `from' must be first element.  */
38 struct arc_item
39   {
40     union value from;           /* Original value. */
41     double to;                  /* Recoded value. */
42   };
43
44 /* Explains how to recode an AUTORECODE variable. */
45 struct arc_spec
46   {
47     struct variable *src;       /* Source variable. */
48     struct variable *dest;      /* Target variable. */
49     struct hsh_table *items;    /* Hash table of `freq's. */
50   };
51
52 /* AUTORECODE transformation. */
53 struct autorecode_trns
54   {
55     struct trns_header h;
56     struct pool *owner;         /* Contains AUTORECODE specs. */
57     struct arc_spec *specs;     /* AUTORECODE specifications. */
58     int spec_cnt;               /* Number of specifications. */
59   };
60
61 /* Descending or ascending sort order. */
62 enum direction 
63   {
64     ASCENDING,
65     DESCENDING
66   };
67
68 /* AUTORECODE data. */
69 struct autorecode_pgm 
70   {
71     struct variable **src_vars;    /* Source variables. */
72     char **dst_names;              /* Target variable names. */
73     struct variable **dst_vars;    /* Target variables. */
74     struct hsh_table **src_values; /* `union value's of source vars. */
75     int var_cnt;                   /* Number of variables. */
76     struct pool *src_values_pool;  /* Pool used by src_values. */
77     enum direction direction;      /* Sort order. */
78     int print;                     /* Print mapping table if nonzero. */
79   };
80
81 static trns_proc_func autorecode_trns_proc;
82 static trns_free_func autorecode_trns_free;
83 static int autorecode_proc_func (struct ccase *, void *);
84 static hsh_compare_func compare_alpha_value, compare_numeric_value;
85 static hsh_hash_func hash_alpha_value, hash_numeric_value;
86
87 static void recode (const struct autorecode_pgm *);
88 static void arc_free (struct autorecode_pgm *);
89
90 /* Performs the AUTORECODE procedure. */
91 int
92 cmd_autorecode (void)
93 {
94   struct autorecode_pgm arc;
95   int dst_cnt;
96   int i;
97
98   arc.src_vars = NULL;
99   arc.dst_names = NULL;
100   arc.dst_vars = NULL;
101   arc.src_values = NULL;
102   arc.var_cnt = 0;
103   arc.src_values_pool = NULL;
104   arc.direction = ASCENDING;
105   arc.print = 0;
106   dst_cnt = 0;
107
108   lex_match_id ("VARIABLES");
109   lex_match ('=');
110   if (!parse_variables (default_dict, &arc.src_vars, &arc.var_cnt,
111                         PV_NO_DUPLICATE))
112     goto lossage;
113   if (!lex_force_match_id ("INTO"))
114     goto lossage;
115   lex_match ('=');
116   if (!parse_DATA_LIST_vars (&arc.dst_names, &dst_cnt, PV_NONE))
117     goto lossage;
118   if (dst_cnt != arc.var_cnt)
119     {
120       int i;
121
122       msg (SE, _("Source variable count (%d) does not match "
123                  "target variable count (%d)."), arc.var_cnt, dst_cnt);
124
125       for (i = 0; i < dst_cnt; i++)
126         free (arc.dst_names[i]);
127       free (arc.dst_names);
128       arc.dst_names = NULL;
129
130       goto lossage;
131     }
132   while (lex_match ('/'))
133     if (lex_match_id ("DESCENDING"))
134       arc.direction = DESCENDING;
135     else if (lex_match_id ("PRINT"))
136       arc.print = 1;
137   if (token != '.')
138     {
139       lex_error (_("expecting end of command"));
140       goto lossage;
141     }
142
143   for (i = 0; i < arc.var_cnt; i++)
144     {
145       int j;
146
147       if (dict_lookup_var (default_dict, arc.dst_names[i]) != NULL)
148         {
149           msg (SE, _("Target variable %s duplicates existing variable %s."),
150                arc.dst_names[i], arc.dst_names[i]);
151           goto lossage;
152         }
153       for (j = 0; j < i; j++)
154         if (!strcmp (arc.dst_names[i], arc.dst_names[j]))
155           {
156             msg (SE, _("Duplicate variable name %s among target variables."),
157                  arc.dst_names[i]);
158             goto lossage;
159           }
160     }
161
162   arc.src_values_pool = pool_create ();
163   arc.dst_vars = xmalloc (sizeof *arc.dst_vars * arc.var_cnt);
164   arc.src_values = xmalloc (sizeof *arc.src_values * arc.var_cnt);
165   for (i = 0; i < dst_cnt; i++)
166     if (arc.src_vars[i]->type == ALPHA)
167       arc.src_values[i] = hsh_create (10, compare_alpha_value,
168                                       hash_alpha_value, NULL, arc.src_vars[i]);
169     else
170       arc.src_values[i] = hsh_create (10, compare_numeric_value,
171                                       hash_numeric_value, NULL, NULL);
172
173   procedure (autorecode_proc_func, &arc);
174
175   for (i = 0; i < arc.var_cnt; i++)
176     {
177       arc.dst_vars[i] = dict_create_var_assert (default_dict,
178                                                 arc.dst_names[i], 0);
179       arc.dst_vars[i]->init = 0;
180     }
181
182   recode (&arc);
183   arc_free (&arc);
184   return CMD_SUCCESS;
185
186 lossage:
187   arc_free (&arc);
188   return CMD_FAILURE;
189 }
190
191 static void
192 arc_free (struct autorecode_pgm *arc) 
193 {
194   free (arc->src_vars);
195   if (arc->dst_names != NULL) 
196     {
197       int i;
198       
199       for (i = 0; i < arc->var_cnt; i++)
200         free (arc->dst_names[i]);
201       free (arc->dst_names);
202     }
203   free (arc->dst_vars);
204   if (arc->src_values != NULL) 
205     {
206       int i;
207
208       for (i = 0; i < arc->var_cnt; i++)
209         hsh_destroy (arc->src_values[i]);
210       free (arc->src_values);
211     }
212   pool_destroy (arc->src_values_pool);
213 }
214
215 \f
216 /* AUTORECODE transformation. */
217
218 static void
219 recode (const struct autorecode_pgm *arc)
220 {
221   struct autorecode_trns *t;
222   struct pool *pool;
223   int i;
224
225   pool = pool_create ();
226   t = xmalloc (sizeof *t);
227   t->h.proc = autorecode_trns_proc;
228   t->h.free = autorecode_trns_free;
229   t->owner = pool;
230   t->specs = pool_alloc (t->owner, sizeof *t->specs * arc->var_cnt);
231   t->spec_cnt = arc->var_cnt;
232   for (i = 0; i < arc->var_cnt; i++)
233     {
234       struct arc_spec *spec = &t->specs[i];
235       void **p = hsh_sort (arc->src_values[i]);
236       int count = hsh_count (arc->src_values[i]);
237       int j;
238
239       spec->src = arc->src_vars[i];
240       spec->dest = arc->dst_vars[i];
241
242       if (arc->src_vars[i]->type == ALPHA)
243         spec->items = hsh_create (2 * count, compare_alpha_value,
244                                   hash_alpha_value, NULL, arc->src_vars[i]);
245       else
246         spec->items = hsh_create (2 * count, compare_numeric_value,
247                                   hash_numeric_value, NULL, NULL);
248
249       for (j = 0; *p; p++, j++)
250         {
251           struct arc_item *item = pool_alloc (t->owner, sizeof *item);
252           union value *vp = *p;
253           
254           if (arc->src_vars[i]->type == NUMERIC)
255             item->from.f = vp->f;
256           else
257             item->from.c = pool_strdup (t->owner, vp->c);
258           item->to = arc->direction == ASCENDING ? j + 1 : count - j;
259           hsh_force_insert (spec->items, item);
260         }
261     }
262   add_transformation (&t->h);
263 }
264
265 static int
266 autorecode_trns_proc (struct trns_header * trns, struct ccase * c,
267                       int case_idx UNUSED)
268 {
269   struct autorecode_trns *t = (struct autorecode_trns *) trns;
270   int i;
271
272   for (i = 0; i < t->spec_cnt; i++)
273     {
274       struct arc_spec *spec = &t->specs[i];
275       struct arc_item *item;
276       union value v;
277
278       if (spec->src->type == NUMERIC)
279         v.f = case_num (c, spec->src->fv);
280       else
281         v.c = (char *) case_str (c, spec->src->fv);
282       item = hsh_force_find (spec->items, &v);
283
284       case_data_rw (c, spec->dest->fv)->f = item->to;
285     }
286   return -1;
287 }
288
289 static void
290 autorecode_trns_free (struct trns_header * trns)
291 {
292   struct autorecode_trns *t = (struct autorecode_trns *) trns;
293   int i;
294
295   for (i = 0; i < t->spec_cnt; i++)
296     hsh_destroy (t->specs[i].items);
297   pool_destroy (t->owner);
298 }
299 \f
300 /* AUTORECODE procedure. */
301
302 static int
303 compare_alpha_value (const void *a_, const void *b_, void *v_)
304 {
305   const union value *a = a_;
306   const union value *b = b_;
307   const struct variable *v = v_;
308
309   return memcmp (a->c, b->c, v->width);
310 }
311
312 static unsigned
313 hash_alpha_value (const void *a_, void *v_)
314 {
315   const union value *a = a_;
316   const struct variable *v = v_;
317   
318   return hsh_hash_bytes (a->c, v->width);
319 }
320
321 static int
322 compare_numeric_value (const void *a_, const void *b_, void *foo UNUSED)
323 {
324   const union value *a = a_;
325   const union value *b = b_;
326
327   return a->f < b->f ? -1 : a->f > b->f;
328 }
329
330 static unsigned
331 hash_numeric_value (const void *a_, void *foo UNUSED)
332 {
333   const union value *a = a_;
334
335   return hsh_hash_double (a->f);
336 }
337
338 static int
339 autorecode_proc_func (struct ccase *c, void *arc_)
340 {
341   struct autorecode_pgm *arc = arc_;
342   int i;
343
344   for (i = 0; i < arc->var_cnt; i++)
345     {
346       union value v, *vp, **vpp;
347
348       if (arc->src_vars[i]->type == NUMERIC)
349         v.f = case_num (c, arc->src_vars[i]->fv);
350       else
351         v.c = (char *) case_str (c, arc->src_vars[i]->fv);
352
353       vpp = (union value **) hsh_probe (arc->src_values[i], &v);
354       if (*vpp == NULL)
355         {
356           vp = pool_alloc (arc->src_values_pool, sizeof (union value));
357           if (arc->src_vars[i]->type == NUMERIC)
358             vp->f = v.f;
359           else
360             vp->c = pool_strndup (arc->src_values_pool,
361                                   v.c, arc->src_vars[i]->width);
362           *vpp = vp;
363         }
364     }
365   return 1;
366 }