1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * This file is part of the LibreOffice project.
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/.
9 * This file incorporates work covered by the following license notice:
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 .
21 #include "compressedarray.hxx"
22 #include "address.hxx"
26 template< typename A
, typename D
>
27 ScCompressedArray
<A
,D
>::ScCompressedArray( A nMaxAccessP
, const D
& rValue
,
31 , nDelta( nDeltaP
> 0 ? nDeltaP
: 1)
32 , pData( new DataEntry
[1])
33 , nMaxAccess( nMaxAccessP
)
35 pData
[0].aValue
= rValue
;
36 pData
[0].nEnd
= nMaxAccess
;
40 template< typename A
, typename D
>
41 ScCompressedArray
<A
,D
>::ScCompressedArray( A nMaxAccessP
, const D
* pDataArray
,
45 , nDelta( nScCompressedArrayDelta
)
46 , pData( new DataEntry
[nDataCount
])
47 , nMaxAccess( nMaxAccessP
)
49 D aValue
= pDataArray
[0];
50 for (size_t j
=0; j
<nDataCount
; ++j
)
52 if (!(aValue
== pDataArray
[j
]))
54 pData
[nCount
].aValue
= aValue
;
55 pData
[nCount
].nEnd
= j
-1;
57 aValue
= pDataArray
[j
];
60 pData
[nCount
].aValue
= aValue
;
61 pData
[nCount
].nEnd
= nMaxAccess
;
67 template< typename A
, typename D
>
68 ScCompressedArray
<A
,D
>::~ScCompressedArray()
74 template< typename A
, typename D
>
75 void ScCompressedArray
<A
,D
>::Resize( size_t nNewLimit
)
77 if ((nCount
<= nNewLimit
&& nNewLimit
< nLimit
) || nLimit
< nNewLimit
)
80 DataEntry
* pNewData
= new DataEntry
[nLimit
];
81 memcpy( pNewData
, pData
, nCount
*sizeof(DataEntry
));
88 template< typename A
, typename D
>
89 size_t ScCompressedArray
<A
,D
>::Search( A nAccess
) const
95 long nHi
= static_cast<long>(nCount
) - 1;
99 bool bFound
= (nCount
== 1);
100 while (!bFound
&& nLo
<= nHi
)
104 nStart
= (long) pData
[i
- 1].nEnd
;
107 nEnd
= (long) pData
[i
].nEnd
;
108 if (nEnd
< (long) nAccess
)
111 if (nStart
>= (long) nAccess
)
116 return (bFound
? static_cast<size_t>(i
) : (nAccess
< 0 ? 0 : nCount
-1));
120 template< typename A
, typename D
>
121 void ScCompressedArray
<A
,D
>::SetValue( A nStart
, A nEnd
, const D
& rValue
)
123 if (0 <= nStart
&& nStart
<= nMaxAccess
&& 0 <= nEnd
&& nEnd
<= nMaxAccess
126 if ((nStart
== 0) && (nEnd
== nMaxAccess
))
130 // Create a temporary copy in case we got a reference passed that
131 // points to a part of the array to be reallocated.
133 size_t nNeeded
= nCount
+ 2;
134 if (nLimit
< nNeeded
)
137 if (nLimit
< nNeeded
)
139 DataEntry
* pNewData
= new DataEntry
[nLimit
];
140 memcpy( pNewData
, pData
, nCount
*sizeof(DataEntry
));
145 size_t ni
; // number of leading entries
146 size_t nInsert
; // insert position (nMaxAccess+1 := no insert)
147 bool bCombined
= false;
152 ni
= this->Search( nStart
);
154 nInsert
= nMaxAccess
+1;
155 if (!(pData
[ni
].aValue
== aNewVal
))
157 if (ni
== 0 || (pData
[ni
-1].nEnd
< nStart
- 1))
158 { // may be a split or a simple insert or just a shrink,
159 // row adjustment is done further down
160 if (pData
[ni
].nEnd
> nEnd
)
165 else if (ni
> 0 && pData
[ni
-1].nEnd
== nStart
- 1)
168 if (ni
> 0 && pData
[ni
-1].aValue
== aNewVal
)
170 pData
[ni
-1].nEnd
= nEnd
;
171 nInsert
= nMaxAccess
+1;
181 size_t nj
= ni
; // stop position of range to replace
182 while (nj
< nCount
&& pData
[nj
].nEnd
<= nEnd
)
186 if (nj
< nCount
&& pData
[nj
].aValue
== aNewVal
)
190 if (pData
[ni
-1].aValue
== aNewVal
)
191 { // adjacent entries
192 pData
[ni
-1].nEnd
= pData
[nj
].nEnd
;
195 else if (ni
== nInsert
)
196 pData
[ni
-1].nEnd
= nStart
- 1; // shrink
198 nInsert
= nMaxAccess
+1;
201 else if (ni
> 0 && ni
== nInsert
)
202 pData
[ni
-1].nEnd
= nStart
- 1; // shrink
205 { // remove middle entries
207 { // replace one entry
208 pData
[ni
].nEnd
= nEnd
;
209 pData
[ni
].aValue
= aNewVal
;
211 nInsert
= nMaxAccess
+1;
215 memmove( pData
+ ni
, pData
+ nj
,
216 (nCount
- nj
) * sizeof(DataEntry
));
221 if (nInsert
< static_cast<size_t>(nMaxAccess
+1))
222 { // insert or append new entry
223 if (nInsert
<= nCount
)
226 memmove( pData
+ nInsert
+ 1, pData
+ nInsert
,
227 (nCount
- nInsert
) * sizeof(DataEntry
));
230 memmove( pData
+ nInsert
+ 2, pData
+ nInsert
,
231 (nCount
- nInsert
) * sizeof(DataEntry
));
232 pData
[nInsert
+1] = pData
[nInsert
-1];
237 pData
[nInsert
-1].nEnd
= nStart
- 1;
238 pData
[nInsert
].nEnd
= nEnd
;
239 pData
[nInsert
].aValue
= aNewVal
;
247 template< typename A
, typename D
>
248 void ScCompressedArray
<A
,D
>::CopyFrom( const ScCompressedArray
<A
,D
>& rArray
, A nStart
,
249 A nEnd
, long nSourceDy
)
253 for (A j
=nStart
; j
<=nEnd
; ++j
)
255 const D
& rValue
= (j
==nStart
?
256 rArray
.GetValue( j
+nSourceDy
, nIndex
, nRegionEnd
) :
257 rArray
.GetNextValue( nIndex
, nRegionEnd
));
258 nRegionEnd
-= nSourceDy
;
259 if (nRegionEnd
> nEnd
)
261 this->SetValue( j
, nRegionEnd
, rValue
);
267 template< typename A
, typename D
>
268 const D
& ScCompressedArray
<A
,D
>::Insert( A nStart
, size_t nAccessCount
)
270 size_t nIndex
= this->Search( nStart
);
271 // No real insertion is needed, simply extend the one entry and adapt all
272 // following. In case nStart points to the start row of an entry, extend
273 // the previous entry (inserting before nStart).
274 if (nIndex
> 0 && pData
[nIndex
-1].nEnd
+1 == nStart
)
276 const D
& rValue
= pData
[nIndex
].aValue
; // the value "copied"
279 pData
[nIndex
].nEnd
+= nAccessCount
;
280 if (pData
[nIndex
].nEnd
>= nMaxAccess
)
282 pData
[nIndex
].nEnd
= nMaxAccess
;
283 nCount
= nIndex
+ 1; // discard trailing entries
285 } while (++nIndex
< nCount
);
290 template< typename A
, typename D
>
291 void ScCompressedArray
<A
,D
>::Remove( A nStart
, size_t nAccessCount
)
293 A nEnd
= nStart
+ nAccessCount
- 1;
294 size_t nIndex
= this->Search( nStart
);
295 // equalize/combine/remove all entries in between
296 if (nEnd
> pData
[nIndex
].nEnd
)
297 this->SetValue( nStart
, nEnd
, pData
[nIndex
].aValue
);
298 // remove an exactly matching entry by shifting up all following by one
299 if ((nStart
== 0 || (nIndex
> 0 && nStart
== pData
[nIndex
-1].nEnd
+1)) &&
300 pData
[nIndex
].nEnd
== nEnd
&& nIndex
< nCount
-1)
302 // In case removing an entry results in two adjacent entries with
303 // identical data, combine them into one. This is also necessary to
304 // make the algorithm used in SetValue() work correctly, it relies on
305 // the fact that consecutive values actually differ.
307 if (nIndex
> 0 && pData
[nIndex
-1].aValue
== pData
[nIndex
+1].aValue
)
314 memmove( pData
+ nIndex
, pData
+ nIndex
+ nRemove
, (nCount
- (nIndex
+
315 nRemove
)) * sizeof(DataEntry
));
318 // adjust end rows, nIndex still being valid
321 pData
[nIndex
].nEnd
-= nAccessCount
;
322 } while (++nIndex
< nCount
);
323 pData
[nCount
-1].nEnd
= nMaxAccess
;
327 // === ScBitMaskCompressedArray ==============================================
329 template< typename A
, typename D
>
330 void ScBitMaskCompressedArray
<A
,D
>::AndValue( A nStart
, A nEnd
,
331 const D
& rValueToAnd
)
336 size_t nIndex
= this->Search( nStart
);
339 if ((this->pData
[nIndex
].aValue
& rValueToAnd
) != this->pData
[nIndex
].aValue
)
341 A nS
= ::std::max( (nIndex
>0 ? this->pData
[nIndex
-1].nEnd
+1 : 0), nStart
);
342 A nE
= ::std::min( this->pData
[nIndex
].nEnd
, nEnd
);
343 this->SetValue( nS
, nE
, this->pData
[nIndex
].aValue
& rValueToAnd
);
346 nIndex
= this->Search( nE
+ 1);
348 else if (this->pData
[nIndex
].nEnd
>= nEnd
)
352 } while (nIndex
< this->nCount
);
356 template< typename A
, typename D
>
357 void ScBitMaskCompressedArray
<A
,D
>::OrValue( A nStart
, A nEnd
,
358 const D
& rValueToOr
)
363 size_t nIndex
= this->Search( nStart
);
366 if ((this->pData
[nIndex
].aValue
| rValueToOr
) != this->pData
[nIndex
].aValue
)
368 A nS
= ::std::max( (nIndex
>0 ? this->pData
[nIndex
-1].nEnd
+1 : 0), nStart
);
369 A nE
= ::std::min( this->pData
[nIndex
].nEnd
, nEnd
);
370 this->SetValue( nS
, nE
, this->pData
[nIndex
].aValue
| rValueToOr
);
373 nIndex
= this->Search( nE
+ 1);
375 else if (this->pData
[nIndex
].nEnd
>= nEnd
)
379 } while (nIndex
< this->nCount
);
383 template< typename A
, typename D
>
384 void ScBitMaskCompressedArray
<A
,D
>::CopyFromAnded(
385 const ScBitMaskCompressedArray
<A
,D
>& rArray
, A nStart
, A nEnd
,
386 const D
& rValueToAnd
, long nSourceDy
)
390 for (A j
=nStart
; j
<=nEnd
; ++j
)
392 const D
& rValue
= (j
==nStart
?
393 rArray
.GetValue( j
+nSourceDy
, nIndex
, nRegionEnd
) :
394 rArray
.GetNextValue( nIndex
, nRegionEnd
));
395 nRegionEnd
-= nSourceDy
;
396 if (nRegionEnd
> nEnd
)
398 this->SetValue( j
, nRegionEnd
, rValue
& rValueToAnd
);
403 template< typename A
, typename D
>
404 A ScBitMaskCompressedArray
<A
,D
>::GetFirstForCondition( A nStart
, A nEnd
,
405 const D
& rBitMask
, const D
& rMaskedCompare
) const
407 size_t nIndex
= this->Search( nStart
);
410 if ((this->pData
[nIndex
].aValue
& rBitMask
) == rMaskedCompare
)
412 A nFound
= nIndex
> 0 ? this->pData
[nIndex
-1].nEnd
+ 1 : 0;
413 return ::std::max( nFound
, nStart
);
415 if (this->pData
[nIndex
].nEnd
>= nEnd
)
418 } while (nIndex
< this->nCount
);
419 return ::std::numeric_limits
<A
>::max();
422 template< typename A
, typename D
>
423 A ScBitMaskCompressedArray
<A
,D
>::GetLastAnyBitAccess( A nStart
,
424 const D
& rBitMask
) const
426 A nEnd
= ::std::numeric_limits
<A
>::max();
427 size_t nIndex
= this->nCount
-1;
430 if ((this->pData
[nIndex
].aValue
& rBitMask
) != 0)
432 nEnd
= this->pData
[nIndex
].nEnd
;
440 if (this->pData
[nIndex
].nEnd
< nStart
)
450 // === Force instantiation of specializations ================================
452 template class ScCompressedArray
< SCROW
, sal_uInt8
>; // flags, base class
453 template class ScBitMaskCompressedArray
< SCROW
, sal_uInt8
>; // flags
455 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */