sc/source/core/data/markarr.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 <markarr.hxx>
  21 #include <address.hxx>
  22 #include <sheetlimits.hxx>
  23 #include <vector>
  24
  25 ScMarkArray::ScMarkArray(const ScSheetLimits& rLimits) :
  26     mrSheetLimits(rLimits)
  27 {
  28     Reset(false);
  29 }
  30
  31 // Move constructor
  32 ScMarkArray::ScMarkArray( ScMarkArray&& rOther ) noexcept
  33     : mrSheetLimits(rOther.mrSheetLimits)
  34 {
  35     operator=(std::move(rOther));
  36 }
  37
  38 // Copy constructor
  39 ScMarkArray::ScMarkArray( const ScMarkArray & rOther )
  40     : mrSheetLimits(rOther.mrSheetLimits)
  41 {
  42     operator=(rOther);
  43 }
  44
  45 void ScMarkArray::Reset( bool bMarked, SCSIZE nNeeded )
  46 {
  47     // always create pData here
  48     // (or have separate method to ensure pData)
  49
  50     assert(nNeeded);
  51     mvData.resize(1);
  52     mvData.reserve(nNeeded);
  53     mvData[0].nRow = mrSheetLimits.mnMaxRow;
  54     mvData[0].bMarked = bMarked;
  55 }
  56
  57 // Iterative implementation of Binary Search
  58 bool ScMarkArray::Search( SCROW nRow, SCSIZE& nIndex ) const
  59 {
  60     assert(mvData.size() > 0);
  61     SCSIZE    nHi         = mvData.size() - 1;
  62     SCSIZE    nLo         = 0;
  63
  64     while ( nLo <= nHi )
  65     {
  66         SCSIZE i = (nLo + nHi) / 2;
  67
  68         if (mvData[i].nRow < nRow)
  69         {
  70             // If [nRow] greater, ignore left half
  71             nLo = i + 1;
  72         }
  73         else if ((i > 0) && (mvData[i - 1].nRow >= nRow))
  74         {
  75             // If [nRow] is smaller, ignore right half
  76             nHi = i - 1;
  77         }
  78         else
  79         {
  80             // found
  81             nIndex=i;
  82             return true;
  83         }
  84     }
  85
  86     // not found
  87     nIndex=0;
  88     return false;
  89 }
  90
  91 bool ScMarkArray::GetMark( SCROW nRow ) const
  92 {
  93     SCSIZE i;
  94     if (Search( nRow, i ))
  95         return mvData[i].bMarked;
  96     else
  97         return false;
  98
  99 }
 100
 101 void ScMarkArray::SetMarkArea( SCROW nStartRow, SCROW nEndRow, bool bMarked )
 102 {
 103     if (!(mrSheetLimits.ValidRow(nStartRow) && mrSheetLimits.ValidRow(nEndRow)))
 104         return;
 105
 106     if ((nStartRow == 0) && (nEndRow == mrSheetLimits.mnMaxRow))
 107     {
 108         Reset(bMarked);
 109     }
 110     else
 111     {
 112         SCSIZE ni;          // number of entries in beginning
 113         SCSIZE nInsert;     // insert position (mnMaxRow+1 := no insert)
 114         bool bCombined = false;
 115         bool bSplit = false;
 116         if ( nStartRow > 0 )
 117         {
 118             // skip beginning
 119             SCSIZE nIndex;
 120             Search( nStartRow, nIndex );
 121             ni = nIndex;
 122
 123             nInsert = mrSheetLimits.GetMaxRowCount();
 124             if ( mvData[ni].bMarked != bMarked )
 125             {
 126                 if ( ni == 0 || (mvData[ni-1].nRow < nStartRow - 1) )
 127                 {   // may be a split or a simple insert or just a shrink,
 128                     // row adjustment is done further down
 129                     if ( mvData[ni].nRow > nEndRow )
 130                         bSplit = true;
 131                     ni++;
 132                     nInsert = ni;
 133                 }
 134                 else if ( ni > 0 && mvData[ni-1].nRow == nStartRow - 1 )
 135                     nInsert = ni;
 136             }
 137             if ( ni > 0 && mvData[ni-1].bMarked == bMarked )
 138             {   // combine
 139                 mvData[ni-1].nRow = nEndRow;
 140                 nInsert = mrSheetLimits.GetMaxRowCount();
 141                 bCombined = true;
 142             }
 143         }
 144         else
 145         {
 146             nInsert = 0;
 147             ni = 0;
 148         }
 149
 150         SCSIZE nj = ni;     // stop position of range to replace
 151         while ( nj < mvData.size() && mvData[nj].nRow <= nEndRow )
 152             nj++;
 153         if ( !bSplit )
 154         {
 155             if ( nj < mvData.size() && mvData[nj].bMarked == bMarked )
 156             {   // combine
 157                 if ( ni > 0 )
 158                 {
 159                     if ( mvData[ni-1].bMarked == bMarked )
 160                     {   // adjacent entries
 161                         mvData[ni-1].nRow = mvData[nj].nRow;
 162                         nj++;
 163                     }
 164                     else if ( ni == nInsert )
 165                         mvData[ni-1].nRow = nStartRow - 1;   // shrink
 166                 }
 167                 nInsert = mrSheetLimits.GetMaxRowCount();
 168                 bCombined = true;
 169             }
 170             else if ( ni > 0 && ni == nInsert )
 171                 mvData[ni-1].nRow = nStartRow - 1;   // shrink
 172         }
 173         if ( ni < nj )
 174         {   // remove middle entries
 175             if ( !bCombined )
 176             {   // replace one entry
 177                 mvData[ni].nRow = nEndRow;
 178                 mvData[ni].bMarked = bMarked;
 179                 ni++;
 180                 nInsert = mrSheetLimits.GetMaxRowCount();
 181             }
 182             if ( ni < nj )
 183             {   // remove entries
 184                 mvData.erase(mvData.begin() + ni, mvData.begin() + nj);
 185             }
 186         }
 187
 188         if ( nInsert < sal::static_int_cast<SCSIZE>(mrSheetLimits.GetMaxRowCount()) )
 189         {   // insert or append new entry
 190             if ( nInsert <= mvData.size() )
 191             {
 192                 if ( !bSplit )
 193                     mvData.insert(mvData.begin() + nInsert, { nEndRow, bMarked });
 194                 else
 195                 {
 196                     mvData.insert(mvData.begin() + nInsert, 2, { nEndRow, bMarked });
 197                     mvData[nInsert+1] = mvData[nInsert-1];
 198                 }
 199             }
 200             else
 201                 mvData.push_back(ScMarkEntry{ nEndRow, bMarked });
 202             if ( nInsert )
 203                 mvData[nInsert-1].nRow = nStartRow - 1;
 204         }
 205     }
 206 }
 207
 208 /**
 209   optimised init-from-range-list. Specifically this is optimised for cases
 210   where we have very large data columns with lots and lots of ranges.
 211 */
 212 void ScMarkArray::Set( std::vector<ScMarkEntry> && rMarkEntries )
 213 {
 214     mvData = std::move(rMarkEntries);
 215 }
 216
 217 bool ScMarkArray::IsAllMarked( SCROW nStartRow, SCROW nEndRow ) const
 218 {
 219     SCSIZE nStartIndex;
 220     SCSIZE nEndIndex;
 221
 222     if (Search( nStartRow, nStartIndex ))
 223         if (mvData[nStartIndex].bMarked)
 224             if (Search( nEndRow, nEndIndex ))
 225                 if (nEndIndex==nStartIndex)
 226                     return true;
 227
 228     return false;
 229 }
 230
 231 bool ScMarkArray::HasOneMark( SCROW& rStartRow, SCROW& rEndRow ) const
 232 {
 233     bool bRet = false;
 234     if ( mvData.size() == 1 )
 235     {
 236         if ( mvData[0].bMarked )
 237         {
 238             rStartRow = 0;
 239             rEndRow = mrSheetLimits.mnMaxRow;
 240             bRet = true;
 241         }
 242     }
 243     else if ( mvData.size() == 2 )
 244     {
 245         if ( mvData[0].bMarked )
 246         {
 247             rStartRow = 0;
 248             rEndRow = mvData[0].nRow;
 249         }
 250         else
 251         {
 252             rStartRow = mvData[0].nRow + 1;
 253             rEndRow = mrSheetLimits.mnMaxRow;
 254         }
 255         bRet = true;
 256     }
 257     else if ( mvData.size() == 3 )
 258     {
 259         if ( mvData[1].bMarked )
 260         {
 261             rStartRow = mvData[0].nRow + 1;
 262             rEndRow = mvData[1].nRow;
 263             bRet = true;
 264         }
 265     }
 266     return bRet;
 267 }
 268
 269 bool ScMarkArray::operator==( const ScMarkArray& rOther ) const
 270 {
 271     return mvData == rOther.mvData;
 272 }
 273
 274 ScMarkArray& ScMarkArray::operator=( const ScMarkArray& rOther )
 275 {
 276     mvData = rOther.mvData;
 277     return *this;
 278 }
 279
 280 ScMarkArray& ScMarkArray::operator=(ScMarkArray&& rOther) noexcept
 281 {
 282     mvData = std::move(rOther.mvData);
 283     return *this;
 284 }
 285
 286 SCROW ScMarkArray::GetNextMarked( SCROW nRow, bool bUp ) const
 287 {
 288     SCROW nRet = nRow;
 289     if (mrSheetLimits.ValidRow(nRow))
 290     {
 291         SCSIZE nIndex;
 292         Search(nRow, nIndex);
 293         if (!mvData[nIndex].bMarked)
 294         {
 295             if (bUp)
 296             {
 297                 if (nIndex>0)
 298                     nRet = mvData[nIndex-1].nRow;
 299                 else
 300                     nRet = -1;
 301             }
 302             else
 303                 nRet = mvData[nIndex].nRow + 1;
 304         }
 305     }
 306     return nRet;
 307 }
 308
 309 SCROW ScMarkArray::GetMarkEnd( SCROW nRow, bool bUp ) const
 310 {
 311     SCROW nRet;
 312     SCSIZE nIndex;
 313     Search(nRow, nIndex);
 314     assert( mvData[nIndex].bMarked && "GetMarkEnd without bMarked" );
 315     if (bUp)
 316     {
 317         if (nIndex>0)
 318             nRet = mvData[nIndex-1].nRow + 1;
 319         else
 320             nRet = 0;
 321     }
 322     else
 323         nRet = mvData[nIndex].nRow;
 324
 325     return nRet;
 326 }
 327
 328 void ScMarkArray::Shift(SCROW nStartRow, tools::Long nOffset)
 329 {
 330     if (nOffset == 0 || nStartRow > mrSheetLimits.mnMaxRow)
 331         return;
 332
 333     for (size_t i=0; i < mvData.size(); ++i)
 334     {
 335         auto& rEntry = mvData[i];
 336
 337         if (rEntry.nRow < nStartRow)
 338             continue;
 339         rEntry.nRow += nOffset;
 340         if (rEntry.nRow < 0)
 341         {
 342             rEntry.nRow = 0;
 343         }
 344         else if (rEntry.nRow > mrSheetLimits.mnMaxRow)
 345         {
 346             rEntry.nRow = mrSheetLimits.mnMaxRow;
 347         }
 348     }
 349 }
 350
 351 //  -------------- Iterator ----------------------------------------------
 352
 353 ScMarkArrayIter::ScMarkArrayIter( const ScMarkArray* pNewArray ) :
 354     pArray( pNewArray ),
 355     nPos( 0 )
 356 {
 357 }
 358
 359 void ScMarkArrayIter::reset( const ScMarkArray* pNewArray )
 360 {
 361     pArray = pNewArray;
 362     nPos = 0;
 363 }
 364
 365 bool ScMarkArrayIter::Next( SCROW& rTop, SCROW& rBottom )
 366 {
 367     if (!pArray)
 368         return false;
 369     if ( nPos >= pArray->mvData.size() )
 370         return false;
 371     while (!pArray->mvData[nPos].bMarked)
 372     {
 373         ++nPos;
 374         if ( nPos >= pArray->mvData.size() )
 375             return false;
 376     }
 377     rBottom = pArray->mvData[nPos].nRow;
 378     if (nPos==0)
 379         rTop = 0;
 380     else
 381         rTop = pArray->mvData[nPos-1].nRow + 1;
 382     ++nPos;
 383     return true;
 384 }
 385
 386 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */