sc/source/core/data/markmulti.cxx

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