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     /* Sort keys. */
  41     struct sort_key *keys;
  42     size_t key_cnt;
  43   };
  44
  45 /* Creates and returns a new case ordering for comparing cases
  46    that represent dictionary DICT.  The case ordering initially
  47    contains no variables, so that all cases will compare as
  48    equal. */
  49 struct case_ordering *
  50 case_ordering_create (void)
  51 {
  52   struct case_ordering *co = xmalloc (sizeof *co);
  53   co->keys = NULL;
  54   co->key_cnt = 0;
  55   return co;
  56 }
  57
  58 /* Creates and returns a clone of case ordering ORIG. */
  59 struct case_ordering *
  60 case_ordering_clone (const struct case_ordering *orig)
  61 {
  62   struct case_ordering *co = xmalloc (sizeof *co);
  63   co->keys = xmemdup (orig->keys, orig->key_cnt * sizeof *orig->keys);
  64   co->key_cnt = orig->key_cnt;
  65   return co;
  66 }
  67
  68 /* Destroys case ordering CO. */
  69 void
  70 case_ordering_destroy (struct case_ordering *co)
  71 {
  72   if (co != NULL)
  73     {
  74       free (co->keys);
  75       free (co);
  76     }
  77 }
  78
  79 /* Compares cases A and B given case ordering CO and returns a
  80    strcmp()-type result. */
  81 int
  82 case_ordering_compare_cases (const struct ccase *a, const struct ccase *b,
  83                              const struct case_ordering *co)
  84 {
  85   size_t i;
  86
  87   for (i = 0; i < co->key_cnt; i++)
  88     {
  89       const struct sort_key *key = &co->keys[i];
  90       int width = var_get_width (key->var);
  91       int cmp;
  92
  93       if (width == 0)
  94         {
  95           double af = case_num (a, key->var);
  96           double bf = case_num (b, key->var);
  97           if (af == bf)
  98             continue;
  99           cmp = af > bf ? 1 : -1;
 100         }
 101       else
 102         {
 103           const char *as = case_str (a, key->var);
 104           const char *bs = case_str (b, key->var);
 105           cmp = memcmp (as, bs, width);
 106           if (cmp == 0)
 107             continue;
 108         }
 109
 110       return key->dir == SRT_ASCEND ? cmp : -cmp;
 111     }
 112   return 0;
 113 }
 114
 115 /* Adds VAR to case ordering CO as an additional sort key in sort
 116    direction DIR.  Returns true if successful, false if VAR was
 117    already part of the ordering for CO. */
 118 bool
 119 case_ordering_add_var (struct case_ordering *co,
 120                        const struct variable *var, enum sort_direction dir)
 121 {
 122   struct sort_key *key;
 123   size_t i;
 124
 125   for (i = 0; i < co->key_cnt; i++)
 126     if (var_get_case_index (co->keys[i].var) == var_get_case_index (var))
 127       return false;
 128
 129   co->keys = xnrealloc (co->keys, co->key_cnt + 1, sizeof *co->keys);
 130   key = &co->keys[co->key_cnt++];
 131   key->var = var;
 132   key->dir = dir;
 133   return true;
 134 }
 135
 136 /* Returns the number of variables used for ordering within
 137    CO. */
 138 size_t
 139 case_ordering_get_var_cnt (const struct case_ordering *co)
 140 {
 141   return co->key_cnt;
 142 }
 143
 144 /* Returns sort variable IDX within CO.  An IDX of 0 returns the
 145    primary sort key (the one added first), an IDX of 1 returns
 146    the secondary sort key, and so on.  IDX must be less than the
 147    number of sort variables. */
 148 const struct variable *
 149 case_ordering_get_var (const struct case_ordering *co, size_t idx)
 150 {
 151   assert (idx < co->key_cnt);
 152   return co->keys[idx].var;
 153 }
 154
 155 /* Returns the sort direction for sort variable IDX within CO. */
 156 enum sort_direction
 157 case_ordering_get_direction (const struct case_ordering *co, size_t idx)
 158 {
 159   assert (idx < co->key_cnt);
 160   return co->keys[idx].dir;
 161 }
 162
 163 /* Stores an array listing all of the variables used for sorting
 164    within CO into *VARS and the number of variables into
 165    *VAR_CNT.  The caller is responsible for freeing *VARS when it
 166    is no longer needed. */
 167 void
 168 case_ordering_get_vars (const struct case_ordering *co,
 169                         const struct variable ***vars, size_t *var_cnt)
 170 {
 171   size_t i;
 172
 173   *var_cnt = co->key_cnt;
 174   *vars = xnmalloc (*var_cnt, sizeof **vars);
 175   for (i = 0; i < co->key_cnt; i++)
 176     (*vars)[i] = co->keys[i].var;
 177 }
 178