New Slovenian localisation from http://translationproject.org
[pspp] / src / math / categoricals.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2009, 2010, 2011, 2012 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 "math/categoricals.h"
20 #include "math/interaction.h"
21
22 #include <stdio.h>
23
24 #include "data/case.h"
25 #include "data/value.h"
26 #include "data/variable.h"
27 #include "libpspp/array.h"
28 #include "libpspp/hmap.h"
29 #include "libpspp/pool.h"
30 #include "libpspp/str.h"
31 #include "libpspp/hash-functions.h"
32
33 #include "gl/xalloc.h"
34
35 #define CATEGORICALS_DEBUG 0
36
37 #define EFFECTS_CODING 1
38
39 struct value_node
40 {
41   struct hmap_node node;      /* Node in hash map. */
42
43   union value val;            /* The value */
44
45   int index;                  /* A zero based unique index for this value */
46 };
47
48 struct interaction_value
49 {
50   struct hmap_node node;      /* Node in hash map */
51
52   struct ccase *ccase;        /* A case (probably the first in the dataset) which matches this value */
53
54   double cc;        /* Total of the weights of cases matching this interaction */
55
56   void *user_data;            /* A pointer to data which the caller can store stuff */
57 };
58
59 static struct value_node *
60 lookup_value (const struct hmap *map, const union value *val, unsigned int hash, int width)
61 {
62   struct value_node *vn = NULL;
63   HMAP_FOR_EACH_WITH_HASH (vn, struct value_node, node, hash, map)
64     {
65       if (value_equal (&vn->val, val, width))
66         break;
67     }
68   
69   return vn;
70 }
71
72 struct variable_node
73 {
74   struct hmap_node node;      /* Node in hash map. */
75   const struct variable *var; /* The variable */
76
77   struct hmap valmap;         /* A map of value nodes */
78   int n_vals;                 /* Number of values for this variable */
79 };
80
81 static struct variable_node *
82 lookup_variable (const struct hmap *map, const struct variable *var, unsigned int hash)
83 {
84   struct variable_node *vn = NULL;
85   HMAP_FOR_EACH_WITH_HASH (vn, struct variable_node, node, hash, map)
86     {
87       if (vn->var == var)
88         break;
89       
90       fprintf (stderr, "Warning: Hash table collision\n");
91     }
92   
93   return vn;
94 }
95
96
97 struct interact_params
98 {
99   /* A map indexed by a interaction_value */
100   struct hmap ivmap;
101
102   const struct interaction *iact;
103
104   int base_subscript_short;
105   int base_subscript_long;
106
107   /* The number of distinct values of this interaction */
108   int n_cats;
109
110   /* An array of integers df_n * df_{n-1} * df_{n-2} ...
111      These are the products of the degrees of freedom for the current 
112      variable and all preceeding variables */
113   int *df_prod; 
114
115   double *enc_sum;
116
117   /* A map of interaction_values indexed by subscript */
118   struct interaction_value **reverse_interaction_value_map;
119
120   double cc;
121 };
122
123
124 /* Comparison function to sort the reverse_value_map in ascending order */
125 static int
126 compare_interaction_value_3way (const void *vn1_, const void *vn2_, const void *aux)
127 {
128   const struct interaction_value *const *vn1p = vn1_;
129   const struct interaction_value *const *vn2p = vn2_;
130
131   const struct interact_params *iap = aux;
132
133   return interaction_case_cmp_3way (iap->iact, (*vn1p)->ccase, (*vn2p)->ccase);
134 }
135
136 struct categoricals
137 {
138   /* The weight variable */
139   const struct variable *wv;
140
141   /* An array of interact_params */
142   struct interact_params *iap;
143
144   /* Map whose members are the union of the variables which comprise IAP */
145   struct hmap varmap;
146
147   /* The size of IAP. (ie, the number of interactions involved.) */
148   size_t n_iap;
149
150   /* The number of categorical variables which contain entries.
151      In the absence of missing values, this will be equal to N_IAP */
152   size_t n_vars;
153
154   size_t df_sum;
155
156   /* A map to enable the lookup of variables indexed by subscript.
157      This map considers only the N - 1 of the N variables.
158   */
159   int *reverse_variable_map_short;
160
161   /* Like the above, but uses all N variables */
162   int *reverse_variable_map_long;
163
164   size_t n_cats_total;
165
166   struct pool *pool;
167
168   /* Missing values in the dependent varirable to be excluded */
169   enum mv_class dep_excl;
170
171   /* Missing values in the factor variables to be excluded */
172   enum mv_class fctr_excl;
173
174   const void *aux1;
175   void *aux2;
176
177   const struct payload *payload;
178 };
179
180 static void
181 categoricals_dump (const struct categoricals *cat)
182 {
183   if (CATEGORICALS_DEBUG)
184     {
185       int i;
186
187       printf ("Reverse Variable Map (short):\n");
188       for (i = 0; i < cat->df_sum; ++i)
189         {
190           printf (" %d", cat->reverse_variable_map_short[i]);
191         }
192       printf ("\n");
193
194       printf ("Reverse Variable Map (long):\n");
195       for (i = 0; i < cat->n_cats_total; ++i)
196         {
197           printf (" %d", cat->reverse_variable_map_long[i]);
198         }
199       printf ("\n");
200
201
202       printf ("Number of interactions %d\n", cat->n_iap);
203       for (i = 0 ; i < cat->n_iap; ++i)
204         {
205           int v;
206           struct string str;
207           const struct interact_params *iap = &cat->iap[i];
208           const struct interaction *iact = iap->iact;
209
210           ds_init_empty (&str);
211           interaction_to_string (iact, &str);
212
213           printf ("\nInteraction: %s (n: %d); ", ds_cstr (&str), iap->n_cats);
214           ds_destroy (&str);
215           printf ("Base subscript: %d\n", iap->base_subscript_short);
216
217           printf ("\t(");
218           for (v = 0; v < hmap_count (&iap->ivmap); ++v)
219             {
220               int vv;
221               const struct interaction_value *iv = iap->reverse_interaction_value_map[v];
222           
223               if (v > 0)  printf ("   ");
224               printf ("{");
225               for (vv = 0; vv < iact->n_vars; ++vv)
226                 {
227                   const struct variable *var = iact->vars[vv];
228                   const union value *val = case_data (iv->ccase, var);
229               
230                   printf ("%g", val->f);
231                   if (vv < iact->n_vars - 1)
232                     printf (", ");
233                 }
234               printf ("}");
235             }
236           printf (")\n");
237         }
238     }
239 }
240
241 void
242 categoricals_destroy (struct categoricals *cat)
243 {
244   struct variable_node *vn = NULL;
245   int i;
246   if (NULL == cat)
247     return;
248   for (i = 0; i < cat->n_iap; ++i)
249     {
250       struct interaction_value *iv = NULL;
251       /* Interate over each interaction value, and unref any cases that we reffed */
252       HMAP_FOR_EACH (iv, struct interaction_value, node, &cat->iap[i].ivmap)
253         {
254 #if 0
255           if (cat->payload)
256             cat->payload->destroy (cat->aux1, iv->user_data);
257 #endif
258           case_unref (iv->ccase);
259         }
260
261       free (cat->iap[i].enc_sum);
262       free (cat->iap[i].df_prod);
263       hmap_destroy (&cat->iap[i].ivmap);
264     }
265
266   /* Interate over each variable and delete its value map */
267   HMAP_FOR_EACH (vn, struct variable_node, node, &cat->varmap)
268     {
269       hmap_destroy (&vn->valmap);
270     }
271
272   hmap_destroy (&cat->varmap);
273
274   pool_destroy (cat->pool);
275
276   free (cat);
277 }
278
279
280
281 static struct interaction_value *
282 lookup_case (const struct hmap *map, const struct interaction *iact, const struct ccase *c)
283 {
284   struct interaction_value *iv = NULL;
285   size_t hash = interaction_case_hash (iact, c, 0);
286
287   HMAP_FOR_EACH_WITH_HASH (iv, struct interaction_value, node, hash, map)
288     {
289       if (interaction_case_equal (iact, c, iv->ccase))
290         break;
291
292       fprintf (stderr, "Warning: Hash table collision\n");
293     }
294
295   return iv;
296 }
297
298
299 struct categoricals *
300 categoricals_create (struct interaction *const*inter, size_t n_inter,
301                      const struct variable *wv, enum mv_class dep_excl, enum mv_class fctr_excl)
302 {
303   size_t i;
304   struct categoricals *cat = xmalloc (sizeof *cat);
305   
306   cat->n_iap = n_inter;
307   cat->wv = wv;
308   cat->n_cats_total = 0;
309   cat->n_vars = 0;
310   cat->reverse_variable_map_short = NULL;
311   cat->reverse_variable_map_long = NULL;
312   cat->pool = pool_create ();
313   cat->dep_excl = dep_excl;
314   cat->fctr_excl = fctr_excl;
315   cat->payload = NULL;
316   cat->aux2 = NULL;
317
318   cat->iap = pool_calloc (cat->pool, cat->n_iap, sizeof *cat->iap);
319
320   hmap_init (&cat->varmap);
321   for (i = 0 ; i < cat->n_iap; ++i)
322     {
323       int v;
324       hmap_init (&cat->iap[i].ivmap);
325       cat->iap[i].iact = inter[i];
326       cat->iap[i].cc = 0.0;
327       for (v = 0; v < inter[i]->n_vars; ++v)
328         {
329           const struct variable *var = inter[i]->vars[v];
330           unsigned int hash = hash_pointer (var, 0);
331           struct variable_node *vn = lookup_variable (&cat->varmap, var, hash);
332           if (vn == NULL)
333             {
334               vn = pool_malloc (cat->pool, sizeof *vn);
335               vn->var = var;
336               vn->n_vals = 0;
337               hmap_init (&vn->valmap);
338
339               hmap_insert (&cat->varmap, &vn->node,  hash);
340             }
341         }
342     }
343
344   return cat;
345 }
346
347
348
349 void
350 categoricals_update (struct categoricals *cat, const struct ccase *c)
351 {
352   int i;
353   struct variable_node *vn = NULL;
354   const double weight = cat->wv ? case_data (c, cat->wv)->f : 1.0;
355
356   assert (NULL == cat->reverse_variable_map_short);
357   assert (NULL == cat->reverse_variable_map_long);
358
359   /* Interate over each variable, and add the value of that variable
360      to the appropriate map, if it's not already present. */
361   HMAP_FOR_EACH (vn, struct variable_node, node, &cat->varmap)
362     {
363       const int width = var_get_width (vn->var);
364       const union value *val = case_data (c, vn->var);
365       unsigned int hash = value_hash (val, width, 0);
366
367       struct value_node *valn = lookup_value (&vn->valmap, val, hash, width);
368       if (valn == NULL)
369         {
370           valn = pool_malloc (cat->pool, sizeof *valn);
371           valn->index = vn->n_vals++;
372           value_init (&valn->val, width);
373           value_copy (&valn->val, val, width);
374           hmap_insert (&vn->valmap, &valn->node, hash);
375         }
376     }     
377   
378   for (i = 0 ; i < cat->n_iap; ++i)
379     {
380       const struct interaction *iact = cat->iap[i].iact;
381
382       size_t hash;
383       struct interaction_value *node;
384
385       if ( interaction_case_is_missing (iact, c, cat->fctr_excl))
386         continue;
387
388       hash = interaction_case_hash (iact, c, 0);
389       node = lookup_case (&cat->iap[i].ivmap, iact, c);
390
391       if ( NULL == node)
392         {
393           node = pool_malloc (cat->pool, sizeof *node);
394
395           node->ccase = case_ref (c);
396           node->cc = weight;
397
398           hmap_insert (&cat->iap[i].ivmap, &node->node, hash);
399
400           if (cat->payload) 
401             {
402               node->user_data = cat->payload->create (cat->aux1, cat->aux2);
403             }
404         }
405       else
406         {
407           node->cc += weight;
408         }
409       cat->iap[i].cc += weight;
410
411       if (cat->payload)
412         {
413           double weight = cat->wv ? case_data (c, cat->wv)->f : 1.0;
414           cat->payload->update (cat->aux1, cat->aux2, node->user_data, c, weight);
415         }
416
417     }
418 }
419
420 /* Return the number of categories (distinct values) for interction N */
421 size_t
422 categoricals_n_count (const struct categoricals *cat, size_t n)
423 {
424   return hmap_count (&cat->iap[n].ivmap);
425 }
426
427
428 size_t
429 categoricals_df (const struct categoricals *cat, size_t n)
430 {
431   const struct interact_params *iap = &cat->iap[n];
432   return iap->df_prod[iap->iact->n_vars - 1];
433 }
434
435
436 /* Return the total number of categories */
437 size_t
438 categoricals_n_total (const struct categoricals *cat)
439 {
440   if (!categoricals_is_complete (cat))
441     return 0;
442
443   return cat->n_cats_total;
444 }
445
446 size_t
447 categoricals_df_total (const struct categoricals *cat)
448 {
449   return cat->df_sum;
450 }
451
452 bool
453 categoricals_is_complete (const struct categoricals *cat)
454 {
455   return (NULL != cat->reverse_variable_map_short);
456 }
457
458
459 /* This function must be called *before* any call to categoricals_get_*_by subscript and
460  *after* all calls to categoricals_update */
461 bool
462 categoricals_done (const struct categoricals *cat_)
463 {
464   /* Implementation Note: Whilst this function is O(n) in cat->n_cats_total, in most
465      uses it will be more efficient that using a tree based structure, since it
466      is called only once, and means that subsequent lookups will be O(1).
467
468      1 call of O(n) + 10^9 calls of O(1) is better than 10^9 calls of O(log n).
469   */
470   struct categoricals *cat = CONST_CAST (struct categoricals *, cat_);
471   int v;
472   int i;
473   int idx_short = 0;
474   int idx_long = 0;
475   cat->df_sum = 0;
476   cat->n_cats_total = 0;
477
478   /* Calculate the degrees of freedom, and the number of categories */
479   for (i = 0 ; i < cat->n_iap; ++i)
480     {
481       int df = 1;
482       const struct interaction *iact = cat->iap[i].iact;
483
484       cat->iap[i].df_prod = iact->n_vars ? xcalloc (iact->n_vars, sizeof (int)) : NULL;
485
486       cat->iap[i].n_cats = 1;
487       
488       for (v = 0 ; v < iact->n_vars; ++v)
489         {
490           const struct variable *var = iact->vars[v];
491
492           struct variable_node *vn = lookup_variable (&cat->varmap, var, hash_pointer (var, 0));
493
494           if  (hmap_count (&vn->valmap) == 0)
495             return false;
496
497           cat->iap[i].df_prod[v] = df * (hmap_count (&vn->valmap) - 1);
498           df = cat->iap[i].df_prod[v];
499
500           cat->iap[i].n_cats *= hmap_count (&vn->valmap);
501         }
502
503       assert (v == iact->n_vars);
504       if (v > 0)
505         cat->df_sum += cat->iap[i].df_prod [v - 1];
506
507       cat->n_cats_total += cat->iap[i].n_cats;
508     }
509
510
511   cat->reverse_variable_map_short = pool_calloc (cat->pool,
512                                                  cat->df_sum,
513                                                  sizeof *cat->reverse_variable_map_short);
514
515   cat->reverse_variable_map_long = pool_calloc (cat->pool,
516                                                 cat->n_cats_total,
517                                                 sizeof *cat->reverse_variable_map_long);
518
519   for (i = 0 ; i < cat->n_iap; ++i)
520     {
521       struct interaction_value *ivn = NULL;
522       int x = 0;
523       int ii;
524       struct interact_params *iap = &cat->iap[i];
525
526       iap->base_subscript_short = idx_short;
527       iap->base_subscript_long = idx_long;
528
529       iap->reverse_interaction_value_map = pool_calloc (cat->pool, iap->n_cats,
530                                                         sizeof *iap->reverse_interaction_value_map);
531
532       HMAP_FOR_EACH (ivn, struct interaction_value, node, &iap->ivmap)
533         {
534           iap->reverse_interaction_value_map[x++] = ivn;
535
536         }
537
538       assert (x <= iap->n_cats);
539
540       /* For some purposes (eg CONTRASTS in ONEWAY) the values need to be sorted */
541       sort (iap->reverse_interaction_value_map, x, sizeof (*iap->reverse_interaction_value_map),
542             compare_interaction_value_3way, iap);
543
544       /* Fill the remaining values with null */
545       for (ii = x ; ii < iap->n_cats; ++ii)
546         iap->reverse_interaction_value_map[ii] = NULL;
547
548       /* Populate the reverse variable maps. */
549       if (iap->df_prod)
550         {
551           for (ii = 0; ii < iap->df_prod [iap->iact->n_vars - 1]; ++ii)
552             cat->reverse_variable_map_short[idx_short++] = i;
553         }
554
555       for (ii = 0; ii < iap->n_cats; ++ii)
556         cat->reverse_variable_map_long[idx_long++] = i;
557     }
558
559   assert (cat->n_vars <= cat->n_iap);
560
561   categoricals_dump (cat);
562
563   /* Tally up the sums for all the encodings */
564   for (i = 0 ; i < cat->n_iap; ++i)
565     {
566       int x, y;
567       struct interact_params *iap = &cat->iap[i];
568       const struct interaction *iact = iap->iact;
569
570       const int df = iap->df_prod ? iap->df_prod [iact->n_vars - 1] : 0;
571
572       iap->enc_sum = xcalloc (df, sizeof (*(iap->enc_sum)));
573
574       for (y = 0; y < hmap_count (&iap->ivmap); ++y)
575         {
576           struct interaction_value *iv = iap->reverse_interaction_value_map[y];
577           for (x = iap->base_subscript_short; x < iap->base_subscript_short + df ;++x)
578             {
579               const double bin = categoricals_get_code_for_case (cat, x, iv->ccase); \
580               iap->enc_sum [x - iap->base_subscript_short] += bin * iv->cc;
581             }
582           if (cat->payload && cat->payload->destroy)
583             cat->payload->destroy (cat->aux1, cat->aux2, iv->user_data);
584         }
585     }
586
587   return true;
588 }
589
590
591 static int
592 reverse_variable_lookup_short (const struct categoricals *cat, int subscript)
593 {
594   assert (cat->reverse_variable_map_short);
595   assert (subscript >= 0);
596   assert (subscript < cat->df_sum);
597
598   return cat->reverse_variable_map_short[subscript];
599 }
600
601 static int
602 reverse_variable_lookup_long (const struct categoricals *cat, int subscript)
603 {
604   assert (cat->reverse_variable_map_long);
605   assert (subscript >= 0);
606   assert (subscript < cat->n_cats_total);
607
608   return cat->reverse_variable_map_long[subscript];
609 }
610
611
612 /* Return the interaction corresponding to SUBSCRIPT */
613 const struct interaction *
614 categoricals_get_interaction_by_subscript (const struct categoricals *cat, int subscript)
615 {
616   int index = reverse_variable_lookup_short (cat, subscript);
617
618   return cat->iap[index].iact;
619 }
620
621 double
622 categoricals_get_weight_by_subscript (const struct categoricals *cat, int subscript)
623 {
624   int vindex = reverse_variable_lookup_short (cat, subscript);
625   const struct interact_params *vp = &cat->iap[vindex];
626
627   return vp->cc;
628 }
629
630 double
631 categoricals_get_sum_by_subscript (const struct categoricals *cat, int subscript)
632 {
633   int vindex = reverse_variable_lookup_short (cat, subscript);
634   const struct interact_params *vp = &cat->iap[vindex];
635
636   return   vp->enc_sum[subscript - vp->base_subscript_short];
637 }
638
639 /* Returns unity if the value in case C at SUBSCRIPT is equal to the category
640    for that subscript */
641 double
642 categoricals_get_code_for_case (const struct categoricals *cat, int subscript,
643                                 const struct ccase *c)
644 {
645   const struct interaction *iact = categoricals_get_interaction_by_subscript (cat, subscript);
646
647   const int i = reverse_variable_lookup_short (cat, subscript);
648
649   const int base_index = cat->iap[i].base_subscript_short;
650
651   int v;
652   double result = 1.0;
653
654   const struct interact_params *iap = &cat->iap[i];
655
656   double dfp = 1.0;
657   for (v = 0; v < iact->n_vars; ++v)
658     {
659       const struct variable *var = iact->vars[v];
660
661       const union value *val = case_data (c, var);
662       const int width = var_get_width (var);
663       const struct variable_node *vn = lookup_variable (&cat->varmap, var, hash_pointer (var, 0));
664
665       const unsigned int hash = value_hash (val, width, 0);
666       const struct value_node *valn = lookup_value (&vn->valmap, val, hash, width);
667
668       double bin = 1.0;
669
670       const double df = iap->df_prod[v] / dfp;
671
672       /* Translate the subscript into an index for the individual variable */
673       const int index = ((subscript - base_index) % iap->df_prod[v] ) / dfp;
674       dfp = iap->df_prod [v];
675
676 #if EFFECTS_CODING
677       if ( valn->index == df )
678         bin = -1.0;
679       else 
680 #endif
681         if ( valn->index  != index )
682           bin = 0;
683     
684       result *= bin;
685     }
686
687   return result;
688 }
689
690
691 size_t
692 categoricals_get_n_variables (const struct categoricals *cat)
693 {
694   printf ("%s\n", __FUNCTION__);
695   return cat->n_vars;
696 }
697
698
699 /* Return a case containing the set of values corresponding to 
700    the Nth Category of the IACTth interaction */
701 const struct ccase *
702 categoricals_get_case_by_category_real (const struct categoricals *cat, int iact, int n)
703 {
704   const struct interaction_value *vn;
705
706   const struct interact_params *vp = &cat->iap[iact];
707
708   if ( n >= hmap_count (&vp->ivmap))
709     return NULL;
710
711   vn = vp->reverse_interaction_value_map [n];
712
713   return vn->ccase;
714 }
715
716 /* Return a the user data corresponding to the Nth Category of the IACTth interaction. */
717 void *
718 categoricals_get_user_data_by_category_real (const struct categoricals *cat, int iact, int n)
719 {
720   const struct interact_params *vp = &cat->iap[iact];
721   const struct interaction_value *iv ;
722
723   if ( n >= hmap_count (&vp->ivmap))
724     return NULL;
725
726   iv = vp->reverse_interaction_value_map [n];
727
728   return iv->user_data;
729 }
730
731
732
733 /* Return a case containing the set of values corresponding to SUBSCRIPT */
734 const struct ccase *
735 categoricals_get_case_by_category (const struct categoricals *cat, int subscript)
736 {
737   int vindex = reverse_variable_lookup_long (cat, subscript);
738   const struct interact_params *vp = &cat->iap[vindex];
739   const struct interaction_value *vn = vp->reverse_interaction_value_map [subscript - vp->base_subscript_long];
740
741   return vn->ccase;
742 }
743
744 void *
745 categoricals_get_user_data_by_category (const struct categoricals *cat, int subscript)
746 {
747   int vindex = reverse_variable_lookup_long (cat, subscript);
748   const struct interact_params *vp = &cat->iap[vindex];
749
750   const struct interaction_value *iv = vp->reverse_interaction_value_map [subscript - vp->base_subscript_long];
751   return iv->user_data;
752 }
753
754
755 \f
756
757 void
758 categoricals_set_payload (struct categoricals *cat, const struct payload *p,
759                           const void *aux1, void *aux2)
760 {
761   cat->payload = p;
762   cat->aux1 = aux1;
763   cat->aux2 = aux2;
764 }