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/dictionary.h>
  25 #include <data/variable.h>
  26 #include <data/case.h>
  27 #include <libpspp/assertion.h>
  28
  29 #include "xalloc.h"
  30
  31 /* A case map. */
  32 struct case_map
  33   {
  34     size_t value_cnt;   /* Number of values in map. */
  35     int *map;           /* For each destination index, the
  36                            corresponding source index. */
  37   };
  38
  39 /* Creates and returns an empty map. */
  40 static struct case_map *
  41 create_case_map (size_t n)
  42 {
  43   struct case_map *map;
  44   size_t i;
  45
  46   map = xmalloc (sizeof *map);
  47   map->value_cnt = n;
  48   map->map = xnmalloc (n, sizeof *map->map);
  49   for (i = 0; i < map->value_cnt; i++)
  50     map->map[i] = -1;
  51
  52   return map;
  53 }
  54
  55 /* Inserts into MAP a mapping of the CNT values starting at FROM
  56    to the CNT values starting at TO. */
  57 static void
  58 insert_mapping (struct case_map *map, size_t from, size_t to, size_t cnt)
  59 {
  60   size_t i;
  61
  62   assert (to + cnt <= map->value_cnt);
  63   for (i = 0; i < cnt; i++)
  64     {
  65       assert (map->map[to + i] == -1);
  66       map->map[to + i] = from + i;
  67     }
  68 }
  69
  70 /* Destroys case map MAP. */
  71 void
  72 case_map_destroy (struct case_map *map)
  73 {
  74   if (map != NULL)
  75     {
  76       free (map->map);
  77       free (map);
  78     }
  79 }
  80
  81 /* Maps from SRC to DST, applying case map MAP. */
  82 void
  83 case_map_execute (const struct case_map *map,
  84                   const struct ccase *src, struct ccase *dst)
  85 {
  86   size_t dst_idx;
  87
  88   case_create (dst, map->value_cnt);
  89   for (dst_idx = 0; dst_idx < map->value_cnt; dst_idx++)
  90     {
  91       int src_idx = map->map[dst_idx];
  92       if (src_idx != -1)
  93         *case_data_rw_idx (dst, dst_idx) = *case_data_idx (src, src_idx);
  94     }
  95 }
  96
  97 /* Returns the number of `union value's in cases created by
  98    MAP. */
  99 size_t
 100 case_map_get_value_cnt (const struct case_map *map)
 101 {
 102   return map->value_cnt;
 103 }
 104
 105 /* Creates and returns a case_map that can be used to compact
 106    cases for dictionary D.
 107
 108    Compacting a case eliminates "holes" between values and after
 109    the last value.  (Holes are created by deleting variables.)
 110
 111    All variables are compacted if EXCLUDE_CLASSES is 0, or it may
 112    contain one or more of (1u << DC_ORDINARY), (1u << DC_SYSTEM),
 113    or (1u << DC_SCRATCH) to cause the corresponding type of
 114    variable to be deleted during compaction. */
 115 struct case_map *
 116 case_map_to_compact_dict (const struct dictionary *d,
 117                           unsigned int exclude_classes)
 118 {
 119   size_t var_cnt;
 120   struct case_map *map;
 121   size_t value_idx;
 122   size_t i;
 123
 124   assert ((exclude_classes & ~((1u << DC_ORDINARY)
 125                                | (1u << DC_SYSTEM)
 126                                | (1u << DC_SCRATCH))) == 0);
 127
 128   map = create_case_map (dict_count_values (d, exclude_classes));
 129   var_cnt = dict_get_var_cnt (d);
 130   value_idx = 0;
 131   for (i = 0; i < var_cnt; i++)
 132     {
 133       struct variable *v = dict_get_var (d, i);
 134       enum dict_class class = dict_class_from_id (var_get_name (v));
 135
 136       if (!(exclude_classes & (1u << class)))
 137         {
 138           size_t value_cnt = var_get_value_cnt (v);
 139           insert_mapping (map, var_get_case_index (v), value_idx, value_cnt);
 140           value_idx += value_cnt;
 141         }
 142     }
 143   assert (value_idx == map->value_cnt);
 144
 145   return map;
 146 }
 147
 148 /* Prepares dictionary D for producing a case map.  Afterward,
 149    the caller may delete, reorder, or rename variables within D
 150    at will before using case_map_from_dict() to produce the case
 151    map.
 152
 153    Uses D's aux members, which must otherwise not be in use. */
 154 void
 155 case_map_prepare_dict (const struct dictionary *d)
 156 {
 157   size_t var_cnt = dict_get_var_cnt (d);
 158   size_t i;
 159
 160   for (i = 0; i < var_cnt; i++)
 161     {
 162       struct variable *v = dict_get_var (d, i);
 163       int *src_fv = xmalloc (sizeof *src_fv);
 164       *src_fv = var_get_case_index (v);
 165       var_attach_aux (v, src_fv, var_dtor_free);
 166     }
 167 }
 168
 169 /* Produces a case map from dictionary D, which must have been
 170    previously prepared with case_map_prepare_dict().
 171
 172    Does not retain any reference to D, and clears the aux members
 173    set up by case_map_prepare_dict().
 174
 175    Returns the new case map, or a null pointer if no mapping is
 176    required (that is, no data has changed position). */
 177 struct case_map *
 178 case_map_from_dict (const struct dictionary *d)
 179 {
 180   struct case_map *map;
 181   size_t var_cnt = dict_get_var_cnt (d);
 182   size_t i;
 183   bool identity_map = true;
 184
 185   map = create_case_map (dict_get_next_value_idx (d));
 186   for (i = 0; i < var_cnt; i++)
 187     {
 188       struct variable *v = dict_get_var (d, i);
 189       size_t value_cnt = var_get_value_cnt (v);
 190       int *src_fv = (int *) var_detach_aux (v);
 191
 192       if (var_get_case_index (v) != *src_fv)
 193         identity_map = false;
 194
 195       insert_mapping (map, *src_fv, var_get_case_index (v), value_cnt);
 196
 197       free (src_fv);
 198     }
 199
 200   if (identity_map)
 201     {
 202       case_map_destroy (map);
 203       return NULL;
 204     }
 205
 206   while (map->value_cnt > 0 && map->map[map->value_cnt - 1] == -1)
 207     map->value_cnt--;
 208
 209   return map;
 210 }
 211
 212 /* Creates and returns a case map for mapping variables in OLD to
 213    variables in NEW based on their name.  For every variable in
 214    NEW, there must be a variable in OLD with the same name, type,
 215    and width. */
 216 struct case_map *
 217 case_map_by_name (const struct dictionary *old,
 218                   const struct dictionary *new)
 219 {
 220   struct case_map *map;
 221   size_t var_cnt = dict_get_var_cnt (new);
 222   size_t i;
 223
 224   map = create_case_map (dict_get_next_value_idx (new));
 225   for (i = 0; i < var_cnt; i++)
 226     {
 227       struct variable *nv = dict_get_var (new, i);
 228       struct variable *ov = dict_lookup_var_assert (old, var_get_name (nv));
 229       assert (var_get_width (nv) == var_get_width (ov));
 230       insert_mapping (map, var_get_case_index (ov), var_get_case_index (nv),
 231                       var_get_value_cnt (ov));
 232     }
 233   return map;
 234 }
 235
 236 /* Prints the mapping represented by case map CM to stdout, for
 237    debugging purposes. */
 238 void
 239 case_map_dump (const struct case_map *cm)
 240 {
 241   int i;
 242   for (i = 0 ; i < cm->value_cnt; ++i )
 243     printf ("%d -> %d\n", i, cm->map[i]);
 244 }