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