src/data/case-ordering.c

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