1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
3
4#include "compress.h"
5
6#include <QtCore/qdebug.h>
7#include <QtCore/qlist.h>
8
9#include <algorithm>
10#include <iterator>
11#include <iostream>
12
13#define QLALR_NO_CHECK_SORTED_TABLE
14
15struct _Fit
16{
17 inline bool operator () (int a, int b) const
18 {
19 return a == 0 || b == 0 || a == b;
20 }
21};
22
23struct _PerfectMatch
24{
25 inline bool operator () (int a, int b) const
26 { return a == b; }
27};
28
29struct _GenerateCheck
30{
31 QList<int>::const_iterator iterator;
32 int initial;
33
34 _GenerateCheck(QList<int>::const_iterator it, int i) : iterator(it), initial(i) { }
35
36 inline int operator()()
37 {
38 int check = initial++;
39 return *iterator++ ? check : -1;
40 }
41};
42
43class UncompressedRow
44{
45public:
46 typedef const int *const_iterator;
47 typedef const int *iterator;
48
49public:
50 inline UncompressedRow ():
51 _M_index (0),
52 _M_begin (nullptr),
53 _M_end (nullptr),
54 _M_beginNonZeros (nullptr),
55 _M_endNonZeros (nullptr) {}
56
57 inline UncompressedRow (int index, const_iterator begin, const_iterator end)
58 { assign (index, begin, end); }
59
60 inline int index () const { return _M_index; }
61 inline const_iterator begin () const { return _M_begin; }
62 inline const_iterator end () const { return _M_end; }
63
64 inline void assign (int index, const_iterator begin, const_iterator end)
65 {
66 _M_index = index;
67 _M_begin = begin;
68 _M_end = end;
69
70 _M_beginNonZeros = _M_begin;
71 _M_endNonZeros = _M_end;
72
73 for (_M_beginNonZeros = _M_begin; _M_beginNonZeros != _M_end && ! _M_beginNonZeros [0]; ++_M_beginNonZeros)
74 /*continue*/ ;
75
76#if 0
77 for (_M_endNonZeros = _M_end; _M_endNonZeros != _M_beginNonZeros && ! _M_endNonZeros [-1]; --_M_endNonZeros)
78 /*continue*/ ;
79#endif
80 }
81
82 inline int at (int index) const
83 { return _M_begin [index]; }
84
85 inline bool isEmpty () const
86 { return _M_begin == _M_end; }
87
88 inline int size () const
89 { return _M_end - _M_begin; }
90
91 inline int nonZeroElements () const
92 { return _M_endNonZeros - _M_beginNonZeros; }
93
94 inline int count (int value) const
95 { return std::count (first: begin (), last: end (), value: value); }
96
97 inline const_iterator beginNonZeros () const
98 { return _M_beginNonZeros; }
99
100 inline const_iterator endNonZeros () const
101 { return _M_endNonZeros; }
102
103private:
104 int _M_index;
105 const_iterator _M_begin;
106 const_iterator _M_end;
107 const_iterator _M_beginNonZeros;
108 const_iterator _M_endNonZeros;
109};
110
111struct _SortUncompressedRow
112{
113 inline bool operator () (const UncompressedRow &a, const UncompressedRow &b) const
114 { return a.count (value: 0) > b.count (value: 0); }
115};
116
117Compress::Compress ()
118{
119}
120
121void Compress::operator () (int *table, int row_count, int column_count)
122{
123 index.clear ();
124 info.clear ();
125 check.clear ();
126
127 QList<UncompressedRow> sortedTable(row_count);
128
129 for (int i = 0; i < row_count; ++i)
130 {
131 int *begin = &table [i * column_count];
132 int *end = begin + column_count;
133
134 sortedTable [i].assign (index: i, begin, end);
135 }
136
137 std::sort (first: sortedTable.begin (), last: sortedTable.end (), comp: _SortUncompressedRow ());
138
139#ifndef QLALR_NO_CHECK_SORTED_TABLE
140 int previous_zeros = INT_MAX;
141
142 for (const UncompressedRow &row : std::as_const(sortedTable))
143 {
144 int zeros = row.count (0);
145
146 Q_ASSERT (zeros <= previous_zeros);
147 zeros = previous_zeros;
148 qDebug () << "OK!";
149 }
150#endif
151
152 index.fill (t: -999999, newSize: row_count);
153
154 for (const UncompressedRow &row : std::as_const(t&: sortedTable))
155 {
156 int first_token = std::distance (first: row.begin (), last: row.beginNonZeros ());
157 QList<int>::iterator pos = info.begin();
158
159 while (pos != info.end ())
160 {
161 if (pos == info.begin ())
162 {
163 // try to find a perfect match
164 QList<int>::iterator pm = std::search(first1: pos, last1: info.end(), first2: row.beginNonZeros(),
165 last2: row.endNonZeros(), predicate: _PerfectMatch());
166
167 if (pm != info.end ())
168 {
169 pos = pm;
170 break;
171 }
172 }
173
174 pos = std::search (first1: pos, last1: info.end (), first2: row.beginNonZeros (), last2: row.endNonZeros (), predicate: _Fit ());
175
176 if (pos == info.end ())
177 break;
178
179 int idx = std::distance (first: info.begin (), last: pos) - first_token;
180 bool conflict = false;
181
182 for (int j = 0; ! conflict && j < row.size (); ++j)
183 {
184 if (row.at (index: j) == 0)
185 conflict |= idx + j >= 0 && check [idx + j] == j;
186
187 else
188 conflict |= check [idx + j] == j;
189 }
190
191 if (! conflict)
192 break;
193
194 ++pos;
195 }
196
197 if (pos == info.end ())
198 {
199 int size = info.size ();
200
201 info.resize (size: info.size () + row.nonZeroElements ());
202 check.resize (size: info.size ());
203
204 std::fill (first: check.begin () + size, last: check.end (), value: -1);
205 pos = info.begin () + size;
206 }
207
208 int offset = std::distance (first: info.begin (), last: pos);
209 index [row.index ()] = offset - first_token;
210
211 for (const int *it = row.beginNonZeros (); it != row.endNonZeros (); ++it, ++pos)
212 {
213 if (*it)
214 *pos = *it;
215 }
216
217 int i = row.index ();
218
219 for (int j = 0; j < row.size (); ++j)
220 {
221 if (row.at (index: j) == 0)
222 continue;
223
224 check [index [i] + j] = j;
225 }
226 }
227
228#if 0
229 for (const UncompressedRow &row : std::as_const(sortedTable))
230 {
231 int i = row.index ();
232 Q_ASSERT (i < sortedTable.size ());
233
234 for (int j = 0; j < row.size (); ++j)
235 {
236 if (row.at (j) == 0)
237 {
238 Q_ASSERT (index [i] + j < 0 || check [index [i] + j] != j);
239 continue;
240 }
241
242 Q_ASSERT ( info [index [i] + j] == row.at (j));
243 Q_ASSERT (check [index [i] + j] == j);
244 }
245 }
246#endif
247}
248

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