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 }