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 INCLUDED_SC_INC_COMPRESSEDARRAY_HXX
21 : #define INCLUDED_SC_INC_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 45838 : 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 : // methods public for the coupled array sum methods
91 : /** Obtain index into entries for nPos */
92 : SC_DLLPUBLIC size_t Search( A nPos ) const;
93 :
94 : protected:
95 : size_t nCount;
96 : size_t nLimit;
97 : size_t nDelta;
98 : DataEntry* pData;
99 : A nMaxAccess;
100 : };
101 :
102 : template< typename A, typename D >
103 106 : void ScCompressedArray<A,D>::Reset( const D& rValue )
104 : {
105 : // Create a temporary copy in case we got a reference passed that points to
106 : // a part of the array to be reallocated.
107 106 : D aTmpVal( rValue);
108 106 : delete[] pData;
109 106 : nCount = nLimit = 1;
110 106 : pData = new DataEntry[1];
111 106 : pData[0].aValue = aTmpVal;
112 106 : pData[0].nEnd = nMaxAccess;
113 106 : }
114 :
115 : template< typename A, typename D >
116 0 : void ScCompressedArray<A,D>::SetValue( A nPos, const D& rValue )
117 : {
118 0 : SetValue( nPos, nPos, rValue);
119 0 : }
120 :
121 : template< typename A, typename D >
122 4656 : const D& ScCompressedArray<A,D>::GetValue( A nPos ) const
123 : {
124 4656 : size_t nIndex = Search( nPos);
125 4656 : return pData[nIndex].aValue;
126 : }
127 :
128 : template< typename A, typename D >
129 3202 : const D& ScCompressedArray<A,D>::GetValue( A nPos, size_t& nIndex, A& nEnd ) const
130 : {
131 3202 : nIndex = Search( nPos);
132 3202 : nEnd = pData[nIndex].nEnd;
133 3202 : return pData[nIndex].aValue;
134 : }
135 :
136 : template< typename A, typename D >
137 90 : const D& ScCompressedArray<A,D>::GetNextValue( size_t& nIndex, A& nEnd ) const
138 : {
139 90 : if (nIndex < nCount)
140 90 : ++nIndex;
141 90 : size_t nEntry = (nIndex < nCount ? nIndex : nCount-1);
142 90 : nEnd = pData[nEntry].nEnd;
143 90 : return pData[nEntry].aValue;
144 : }
145 :
146 : // ScBitMaskCompressedArray
147 : /** The data type represents bits, managable by bitwise operations.
148 : */
149 :
150 5120 : template< typename A, typename D > class ScBitMaskCompressedArray : public ScCompressedArray<A,D>
151 : {
152 : public:
153 2544 : ScBitMaskCompressedArray( A nMaxAccessP,
154 : const D& rValue,
155 : size_t nDeltaP = nScCompressedArrayDelta )
156 2544 : : ScCompressedArray<A,D>( nMaxAccessP, rValue, nDeltaP)
157 2544 : {}
158 40 : ScBitMaskCompressedArray( A nMaxAccessP,
159 : const D* pDataArray, size_t nDataCount )
160 : : ScCompressedArray<A,D>( nMaxAccessP,
161 40 : pDataArray, nDataCount)
162 40 : {}
163 : void AndValue( A nPos, const D& rValueToAnd );
164 : void OrValue( A nPos, const D& rValueToOr );
165 : void AndValue( A nStart, A nEnd, const D& rValueToAnd );
166 : void OrValue( A nStart, A nEnd, const D& rValueToOr );
167 :
168 : /** Copy values from rArray and bitwise AND them with rValueToAnd. */
169 : void CopyFromAnded(
170 : const ScBitMaskCompressedArray& rArray,
171 : A nStart, A nEnd, const D& rValueToAnd,
172 : long nSourceDy = 0 );
173 :
174 : /** Return the last row where an entry meets the condition:
175 : ((aValue & rBitMask) != 0), start searching at nStart. If no entry
176 : meets this condition, ::std::numeric_limits<A>::max() is returned. */
177 : A GetLastAnyBitAccess( A nStart,
178 : const D& rBitMask ) const;
179 : };
180 :
181 : template< typename A, typename D >
182 0 : void ScBitMaskCompressedArray<A,D>::AndValue( A nPos, const D& rValueToAnd )
183 : {
184 0 : const D& rValue = this->GetValue( nPos);
185 0 : if ((rValue & rValueToAnd) != rValue)
186 0 : this->SetValue( nPos, rValue & rValueToAnd);
187 0 : }
188 :
189 : template< typename A, typename D >
190 0 : void ScBitMaskCompressedArray<A,D>::OrValue( A nPos, const D& rValueToOr )
191 : {
192 0 : const D& rValue = this->GetValue( nPos);
193 0 : if ((rValue | rValueToOr) != rValue)
194 0 : this->SetValue( nPos, rValue | rValueToOr);
195 0 : }
196 :
197 : #endif // INCLUDED_SC_INC_COMPRESSEDARRAY_HXX
198 :
199 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
