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 QVector<int>::const_iterator iterator;
57 int initial;
58
59 _GenerateCheck (QVector<int>::const_iterator it, int i):
60 iterator (it),
61 initial (i) {}
62
63 inline int operator () ()
64 {
65 int check = initial++;
66 return *iterator++ ? check : -1;
67 }
68};
69
70class UncompressedRow
71{
72public:
73 typedef const int *const_iterator;
74 typedef const int *iterator;
75
76public:
77 inline UncompressedRow ():
78 _M_index (0),
79 _M_begin (0),
80 _M_end (0),
81 _M_beginNonZeros (0),
82 _M_endNonZeros (0) {}
83
84 inline UncompressedRow (int index, const_iterator begin, const_iterator end)
85 { assign (index, begin, end); }
86
87 inline int index () const { return _M_index; }
88 inline const_iterator begin () const { return _M_begin; }
89 inline const_iterator end () const { return _M_end; }
90
91 inline void assign (int index, const_iterator begin, const_iterator end)
92 {
93 _M_index = index;
94 _M_begin = begin;
95 _M_end = end;
96
97 _M_beginNonZeros = _M_begin;
98 _M_endNonZeros = _M_end;
99
100 for (_M_beginNonZeros = _M_begin; _M_beginNonZeros != _M_end && ! _M_beginNonZeros [0]; ++_M_beginNonZeros)
101 /*continue*/ ;
102
103#if 0
104 for (_M_endNonZeros = _M_end; _M_endNonZeros != _M_beginNonZeros && ! _M_endNonZeros [-1]; --_M_endNonZeros)
105 /*continue*/ ;
106#endif
107 }
108
109 inline int at (int index) const
110 { return _M_begin [index]; }
111
112 inline bool isEmpty () const
113 { return _M_begin == _M_end; }
114
115 inline int size () const
116 { return _M_end - _M_begin; }
117
118 inline int nonZeroElements () const
119 { return _M_endNonZeros - _M_beginNonZeros; }
120
121 inline int count (int value) const
122 { return std::count (first: begin (), last: end (), value: value); }
123
124 inline const_iterator beginNonZeros () const
125 { return _M_beginNonZeros; }
126
127 inline const_iterator endNonZeros () const
128 { return _M_endNonZeros; }
129
130private:
131 int _M_index;
132 const_iterator _M_begin;
133 const_iterator _M_end;
134 const_iterator _M_beginNonZeros;
135 const_iterator _M_endNonZeros;
136};
137
138struct _SortUncompressedRow
139{
140 inline bool operator () (const UncompressedRow &a, const UncompressedRow &b) const
141 { return a.count (value: 0) > b.count (value: 0); }
142};
143
144Compress::Compress ()
145{
146}
147
148void Compress::operator () (int *table, int row_count, int column_count)
149{
150 index.clear ();
151 info.clear ();
152 check.clear ();
153
154 QVector<UncompressedRow> sortedTable (row_count);
155
156 for (int i = 0; i < row_count; ++i)
157 {
158 int *begin = &table [i * column_count];
159 int *end = begin + column_count;
160
161 sortedTable [i].assign (index: i, begin, end);
162 }
163
164 std::sort (first: sortedTable.begin (), last: sortedTable.end (), comp: _SortUncompressedRow ());
165
166#ifndef QLALR_NO_CHECK_SORTED_TABLE
167 int previous_zeros = INT_MAX;
168
169 for (const UncompressedRow &row : qAsConst(sortedTable))
170 {
171 int zeros = row.count (0);
172
173 Q_ASSERT (zeros <= previous_zeros);
174 zeros = previous_zeros;
175 qDebug () << "OK!";
176 }
177#endif
178
179 index.fill (from: -999999, asize: row_count);
180
181 for (const UncompressedRow &row : qAsConst(t&: sortedTable))
182 {
183 int first_token = std::distance (first: row.begin (), last: row.beginNonZeros ());
184 QVector<int>::iterator pos = info.begin ();
185
186 while (pos != info.end ())
187 {
188 if (pos == info.begin ())
189 {
190 // try to find a perfect match
191 QVector<int>::iterator pm = std::search (first1: pos, last1: info.end (), first2: row.beginNonZeros (), last2: row.endNonZeros (), predicate: _PerfectMatch ());
192
193 if (pm != info.end ())
194 {
195 pos = pm;
196 break;
197 }
198 }
199
200 pos = std::search (first1: pos, last1: info.end (), first2: row.beginNonZeros (), last2: row.endNonZeros (), predicate: _Fit ());
201
202 if (pos == info.end ())
203 break;
204
205 int idx = std::distance (first: info.begin (), last: pos) - first_token;
206 bool conflict = false;
207
208 for (int j = 0; ! conflict && j < row.size (); ++j)
209 {
210 if (row.at (index: j) == 0)
211 conflict |= idx + j >= 0 && check [idx + j] == j;
212
213 else
214 conflict |= check [idx + j] == j;
215 }
216
217 if (! conflict)
218 break;
219
220 ++pos;
221 }
222
223 if (pos == info.end ())
224 {
225 int size = info.size ();
226
227 info.resize (asize: info.size () + row.nonZeroElements ());
228 check.resize (asize: info.size ());
229
230 std::fill (first: check.begin () + size, last: check.end (), value: -1);
231 pos = info.begin () + size;
232 }
233
234 int offset = std::distance (first: info.begin (), last: pos);
235 index [row.index ()] = offset - first_token;
236
237 for (const int *it = row.beginNonZeros (); it != row.endNonZeros (); ++it, ++pos)
238 {
239 if (*it)
240 *pos = *it;
241 }
242
243 int i = row.index ();
244
245 for (int j = 0; j < row.size (); ++j)
246 {
247 if (row.at (index: j) == 0)
248 continue;
249
250 check [index [i] + j] = j;
251 }
252 }
253
254#if 0
255 for (const UncompressedRow &row : qAsConst(sortedTable))
256 {
257 int i = row.index ();
258 Q_ASSERT (i < sortedTable.size ());
259
260 for (int j = 0; j < row.size (); ++j)
261 {
262 if (row.at (j) == 0)
263 {
264 Q_ASSERT (index [i] + j < 0 || check [index [i] + j] != j);
265 continue;
266 }
267
268 Q_ASSERT ( info [index [i] + j] == row.at (j));
269 Q_ASSERT (check [index [i] + j] == j);
270 }
271 }
272#endif
273}
274

source code of qtbase/src/tools/qlalr/compress.cpp