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