src/data/case-map.c

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