util/qlalr/compress.cpp

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