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