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