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