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