1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the test suite module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:GPL-EXCEPT$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU
19** General Public License version 3 as published by the Free Software
20** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
21** included in the packaging of this file. Please review the following
22** information to ensure the GNU General Public License requirements will
23** be met: https://www.gnu.org/licenses/gpl-3.0.html.
24**
25** $QT_END_LICENSE$
26**
27****************************************************************************/
28
29#include "compress.h"
30
31#include <QtCore/qdebug.h>
32#include <QtCore/qlist.h>
33
34#include <algorithm>
35#include <iterator>
36#include <iostream>
37
38#define QLALR_NO_CHECK_SORTED_TABLE
39
40struct _Fit
41{
42 inline bool operator () (int a, int b) const
43 {
44 return a == 0 || b == 0 || a == b;
45 }
46};
47
48struct _PerfectMatch
49{
50 inline bool operator () (int a, int b) const
51 { return a == b; }
52};
53
54struct _GenerateCheck
55{
56 QList<int>::const_iterator iterator;
57 int initial;
58
59 _GenerateCheck(QList<int>::const_iterator it, int i) : iterator(it), initial(i) { }
60
61 inline int operator()()
62 {
63 int check = initial++;
64 return *iterator++ ? check : -1;
65 }
66};
67
68class UncompressedRow
69{
70public:
71 typedef const int *const_iterator;
72 typedef const int *iterator;
73
74public:
75 inline UncompressedRow ():
76 _M_index (0),
77 _M_begin (nullptr),
78 _M_end (nullptr),
79 _M_beginNonZeros (nullptr),
80 _M_endNonZeros (nullptr) {}
81
82 inline UncompressedRow (int index, const_iterator begin, const_iterator end)
83 { assign (index, begin, end); }
84
85 inline int index () const { return _M_index; }
86 inline const_iterator begin () const { return _M_begin; }
87 inline const_iterator end () const { return _M_end; }
88
89 inline void assign (int index, const_iterator begin, const_iterator end)
90 {
91 _M_index = index;
92 _M_begin = begin;
93 _M_end = end;
94
95 _M_beginNonZeros = _M_begin;
96 _M_endNonZeros = _M_end;
97
98 for (_M_beginNonZeros = _M_begin; _M_beginNonZeros != _M_end && ! _M_beginNonZeros [0]; ++_M_beginNonZeros)
99 /*continue*/ ;
100
101#if 0
102 for (_M_endNonZeros = _M_end; _M_endNonZeros != _M_beginNonZeros && ! _M_endNonZeros [-1]; --_M_endNonZeros)
103 /*continue*/ ;
104#endif
105 }
106
107 inline int at (int index) const
108 { return _M_begin [index]; }
109
110 inline bool isEmpty () const
111 { return _M_begin == _M_end; }
112
113 inline int size () const
114 { return _M_end - _M_begin; }
115
116 inline int nonZeroElements () const
117 { return _M_endNonZeros - _M_beginNonZeros; }
118
119 inline int count (int value) const
120 { return std::count (begin (), end (), value); }
121
122 inline const_iterator beginNonZeros () const
123 { return _M_beginNonZeros; }
124
125 inline const_iterator endNonZeros () const
126 { return _M_endNonZeros; }
127
128private:
129 int _M_index;
130 const_iterator _M_begin;
131 const_iterator _M_end;
132 const_iterator _M_beginNonZeros;
133 const_iterator _M_endNonZeros;
134};
135
136struct _SortUncompressedRow
137{
138 inline bool operator () (const UncompressedRow &a, const UncompressedRow &b) const
139 { return a.count (0) > b.count (0); }
140};
141
142Compress::Compress ()
143{
144}
145
146void Compress::operator () (int *table, int row_count, int column_count)
147{
148 index.clear ();
149 info.clear ();
150 check.clear ();
151
152 QList<UncompressedRow> sortedTable(row_count);
153
154 for (int i = 0; i < row_count; ++i)
155 {
156 int *begin = &table [i * column_count];
157 int *end = begin + column_count;
158
159 sortedTable [i].assign (i, begin, end);
160 }
161
162 std::sort (sortedTable.begin (), sortedTable.end (), _SortUncompressedRow ());
163
164#ifndef QLALR_NO_CHECK_SORTED_TABLE
165 int previous_zeros = INT_MAX;
166
167 for (const UncompressedRow &row : qAsConst(sortedTable))
168 {
169 int zeros = row.count (0);
170
171 Q_ASSERT (zeros <= previous_zeros);
172 zeros = previous_zeros;
173 qDebug () << "OK!";
174 }
175#endif
176
177 index.fill (-999999, row_count);
178
179 for (const UncompressedRow &row : qAsConst(sortedTable))
180 {
181 int first_token = std::distance (row.begin (), row.beginNonZeros ());
182 QList<int>::iterator pos = info.begin();
183
184 while (pos != info.end ())
185 {
186 if (pos == info.begin ())
187 {
188 // try to find a perfect match
189 QList<int>::iterator pm = std::search(&*pos, &*info.end(), row.beginNonZeros(),
190 row.endNonZeros(), _PerfectMatch());
191
192 if (pm != info.end ())
193 {
194 pos = pm;
195 break;
196 }
197 }
198
199 pos = std::search (&*pos, &*info.end (), row.beginNonZeros (), row.endNonZeros (), _Fit ());
200
201 if (pos == info.end ())
202 break;
203
204 int idx = std::distance (info.begin (), pos) - first_token;
205 bool conflict = false;
206
207 for (int j = 0; ! conflict && j < row.size (); ++j)
208 {
209 if (row.at (j) == 0)
210 conflict |= idx + j >= 0 && check [idx + j] == j;
211
212 else
213 conflict |= check [idx + j] == j;
214 }
215
216 if (! conflict)
217 break;
218
219 ++pos;
220 }
221
222 if (pos == info.end ())
223 {
224 int size = info.size ();
225
226 info.resize (info.size () + row.nonZeroElements ());
227 check.resize (info.size ());
228
229 std::fill (check.begin () + size, check.end (), -1);
230 pos = info.begin () + size;
231 }
232
233 int offset = std::distance (info.begin (), pos);
234 index [row.index ()] = offset - first_token;
235
236 for (const int *it = row.beginNonZeros (); it != row.endNonZeros (); ++it, ++pos)
237 {
238 if (*it)
239 *pos = *it;
240 }
241
242 int i = row.index ();
243
244 for (int j = 0; j < row.size (); ++j)
245 {
246 if (row.at (j) == 0)
247 continue;
248
249 check [index [i] + j] = j;
250 }
251 }
252
253#if 0
254 for (const UncompressedRow &row : qAsConst(sortedTable))
255 {
256 int i = row.index ();
257 Q_ASSERT (i < sortedTable.size ());
258
259 for (int j = 0; j < row.size (); ++j)
260 {
261 if (row.at (j) == 0)
262 {
263 Q_ASSERT (index [i] + j < 0 || check [index [i] + j] != j);
264 continue;
265 }
266
267 Q_ASSERT ( info [index [i] + j] == row.at (j));
268 Q_ASSERT (check [index [i] + j] == j);
269 }
270 }
271#endif
272}
273