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