sc/source/core/tool/rangelst.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 <stdlib.h>
  21 #include <unotools/collatorwrapper.hxx>
  22 #include <sal/log.hxx>
  23 #include <o3tl/string_view.hxx>
  24
  25 #include <rangelst.hxx>
  26 #include <document.hxx>
  27 #include <refupdat.hxx>
  28 #include <compiler.hxx>
  29 #include <algorithm>
  30 #include <memory>
  31
  32 using ::std::vector;
  33 using ::std::find_if;
  34 using ::std::for_each;
  35 using ::formula::FormulaGrammar;
  36
  37 namespace {
  38
  39 template<typename T>
  40 class FindEnclosingRange
  41 {
  42 public:
  43     explicit FindEnclosingRange(const T& rTest) : mrTest(rTest) {}
  44     bool operator() (const ScRange & rRange) const
  45     {
  46         return rRange.Contains(mrTest);
  47     }
  48 private:
  49     const T& mrTest;
  50 };
  51
  52 template<typename T>
  53 class FindIntersectingRange
  54 {
  55 public:
  56     explicit FindIntersectingRange(const T& rTest) : mrTest(rTest) {}
  57     bool operator() (const ScRange & rRange) const
  58     {
  59         return rRange.Intersects(mrTest);
  60     }
  61 private:
  62     const T& mrTest;
  63 };
  64
  65 class CountCells
  66 {
  67 public:
  68     CountCells() : mnCellCount(0) {}
  69
  70     void operator() (const ScRange & r)
  71     {
  72         mnCellCount +=
  73               sal_uInt64(r.aEnd.Col() - r.aStart.Col() + 1)
  74             * sal_uInt64(r.aEnd.Row() - r.aStart.Row() + 1)
  75             * sal_uInt64(r.aEnd.Tab() - r.aStart.Tab() + 1);
  76     }
  77
  78     sal_uInt64 getCellCount() const { return mnCellCount; }
  79
  80 private:
  81     sal_uInt64 mnCellCount;
  82 };
  83
  84
  85 }
  86
  87 //  ScRangeList
  88 ScRangeList::~ScRangeList()
  89 {
  90 }
  91
  92 ScRefFlags ScRangeList::Parse( std::u16string_view rStr, const ScDocument& rDoc,
  93                            formula::FormulaGrammar::AddressConvention eConv,
  94                            SCTAB nDefaultTab, sal_Unicode cDelimiter )
  95 {
  96     if ( !rStr.empty() )
  97     {
  98         if (!cDelimiter)
  99             cDelimiter = ScCompiler::GetNativeSymbolChar(ocSep);
 100
 101         ScRefFlags nResult = ~ScRefFlags::ZERO;    // set all bits
 102         ScRange aRange;
 103         const SCTAB nTab = nDefaultTab;
 104
 105         sal_Int32 nPos = 0;
 106         do
 107         {
 108             const OUString aOne( o3tl::getToken(rStr, 0, cDelimiter, nPos ) );
 109             aRange.aStart.SetTab( nTab );   // default tab if not specified
 110             ScRefFlags nRes = aRange.ParseAny( aOne, rDoc, eConv );
 111             ScRefFlags nEndRangeBits = ScRefFlags::COL2_VALID | ScRefFlags::ROW2_VALID | ScRefFlags::TAB2_VALID;
 112             ScRefFlags nTmp1 = nRes & ScRefFlags::BITS;
 113             ScRefFlags nTmp2 = nRes & nEndRangeBits;
 114             // If we have a valid single range with
 115             // any of the address bits we are interested in
 116             // set - set the equiv end range bits
 117             if ( (nRes & ScRefFlags::VALID ) && (nTmp1 != ScRefFlags::ZERO) && ( nTmp2 != nEndRangeBits ) )
 118                 applyStartToEndFlags(nRes, nTmp1);
 119
 120             if ( nRes & ScRefFlags::VALID )
 121                 push_back( aRange );
 122             nResult &= nRes;        // all common bits are preserved
 123         }
 124         while (nPos >= 0);
 125
 126         return nResult;             // ScRefFlags::VALID set when all are OK
 127     }
 128     else
 129         return ScRefFlags::ZERO;
 130 }
 131
 132 void ScRangeList::Format( OUString& rStr, ScRefFlags nFlags, const ScDocument& rDoc,
 133                           formula::FormulaGrammar::AddressConvention eConv,
 134                           sal_Unicode cDelimiter, bool bFullAddressNotation ) const
 135 {
 136     if (!cDelimiter)
 137         cDelimiter = ScCompiler::GetNativeSymbolChar(ocSep);
 138
 139     OUStringBuffer aBuf;
 140     bool bFirst = true;
 141     for( auto const & r : maRanges)
 142     {
 143         if (bFirst)
 144             bFirst = false;
 145         else
 146             aBuf.append(OUStringChar(cDelimiter));
 147         aBuf.append(r.Format(rDoc, nFlags, eConv, bFullAddressNotation));
 148     }
 149     rStr = aBuf.makeStringAndClear();
 150 }
 151
 152 void ScRangeList::Join( const ScRange& rNewRange, bool bIsInList )
 153 {
 154     if ( maRanges.empty() )
 155     {
 156         push_back( rNewRange );
 157         return ;
 158     }
 159
 160     // One common usage is to join ranges that actually are top to bottom
 161     // appends but the caller doesn't exactly know about it, e.g. when invoked
 162     // by ScMarkData::FillRangeListWithMarks(), check for this special case
 163     // first and speed up things by not looping over all ranges for each range
 164     // to be joined. We don't remember the exact encompassing range that would
 165     // have to be updated on refupdates and insertions and deletions, instead
 166     // remember just the maximum row used, even independently of the sheet.
 167     // This satisfies most use cases.
 168
 169     if (!bIsInList)
 170     {
 171         const SCROW nRow1 = rNewRange.aStart.Row();
 172         if (nRow1 > mnMaxRowUsed + 1)
 173         {
 174             push_back( rNewRange );
 175             return;
 176         }
 177         else if (nRow1 == mnMaxRowUsed + 1)
 178         {
 179             // Check if we can simply enlarge the last range.
 180             ScRange & rLast = maRanges.back();
 181             if (rLast.aEnd.Row() + 1 == nRow1 &&
 182                     rLast.aStart.Col() == rNewRange.aStart.Col() && rLast.aEnd.Col() == rNewRange.aEnd.Col() &&
 183                     rLast.aStart.Tab() == rNewRange.aStart.Tab() && rLast.aEnd.Tab() == rNewRange.aEnd.Tab())
 184             {
 185                 const SCROW nRow2 = rNewRange.aEnd.Row();
 186                 rLast.aEnd.SetRow( nRow2 );
 187                 mnMaxRowUsed = nRow2;
 188                 return;
 189             }
 190         }
 191     }
 192
 193     bool bJoinedInput = false;
 194     const ScRange* pOver = &rNewRange;
 195
 196 Label_Range_Join:
 197
 198     assert(pOver);
 199     const SCCOL nCol1 = pOver->aStart.Col();
 200     const SCROW nRow1 = pOver->aStart.Row();
 201     const SCCOL nTab1 = pOver->aStart.Tab();
 202     const SCCOL nCol2 = pOver->aEnd.Col();
 203     const SCROW nRow2 = pOver->aEnd.Row();
 204     const SCCOL nTab2 = pOver->aEnd.Tab();
 205
 206     size_t nOverPos = std::numeric_limits<size_t>::max();
 207     for (size_t i = 0; i < maRanges.size(); ++i)
 208     {
 209         ScRange & rRange = maRanges[i];
 210         if ( &rRange == pOver )
 211         {
 212             nOverPos = i;
 213             continue;           // the same one, continue with the next
 214         }
 215         bool bJoined = false;
 216         if ( rRange.Contains( *pOver ) )
 217         {   // range pOver included in or identical to range p
 218             // XXX if we never used Append() before Join() we could remove
 219             // pOver and end processing, but it is not guaranteed and there can
 220             // be duplicates.
 221             if ( bIsInList )
 222                 bJoined = true;     // do away with range pOver
 223             else
 224             {   // that was all then
 225                 bJoinedInput = true;    // don't append
 226                 break;  // for
 227             }
 228         }
 229         else if ( pOver->Contains( rRange ) )
 230         {   // range rRange included in range pOver, make pOver the new range
 231             rRange = *pOver;
 232             bJoined = true;
 233         }
 234         if ( !bJoined && rRange.aStart.Tab() == nTab1 && rRange.aEnd.Tab() == nTab2 )
 235         {   // 2D
 236             if ( rRange.aStart.Col() == nCol1 && rRange.aEnd.Col() == nCol2 )
 237             {
 238                 if ( rRange.aStart.Row() <= nRow2+1 &&
 239                      rRange.aStart.Row() >= nRow1 )
 240                 {   // top
 241                     rRange.aStart.SetRow( nRow1 );
 242                     bJoined = true;
 243                 }
 244                 else if ( rRange.aEnd.Row() >= nRow1-1 &&
 245                           rRange.aEnd.Row() <= nRow2 )
 246                 {   // bottom
 247                     rRange.aEnd.SetRow( nRow2 );
 248                     bJoined = true;
 249                 }
 250             }
 251             else if ( rRange.aStart.Row() == nRow1 && rRange.aEnd.Row() == nRow2 )
 252             {
 253                 if ( rRange.aStart.Col() <= nCol2+1 &&
 254                      rRange.aStart.Col() >= nCol1 )
 255                 {   // left
 256                     rRange.aStart.SetCol( nCol1 );
 257                     bJoined = true;
 258                 }
 259                 else if ( rRange.aEnd.Col() >= nCol1-1 &&
 260                           rRange.aEnd.Col() <= nCol2 )
 261                 {   // right
 262                     rRange.aEnd.SetCol( nCol2 );
 263                     bJoined = true;
 264                 }
 265             }
 266         }
 267         if ( bJoined )
 268         {
 269             if ( bIsInList )
 270             {   // delete range pOver within the list
 271                 if (nOverPos != std::numeric_limits<size_t>::max())
 272                 {
 273                     Remove(nOverPos);
 274                     if (nOverPos < i)
 275                         --i;
 276                 }
 277                 else
 278                 {
 279                     for (size_t nOver = 0, nRanges = maRanges.size(); nOver < nRanges; ++nOver)
 280                     {
 281                         if (&maRanges[nOver] == pOver)
 282                         {
 283                             Remove(nOver);
 284                             break;
 285                         }
 286                     }
 287                 }
 288             }
 289             bJoinedInput = true;
 290             pOver = &maRanges[i];
 291             bIsInList = true;
 292             goto Label_Range_Join;
 293         }
 294     }
 295     if (  !bIsInList && !bJoinedInput )
 296         push_back( rNewRange );
 297 }
 298
 299 void ScRangeList::AddAndPartialCombine( const ScRange& rNewRange )
 300 {
 301     if ( maRanges.empty() )
 302     {
 303         push_back( rNewRange );
 304         return ;
 305     }
 306
 307     // One common usage is to join ranges that actually are top to bottom
 308     // appends but the caller doesn't exactly know about it, e.g. when invoked
 309     // by ScMarkData::FillRangeListWithMarks(), check for this special case
 310     // first and speed up things by not looping over all ranges for each range
 311     // to be joined. We don't remember the exact encompassing range that would
 312     // have to be updated on refupdates and insertions and deletions, instead
 313     // remember just the maximum row used, even independently of the sheet.
 314     // This satisfies most use cases.
 315
 316     const SCROW nRow1 = rNewRange.aStart.Row();
 317     if (nRow1 > mnMaxRowUsed + 1)
 318     {
 319         push_back( rNewRange );
 320         return;
 321     }
 322
 323     // scan backwards 2 rows to see if we can merge with anything
 324     auto it = maRanges.rbegin();
 325     while (it != maRanges.rend() && it->aStart.Row() >= (rNewRange.aStart.Row() - 2))
 326     {
 327         // Check if we can simply enlarge this range.
 328         ScRange & rLast = *it;
 329         if (rLast.aEnd.Row() + 1 == nRow1 &&
 330                 rLast.aStart.Col() == rNewRange.aStart.Col() && rLast.aEnd.Col() == rNewRange.aEnd.Col() &&
 331                 rLast.aStart.Tab() == rNewRange.aStart.Tab() && rLast.aEnd.Tab() == rNewRange.aEnd.Tab())
 332         {
 333             const SCROW nRow2 = rNewRange.aEnd.Row();
 334             rLast.aEnd.SetRow( nRow2 );
 335             mnMaxRowUsed = std::max(mnMaxRowUsed, nRow2);
 336             return;
 337         }
 338         ++it;
 339     }
 340
 341     push_back( rNewRange );
 342 }
 343
 344 bool ScRangeList::operator==( const ScRangeList& r ) const
 345 {
 346     if ( this == &r )
 347         return true;
 348
 349     return maRanges == r.maRanges;
 350 }
 351
 352 bool ScRangeList::operator!=( const ScRangeList& r ) const
 353 {
 354     return !operator==( r );
 355 }
 356
 357 bool ScRangeList::UpdateReference(
 358     UpdateRefMode eUpdateRefMode,
 359     const ScDocument* pDoc,
 360     const ScRange& rWhere,
 361     SCCOL nDx,
 362     SCROW nDy,
 363     SCTAB nDz
 364 )
 365 {
 366     if (maRanges.empty())
 367         // No ranges to update.  Bail out.
 368         return false;
 369
 370     bool bChanged = false;
 371     SCCOL nCol1;
 372     SCROW nRow1;
 373     SCTAB nTab1;
 374     SCCOL nCol2;
 375     SCROW nRow2;
 376     SCTAB nTab2;
 377     rWhere.GetVars( nCol1, nRow1, nTab1, nCol2, nRow2, nTab2 );
 378
 379     if(eUpdateRefMode == URM_INSDEL)
 380     {
 381         // right now this only works for nTab1 == nTab2
 382         if(nTab1 == nTab2)
 383         {
 384             if(nDx < 0)
 385             {
 386                 bChanged = DeleteArea(nCol1+nDx, nRow1, nTab1, nCol1-1, nRow2, nTab2);
 387             }
 388             if(nDy < 0)
 389             {
 390                 bChanged = DeleteArea(nCol1, nRow1+nDy, nTab1, nCol2, nRow1-1, nTab2);
 391             }
 392             SAL_WARN_IF(nDx < 0 && nDy < 0, "sc", "nDx and nDy are negative, check why");
 393         }
 394     }
 395
 396     if(maRanges.empty())
 397         return true;
 398
 399     for (auto& rR : maRanges)
 400     {
 401         SCCOL theCol1;
 402         SCROW theRow1;
 403         SCTAB theTab1;
 404         SCCOL theCol2;
 405         SCROW theRow2;
 406         SCTAB theTab2;
 407         rR.GetVars( theCol1, theRow1, theTab1, theCol2, theRow2, theTab2 );
 408         if ( ScRefUpdate::Update( pDoc, eUpdateRefMode,
 409                 nCol1, nRow1, nTab1, nCol2, nRow2, nTab2,
 410                 nDx, nDy, nDz,
 411                 theCol1, theRow1, theTab1, theCol2, theRow2, theTab2 )
 412                 != UR_NOTHING )
 413         {
 414             bChanged = true;
 415             rR.aStart.Set( theCol1, theRow1, theTab1 );
 416             rR.aEnd.Set( theCol2, theRow2, theTab2 );
 417             if (mnMaxRowUsed < theRow2)
 418                 mnMaxRowUsed = theRow2;
 419         }
 420     }
 421
 422     if(eUpdateRefMode == URM_INSDEL)
 423     {
 424         if( nDx < 0 || nDy < 0 )
 425         {
 426             size_t n = maRanges.size();
 427             for(size_t i = n-1; i > 0;)
 428             {
 429                 Join(maRanges[i], true);
 430                 // Join() may merge and remove even more than one item, protect against it.
 431                 if(i >= maRanges.size())
 432                     i = maRanges.size()-1;
 433                 else
 434                     --i;
 435             }
 436         }
 437     }
 438
 439     return bChanged;
 440 }
 441
 442 void ScRangeList::InsertRow( SCTAB nTab, SCCOL nColStart, SCCOL nColEnd, SCROW nRowPos, SCSIZE nSize )
 443 {
 444     std::vector<ScRange> aNewRanges;
 445     for(const auto & rRange : maRanges)
 446     {
 447         if(rRange.aStart.Tab() <= nTab && rRange.aEnd.Tab() >= nTab)
 448         {
 449             if(rRange.aEnd.Row() == nRowPos - 1 && (nColStart <= rRange.aEnd.Col() || nColEnd >= rRange.aStart.Col()))
 450             {
 451                 SCCOL nNewRangeStartCol = std::max<SCCOL>(nColStart, rRange.aStart.Col());
 452                 SCCOL nNewRangeEndCol = std::min<SCCOL>(nColEnd, rRange.aEnd.Col());
 453                 SCROW nNewRangeStartRow = rRange.aEnd.Row() + 1;
 454                 SCROW nNewRangeEndRow = nRowPos + nSize - 1;
 455                 aNewRanges.emplace_back(nNewRangeStartCol, nNewRangeStartRow, nTab, nNewRangeEndCol,
 456                             nNewRangeEndRow, nTab);
 457                 if (mnMaxRowUsed < nNewRangeEndRow)
 458                     mnMaxRowUsed = nNewRangeEndRow;
 459             }
 460         }
 461     }
 462
 463     for(const auto & rRange : aNewRanges)
 464     {
 465         if(!rRange.IsValid())
 466             continue;
 467
 468         Join(rRange);
 469     }
 470 }
 471
 472 void ScRangeList::InsertCol( SCTAB nTab, SCROW nRowStart, SCROW nRowEnd, SCCOL nColPos, SCSIZE nSize )
 473 {
 474     std::vector<ScRange> aNewRanges;
 475     for(const auto & rRange : maRanges)
 476     {
 477         if(rRange.aStart.Tab() <= nTab && rRange.aEnd.Tab() >= nTab)
 478         {
 479             if(rRange.aEnd.Col() == nColPos - 1 && (nRowStart <= rRange.aEnd.Row() || nRowEnd >= rRange.aStart.Row()))
 480             {
 481                 SCROW nNewRangeStartRow = std::max<SCROW>(nRowStart, rRange.aStart.Row());
 482                 SCROW nNewRangeEndRow = std::min<SCROW>(nRowEnd, rRange.aEnd.Row());
 483                 SCCOL nNewRangeStartCol = rRange.aEnd.Col() + 1;
 484                 SCCOL nNewRangeEndCol = nColPos + nSize - 1;
 485                 aNewRanges.emplace_back(nNewRangeStartCol, nNewRangeStartRow, nTab, nNewRangeEndCol,
 486                             nNewRangeEndRow, nTab);
 487             }
 488         }
 489     }
 490
 491     for(const auto & rRange : aNewRanges)
 492     {
 493         if(!rRange.IsValid())
 494             continue;
 495
 496         Join(rRange);
 497     }
 498 }
 499
 500 void ScRangeList::InsertCol( SCTAB nTab, SCCOL nCol )
 501 {
 502     std::vector<ScRange> aNewRanges;
 503     for(const auto & rRange : maRanges)
 504     {
 505         if(rRange.aStart.Tab() <= nTab && rRange.aEnd.Tab() >= nTab)
 506         {
 507             if(rRange.aEnd.Col() == nCol - 1)
 508             {
 509                 SCCOL nNewRangeStartCol = rRange.aEnd.Col() + 1;
 510                 SCCOL nNewRangeEndCol = nCol;
 511                 aNewRanges.emplace_back(nNewRangeStartCol, rRange.aStart.Row(), nTab, nNewRangeEndCol,
 512                             rRange.aEnd.Row(), nTab);
 513             }
 514         }
 515     }
 516
 517     for(const auto & rRange : aNewRanges)
 518     {
 519         if(!rRange.IsValid())
 520             continue;
 521
 522         Join(rRange);
 523     }
 524 }
 525
 526 namespace {
 527
 528 /**
 529  * Check if the deleting range cuts the test range exactly into a single
 530  * piece.
 531  *
 532  * X = column ; Y = row
 533  * +------+    +------+
 534  * |xxxxxx|    |      |
 535  * +------+ or +------+
 536  * |      |    |xxxxxx|
 537  * +------+    +------+
 538  *
 539  * X = row; Y = column
 540  * +--+--+    +--+--+
 541  * |xx|  |    |  |xx|
 542  * |xx|  | or |  |xx|
 543  * |xx|  |    |  |xx|
 544  * +--+--+    +--+--+
 545  * where xxx is the deleted region.
 546  */
 547 template<typename X, typename Y>
 548 bool checkForOneRange(
 549    X nDeleteX1, X nDeleteX2, Y nDeleteY1, Y nDeleteY2, X nX1, X nX2, Y nY1, Y nY2)
 550 {
 551     return nDeleteX1 <= nX1 && nX2 <= nDeleteX2 && (nDeleteY1 <= nY1 || nY2 <= nDeleteY2);
 552 }
 553
 554 bool handleOneRange( const ScRange& rDeleteRange, ScRange& r )
 555 {
 556     const ScAddress& rDelStart = rDeleteRange.aStart;
 557     const ScAddress& rDelEnd = rDeleteRange.aEnd;
 558     ScAddress aPStart = r.aStart;
 559     ScAddress aPEnd = r.aEnd;
 560     SCCOL nDeleteCol1 = rDelStart.Col();
 561     SCCOL nDeleteCol2 = rDelEnd.Col();
 562     SCROW nDeleteRow1 = rDelStart.Row();
 563     SCROW nDeleteRow2 = rDelEnd.Row();
 564     SCCOL nCol1 = aPStart.Col();
 565     SCCOL nCol2 = aPEnd.Col();
 566     SCROW nRow1 = aPStart.Row();
 567     SCROW nRow2 = aPEnd.Row();
 568
 569     if (checkForOneRange(nDeleteCol1, nDeleteCol2, nDeleteRow1, nDeleteRow2, nCol1, nCol2, nRow1, nRow2))
 570     {
 571         // Deleting range fully overlaps the column range.  Adjust the row span.
 572         if (nDeleteRow1 <= nRow1)
 573         {
 574             // +------+
 575             // |xxxxxx|
 576             // +------+
 577             // |      |
 578             // +------+ (xxx) = deleted region
 579
 580             r.aStart.SetRow(nDeleteRow1+1);
 581             return true;
 582         }
 583         else if (nRow2 <= nDeleteRow2)
 584         {
 585             // +------+
 586             // |      |
 587             // +------+
 588             // |xxxxxx|
 589             // +------+ (xxx) = deleted region
 590
 591             r.aEnd.SetRow(nDeleteRow1-1);
 592             return true;
 593         }
 594     }
 595     else if (checkForOneRange(nDeleteRow1, nDeleteRow2, nDeleteCol1, nDeleteCol2, nRow1, nRow2, nCol1, nCol2))
 596     {
 597         // Deleting range fully overlaps the row range.  Adjust the column span.
 598         if (nDeleteCol1 <= nCol1)
 599         {
 600             // +--+--+
 601             // |xx|  |
 602             // |xx|  |
 603             // |xx|  |
 604             // +--+--+ (xxx) = deleted region
 605
 606             r.aStart.SetCol(nDeleteCol2+1);
 607             return true;
 608         }
 609         else if (nCol2 <= nDeleteCol2)
 610         {
 611             // +--+--+
 612             // |  |xx|
 613             // |  |xx|
 614             // |  |xx|
 615             // +--+--+ (xxx) = deleted region
 616
 617             r.aEnd.SetCol(nDeleteCol1-1);
 618             return true;
 619         }
 620     }
 621     return false;
 622 }
 623
 624 bool handleTwoRanges( const ScRange& rDeleteRange, ScRange& r, std::vector<ScRange>& rNewRanges )
 625 {
 626     const ScAddress& rDelStart = rDeleteRange.aStart;
 627     const ScAddress& rDelEnd = rDeleteRange.aEnd;
 628     ScAddress aPStart = r.aStart;
 629     ScAddress aPEnd = r.aEnd;
 630     SCCOL nDeleteCol1 = rDelStart.Col();
 631     SCCOL nDeleteCol2 = rDelEnd.Col();
 632     SCROW nDeleteRow1 = rDelStart.Row();
 633     SCROW nDeleteRow2 = rDelEnd.Row();
 634     SCCOL nCol1 = aPStart.Col();
 635     SCCOL nCol2 = aPEnd.Col();
 636     SCROW nRow1 = aPStart.Row();
 637     SCROW nRow2 = aPEnd.Row();
 638     SCTAB nTab = aPStart.Tab();
 639
 640     if (nCol1 < nDeleteCol1 && nDeleteCol1 <= nCol2 && nCol2 <= nDeleteCol2)
 641     {
 642         // column deleted :     |-------|
 643         // column original: |-------|
 644         if (nRow1 < nDeleteRow1 && nDeleteRow1 <= nRow2 && nRow2 <= nDeleteRow2)
 645         {
 646             // row deleted:     |------|
 647             // row original: |------|
 648             //
 649             // +-------+
 650             // |   1   |
 651             // +---+---+---+
 652             // | 2 |xxxxxxx|
 653             // +---+xxxxxxx|
 654             //     |xxxxxxx|
 655             //     +-------+ (xxx) deleted region
 656
 657             ScRange aNewRange( nCol1, nDeleteRow1, nTab, nDeleteCol1-1, nRow2, nTab ); // 2
 658             rNewRanges.push_back(aNewRange);
 659
 660             r.aEnd.SetRow(nDeleteRow1-1); // 1
 661             return true;
 662         }
 663         else if (nRow1 <= nDeleteRow2 && nDeleteRow2 < nRow2 && nDeleteRow1 <= nRow1)
 664         {
 665             // row deleted:  |------|
 666             // row original:    |------|
 667             //
 668             //     +-------+
 669             //     |xxxxxxx|
 670             // +---+xxxxxxx|
 671             // | 1 |xxxxxxx|
 672             // +---+---+---+
 673             // |   2   |    (xxx) deleted region
 674             // +-------+
 675
 676             ScRange aNewRange( aPStart, ScAddress(nDeleteCol1-1, nRow2, nTab) ); // 1
 677             rNewRanges.push_back(aNewRange);
 678
 679             r.aStart.SetRow(nDeleteRow2+1); // 2
 680             return true;
 681         }
 682     }
 683     else if (nCol1 <= nDeleteCol2 && nDeleteCol2 < nCol2 && nDeleteCol1 <= nCol1)
 684     {
 685         // column deleted : |-------|
 686         // column original:     |-------|
 687         if (nRow1 < nDeleteRow1 && nDeleteRow1 <= nRow2 && nRow2 <= nDeleteRow2)
 688         {
 689             // row deleted:     |------|
 690             // row original: |------|
 691             //
 692             //     +-------+
 693             //     |   1   |
 694             // +-------+---+
 695             // |xxxxxxx| 2 |
 696             // |xxxxxxx+---+
 697             // |xxxxxxx|
 698             // +-------+
 699             //  (xxx) deleted region
 700
 701             ScRange aNewRange( ScAddress( nDeleteCol2+1, nDeleteRow1, nTab ), aPEnd ); // 2
 702             rNewRanges.push_back(aNewRange);
 703
 704             r.aEnd.SetRow(nDeleteRow1-1); // 1
 705             return true;
 706         }
 707         else if (nRow1 <= nDeleteRow2 && nDeleteRow2 < nRow2 && nDeleteRow1 <= nRow1)
 708         {
 709             // row deleted:  |-------|
 710             // row original:     |--------|
 711             //
 712             // +-------+
 713             // |xxxxxxx|
 714             // |xxxxxxx+---+
 715             // |xxxxxxx| 1 |
 716             // +-------+---+
 717             //     |   2   |
 718             //     +-------+ (xxx) deleted region
 719
 720             ScRange aNewRange(nDeleteCol2+1, nRow1, nTab, nCol2, nDeleteRow2, nTab); // 1
 721             rNewRanges.push_back(aNewRange);
 722
 723             r.aStart.SetRow(nDeleteRow2+1); // 2
 724             return true;
 725         }
 726     }
 727     else if (nRow1 < nDeleteRow1 && nDeleteRow2 < nRow2 && nDeleteCol1 <= nCol1 && nCol2 <= nDeleteCol2)
 728     {
 729         // +--------+
 730         // |   1    |
 731         // +--------+
 732         // |xxxxxxxx| (xxx) deleted region
 733         // +--------+
 734         // |   2    |
 735         // +--------+
 736
 737         ScRange aNewRange( aPStart, ScAddress(nCol2, nDeleteRow1-1, nTab) ); // 1
 738         rNewRanges.push_back(aNewRange);
 739
 740         r.aStart.SetRow(nDeleteRow2+1); // 2
 741         return true;
 742     }
 743     else if (nCol1 < nDeleteCol1 && nDeleteCol2 < nCol2 && nDeleteRow1 <= nRow1 && nRow2 <= nDeleteRow2)
 744     {
 745         // +---+-+---+
 746         // |   |x|   |
 747         // |   |x|   |
 748         // | 1 |x| 2 | (xxx) deleted region
 749         // |   |x|   |
 750         // |   |x|   |
 751         // +---+-+---+
 752
 753         ScRange aNewRange( aPStart, ScAddress(nDeleteCol1-1, nRow2, nTab) ); // 1
 754         rNewRanges.push_back(aNewRange);
 755
 756         r.aStart.SetCol(nDeleteCol2+1); // 2
 757         return true;
 758     }
 759
 760     return false;
 761 }
 762
 763 /**
 764  * Check if any of the following applies:
 765  *
 766  * X = column; Y = row
 767  * +----------+           +----------+
 768  * |          |           |          |
 769  * |  +-------+---+    +--+-------+  |
 770  * |  |xxxxxxxxxxx| or |xxxxxxxxxx|  |
 771  * |  +-------+---+    +--+-------+  |
 772  * |          |           |          |
 773  * +----------+           +----------+
 774  *
 775  * X = row; Y = column
 776  *     +--+
 777  *     |xx|
 778  * +---+xx+---+    +----------+
 779  * |   |xx|   |    |          |
 780  * |   |xx|   | or |   +--+   |
 781  * |   +--+   |    |   |xx|   |
 782  * |          |    |   |xx|   |
 783  * +----------+    +---+xx+---+
 784  *                     |xx|
 785  *                     +--+     (xxx) deleted region
 786  */
 787 template<typename X, typename Y>
 788 bool checkForThreeRanges(
 789    X nDeleteX1, X nDeleteX2, Y nDeleteY1, Y nDeleteY2, X nX1, X nX2, Y nY1, Y nY2)
 790 {
 791     if (nX1 <= nDeleteX1 && nX2 <= nDeleteX2 && nY1 < nDeleteY1 && nDeleteY2 < nY2)
 792         return true;
 793
 794     if (nDeleteX1 <= nX1 && nDeleteX2 <= nX2 && nY1 < nDeleteY1 && nDeleteY2 < nY2)
 795         return true;
 796
 797     return false;
 798 }
 799
 800 bool handleThreeRanges( const ScRange& rDeleteRange, ScRange& r, std::vector<ScRange>& rNewRanges )
 801 {
 802     const ScAddress& rDelStart = rDeleteRange.aStart;
 803     const ScAddress& rDelEnd = rDeleteRange.aEnd;
 804     ScAddress aPStart = r.aStart;
 805     ScAddress aPEnd = r.aEnd;
 806     SCCOL nDeleteCol1 = rDelStart.Col();
 807     SCCOL nDeleteCol2 = rDelEnd.Col();
 808     SCROW nDeleteRow1 = rDelStart.Row();
 809     SCROW nDeleteRow2 = rDelEnd.Row();
 810     SCCOL nCol1 = aPStart.Col();
 811     SCCOL nCol2 = aPEnd.Col();
 812     SCROW nRow1 = aPStart.Row();
 813     SCROW nRow2 = aPEnd.Row();
 814     SCTAB nTab = aPStart.Tab();
 815
 816     if (checkForThreeRanges(nDeleteCol1, nDeleteCol2, nDeleteRow1, nDeleteRow2, nCol1, nCol2, nRow1, nRow2))
 817     {
 818         if (nCol1 < nDeleteCol1)
 819         {
 820             // +---+------+
 821             // |   |  2   |
 822             // |   +------+---+
 823             // | 1 |xxxxxxxxxx|
 824             // |   +------+---+
 825             // |   |  3   |
 826             // +---+------+
 827
 828             ScRange aNewRange(nDeleteCol1, nRow1, nTab, nCol2, nDeleteRow1-1, nTab); // 2
 829             rNewRanges.push_back(aNewRange);
 830
 831             aNewRange = ScRange(ScAddress(nDeleteCol1, nDeleteRow2+1, nTab), aPEnd); // 3
 832             rNewRanges.push_back(aNewRange);
 833
 834             r.aEnd.SetCol(nDeleteCol1-1); // 1
 835         }
 836         else
 837         {
 838             //     +------+---+
 839             //     |  1   |   |
 840             // +---+------+   |
 841             // |xxxxxxxxxx| 2 |
 842             // +---+------+   |
 843             //     |  3   |   |
 844             //     +------+---+
 845
 846             ScRange aNewRange(aPStart, ScAddress(nDeleteCol2, nDeleteRow1-1, nTab)); // 1
 847             rNewRanges.push_back(aNewRange);
 848
 849             aNewRange = ScRange(nCol1, nDeleteRow2+1, nTab, nDeleteCol2, nRow2, nTab); // 3
 850             rNewRanges.push_back(aNewRange);
 851
 852             r.aStart.SetCol(nDeleteCol2+1); // 2
 853         }
 854         return true;
 855     }
 856     else if (checkForThreeRanges(nDeleteRow1, nDeleteRow2, nDeleteCol1, nDeleteCol2, nRow1, nRow2, nCol1, nCol2))
 857     {
 858         if (nRow1 < nDeleteRow1)
 859         {
 860             // +----------+
 861             // |    1     |
 862             // +---+--+---+
 863             // |   |xx|   |
 864             // | 2 |xx| 3 |
 865             // |   |xx|   |
 866             // +---+xx+---+
 867             //     |xx|
 868             //     +--+
 869
 870             ScRange aNewRange(nCol1, nDeleteRow1, nTab, nDeleteCol1-1, nRow2, nTab); // 2
 871             rNewRanges.push_back( aNewRange );
 872
 873             aNewRange = ScRange(ScAddress(nDeleteCol2+1, nDeleteRow1, nTab), aPEnd); // 3
 874             rNewRanges.push_back( aNewRange );
 875
 876             r.aEnd.SetRow(nDeleteRow1-1); // 1
 877         }
 878         else
 879         {
 880             //     +--+
 881             //     |xx|
 882             // +---+xx+---+
 883             // | 1 |xx| 2 |
 884             // |   |xx|   |
 885             // +---+--+---+
 886             // |    3     |
 887             // +----------+
 888
 889             ScRange aNewRange(aPStart, ScAddress(nDeleteCol1-1, nDeleteRow2, nTab)); // 1
 890             rNewRanges.push_back(aNewRange);
 891
 892             aNewRange = ScRange(nDeleteCol2+1, nRow1, nTab, nCol2, nDeleteRow2, nTab); // 2
 893             rNewRanges.push_back( aNewRange );
 894
 895             r.aStart.SetRow(nDeleteRow2+1); // 3
 896         }
 897         return true;
 898     }
 899
 900     return false;
 901 }
 902
 903 bool handleFourRanges( const ScRange& rDelRange, ScRange& r, std::vector<ScRange>& rNewRanges )
 904 {
 905     const ScAddress& rDelStart = rDelRange.aStart;
 906     const ScAddress& rDelEnd = rDelRange.aEnd;
 907     ScAddress aPStart = r.aStart;
 908     ScAddress aPEnd = r.aEnd;
 909     SCCOL nDeleteCol1 = rDelStart.Col();
 910     SCCOL nDeleteCol2 = rDelEnd.Col();
 911     SCROW nDeleteRow1 = rDelStart.Row();
 912     SCROW nDeleteRow2 = rDelEnd.Row();
 913     SCCOL nCol1 = aPStart.Col();
 914     SCCOL nCol2 = aPEnd.Col();
 915     SCROW nRow1 = aPStart.Row();
 916     SCROW nRow2 = aPEnd.Row();
 917     SCTAB nTab = aPStart.Tab();
 918
 919     if (nCol1 < nDeleteCol1 && nDeleteCol2 < nCol2 && nRow1 < nDeleteRow1 && nDeleteRow2 < nRow2)
 920     {
 921
 922         // +---------------+
 923         // |       1       |
 924         // +---+-------+---+
 925         // |   |xxxxxxx|   |
 926         // | 2 |xxxxxxx| 3 |
 927         // |   |xxxxxxx|   |
 928         // +---+-------+---+
 929         // |       4       |
 930         // +---------------+
 931
 932         ScRange aNewRange(ScAddress(nCol1, nDeleteRow2+1, nTab), aPEnd); // 4
 933         rNewRanges.push_back( aNewRange );
 934
 935         aNewRange = ScRange(nCol1, nDeleteRow1, nTab, nDeleteCol1-1, nDeleteRow2, nTab); // 2
 936         rNewRanges.push_back( aNewRange );
 937
 938         aNewRange = ScRange(nDeleteCol2+1, nDeleteRow1, nTab, nCol2, nDeleteRow2, nTab); // 3
 939         rNewRanges.push_back( aNewRange );
 940
 941         r.aEnd.SetRow(nDeleteRow1-1); // 1
 942
 943         return true;
 944     }
 945
 946     return false;
 947 }
 948
 949 }
 950
 951 bool ScRangeList::DeleteArea( SCCOL nCol1, SCROW nRow1, SCTAB nTab1,
 952                                 SCCOL nCol2, SCROW nRow2, SCTAB nTab2 )
 953 {
 954     bool bChanged = false;
 955     ScRange aRange( nCol1, nRow1, nTab1, nCol2, nRow2, nTab2 );
 956     for(size_t i = 0; i < maRanges.size();)
 957     {
 958         if(aRange.Contains(maRanges[i]))
 959         {
 960             Remove(i);
 961             bChanged = true;
 962         }
 963         else
 964             ++i;
 965     }
 966
 967     std::vector<ScRange> aNewRanges;
 968
 969     for(auto & rRange : maRanges)
 970     {
 971         // we have two basic cases here:
 972         // 1. Delete area and pRange intersect
 973         // 2. Delete area and pRange are not intersecting
 974         // checking for 2 and if true skip this range
 975         if(!rRange.Intersects(aRange))
 976             continue;
 977
 978         // We get between 1 and 4 ranges from the difference of the first with the second
 979
 980         // X either Col or Row and Y then the opposite
 981         // r = deleteRange, p = entry from ScRangeList
 982
 983         // getting exactly one range is the simple case
 984         // r.aStart.X() <= p.aStart.X() && r.aEnd.X() >= p.aEnd.X()
 985         // && ( r.aStart.Y() <= p.aStart.Y() || r.aEnd.Y() >= r.aEnd.Y() )
 986         if(handleOneRange( aRange, rRange ))
 987         {
 988             bChanged = true;
 989             continue;
 990         }
 991
 992         // getting two ranges
 993         // r.aStart.X()
 994         else if(handleTwoRanges( aRange, rRange, aNewRanges ))
 995         {
 996             bChanged = true;
 997             continue;
 998         }
 999
1000         // getting 3 ranges
1001         // r.aStart.X() > p.aStart.X() && r.aEnd.X() >= p.aEnd.X()
1002         // && r.aStart.Y() > p.aStart.Y() && r.aEnd.Y() < p.aEnd.Y()
1003         // or
1004         // r.aStart.X() <= p.aStart.X() && r.aEnd.X() < p.aEnd.X()
1005         // && r.aStart.Y() > p.aStart.Y() && r.aEnd.Y() < p.aEnd.Y()
1006         else if(handleThreeRanges( aRange, rRange, aNewRanges ))
1007         {
1008             bChanged = true;
1009             continue;
1010         }
1011
1012         // getting 4 ranges
1013         // r.aStart.X() > p.aStart.X() && r.aEnd().X() < p.aEnd.X()
1014         // && r.aStart.Y() > p.aStart.Y() && r.aEnd().Y() < p.aEnd.Y()
1015         else if(handleFourRanges( aRange, rRange, aNewRanges ))
1016         {
1017             bChanged = true;
1018             continue;
1019         }
1020     }
1021     for(const auto & rRange : aNewRanges)
1022         Join(rRange);
1023
1024     return bChanged;
1025 }
1026
1027 const ScRange* ScRangeList::Find( const ScAddress& rAdr ) const
1028 {
1029     auto itr = find_if(
1030         maRanges.cbegin(), maRanges.cend(), FindEnclosingRange<ScAddress>(rAdr));
1031     return itr == maRanges.end() ? nullptr : &*itr;
1032 }
1033
1034 ScRange* ScRangeList::Find( const ScAddress& rAdr )
1035 {
1036     auto itr = find_if(
1037         maRanges.begin(), maRanges.end(), FindEnclosingRange<ScAddress>(rAdr));
1038     return itr == maRanges.end() ? nullptr : &*itr;
1039 }
1040
1041 ScRangeList::ScRangeList() : mnMaxRowUsed(-1) {}
1042
1043 ScRangeList::ScRangeList( const ScRangeList& rList ) :
1044     SvRefBase(rList),
1045     maRanges(rList.maRanges),
1046     mnMaxRowUsed(rList.mnMaxRowUsed)
1047 {
1048 }
1049
1050 ScRangeList::ScRangeList(ScRangeList&& rList) noexcept :
1051     maRanges(std::move(rList.maRanges)),
1052     mnMaxRowUsed(rList.mnMaxRowUsed)
1053 {
1054 }
1055
1056 ScRangeList::ScRangeList( const ScRange& rRange ) :
1057     mnMaxRowUsed(-1)
1058 {
1059     maRanges.reserve(1);
1060     push_back(rRange);
1061 }
1062
1063 ScRangeList& ScRangeList::operator=(const ScRangeList& rList)
1064 {
1065     maRanges = rList.maRanges;
1066     mnMaxRowUsed = rList.mnMaxRowUsed;
1067     return *this;
1068 }
1069
1070 ScRangeList& ScRangeList::operator=(ScRangeList&& rList) noexcept
1071 {
1072     maRanges = std::move(rList.maRanges);
1073     mnMaxRowUsed = rList.mnMaxRowUsed;
1074     return *this;
1075 }
1076
1077 bool ScRangeList::Intersects( const ScRange& rRange ) const
1078 {
1079     return std::any_of(maRanges.begin(), maRanges.end(), FindIntersectingRange<ScRange>(rRange));
1080 }
1081
1082 bool ScRangeList::Contains( const ScRange& rRange ) const
1083 {
1084     return std::any_of(maRanges.begin(), maRanges.end(), FindEnclosingRange<ScRange>(rRange));
1085 }
1086
1087 sal_uInt64 ScRangeList::GetCellCount() const
1088 {
1089     CountCells func;
1090     return for_each(maRanges.begin(), maRanges.end(), func).getCellCount();
1091 }
1092
1093 void ScRangeList::Remove(size_t nPos)
1094 {
1095     if (maRanges.size() <= nPos)
1096         // Out-of-bound condition.  Bail out.
1097         return;
1098     maRanges.erase(maRanges.begin() + nPos);
1099 }
1100
1101 void ScRangeList::RemoveAll()
1102 {
1103     maRanges.clear();
1104     mnMaxRowUsed = -1;
1105 }
1106
1107 ScRange ScRangeList::Combine() const
1108 {
1109     if (maRanges.empty())
1110         return ScRange();
1111
1112     auto itr = maRanges.cbegin(), itrEnd = maRanges.cend();
1113     ScRange aRet = *itr;
1114     ++itr;
1115     for (; itr != itrEnd; ++itr)
1116     {
1117         const ScRange& r = *itr;
1118         SCROW nRow1 = r.aStart.Row(), nRow2 = r.aEnd.Row();
1119         SCCOL nCol1 = r.aStart.Col(), nCol2 = r.aEnd.Col();
1120         SCTAB nTab1 = r.aStart.Tab(), nTab2 = r.aEnd.Tab();
1121         if (aRet.aStart.Row() > nRow1)
1122             aRet.aStart.SetRow(nRow1);
1123         if (aRet.aStart.Col() > nCol1)
1124             aRet.aStart.SetCol(nCol1);
1125         if (aRet.aStart.Tab() > nTab1)
1126             aRet.aStart.SetTab(nTab1);
1127         if (aRet.aEnd.Row() < nRow2)
1128             aRet.aEnd.SetRow(nRow2);
1129         if (aRet.aEnd.Col() < nCol2)
1130             aRet.aEnd.SetCol(nCol2);
1131         if (aRet.aEnd.Tab() < nTab2)
1132             aRet.aEnd.SetTab(nTab2);
1133     }
1134     return aRet;
1135 }
1136
1137 void ScRangeList::push_back(const ScRange & r)
1138 {
1139     maRanges.push_back(r);
1140     if (mnMaxRowUsed < r.aEnd.Row())
1141         mnMaxRowUsed = r.aEnd.Row();
1142 }
1143
1144 void ScRangeList::swap( ScRangeList& r )
1145 {
1146     maRanges.swap(r.maRanges);
1147     std::swap(mnMaxRowUsed, r.mnMaxRowUsed);
1148 }
1149
1150 ScAddress ScRangeList::GetTopLeftCorner() const
1151 {
1152     if(empty())
1153         return ScAddress();
1154
1155     ScAddress const * pAddr = &maRanges[0].aStart;
1156     for(size_t i = 1, n = size(); i < n; ++i)
1157     {
1158         if(maRanges[i].aStart < *pAddr)
1159             pAddr = &maRanges[i].aStart;
1160     }
1161
1162     return *pAddr;
1163 }
1164
1165 ScRangeList ScRangeList::GetIntersectedRange(const ScRange& rRange) const
1166 {
1167     ScRangeList aReturn;
1168     for(auto& rR : maRanges)
1169     {
1170         if(rR.Intersects(rRange))
1171         {
1172             SCCOL nColStart1, nColEnd1, nColStart2, nColEnd2;
1173             SCROW nRowStart1, nRowEnd1, nRowStart2, nRowEnd2;
1174             SCTAB nTabStart1, nTabEnd1, nTabStart2, nTabEnd2;
1175             rR.GetVars(nColStart1, nRowStart1, nTabStart1,
1176                         nColEnd1, nRowEnd1, nTabEnd1);
1177             rRange.GetVars(nColStart2, nRowStart2, nTabStart2,
1178                         nColEnd2, nRowEnd2, nTabEnd2);
1179
1180             ScRange aNewRange(std::max<SCCOL>(nColStart1, nColStart2), std::max<SCROW>(nRowStart1, nRowStart2),
1181                     std::max<SCTAB>(nTabStart1, nTabStart2), std::min<SCCOL>(nColEnd1, nColEnd2),
1182                     std::min<SCROW>(nRowEnd1, nRowEnd2), std::min<SCTAB>(nTabEnd1, nTabEnd2));
1183             aReturn.Join(aNewRange);
1184         }
1185     }
1186
1187     return aReturn;
1188 }
1189
1190 //  ScRangePairList
1191 ScRangePairList::~ScRangePairList()
1192 {
1193 }
1194
1195 void ScRangePairList::Remove(size_t nPos)
1196 {
1197     if (maPairs.size() <= nPos)
1198         // Out-of-bound condition.  Bail out.
1199         return;
1200     maPairs.erase(maPairs.begin() + nPos);
1201 }
1202
1203 void ScRangePairList::Remove( const ScRangePair & rAdr)
1204 {
1205     auto itr = std::find_if(maPairs.begin(), maPairs.end(), [&rAdr](const ScRangePair& rPair) { return &rAdr == &rPair; });
1206     if (itr != maPairs.end())
1207     {
1208         maPairs.erase( itr );
1209         return;
1210     }
1211     assert(false);
1212 }
1213
1214 ScRangePair & ScRangePairList::operator [](size_t idx)
1215 {
1216     return maPairs[idx];
1217 }
1218
1219 const ScRangePair & ScRangePairList::operator [](size_t idx) const
1220 {
1221     return maPairs[idx];
1222 }
1223
1224 size_t ScRangePairList::size() const
1225 {
1226     return maPairs.size();
1227 }
1228
1229 void ScRangePairList::UpdateReference( UpdateRefMode eUpdateRefMode,
1230                                     const ScDocument* pDoc, const ScRange& rWhere,
1231                                     SCCOL nDx, SCROW nDy, SCTAB nDz )
1232 {
1233     if ( maPairs.empty() )
1234         return;
1235
1236     SCCOL nCol1;
1237     SCROW nRow1;
1238     SCTAB nTab1;
1239     SCCOL nCol2;
1240     SCROW nRow2;
1241     SCTAB nTab2;
1242     rWhere.GetVars( nCol1, nRow1, nTab1, nCol2, nRow2, nTab2 );
1243     for (ScRangePair & rR : maPairs)
1244     {
1245         for ( sal_uInt16 j=0; j<2; j++ )
1246         {
1247             ScRange& rRange = rR.GetRange(j);
1248             SCCOL theCol1;
1249             SCROW theRow1;
1250             SCTAB theTab1;
1251             SCCOL theCol2;
1252             SCROW theRow2;
1253             SCTAB theTab2;
1254             rRange.GetVars( theCol1, theRow1, theTab1, theCol2, theRow2, theTab2 );
1255             if ( ScRefUpdate::Update( pDoc, eUpdateRefMode,
1256                     nCol1, nRow1, nTab1, nCol2, nRow2, nTab2,
1257                     nDx, nDy, nDz,
1258                     theCol1, theRow1, theTab1, theCol2, theRow2, theTab2 )
1259                     != UR_NOTHING )
1260             {
1261                 rRange.aStart.Set( theCol1, theRow1, theTab1 );
1262                 rRange.aEnd.Set( theCol2, theRow2, theTab2 );
1263             }
1264         }
1265     }
1266 }
1267
1268 // Delete entries that have the labels (first range) on nTab
1269 void ScRangePairList::DeleteOnTab( SCTAB nTab )
1270 {
1271     std::erase_if(maPairs,
1272         [&nTab](const ScRangePair& rR) {
1273             const ScRange & rRange = rR.GetRange(0);
1274             return (rRange.aStart.Tab() == nTab) && (rRange.aEnd.Tab() == nTab);
1275         });
1276 }
1277
1278 ScRangePair* ScRangePairList::Find( const ScAddress& rAdr )
1279 {
1280     for (ScRangePair & rR : maPairs)
1281     {
1282         if ( rR.GetRange(0).Contains( rAdr ) )
1283             return &rR;
1284     }
1285     return nullptr;
1286 }
1287
1288 ScRangePair* ScRangePairList::Find( const ScRange& rRange )
1289 {
1290     for (ScRangePair & rR : maPairs)
1291     {
1292         if ( rR.GetRange(0) == rRange )
1293             return &rR;
1294     }
1295     return nullptr;
1296 }
1297
1298 ScRangePairList* ScRangePairList::Clone() const
1299 {
1300     ScRangePairList* pNew = new ScRangePairList;
1301     for (const ScRangePair & rR : maPairs)
1302     {
1303         pNew->Append( rR );
1304     }
1305     return pNew;
1306 }
1307
1308 namespace {
1309
1310 class ScRangePairList_sortNameCompare
1311 {
1312 public:
1313     ScRangePairList_sortNameCompare(ScDocument& rDoc) : mrDoc(rDoc) {}
1314
1315     bool operator()( const ScRangePair *ps1, const ScRangePair* ps2 ) const
1316     {
1317         const ScAddress& rStartPos1 = ps1->GetRange(0).aStart;
1318         const ScAddress& rStartPos2 = ps2->GetRange(0).aStart;
1319         OUString aStr1, aStr2;
1320         sal_Int32 nComp;
1321         if ( rStartPos1.Tab() == rStartPos2.Tab() )
1322             nComp = 0;
1323         else
1324         {
1325             mrDoc.GetName( rStartPos1.Tab(), aStr1 );
1326             mrDoc.GetName( rStartPos2.Tab(), aStr2 );
1327             nComp = ScGlobal::GetCollator().compareString( aStr1, aStr2 );
1328         }
1329         if (nComp < 0)
1330         {
1331             return true; // -1;
1332         }
1333         else if (nComp > 0)
1334         {
1335             return false; // 1;
1336         }
1337
1338         // equal tabs
1339         if ( rStartPos1.Col() < rStartPos2.Col() )
1340             return true; // -1;
1341         if ( rStartPos1.Col() > rStartPos2.Col() )
1342             return false; // 1;
1343         // equal cols
1344         if ( rStartPos1.Row() < rStartPos2.Row() )
1345             return true; // -1;
1346         if ( rStartPos1.Row() > rStartPos2.Row() )
1347             return false; // 1;
1348
1349         // first corner equal, second corner
1350         const ScAddress& rEndPos1 = ps1->GetRange(0).aEnd;
1351         const ScAddress& rEndPos2 = ps2->GetRange(0).aEnd;
1352         if ( rEndPos1.Tab() == rEndPos2.Tab() )
1353             nComp = 0;
1354         else
1355         {
1356             mrDoc.GetName( rEndPos1.Tab(), aStr1 );
1357             mrDoc.GetName( rEndPos2.Tab(), aStr2 );
1358             nComp = ScGlobal::GetCollator().compareString( aStr1, aStr2 );
1359         }
1360         if (nComp < 0)
1361         {
1362             return true; // -1;
1363         }
1364         else if (nComp > 0)
1365         {
1366             return false; // 1;
1367         }
1368
1369         // equal tabs
1370         if ( rEndPos1.Col() < rEndPos2.Col() )
1371             return true; // -1;
1372         if ( rEndPos1.Col() > rEndPos2.Col() )
1373             return false; // 1;
1374         // equal cols
1375         if ( rEndPos1.Row() < rEndPos2.Row() )
1376             return true; // -1;
1377         if ( rEndPos1.Row() > rEndPos2.Row() )
1378             return false; // 1;
1379
1380         return false;
1381     }
1382 private:
1383     ScDocument& mrDoc;
1384 };
1385
1386 }
1387
1388 void ScRangePairList::Join( const ScRangePair& r, bool bIsInList )
1389 {
1390     if ( maPairs.empty() )
1391     {
1392         Append( r );
1393         return ;
1394     }
1395
1396     bool bJoinedInput = false;
1397     const ScRangePair* pOver = &r;
1398
1399 Label_RangePair_Join:
1400
1401     assert(pOver);
1402     const ScRange& r1 = pOver->GetRange(0);
1403     const ScRange& r2 = pOver->GetRange(1);
1404     const SCCOL nCol1 = r1.aStart.Col();
1405     const SCROW nRow1 = r1.aStart.Row();
1406     const SCTAB nTab1 = r1.aStart.Tab();
1407     const SCCOL nCol2 = r1.aEnd.Col();
1408     const SCROW nRow2 = r1.aEnd.Row();
1409     const SCTAB nTab2 = r1.aEnd.Tab();
1410
1411     size_t nOverPos = std::numeric_limits<size_t>::max();
1412     for (size_t i = 0; i < maPairs.size(); ++i)
1413     {
1414         ScRangePair & rPair = maPairs[ i ];
1415         if ( &rPair == pOver )
1416         {
1417             nOverPos = i;
1418             continue;           // the same one, continue with the next
1419         }
1420         bool bJoined = false;
1421         ScRange& rp1 = rPair.GetRange(0);
1422         ScRange& rp2 = rPair.GetRange(1);
1423         if ( rp2 == r2 )
1424         {   // only if Range2 is equal
1425             if ( rp1.Contains( r1 ) )
1426             {   // RangePair pOver included in or identical to RangePair p
1427                 if ( bIsInList )
1428                     bJoined = true;     // do away with RangePair pOver
1429                 else
1430                 {   // that was all then
1431                     bJoinedInput = true;    // don't append
1432                     break;  // for
1433                 }
1434             }
1435             else if ( r1.Contains( rp1 ) )
1436             {   // RangePair p included in RangePair pOver, make pOver the new RangePair
1437                 rPair = *pOver;
1438                 bJoined = true;
1439             }
1440         }
1441         if ( !bJoined && rp1.aStart.Tab() == nTab1 && rp1.aEnd.Tab() == nTab2
1442           && rp2.aStart.Tab() == r2.aStart.Tab()
1443           && rp2.aEnd.Tab() == r2.aEnd.Tab() )
1444         {   // 2D, Range2 must be located side-by-side just like Range1
1445             if ( rp1.aStart.Col() == nCol1 && rp1.aEnd.Col() == nCol2
1446               && rp2.aStart.Col() == r2.aStart.Col()
1447               && rp2.aEnd.Col() == r2.aEnd.Col() )
1448             {
1449                 if ( rp1.aStart.Row() == nRow2+1
1450                   && rp2.aStart.Row() == r2.aEnd.Row()+1 )
1451                 {   // top
1452                     rp1.aStart.SetRow( nRow1 );
1453                     rp2.aStart.SetRow( r2.aStart.Row() );
1454                     bJoined = true;
1455                 }
1456                 else if ( rp1.aEnd.Row() == nRow1-1
1457                   && rp2.aEnd.Row() == r2.aStart.Row()-1 )
1458                 {   // bottom
1459                     rp1.aEnd.SetRow( nRow2 );
1460                     rp2.aEnd.SetRow( r2.aEnd.Row() );
1461                     bJoined = true;
1462                 }
1463             }
1464             else if ( rp1.aStart.Row() == nRow1 && rp1.aEnd.Row() == nRow2
1465               && rp2.aStart.Row() == r2.aStart.Row()
1466               && rp2.aEnd.Row() == r2.aEnd.Row() )
1467             {
1468                 if ( rp1.aStart.Col() == nCol2+1
1469                   && rp2.aStart.Col() == r2.aEnd.Col()+1 )
1470                 {   // left
1471                     rp1.aStart.SetCol( nCol1 );
1472                     rp2.aStart.SetCol( r2.aStart.Col() );
1473                     bJoined = true;
1474                 }
1475                 else if ( rp1.aEnd.Col() == nCol1-1
1476                   && rp2.aEnd.Col() == r2.aEnd.Col()-1 )
1477                 {   // right
1478                     rp1.aEnd.SetCol( nCol2 );
1479                     rp2.aEnd.SetCol( r2.aEnd.Col() );
1480                     bJoined = true;
1481                 }
1482             }
1483         }
1484         if ( bJoined )
1485         {
1486             if ( bIsInList )
1487             {   // delete RangePair pOver within the list
1488                 if (nOverPos != std::numeric_limits<size_t>::max())
1489                 {
1490                     Remove(nOverPos);
1491                     if (nOverPos < i)
1492                         --i;
1493                 }
1494                 else
1495                 {
1496                     for (size_t nOver = 0, nRangePairs = maPairs.size(); nOver < nRangePairs; ++nOver)
1497                     {
1498                         if (&maPairs[nOver] == pOver)
1499                         {
1500                             maPairs.erase(maPairs.begin() + nOver);
1501                             break;
1502                         }
1503                     }
1504                     assert(false);
1505                 }
1506             }
1507             bJoinedInput = true;
1508             pOver = &maPairs[i];
1509             bIsInList = true;
1510             goto Label_RangePair_Join;
1511         }
1512     }
1513     if ( !bIsInList && !bJoinedInput )
1514         Append( r );
1515 }
1516
1517 std::vector<const ScRangePair*> ScRangePairList::CreateNameSortedArray( ScDocument& rDoc ) const
1518 {
1519     std::vector<const ScRangePair*> aSortedVec(maPairs.size());
1520     size_t i = 0;
1521     for ( auto const & rPair : maPairs)
1522     {
1523         aSortedVec[i++] = &rPair;
1524     }
1525
1526     std::sort( aSortedVec.begin(), aSortedVec.end(), ScRangePairList_sortNameCompare(rDoc) );
1527
1528     return aSortedVec;
1529 }
1530
1531 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */