Replace checkbox-treeview functions with a object PsppireCheckboxTreeview
[pspp] / src / math / merge.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2009, 2011 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 "gl/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