Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #ifndef SC_COMPRESSEDARRAY_HXX
21 : #define SC_COMPRESSEDARRAY_HXX
22 :
23 : #include <cstddef>
24 : #include <algorithm>
25 :
26 : #include "scdllapi.h"
27 :
28 : const size_t nScCompressedArrayDelta = 4;
29 :
30 : /** Compressed array of row (or column) entries, e.g. heights, flags, ...
31 :
32 : The array stores ranges of values such that consecutive values occupy only
33 : one entry. Initially it consists of one DataEntry with an implied start
34 : row/column of 0 and an end row/column of access type maximum value.
35 :
36 : typename A := access type, e.g. SCROW or SCCOL, must be a POD.
37 :
38 : typename D := data type, e.g. sal_uInt16 or sal_uInt8 or whatever, may also be a
39 : struct or class.
40 :
41 : D::operator==() and D::operator=() must be implemented. Force template
42 : instantiation for a specific type in source/core/data/compressedarray.cxx
43 :
44 : TODO: Currently the allocated memory never shrinks, must manually invoke
45 : Resize() if needed.
46 : */
47 :
48 : template< typename A, typename D > class ScCompressedArray
49 : {
50 : public:
51 : struct DataEntry
52 : {
53 : A nEnd; // start is end of previous entry + 1
54 : D aValue;
55 22106 : DataEntry() {} //! uninitialized
56 : };
57 :
58 : /** Construct with nMaxAccess=MAXROW, for example. */
59 : ScCompressedArray( A nMaxAccess,
60 : const D& rValue,
61 : size_t nDelta = nScCompressedArrayDelta );
62 : /** Construct from a plain array of D */
63 : ScCompressedArray( A nMaxAccess,
64 : const D* pDataArray, size_t nDataCount );
65 : virtual ~ScCompressedArray();
66 : void Resize( size_t nNewSize );
67 : void Reset( const D& rValue );
68 : void SetValue( A nPos, const D& rValue );
69 : void SetValue( A nStart, A nEnd, const D& rValue );
70 : const D& GetValue( A nPos ) const;
71 :
72 : /** Get value for a row, and it's region end row */
73 : const D& GetValue( A nPos, size_t& nIndex, A& nEnd ) const;
74 :
75 : /** Get next value and it's region end row. If nIndex<nCount, nIndex is
76 : incremented first. If the resulting nIndex>=nCount, the value of the
77 : last entry is returned again. */
78 : const D& GetNextValue( size_t& nIndex, A& nEnd ) const;
79 :
80 : /** Insert rows before nStart and copy value for inserted rows from
81 : nStart-1, return that value. */
82 : const D& Insert( A nStart, size_t nCount );
83 :
84 : void Remove( A nStart, size_t nCount );
85 :
86 : /** Copy rArray.nStart+nSourceDy to this.nStart */
87 : void CopyFrom( const ScCompressedArray& rArray,
88 : A nStart, A nEnd, long nSourceDy = 0 );
89 :
90 :
91 : // methods public for the coupled array sum methods
92 : /** Obtain index into entries for nPos */
93 : SC_DLLPUBLIC size_t Search( A nPos ) const;
94 :
95 : protected:
96 : size_t nCount;
97 : size_t nLimit;
98 : size_t nDelta;
99 : DataEntry* pData;
100 : A nMaxAccess;
101 : };
102 :
103 :
104 : template< typename A, typename D >
105 43 : void ScCompressedArray<A,D>::Reset( const D& rValue )
106 : {
107 : // Create a temporary copy in case we got a reference passed that points to
108 : // a part of the array to be reallocated.
109 43 : D aTmpVal( rValue);
110 43 : delete[] pData;
111 43 : nCount = nLimit = 1;
112 43 : pData = new DataEntry[1];
113 43 : pData[0].aValue = aTmpVal;
114 43 : pData[0].nEnd = nMaxAccess;
115 43 : }
116 :
117 :
118 : template< typename A, typename D >
119 0 : void ScCompressedArray<A,D>::SetValue( A nPos, const D& rValue )
120 : {
121 0 : SetValue( nPos, nPos, rValue);
122 0 : }
123 :
124 :
125 : template< typename A, typename D >
126 1723 : const D& ScCompressedArray<A,D>::GetValue( A nPos ) const
127 : {
128 1723 : size_t nIndex = Search( nPos);
129 1723 : return pData[nIndex].aValue;
130 : }
131 :
132 :
133 : template< typename A, typename D >
134 1014 : const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nEnd ) const
135 : {
136 1014 : nIndex = Search( nPos);
137 1014 : nEnd = pData[nIndex].nEnd;
138 1014 : return pData[nIndex].aValue;
139 : }
140 :
141 :
142 : template< typename A, typename D >
143 36 : const D& ScCompressedArray<A,D>::GetNextValue( size_t& nIndex, A& nEnd ) const
144 : {
145 36 : if (nIndex < nCount)
146 36 : ++nIndex;
147 36 : size_t nEntry = (nIndex < nCount ? nIndex : nCount-1);
148 36 : nEnd = pData[nEntry].nEnd;
149 36 : return pData[nEntry].aValue;
150 : }
151 :
152 : // === ScBitMaskCompressedArray ==============================================
153 :
154 : /** The data type represents bits, managable by bitwise operations.
155 : */
156 :
157 1454 : template< typename A, typename D > class ScBitMaskCompressedArray : public ScCompressedArray<A,D>
158 : {
159 : public:
160 814 : ScBitMaskCompressedArray( A nMaxAccessP,
161 : const D& rValue,
162 : size_t nDeltaP = nScCompressedArrayDelta )
163 814 : : ScCompressedArray<A,D>( nMaxAccessP, rValue, nDeltaP)
164 814 : {}
165 20 : ScBitMaskCompressedArray( A nMaxAccessP,
166 : const D* pDataArray, size_t nDataCount )
167 : : ScCompressedArray<A,D>( nMaxAccessP,
168 20 : pDataArray, nDataCount)
169 20 : {}
170 : void AndValue( A nPos, const D& rValueToAnd );
171 : void OrValue( A nPos, const D& rValueToOr );
172 : void AndValue( A nStart, A nEnd, const D& rValueToAnd );
173 : void OrValue( A nStart, A nEnd, const D& rValueToOr );
174 :
175 : /** Copy values from rArray and bitwise AND them with rValueToAnd. */
176 : void CopyFromAnded(
177 : const ScBitMaskCompressedArray& rArray,
178 : A nStart, A nEnd, const D& rValueToAnd,
179 : long nSourceDy = 0 );
180 :
181 : /** Return the first row where an entry meets the condition:
182 : ((aValue & rBitMask) == rMaskedCompare), searching between nStart and
183 : nEnd. If no entry meets this condition, ::std::numeric_limits<A>::max()
184 : is returned. */
185 : SC_DLLPUBLIC A GetFirstForCondition( A nStart, A nEnd,
186 : const D& rBitMask,
187 : const D& rMaskedCompare ) const;
188 :
189 : /** Return the last row where an entry meets the condition:
190 : ((aValue & rBitMask) != 0), start searching at nStart. If no entry
191 : meets this condition, ::std::numeric_limits<A>::max() is returned. */
192 : A GetLastAnyBitAccess( A nStart,
193 : const D& rBitMask ) const;
194 : };
195 :
196 :
197 : template< typename A, typename D >
198 0 : void ScBitMaskCompressedArray<A,D>::AndValue( A nPos, const D& rValueToAnd )
199 : {
200 0 : const D& rValue = this->GetValue( nPos);
201 0 : if ((rValue & rValueToAnd) != rValue)
202 0 : this->SetValue( nPos, rValue & rValueToAnd);
203 0 : }
204 :
205 :
206 : template< typename A, typename D >
207 0 : void ScBitMaskCompressedArray<A,D>::OrValue( A nPos, const D& rValueToOr )
208 : {
209 0 : const D& rValue = this->GetValue( nPos);
210 0 : if ((rValue | rValueToOr) != rValue)
211 0 : this->SetValue( nPos, rValue | rValueToOr);
212 0 : }
213 :
214 :
215 : #endif // SC_COMPRESSEDARRAY_HXX
216 :
217 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
