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