X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flanguage%2Fstats%2Frank.q;h=c225370e459269cc572430f87e533f7a591662c4;hb=2cf38ce51a9f34961d68a75e0b312a591b5c9abf;hp=3f1dd3a9e92c6eb7fcb159eff15846e4cb7c16b3;hpb=48386ee68a5283653435d05a9ea4e449710fd370;p=pspp-builds.git diff --git a/src/language/stats/rank.q b/src/language/stats/rank.q index 3f1dd3a9..c225370e 100644 --- a/src/language/stats/rank.q +++ b/src/language/stats/rank.q @@ -1,44 +1,44 @@ -/* PSPP - RANK. -*-c-*- -Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. +/* PSPP - a program for statistical analysis. + Copyright (C) 2005, 2006, 2007, 2009 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. */ + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ #include -#include "sort-criteria.h" +#include +#include +#include +#include +#include +#include #include #include #include #include +#include +#include #include -#include -#include -#include -#include #include #include -#include #include +#include #include -#include #include +#include #include -#include #include "gettext.h" #define _(msgid) gettext (msgid) @@ -152,7 +152,7 @@ static enum mv_class exclude_values; static struct rank_spec *rank_specs; static size_t n_rank_specs; -static struct sort_criteria *sc; +static struct subcase sc; static const struct variable **group_vars; static size_t n_group_vars; @@ -165,14 +165,14 @@ static int k_ntiles; static struct cmd_rank cmd; -static struct casefile *rank_sorted_casefile (struct casefile *cf, - const struct sort_criteria *, - const struct dictionary *, - const struct rank_spec *rs, - int n_rank_specs, - int idx, - const struct missing_values *miss - ); +static void rank_sorted_file (struct casereader *, + struct casewriter *, + const struct dictionary *, + const struct rank_spec *rs, + int n_rank_specs, + int idx, + const struct variable *rank_var); + static const char * fraction_name(void) { @@ -233,68 +233,61 @@ create_var_label (struct variable *dest_var, static bool -rank_cmd (struct dataset *ds, const struct sort_criteria *sc, +rank_cmd (struct dataset *ds, const struct subcase *sc, const struct rank_spec *rank_specs, int n_rank_specs) { - struct sort_criteria criteria; - bool result = true; + struct dictionary *d = dataset_dict (ds); + bool ok = true; int i; - const int n_splits = dict_get_split_cnt (dataset_dict (ds)); - criteria.crit_cnt = n_splits + n_group_vars + 1; - criteria.crits = xnmalloc (criteria.crit_cnt, sizeof *criteria.crits); - for (i = 0; i < n_splits ; i++) - { - const struct variable *v = dict_get_split_vars (dataset_dict (ds))[i]; - criteria.crits[i].fv = var_get_case_index (v); - criteria.crits[i].width = var_get_width (v); - criteria.crits[i].dir = SRT_ASCEND; - } - for (i = 0; i < n_group_vars; i++) - { - criteria.crits[i + n_splits].fv = var_get_case_index (group_vars[i]); - criteria.crits[i + n_splits].width = var_get_width (group_vars[i]); - criteria.crits[i + n_splits].dir = SRT_ASCEND; - } - for (i = 0 ; i < sc->crit_cnt ; ++i ) + for (i = 0 ; i < subcase_get_n_fields (sc) ; ++i ) { - struct casefile *out ; - struct casefile *cf ; - struct casereader *reader ; - struct casefile *sorted_cf ; - - /* Obtain active file in CF. */ - if (!procedure (ds, NULL, NULL)) - goto error; - - cf = proc_capture_output (ds); - - /* Sort CF into SORTED_CF. */ - reader = casefile_get_destructive_reader (cf) ; - criteria.crits[criteria.crit_cnt - 1] = sc->crits[i]; - assert ( sc->crits[i].fv == var_get_case_index (src_vars[i]) ); - sorted_cf = sort_execute (reader, &criteria, NULL); - casefile_destroy (cf); - - out = rank_sorted_casefile (sorted_cf, &criteria, - dataset_dict (ds), - rank_specs, n_rank_specs, - i, var_get_missing_values (src_vars[i])); - if ( NULL == out ) - { - result = false ; - continue ; - } + /* Rank variable at index I in SC. */ + struct casegrouper *split_grouper; + struct casereader *split_group; + struct casewriter *output; - proc_set_source (ds, storage_source_create (out)); - } + proc_discard_output (ds); + split_grouper = casegrouper_create_splits (proc_open (ds), d); + output = autopaging_writer_create (dict_get_proto (d)); - free (criteria.crits); - return result ; + while (casegrouper_get_next_group (split_grouper, &split_group)) + { + struct subcase ordering; + struct casereader *ordered; + struct casegrouper *by_grouper; + struct casereader *by_group; + + /* Sort this split group by the BY variables as primary + keys and the rank variable as secondary key. */ + subcase_init_vars (&ordering, group_vars, n_group_vars); + subcase_add_var (&ordering, src_vars[i], + subcase_get_direction (sc, i)); + ordered = sort_execute (split_group, &ordering); + subcase_destroy (&ordering); + + /* Rank the rank variable within this split group. */ + by_grouper = casegrouper_create_vars (ordered, + group_vars, n_group_vars); + while (casegrouper_get_next_group (by_grouper, &by_group)) + { + /* Rank the rank variable within this BY group + within the split group. */ -error: - free (criteria.crits); - return false ; + rank_sorted_file (by_group, output, d, rank_specs, n_rank_specs, + i, src_vars[i]); + } + ok = casegrouper_destroy (by_grouper) && ok; + } + ok = casegrouper_destroy (split_grouper); + ok = proc_commit (ds) && ok; + ok = (proc_set_active_file_data (ds, casewriter_make_reader (output)) + && ok); + if (!ok) + break; + } + + return ok; } /* Hardly a rank function !! */ @@ -311,6 +304,7 @@ rank_rank (double c, double cc, double cc_1, int i, double w UNUSED) { double rank; + if ( c >= 1.0 ) { switch (cmd.ties) @@ -471,199 +465,80 @@ rank_savage (double c, double cc, double cc_1, NOT_REACHED(); } - -/* Rank the casefile belonging to CR, starting from the current - postition of CR continuing up to and including the ENDth case. - - RS points to an array containing the rank specifications to - use. N_RANK_SPECS is the number of elements of RS. - - - DEST_VAR_INDEX is the index into the rank_spec destvar element - to be used for this ranking. - - Prerequisites: 1. The casefile must be sorted according to CRITERION. - 2. W is the sum of the non-missing caseweights for this - range of the casefile. -*/ static void -rank_cases (struct casereader *cr, - unsigned long end, - const struct dictionary *dict, - const struct sort_criterion *criterion, - const struct missing_values *mv, - double w, - const struct rank_spec *rs, - int n_rank_specs, - int dest_var_index, - struct casefile *dest) +rank_sorted_file (struct casereader *input, + struct casewriter *output, + const struct dictionary *dict, + const struct rank_spec *rs, + int n_rank_specs, + int dest_idx, + const struct variable *rank_var) { - bool warn = true; + struct casereader *pass1, *pass2, *pass2_1; + struct casegrouper *tie_grouper; + struct ccase *c; + double w = 0.0; double cc = 0.0; - double cc_1; - int iter = 1; + int tie_group = 1; - const int fv = criterion->fv; - const int width = criterion->width; - while (casereader_cnum (cr) < end) - { - struct casereader *lookahead; - const union value *this_value; - bool this_value_is_missing; - struct ccase this_case, lookahead_case; - double c; - int i; - size_t n = 0; + input = casereader_create_filter_missing (input, &rank_var, 1, + exclude_values, NULL, output); + input = casereader_create_filter_weight (input, dict, NULL, output); - if (!casereader_read_xfer (cr, &this_case)) - break; + casereader_split (input, &pass1, &pass2); - this_value = case_data_idx (&this_case, fv); - this_value_is_missing = mv_is_value_missing (mv, this_value, - exclude_values); - c = dict_get_case_weight (dict, &this_case, &warn); - - lookahead = casereader_clone (cr); - n = 0; - while (casereader_cnum (lookahead) < end - && casereader_read_xfer (lookahead, &lookahead_case)) - { - const union value *lookahead_value = case_data_idx (&lookahead_case, fv); - int diff = compare_values (this_value, lookahead_value, width); - - if (diff != 0) - { - /* Make sure the casefile was sorted */ - assert ( diff == ((criterion->dir == SRT_ASCEND) ? -1 :1)); - - case_destroy (&lookahead_case); - break; - } + /* Pass 1: Get total group weight. */ + for (; (c = casereader_read (pass1)) != NULL; case_unref (c)) + w += dict_get_case_weight (dict, c, NULL); + casereader_destroy (pass1); - c += dict_get_case_weight (dict, &lookahead_case, &warn); - case_destroy (&lookahead_case); - n++; - } - casereader_destroy (lookahead); - - cc_1 = cc; - if ( !this_value_is_missing ) - cc += c; - - do - { - for (i = 0; i < n_rank_specs; ++i) - { - const struct variable *dst_var = rs[i].destvars[dest_var_index]; - - if (this_value_is_missing) - case_data_rw (&this_case, dst_var)->f = SYSMIS; - else - case_data_rw (&this_case, dst_var)->f = - rank_func[rs[i].rfunc](c, cc, cc_1, iter, w); - } - casefile_append_xfer (dest, &this_case); - } - while (n-- > 0 && casereader_read_xfer (cr, &this_case)); - - if ( !this_value_is_missing ) - iter++; - } - - /* If this isn't true, then all the results will be wrong */ - assert ( w == cc ); -} - -static bool -same_group (const struct ccase *a, const struct ccase *b, - const struct sort_criteria *crit) -{ - size_t i; - - for (i = 0; i < crit->crit_cnt - 1; i++) + /* Pass 2: Do ranking. */ + tie_grouper = casegrouper_create_vars (pass2, &rank_var, 1); + while (casegrouper_get_next_group (tie_grouper, &pass2_1)) { - struct sort_criterion *c = &crit->crits[i]; - if (compare_values (case_data_idx (a, c->fv), - case_data_idx (b, c->fv), c->width) != 0) - return false; - } - - return true; -} - -static struct casefile * -rank_sorted_casefile (struct casefile *cf, - const struct sort_criteria *crit, - const struct dictionary *dict, - const struct rank_spec *rs, - int n_rank_specs, - int dest_idx, - const struct missing_values *mv) -{ - struct casefile *dest = fastfile_create (casefile_get_value_cnt (cf)); - struct casereader *lookahead = casefile_get_reader (cf, NULL); - struct casereader *pos = casereader_clone (lookahead); - struct ccase group_case; - bool warn = true; - - struct sort_criterion *ultimate_crit = &crit->crits[crit->crit_cnt - 1]; + struct casereader *pass2_2; + double cc_1 = cc; + double tw = 0.0; + int i; - if (casereader_read (lookahead, &group_case)) - { - struct ccase this_case; - const union value *this_value ; - double w = 0.0; - this_value = case_data_idx( &group_case, ultimate_crit->fv); + pass2_2 = casereader_clone (pass2_1); + taint_propagate (casereader_get_taint (pass2_2), + casewriter_get_taint (output)); - if ( !mv_is_value_missing (mv, this_value, exclude_values) ) - w = dict_get_case_weight (dict, &group_case, &warn); + /* Pass 2.1: Sum up weight for tied cases. */ + for (; (c = casereader_read (pass2_1)) != NULL; case_unref (c)) + tw += dict_get_case_weight (dict, c, NULL); + cc += tw; + casereader_destroy (pass2_1); - while (casereader_read (lookahead, &this_case)) + /* Pass 2.2: Rank tied cases. */ + while ((c = casereader_read (pass2_2)) != NULL) { - const union value *this_value = - case_data_idx(&this_case, ultimate_crit->fv); - double c = dict_get_case_weight (dict, &this_case, &warn); - if (!same_group (&group_case, &this_case, crit)) + c = case_unshare (c); + for (i = 0; i < n_rank_specs; ++i) { - rank_cases (pos, casereader_cnum (lookahead) - 1, - dict, - ultimate_crit, - mv, w, - rs, n_rank_specs, - dest_idx, dest); - - w = 0.0; - case_destroy (&group_case); - case_move (&group_case, &this_case); + const struct variable *dst_var = rs[i].destvars[dest_idx]; + double *dst_value = &case_data_rw (c, dst_var)->f; + *dst_value = rank_func[rs[i].rfunc] (tw, cc, cc_1, tie_group, w); } - if ( !mv_is_value_missing (mv, this_value, exclude_values) ) - w += c; - case_destroy (&this_case); + casewriter_write (output, c); } - case_destroy (&group_case); - rank_cases (pos, ULONG_MAX, dict, ultimate_crit, mv, w, - rs, n_rank_specs, dest_idx, dest); - } + casereader_destroy (pass2_2); - if (casefile_error (dest)) - { - casefile_destroy (dest); - dest = NULL; + tie_group++; } - - casefile_destroy (cf); - return dest; + casegrouper_destroy (tie_grouper); } - /* Transformation function to enumerate all the cases */ static int -create_resort_key (void *key_var_, struct ccase *cc, casenumber case_num) +create_resort_key (void *key_var_, struct ccase **cc, casenumber case_num) { struct variable *key_var = key_var_; - case_data_rw(cc, key_var)->f = case_num; + *cc = case_unshare (*cc); + case_data_rw (*cc, key_var)->f = case_num; return TRNS_CONTINUE; } @@ -749,8 +624,7 @@ rank_cleanup(void) rank_specs = NULL; n_rank_specs = 0; - sort_destroy_criteria (sc); - sc = NULL; + subcase_destroy (&sc); free (src_vars); src_vars = NULL; @@ -765,6 +639,7 @@ cmd_rank (struct lexer *lexer, struct dataset *ds) size_t i; n_rank_specs = 0; + subcase_init_empty (&sc); if ( !parse_rank (lexer, ds, &cmd, NULL) ) { rank_cleanup (); @@ -784,12 +659,12 @@ cmd_rank (struct lexer *lexer, struct dataset *ds) rank_specs = xmalloc (sizeof (*rank_specs)); rank_specs[0].rfunc = RANK; rank_specs[0].destvars = - xcalloc (sc->crit_cnt, sizeof (struct variable *)); + xcalloc (subcase_get_n_fields (&sc), sizeof (struct variable *)); n_rank_specs = 1; } - assert ( sc->crit_cnt == n_src_vars); + assert ( subcase_get_n_fields (&sc) == n_src_vars); /* Create variables for all rank destinations which haven't already been created with INTO. @@ -839,48 +714,44 @@ cmd_rank (struct lexer *lexer, struct dataset *ds) if ( rank_specs[i].rfunc == NORMAL || rank_specs[i].rfunc == PROPORTION ) - tab_output_text (TAT_PRINTF, - _("%s into %s(%s of %s using %s BY %s)"), - var_get_name (src_vars[v]), - var_get_name (rank_specs[i].destvars[v]), - function_name[rank_specs[i].rfunc], - var_get_name (src_vars[v]), - fraction_name(), - ds_cstr (&varlist) - ); + tab_output_text_format (0, + _("%s into %s(%s of %s using %s BY %s)"), + var_get_name (src_vars[v]), + var_get_name (rank_specs[i].destvars[v]), + function_name[rank_specs[i].rfunc], + var_get_name (src_vars[v]), + fraction_name(), + ds_cstr (&varlist)); else - tab_output_text (TAT_PRINTF, - _("%s into %s(%s of %s BY %s)"), - var_get_name (src_vars[v]), - var_get_name (rank_specs[i].destvars[v]), - function_name[rank_specs[i].rfunc], - var_get_name (src_vars[v]), - ds_cstr (&varlist) - ); + tab_output_text_format (0, + _("%s into %s(%s of %s BY %s)"), + var_get_name (src_vars[v]), + var_get_name (rank_specs[i].destvars[v]), + function_name[rank_specs[i].rfunc], + var_get_name (src_vars[v]), + ds_cstr (&varlist)); ds_destroy (&varlist); } else { if ( rank_specs[i].rfunc == NORMAL || rank_specs[i].rfunc == PROPORTION ) - tab_output_text (TAT_PRINTF, - _("%s into %s(%s of %s using %s)"), - var_get_name (src_vars[v]), - var_get_name (rank_specs[i].destvars[v]), - function_name[rank_specs[i].rfunc], - var_get_name (src_vars[v]), - fraction_name() - ); + tab_output_text_format (0, + _("%s into %s(%s of %s using %s)"), + var_get_name (src_vars[v]), + var_get_name (rank_specs[i].destvars[v]), + function_name[rank_specs[i].rfunc], + var_get_name (src_vars[v]), + fraction_name()); else - tab_output_text (TAT_PRINTF, - _("%s into %s(%s of %s)"), - var_get_name (src_vars[v]), - var_get_name (rank_specs[i].destvars[v]), - function_name[rank_specs[i].rfunc], - var_get_name (src_vars[v]) - ); + tab_output_text_format (0, + _("%s into %s(%s of %s)"), + var_get_name (src_vars[v]), + var_get_name (rank_specs[i].destvars[v]), + function_name[rank_specs[i].rfunc], + var_get_name (src_vars[v])); } } } @@ -897,24 +768,22 @@ cmd_rank (struct lexer *lexer, struct dataset *ds) add_transformation (ds, create_resort_key, 0, order); /* Do the ranking */ - result = rank_cmd (ds, sc, rank_specs, n_rank_specs); + result = rank_cmd (ds, &sc, rank_specs, n_rank_specs); - /* Put the active file back in its original order */ + /* Put the active file back in its original order. Delete + our sort key, which we don't need anymore. */ { - struct sort_criteria criteria; - struct sort_criterion restore_criterion ; - restore_criterion.fv = var_get_case_index (order); - restore_criterion.width = 0; - restore_criterion.dir = SRT_ASCEND; + struct casereader *sorted; - criteria.crits = &restore_criterion; - criteria.crit_cnt = 1; + /* FIXME: loses error conditions. */ - sort_active_file_in_place (ds, &criteria); - } + proc_discard_output (ds); + sorted = sort_execute_1var (proc_open (ds), order); + result = proc_commit (ds) && result; - /* ... and we don't need our sort key anymore. So delete it */ - dict_delete_var (dataset_dict (ds), order); + dict_delete_var (dataset_dict (ds), order); + result = proc_set_active_file_data (ds, sorted) && result; + } rank_cleanup(); @@ -928,16 +797,15 @@ cmd_rank (struct lexer *lexer, struct dataset *ds) static int rank_custom_variables (struct lexer *lexer, struct dataset *ds, struct cmd_rank *cmd UNUSED, void *aux UNUSED) { - static const int terminators[2] = {T_BY, 0}; - lex_match (lexer, '='); if ((lex_token (lexer) != T_ID || dict_lookup_var (dataset_dict (ds), lex_tokid (lexer)) == NULL) && lex_token (lexer) != T_ALL) return 2; - sc = sort_parse_criteria (lexer, dataset_dict (ds), - &src_vars, &n_src_vars, 0, terminators); + if (!parse_sort_criteria (lexer, dataset_dict (ds), &sc, &src_vars, NULL)) + return 0; + n_src_vars = subcase_get_n_fields (&sc); if ( lex_match (lexer, T_BY) ) { @@ -971,7 +839,7 @@ parse_rank_function (struct lexer *lexer, struct dictionary *dict, struct cmd_ra rank_specs[n_rank_specs - 1].destvars = NULL; rank_specs[n_rank_specs - 1].destvars = - xcalloc (sc->crit_cnt, sizeof (struct variable *)); + xcalloc (subcase_get_n_fields (&sc), sizeof (struct variable *)); if (lex_match_id (lexer, "INTO")) { @@ -985,7 +853,7 @@ parse_rank_function (struct lexer *lexer, struct dictionary *dict, struct cmd_ra msg(SE, _("Variable %s already exists."), lex_tokid (lexer)); return 0; } - if ( var_count >= sc->crit_cnt ) + if ( var_count >= subcase_get_n_fields (&sc) ) { msg(SE, _("Too many variables in INTO clause.")); return 0; @@ -1081,3 +949,9 @@ rank_custom_ntiles (struct lexer *lexer, struct dataset *ds, struct cmd_rank *cm return parse_rank_function (lexer, dict, cmd, NTILES); } + +/* + Local Variables: + mode: c + End: +*/