src/math/merge.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    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, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 /* FIXME: error checking. */
  20 /* FIXME: merge pattern should be improved, this one causes a
  21    performance regression. */
  22 #include <config.h>
  23
  24 #include <math/merge.h>
  25
  26 #include <data/case-ordering.h>
  27 #include <data/case.h>
  28 #include <data/casereader.h>
  29 #include <data/casewriter.h>
  30 #include <libpspp/array.h>
  31 #include <libpspp/assertion.h>
  32 #include <libpspp/taint.h>
  33
  34 #include "xalloc.h"
  35
  36 #define MAX_MERGE_ORDER 7
  37
  38 struct merge_input
  39   {
  40     struct casereader *reader;
  41     struct ccase c;
  42   };
  43
  44 struct merge
  45   {
  46     struct case_ordering *ordering;
  47     struct merge_input inputs[MAX_MERGE_ORDER];
  48     size_t input_cnt;
  49   };
  50
  51 static void do_merge (struct merge *m);
  52
  53 struct merge *
  54 merge_create (const struct case_ordering *ordering)
  55 {
  56   struct merge *m = xmalloc (sizeof *m);
  57   m->ordering = case_ordering_clone (ordering);
  58   m->input_cnt = 0;
  59   return m;
  60 }
  61
  62 void
  63 merge_destroy (struct merge *m)
  64 {
  65   if (m != NULL)
  66     {
  67       size_t i;
  68
  69       case_ordering_destroy (m->ordering);
  70       for (i = 0; i < m->input_cnt; i++)
  71         casereader_destroy (m->inputs[i].reader);
  72       free (m);
  73     }
  74 }
  75
  76 void
  77 merge_append (struct merge *m, struct casereader *r)
  78 {
  79   r = casereader_rename (r);
  80   m->inputs[m->input_cnt++].reader = r;
  81   if (m->input_cnt >= MAX_MERGE_ORDER)
  82     do_merge (m);
  83 }
  84
  85 struct casereader *
  86 merge_make_reader (struct merge *m)
  87 {
  88   struct casereader *r;
  89
  90   if (m->input_cnt > 1)
  91     do_merge (m);
  92
  93   if (m->input_cnt == 1)
  94     {
  95       r = m->inputs[0].reader;
  96       m->input_cnt = 0;
  97     }
  98   else if (m->input_cnt == 0)
  99     {
 100       size_t value_cnt = case_ordering_get_value_cnt (m->ordering);
 101       struct casewriter *writer = mem_writer_create (value_cnt);
 102       r = casewriter_make_reader (writer);
 103     }
 104   else
 105     NOT_REACHED ();
 106
 107   return r;
 108 }
 109
 110 static bool
 111 read_input_case (struct merge *m, size_t idx)
 112 {
 113   struct merge_input *i = &m->inputs[idx];
 114
 115   if (casereader_read (i->reader, &i->c))
 116     return true;
 117   else
 118     {
 119       casereader_destroy (i->reader);
 120       remove_element (m->inputs, m->input_cnt, sizeof *m->inputs, idx);
 121       m->input_cnt--;
 122       return false;
 123     }
 124 }
 125
 126 static void
 127 do_merge (struct merge *m)
 128 {
 129   struct casewriter *w;
 130   size_t i;
 131
 132   assert (m->input_cnt > 1);
 133
 134   w = tmpfile_writer_create (case_ordering_get_value_cnt (m->ordering));
 135   for (i = 0; i < m->input_cnt; i++)
 136     taint_propagate (casereader_get_taint (m->inputs[i].reader),
 137                      casewriter_get_taint (w));
 138
 139   for (i = 0; i < m->input_cnt; )
 140     if (read_input_case (m, i))
 141       i++;
 142   while (m->input_cnt > 0)
 143     {
 144       size_t min;
 145
 146       min = 0;
 147       for (i = 1; i < m->input_cnt; i++)
 148         if (case_ordering_compare_cases (&m->inputs[i].c, &m->inputs[min].c,
 149                                          m->ordering) < 0)
 150           min = i;
 151
 152       casewriter_write (w, &m->inputs[min].c);
 153       read_input_case (m, min);
 154     }
 155
 156   m->input_cnt = 1;
 157   m->inputs[0].reader = casewriter_make_reader (w);
 158 }
 159