X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flanguage%2Fstats%2Frank.q;h=cb63949076bb4b03d50d009b0805762a3d250dae;hb=dc44e4b118592d1719d9b9ae23ce64a2861fb198;hp=f5be9e9a24405bb4351ea8676f52fa7bee033c22;hpb=4517b68e7248f22e7b7ed81f0d73179351a53047;p=pspp-builds.git diff --git a/src/language/stats/rank.q b/src/language/stats/rank.q index f5be9e9a..cb639490 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 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,12 +152,12 @@ 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 case_ordering *sc; -static struct variable **group_vars; +static const struct variable **group_vars; static size_t n_group_vars; -static struct variable **src_vars; +static const struct variable **src_vars; static size_t n_src_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,64 @@ 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 case_ordering *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++) - { - 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 < case_ordering_get_var_cnt (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_next_value_idx (d)); - free (criteria.crits); - return result ; + while (casegrouper_get_next_group (split_grouper, &split_group)) + { + struct case_ordering *ordering; + struct casereader *ordered; + struct casegrouper *by_grouper; + struct casereader *by_group; + int j; + + /* Sort this split group by the BY variables as primary + keys and the rank variable as secondary key. */ + ordering = case_ordering_create (); + for (j = 0; j < n_group_vars; j++) + case_ordering_add_var (ordering, group_vars[j], SRT_ASCEND); + case_ordering_add_var (ordering, + case_ordering_get_var (sc, i), + case_ordering_get_direction (sc, i)); + ordered = sort_execute (split_group, 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 +307,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,189 +468,71 @@ 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; - - const int fv = criterion->fv; - const int width = criterion->width; - - while (casereader_cnum (cr) < end) - { - struct casereader *lookahead; - const union value *this_value; - struct ccase this_case, lookahead_case; - double c; - int i; - size_t n = 0; - - if (!casereader_read_xfer (cr, &this_case)) - break; - - this_value = case_data_idx (&this_case, fv); - 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); + int tie_group = 1; - if (diff != 0) - { - /* Make sure the casefile was sorted */ - assert ( diff == ((criterion->dir == SRT_ASCEND) ? -1 :1)); - - case_destroy (&lookahead_case); - break; - } - - c += dict_get_case_weight (dict, &lookahead_case, &warn); - case_destroy (&lookahead_case); - n++; - } - casereader_destroy (lookahead); - - cc_1 = cc; - if ( !mv_is_value_missing (mv, this_value, exclude_values) ) - cc += c; - - do - { - for (i = 0; i < n_rank_specs; ++i) - { - const struct variable *dst_var = rs[i].destvars[dest_var_index]; - if ( mv_is_value_missing (mv, this_value, exclude_values) ) - 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 ( !mv_is_value_missing (mv, this_value, exclude_values) ) - iter++; - } + input = casereader_create_filter_missing (input, &rank_var, 1, + exclude_values, output); + input = casereader_create_filter_weight (input, dict, NULL, output); - /* If this isn't true, then all the results will be wrong */ - assert ( w == cc ); -} + casereader_split (input, &pass1, &pass2); -static bool -same_group (const struct ccase *a, const struct ccase *b, - const struct sort_criteria *crit) -{ - size_t i; + /* Pass 1: Get total group weight. */ + for (; casereader_read (pass1, &c); case_destroy (&c)) + w += dict_get_case_weight (dict, &c, NULL); + casereader_destroy (pass1); - 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 (; casereader_read (pass2_1, &c); case_destroy (&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 (casereader_read (pass2_2, &c)) { - 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)) + 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) @@ -746,7 +625,7 @@ rank_cleanup(void) rank_specs = NULL; n_rank_specs = 0; - sort_destroy_criteria (sc); + case_ordering_destroy (sc); sc = NULL; free (src_vars); @@ -781,12 +660,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 (case_ordering_get_var_cnt (sc), sizeof (struct variable *)); n_rank_specs = 1; } - assert ( sc->crit_cnt == n_src_vars); + assert ( case_ordering_get_var_cnt (sc) == n_src_vars); /* Create variables for all rank destinations which haven't already been created with INTO. @@ -896,23 +775,21 @@ cmd_rank (struct lexer *lexer, struct dataset *ds) /* Do the ranking */ 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; - - criteria.crits = &restore_criterion; - criteria.crit_cnt = 1; - - sort_active_file_in_place (ds, &criteria); + struct case_ordering *ordering = case_ordering_create (); + struct casereader *sorted; + case_ordering_add_var (ordering, order, SRT_ASCEND); + /* FIXME: loses error conditions. */ + proc_discard_output (ds); + sorted = sort_execute (proc_open (ds), ordering); + result = proc_commit (ds) && result; + + dict_delete_var (dataset_dict (ds), order); + result = proc_set_active_file_data (ds, sorted) && result; } - /* ... and we don't need our sort key anymore. So delete it */ - dict_delete_var (dataset_dict (ds), order); - rank_cleanup(); @@ -925,16 +802,16 @@ 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); + sc = parse_case_ordering (lexer, dataset_dict (ds), NULL); + if (sc == NULL) + return 0; + case_ordering_get_vars (sc, &src_vars, &n_src_vars); if ( lex_match (lexer, T_BY) ) { @@ -943,7 +820,7 @@ rank_custom_variables (struct lexer *lexer, struct dataset *ds, struct cmd_rank return 2; } - if (!parse_variables (lexer, dataset_dict (ds), + if (!parse_variables_const (lexer, dataset_dict (ds), &group_vars, &n_group_vars, PV_NO_DUPLICATE | PV_NO_SCRATCH) ) { @@ -968,7 +845,8 @@ 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 (case_ordering_get_var_cnt (sc), + sizeof (struct variable *)); if (lex_match_id (lexer, "INTO")) { @@ -982,7 +860,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 >= case_ordering_get_var_cnt (sc) ) { msg(SE, _("Too many variables in INTO clause.")); return 0; @@ -1078,3 +956,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: +*/