src/data/case-map.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 1997-9, 2000, 2006, 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-map.h>
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23
  24 #include <data/casereader.h>
  25 #include <data/casewriter.h>
  26 #include <data/dictionary.h>
  27 #include <data/variable.h>
  28 #include <data/case.h>
  29 #include <libpspp/assertion.h>
  30
  31 #include "xalloc.h"
  32
  33 /* A case map. */
  34 struct case_map
  35   {
  36     size_t value_cnt;   /* Number of values in map. */
  37     int *map;           /* For each destination index, the
  38                            corresponding source index. */
  39   };
  40
  41 static void translate_case (struct ccase *, struct ccase *, void *map_);
  42 static bool destroy_case_map (void *map_);
  43
  44 /* Creates and returns an empty map. */
  45 static struct case_map *
  46 create_case_map (size_t n)
  47 {
  48   struct case_map *map;
  49   size_t i;
  50
  51   map = xmalloc (sizeof *map);
  52   map->value_cnt = n;
  53   map->map = xnmalloc (n, sizeof *map->map);
  54   for (i = 0; i < map->value_cnt; i++)
  55     map->map[i] = -1;
  56
  57   return map;
  58 }
  59
  60 /* Inserts into MAP a mapping of the CNT values starting at FROM
  61    to the CNT values starting at TO. */
  62 static void
  63 insert_mapping (struct case_map *map, size_t from, size_t to, size_t cnt)
  64 {
  65   size_t i;
  66
  67   assert (to + cnt <= map->value_cnt);
  68   for (i = 0; i < cnt; i++)
  69     {
  70       assert (map->map[to + i] == -1);
  71       map->map[to + i] = from + i;
  72     }
  73 }
  74
  75 /* Destroys case map MAP. */
  76 void
  77 case_map_destroy (struct case_map *map)
  78 {
  79   if (map != NULL)
  80     {
  81       free (map->map);
  82       free (map);
  83     }
  84 }
  85
  86 /* Maps from SRC to DST, applying case map MAP. */
  87 void
  88 case_map_execute (const struct case_map *map,
  89                   const struct ccase *src, struct ccase *dst)
  90 {
  91   size_t dst_idx;
  92
  93   case_create (dst, map->value_cnt);
  94   for (dst_idx = 0; dst_idx < map->value_cnt; dst_idx++)
  95     {
  96       int src_idx = map->map[dst_idx];
  97       if (src_idx != -1)
  98         *case_data_rw_idx (dst, dst_idx) = *case_data_idx (src, src_idx);
  99     }
 100 }
 101
 102 /* Returns the number of `union value's in cases created by
 103    MAP. */
 104 size_t
 105 case_map_get_value_cnt (const struct case_map *map)
 106 {
 107   return map->value_cnt;
 108 }
 109
 110 /* Creates and returns a new casereader whose cases are produced
 111    by reading from SUBREADER and executing the actions of MAP.
 112    The casereader will have as many `union value's as MAP.  When
 113    the new casereader is destroyed, MAP will be destroyed too.
 114
 115    After this function is called, SUBREADER must not ever again
 116    be referenced directly.  It will be destroyed automatically
 117    when the returned casereader is destroyed. */
 118 struct casereader *
 119 case_map_create_input_translator (struct case_map *map,
 120                                   struct casereader *subreader)
 121 {
 122     return casereader_create_translator (subreader,
 123                                          case_map_get_value_cnt (map),
 124                                          translate_case,
 125                                          destroy_case_map,
 126                                          map);
 127 }
 128
 129 /* Creates and returns a new casewriter.  Cases written to the
 130    new casewriter will be passed through MAP and written to
 131    SUBWRITER.  The casewriter will have as many `union value's as
 132    MAP.  When the new casewriter is destroyed, MAP will be
 133    destroyed too.
 134
 135    After this function is called, SUBWRITER must not ever again
 136    be referenced directly.  It will be destroyed automatically
 137    when the returned casewriter is destroyed. */
 138 struct casewriter *
 139 case_map_create_output_translator (struct case_map *map,
 140                                    struct casewriter *subwriter)
 141 {
 142     return casewriter_create_translator (subwriter,
 143                                          case_map_get_value_cnt (map),
 144                                          translate_case,
 145                                          destroy_case_map,
 146                                          map);
 147 }
 148
 149 /* Casereader/casewriter translation callback. */
 150 static void
 151 translate_case (struct ccase *input, struct ccase *output, void *map_)
 152 {
 153   struct case_map *map = map_;
 154   case_map_execute (map, input, output);
 155   case_destroy (input);
 156 }
 157
 158 /* Casereader/casewriter destruction callback. */
 159 static bool
 160 destroy_case_map (void *map_)
 161 {
 162   struct case_map *map = map_;
 163   case_map_destroy (map);
 164   return true;
 165 }
 166
 167 /* Creates and returns a case_map that can be used to compact
 168    cases for dictionary D.
 169
 170    Compacting a case eliminates "holes" between values and after
 171    the last value.  (Holes are created by deleting variables.)
 172
 173    All variables are compacted if EXCLUDE_CLASSES is 0, or it may
 174    contain one or more of (1u << DC_ORDINARY), (1u << DC_SYSTEM),
 175    or (1u << DC_SCRATCH) to cause the corresponding type of
 176    variable to be deleted during compaction. */
 177 struct case_map *
 178 case_map_to_compact_dict (const struct dictionary *d,
 179                           unsigned int exclude_classes)
 180 {
 181   size_t var_cnt;
 182   struct case_map *map;
 183   size_t value_idx;
 184   size_t i;
 185
 186   assert ((exclude_classes & ~((1u << DC_ORDINARY)
 187                                | (1u << DC_SYSTEM)
 188                                | (1u << DC_SCRATCH))) == 0);
 189
 190   map = create_case_map (dict_count_values (d, exclude_classes));
 191   var_cnt = dict_get_var_cnt (d);
 192   value_idx = 0;
 193   for (i = 0; i < var_cnt; i++)
 194     {
 195       struct variable *v = dict_get_var (d, i);
 196       enum dict_class class = dict_class_from_id (var_get_name (v));
 197
 198       if (!(exclude_classes & (1u << class)))
 199         {
 200           size_t value_cnt = var_get_value_cnt (v);
 201           insert_mapping (map, var_get_case_index (v), value_idx, value_cnt);
 202           value_idx += value_cnt;
 203         }
 204     }
 205   assert (value_idx == map->value_cnt);
 206
 207   return map;
 208 }
 209
 210 /* Prepares dictionary D for producing a case map.  Afterward,
 211    the caller may delete, reorder, or rename variables within D
 212    at will before using case_map_from_dict() to produce the case
 213    map.
 214
 215    Uses D's aux members, which must otherwise not be in use. */
 216 void
 217 case_map_prepare_dict (const struct dictionary *d)
 218 {
 219   size_t var_cnt = dict_get_var_cnt (d);
 220   size_t i;
 221
 222   for (i = 0; i < var_cnt; i++)
 223     {
 224       struct variable *v = dict_get_var (d, i);
 225       int *src_fv = xmalloc (sizeof *src_fv);
 226       *src_fv = var_get_case_index (v);
 227       var_attach_aux (v, src_fv, var_dtor_free);
 228     }
 229 }
 230
 231 /* Produces a case map from dictionary D, which must have been
 232    previously prepared with case_map_prepare_dict().
 233
 234    Does not retain any reference to D, and clears the aux members
 235    set up by case_map_prepare_dict().
 236
 237    Returns the new case map, or a null pointer if no mapping is
 238    required (that is, no data has changed position). */
 239 struct case_map *
 240 case_map_from_dict (const struct dictionary *d)
 241 {
 242   struct case_map *map;
 243   size_t var_cnt = dict_get_var_cnt (d);
 244   size_t i;
 245   bool identity_map = true;
 246
 247   map = create_case_map (dict_get_next_value_idx (d));
 248   for (i = 0; i < var_cnt; i++)
 249     {
 250       struct variable *v = dict_get_var (d, i);
 251       size_t value_cnt = var_get_value_cnt (v);
 252       int *src_fv = (int *) var_detach_aux (v);
 253
 254       if (var_get_case_index (v) != *src_fv)
 255         identity_map = false;
 256
 257       insert_mapping (map, *src_fv, var_get_case_index (v), value_cnt);
 258
 259       free (src_fv);
 260     }
 261
 262   if (identity_map)
 263     {
 264       case_map_destroy (map);
 265       return NULL;
 266     }
 267
 268   while (map->value_cnt > 0 && map->map[map->value_cnt - 1] == -1)
 269     map->value_cnt--;
 270
 271   return map;
 272 }
 273
 274 /* Creates and returns a case map for mapping variables in OLD to
 275    variables in NEW based on their name.  For every variable in
 276    NEW, there must be a variable in OLD with the same name, type,
 277    and width. */
 278 struct case_map *
 279 case_map_by_name (const struct dictionary *old,
 280                   const struct dictionary *new)
 281 {
 282   struct case_map *map;
 283   size_t var_cnt = dict_get_var_cnt (new);
 284   size_t i;
 285
 286   map = create_case_map (dict_get_next_value_idx (new));
 287   for (i = 0; i < var_cnt; i++)
 288     {
 289       struct variable *nv = dict_get_var (new, i);
 290       struct variable *ov = dict_lookup_var_assert (old, var_get_name (nv));
 291       assert (var_get_width (nv) == var_get_width (ov));
 292       insert_mapping (map, var_get_case_index (ov), var_get_case_index (nv),
 293                       var_get_value_cnt (ov));
 294     }
 295   return map;
 296 }
 297
 298 /* Prints the mapping represented by case map CM to stdout, for
 299    debugging purposes. */
 300 void
 301 case_map_dump (const struct case_map *cm)
 302 {
 303   int i;
 304   for (i = 0 ; i < cm->value_cnt; ++i )
 305     printf ("%d -> %d\n", i, cm->map[i]);
 306 }