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