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