src/data/case-ordering.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18
  19 #include <data/case-ordering.h>
  20
  21 #include <assert.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include <data/dictionary.h>
  26 #include <data/variable.h>
  27
  28 #include "xalloc.h"
  29
  30 /* One key used for sorting. */
  31 struct sort_key
  32   {
  33     const struct variable *var;       /* Variable. */
  34     enum sort_direction dir;    /* Sort direction. */
  35   };
  36
  37 /* A set of criteria for ordering cases. */
  38 struct case_ordering
  39   {
  40     size_t value_cnt;           /* Number of `union value's per case. */
  41
  42     /* Sort keys. */
  43     struct sort_key *keys;
  44     size_t key_cnt;
  45   };
  46
  47 /* Creates and returns a new case ordering for comparing cases
  48    that represent dictionary DICT.  The case ordering initially
  49    contains no variables, so that all cases will compare as
  50    equal. */
  51 struct case_ordering *
  52 case_ordering_create (const struct dictionary *dict)
  53 {
  54   struct case_ordering *co = xmalloc (sizeof *co);
  55   co->value_cnt = dict_get_next_value_idx (dict);
  56   co->keys = NULL;
  57   co->key_cnt = 0;
  58   return co;
  59 }
  60
  61 /* Creates and returns a clone of case ordering ORIG. */
  62 struct case_ordering *
  63 case_ordering_clone (const struct case_ordering *orig)
  64 {
  65   struct case_ordering *co = xmalloc (sizeof *co);
  66   co->value_cnt = orig->value_cnt;
  67   co->keys = xmemdup (orig->keys, orig->key_cnt * sizeof *orig->keys);
  68   co->key_cnt = orig->key_cnt;
  69   return co;
  70 }
  71
  72 /* Destroys case ordering CO. */
  73 void
  74 case_ordering_destroy (struct case_ordering *co)
  75 {
  76   if (co != NULL)
  77     {
  78       free (co->keys);
  79       free (co);
  80     }
  81 }
  82
  83 /* Returns the number of `union value's in the cases that case
  84    ordering CO compares (taken from the dictionary used to
  85    construct it). */
  86 size_t
  87 case_ordering_get_value_cnt (const struct case_ordering *co)
  88 {
  89   return co->value_cnt;
  90 }
  91
  92 /* Compares cases A and B given case ordering CO and returns a
  93    strcmp()-type result. */
  94 int
  95 case_ordering_compare_cases (const struct ccase *a, const struct ccase *b,
  96                              const struct case_ordering *co)
  97 {
  98   size_t i;
  99
 100   for (i = 0; i < co->key_cnt; i++)
 101     {
 102       const struct sort_key *key = &co->keys[i];
 103       int width = var_get_width (key->var);
 104       int cmp;
 105
 106       if (width == 0)
 107         {
 108           double af = case_num (a, key->var);
 109           double bf = case_num (b, key->var);
 110           if (af == bf)
 111             continue;
 112           cmp = af > bf ? 1 : -1;
 113         }
 114       else
 115         {
 116           const char *as = case_str (a, key->var);
 117           const char *bs = case_str (b, key->var);
 118           cmp = memcmp (as, bs, width);
 119           if (cmp == 0)
 120             continue;
 121         }
 122
 123       return key->dir == SRT_ASCEND ? cmp : -cmp;
 124     }
 125   return 0;
 126 }
 127
 128 /* Adds VAR to case ordering CO as an additional sort key in sort
 129    direction DIR.  Returns true if successful, false if VAR was
 130    already part of the ordering for CO. */
 131 bool
 132 case_ordering_add_var (struct case_ordering *co,
 133                        const struct variable *var, enum sort_direction dir)
 134 {
 135   struct sort_key *key;
 136   size_t i;
 137
 138   for (i = 0; i < co->key_cnt; i++)
 139     if (var_get_case_index (co->keys[i].var) == var_get_case_index (var))
 140       return false;
 141
 142   co->keys = xnrealloc (co->keys, co->key_cnt + 1, sizeof *co->keys);
 143   key = &co->keys[co->key_cnt++];
 144   key->var = var;
 145   key->dir = dir;
 146   return true;
 147 }
 148
 149 /* Returns the number of variables used for ordering within
 150    CO. */
 151 size_t
 152 case_ordering_get_var_cnt (const struct case_ordering *co)
 153 {
 154   return co->key_cnt;
 155 }
 156
 157 /* Returns sort variable IDX within CO.  An IDX of 0 returns the
 158    primary sort key (the one added first), an IDX of 1 returns
 159    the secondary sort key, and so on.  IDX must be less than the
 160    number of sort variables. */
 161 const struct variable *
 162 case_ordering_get_var (const struct case_ordering *co, size_t idx)
 163 {
 164   assert (idx < co->key_cnt);
 165   return co->keys[idx].var;
 166 }
 167
 168 /* Returns the sort direction for sort variable IDX within CO. */
 169 enum sort_direction
 170 case_ordering_get_direction (const struct case_ordering *co, size_t idx)
 171 {
 172   assert (idx < co->key_cnt);
 173   return co->keys[idx].dir;
 174 }
 175
 176 /* Stores an array listing all of the variables used for sorting
 177    within CO into *VARS and the number of variables into
 178    *VAR_CNT.  The caller is responsible for freeing *VARS when it
 179    is no longer needed. */
 180 void
 181 case_ordering_get_vars (const struct case_ordering *co,
 182                         const struct variable ***vars, size_t *var_cnt)
 183 {
 184   size_t i;
 185
 186   *var_cnt = co->key_cnt;
 187   *vars = xnmalloc (*var_cnt, sizeof **vars);
 188   for (i = 0; i < co->key_cnt; i++)
 189     (*vars)[i] = co->keys[i].var;
 190 }
 191