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