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 >
ScCompressedArray(A nMaxAccessP,const D & rValue,size_t nDeltaP)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 >
ScCompressedArray(A nMaxAccessP,const D * pDataArray,size_t nDataCount)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 >
~ScCompressedArray()74 ScCompressedArray<A,D>::~ScCompressedArray()
75 {
76     delete[] pData;
77 }
78 
79 
80 template< typename A, typename D >
Resize(size_t nNewLimit)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 >
Search(A nAccess) const95 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 >
SetValue(A nStart,A nEnd,const D & rValue)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 >
CopyFrom(const ScCompressedArray<A,D> & rArray,A nStart,A nEnd,long nSourceDy)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 >
Insert(A nStart,size_t nAccessCount)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 >
Remove(A nStart,size_t nAccessCount)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 >
GetLastUnequalAccess(A nStart,const D & rCompare)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 >
SumValues(A nStart,A nEnd) const364 unsigned long ScSummableCompressedArray<A,D>::SumValues( A nStart, A nEnd ) const
365 {
366     size_t nIndex = this->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 >
SumValuesContinuation(A nStart,A nEnd,size_t & nIndex) const375 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 >
SumScaledValuesContinuation(A nStart,A nEnd,size_t & nIndex,double fScale) const397 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 >
AndValue(A nStart,A nEnd,const D & rValueToAnd)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 = this->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             this->SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd);
436             if (nE >= nEnd)
437                 break;  // while
438             nIndex = this->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 >
OrValue(A nStart,A nEnd,const D & rValueToOr)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 = this->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             this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
463             if (nE >= nEnd)
464                 break;  // while
465             nIndex = this->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 >
CopyFromAnded(const ScBitMaskCompressedArray<A,D> & rArray,A nStart,A nEnd,const D & rValueToAnd,long nSourceDy)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         this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
491         j = nRegionEnd;
492     }
493 }
494 
495 
496 template< typename A, typename D >
CopyFromOred(const ScBitMaskCompressedArray<A,D> & rArray,A nStart,A nEnd,const D & rValueToOr,long nSourceDy)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         this->SetValue( j, nRegionEnd, rValue | rValueToOr);
512         j = nRegionEnd;
513     }
514 }
515 
516 
517 template< typename A, typename D >
GetBitStateStart(A nEnd,const D & rBitMask,const D & rMaskedCompare) const518 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 = this->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 >
GetBitStateEnd(A nStart,const D & rBitMask,const D & rMaskedCompare) const541 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 = this->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 >
GetFirstForCondition(A nStart,A nEnd,const D & rBitMask,const D & rMaskedCompare) const557 A ScBitMaskCompressedArray<A,D>::GetFirstForCondition( A nStart, A nEnd,
558         const D& rBitMask, const D& rMaskedCompare ) const
559 {
560     size_t nIndex = this->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 >
GetLastForCondition(A nStart,A nEnd,const D & rBitMask,const D & rMaskedCompare) const577 A ScBitMaskCompressedArray<A,D>::GetLastForCondition( A nStart, A nEnd,
578         const D& rBitMask, const D& rMaskedCompare ) const
579 {
580     size_t nIndex = this->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 >
CountForCondition(A nStart,A nEnd,const D & rBitMask,const D & rMaskedCompare) const600 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 = this->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 >
FillArrayForCondition(A nStart,A nEnd,const D & rBitMask,const D & rMaskedCompare,A * pArray,size_t nArraySize) const622 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 = this->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 >
HasCondition(A nStart,A nEnd,const D & rBitMask,const D & rMaskedCompare) const646 bool ScBitMaskCompressedArray<A,D>::HasCondition( A nStart, A nEnd,
647         const D& rBitMask, const D& rMaskedCompare ) const
648 {
649     size_t nIndex = this->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 >
CountForAnyBitCondition(A nStart,A nEnd,const D & rBitMask) const663 A ScBitMaskCompressedArray<A,D>::CountForAnyBitCondition( A nStart, A nEnd,
664         const D& rBitMask ) const
665 {
666     A nRet = 0;
667     size_t nIndex = this->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 >
GetLastAnyBitAccess(A nStart,const D & rBitMask) const685 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 >
SumCoupledArrayForCondition(A nStart,A nEnd,const D & rBitMask,const D & rMaskedCompare,const ScSummableCompressedArray<A,S> & rArray) const715 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 = this->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 >
SumScaledCoupledArrayForCondition(A nStart,A nEnd,const D & rBitMask,const D & rMaskedCompare,const ScSummableCompressedArray<A,S> & rArray,double fScale) const749 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 = this->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 >
Follow(const ScCompressedArrayIterator<A,X> & rIter)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 >
ScCoupledCompressedArrayIterator(const ScBitMaskCompressedArray<A,D> & rArray1,A nStart,A nEnd,const D & rBitMaskP,const D & rMaskedCompareP,const ScCompressedArray<A,S> & rArray2)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 >
InitLimits()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 >
NewLimits(A nStart,A nEnd)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 >
NextRange()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 >
Resync(A nPos)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