LibreOffice Module sc (master)  1
compressedarray.cxx
Go to the documentation of this file.
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 #include <compressedarray.hxx>
21 #include <global.hxx>
22 
23 template< typename A, typename D >
24 ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D& rValue )
25  : nCount(1)
26  , nLimit(1)
27  , pData( new DataEntry[1])
28  , nMaxAccess( nMaxAccessP)
29 {
30  pData[0].aValue = rValue;
31  pData[0].nEnd = nMaxAccess;
32 }
33 
34 template< typename A, typename D >
36 {
37 }
38 
39 template< typename A, typename D >
40 size_t ScCompressedArray<A,D>::Search( A nAccess ) const
41 {
42  if (nAccess == 0)
43  return 0;
44 
45  long nLo = 0;
46  long nHi = static_cast<long>(nCount) - 1;
47  long nStart = 0;
48  long i = 0;
49  bool bFound = (nCount == 1);
50  while (!bFound && nLo <= nHi)
51  {
52  i = (nLo + nHi) / 2;
53  if (i > 0)
54  nStart = static_cast<long>(pData[i - 1].nEnd);
55  else
56  nStart = -1;
57  long nEnd = static_cast<long>(pData[i].nEnd);
58  if (nEnd < static_cast<long>(nAccess))
59  nLo = ++i;
60  else
61  if (nStart >= static_cast<long>(nAccess))
62  nHi = --i;
63  else
64  bFound = true;
65  }
66  return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
67 }
68 
69 template< typename A, typename D >
70 void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
71 {
72  if (!(0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
73  && nStart <= nEnd))
74  return;
75 
76  if ((nStart == 0) && (nEnd == nMaxAccess))
77  Reset( rValue);
78  else
79  {
80  // Create a temporary copy in case we got a reference passed that
81  // points to a part of the array to be reallocated.
82  D aNewVal( rValue);
83  size_t nNeeded = nCount + 2;
84  if (nLimit < nNeeded)
85  {
86  nLimit *= 1.5;
87  if (nLimit < nNeeded)
88  nLimit = nNeeded;
89  std::unique_ptr<DataEntry[]> pNewData(new DataEntry[nLimit]);
90  memcpy( pNewData.get(), pData.get(), nCount*sizeof(DataEntry));
91  pData = std::move(pNewData);
92  }
93 
94  size_t ni; // number of leading entries
95  size_t nInsert; // insert position (nMaxAccess+1 := no insert)
96  bool bCombined = false;
97  bool bSplit = false;
98  if (nStart > 0)
99  {
100  // skip leading
101  ni = this->Search( nStart);
102 
103  nInsert = nMaxAccess+1;
104  if (!(pData[ni].aValue == aNewVal))
105  {
106  if (ni == 0 || (pData[ni-1].nEnd < nStart - 1))
107  { // may be a split or a simple insert or just a shrink,
108  // row adjustment is done further down
109  if (pData[ni].nEnd > nEnd)
110  bSplit = true;
111  ni++;
112  nInsert = ni;
113  }
114  else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
115  nInsert = ni;
116  }
117  if (ni > 0 && pData[ni-1].aValue == aNewVal)
118  { // combine
119  pData[ni-1].nEnd = nEnd;
120  nInsert = nMaxAccess+1;
121  bCombined = true;
122  }
123  }
124  else
125  {
126  nInsert = 0;
127  ni = 0;
128  }
129 
130  size_t nj = ni; // stop position of range to replace
131  while (nj < nCount && pData[nj].nEnd <= nEnd)
132  nj++;
133  if (!bSplit)
134  {
135  if (nj < nCount && pData[nj].aValue == aNewVal)
136  { // combine
137  if (ni > 0)
138  {
139  if (pData[ni-1].aValue == aNewVal)
140  { // adjacent entries
141  pData[ni-1].nEnd = pData[nj].nEnd;
142  nj++;
143  }
144  else if (ni == nInsert)
145  pData[ni-1].nEnd = nStart - 1; // shrink
146  }
147  nInsert = nMaxAccess+1;
148  bCombined = true;
149  }
150  else if (ni > 0 && ni == nInsert)
151  pData[ni-1].nEnd = nStart - 1; // shrink
152  }
153  if (ni < nj)
154  { // remove middle entries
155  if (!bCombined)
156  { // replace one entry
157  pData[ni].nEnd = nEnd;
158  pData[ni].aValue = aNewVal;
159  ni++;
160  nInsert = nMaxAccess+1;
161  }
162  if (ni < nj)
163  { // remove entries
164  memmove( pData.get() + ni, pData.get() + nj,
165  (nCount - nj) * sizeof(DataEntry));
166  nCount -= nj - ni;
167  }
168  }
169 
170  if (nInsert < static_cast<size_t>(nMaxAccess+1))
171  { // insert or append new entry
172  if (nInsert <= nCount)
173  {
174  if (!bSplit)
175  memmove( pData.get() + nInsert + 1, pData.get() + nInsert,
176  (nCount - nInsert) * sizeof(DataEntry));
177  else
178  {
179  memmove( pData.get() + nInsert + 2, pData.get() + nInsert,
180  (nCount - nInsert) * sizeof(DataEntry));
181  pData[nInsert+1] = pData[nInsert-1];
182  nCount++;
183  }
184  }
185  if (nInsert)
186  pData[nInsert-1].nEnd = nStart - 1;
187  pData[nInsert].nEnd = nEnd;
188  pData[nInsert].aValue = aNewVal;
189  nCount++;
190  }
191  }
192 }
193 
194 template< typename A, typename D >
196  A nDestEnd, A nSrcStart )
197 {
198  assert( this != &rArray && "cannot copy self->self" );
199  size_t nIndex = 0;
200  A nRegionEnd;
201  for (A j=nDestStart; j<=nDestEnd; ++j)
202  {
203  const D& rValue = (j==nDestStart ?
204  rArray.GetValue( j - nDestStart + nSrcStart, nIndex, nRegionEnd) :
205  rArray.GetNextValue( nIndex, nRegionEnd));
206  nRegionEnd = nRegionEnd - nSrcStart + nDestStart;
207  if (nRegionEnd > nDestEnd)
208  nRegionEnd = nDestEnd;
209  this->SetValue( j, nRegionEnd, rValue);
210  j = nRegionEnd;
211  }
212 }
213 
214 template< typename A, typename D >
215 const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
216 {
217  size_t nIndex = this->Search( nStart);
218  // No real insertion is needed, simply extend the one entry and adapt all
219  // following. In case nStart points to the start row of an entry, extend
220  // the previous entry (inserting before nStart).
221  if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
222  --nIndex;
223  const D& rValue = pData[nIndex].aValue; // the value "copied"
224  do
225  {
226  pData[nIndex].nEnd += nAccessCount;
227  if (pData[nIndex].nEnd >= nMaxAccess)
228  {
229  pData[nIndex].nEnd = nMaxAccess;
230  nCount = nIndex + 1; // discard trailing entries
231  }
232  } while (++nIndex < nCount);
233  return rValue;
234 }
235 
236 template< typename A, typename D >
237 void ScCompressedArray<A,D>::InsertPreservingSize( A nStart, size_t nAccessCount, const D& rFillValue )
238 {
239  const A nPrevLastPos = GetLastPos();
240 
241  Insert(nStart, nAccessCount);
242  for (A i = nStart; i < A(nStart + nAccessCount); ++i)
243  SetValue(i, rFillValue);
244 
245  const A nNewLastPos = GetLastPos();
246  Remove(nPrevLastPos, nNewLastPos - nPrevLastPos);
247 }
248 
249 template< typename A, typename D >
250 void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
251 {
252  A nEnd = nStart + nAccessCount - 1;
253  size_t nIndex = this->Search( nStart);
254  // equalize/combine/remove all entries in between
255  if (nEnd > pData[nIndex].nEnd)
256  this->SetValue( nStart, nEnd, pData[nIndex].aValue);
257  // remove an exactly matching entry by shifting up all following by one
258  if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
259  pData[nIndex].nEnd == nEnd && nIndex < nCount-1)
260  {
261  // In case removing an entry results in two adjacent entries with
262  // identical data, combine them into one. This is also necessary to
263  // make the algorithm used in SetValue() work correctly, it relies on
264  // the fact that consecutive values actually differ.
265  size_t nRemove;
266  if (nIndex > 0 && pData[nIndex-1].aValue == pData[nIndex+1].aValue)
267  {
268  nRemove = 2;
269  --nIndex;
270  }
271  else
272  nRemove = 1;
273  memmove( pData.get() + nIndex, pData.get() + nIndex + nRemove, (nCount - (nIndex +
274  nRemove)) * sizeof(DataEntry));
275  nCount -= nRemove;
276  }
277  // adjust end rows, nIndex still being valid
278  do
279  {
280  pData[nIndex].nEnd -= nAccessCount;
281  } while (++nIndex < nCount);
282  pData[nCount-1].nEnd = nMaxAccess;
283 }
284 
285 template< typename A, typename D >
286 void ScCompressedArray<A,D>::RemovePreservingSize( A nStart, size_t nAccessCount, const D& rFillValue )
287 {
288  const A nPrevLastPos = GetLastPos();
289 
290  Remove(nStart, nAccessCount);
291 
292  const A nNewLastPos = GetLastPos();
293  InsertPreservingSize(nNewLastPos, nNewLastPos - nPrevLastPos, rFillValue);
294 }
295 
296 template< typename A, typename D >
298 {
299  ++mnRegion;
300  if (mnRegion > mrArray.pData[mnIndex].nEnd)
301  ++mnIndex;
302 }
303 
304 template< typename A, typename D >
306 {
307  A nRegion = mnRegion + nAccessCount;
308  auto nIndex = mnIndex;
309  while (nRegion > mrArray.pData[nIndex].nEnd)
310  ++nIndex;
311  return Iterator(mrArray, nIndex, nRegion);
312 }
313 
314 // === ScBitMaskCompressedArray ==============================================
315 
316 template< typename A, typename D >
318  const D& rValueToAnd )
319 {
320  if (nStart > nEnd)
321  return;
322 
323  size_t nIndex = this->Search( nStart);
324  do
325  {
326  if ((this->pData[nIndex].aValue & rValueToAnd) != this->pData[nIndex].aValue)
327  {
328  A nS = ::std::max<A>( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
329  A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
330  this->SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd);
331  if (nE >= nEnd)
332  break; // while
333  nIndex = this->Search( nE + 1);
334  }
335  else if (this->pData[nIndex].nEnd >= nEnd)
336  break; // while
337  else
338  ++nIndex;
339  } while (nIndex < this->nCount);
340 }
341 
342 template< typename A, typename D >
344  const D& rValueToOr )
345 {
346  if (nStart > nEnd)
347  return;
348 
349  size_t nIndex = this->Search( nStart);
350  do
351  {
352  if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
353  {
354  A nS = ::std::max<A>( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
355  A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
356  this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
357  if (nE >= nEnd)
358  break; // while
359  nIndex = this->Search( nE + 1);
360  }
361  else if (this->pData[nIndex].nEnd >= nEnd)
362  break; // while
363  else
364  ++nIndex;
365  } while (nIndex < this->nCount);
366 }
367 
368 template< typename A, typename D >
370  const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
371  const D& rValueToAnd )
372 {
373  size_t nIndex = 0;
374  A nRegionEnd;
375  for (A j=nStart; j<=nEnd; ++j)
376  {
377  const D& rValue = (j==nStart ?
378  rArray.GetValue( j, nIndex, nRegionEnd) :
379  rArray.GetNextValue( nIndex, nRegionEnd));
380  if (nRegionEnd > nEnd)
381  nRegionEnd = nEnd;
382  this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
383  j = nRegionEnd;
384  }
385 }
386 
387 template< typename A, typename D >
389 {
390  A nEnd = ::std::numeric_limits<A>::max();
391  size_t nIndex = this->nCount-1;
392  while (true)
393  {
394  if (this->pData[nIndex].aValue & rBitMask)
395  {
396  nEnd = this->pData[nIndex].nEnd;
397  break; // while
398  }
399  else
400  {
401  if (nIndex > 0)
402  {
403  --nIndex;
404  if (this->pData[nIndex].nEnd < 0)
405  break; // while
406  }
407  else
408  break; // while
409  }
410  }
411  return nEnd;
412 }
413 
414 // === Force instantiation of specializations ================================
415 
416 template class ScCompressedArray< SCROW, CRFlags>; // flags, base class
417 template class ScBitMaskCompressedArray< SCROW, CRFlags>; // flags
422 
423 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
const D & GetNextValue(size_t &nIndex, A &nEnd) const
Get next value and it's region end row.
sal_Int32 nIndex
void CopyFromAnded(const ScBitMaskCompressedArray &rArray, A nStart, A nEnd, const D &rValueToAnd)
Copy values from rArray and bitwise AND them with rValueToAnd.
void Remove(A nStart, size_t nCount)
std::unique_ptr< ContentProperties > pData
void AndValue(A nPos, const D &rValueToAnd)
void InsertPreservingSize(A nStart, size_t nCount, const D &rFillValue)
virtual ~ScCompressedArray()
A GetLastAnyBitAccess(const D &rBitMask) const
Return the last row where an entry meets the condition: ((aValue & rBitMask) != 0), start searching at 0.
const sal_uInt8 A
Definition: xlformula.cxx:52
css::uno::Any const & rValue
const BorderLinePrimitive2D *pCandidateB assert(pCandidateA)
int nCount
SC_DLLPUBLIC size_t Search(A nPos) const
Obtain index into entries for nPos.
int i
const ScCompressedArray & mrArray
void SetValue(A nPos, const D &rValue)
void RemovePreservingSize(A nStart, size_t nCount, const D &rFillValue)
ScCompressedArray(A nMaxAccess, const D &rValue)
Construct with nMaxAccess=MAXROW, for example.
const D & GetValue(A nPos) const
Iterator operator+(size_t) const
void CopyFrom(const ScCompressedArray &rArray, A nStart, A nEnd)
Copy rArray.nStart+nSourceDy to this.nStart.
Compressed array of row (or column) entries, e.g.
The data type represents bits, manageable by bitwise operations.
int mnIndex
void OrValue(A nPos, const D &rValueToOr)
const D & Insert(A nStart, size_t nCount)
Insert rows before nStart and copy value for inserted rows from nStart-1, return that value...
std::unique_ptr< DataEntry[]> pData