src/math/merge.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 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.h>
  25 #include <data/casereader.h>
  26 #include <data/casewriter.h>
  27 #include <data/subcase.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 subcase ordering;
  45     struct merge_input inputs[MAX_MERGE_ORDER];
  46     size_t input_cnt;
  47     struct caseproto *proto;
  48   };
  49
  50 static void do_merge (struct merge *m);
  51
  52 struct merge *
  53 merge_create (const struct subcase *ordering, const struct caseproto *proto)
  54 {
  55   struct merge *m = xmalloc (sizeof *m);
  56   subcase_clone (&m->ordering, ordering);
  57   m->input_cnt = 0;
  58   m->proto = caseproto_ref (proto);
  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       subcase_destroy (&m->ordering);
  70       for (i = 0; i < m->input_cnt; i++)
  71         casereader_destroy (m->inputs[i].reader);
  72       caseproto_unref (m->proto);
  73       free (m);
  74     }
  75 }
  76
  77 void
  78 merge_append (struct merge *m, struct casereader *r)
  79 {
  80   r = casereader_rename (r);
  81   m->inputs[m->input_cnt++].reader = r;
  82   if (m->input_cnt >= MAX_MERGE_ORDER)
  83     do_merge (m);
  84 }
  85
  86 struct casereader *
  87 merge_make_reader (struct merge *m)
  88 {
  89   struct casereader *r;
  90
  91   if (m->input_cnt > 1)
  92     do_merge (m);
  93
  94   if (m->input_cnt == 1)
  95     {
  96       r = m->inputs[0].reader;
  97       m->input_cnt = 0;
  98     }
  99   else if (m->input_cnt == 0)
 100     {
 101       struct casewriter *writer = mem_writer_create (m->proto);
 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   i->c = casereader_read (i->reader);
 116   if (i->c)
 117     return true;
 118   else
 119     {
 120       casereader_destroy (i->reader);
 121       remove_element (m->inputs, m->input_cnt, sizeof *m->inputs, idx);
 122       m->input_cnt--;
 123       return false;
 124     }
 125 }
 126
 127 static void
 128 do_merge (struct merge *m)
 129 {
 130   struct casewriter *w;
 131   size_t i;
 132
 133   assert (m->input_cnt > 1);
 134
 135   w = tmpfile_writer_create (m->proto);
 136   for (i = 0; i < m->input_cnt; i++)
 137     taint_propagate (casereader_get_taint (m->inputs[i].reader),
 138                      casewriter_get_taint (w));
 139
 140   for (i = 0; i < m->input_cnt; )
 141     if (read_input_case (m, i))
 142       i++;
 143   while (m->input_cnt > 0)
 144     {
 145       size_t min;
 146
 147       min = 0;
 148       for (i = 1; i < m->input_cnt; i++)
 149         if (subcase_compare_3way (&m->ordering, m->inputs[i].c,
 150                                   &m->ordering, m->inputs[min].c) < 0)
 151           min = i;
 152
 153       casewriter_write (w, m->inputs[min].c);
 154       read_input_case (m, min);
 155     }
 156
 157   m->input_cnt = 1;
 158   m->inputs[0].reader = casewriter_make_reader (w);
 159 }
 160