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 #ifndef SC_COMPRESSEDARRAY_HXX 25 #define SC_COMPRESSEDARRAY_HXX 26 27 #ifndef INCLUDED_CSTDDEF 28 #include <cstddef> 29 #define INCLUDED_CSTDDEF 30 #endif 31 32 #ifndef INCLUDED_ALGORITHM 33 #include <algorithm> 34 #define INCLUDED_ALGORITHM 35 #endif 36 #include "scdllapi.h" 37 38 const size_t nScCompressedArrayDelta = 4; 39 40 template< typename A, typename D > class ScCompressedArrayIterator; 41 42 /** Compressed array of row (or column) entries, e.g. heights, flags, ... 43 44 The array stores ranges of values such that consecutive values occupy only 45 one entry. Initially it consists of one DataEntry with an implied start 46 row/column of 0 and an end row/column of access type maximum value. 47 48 typename A := access type, e.g. SCROW or SCCOL, must be a POD. 49 50 typename D := data type, e.g. sal_uInt16 or sal_uInt8 or whatever, may also be a 51 struct or class. 52 53 D::operator==() and D::operator=() must be implemented. Force template 54 instantiation for a specific type in source/core/data/compressedarray.cxx 55 56 TODO: Currently the allocated memory never shrinks, must manually invoke 57 Resize() if needed. 58 */ 59 60 template< typename A, typename D > class ScCompressedArray 61 { 62 public: 63 struct DataEntry 64 { 65 A nEnd; // start is end of previous entry + 1 66 D aValue; 67 DataEntry() {} //! uninitialized 68 }; 69 70 /** Construct with nMaxAccess=MAXROW, for example. */ 71 ScCompressedArray( A nMaxAccess, 72 const D& rValue, 73 size_t nDelta = nScCompressedArrayDelta ); 74 /** Construct from a plain array of D */ 75 ScCompressedArray( A nMaxAccess, 76 const D* pDataArray, size_t nDataCount ); 77 virtual ~ScCompressedArray(); 78 void Resize( size_t nNewSize ); 79 void Reset( const D& rValue ); 80 void SetValue( A nPos, const D& rValue ); 81 void SetValue( A nStart, A nEnd, const D& rValue ); 82 const D& GetValue( A nPos ) const; 83 84 /** Get value for a row, and it's region end row */ 85 const D& GetValue( A nPos, size_t& nIndex, A& nEnd ) const; 86 87 /** Get value for a row, and it's region start row and end row */ 88 const D& GetValue( A nPos, size_t& nIndex, A& nStart, A& nEnd ) const; 89 90 /** Get next value and it's region end row. If nIndex<nCount, nIndex is 91 incremented first. If the resulting nIndex>=nCount, the value of the 92 last entry is returned again. */ 93 const D& GetNextValue( size_t& nIndex, A& nEnd ) const; 94 95 /** Get previous value and it's region start row. If nIndex==0, nIndex is 96 not decremented and the value of the first entry is returned again. */ 97 const D& GetPrevValue( size_t& nIndex, A& nStart ) const; 98 99 /** Return the last row where an entry meets the condition: 100 (aValue != rCompare). If no entry meets this condition 101 ::std::numeric_limits<A>::max() is returned. */ 102 A GetLastUnequalAccess( A nStart, const D& rCompare ); 103 104 /** Insert rows before nStart and copy value for inserted rows from 105 nStart-1, return that value. */ 106 const D& Insert( A nStart, size_t nCount ); 107 108 void Remove( A nStart, size_t nCount ); 109 110 /** Copy rArray.nStart+nSourceDy to this.nStart */ 111 void CopyFrom( const ScCompressedArray& rArray, 112 A nStart, A nEnd, long nSourceDy = 0 ); 113 114 115 // methods public for the coupled array sum methods 116 /** Obtain index into entries for nPos */ 117 SC_DLLPUBLIC size_t Search( A nPos ) const; 118 /** Get number of entries */ 119 size_t GetEntryCount() const; 120 /** Get data entry for an index */ 121 const DataEntry& GetDataEntry( size_t nIndex ) const; 122 123 protected: 124 125 friend class ScCompressedArrayIterator<A,D>; 126 127 size_t nCount; 128 size_t nLimit; 129 size_t nDelta; 130 DataEntry* pData; 131 A nMaxAccess; 132 }; 133 134 135 template< typename A, typename D > 136 void ScCompressedArray<A,D>::Reset( const D& rValue ) 137 { 138 // Create a temporary copy in case we got a reference passed that points to 139 // a part of the array to be reallocated. 140 D aTmpVal( rValue); 141 delete[] pData; 142 nCount = nLimit = 1; 143 pData = new DataEntry[1]; 144 pData[0].aValue = aTmpVal; 145 pData[0].nEnd = nMaxAccess; 146 } 147 148 149 template< typename A, typename D > 150 void ScCompressedArray<A,D>::SetValue( A nPos, const D& rValue ) 151 { 152 SetValue( nPos, nPos, rValue); 153 } 154 155 156 template< typename A, typename D > 157 const D& ScCompressedArray<A,D>::GetValue( A nPos ) const 158 { 159 size_t nIndex = Search( nPos); 160 return pData[nIndex].aValue; 161 } 162 163 164 template< typename A, typename D > 165 const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nEnd ) const 166 { 167 nIndex = Search( nPos); 168 nEnd = pData[nIndex].nEnd; 169 return pData[nIndex].aValue; 170 } 171 172 173 template< typename A, typename D > 174 const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nStart, 175 A& nEnd ) const 176 { 177 nIndex = Search( nPos); 178 nStart = (nIndex > 0 ? pData[nIndex-1].nEnd + 1 : 0); 179 nEnd = pData[nIndex].nEnd; 180 return pData[nIndex].aValue; 181 } 182 183 184 template< typename A, typename D > 185 const D& ScCompressedArray<A,D>::GetNextValue( size_t& nIndex, A& nEnd ) const 186 { 187 if (nIndex < nCount) 188 ++nIndex; 189 size_t nEntry = (nIndex < nCount ? nIndex : nCount-1); 190 nEnd = pData[nEntry].nEnd; 191 return pData[nEntry].aValue; 192 } 193 194 195 template< typename A, typename D > 196 const D& ScCompressedArray<A,D>::GetPrevValue( size_t& nIndex, A& nStart ) const 197 { 198 if (nIndex > 0) 199 --nIndex; 200 nStart = (nIndex > 0 ? pData[nIndex-1].nEnd + 1 : 0); 201 return pData[nIndex].aValue; 202 } 203 204 205 template< typename A, typename D > 206 size_t ScCompressedArray<A,D>::GetEntryCount() const 207 { 208 return nCount; 209 } 210 211 212 template< typename A, typename D > 213 const typename ScCompressedArray<A,D>::DataEntry& 214 ScCompressedArray<A,D>::GetDataEntry( size_t nIndex ) const 215 { 216 return pData[nIndex]; 217 } 218 219 220 // === ScCompressedArrayIterator ============================================= 221 222 /** Iterator for ScCompressedArray. 223 224 @ATTENTION: the iterator is not persistent if the underlying 225 ScCompressedArray happens to be changed by any means, for example by 226 setting new values or adding or removing or combining entries. If you do 227 such things inside a loop you MUST resynchronize the iterator by calling 228 <method>Resync()</method> with the row where resynchronization should 229 start. After doing so, <method>GetRangeStart()</method> and 230 <method>GetRangeEnd()</method> may not point to the previous access points 231 anymore. Use with care. 232 */ 233 234 template< typename A, typename D > class ScCompressedArrayIterator 235 { 236 public: 237 ScCompressedArrayIterator( 238 const ScCompressedArray<A,D> & rArray, 239 A nStart, A nEnd ); 240 /// Set new start and end, position on start. 241 void NewLimits( A nStart, A nEnd ); 242 A GetIterStart() const; 243 A GetIterEnd() const; 244 /// Advance by a single access point (e.g. row). 245 bool operator ++(); 246 A GetPos() const; 247 operator bool() const; 248 const D& operator *() const; 249 /// Advance an entire range, one entry of the array. 250 bool NextRange(); 251 A GetRangeStart() const; 252 A GetRangeEnd() const; 253 /// Resync to underlying array, calling Search(). 254 void Resync( A nPos ); 255 /** Set position without resyncing, avoid calling Search() if possible. 256 Position obtained from steering coupled iterator is NOT checked for 257 iterator bounds. */ 258 template< typename X > 259 void Follow( const ScCompressedArrayIterator<A,X>& ); 260 261 private: 262 const ScCompressedArray<A,D> & rArray; 263 size_t nIndex; 264 A nIterStart; 265 A nIterEnd; 266 A nCurrent; 267 bool bEnd; 268 }; 269 270 271 template< typename A, typename D > 272 ScCompressedArrayIterator<A,D>::ScCompressedArrayIterator( 273 const ScCompressedArray<A,D> & rArrayP, A nStart, A nEnd ) 274 : rArray( rArrayP ) 275 // other values set in NewLimits() 276 { 277 NewLimits( nStart, nEnd); 278 } 279 280 281 template< typename A, typename D > 282 void ScCompressedArrayIterator<A,D>::NewLimits( A nStart, A nEnd ) 283 { 284 nIterStart = nStart; 285 nIterEnd = nEnd; 286 nIndex = rArray.Search( nStart); 287 nCurrent = GetRangeStart(); 288 bEnd = (nIterEnd < nIterStart); 289 } 290 291 292 template< typename A, typename D > 293 A ScCompressedArrayIterator<A,D>::GetIterStart() const 294 { 295 return nIterStart; 296 } 297 298 299 template< typename A, typename D > 300 A ScCompressedArrayIterator<A,D>::GetIterEnd() const 301 { 302 return nIterEnd; 303 } 304 305 306 template< typename A, typename D > 307 bool ScCompressedArrayIterator<A,D>::operator++() 308 { 309 if (nCurrent < GetRangeEnd()) 310 { 311 ++nCurrent; 312 return true; 313 } 314 else 315 return NextRange(); 316 } 317 318 319 template< typename A, typename D > 320 A ScCompressedArrayIterator<A,D>::GetPos() const 321 { 322 return nCurrent; 323 } 324 325 326 template< typename A, typename D > 327 bool ScCompressedArrayIterator<A,D>::NextRange() 328 { 329 if (!operator bool()) 330 return false; 331 332 if (rArray.pData[nIndex].nEnd >= nIterEnd) 333 bEnd = true; 334 else if (++nIndex >= rArray.GetEntryCount()) 335 { 336 nIndex = rArray.GetEntryCount() - 1; 337 bEnd = true; 338 } 339 nCurrent = bEnd ? nIterEnd : GetRangeStart(); 340 return operator bool(); 341 } 342 343 344 template< typename A, typename D > 345 ScCompressedArrayIterator<A,D>::operator bool() const 346 { 347 return !bEnd; 348 } 349 350 351 template< typename A, typename D > 352 const D& ScCompressedArrayIterator<A,D>::operator*() const 353 { 354 return rArray.pData[nIndex].aValue; 355 } 356 357 358 template< typename A, typename D > 359 A ScCompressedArrayIterator<A,D>::GetRangeStart() const 360 { 361 if (nIndex == 0) 362 return nIterStart > 0 ? nIterStart : 0; 363 else 364 return nIterStart > rArray.pData[nIndex-1].nEnd ? nIterStart : 365 rArray.pData[nIndex-1].nEnd + 1; 366 } 367 368 369 template< typename A, typename D > 370 A ScCompressedArrayIterator<A,D>::GetRangeEnd() const 371 { 372 return nIterEnd < rArray.pData[nIndex].nEnd ? nIterEnd : 373 rArray.pData[nIndex].nEnd; 374 } 375 376 377 template< typename A, typename D > 378 void ScCompressedArrayIterator<A,D>::Resync( A nPos ) 379 { 380 if (nPos < nIterStart) 381 nPos = nIterStart; 382 else if (nPos > nIterEnd) 383 nPos = nIterEnd; 384 nCurrent = nPos; 385 bEnd = (nIterEnd < nIterStart); 386 nIndex = rArray.Search( nPos); 387 } 388 389 390 // === ScSummableCompressedArray ============================================= 391 392 /** Data type D must be of a type that is convertable to unsigned long. The 393 advantage is that specialized methods exist to act on a region of values 394 for performance reasons. 395 */ 396 397 template< typename A, typename D > class ScSummableCompressedArray : public ScCompressedArray<A,D> 398 { 399 public: 400 ScSummableCompressedArray( A nMaxAccessP, 401 const D& rValue, 402 size_t nDeltaP = nScCompressedArrayDelta ) 403 : ScCompressedArray<A,D>( nMaxAccessP, 404 rValue, nDeltaP) 405 {} 406 ScSummableCompressedArray( A nMaxAccessP, 407 const D* pDataArray, size_t nDataCount ) 408 : ScCompressedArray<A,D>( nMaxAccessP, 409 pDataArray, nDataCount) 410 {} 411 412 /** Returns the sum of all values for a region. If an overflow would occur, 413 ::std::numeric_limits<unsigned long>::max() is returned. */ 414 unsigned long SumValues( A nStart, A nEnd ) const; 415 416 /** Returns the sum of all values for a region. If an overflow would occur, 417 ::std::numeric_limits<unsigned long>::max() is returned. 418 The caller has to assure that nIndex matches an entry belonging to 419 nStart, for example, by calling Search(nStart) first! */ 420 unsigned long SumValuesContinuation( A nStart, A nEnd, 421 size_t& nIndex ) const; 422 423 /** Returns the sum of all scaled values for a region. If an overflow would 424 occur, ::std::numeric_limits<unsigned long>::max() is returned. 425 Summed values are treated as if for each row the expression 426 (sum += (unsigned long) (scale * value)) had been applied. 427 The caller has to assure that nIndex matches an entry belonging to 428 nStart, for example, by calling Search(nStart) first! */ 429 unsigned long SumScaledValuesContinuation( A nStart, A nEnd, 430 size_t& nIndex, double fScale ) const; 431 432 }; 433 434 435 // === ScBitMaskCompressedArray ============================================== 436 437 /** The data type represents bits, managable by bitwise operations. 438 */ 439 440 template< typename A, typename D > class ScBitMaskCompressedArray : public ScCompressedArray<A,D> 441 { 442 public: 443 ScBitMaskCompressedArray( A nMaxAccessP, 444 const D& rValue, 445 size_t nDeltaP = nScCompressedArrayDelta ) 446 : ScCompressedArray<A,D>( nMaxAccessP, rValue, nDeltaP) 447 {} 448 ScBitMaskCompressedArray( A nMaxAccessP, 449 const D* pDataArray, size_t nDataCount ) 450 : ScCompressedArray<A,D>( nMaxAccessP, 451 pDataArray, nDataCount) 452 {} 453 void AndValue( A nPos, const D& rValueToAnd ); 454 void OrValue( A nPos, const D& rValueToOr ); 455 void AndValue( A nStart, A nEnd, const D& rValueToAnd ); 456 void OrValue( A nStart, A nEnd, const D& rValueToOr ); 457 458 /** Copy values from rArray and bitwise AND them with rValueToAnd. */ 459 void CopyFromAnded( 460 const ScBitMaskCompressedArray& rArray, 461 A nStart, A nEnd, const D& rValueToAnd, 462 long nSourceDy = 0 ); 463 464 /** Copy values from rArray and bitwise OR them with rValueToOr. */ 465 void CopyFromOred( 466 const ScBitMaskCompressedArray& rArray, 467 A nStart, A nEnd, const D& rValueToOr, 468 long nSourceDy = 0 ); 469 470 /** Return the start row of a region where all entries meet the condition: 471 ((aValue & rBitMask) == rMaskedCompare). If not even nEnd meets 472 this condition, ::std::numeric_limits<A>::max() is returned. */ 473 A GetBitStateStart( A nEnd, const D& rBitMask, 474 const D& rMaskedCompare ) const; 475 476 /** Return the end row of a region where all entries meet the condition: 477 ((aValue & rBitMask) == rMaskedCompare). If not even nStart meets 478 this condition, ::std::numeric_limits<A>::max() is returned. */ 479 A GetBitStateEnd( A nStart, const D& rBitMask, 480 const D& rMaskedCompare ) const; 481 482 /** Return the first row where an entry meets the condition: 483 ((aValue & rBitMask) == rMaskedCompare), searching between nStart and 484 nEnd. If no entry meets this condition, ::std::numeric_limits<A>::max() 485 is returned. */ 486 SC_DLLPUBLIC A GetFirstForCondition( A nStart, A nEnd, 487 const D& rBitMask, 488 const D& rMaskedCompare ) const; 489 490 /** Return the last row where an entry meets the condition: 491 ((aValue & rBitMask) == rMaskedCompare), searching between nStart and 492 nEnd. If no entry meets this condition, ::std::numeric_limits<A>::max() 493 is returned. */ 494 SC_DLLPUBLIC A GetLastForCondition( A nStart, A nEnd, 495 const D& rBitMask, 496 const D& rMaskedCompare ) const; 497 498 /** Count rows between nStart and nEnd where entries meet the condition: 499 ((aValue & rBitMask) == rMaskedCompare) */ 500 A CountForCondition( A nStart, A nEnd, 501 const D& rBitMask, 502 const D& rMaskedCompare ) const; 503 504 /** Whether there is any entry between nStart and nEnd where the condition 505 is met: ((aValue & rBitMask) == rMaskedCompare) */ 506 SC_DLLPUBLIC bool HasCondition( A nStart, A nEnd, 507 const D& rBitMask, 508 const D& rMaskedCompare ) const; 509 510 /** Fill an array with row numbers between nStart and nEnd where entries 511 meet the condition: ((aValue & rBitMask) == rMaskedCompare). 512 @return the count of used elements in array. */ 513 size_t FillArrayForCondition( A nStart, A nEnd, 514 const D& rBitMask, 515 const D& rMaskedCompare, 516 A * pArray, size_t nArraySize ) const; 517 518 /** Count rows between nStart and nEnd where entries meet the condition: 519 ((aValue & rBitMask) != 0) */ 520 A CountForAnyBitCondition( A nStart, A nEnd, 521 const D& rBitMask ) const; 522 523 /** Return the last row where an entry meets the condition: 524 ((aValue & rBitMask) != 0), start searching at nStart. If no entry 525 meets this condition, ::std::numeric_limits<A>::max() is returned. */ 526 A GetLastAnyBitAccess( A nStart, 527 const D& rBitMask ) const; 528 529 /** Sum values of a ScSummableCompressedArray for each row where in *this* 530 array the condition is met: ((aValue & rBitMask) == rMaskedCompare). */ 531 template< typename S > 532 SC_DLLPUBLIC unsigned long SumCoupledArrayForCondition( A nStart, A nEnd, 533 const D& rBitMask, const D& rMaskedCompare, 534 const ScSummableCompressedArray<A,S>& rArray ) const; 535 536 /** Sum scaled values of a ScSummableCompressedArray for each row where in 537 *this* array the condition is met: ((aValue & rBitMask) == rMaskedCompare). */ 538 template< typename S > 539 SC_DLLPUBLIC unsigned long SumScaledCoupledArrayForCondition( A nStart, A nEnd, 540 const D& rBitMask, const D& rMaskedCompare, 541 const ScSummableCompressedArray<A,S>& rArray, 542 double fScale ) const; 543 }; 544 545 546 template< typename A, typename D > 547 void ScBitMaskCompressedArray<A,D>::AndValue( A nPos, const D& rValueToAnd ) 548 { 549 const D& rValue = this->GetValue( nPos); 550 if ((rValue & rValueToAnd) != rValue) 551 this->SetValue( nPos, rValue & rValueToAnd); 552 } 553 554 555 template< typename A, typename D > 556 void ScBitMaskCompressedArray<A,D>::OrValue( A nPos, const D& rValueToOr ) 557 { 558 const D& rValue = this->GetValue( nPos); 559 if ((rValue | rValueToOr) != rValue) 560 this->SetValue( nPos, rValue | rValueToOr); 561 } 562 563 564 // === ScCoupledCompressedArrayIterator ====================================== 565 566 /** Iterate over a ScBitMaskCompressedArray and retrieve values from a coupled 567 array for positions where in the bit mask array the condition ((*aIter1 & 568 rBitMask) == rMaskedCompare) is met. 569 */ 570 571 template< typename A, typename D, typename S > class ScCoupledCompressedArrayIterator 572 { 573 public: 574 SC_DLLPUBLIC ScCoupledCompressedArrayIterator( 575 const ScBitMaskCompressedArray<A,D> & rArray1, 576 A nStart, A nEnd, 577 const D& rBitMask, 578 const D& rMaskedCompare, 579 const ScCompressedArray<A,S> & rArray2 ); 580 void NewLimits( A nStart, A nEnd ); 581 A GetIterStart() const; 582 A GetIterEnd() const; 583 bool operator ++(); 584 A GetPos() const; 585 operator bool() const; 586 const S& operator *() const; 587 SC_DLLPUBLIC bool NextRange(); 588 A GetRangeStart() const; 589 A GetRangeEnd() const; 590 void Resync( A nPos ); 591 592 private: 593 ScCompressedArrayIterator<A,D> aIter1; 594 ScCompressedArrayIterator<A,S> aIter2; 595 const D& rBitMask; 596 const D& rMaskedCompare; 597 598 void InitLimits(); 599 }; 600 601 602 template< typename A, typename D, typename S > 603 A ScCoupledCompressedArrayIterator<A,D,S>::GetIterStart() const 604 { 605 return aIter1.GetIterStart(); 606 } 607 608 609 template< typename A, typename D, typename S > 610 A ScCoupledCompressedArrayIterator<A,D,S>::GetIterEnd() const 611 { 612 return aIter1.GetIterEnd(); 613 } 614 615 616 template< typename A, typename D, typename S > 617 ScCoupledCompressedArrayIterator<A,D,S>::operator bool() const 618 { 619 return aIter1 && aIter2; 620 } 621 622 623 template< typename A, typename D, typename S > 624 const S& ScCoupledCompressedArrayIterator<A,D,S>::operator*() const 625 { 626 return *aIter2; 627 } 628 629 630 template< typename A, typename D, typename S > 631 bool ScCoupledCompressedArrayIterator<A,D,S>::operator ++() 632 { 633 if (aIter1.GetPos() < aIter1.GetRangeEnd()) 634 { 635 ++aIter1; 636 ++aIter2; 637 return operator bool(); 638 } 639 else 640 return NextRange(); 641 } 642 643 644 template< typename A, typename D, typename S > 645 A ScCoupledCompressedArrayIterator<A,D,S>::GetPos() const 646 { 647 return aIter2.GetPos(); 648 } 649 650 651 template< typename A, typename D, typename S > 652 A ScCoupledCompressedArrayIterator<A,D,S>::GetRangeStart() const 653 { 654 return ::std::max( aIter1.GetRangeStart(), aIter2.GetRangeStart()); 655 } 656 657 658 template< typename A, typename D, typename S > 659 A ScCoupledCompressedArrayIterator<A,D,S>::GetRangeEnd() const 660 { 661 return ::std::min( aIter1.GetRangeEnd(), aIter2.GetRangeEnd()); 662 } 663 664 665 #endif // SC_COMPRESSEDARRAY_HXX 666