LibreOffice Module sc (master)  1
markmulti.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 <markmulti.hxx>
21 #include <markarr.hxx>
22 #include <rangelst.hxx>
23 #include <segmenttree.hxx>
24 #include <sheetlimits.hxx>
25 #include <sal/log.hxx>
26 #include <o3tl/sorted_vector.hxx>
27 
28 #include <algorithm>
29 
30 ScMultiSel::ScMultiSel(const ScSheetLimits& rSheetLimits)
31  : aRowSel(rSheetLimits), mrSheetLimits(rSheetLimits)
32 {
33 }
34 
36 {
37 }
38 
40 {
42  aRowSel = rOther.aRowSel;
43  return *this;
44 }
45 
47 {
48  aMultiSelContainer = std::move(rOther.aMultiSelContainer);
49  aRowSel = std::move(rOther.aRowSel);
50  return *this;
51 }
52 
53 
55 {
56  aMultiSelContainer.clear();
57  aRowSel.Reset();
58 }
59 
61 {
62  SCCOL nCount = 0;
63  for (const auto & i : aMultiSelContainer)
64  if (i.HasMarks())
65  ++nCount;
66  return nCount;
67 }
68 
69 bool ScMultiSel::HasMarks( SCCOL nCol ) const
70 {
71  if ( aRowSel.HasMarks() )
72  return true;
73  return nCol < static_cast<SCCOL>(aMultiSelContainer.size()) && aMultiSelContainer[nCol].HasMarks();
74 }
75 
76 bool ScMultiSel::HasOneMark( SCCOL nCol, SCROW& rStartRow, SCROW& rEndRow ) const
77 {
78  SCROW nRow1 = -1, nRow2 = -1, nRow3 = -1, nRow4 = -1;
79  bool aResult1 = aRowSel.HasOneMark( nRow1, nRow2 );
80  bool aResult2 = nCol < static_cast<SCCOL>(aMultiSelContainer.size())
81  && aMultiSelContainer[nCol].HasOneMark( nRow3, nRow4 );
82 
83  if ( aResult1 || aResult2 )
84  {
85  if ( aResult1 && aResult2 )
86  {
87  if ( ( nRow2 + 1 ) < nRow3 )
88  return false;
89  if ( ( nRow4 + 1 ) < nRow1 )
90  return false;
91 
92  auto aRows = std::minmax( { nRow1, nRow2, nRow3, nRow4 } );
93  rStartRow = aRows.first;
94  rEndRow = aRows.second;
95  return true;
96  }
97  if ( aResult1 )
98  {
99  rStartRow = nRow1;
100  rEndRow = nRow2;
101  return true;
102  }
103 
104  rStartRow = nRow3;
105  rEndRow = nRow4;
106  return true;
107  }
108 
109  return false;
110 }
111 
112 bool ScMultiSel::GetMark( SCCOL nCol, SCROW nRow ) const
113 {
114  if ( aRowSel.GetMark( nRow ) )
115  return true;
116  return nCol < static_cast<SCCOL>(aMultiSelContainer.size()) && aMultiSelContainer[nCol].GetMark(nRow);
117 }
118 
119 bool ScMultiSel::IsAllMarked( SCCOL nCol, SCROW nStartRow, SCROW nEndRow ) const
120 {
121  bool bHasMarks1 = aRowSel.HasMarks();
122  bool bHasMarks2 = nCol < static_cast<SCCOL>(aMultiSelContainer.size()) && aMultiSelContainer[nCol].HasMarks();
123 
124  if ( !bHasMarks1 && !bHasMarks2 )
125  return false;
126 
127  if ( bHasMarks1 && bHasMarks2 )
128  {
129  if ( aRowSel.IsAllMarked( nStartRow, nEndRow ) ||
130  aMultiSelContainer[nCol].IsAllMarked( nStartRow, nEndRow ) )
131  return true;
132  ScMultiSelIter aMultiIter( *this, nCol );
134  bool bRet = aMultiIter.GetRangeData( nStartRow, aRowRange );
135  return bRet && aRowRange.mbValue && aRowRange.mnRow2 >= nEndRow;
136  }
137 
138  if ( bHasMarks1 )
139  return aRowSel.IsAllMarked( nStartRow, nEndRow );
140 
141  return aMultiSelContainer[nCol].IsAllMarked( nStartRow, nEndRow );
142 }
143 
144 bool ScMultiSel::HasEqualRowsMarked( SCCOL nCol1, SCCOL nCol2 ) const
145 {
146  bool bCol1Exists = nCol1 < static_cast<SCCOL>(aMultiSelContainer.size());
147  bool bCol2Exists = nCol2 < static_cast<SCCOL>(aMultiSelContainer.size());
148  if ( bCol1Exists || bCol2Exists )
149  {
150  if ( bCol1Exists && bCol2Exists )
151  return aMultiSelContainer[nCol1] == aMultiSelContainer[nCol2];
152  else if ( bCol1Exists )
153  return !aMultiSelContainer[nCol1].HasMarks();
154  else
155  return !aMultiSelContainer[nCol2].HasMarks();
156  }
157 
158  return true;
159 }
160 
161 SCROW ScMultiSel::GetNextMarked( SCCOL nCol, SCROW nRow, bool bUp ) const
162 {
163  if ( nCol >= static_cast<SCCOL>(aMultiSelContainer.size()) || !aMultiSelContainer[nCol].HasMarks() )
164  return aRowSel.GetNextMarked( nRow, bUp );
165 
166  SCROW nRow1, nRow2;
167  nRow1 = aRowSel.GetNextMarked( nRow, bUp );
168  nRow2 = aMultiSelContainer[nCol].GetNextMarked( nRow, bUp );
169  if ( nRow1 == nRow2 )
170  return nRow1;
171  if ( nRow1 == -1 )
172  return nRow2;
173  if ( nRow2 == -1 )
174  return nRow1;
175 
176  PutInOrder( nRow1, nRow2 );
177  return ( bUp ? nRow2 : nRow1 );
178 }
179 
180 void ScMultiSel::MarkAllCols( SCROW nStartRow, SCROW nEndRow )
181 {
183  for ( SCCOL nCol = mrSheetLimits.mnMaxCol; nCol >= 0; --nCol )
184  {
185  aMultiSelContainer[nCol].SetMarkArea( nStartRow, nEndRow, true );
186  }
187 }
188 
189 void ScMultiSel::SetMarkArea( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCROW nEndRow, bool bMark )
190 {
191  if ( nStartCol == 0 && nEndCol == mrSheetLimits.mnMaxCol )
192  {
193  aRowSel.SetMarkArea( nStartRow, nEndRow, bMark );
194  if ( !bMark )
195  {
196  // Remove any per column marks for the row range.
197  for ( auto& aIter : aMultiSelContainer )
198  if ( aIter.HasMarks() )
199  aIter.SetMarkArea( nStartRow, nEndRow, false );
200  }
201  return;
202  }
203 
204  // Bad case - we need to extend aMultiSelContainer size to MAXCOL
205  // and move row marks from aRowSel to aMultiSelContainer
206  if ( !bMark && aRowSel.HasMarks() )
207  {
208  SCROW nBeg, nLast = nEndRow;
209  if ( aRowSel.GetMark( nStartRow ) )
210  {
211  nBeg = nStartRow;
212  nLast = aRowSel.GetMarkEnd( nStartRow, false );
213  }
214  else
215  {
216  nBeg = aRowSel.GetNextMarked( nStartRow, false );
217  if ( nBeg != mrSheetLimits.GetMaxRowCount() )
218  nLast = aRowSel.GetMarkEnd( nBeg, false );
219  }
220 
221  if ( nBeg != mrSheetLimits.GetMaxRowCount() && nLast >= nEndRow )
222  MarkAllCols( nBeg, nEndRow );
223  else
224  {
225  while ( nBeg != mrSheetLimits.GetMaxRowCount() && nLast < nEndRow )
226  {
227  MarkAllCols( nBeg, nLast );
228  nBeg = aRowSel.GetNextMarked( nLast + 1, false );
229  if ( nBeg != mrSheetLimits.GetMaxRowCount() )
230  nLast = aRowSel.GetMarkEnd( nBeg, false );
231  }
232  if ( nBeg != mrSheetLimits.GetMaxRowCount() && nLast >= nEndRow )
233  MarkAllCols( nBeg, nEndRow );
234  }
235 
236  aRowSel.SetMarkArea( nStartRow, nEndRow, false );
237  }
238 
239  if (nEndCol >= static_cast<SCCOL>(aMultiSelContainer.size()))
240  aMultiSelContainer.resize(nEndCol+1, ScMarkArray(mrSheetLimits));
241  for ( SCCOL nColIter = nEndCol; nColIter >= nStartCol; --nColIter )
242  aMultiSelContainer[nColIter].SetMarkArea( nStartRow, nEndRow, bMark );
243 }
244 
249 void ScMultiSel::Set( ScRangeList const & rList )
250 {
251  Clear();
252  if (rList.size() == 0)
253  return;
254 
255  // sort by row to make the combining/merging faster
256  auto aNewList = rList;
257  std::sort(aNewList.begin(), aNewList.end(),
258  [](const ScRange& lhs, const ScRange& rhs)
259  {
260  return lhs.aStart.Row() < rhs.aStart.Row();
261  });
262 
263  std::vector<std::vector<ScMarkEntry>> aMarkEntriesPerCol(mrSheetLimits.mnMaxCol+1);
264 
265  SCCOL nMaxCol = -1;
266  int i = 0;
267  for (const ScRange& rRange : aNewList)
268  {
269  SCCOL nStartCol = rRange.aStart.Col();
270  SCROW nStartRow = rRange.aStart.Row();
271  SCCOL nEndCol = rRange.aEnd.Col();
272  SCROW nEndRow = rRange.aEnd.Row();
273  assert( nEndRow >= nStartRow && "this method assumes the input data has ranges with endrow>=startrow");
274  assert( nEndCol >= nStartCol && "this method assumes the input data has ranges with endcol>=startcol");
275  if ( nStartCol == 0 && nEndCol == mrSheetLimits.mnMaxCol )
276  aRowSel.SetMarkArea( nStartRow, nEndRow, /*bMark*/true );
277  else
278  {
279  for ( SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol )
280  {
281  auto & rMarkEntries = aMarkEntriesPerCol[nCol];
282  int nEntries = rMarkEntries.size();
283  if (nEntries > 1 && nStartRow >= rMarkEntries[nEntries-2].nRow+1
284  && nStartRow <= rMarkEntries[nEntries-1].nRow+1)
285  {
286  // overlaps or directly adjacent previous range
287  rMarkEntries.back().nRow = std::max(nEndRow, rMarkEntries.back().nRow);
288  }
289  else
290  {
291  // new range
292  if (nStartRow > 0)
293  rMarkEntries.emplace_back(ScMarkEntry{nStartRow-1, false});
294  rMarkEntries.emplace_back(ScMarkEntry{nEndRow, true});
295  }
296  }
297  nMaxCol = std::max(nMaxCol, nEndCol);
298  }
299  ++i;
300  }
301 
302  aMultiSelContainer.resize(nMaxCol+1, ScMarkArray(mrSheetLimits));
303  for (SCCOL nCol = 0; nCol<=nMaxCol; ++nCol)
304  if (!aMarkEntriesPerCol[nCol].empty())
305  {
306  aMultiSelContainer[nCol].Set( aMarkEntriesPerCol[nCol] );
307  aMarkEntriesPerCol[nCol].clear(); // reduce peak memory usage
308  }
309 }
310 
311 bool ScMultiSel::IsRowMarked( SCROW nRow ) const
312 {
313  return aRowSel.GetMark( nRow );
314 }
315 
316 bool ScMultiSel::IsRowRangeMarked( SCROW nStartRow, SCROW nEndRow ) const
317 {
318  if ( !aRowSel.GetMark( nStartRow ) )
319  return false;
320  SCROW nLast = aRowSel.GetMarkEnd( nStartRow, false );
321  return ( nLast >= nEndRow );
322 }
323 
325 {
326  ScMultiSelIter aMultiIter( *this, nCol );
327  ScMarkArray aMarkArray(mrSheetLimits);
328  SCROW nTop, nBottom;
329  while( aMultiIter.Next( nTop, nBottom ) )
330  aMarkArray.SetMarkArea( nTop, nBottom, true );
331  return aMarkArray;
332 }
333 
335 {
336  if ( aRowSel.HasMarks() )
337  return true;
338  for ( const auto& aPair : aMultiSelContainer )
339  if ( aPair.HasMarks() )
340  return true;
341  return false;
342 }
343 
344 void ScMultiSel::ShiftCols(SCCOL nStartCol, long nColOffset)
345 {
346  if (nStartCol > mrSheetLimits.mnMaxCol)
347  return;
348 
349  ScMultiSel aNewMultiSel(*this);
350  Clear();
351 
352  if (nColOffset < 0)
353  {
354  // columns that would be moved on the left of nStartCol must be removed
355  const SCCOL nEndPos = std::min<SCCOL>(aNewMultiSel.aMultiSelContainer.size(), nStartCol - nColOffset);
356  for (SCCOL nSearchPos = nStartCol; nSearchPos < nEndPos; ++nSearchPos)
357  aNewMultiSel.aMultiSelContainer[nSearchPos].Reset();
358  }
359 
360  SCCOL nCol = 0;
361  for (const auto& aSourceArray : aNewMultiSel.aMultiSelContainer)
362  {
363  SCCOL nDestCol = nCol;
364  if (nDestCol >= nStartCol)
365  {
366  nDestCol += nColOffset;
367  if (nDestCol < 0)
368  nDestCol = 0;
369  else if (nDestCol > mrSheetLimits.mnMaxCol)
370  nDestCol = mrSheetLimits.mnMaxCol;
371  }
372  if (nDestCol >= static_cast<SCCOL>(aMultiSelContainer.size()))
373  aMultiSelContainer.resize(nDestCol, ScMarkArray(mrSheetLimits));
374  aMultiSelContainer[nDestCol] = aSourceArray;
375  ++nCol;
376  }
377  aRowSel = aNewMultiSel.aRowSel;
378 
379  if (!(nColOffset > 0 && nStartCol > 0 && nStartCol < static_cast<SCCOL>(aNewMultiSel.aMultiSelContainer.size())))
380  return;
381 
382  // insert nColOffset new columns, and select their cells if they are selected
383  // both in the old column at nStartPos and in the previous column
384  auto& rPrevPos = aNewMultiSel.aMultiSelContainer[nStartCol - 1];
385  auto& rStartPos = aNewMultiSel.aMultiSelContainer[nStartCol];
386  auto& rNewCol = aMultiSelContainer[nStartCol];
387  rNewCol = rStartPos;
388  rNewCol.Intersect(rPrevPos);
389  if (nStartCol + nColOffset >= static_cast<SCCOL>(aNewMultiSel.aMultiSelContainer.size()))
390  aNewMultiSel.aMultiSelContainer.resize(nStartCol + nColOffset, ScMarkArray(mrSheetLimits));
391  for (long i = 1; i < nColOffset; ++i)
392  aMultiSelContainer[nStartCol + i] = rNewCol;
393 }
394 
395 void ScMultiSel::ShiftRows(SCROW nStartRow, long nRowOffset)
396 {
397  for (auto& aPair: aMultiSelContainer)
398  aPair.Shift(nStartRow, nRowOffset);
399  aRowSel.Shift(nStartRow, nRowOffset);
400 }
401 
403 {
404  return aRowSel;
405 }
406 
408 {
409  if (nCol >= static_cast<SCCOL>(aMultiSelContainer.size()))
410  return nullptr;
411  return &aMultiSelContainer[nCol];
412 }
413 
415  aMarkArrayIter(nullptr),
416  nNextSegmentStart(0)
417 {
418  bool bHasMarks1 = rMultiSel.aRowSel.HasMarks();
419  bool bHasMarks2 = nCol < static_cast<SCCOL>(rMultiSel.aMultiSelContainer.size())
420  && rMultiSel.aMultiSelContainer[nCol].HasMarks();
421 
422  if (bHasMarks1 && bHasMarks2)
423  {
424  pRowSegs.reset( new ScFlatBoolRowSegments(rMultiSel.mrSheetLimits.mnMaxRow) );
425  pRowSegs->setFalse( 0, rMultiSel.mrSheetLimits.mnMaxRow );
426  {
427  ScMarkArrayIter aMarkIter( &rMultiSel.aRowSel );
428  SCROW nTop, nBottom;
429  while ( aMarkIter.Next( nTop, nBottom ) )
430  pRowSegs->setTrue( nTop, nBottom );
431  }
432 
433  {
434  ScMarkArrayIter aMarkIter( &rMultiSel.aMultiSelContainer[nCol] );
435  SCROW nTop, nBottom;
436  while ( aMarkIter.Next( nTop, nBottom ) )
437  pRowSegs->setTrue( nTop, nBottom );
438  }
439  }
440  else if (bHasMarks1)
441  {
442  aMarkArrayIter.reset( &rMultiSel.aRowSel);
443  }
444  else if (bHasMarks2)
445  {
446  aMarkArrayIter.reset( &rMultiSel.aMultiSelContainer[nCol]);
447  }
448 }
449 
451 {
452 }
453 
454 bool ScMultiSelIter::Next( SCROW& rTop, SCROW& rBottom )
455 {
456  if (pRowSegs)
457  {
459  bool bRet = pRowSegs->getRangeData( nNextSegmentStart, aRowRange );
460  if ( bRet && !aRowRange.mbValue )
461  {
462  nNextSegmentStart = aRowRange.mnRow2 + 1;
463  bRet = pRowSegs->getRangeData( nNextSegmentStart, aRowRange );
464  }
465  if ( bRet )
466  {
467  rTop = aRowRange.mnRow1;
468  rBottom = aRowRange.mnRow2;
469  nNextSegmentStart = rBottom + 1;
470  }
471  return bRet;
472  }
473 
474  return aMarkArrayIter.Next( rTop, rBottom);
475 }
476 
478 {
479  assert(pRowSegs);
480  return pRowSegs->getRangeData( nRow, rRowRange);
481 }
482 
483 
484 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
ScAddress aStart
Definition: address.hxx:500
void SetMarkArea(SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCROW nEndRow, bool bMark)
Definition: markmulti.cxx:189
SCROW Row() const
Definition: address.hxx:262
bool HasOneMark(SCROW &rStartRow, SCROW &rEndRow) const
Definition: markarr.cxx:238
bool HasOneMark(SCCOL nCol, SCROW &rStartRow, SCROW &rEndRow) const
Definition: markmulti.cxx:76
bool IsAllMarked(SCROW nStartRow, SCROW nEndRow) const
Definition: markarr.cxx:224
MapType aMultiSelContainer
Definition: markmulti.hxx:36
const ScMarkArray * GetMultiSelArray(SCCOL nCol) const
Definition: markmulti.cxx:407
SCROW GetMaxRowCount() const
Definition: sheetlimits.hxx:61
void SetMarkArea(SCROW nStartRow, SCROW nEndRow, bool bMarked)
Definition: markarr.cxx:108
ScMarkArrayIter aMarkArrayIter
Definition: markmulti.hxx:81
bool GetRangeData(SCROW nRow, ScFlatBoolRowSegments::RangeData &rRowRange) const
Only to be used by ScMultiSel::IsAllMarked() or otherwise sure that a segment tree is actually used...
Definition: markmulti.cxx:477
bool Next(SCROW &rTop, SCROW &rBottom)
Definition: markarr.cxx:452
bool Next(SCROW &rTop, SCROW &rBottom)
Definition: markmulti.cxx:454
bool HasMarks(SCCOL nCol) const
Definition: markmulti.cxx:69
ScMultiSelIter(const ScMultiSel &rMultiSel, SCCOL nCol)
Definition: markmulti.cxx:414
ScMultiSel(ScSheetLimits const &)
bool GetMark(SCCOL nCol, SCROW nRow) const
Definition: markmulti.cxx:112
const BorderLinePrimitive2D *pCandidateB assert(pCandidateA)
This is a rather odd datastructure.
Definition: markarr.hxx:43
int nCount
bool IsRowMarked(SCROW nRow) const
Definition: markmulti.cxx:311
void Shift(SCROW nStartRow, long nOffset)
Definition: markarr.cxx:335
void Clear()
Definition: markmulti.cxx:54
bool HasMarks() const
Definition: markarr.hxx:63
void PutInOrder(T &nStart, T &nEnd)
Definition: address.hxx:954
void Reset(bool bMarked=false, SCSIZE nNeeded=1)
Definition: markarr.cxx:52
SCCOL GetMultiSelectionCount() const
Definition: markmulti.cxx:60
int i
const SCROW mnMaxRow
Maximum addressable column.
Definition: sheetlimits.hxx:30
SCROW GetNextMarked(SCCOL nCol, SCROW nRow, bool bUp) const
Definition: markmulti.cxx:161
sal_Int16 SCCOL
Definition: types.hxx:22
size_t size() const
Definition: rangelst.hxx:90
SCROW GetMarkEnd(SCROW nRow, bool bUp) const
Definition: markarr.cxx:316
std::unique_ptr< ScFlatBoolRowSegments > pRowSegs
Definition: markmulti.hxx:80
SCROW nNextSegmentStart
Definition: markmulti.hxx:82
bool HasEqualRowsMarked(SCCOL nCol1, SCCOL nCol2) const
Definition: markmulti.cxx:144
bool HasAnyMarks() const
Definition: markmulti.cxx:334
const ScMarkArray & GetRowSelArray() const
Definition: markmulti.cxx:402
ScMultiSel & operator=(const ScMultiSel &rMultiSel)
Definition: markmulti.cxx:39
void MarkAllCols(SCROW nStartRow, SCROW nEndRow)
Definition: markmulti.cxx:180
ScMarkArray aRowSel
Definition: markmulti.hxx:37
sal_Int32 SCROW
Definition: types.hxx:18
ScMarkArray GetMarkArray(SCCOL nCol) const
Definition: markmulti.cxx:324
bool IsRowRangeMarked(SCROW nStartRow, SCROW nEndRow) const
Definition: markmulti.cxx:316
bool IsAllMarked(SCCOL nCol, SCROW nStartRow, SCROW nEndRow) const
Definition: markmulti.cxx:119
const SCCOL mnMaxCol
Definition: sheetlimits.hxx:29
void reset(const ScMarkArray *pNewArray)
Definition: markarr.cxx:446
bool GetMark(SCROW nRow) const
Definition: markarr.cxx:98
void Set(ScRangeList const &)
optimised init-from-range-list.
Definition: markmulti.cxx:249
const ScSheetLimits & mrSheetLimits
Definition: markmulti.hxx:38
SCROW GetNextMarked(SCROW nRow, bool bUp) const
Including current row, may return -1 if bUp and not found.
Definition: markarr.cxx:293
void ShiftCols(SCCOL nStartCol, long nColOffset)
Definition: markmulti.cxx:344
void ShiftRows(SCROW nStartRow, long nRowOffset)
Definition: markmulti.cxx:395