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