X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flanguage%2Fstats%2Fautorecode.c;h=a18a94c6bd5fa5514a7fb69e43ac5a58e4f1697c;hb=8f40c87f9db239685a174ffc526cb91f0c76ee97;hp=db45d4eae701d09aa2b8fb5100b61afb68e7e329;hpb=244ade48f9c233532cc535d3233fdef53bf9266b;p=pspp diff --git a/src/language/stats/autorecode.c b/src/language/stats/autorecode.c index db45d4eae7..a18a94c6bd 100644 --- a/src/language/stats/autorecode.c +++ b/src/language/stats/autorecode.c @@ -1,377 +1,393 @@ -/* PSPP - computes sample statistics. - Copyright (C) 1997-9, 2000 Free Software Foundation, Inc. - Written by Ben Pfaff . +/* PSPP - a program for statistical analysis. + Copyright (C) 1997-9, 2000, 2009, 2010 Free Software Foundation, Inc. - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2 of the - License, or (at your option) any later version. + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. - This program is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - 02110-1301, USA. */ + along with this program. If not, see . */ #include + #include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include +#include "data/case.h" +#include "data/casereader.h" +#include "data/dictionary.h" +#include "data/procedure.h" +#include "data/transformations.h" +#include "data/variable.h" +#include "language/command.h" +#include "language/lexer/lexer.h" +#include "language/lexer/variable-parser.h" +#include "libpspp/array.h" +#include "libpspp/i18n.h" +#include "libpspp/compiler.h" +#include "libpspp/hash-functions.h" +#include "libpspp/hmap.h" +#include "libpspp/message.h" +#include "libpspp/pool.h" +#include "libpspp/str.h" + +#include "gl/xalloc.h" +#include "gl/vasnprintf.h" #include "gettext.h" #define _(msgid) gettext (msgid) /* FIXME: Implement PRINT subcommand. */ -/* An AUTORECODE variable's original value. */ -union arc_value - { - double f; /* Numeric. */ - char *c; /* Short or long string. */ - }; - -/* Explains how to recode one value. `from' must be first element. */ +/* Explains how to recode one value. */ struct arc_item { - union arc_value from; /* Original value. */ + struct hmap_node hmap_node; /* Element in "struct arc_spec" hash table. */ + union value from; /* Original value. */ + int width; /* Width of the original value */ + double to; /* Recoded value. */ }; /* Explains how to recode an AUTORECODE variable. */ struct arc_spec { - struct variable *src; /* Source variable. */ - struct variable *dest; /* Target variable. */ - struct hsh_table *items; /* Hash table of `freq's. */ - }; - -/* AUTORECODE transformation. */ -struct autorecode_trns - { - struct pool *pool; /* Contains AUTORECODE specs. */ - struct arc_spec *specs; /* AUTORECODE specifications. */ - size_t spec_cnt; /* Number of specifications. */ + const struct variable *src; /* Source variable. */ + struct variable *dst; /* Target variable. */ + struct hmap *items; /* Hash table of "struct arc_item"s. */ }; /* Descending or ascending sort order. */ -enum direction +enum arc_direction { ASCENDING, DESCENDING }; /* AUTORECODE data. */ -struct autorecode_pgm - { - struct variable **src_vars; /* Source variables. */ - char **dst_names; /* Target variable names. */ - struct variable **dst_vars; /* Target variables. */ - struct hsh_table **src_values; /* `union arc_value's of source vars. */ - size_t var_cnt; /* Number of variables. */ - struct pool *src_values_pool; /* Pool used by src_values. */ - enum direction direction; /* Sort order. */ - int print; /* Print mapping table if nonzero. */ - }; +struct autorecode_pgm +{ + struct arc_spec *specs; + size_t n_specs; + + /* Hash table of "struct arc_item"s. */ + struct hmap *global_items; +}; static trns_proc_func autorecode_trns_proc; static trns_free_func autorecode_trns_free; -static bool autorecode_proc_func (const struct ccase *, void *, const struct dataset *); -static hsh_compare_func compare_alpha_value, compare_numeric_value; -static hsh_hash_func hash_alpha_value, hash_numeric_value; -static void recode (struct dataset *, const struct autorecode_pgm *); +static int compare_arc_items (const void *, const void *, const void *aux); static void arc_free (struct autorecode_pgm *); +static struct arc_item *find_arc_item (const struct arc_spec *, const union value *, + size_t hash); /* Performs the AUTORECODE procedure. */ int -cmd_autorecode (struct dataset *ds) +cmd_autorecode (struct lexer *lexer, struct dataset *ds) { - struct autorecode_pgm arc; - size_t dst_cnt; + struct autorecode_pgm *arc = NULL; + struct dictionary *dict = dataset_dict (ds); + + const struct variable **src_vars = NULL; + char **dst_names = NULL; + size_t n_srcs = 0; + size_t n_dsts = 0; + + enum arc_direction direction = ASCENDING; + bool print = true; + + struct casereader *input; + struct ccase *c; + size_t i; bool ok; - arc.src_vars = NULL; - arc.dst_names = NULL; - arc.dst_vars = NULL; - arc.src_values = NULL; - arc.var_cnt = 0; - arc.src_values_pool = NULL; - arc.direction = ASCENDING; - arc.print = 0; - dst_cnt = 0; - - lex_match_id ("VARIABLES"); - lex_match ('='); - if (!parse_variables (dataset_dict (ds), &arc.src_vars, &arc.var_cnt, - PV_NO_DUPLICATE)) - goto lossage; - if (!lex_force_match_id ("INTO")) - goto lossage; - lex_match ('='); - if (!parse_DATA_LIST_vars (&arc.dst_names, &dst_cnt, PV_NONE)) - goto lossage; - if (dst_cnt != arc.var_cnt) + /* Create procedure. */ + arc = xzalloc (sizeof *arc); + + /* Parse variable lists. */ + lex_match_id (lexer, "VARIABLES"); + lex_match (lexer, '='); + if (!parse_variables_const (lexer, dict, &src_vars, &n_srcs, + PV_NO_DUPLICATE)) + goto error; + if (!lex_force_match_id (lexer, "INTO")) + goto error; + lex_match (lexer, '='); + if (!parse_DATA_LIST_vars (lexer, &dst_names, &n_dsts, PV_NO_DUPLICATE)) + goto error; + if (n_dsts != n_srcs) { - size_t i; - - msg (SE, _("Source variable count (%u) does not match " - "target variable count (%u)."), - (unsigned) arc.var_cnt, (unsigned) dst_cnt); + msg (SE, _("Source variable count (%zu) does not match " + "target variable count (%zu)."), + n_srcs, n_dsts); - for (i = 0; i < dst_cnt; i++) - free (arc.dst_names[i]); - free (arc.dst_names); - arc.dst_names = NULL; - - goto lossage; + goto error; } - while (lex_match ('/')) - if (lex_match_id ("DESCENDING")) - arc.direction = DESCENDING; - else if (lex_match_id ("PRINT")) - arc.print = 1; - if (token != '.') + for (i = 0; i < n_dsts; i++) { - lex_error (_("expecting end of command")); - goto lossage; + const char *name = dst_names[i]; + + if (dict_lookup_var (dict, name) != NULL) + { + msg (SE, _("Target variable %s duplicates existing variable %s."), + name, name); + goto error; + } } - for (i = 0; i < arc.var_cnt; i++) + /* Parse options. */ + while (lex_match (lexer, '/')) { - int j; - - if (dict_lookup_var (dataset_dict (ds), arc.dst_names[i]) != NULL) + if (lex_match_id (lexer, "DESCENDING")) + direction = DESCENDING; + else if (lex_match_id (lexer, "PRINT")) + print = true; + else if (lex_match_id (lexer, "GROUP")) { - msg (SE, _("Target variable %s duplicates existing variable %s."), - arc.dst_names[i], arc.dst_names[i]); - goto lossage; + arc->global_items = xmalloc (sizeof (*arc->global_items)); + hmap_init (arc->global_items); } - for (j = 0; j < i; j++) - if (!strcasecmp (arc.dst_names[i], arc.dst_names[j])) - { - msg (SE, _("Duplicate variable name %s among target variables."), - arc.dst_names[i]); - goto lossage; - } } - arc.src_values_pool = pool_create (); - arc.dst_vars = xnmalloc (arc.var_cnt, sizeof *arc.dst_vars); - arc.src_values = xnmalloc (arc.var_cnt, sizeof *arc.src_values); - for (i = 0; i < dst_cnt; i++) - if (arc.src_vars[i]->type == ALPHA) - arc.src_values[i] = hsh_create (10, compare_alpha_value, - hash_alpha_value, NULL, arc.src_vars[i]); - else - arc.src_values[i] = hsh_create (10, compare_numeric_value, - hash_numeric_value, NULL, NULL); - - ok = procedure (ds, autorecode_proc_func, &arc); - - for (i = 0; i < arc.var_cnt; i++) - arc.dst_vars[i] = dict_create_var_assert (dataset_dict (ds), - arc.dst_names[i], 0); - - recode (ds, &arc); - arc_free (&arc); - return ok ? CMD_SUCCESS : CMD_CASCADING_FAILURE; - -lossage: - arc_free (&arc); - return CMD_CASCADING_FAILURE; -} - -static void -arc_free (struct autorecode_pgm *arc) -{ - free (arc->src_vars); - if (arc->dst_names != NULL) + if (lex_token (lexer) != '.') { - size_t i; - - for (i = 0; i < arc->var_cnt; i++) - free (arc->dst_names[i]); - free (arc->dst_names); + lex_error (lexer, _("expecting end of command")); + goto error; } - free (arc->dst_vars); - if (arc->src_values != NULL) + + arc->specs = xmalloc (n_dsts * sizeof *arc->specs); + arc->n_specs = n_dsts; + + for (i = 0; i < n_dsts; i++) { - size_t i; + struct arc_spec *spec = &arc->specs[i]; - for (i = 0; i < arc->var_cnt; i++) - hsh_destroy (arc->src_values[i]); - free (arc->src_values); + spec->src = src_vars[i]; + if (arc->global_items) + { + spec->items = arc->global_items; + } + else + { + spec->items = xmalloc (sizeof (*spec->items)); + hmap_init (spec->items); + } } - pool_destroy (arc->src_values_pool); -} - -/* AUTORECODE transformation. */ -static void -recode (struct dataset *ds, const struct autorecode_pgm *arc) -{ - struct autorecode_trns *trns; - size_t i; - - trns = pool_create_container (struct autorecode_trns, pool); - trns->specs = pool_nalloc (trns->pool, arc->var_cnt, sizeof *trns->specs); - trns->spec_cnt = arc->var_cnt; - for (i = 0; i < arc->var_cnt; i++) + /* Execute procedure. */ + input = proc_open (ds); + for (; (c = casereader_read (input)) != NULL; case_unref (c)) + for (i = 0; i < arc->n_specs; i++) + { + struct arc_spec *spec = &arc->specs[i]; + int width = var_get_width (spec->src); + const union value *value = case_data (c, spec->src); + size_t hash = value_hash (value, width, 0); + struct arc_item *item; + + item = find_arc_item (spec, value, hash); + if (item == NULL) + { + item = xmalloc (sizeof *item); + item->width = width; + value_clone (&item->from, value, width); + hmap_insert (spec->items, &item->hmap_node, hash); + } + } + ok = casereader_destroy (input); + ok = proc_commit (ds) && ok; + + /* Create transformation. */ + for (i = 0; i < arc->n_specs; i++) { - struct arc_spec *spec = &trns->specs[i]; - void *const *p = hsh_sort (arc->src_values[i]); - int count = hsh_count (arc->src_values[i]); - int j; + struct arc_spec *spec = &arc->specs[i]; + struct arc_item **items; + struct arc_item *item; + size_t n_items; + size_t j; - spec->src = arc->src_vars[i]; - spec->dest = arc->dst_vars[i]; + /* Create destination variable. */ + spec->dst = dict_create_var_assert (dict, dst_names[i], 0); - if (arc->src_vars[i]->type == ALPHA) - spec->items = hsh_create (2 * count, compare_alpha_value, - hash_alpha_value, NULL, arc->src_vars[i]); - else - spec->items = hsh_create (2 * count, compare_numeric_value, - hash_numeric_value, NULL, NULL); + /* Create array of pointers to items. */ + n_items = hmap_count (spec->items); + items = xmalloc (n_items * sizeof *items); + j = 0; + HMAP_FOR_EACH (item, struct arc_item, hmap_node, spec->items) + items[j++] = item; + + assert (j == n_items); + + /* Sort array by value. */ + sort (items, n_items, sizeof *items, compare_arc_items, NULL); - for (j = 0; *p; p++, j++) + /* Assign recoded values in sorted order. */ + for (j = 0; j < n_items; j++) { - struct arc_item *item = pool_alloc (trns->pool, sizeof *item); - union arc_value *vp = *p; - - if (arc->src_vars[i]->type == NUMERIC) - item->from.f = vp->f; - else - item->from.c = pool_clone (trns->pool, vp->c, - arc->src_vars[i]->width); - item->to = arc->direction == ASCENDING ? j + 1 : count - j; - hsh_force_insert (spec->items, item); + const union value *from = &items[j]->from; + size_t len; + char *recoded_value = NULL; + char *c; + const int src_width = items[j]->width; + union value to_val; + value_init (&to_val, 0); + + items[j]->to = direction == ASCENDING ? j + 1 : n_items - j; + + to_val.f = items[j]->to; + + /* Add value labels to the destination variable which indicate + the source value from whence the new value comes. */ + if (src_width > 0) + { + const char *str = (const char *) value_str (from, src_width); + + recoded_value = recode_string (UTF8, dict_get_encoding (dict), str, src_width); + } + else + recoded_value = asnprintf (NULL, &len, "%g", from->f); + + /* Remove trailing whitespace */ + for (c = recoded_value; *c != '\0'; c++) + if ( *c == ' ') + { + *c = '\0'; + break; + } + + var_add_value_label (spec->dst, &to_val, recoded_value); + value_destroy (&to_val, 0); + free (recoded_value); } + + /* Free array. */ + free (items); } - add_transformation (ds, - autorecode_trns_proc, autorecode_trns_free, trns); + add_transformation (ds, autorecode_trns_proc, autorecode_trns_free, arc); + + return ok ? CMD_SUCCESS : CMD_CASCADING_FAILURE; + +error: + for (i = 0; i < n_dsts; i++) + free (dst_names[i]); + free (dst_names); + free (src_vars); + arc_free (arc); + return CMD_CASCADING_FAILURE; } -/* Executes an AUTORECODE transformation. */ -static int -autorecode_trns_proc (void *trns_, struct ccase *c, casenumber case_idx UNUSED) +static void +arc_free (struct autorecode_pgm *arc) { - struct autorecode_trns *trns = trns_; - size_t i; - - for (i = 0; i < trns->spec_cnt; i++) + if (arc != NULL) { - struct arc_spec *spec = &trns->specs[i]; - struct arc_item *item; - union arc_value v; + size_t i; + + for (i = 0; i < arc->n_specs; i++) + { + struct arc_spec *spec = &arc->specs[i]; + int width = var_get_width (spec->src); + struct arc_item *item, *next; + + HMAP_FOR_EACH_SAFE (item, next, struct arc_item, hmap_node, + spec->items) + { + value_destroy (&item->from, width); + hmap_delete (spec->items, &item->hmap_node); + free (item); + } + } - if (spec->src->type == NUMERIC) - v.f = case_num (c, spec->src->fv); + if (arc->global_items) + { + free (arc->global_items); + } else - v.c = (char *) case_str (c, spec->src->fv); - item = hsh_force_find (spec->items, &v); + { + for (i = 0; i < arc->n_specs; i++) + { + struct arc_spec *spec = &arc->specs[i]; + if (spec->items) + { + hmap_destroy (spec->items); + free (spec->items); + } + } + } - case_data_rw (c, spec->dest->fv)->f = item->to; + free (arc->specs); + free (arc); } - return TRNS_CONTINUE; } -/* Frees an AUTORECODE transformation. */ -static bool -autorecode_trns_free (void *trns_) +static struct arc_item * +find_arc_item (const struct arc_spec *spec, const union value *value, + size_t hash) { - struct autorecode_trns *trns = trns_; - size_t i; + struct arc_item *item; - for (i = 0; i < trns->spec_cnt; i++) - hsh_destroy (trns->specs[i].items); - pool_destroy (trns->pool); - return true; + HMAP_FOR_EACH_WITH_HASH (item, struct arc_item, hmap_node, hash, spec->items) + if (value_equal (value, &item->from, var_get_width (spec->src))) + return item; + return NULL; } - -/* AUTORECODE procedure. */ static int -compare_alpha_value (const void *a_, const void *b_, void *v_) +compare_arc_items (const void *a_, const void *b_, const void *aux UNUSED) { - const union arc_value *a = a_; - const union arc_value *b = b_; - const struct variable *v = v_; + const struct arc_item *const *a = a_; + const struct arc_item *const *b = b_; + int width_a = (*a)->width; + int width_b = (*b)->width; - return memcmp (a->c, b->c, v->width); -} + if ( width_a == width_b) + return value_compare_3way (&(*a)->from, &(*b)->from, width_a); -static unsigned -hash_alpha_value (const void *a_, void *v_) -{ - const union arc_value *a = a_; - const struct variable *v = v_; - - return hsh_hash_bytes (a->c, v->width); + if ( width_a == 0 && width_b != 0) + return -1; + + if ( width_b == 0 && width_a != 0) + return +1; + + return buf_compare_rpad ((const char *) value_str (&(*a)->from, width_a), width_a, + (const char *) value_str (&(*b)->from, width_b), width_b); } static int -compare_numeric_value (const void *a_, const void *b_, void *foo UNUSED) +autorecode_trns_proc (void *arc_, struct ccase **c, + casenumber case_idx UNUSED) { - const union arc_value *a = a_; - const union arc_value *b = b_; + struct autorecode_pgm *arc = arc_; + size_t i; - return a->f < b->f ? -1 : a->f > b->f; -} + *c = case_unshare (*c); + for (i = 0; i < arc->n_specs; i++) + { + const struct arc_spec *spec = &arc->specs[i]; + int width = var_get_width (spec->src); + const union value *value = case_data (*c, spec->src); + struct arc_item *item; -static unsigned -hash_numeric_value (const void *a_, void *foo UNUSED) -{ - const union arc_value *a = a_; + item = find_arc_item (spec, value, value_hash (value, width, 0)); + case_data_rw (*c, spec->dst)->f = item ? item->to : SYSMIS; + } - return hsh_hash_double (a->f); + return TRNS_CONTINUE; } static bool -autorecode_proc_func (const struct ccase *c, void *arc_, const struct dataset *ds UNUSED) +autorecode_trns_free (void *arc_) { struct autorecode_pgm *arc = arc_; - size_t i; - - for (i = 0; i < arc->var_cnt; i++) - { - union arc_value v, *vp, **vpp; - if (arc->src_vars[i]->type == NUMERIC) - v.f = case_num (c, arc->src_vars[i]->fv); - else - v.c = (char *) case_str (c, arc->src_vars[i]->fv); - - vpp = (union arc_value **) hsh_probe (arc->src_values[i], &v); - if (*vpp == NULL) - { - vp = pool_alloc (arc->src_values_pool, sizeof *vp); - if (arc->src_vars[i]->type == NUMERIC) - vp->f = v.f; - else - vp->c = pool_clone (arc->src_values_pool, - v.c, arc->src_vars[i]->width); - *vpp = vp; - } - } + arc_free (arc); return true; }