59536da648d8a66be1955a5f27f4880c503111c3
[pspp-builds.git] / 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