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