LibreOffice Module sc (master)  1
markarr.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 <markarr.hxx>
21 #include <address.hxx>
22 #include <sheetlimits.hxx>
23 #include <vector>
24 
26  mrSheetLimits(rLimits)
27 {
28  Reset(false);
29 }
30 
31 // Move constructor
33  : mrSheetLimits(rOther.mrSheetLimits)
34 {
35  operator=(std::move(rOther));
36 }
37 
38 // Copy constructor
40  : mrSheetLimits(rOther.mrSheetLimits)
41 {
42  operator=(rOther);
43 }
44 
45 void ScMarkArray::Reset( bool bMarked, SCSIZE nNeeded )
46 {
47  // always create pData here
48  // (or have separate method to ensure pData)
49 
50  assert(nNeeded);
51  mvData.resize(1);
52  mvData.reserve(nNeeded);
53  mvData[0].nRow = mrSheetLimits.mnMaxRow;
54  mvData[0].bMarked = bMarked;
55 }
56 
57 // Iterative implementation of Binary Search
58 bool ScMarkArray::Search( SCROW nRow, SCSIZE& nIndex ) const
59 {
60  assert(mvData.size() > 0);
61  SCSIZE nHi = mvData.size() - 1;
62  SCSIZE nLo = 0;
63 
64  while ( nLo <= nHi )
65  {
66  SCSIZE i = (nLo + nHi) / 2;
67 
68  if (mvData[i].nRow < nRow)
69  {
70  // If [nRow] greater, ignore left half
71  nLo = i + 1;
72  }
73  else if ((i > 0) && (mvData[i - 1].nRow >= nRow))
74  {
75  // If [nRow] is smaller, ignore right half
76  nHi = i - 1;
77  }
78  else
79  {
80  // found
81  nIndex=i;
82  return true;
83  }
84  }
85 
86  // not found
87  nIndex=0;
88  return false;
89 }
90 
91 bool ScMarkArray::GetMark( SCROW nRow ) const
92 {
93  SCSIZE i;
94  if (Search( nRow, i ))
95  return mvData[i].bMarked;
96  else
97  return false;
98 
99 }
100 
101 void ScMarkArray::SetMarkArea( SCROW nStartRow, SCROW nEndRow, bool bMarked )
102 {
103  if (!(mrSheetLimits.ValidRow(nStartRow) && mrSheetLimits.ValidRow(nEndRow)))
104  return;
105 
106  if ((nStartRow == 0) && (nEndRow == mrSheetLimits.mnMaxRow))
107  {
108  Reset(bMarked);
109  }
110  else
111  {
112  SCSIZE ni; // number of entries in beginning
113  SCSIZE nInsert; // insert position (mnMaxRow+1 := no insert)
114  bool bCombined = false;
115  bool bSplit = false;
116  if ( nStartRow > 0 )
117  {
118  // skip beginning
119  SCSIZE nIndex;
120  Search( nStartRow, nIndex );
121  ni = nIndex;
122 
123  nInsert = mrSheetLimits.GetMaxRowCount();
124  if ( mvData[ni].bMarked != bMarked )
125  {
126  if ( ni == 0 || (mvData[ni-1].nRow < nStartRow - 1) )
127  { // may be a split or a simple insert or just a shrink,
128  // row adjustment is done further down
129  if ( mvData[ni].nRow > nEndRow )
130  bSplit = true;
131  ni++;
132  nInsert = ni;
133  }
134  else if ( ni > 0 && mvData[ni-1].nRow == nStartRow - 1 )
135  nInsert = ni;
136  }
137  if ( ni > 0 && mvData[ni-1].bMarked == bMarked )
138  { // combine
139  mvData[ni-1].nRow = nEndRow;
140  nInsert = mrSheetLimits.GetMaxRowCount();
141  bCombined = true;
142  }
143  }
144  else
145  {
146  nInsert = 0;
147  ni = 0;
148  }
149 
150  SCSIZE nj = ni; // stop position of range to replace
151  while ( nj < mvData.size() && mvData[nj].nRow <= nEndRow )
152  nj++;
153  if ( !bSplit )
154  {
155  if ( nj < mvData.size() && mvData[nj].bMarked == bMarked )
156  { // combine
157  if ( ni > 0 )
158  {
159  if ( mvData[ni-1].bMarked == bMarked )
160  { // adjacent entries
161  mvData[ni-1].nRow = mvData[nj].nRow;
162  nj++;
163  }
164  else if ( ni == nInsert )
165  mvData[ni-1].nRow = nStartRow - 1; // shrink
166  }
167  nInsert = mrSheetLimits.GetMaxRowCount();
168  bCombined = true;
169  }
170  else if ( ni > 0 && ni == nInsert )
171  mvData[ni-1].nRow = nStartRow - 1; // shrink
172  }
173  if ( ni < nj )
174  { // remove middle entries
175  if ( !bCombined )
176  { // replace one entry
177  mvData[ni].nRow = nEndRow;
178  mvData[ni].bMarked = bMarked;
179  ni++;
180  nInsert = mrSheetLimits.GetMaxRowCount();
181  }
182  if ( ni < nj )
183  { // remove entries
184  mvData.erase(mvData.begin() + ni, mvData.begin() + nj);
185  }
186  }
187 
188  if ( nInsert < sal::static_int_cast<SCSIZE>(mrSheetLimits.GetMaxRowCount()) )
189  { // insert or append new entry
190  if ( nInsert <= mvData.size() )
191  {
192  if ( !bSplit )
193  mvData.insert(mvData.begin() + nInsert, { nEndRow, bMarked });
194  else
195  {
196  mvData.insert(mvData.begin() + nInsert, 2, { nEndRow, bMarked });
197  mvData[nInsert+1] = mvData[nInsert-1];
198  }
199  }
200  else
201  mvData.push_back(ScMarkEntry{ nEndRow, bMarked });
202  if ( nInsert )
203  mvData[nInsert-1].nRow = nStartRow - 1;
204  }
205  }
206 }
207 
212 void ScMarkArray::Set( std::vector<ScMarkEntry> && rMarkEntries )
213 {
214  mvData = std::move(rMarkEntries);
215 }
216 
217 bool ScMarkArray::IsAllMarked( SCROW nStartRow, SCROW nEndRow ) const
218 {
219  SCSIZE nStartIndex;
220  SCSIZE nEndIndex;
221 
222  if (Search( nStartRow, nStartIndex ))
223  if (mvData[nStartIndex].bMarked)
224  if (Search( nEndRow, nEndIndex ))
225  if (nEndIndex==nStartIndex)
226  return true;
227 
228  return false;
229 }
230 
231 bool ScMarkArray::HasOneMark( SCROW& rStartRow, SCROW& rEndRow ) const
232 {
233  bool bRet = false;
234  if ( mvData.size() == 1 )
235  {
236  if ( mvData[0].bMarked )
237  {
238  rStartRow = 0;
239  rEndRow = mrSheetLimits.mnMaxRow;
240  bRet = true;
241  }
242  }
243  else if ( mvData.size() == 2 )
244  {
245  if ( mvData[0].bMarked )
246  {
247  rStartRow = 0;
248  rEndRow = mvData[0].nRow;
249  }
250  else
251  {
252  rStartRow = mvData[0].nRow + 1;
253  rEndRow = mrSheetLimits.mnMaxRow;
254  }
255  bRet = true;
256  }
257  else if ( mvData.size() == 3 )
258  {
259  if ( mvData[1].bMarked )
260  {
261  rStartRow = mvData[0].nRow + 1;
262  rEndRow = mvData[1].nRow;
263  bRet = true;
264  }
265  }
266  return bRet;
267 }
268 
269 bool ScMarkArray::operator==( const ScMarkArray& rOther ) const
270 {
271  return mvData == rOther.mvData;
272 }
273 
275 {
276  mvData = rOther.mvData;
277  return *this;
278 }
279 
281 {
282  mvData = std::move(rOther.mvData);
283  return *this;
284 }
285 
286 SCROW ScMarkArray::GetNextMarked( SCROW nRow, bool bUp ) const
287 {
288  SCROW nRet = nRow;
289  if (mrSheetLimits.ValidRow(nRow))
290  {
291  SCSIZE nIndex;
292  Search(nRow, nIndex);
293  if (!mvData[nIndex].bMarked)
294  {
295  if (bUp)
296  {
297  if (nIndex>0)
298  nRet = mvData[nIndex-1].nRow;
299  else
300  nRet = -1;
301  }
302  else
303  nRet = mvData[nIndex].nRow + 1;
304  }
305  }
306  return nRet;
307 }
308 
309 SCROW ScMarkArray::GetMarkEnd( SCROW nRow, bool bUp ) const
310 {
311  SCROW nRet;
312  SCSIZE nIndex;
313  Search(nRow, nIndex);
314  assert( mvData[nIndex].bMarked && "GetMarkEnd without bMarked" );
315  if (bUp)
316  {
317  if (nIndex>0)
318  nRet = mvData[nIndex-1].nRow + 1;
319  else
320  nRet = 0;
321  }
322  else
323  nRet = mvData[nIndex].nRow;
324 
325  return nRet;
326 }
327 
328 void ScMarkArray::Shift(SCROW nStartRow, tools::Long nOffset)
329 {
330  if (nOffset == 0 || nStartRow > mrSheetLimits.mnMaxRow)
331  return;
332 
333  for (size_t i=0; i < mvData.size(); ++i)
334  {
335  auto& rEntry = mvData[i];
336 
337  if (rEntry.nRow < nStartRow)
338  continue;
339  rEntry.nRow += nOffset;
340  if (rEntry.nRow < 0)
341  {
342  rEntry.nRow = 0;
343  }
344  else if (rEntry.nRow > mrSheetLimits.mnMaxRow)
345  {
346  rEntry.nRow = mrSheetLimits.mnMaxRow;
347  }
348  }
349 }
350 
352 {
353  size_t i = 0;
354  size_t j = 0;
355 
356  std::vector<ScMarkEntry> aEntryArray;
357  aEntryArray.reserve(std::max(mvData.size(), rOther.mvData.size()));
358 
359  while (i < mvData.size() && j < rOther.mvData.size())
360  {
361  const auto& rEntry = mvData[i];
362  const auto& rOtherEntry = rOther.mvData[j];
363 
364  if (rEntry.bMarked != rOtherEntry.bMarked)
365  {
366  if (!rOtherEntry.bMarked)
367  {
368  aEntryArray.push_back(rOther.mvData[j++]);
369  while (i < mvData.size() && mvData[i].nRow <= rOtherEntry.nRow)
370  ++i;
371  }
372  else // rEntry not marked
373  {
374  aEntryArray.push_back(mvData[i++]);
375  while (j < rOther.mvData.size() && rOther.mvData[j].nRow <= rEntry.nRow)
376  ++j;
377  }
378  }
379  else // rEntry.bMarked == rOtherEntry.bMarked
380  {
381  if (rEntry.bMarked) // both marked
382  {
383  if (rEntry.nRow <= rOtherEntry.nRow)
384  {
385  aEntryArray.push_back(mvData[i++]); // upper row
386  if (rEntry.nRow == rOtherEntry.nRow)
387  ++j;
388  }
389  else
390  {
391  aEntryArray.push_back(rOther.mvData[j++]); // upper row
392  }
393  }
394  else // both not marked
395  {
396  if (rEntry.nRow <= rOtherEntry.nRow)
397  {
398  aEntryArray.push_back(rOther.mvData[j++]); // lower row
399  while (i < mvData.size() && mvData[i].nRow <= rOtherEntry.nRow)
400  ++i;
401  }
402  else
403  {
404  aEntryArray.push_back(mvData[i++]); // lower row
405  while (j < rOther.mvData.size() && rOther.mvData[j].nRow <= rEntry.nRow)
406  ++j;
407  }
408  }
409  }
410  }
411 
412  assert((i == mvData.size() || j == rOther.mvData.size()) && "Unexpected case.");
413 
414  if (i == mvData.size())
415  {
416  aEntryArray.insert(aEntryArray.end(), rOther.mvData.begin() + j, rOther.mvData.end());
417  }
418  else // j == rOther.nCount
419  {
420  aEntryArray.insert(aEntryArray.end(), mvData.begin() + i, mvData.end());
421  }
422 
423  mvData = std::move(aEntryArray);
424 }
425 
426 
427 // -------------- Iterator ----------------------------------------------
428 
430  pArray( pNewArray ),
431  nPos( 0 )
432 {
433 }
434 
435 void ScMarkArrayIter::reset( const ScMarkArray* pNewArray )
436 {
437  pArray = pNewArray;
438  nPos = 0;
439 }
440 
441 bool ScMarkArrayIter::Next( SCROW& rTop, SCROW& rBottom )
442 {
443  if (!pArray)
444  return false;
445  if ( nPos >= pArray->mvData.size() )
446  return false;
447  while (!pArray->mvData[nPos].bMarked)
448  {
449  ++nPos;
450  if ( nPos >= pArray->mvData.size() )
451  return false;
452  }
453  rBottom = pArray->mvData[nPos].nRow;
454  if (nPos==0)
455  rTop = 0;
456  else
457  rTop = pArray->mvData[nPos-1].nRow + 1;
458  ++nPos;
459  return true;
460 }
461 
462 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
ScMarkArray & operator=(ScMarkArray const &rSource)
sal_Int32 nIndex
std::vector< ScMarkEntry > mvData
Definition: markarr.hxx:46
bool HasOneMark(SCROW &rStartRow, SCROW &rEndRow) const
Definition: markarr.cxx:231
long Long
bool IsAllMarked(SCROW nStartRow, SCROW nEndRow) const
Definition: markarr.cxx:217
bool Search(SCROW nRow, SCSIZE &nIndex) const
Definition: markarr.cxx:58
SCROW GetMaxRowCount() const
Definition: sheetlimits.hxx:66
void SetMarkArea(SCROW nStartRow, SCROW nEndRow, bool bMarked)
Definition: markarr.cxx:101
bool Next(SCROW &rTop, SCROW &rBottom)
Definition: markarr.cxx:441
void Shift(SCROW nStartRow, tools::Long nOffset)
Definition: markarr.cxx:328
size_t SCSIZE
size_t typedef to be able to find places where code was changed from USHORT to size_t and is used to ...
Definition: address.hxx:44
This is a rather odd datastructure.
Definition: markarr.hxx:43
ScMarkArrayIter(const ScMarkArray *pNewArray)
Definition: markarr.cxx:429
void Set(std::vector< ScMarkEntry > &&)
optimised init-from-range-list.
Definition: markarr.cxx:212
void Reset(bool bMarked=false, SCSIZE nNeeded=1)
Definition: markarr.cxx:45
int i
const SCROW mnMaxRow
Maximum addressable column.
Definition: sheetlimits.hxx:30
bool operator==(ScMarkArray const &rOther) const
Definition: markarr.cxx:269
SCROW GetMarkEnd(SCROW nRow, bool bUp) const
Definition: markarr.cxx:309
const ScMarkArray * pArray
Definition: markarr.hxx:80
bool ValidRow(SCROW nRow) const
Definition: sheetlimits.hxx:41
sal_Int32 SCROW
Definition: types.hxx:17
ScMarkArray(const ScSheetLimits &rLimits)
Definition: markarr.cxx:25
void Intersect(const ScMarkArray &rOther)
Definition: markarr.cxx:351
void reset(const ScMarkArray *pNewArray)
Definition: markarr.cxx:435
bool GetMark(SCROW nRow) const
Definition: markarr.cxx:91
SCROW GetNextMarked(SCROW nRow, bool bUp) const
Including current row, may return -1 if bUp and not found.
Definition: markarr.cxx:286
sal_uInt16 nPos
const ScSheetLimits & mrSheetLimits
Definition: markarr.hxx:45