sc/source/core/data/compressedarray.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: compressedarray.cxx,v $
  10  * $Revision: 1.10.32.1 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_sc.hxx"
  33
  34 #include "compressedarray.hxx"
  35 #include "address.hxx"
  36
  37 #include <algorithm>
  38
  39 template< typename A, typename D >
  40 ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D& rValue,
  41         size_t nDeltaP )
  42     : nCount(1)
  43     , nLimit(1)
  44     , nDelta( nDeltaP > 0 ? nDeltaP : 1)
  45     , pData( new DataEntry[1])
  46     , nMaxAccess( nMaxAccessP)
  47 {
  48     pData[0].aValue = rValue;
  49     pData[0].nEnd = nMaxAccess;
  50 }
  51
  52
  53 template< typename A, typename D >
  54 ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D* pDataArray,
  55         size_t nDataCount )
  56     : nCount(0)
  57     , nLimit( nDataCount)
  58     , nDelta( nScCompressedArrayDelta)
  59     , pData( new DataEntry[nDataCount])
  60     , nMaxAccess( nMaxAccessP)
  61 {
  62     D aValue = pDataArray[0];
  63     for (size_t j=0; j<nDataCount; ++j)
  64     {
  65         if (!(aValue == pDataArray[j]))
  66         {
  67             pData[nCount].aValue = aValue;
  68             pData[nCount].nEnd = j-1;
  69             ++nCount;
  70             aValue = pDataArray[j];
  71         }
  72     }
  73     pData[nCount].aValue = aValue;
  74     pData[nCount].nEnd = nMaxAccess;
  75     ++nCount;
  76     Resize( nCount);
  77 }
  78
  79
  80 template< typename A, typename D >
  81 ScCompressedArray<A,D>::~ScCompressedArray()
  82 {
  83     delete[] pData;
  84 }
  85
  86
  87 template< typename A, typename D >
  88 void ScCompressedArray<A,D>::Resize( size_t nNewLimit)
  89 {
  90     if ((nCount <= nNewLimit && nNewLimit < nLimit) || nLimit < nNewLimit)
  91     {
  92         nLimit = nNewLimit;
  93         DataEntry* pNewData = new DataEntry[nLimit];
  94         memcpy( pNewData, pData, nCount*sizeof(DataEntry));
  95         delete[] pData;
  96         pData = pNewData;
  97     }
  98 }
  99
 100
 101 template< typename A, typename D >
 102 size_t ScCompressedArray<A,D>::Search( A nAccess ) const
 103 {
 104     if (nAccess == 0)
 105         return 0;
 106
 107     long nLo    = 0;
 108     long nHi    = static_cast<long>(nCount) - 1;
 109     long nStart = 0;
 110     long nEnd   = 0;
 111     long i      = 0;
 112     bool bFound = (nCount == 1);
 113     while (!bFound && nLo <= nHi)
 114     {
 115         i = (nLo + nHi) / 2;
 116         if (i > 0)
 117             nStart = (long) pData[i - 1].nEnd;
 118         else
 119             nStart = -1;
 120         nEnd = (long) pData[i].nEnd;
 121         if (nEnd < (long) nAccess)
 122             nLo = ++i;
 123         else
 124             if (nStart >= (long) nAccess)
 125                 nHi = --i;
 126             else
 127                 bFound = true;
 128     }
 129     return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
 130 }
 131
 132
 133 template< typename A, typename D >
 134 void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
 135 {
 136     if (0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
 137             && nStart <= nEnd)
 138     {
 139         if ((nStart == 0) && (nEnd == nMaxAccess))
 140             Reset( rValue);
 141         else
 142         {
 143             // Create a temporary copy in case we got a reference passed that
 144             // points to a part of the array to be reallocated.
 145             D aNewVal( rValue);
 146             size_t nNeeded = nCount + 2;
 147             if (nLimit < nNeeded)
 148             {
 149                 nLimit += nDelta;
 150                 if (nLimit < nNeeded)
 151                     nLimit = nNeeded;
 152                 DataEntry* pNewData = new DataEntry[nLimit];
 153                 memcpy( pNewData, pData, nCount*sizeof(DataEntry));
 154                 delete[] pData;
 155                 pData = pNewData;
 156             }
 157
 158             size_t ni;          // number of leading entries
 159             size_t nInsert;     // insert position (nMaxAccess+1 := no insert)
 160             bool bCombined = false;
 161             bool bSplit = false;
 162             if (nStart > 0)
 163             {
 164                 // skip leading
 165                 ni = Search( nStart);
 166
 167                 nInsert = nMaxAccess+1;
 168                 if (!(pData[ni].aValue == aNewVal))
 169                 {
 170                     if (ni == 0 || (pData[ni-1].nEnd < nStart - 1))
 171                     {   // may be a split or a simple insert or just a shrink,
 172                         // row adjustment is done further down
 173                         if (pData[ni].nEnd > nEnd)
 174                             bSplit = true;
 175                         ni++;
 176                         nInsert = ni;
 177                     }
 178                     else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
 179                         nInsert = ni;
 180                 }
 181                 if (ni > 0 && pData[ni-1].aValue == aNewVal)
 182                 {   // combine
 183                     pData[ni-1].nEnd = nEnd;
 184                     nInsert = nMaxAccess+1;
 185                     bCombined = true;
 186                 }
 187             }
 188             else
 189             {
 190                 nInsert = 0;
 191                 ni = 0;
 192             }
 193
 194             size_t nj = ni;     // stop position of range to replace
 195             while (nj < nCount && pData[nj].nEnd <= nEnd)
 196                 nj++;
 197             if (!bSplit)
 198             {
 199                 if (nj < nCount && pData[nj].aValue == aNewVal)
 200                 {   // combine
 201                     if (ni > 0)
 202                     {
 203                         if (pData[ni-1].aValue == aNewVal)
 204                         {   // adjacent entries
 205                             pData[ni-1].nEnd = pData[nj].nEnd;
 206                             nj++;
 207                         }
 208                         else if (ni == nInsert)
 209                             pData[ni-1].nEnd = nStart - 1;   // shrink
 210                     }
 211                     nInsert = nMaxAccess+1;
 212                     bCombined = true;
 213                 }
 214                 else if (ni > 0 && ni == nInsert)
 215                     pData[ni-1].nEnd = nStart - 1;   // shrink
 216             }
 217             if (ni < nj)
 218             {   // remove middle entries
 219                 if (!bCombined)
 220                 {   // replace one entry
 221                     pData[ni].nEnd = nEnd;
 222                     pData[ni].aValue = aNewVal;
 223                     ni++;
 224                     nInsert = nMaxAccess+1;
 225                 }
 226                 if (ni < nj)
 227                 {   // remove entries
 228                     memmove( pData + ni, pData + nj,
 229                             (nCount - nj) * sizeof(DataEntry));
 230                     nCount -= nj - ni;
 231                 }
 232             }
 233
 234             if (nInsert < static_cast<size_t>(nMaxAccess+1))
 235             {   // insert or append new entry
 236                 if (nInsert <= nCount)
 237                 {
 238                     if (!bSplit)
 239                         memmove( pData + nInsert + 1, pData + nInsert,
 240                                 (nCount - nInsert) * sizeof(DataEntry));
 241                     else
 242                     {
 243                         memmove( pData + nInsert + 2, pData + nInsert,
 244                                 (nCount - nInsert) * sizeof(DataEntry));
 245                         pData[nInsert+1] = pData[nInsert-1];
 246                         nCount++;
 247                     }
 248                 }
 249                 if (nInsert)
 250                     pData[nInsert-1].nEnd = nStart - 1;
 251                 pData[nInsert].nEnd = nEnd;
 252                 pData[nInsert].aValue = aNewVal;
 253                 nCount++;
 254             }
 255         }
 256     }
 257 }
 258
 259
 260 template< typename A, typename D >
 261 void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nStart,
 262         A nEnd, long nSourceDy )
 263 {
 264     size_t nIndex;
 265     A nRegionEnd;
 266     for (A j=nStart; j<=nEnd; ++j)
 267     {
 268         const D& rValue = (j==nStart ?
 269                 rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
 270                 rArray.GetNextValue( nIndex, nRegionEnd));
 271         nRegionEnd -= nSourceDy;
 272         if (nRegionEnd > nEnd)
 273             nRegionEnd = nEnd;
 274         SetValue( j, nRegionEnd, rValue);
 275         j = nRegionEnd;
 276     }
 277 }
 278
 279
 280 template< typename A, typename D >
 281 const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
 282 {
 283     size_t nIndex = Search( nStart);
 284     // No real insertion is needed, simply extend the one entry and adapt all
 285     // following. In case nStart points to the start row of an entry, extend
 286     // the previous entry (inserting before nStart).
 287     if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
 288         --nIndex;
 289     const D& rValue = pData[nIndex].aValue; // the value "copied"
 290     do
 291     {
 292         pData[nIndex].nEnd += nAccessCount;
 293         if (pData[nIndex].nEnd >= nMaxAccess)
 294         {
 295             pData[nIndex].nEnd = nMaxAccess;
 296             nCount = nIndex + 1;    // discard trailing entries
 297         }
 298     } while (++nIndex < nCount);
 299     return rValue;
 300 }
 301
 302
 303 template< typename A, typename D >
 304 void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
 305 {
 306     A nEnd = nStart + nAccessCount - 1;
 307     size_t nIndex = Search( nStart);
 308     // equalize/combine/remove all entries in between
 309     if (nEnd > pData[nIndex].nEnd)
 310         SetValue( nStart, nEnd, pData[nIndex].aValue);
 311     // remove an exactly matching entry by shifting up all following by one
 312     if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
 313             pData[nIndex].nEnd == nEnd && nIndex < nCount-1)
 314     {
 315         // In case removing an entry results in two adjacent entries with
 316         // identical data, combine them into one. This is also necessary to
 317         // make the algorithm used in SetValue() work correctly, it relies on
 318         // the fact that consecutive values actually differ.
 319         size_t nRemove;
 320         if (nIndex > 0 && pData[nIndex-1].aValue == pData[nIndex+1].aValue)
 321         {
 322             nRemove = 2;
 323             --nIndex;
 324         }
 325         else
 326             nRemove = 1;
 327         memmove( pData + nIndex, pData + nIndex + nRemove, (nCount - (nIndex +
 328                         nRemove)) * sizeof(DataEntry));
 329         nCount -= nRemove;
 330     }
 331     // adjust end rows, nIndex still being valid
 332     do
 333     {
 334         pData[nIndex].nEnd -= nAccessCount;
 335     } while (++nIndex < nCount);
 336     pData[nCount-1].nEnd = nMaxAccess;
 337 }
 338
 339
 340 template< typename A, typename D >
 341 A ScCompressedArray<A,D>::GetLastUnequalAccess( A nStart, const D& rCompare )
 342 {
 343     A nEnd = ::std::numeric_limits<A>::max();
 344     size_t nIndex = nCount-1;
 345     while (1)
 346     {
 347         if (pData[nIndex].aValue != rCompare)
 348         {
 349             nEnd = pData[nIndex].nEnd;
 350             break;  // while
 351         }
 352         else
 353         {
 354             if (nIndex > 0)
 355             {
 356                 --nIndex;
 357                 if (pData[nIndex].nEnd < nStart)
 358                     break;  // while
 359             }
 360             else
 361                 break;  // while
 362         }
 363     }
 364     return nEnd;
 365 }
 366
 367
 368 // === ScSummableCompressedArray =============================================
 369
 370 template< typename A, typename D >
 371 unsigned long ScSummableCompressedArray<A,D>::SumValues( A nStart, A nEnd ) const
 372 {
 373     size_t nIndex = Search( nStart);
 374     unsigned long nSum = SumValuesContinuation( nStart, nEnd, nIndex);
 375     if (nEnd > this->nMaxAccess)
 376         nSum += this->pData[this->nCount-1].aValue * (nEnd - this->nMaxAccess);
 377     return nSum;
 378 }
 379
 380
 381 template< typename A, typename D >
 382 unsigned long ScSummableCompressedArray<A,D>::SumValuesContinuation(
 383         A nStart, A nEnd, size_t& nIndex ) const
 384 {
 385     unsigned long nSum = 0;
 386     A nS = nStart;
 387     while (nIndex < this->nCount && nS <= nEnd)
 388     {
 389         A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
 390         // FIXME: test for overflow in a single region?
 391         unsigned long nNew = (unsigned long) this->pData[nIndex].aValue * (nE - nS + 1);
 392         nSum += nNew;
 393         if (nSum < nNew)
 394             return ::std::numeric_limits<unsigned long>::max();
 395         nS = nE + 1;
 396         if (nS <= nEnd)
 397             ++nIndex;
 398     }
 399     return nSum;
 400 }
 401
 402
 403 template< typename A, typename D >
 404 unsigned long ScSummableCompressedArray<A,D>::SumScaledValuesContinuation(
 405         A nStart, A nEnd, size_t& nIndex, double fScale ) const
 406 {
 407     unsigned long nSum = 0;
 408     A nS = nStart;
 409     while (nIndex < this->nCount && nS <= nEnd)
 410     {
 411         A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
 412         unsigned long nScaledVal = (unsigned long) (this->pData[nIndex].aValue * fScale);
 413         // FIXME: test for overflow in a single region?
 414         unsigned long nNew = nScaledVal * (nE - nS + 1);
 415         nSum += nNew;
 416         if (nSum < nNew)
 417             return ::std::numeric_limits<unsigned long>::max();
 418         nS = nE + 1;
 419         if (nS <= nEnd)
 420             ++nIndex;
 421     }
 422     return nSum;
 423 }
 424
 425
 426 // === ScBitMaskCompressedArray ==============================================
 427
 428 template< typename A, typename D >
 429 void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd,
 430         const D& rValueToAnd )
 431 {
 432     if (nStart > nEnd)
 433         return;
 434
 435     size_t nIndex = Search( nStart);
 436     do
 437     {
 438         if ((this->pData[nIndex].aValue & rValueToAnd) != this->pData[nIndex].aValue)
 439         {
 440             A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
 441             A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
 442             SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd);
 443             if (nE >= nEnd)
 444                 break;  // while
 445             nIndex = Search( nE + 1);
 446         }
 447         else if (this->pData[nIndex].nEnd >= nEnd)
 448             break;  // while
 449         else
 450             ++nIndex;
 451     } while (nIndex < this->nCount);
 452 }
 453
 454
 455 template< typename A, typename D >
 456 void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd,
 457         const D& rValueToOr )
 458 {
 459     if (nStart > nEnd)
 460         return;
 461
 462     size_t nIndex = Search( nStart);
 463     do
 464     {
 465         if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
 466         {
 467             A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
 468             A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
 469             SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
 470             if (nE >= nEnd)
 471                 break;  // while
 472             nIndex = Search( nE + 1);
 473         }
 474         else if (this->pData[nIndex].nEnd >= nEnd)
 475             break;  // while
 476         else
 477             ++nIndex;
 478     } while (nIndex < this->nCount);
 479 }
 480
 481
 482 template< typename A, typename D >
 483 void ScBitMaskCompressedArray<A,D>::CopyFromAnded(
 484         const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
 485         const D& rValueToAnd, long nSourceDy )
 486 {
 487     size_t nIndex;
 488     A nRegionEnd;
 489     for (A j=nStart; j<=nEnd; ++j)
 490     {
 491         const D& rValue = (j==nStart ?
 492                 rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
 493                 rArray.GetNextValue( nIndex, nRegionEnd));
 494         nRegionEnd -= nSourceDy;
 495         if (nRegionEnd > nEnd)
 496             nRegionEnd = nEnd;
 497         SetValue( j, nRegionEnd, rValue & rValueToAnd);
 498         j = nRegionEnd;
 499     }
 500 }
 501
 502
 503 template< typename A, typename D >
 504 void ScBitMaskCompressedArray<A,D>::CopyFromOred(
 505         const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
 506         const D& rValueToOr, long nSourceDy )
 507 {
 508     size_t nIndex;
 509     A nRegionEnd;
 510     for (A j=nStart; j<=nEnd; ++j)
 511     {
 512         const D& rValue = (j==nStart ?
 513                 rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
 514                 rArray.GetNextValue( nIndex, nRegionEnd));
 515         nRegionEnd -= nSourceDy;
 516         if (nRegionEnd > nEnd)
 517             nRegionEnd = nEnd;
 518         SetValue( j, nRegionEnd, rValue | rValueToOr);
 519         j = nRegionEnd;
 520     }
 521 }
 522
 523
 524 template< typename A, typename D >
 525 A ScBitMaskCompressedArray<A,D>::GetBitStateStart( A nEnd,
 526         const D& rBitMask, const D& rMaskedCompare ) const
 527 {
 528     A nStart = ::std::numeric_limits<A>::max();
 529     size_t nIndex = Search( nEnd);
 530     while ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
 531     {
 532         if (nIndex > 0)
 533         {
 534             --nIndex;
 535             nStart = this->pData[nIndex].nEnd + 1;
 536         }
 537         else
 538         {
 539             nStart = 0;
 540             break;  // while
 541         }
 542     }
 543     return nStart;
 544 }
 545
 546
 547 template< typename A, typename D >
 548 A ScBitMaskCompressedArray<A,D>::GetBitStateEnd( A nStart,
 549         const D& rBitMask, const D& rMaskedCompare ) const
 550 {
 551     A nEnd = ::std::numeric_limits<A>::max();
 552     size_t nIndex = Search( nStart);
 553     while (nIndex < this->nCount && (this->pData[nIndex].aValue & rBitMask) ==
 554             rMaskedCompare)
 555     {
 556         nEnd = this->pData[nIndex].nEnd;
 557         ++nIndex;
 558     }
 559     return nEnd;
 560 }
 561
 562
 563 template< typename A, typename D >
 564 A ScBitMaskCompressedArray<A,D>::GetFirstForCondition( A nStart, A nEnd,
 565         const D& rBitMask, const D& rMaskedCompare ) const
 566 {
 567     size_t nIndex = Search( nStart);
 568     do
 569     {
 570         if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
 571         {
 572             A nFound = nIndex > 0 ? this->pData[nIndex-1].nEnd + 1 : 0;
 573             return ::std::max( nFound, nStart);
 574         }
 575         if (this->pData[nIndex].nEnd >= nEnd)
 576             break;  // while
 577         ++nIndex;
 578     } while (nIndex < this->nCount);
 579     return ::std::numeric_limits<A>::max();
 580 }
 581
 582
 583 template< typename A, typename D >
 584 A ScBitMaskCompressedArray<A,D>::GetLastForCondition( A nStart, A nEnd,
 585         const D& rBitMask, const D& rMaskedCompare ) const
 586 {
 587     size_t nIndex = Search( nEnd);
 588     while (1)
 589     {
 590         if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
 591             return ::std::min( this->pData[nIndex].nEnd, nEnd);
 592
 593         if (nIndex > 0)
 594         {
 595             --nIndex;
 596             if (this->pData[nIndex].nEnd < nStart)
 597                 break;  // while
 598         }
 599         else
 600             break;  // while
 601     }
 602     return ::std::numeric_limits<A>::max();
 603 }
 604
 605
 606 template< typename A, typename D >
 607 A ScBitMaskCompressedArray<A,D>::CountForCondition( A nStart, A nEnd,
 608         const D& rBitMask, const D& rMaskedCompare ) const
 609 {
 610     A nRet = 0;
 611     size_t nIndex = Search( nStart);
 612     do
 613     {
 614         if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
 615         {
 616             A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
 617             A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
 618             nRet += nE - nS + 1;
 619         }
 620         if (this->pData[nIndex].nEnd >= nEnd)
 621             break;  // while
 622         ++nIndex;
 623     } while (nIndex < this->nCount);
 624     return nRet;
 625 }
 626
 627
 628 template< typename A, typename D >
 629 size_t ScBitMaskCompressedArray<A,D>::FillArrayForCondition( A nStart, A nEnd,
 630         const D& rBitMask, const D& rMaskedCompare,
 631         A * pArray, size_t nArraySize ) const
 632 {
 633     size_t nUsed = 0;
 634     size_t nIndex = Search( nStart);
 635     while (nIndex < this->nCount && nUsed < nArraySize)
 636     {
 637         if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
 638         {
 639             A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
 640             A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
 641             while (nS <= nE && nUsed < nArraySize)
 642                 pArray[nUsed++] = nS++;
 643         }
 644         if (this->pData[nIndex].nEnd >= nEnd)
 645             break;  // while
 646         ++nIndex;
 647     }
 648     return nUsed;
 649 }
 650
 651
 652 template< typename A, typename D >
 653 bool ScBitMaskCompressedArray<A,D>::HasCondition( A nStart, A nEnd,
 654         const D& rBitMask, const D& rMaskedCompare ) const
 655 {
 656     size_t nIndex = Search( nStart);
 657     do
 658     {
 659         if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
 660             return true;
 661         if (this->pData[nIndex].nEnd >= nEnd)
 662             break;  // while
 663         ++nIndex;
 664     }  while (nIndex < this->nCount);
 665     return false;
 666 }
 667
 668
 669 template< typename A, typename D >
 670 A ScBitMaskCompressedArray<A,D>::CountForAnyBitCondition( A nStart, A nEnd,
 671         const D& rBitMask ) const
 672 {
 673     A nRet = 0;
 674     size_t nIndex = Search( nStart);
 675     do
 676     {
 677         if ((this->pData[nIndex].aValue & rBitMask) != 0)
 678         {
 679             A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
 680             A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
 681             nRet += nE - nS + 1;
 682         }
 683         if (this->pData[nIndex].nEnd >= nEnd)
 684             break;  // while
 685         ++nIndex;
 686     } while (nIndex < this->nCount);
 687     return nRet;
 688 }
 689
 690
 691 template< typename A, typename D >
 692 A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( A nStart,
 693         const D& rBitMask ) const
 694 {
 695     A nEnd = ::std::numeric_limits<A>::max();
 696     size_t nIndex = this->nCount-1;
 697     while (1)
 698     {
 699         if ((this->pData[nIndex].aValue & rBitMask) != 0)
 700         {
 701             nEnd = this->pData[nIndex].nEnd;
 702             break;  // while
 703         }
 704         else
 705         {
 706             if (nIndex > 0)
 707             {
 708                 --nIndex;
 709                 if (this->pData[nIndex].nEnd < nStart)
 710                     break;  // while
 711             }
 712             else
 713                 break;  // while
 714         }
 715     }
 716     return nEnd;
 717 }
 718
 719
 720 template< typename A, typename D >
 721 template< typename S >
 722 unsigned long ScBitMaskCompressedArray<A,D>::SumCoupledArrayForCondition(
 723         A nStart, A nEnd, const D& rBitMask, const D& rMaskedCompare,
 724         const ScSummableCompressedArray<A,S>& rArray ) const
 725 {
 726     unsigned long nSum = 0;
 727     A nS = nStart;
 728     size_t nIndex1 = Search( nStart);
 729     size_t nIndex2 = rArray.Search( nStart);
 730     do
 731     {
 732         if ((this->pData[nIndex1].aValue & rBitMask) == rMaskedCompare)
 733         {
 734             while (nIndex2 < rArray.GetEntryCount() &&
 735                     rArray.GetDataEntry(nIndex2).nEnd < nS)
 736                 ++nIndex2;
 737             unsigned long nNew = rArray.SumValuesContinuation( nS,
 738                     ::std::min( this->pData[nIndex1].nEnd, nEnd), nIndex2);
 739             nSum += nNew;
 740             if (nSum < nNew)
 741                 return ::std::numeric_limits<unsigned long>::max();
 742         }
 743         nS = this->pData[nIndex1].nEnd + 1;
 744         ++nIndex1;
 745     } while (nIndex1 < this->nCount && nS <= nEnd);
 746     if (nEnd > this->nMaxAccess &&
 747             (this->pData[this->GetEntryCount()-1].aValue & rBitMask) == rMaskedCompare)
 748         nSum += rArray.GetDataEntry(rArray.GetEntryCount()-1).aValue * (nEnd -
 749                 this->nMaxAccess);
 750     return nSum;
 751 }
 752
 753
 754 template< typename A, typename D >
 755 template< typename S >
 756 unsigned long ScBitMaskCompressedArray<A,D>::SumScaledCoupledArrayForCondition(
 757         A nStart, A nEnd, const D& rBitMask, const D& rMaskedCompare,
 758         const ScSummableCompressedArray<A,S>& rArray, double fScale ) const
 759 {
 760     unsigned long nSum = 0;
 761     A nS = nStart;
 762     size_t nIndex1 = Search( nStart);
 763     size_t nIndex2 = rArray.Search( nStart);
 764     do
 765     {
 766         if ((this->pData[nIndex1].aValue & rBitMask) == rMaskedCompare)
 767         {
 768             while (nIndex2 < rArray.GetEntryCount() &&
 769                     rArray.GetDataEntry(nIndex2).nEnd < nS)
 770                 ++nIndex2;
 771             unsigned long nNew = rArray.SumScaledValuesContinuation( nS,
 772                     ::std::min( this->pData[nIndex1].nEnd, nEnd), nIndex2, fScale);
 773             nSum += nNew;
 774             if (nSum < nNew)
 775                 return ::std::numeric_limits<unsigned long>::max();
 776         }
 777         nS = this->pData[nIndex1].nEnd + 1;
 778         ++nIndex1;
 779     } while (nIndex1 < this->nCount && nS <= nEnd);
 780     if (nEnd > this->nMaxAccess &&
 781             (this->pData[this->GetEntryCount()-1].aValue & rBitMask) == rMaskedCompare)
 782         nSum += (unsigned long)
 783             (rArray.GetDataEntry(rArray.GetEntryCount()-1).aValue * fScale) *
 784             (nEnd - this->nMaxAccess);
 785     return nSum;
 786 }
 787
 788
 789 // === ScCompressedArrayIterator =============================================
 790
 791 template< typename A, typename D >
 792 template< typename X >
 793 void ScCompressedArrayIterator<A,D>::Follow(
 794         const ScCompressedArrayIterator<A,X>& rIter )
 795 {
 796     nCurrent = rIter.GetPos();
 797     if (GetRangeStart() <= nCurrent && nCurrent <= GetRangeEnd())
 798         ; // nothing
 799     else if (nCurrent > GetRangeEnd())
 800     {
 801         A nPos = nCurrent;  // nCurrent gets changed in NextRange()
 802         bool bAdv;
 803         do
 804         {
 805             bAdv = NextRange();
 806         } while (bAdv && GetRangeEnd() < nPos);
 807         nCurrent = nPos;
 808     }
 809     else
 810         nIndex = rArray.Search( nCurrent);
 811 }
 812
 813
 814 // === ScCoupledCompressedArrayIterator ======================================
 815
 816 template< typename A, typename D, typename S >
 817 ScCoupledCompressedArrayIterator<A,D,S>::ScCoupledCompressedArrayIterator(
 818         const ScBitMaskCompressedArray<A,D> & rArray1, A nStart, A nEnd,
 819         const D& rBitMaskP, const D& rMaskedCompareP,
 820         const ScCompressedArray<A,S> & rArray2 )
 821     : aIter1( rArray1, nStart, nEnd )
 822     , aIter2( rArray2, nStart, nEnd )
 823     , rBitMask( rBitMaskP )
 824     , rMaskedCompare( rMaskedCompareP )
 825 {
 826     InitLimits();
 827 }
 828
 829
 830 template< typename A, typename D, typename S >
 831 void ScCoupledCompressedArrayIterator<A,D,S>::InitLimits()
 832 {
 833     bool bFound = true;
 834     bool bMoved = false;
 835     while (bFound && ((*aIter1 & rBitMask) != rMaskedCompare))
 836     {
 837         bFound = aIter1.NextRange();
 838         bMoved = true;
 839     }
 840     if (bMoved && bFound)
 841         aIter2.Follow( aIter1);
 842 }
 843
 844
 845 template< typename A, typename D, typename S >
 846 void ScCoupledCompressedArrayIterator<A,D,S>::NewLimits( A nStart, A nEnd )
 847 {
 848     aIter1.NewLimits( nStart, nEnd);
 849     aIter2.NewLimits( nStart, nEnd);
 850     InitLimits();
 851 }
 852
 853
 854 template< typename A, typename D, typename S >
 855 bool ScCoupledCompressedArrayIterator<A,D,S>::NextRange()
 856 {
 857     bool bAdv;
 858     if (aIter1.GetRangeEnd() <= aIter2.GetRangeEnd())
 859     {
 860         // Advance bit mask array until condition is met, coupled array
 861         // follows.
 862         do
 863         {
 864             bAdv = aIter1.NextRange();
 865         } while (bAdv && ((*aIter1 & rBitMask) != rMaskedCompare));
 866         if (bAdv)
 867             aIter2.Follow( aIter1);
 868     }
 869     else
 870     {
 871         // Make coupled array catch up with bit mask array.
 872         do
 873         {
 874             bAdv = aIter2.NextRange();
 875         } while (bAdv && aIter2.GetRangeEnd() < aIter1.GetRangeStart());
 876         if (bAdv)
 877             aIter1.Follow( aIter2);     // synchronize aIter1.nCurrent
 878     }
 879     return operator bool();
 880 }
 881
 882
 883 template< typename A, typename D, typename S >
 884 void ScCoupledCompressedArrayIterator<A,D,S>::Resync( A nPos )
 885 {
 886     aIter1.Resync( nPos);
 887     aIter2.Resync( nPos);
 888     InitLimits();
 889 }
 890
 891
 892 // === Force instantiation of specializations ================================
 893
 894 template class ScCompressedArray< SCROW, USHORT>;           // heights, base class
 895 template class ScSummableCompressedArray< SCROW, USHORT>;   // heights
 896 template class ScCompressedArray< SCROW, BYTE>;             // flags, base class
 897 template class ScBitMaskCompressedArray< SCROW, BYTE>;      // flags
 898 template unsigned long ScBitMaskCompressedArray< SCROW,
 899     BYTE>::SumCoupledArrayForCondition( SCROW, SCROW, const BYTE&, const BYTE&,
 900             const ScSummableCompressedArray< SCROW, USHORT>&) const;
 901 template unsigned long ScBitMaskCompressedArray< SCROW,
 902     BYTE>::SumScaledCoupledArrayForCondition( SCROW, SCROW, const BYTE&,
 903             const BYTE&, const ScSummableCompressedArray< SCROW, USHORT>&,
 904             double) const;
 905 template void ScCompressedArrayIterator< SCROW, USHORT>::Follow(
 906         const ScCompressedArrayIterator< SCROW, BYTE>&);
 907 template class ScCoupledCompressedArrayIterator< SCROW, BYTE, USHORT>;
 908
 909 // === EOF ===================================================================