src/math/merge.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 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 /* FIXME: error checking. */
  18 /* FIXME: merge pattern should be improved, this one causes a
  19    performance regression. */
  20 #include <config.h>
  21
  22 #include <math/merge.h>
  23
  24 #include <data/case-ordering.h>
  25 #include <data/case.h>
  26 #include <data/casereader.h>
  27 #include <data/casewriter.h>
  28 #include <libpspp/array.h>
  29 #include <libpspp/assertion.h>
  30 #include <libpspp/taint.h>
  31
  32 #include "xalloc.h"
  33
  34 #define MAX_MERGE_ORDER 7
  35
  36 struct merge_input
  37   {
  38     struct casereader *reader;
  39     struct ccase c;
  40   };
  41
  42 struct merge
  43   {
  44     struct case_ordering *ordering;
  45     struct merge_input inputs[MAX_MERGE_ORDER];
  46     size_t input_cnt;
  47   };
  48
  49 static void do_merge (struct merge *m);
  50
  51 struct merge *
  52 merge_create (const struct case_ordering *ordering)
  53 {
  54   struct merge *m = xmalloc (sizeof *m);
  55   m->ordering = case_ordering_clone (ordering);
  56   m->input_cnt = 0;
  57   return m;
  58 }
  59
  60 void
  61 merge_destroy (struct merge *m)
  62 {
  63   if (m != NULL)
  64     {
  65       size_t i;
  66
  67       case_ordering_destroy (m->ordering);
  68       for (i = 0; i < m->input_cnt; i++)
  69         casereader_destroy (m->inputs[i].reader);
  70       free (m);
  71     }
  72 }
  73
  74 void
  75 merge_append (struct merge *m, struct casereader *r)
  76 {
  77   r = casereader_rename (r);
  78   m->inputs[m->input_cnt++].reader = r;
  79   if (m->input_cnt >= MAX_MERGE_ORDER)
  80     do_merge (m);
  81 }
  82
  83 struct casereader *
  84 merge_make_reader (struct merge *m)
  85 {
  86   struct casereader *r;
  87
  88   if (m->input_cnt > 1)
  89     do_merge (m);
  90
  91   if (m->input_cnt == 1)
  92     {
  93       r = m->inputs[0].reader;
  94       m->input_cnt = 0;
  95     }
  96   else if (m->input_cnt == 0)
  97     {
  98       size_t value_cnt = case_ordering_get_value_cnt (m->ordering);
  99       struct casewriter *writer = mem_writer_create (value_cnt);
 100       r = casewriter_make_reader (writer);
 101     }
 102   else
 103     NOT_REACHED ();
 104
 105   return r;
 106 }
 107
 108 static bool
 109 read_input_case (struct merge *m, size_t idx)
 110 {
 111   struct merge_input *i = &m->inputs[idx];
 112
 113   if (casereader_read (i->reader, &i->c))
 114     return true;
 115   else
 116     {
 117       casereader_destroy (i->reader);
 118       remove_element (m->inputs, m->input_cnt, sizeof *m->inputs, idx);
 119       m->input_cnt--;
 120       return false;
 121     }
 122 }
 123
 124 static void
 125 do_merge (struct merge *m)
 126 {
 127   struct casewriter *w;
 128   size_t i;
 129
 130   assert (m->input_cnt > 1);
 131
 132   w = tmpfile_writer_create (case_ordering_get_value_cnt (m->ordering));
 133   for (i = 0; i < m->input_cnt; i++)
 134     taint_propagate (casereader_get_taint (m->inputs[i].reader),
 135                      casewriter_get_taint (w));
 136
 137   for (i = 0; i < m->input_cnt; )
 138     if (read_input_case (m, i))
 139       i++;
 140   while (m->input_cnt > 0)
 141     {
 142       size_t min;
 143
 144       min = 0;
 145       for (i = 1; i < m->input_cnt; i++)
 146         if (case_ordering_compare_cases (&m->inputs[i].c, &m->inputs[min].c,
 147                                          m->ordering) < 0)
 148           min = i;
 149
 150       casewriter_write (w, &m->inputs[min].c);
 151       read_input_case (m, min);
 152     }
 153
 154   m->input_cnt = 1;
 155   m->inputs[0].reader = casewriter_make_reader (w);
 156 }
 157