basegfx/source/inc/hommatrixtemplate.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #ifndef INCLUDED_BASEGFX_SOURCE_INC_HOMMATRIXTEMPLATE_HXX
  21 #define INCLUDED_BASEGFX_SOURCE_INC_HOMMATRIXTEMPLATE_HXX
  22
  23 #include <sal/types.h>
  24 #include <basegfx/numeric/ftools.hxx>
  25 #include <cmath>
  26 #include <string.h>
  27
  28 #include <memory>
  29
  30 namespace basegfx
  31 {
  32     namespace internal
  33     {
  34
  35         inline double implGetDefaultValue(sal_uInt16 nRow, sal_uInt16 nColumn)
  36         {
  37             if(nRow == nColumn)
  38                 return 1.0;
  39             return 0.0;
  40         }
  41
  42         template < sal_uInt16 RowSize > class ImplMatLine
  43         {
  44             double                                          mfValue[RowSize];
  45
  46         public:
  47             ImplMatLine()
  48             {
  49             }
  50
  51             explicit ImplMatLine(sal_uInt16 nRow, ImplMatLine< RowSize >* pToBeCopied)
  52             {
  53                 if(pToBeCopied)
  54                 {
  55                     memcpy(&mfValue, pToBeCopied, sizeof(double) * RowSize);
  56                 }
  57                 else
  58                 {
  59                     for(sal_uInt16 a(0); a < RowSize; a++)
  60                     {
  61                         mfValue[a] = implGetDefaultValue(nRow, a);
  62                     }
  63                 }
  64             }
  65
  66             double get(sal_uInt16 nColumn) const
  67             {
  68                 return mfValue[nColumn];
  69             }
  70
  71             void set(sal_uInt16 nColumn, const double& rValue)
  72             {
  73                 mfValue[nColumn] = rValue;
  74             }
  75         };
  76
  77         template < sal_uInt16 RowSize > class ImplHomMatrixTemplate
  78         {
  79             ImplMatLine< RowSize >                          maLine[RowSize - 1];
  80             std::unique_ptr<ImplMatLine< RowSize >> mutable mpLine;
  81
  82         public:
  83             // Is last line used?
  84             bool isLastLineDefault() const
  85             {
  86                 if(!mpLine)
  87                     return true;
  88
  89                 for(sal_uInt16 a(0); a < RowSize; a++)
  90                 {
  91                     const double fDefault(implGetDefaultValue((RowSize - 1), a));
  92                     const double fLineValue(mpLine->get(a));
  93
  94                     if(!::basegfx::fTools::equal(fDefault, fLineValue))
  95                     {
  96                         return false;
  97                     }
  98                 }
  99
 100                 // reset last line, it equals default
 101                 mpLine.reset();
 102
 103                 return true;
 104             }
 105
 106             ImplHomMatrixTemplate()
 107             {
 108                 // complete initialization with identity matrix, all lines
 109                 // were initialized with a trailing 1 followed by 0's.
 110                 for(sal_uInt16 a(0); a < RowSize-1; a++)
 111                 {
 112                     for(sal_uInt16 b(0); b < RowSize; b++)
 113                         maLine[a].set(b, implGetDefaultValue(a, b) );
 114                 }
 115             }
 116
 117             ImplHomMatrixTemplate(const ImplHomMatrixTemplate& rToBeCopied)
 118             {
 119                 operator=(rToBeCopied);
 120             }
 121
 122             ImplHomMatrixTemplate& operator=(const ImplHomMatrixTemplate& rToBeCopied)
 123             {
 124                 if (this != &rToBeCopied)
 125                 {
 126                     // complete initialization using copy
 127                     for(sal_uInt16 a(0); a < (RowSize - 1); a++)
 128                     {
 129                         memcpy(&maLine[a], &rToBeCopied.maLine[a], sizeof(ImplMatLine< RowSize >));
 130                     }
 131                     if(rToBeCopied.mpLine)
 132                     {
 133                         mpLine.reset( new ImplMatLine< RowSize >((RowSize - 1), rToBeCopied.mpLine.get()) );
 134                     }
 135                 }
 136                 return *this;
 137             }
 138
 139             static sal_uInt16 getEdgeLength() { return RowSize; }
 140
 141             double get(sal_uInt16 nRow, sal_uInt16 nColumn) const
 142             {
 143                 if(nRow < (RowSize - 1))
 144                 {
 145                     return maLine[nRow].get(nColumn);
 146                 }
 147
 148                 if(mpLine)
 149                 {
 150                     return mpLine->get(nColumn);
 151                 }
 152
 153                 return implGetDefaultValue((RowSize - 1), nColumn);
 154             }
 155
 156             void set(sal_uInt16 nRow, sal_uInt16 nColumn, const double& rValue)
 157             {
 158                 if(nRow < (RowSize - 1))
 159                 {
 160                     maLine[nRow].set(nColumn, rValue);
 161                 }
 162                 else if(mpLine)
 163                 {
 164                     mpLine->set(nColumn, rValue);
 165                 }
 166                 else
 167                 {
 168                     const double fDefault(implGetDefaultValue((RowSize - 1), nColumn));
 169
 170                     if(!::basegfx::fTools::equal(fDefault, rValue))
 171                     {
 172                         mpLine.reset(new ImplMatLine< RowSize >((RowSize - 1), nullptr));
 173                         mpLine->set(nColumn, rValue);
 174                     }
 175                 }
 176             }
 177
 178             void testLastLine()
 179             {
 180                 if(mpLine)
 181                 {
 182                     bool bNecessary(false);
 183
 184                     for(sal_uInt16 a(0);!bNecessary && a < RowSize; a++)
 185                     {
 186                         const double fDefault(implGetDefaultValue((RowSize - 1), a));
 187                         const double fLineValue(mpLine->get(a));
 188
 189                         if(!::basegfx::fTools::equal(fDefault, fLineValue))
 190                         {
 191                             bNecessary = true;
 192                         }
 193                     }
 194
 195                     if(!bNecessary)
 196                     {
 197                         mpLine.reset();
 198                     }
 199                 }
 200             }
 201
 202             // Left-upper decomposition
 203             bool ludcmp(sal_uInt16 nIndex[], sal_Int16& nParity)
 204             {
 205                 double fBig, fSum, fDum;
 206                 double fStorage[RowSize];
 207                 sal_uInt16 a, b, c;
 208
 209                 // #i30874# Initialize nAMax (compiler warns)
 210                 sal_uInt16 nAMax = 0;
 211
 212                 nParity = 1;
 213
 214                 // Calc the max of each line. If a line is empty,
 215                 // stop immediately since matrix is not invertible then.
 216                 for(a = 0; a < RowSize; a++)
 217                 {
 218                     fBig = 0.0;
 219
 220                     for(b = 0; b < RowSize; b++)
 221                     {
 222                         double fTemp(fabs(get(a, b)));
 223
 224                         if(::basegfx::fTools::more(fTemp, fBig))
 225                         {
 226                             fBig = fTemp;
 227                         }
 228                     }
 229
 230                     if(::basegfx::fTools::equalZero(fBig))
 231                     {
 232                         return false;
 233                     }
 234
 235                     fStorage[a] = 1.0 / fBig;
 236                 }
 237
 238                 // start normalizing
 239                 for(b = 0; b < RowSize; b++)
 240                 {
 241                     for(a = 0; a < b; a++)
 242                     {
 243                         fSum = get(a, b);
 244
 245                         for(c = 0; c < a; c++)
 246                         {
 247                             fSum -= get(a, c) * get(c, b);
 248                         }
 249
 250                         set(a, b, fSum);
 251                     }
 252
 253                     fBig = 0.0;
 254
 255                     for(a = b; a < RowSize; a++)
 256                     {
 257                         fSum = get(a, b);
 258
 259                         for(c = 0; c < b; c++)
 260                         {
 261                             fSum -= get(a, c) * get(c, b);
 262                         }
 263
 264                         set(a, b, fSum);
 265                         fDum = fStorage[a] * fabs(fSum);
 266
 267                         if(::basegfx::fTools::moreOrEqual(fDum, fBig))
 268                         {
 269                             fBig = fDum;
 270                             nAMax = a;
 271                         }
 272                     }
 273
 274                     if(b != nAMax)
 275                     {
 276                         for(c = 0; c < RowSize; c++)
 277                         {
 278                             fDum = get(nAMax, c);
 279                             set(nAMax, c, get(b, c));
 280                             set(b, c, fDum);
 281                         }
 282
 283                         nParity = -nParity;
 284                         fStorage[nAMax] = fStorage[b];
 285                     }
 286
 287                     nIndex[b] = nAMax;
 288
 289                     // here the failure of precision occurs
 290                     const double fValBB(fabs(get(b, b)));
 291
 292                     if(::basegfx::fTools::equalZero(fValBB))
 293                     {
 294                         return false;
 295                     }
 296
 297                     if(b != (RowSize - 1))
 298                     {
 299                         fDum = 1.0 / get(b, b);
 300
 301                         for(a = b + 1; a < RowSize; a++)
 302                         {
 303                             set(a, b, get(a, b) * fDum);
 304                         }
 305                     }
 306                 }
 307
 308                 return true;
 309             }
 310
 311             void lubksb(const sal_uInt16 nIndex[], double fRow[]) const
 312             {
 313                 sal_uInt16 b, ip;
 314                 sal_Int16 a, a2 = -1;
 315                 double fSum;
 316
 317                 for(a = 0; a < RowSize; a++)
 318                 {
 319                     ip = nIndex[a];
 320                     fSum = fRow[ip];
 321                     fRow[ip] = fRow[a];
 322
 323                     if(a2 >= 0)
 324                     {
 325                         for(b = a2; b < a; b++)
 326                         {
 327                             fSum -= get(a, b) * fRow[b];
 328                         }
 329                     }
 330                     else if(!::basegfx::fTools::equalZero(fSum))
 331                     {
 332                         a2 = a;
 333                     }
 334
 335                     fRow[a] = fSum;
 336                 }
 337
 338                 for(a = (RowSize - 1); a >= 0; a--)
 339                 {
 340                     fSum = fRow[a];
 341
 342                     for(b = a + 1; b < RowSize; b++)
 343                     {
 344                         fSum -= get(a, b) * fRow[b];
 345                     }
 346
 347                     const double fValueAA(get(a, a));
 348
 349                     if(!::basegfx::fTools::equalZero(fValueAA))
 350                     {
 351                         fRow[a] = fSum / get(a, a);
 352                     }
 353                 }
 354             }
 355
 356             bool isIdentity() const
 357             {
 358                 // last line needs no testing if not existing
 359                 const sal_uInt16 nMaxLine(
 360                     sal::static_int_cast<sal_uInt16>(mpLine ? RowSize : (RowSize - 1)) );
 361
 362                 for(sal_uInt16 a(0); a < nMaxLine; a++)
 363                 {
 364                     for(sal_uInt16 b(0); b < RowSize; b++)
 365                     {
 366                         const double fDefault(implGetDefaultValue(a, b));
 367                         const double fValueAB(get(a, b));
 368
 369                         if(!::basegfx::fTools::equal(fDefault, fValueAB))
 370                         {
 371                             return false;
 372                         }
 373                     }
 374                 }
 375
 376                 return true;
 377             }
 378
 379             bool isInvertible() const
 380             {
 381                 ImplHomMatrixTemplate aWork(*this);
 382                 sal_uInt16 nIndex[RowSize];
 383                 sal_Int16 nParity;
 384
 385                 return aWork.ludcmp(nIndex, nParity);
 386             }
 387
 388             void doInvert(const ImplHomMatrixTemplate& rWork, const sal_uInt16 nIndex[])
 389             {
 390                 double fArray[RowSize];
 391
 392                 for(sal_uInt16 a(0); a < RowSize; a++)
 393                 {
 394                     // prepare line
 395                     sal_uInt16 b;
 396                     for( b = 0; b < RowSize; b++)
 397                     {
 398                         fArray[b] = implGetDefaultValue(a, b);
 399                     }
 400
 401                     // expand line
 402                     rWork.lubksb(nIndex, fArray);
 403
 404                     // copy line transposed to this matrix
 405                     for( b = 0; b < RowSize; b++)
 406                     {
 407                         set(b, a, fArray[b]);
 408                     }
 409                 }
 410
 411                 // evtl. get rid of last matrix line
 412                 testLastLine();
 413             }
 414
 415             double doDeterminant() const
 416             {
 417                 ImplHomMatrixTemplate aWork(*this);
 418                 sal_uInt16 nIndex[RowSize];
 419                 sal_Int16 nParity;
 420                 double fRetval(0.0);
 421
 422                 if(aWork.ludcmp(nIndex, nParity))
 423                 {
 424                     fRetval = static_cast<double>(nParity);
 425
 426                     // last line needs no multiply if not existing; default value would be 1.
 427                     const sal_uInt16 nMaxLine(
 428                         sal::static_int_cast<sal_uInt16>(aWork.mpLine ? RowSize : (RowSize - 1)) );
 429
 430                     for(sal_uInt16 a(0); a < nMaxLine; a++)
 431                     {
 432                         fRetval *= aWork.get(a, a);
 433                     }
 434                 }
 435
 436                 return fRetval;
 437             }
 438
 439             void doAddMatrix(const ImplHomMatrixTemplate& rMat)
 440             {
 441                 for(sal_uInt16 a(0); a < RowSize; a++)
 442                 {
 443                     for(sal_uInt16 b(0); b < RowSize; b++)
 444                     {
 445                         set(a, b, get(a, b) + rMat.get(a, b));
 446                     }
 447                 }
 448
 449                 testLastLine();
 450             }
 451
 452             void doSubMatrix(const ImplHomMatrixTemplate& rMat)
 453             {
 454                 for(sal_uInt16 a(0); a < RowSize; a++)
 455                 {
 456                     for(sal_uInt16 b(0); b < RowSize; b++)
 457                     {
 458                         set(a, b, get(a, b) - rMat.get(a, b));
 459                     }
 460                 }
 461
 462                 testLastLine();
 463             }
 464
 465             void doMulMatrix(const double& rfValue)
 466             {
 467                 for(sal_uInt16 a(0); a < RowSize; a++)
 468                 {
 469                     for(sal_uInt16 b(0); b < RowSize; b++)
 470                     {
 471                         set(a, b, get(a, b) * rfValue);
 472                     }
 473                 }
 474
 475                 testLastLine();
 476             }
 477
 478             void doMulMatrix(const ImplHomMatrixTemplate& rMat)
 479             {
 480                 // create a copy as source for the original values
 481                 const ImplHomMatrixTemplate aCopy(*this);
 482
 483                 // TODO: maybe optimize cases where last line is [0 0 1].
 484
 485                 double fValue(0.0);
 486
 487                 for(sal_uInt16 a(0); a < RowSize; ++a)
 488                 {
 489                     for(sal_uInt16 b(0); b < RowSize; ++b)
 490                     {
 491                         fValue = 0.0;
 492
 493                         for(sal_uInt16 c(0); c < RowSize; ++c)
 494                             fValue += aCopy.get(c, b) * rMat.get(a, c);
 495
 496                         set(a, b, fValue);
 497                     }
 498                 }
 499
 500                 testLastLine();
 501             }
 502
 503             bool isEqual(const ImplHomMatrixTemplate& rMat) const
 504             {
 505                 const sal_uInt16 nMaxLine(
 506                     sal::static_int_cast<sal_uInt16>((mpLine || rMat.mpLine) ? RowSize : (RowSize - 1)) );
 507
 508                 for(sal_uInt16 a(0); a < nMaxLine; a++)
 509                 {
 510                     for(sal_uInt16 b(0); b < RowSize; b++)
 511                     {
 512                         const double fValueA(get(a, b));
 513                         const double fValueB(rMat.get(a, b));
 514
 515                         if(!::basegfx::fTools::equal(fValueA, fValueB))
 516                         {
 517                             return false;
 518                         }
 519                     }
 520                 }
 521
 522                 return true;
 523             }
 524         };
 525
 526     } // namespace internal
 527 } // namespace basegfx
 528
 529 #endif // INCLUDED_BASEGFX_SOURCE_INC_HOMMATRIXTEMPLATE_HXX
 530
 531 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */