sc/source/core/data/dociter.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 <svl/zforlist.hxx>
  21
  22 #include "scitems.hxx"
  23 #include "global.hxx"
  24 #include "dociter.hxx"
  25 #include "document.hxx"
  26 #include "table.hxx"
  27 #include "column.hxx"
  28 #include "formulacell.hxx"
  29 #include "attarray.hxx"
  30 #include "patattr.hxx"
  31 #include "docoptio.hxx"
  32 #include "cellform.hxx"
  33 #include "segmenttree.hxx"
  34 #include "progress.hxx"
  35 #include "queryparam.hxx"
  36 #include "queryentry.hxx"
  37 #include "globstr.hrc"
  38 #include "editutil.hxx"
  39 #include "cellvalue.hxx"
  40 #include "scmatrix.hxx"
  41
  42 #include "tools/fract.hxx"
  43 #include "editeng/editobj.hxx"
  44 #include "svl/sharedstring.hxx"
  45
  46 #include <vector>
  47
  48 using ::rtl::math::approxEqual;
  49 using ::std::vector;
  50 using ::std::set;
  51
  52 // STATIC DATA -----------------------------------------------------------
  53
  54 namespace {
  55
  56 template<typename _Iter>
  57 void incBlock(std::pair<_Iter, size_t>& rPos)
  58 {
  59     // Move to the next block.
  60     ++rPos.first;
  61     rPos.second = 0;
  62 }
  63
  64 template<typename _Iter>
  65 void incPos(std::pair<_Iter, size_t>& rPos)
  66 {
  67     if (rPos.second + 1 < rPos.first->size)
  68         // Increment within the block.
  69         ++rPos.second;
  70     else
  71         incBlock(rPos);
  72 }
  73
  74 template<typename _Iter>
  75 size_t toLogicalPos(const std::pair<_Iter, size_t>& rPos)
  76 {
  77     return rPos.first->position + rPos.second;
  78 }
  79
  80 }
  81
  82 void ScAttrArray_IterGetNumberFormat( sal_uLong& nFormat, const ScAttrArray*& rpArr,
  83         SCROW& nAttrEndRow, const ScAttrArray* pNewArr, SCROW nRow,
  84         ScDocument* pDoc )
  85 {
  86     if ( rpArr != pNewArr || nAttrEndRow < nRow )
  87     {
  88         SCROW nRowStart = 0;
  89         SCROW nRowEnd = MAXROW;
  90         const ScPatternAttr* pPattern;
  91         if( !(pPattern = pNewArr->GetPatternRange( nRowStart, nRowEnd, nRow ) ) )
  92         {
  93             pPattern = pDoc->GetDefPattern();
  94             nRowEnd = MAXROW;
  95         }
  96
  97         nFormat = pPattern->GetNumberFormat( pDoc->GetFormatTable() );
  98         rpArr = pNewArr;
  99         nAttrEndRow = nRowEnd;
 100     }
 101 }
 102
 103 ScValueIterator::ScValueIterator( ScDocument* pDocument, const ScRange& rRange,
 104             bool bSTotal, bool bTextZero ) :
 105     pDoc( pDocument ),
 106     nNumFmtIndex(0),
 107     maStartPos(rRange.aStart),
 108     maEndPos(rRange.aEnd),
 109     nNumFmtType( NUMBERFORMAT_UNDEFINED ),
 110     bNumValid( false ),
 111     bSubTotal(bSTotal),
 112     bCalcAsShown( pDocument->GetDocOptions().IsCalcAsShown() ),
 113     bTextAsZero( bTextZero )
 114 {
 115     SCTAB nDocMaxTab = pDocument->GetTableCount() - 1;
 116
 117     if (!ValidCol(maStartPos.Col())) maStartPos.SetCol(MAXCOL);
 118     if (!ValidCol(maEndPos.Col())) maEndPos.SetCol(MAXCOL);
 119     if (!ValidRow(maStartPos.Row())) maStartPos.SetRow(MAXROW);
 120     if (!ValidRow(maEndPos.Row())) maEndPos.SetRow(MAXROW);
 121     if (!ValidTab(maStartPos.Tab()) || maStartPos.Tab() > nDocMaxTab) maStartPos.SetTab(nDocMaxTab);
 122     if (!ValidTab(maEndPos.Tab()) || maEndPos.Tab() > nDocMaxTab) maEndPos.SetTab(nDocMaxTab);
 123
 124     nNumFormat = 0; // Initialized in GetNumberFormat
 125     pAttrArray = 0;
 126     nAttrEndRow = 0;
 127 }
 128
 129 SCROW ScValueIterator::GetRow() const
 130 {
 131     // Position of the head of the current block + offset within the block
 132     // equals the logical element position.
 133     return maCurPos.first->position + maCurPos.second;
 134 }
 135
 136 void ScValueIterator::IncBlock()
 137 {
 138     ++maCurPos.first;
 139     maCurPos.second = 0;
 140 }
 141
 142 void ScValueIterator::IncPos()
 143 {
 144     if (maCurPos.second + 1 < maCurPos.first->size)
 145         // Move within the same block.
 146         ++maCurPos.second;
 147     else
 148         // Move to the next block.
 149         IncBlock();
 150 }
 151
 152 void ScValueIterator::SetPos(size_t nPos)
 153 {
 154     maCurPos = mpCells->position(maCurPos.first, nPos);
 155 }
 156
 157 bool ScValueIterator::GetThis(double& rValue, sal_uInt16& rErr)
 158 {
 159     while (true)
 160     {
 161         bool bNextColumn = maCurPos.first == mpCells->end();
 162         if (!bNextColumn)
 163         {
 164             if (GetRow() > maEndPos.Row())
 165                 bNextColumn = true;
 166         }
 167
 168         ScColumn* pCol = NULL;
 169         if (bNextColumn)
 170         {
 171             // Find the next available column.
 172             do
 173             {
 174                 ++mnCol;
 175                 if (mnCol > maEndPos.Col())
 176                 {
 177                     mnCol = maStartPos.Col();
 178                     ++mnTab;
 179                     if (mnTab > maEndPos.Tab())
 180                     {
 181                         rErr = 0;
 182                         return false; // Over and out
 183                     }
 184                 }
 185                 pCol = &(pDoc->maTabs[mnTab])->aCol[mnCol];
 186             }
 187             while (pCol->IsEmptyData());
 188
 189             mpCells = &pCol->maCells;
 190             maCurPos = mpCells->position(maStartPos.Row());
 191         }
 192
 193         SCROW nCurRow = GetRow();
 194         SCROW nLastRow;
 195         if (bSubTotal && pDoc->maTabs[mnTab]->RowFiltered(nCurRow, NULL, &nLastRow))
 196         {
 197             // Skip all filtered rows for subtotal mode.
 198             SetPos(nLastRow+1);
 199             continue;
 200         }
 201
 202         switch (maCurPos.first->type)
 203         {
 204             case sc::element_type_numeric:
 205             {
 206                 bNumValid = false;
 207                 rValue = sc::numeric_block::at(*maCurPos.first->data, maCurPos.second);
 208                 rErr = 0;
 209                 if (bCalcAsShown)
 210                 {
 211                     ScAttrArray_IterGetNumberFormat(nNumFormat, pAttrArray,
 212                         nAttrEndRow, pCol->pAttrArray, nCurRow, pDoc);
 213                     rValue = pDoc->RoundValueAsShown(rValue, nNumFormat);
 214                 }
 215                 return true; // Found it!
 216             }
 217             break;
 218             case sc::element_type_formula:
 219             {
 220                 ScFormulaCell& rCell = *sc::formula_block::at(*maCurPos.first->data, maCurPos.second);
 221                 if (bSubTotal && rCell.IsSubTotal())
 222                 {
 223                     // Skip subtotal formula cells.
 224                     IncPos();
 225                     break;
 226                 }
 227
 228                 if (rCell.GetErrorOrValue(rErr, rValue))
 229                 {
 230                     bNumValid = false;
 231                     return true; // Found it!
 232                 }
 233                 else if (bTextAsZero)
 234                 {
 235                     rValue = 0.0;
 236                     bNumValid = false;
 237                     return true;
 238                 }
 239                 IncPos();
 240             }
 241             break;
 242             case sc::element_type_string :
 243             case sc::element_type_edittext :
 244             {
 245                 if (bTextAsZero)
 246                 {
 247                     rErr = 0;
 248                     rValue = 0.0;
 249                     nNumFmtType = NUMBERFORMAT_NUMBER;
 250                     nNumFmtIndex = 0;
 251                     bNumValid = true;
 252                     return true;
 253                 }
 254                 IncBlock();
 255             }
 256             break;
 257             case sc::element_type_empty:
 258             default:
 259                 // Skip the whole block.
 260                 IncBlock();
 261         }
 262     }
 263 }
 264
 265 void ScValueIterator::GetCurNumFmtInfo( short& nType, sal_uLong& nIndex )
 266 {
 267     if (!bNumValid && mnTab < pDoc->GetTableCount())
 268     {
 269         SCROW nCurRow = GetRow();
 270         const ScColumn* pCol = &(pDoc->maTabs[mnTab])->aCol[mnCol];
 271         nNumFmtIndex = pCol->GetNumberFormat(nCurRow);
 272         nNumFmtType = pDoc->GetFormatTable()->GetType( nNumFmtIndex );
 273         bNumValid = true;
 274     }
 275
 276     nType = nNumFmtType;
 277     nIndex = nNumFmtIndex;
 278 }
 279
 280 bool ScValueIterator::GetFirst(double& rValue, sal_uInt16& rErr)
 281 {
 282     mnCol = maStartPos.Col();
 283     mnTab = maStartPos.Tab();
 284
 285     ScTable* pTab = pDoc->FetchTable(mnTab);
 286     if (!pTab)
 287         return false;
 288
 289     nNumFormat = 0; // Initialized in GetNumberFormat
 290     pAttrArray = 0;
 291     nAttrEndRow = 0;
 292
 293     mpCells = &pTab->aCol[maStartPos.Col()].maCells;
 294     maCurPos = mpCells->position(maStartPos.Row());
 295     return GetThis(rValue, rErr);
 296 }
 297
 298 bool ScValueIterator::GetNext(double& rValue, sal_uInt16& rErr)
 299 {
 300     IncPos();
 301     return GetThis(rValue, rErr);
 302 }
 303
 304 // ============================================================================
 305
 306 ScDBQueryDataIterator::DataAccess::DataAccess(const ScDBQueryDataIterator* pParent) :
 307     mpParent(pParent)
 308 {
 309 }
 310
 311 ScDBQueryDataIterator::DataAccess::~DataAccess()
 312 {
 313 }
 314
 315 const sc::CellStoreType* ScDBQueryDataIterator::GetColumnCellStore(ScDocument& rDoc, SCTAB nTab, SCCOL nCol)
 316 {
 317     ScTable* pTab = rDoc.FetchTable(nTab);
 318     if (!pTab)
 319         return NULL;
 320
 321     return &pTab->aCol[nCol].maCells;
 322 }
 323
 324 const ScAttrArray* ScDBQueryDataIterator::GetAttrArrayByCol(ScDocument& rDoc, SCTAB nTab, SCCOL nCol)
 325 {
 326     if (nTab >= rDoc.GetTableCount())
 327         OSL_FAIL("try to access index out of bounds, FIX IT");
 328     ScColumn* pCol = &rDoc.maTabs[nTab]->aCol[nCol];
 329     return pCol->pAttrArray;
 330 }
 331
 332 bool ScDBQueryDataIterator::IsQueryValid(
 333     ScDocument& rDoc, const ScQueryParam& rParam, SCTAB nTab, SCROW nRow, ScRefCellValue* pCell)
 334 {
 335     if (nTab >= rDoc.GetTableCount())
 336         OSL_FAIL("try to access index out of bounds, FIX IT");
 337     return rDoc.maTabs[nTab]->ValidQuery(nRow, rParam, pCell);
 338 }
 339
 340 // ----------------------------------------------------------------------------
 341
 342 ScDBQueryDataIterator::DataAccessInternal::DataAccessInternal(const ScDBQueryDataIterator* pParent, ScDBQueryParamInternal* pParam, ScDocument* pDoc) :
 343     DataAccess(pParent),
 344     mpCells(NULL),
 345     mpParam(pParam),
 346     mpDoc(pDoc),
 347     bCalcAsShown( pDoc->GetDocOptions().IsCalcAsShown() )
 348 {
 349     nCol = mpParam->mnField;
 350     nRow = mpParam->nRow1;
 351     nTab = mpParam->nTab;
 352     SCSIZE i;
 353     SCSIZE nCount = mpParam->GetEntryCount();
 354     for (i=0; (i<nCount) && (mpParam->GetEntry(i).bDoQuery); i++)
 355     {
 356         ScQueryEntry& rEntry = mpParam->GetEntry(i);
 357         ScQueryEntry::QueryItemsType& rItems = rEntry.GetQueryItems();
 358         rItems.resize(1);
 359         ScQueryEntry::Item& rItem = rItems.front();
 360         sal_uInt32 nIndex = 0;
 361         bool bNumber = mpDoc->GetFormatTable()->IsNumberFormat(
 362             rItem.maString.getString(), nIndex, rItem.mfVal);
 363         rItem.meType = bNumber ? ScQueryEntry::ByValue : ScQueryEntry::ByString;
 364     }
 365     nNumFormat = 0; // Initialized in GetNumberFormat
 366     pAttrArray = 0;
 367     nAttrEndRow = 0;
 368 }
 369
 370 ScDBQueryDataIterator::DataAccessInternal::~DataAccessInternal()
 371 {
 372 }
 373
 374 bool ScDBQueryDataIterator::DataAccessInternal::getCurrent(Value& rValue)
 375 {
 376     // Start with the current row position, and find the first row position
 377     // that satisfies the query.
 378
 379     // If the query starts in the same column as the result vector we can
 380     // prefetch the cell which saves us one fetch in the success case.
 381     SCCOLROW nFirstQueryField = mpParam->GetEntry(0).nField;
 382     ScRefCellValue aCell;
 383
 384     while (true)
 385     {
 386         if (maCurPos.first == mpCells->end() || nRow > mpParam->nRow2)
 387         {
 388             // Bottom of the range reached. Bail out.
 389             rValue.mnError = 0;
 390             return false;
 391         }
 392
 393         if (maCurPos.first->type == sc::element_type_empty)
 394         {
 395             // Skip the whole empty block.
 396             incBlock();
 397             continue;
 398         }
 399
 400         ScRefCellValue* pCell = NULL;
 401         if (nCol == static_cast<SCCOL>(nFirstQueryField))
 402         {
 403             aCell = sc::toRefCell(maCurPos.first, maCurPos.second);
 404             pCell = &aCell;
 405         }
 406
 407         if (ScDBQueryDataIterator::IsQueryValid(*mpDoc, *mpParam, nTab, nRow, pCell))
 408         {
 409             if (!pCell)
 410                 aCell = sc::toRefCell(maCurPos.first, maCurPos.second);
 411             switch (aCell.meType)
 412             {
 413                 case CELLTYPE_VALUE:
 414                 {
 415                     rValue.mfValue = aCell.mfValue;
 416                     rValue.mbIsNumber = true;
 417                     if ( bCalcAsShown )
 418                     {
 419                         const ScAttrArray* pNewAttrArray =
 420                             ScDBQueryDataIterator::GetAttrArrayByCol(*mpDoc, nTab, nCol);
 421                         ScAttrArray_IterGetNumberFormat( nNumFormat, pAttrArray,
 422                             nAttrEndRow, pNewAttrArray, nRow, mpDoc );
 423                         rValue.mfValue = mpDoc->RoundValueAsShown( rValue.mfValue, nNumFormat );
 424                     }
 425                     nNumFmtType = NUMBERFORMAT_NUMBER;
 426                     nNumFmtIndex = 0;
 427                     rValue.mnError = 0;
 428                     return true; // Found it!
 429                 }
 430
 431                 case CELLTYPE_FORMULA:
 432                 {
 433                     if (aCell.mpFormula->IsValue())
 434                     {
 435                         rValue.mfValue = aCell.mpFormula->GetValue();
 436                         rValue.mbIsNumber = true;
 437                         mpDoc->GetNumberFormatInfo(
 438                             nNumFmtType, nNumFmtIndex, ScAddress(nCol, nRow, nTab));
 439                         rValue.mnError = aCell.mpFormula->GetErrCode();
 440                         return true; // Found it!
 441                     }
 442                     else if(mpParam->mbSkipString)
 443                         incPos();
 444                     else
 445                     {
 446                         rValue.maString = aCell.mpFormula->GetString().getString();
 447                         rValue.mfValue = 0.0;
 448                         rValue.mnError = aCell.mpFormula->GetErrCode();
 449                         rValue.mbIsNumber = false;
 450                         return true;
 451                     }
 452                 }
 453                 break;
 454                 case CELLTYPE_STRING:
 455                 case CELLTYPE_EDIT:
 456                     if (mpParam->mbSkipString)
 457                         incPos();
 458                     else
 459                     {
 460                         rValue.maString = aCell.getString(mpDoc);
 461                         rValue.mfValue = 0.0;
 462                         rValue.mnError = 0;
 463                         rValue.mbIsNumber = false;
 464                         return true;
 465                     }
 466                 break;
 467                 default:
 468                     incPos();
 469             }
 470         }
 471         else
 472             incPos();
 473     }
 474 // statement unreachable
 475 }
 476
 477 bool ScDBQueryDataIterator::DataAccessInternal::getFirst(Value& rValue)
 478 {
 479     if (mpParam->bHasHeader)
 480         ++nRow;
 481
 482     mpCells = ScDBQueryDataIterator::GetColumnCellStore(*mpDoc, nTab, nCol);
 483     if (!mpCells)
 484         return false;
 485
 486     maCurPos = mpCells->position(nRow);
 487     return getCurrent(rValue);
 488 }
 489
 490 bool ScDBQueryDataIterator::DataAccessInternal::getNext(Value& rValue)
 491 {
 492     if (!mpCells || maCurPos.first == mpCells->end())
 493         return false;
 494
 495     incPos();
 496     return getCurrent(rValue);
 497 }
 498
 499 void ScDBQueryDataIterator::DataAccessInternal::incBlock()
 500 {
 501     ++maCurPos.first;
 502     maCurPos.second = 0;
 503
 504     nRow = maCurPos.first->position;
 505 }
 506
 507 void ScDBQueryDataIterator::DataAccessInternal::incPos()
 508 {
 509     if (maCurPos.second + 1 < maCurPos.first->size)
 510     {
 511         // Move within the same block.
 512         ++maCurPos.second;
 513         ++nRow;
 514     }
 515     else
 516         // Move to the next block.
 517         incBlock();
 518 }
 519
 520 void ScDBQueryDataIterator::DataAccessInternal::setPos(size_t nPos)
 521 {
 522     maCurPos = mpCells->position(maCurPos.first, nPos);
 523     nRow = nPos;
 524 }
 525
 526 // ----------------------------------------------------------------------------
 527
 528 ScDBQueryDataIterator::DataAccessMatrix::DataAccessMatrix(const ScDBQueryDataIterator* pParent, ScDBQueryParamMatrix* pParam) :
 529     DataAccess(pParent),
 530     mpParam(pParam)
 531 {
 532     SCSIZE nC, nR;
 533     mpParam->mpMatrix->GetDimensions(nC, nR);
 534     mnRows = static_cast<SCROW>(nR);
 535     mnCols = static_cast<SCCOL>(nC);
 536 }
 537
 538 ScDBQueryDataIterator::DataAccessMatrix::~DataAccessMatrix()
 539 {
 540 }
 541
 542 bool ScDBQueryDataIterator::DataAccessMatrix::getCurrent(Value& rValue)
 543 {
 544     // Starting from row == mnCurRow, get the first row that satisfies all the
 545     // query parameters.
 546     for ( ;mnCurRow < mnRows; ++mnCurRow)
 547     {
 548         const ScMatrix& rMat = *mpParam->mpMatrix;
 549         if (rMat.IsEmpty(mpParam->mnField, mnCurRow))
 550             // Don't take empty values into account.
 551             continue;
 552
 553         bool bIsStrVal = rMat.IsString(mpParam->mnField, mnCurRow);
 554         if (bIsStrVal && mpParam->mbSkipString)
 555             continue;
 556
 557         if (isValidQuery(mnCurRow, rMat))
 558         {
 559             rValue.maString = rMat.GetString(mpParam->mnField, mnCurRow).getString();
 560             rValue.mfValue = rMat.GetDouble(mpParam->mnField, mnCurRow);
 561             rValue.mbIsNumber = !bIsStrVal;
 562             rValue.mnError = 0;
 563             return true;
 564         }
 565     }
 566     return false;
 567 }
 568
 569 bool ScDBQueryDataIterator::DataAccessMatrix::getFirst(Value& rValue)
 570 {
 571     mnCurRow = mpParam->bHasHeader ? 1 : 0;
 572     return getCurrent(rValue);
 573 }
 574
 575 bool ScDBQueryDataIterator::DataAccessMatrix::getNext(Value& rValue)
 576 {
 577     ++mnCurRow;
 578     return getCurrent(rValue);
 579 }
 580
 581 namespace {
 582
 583 bool isQueryByValue(const ScQueryEntry::Item& rItem, const ScMatrix& rMat, SCSIZE nCol, SCSIZE nRow)
 584 {
 585     if (rItem.meType == ScQueryEntry::ByString)
 586         return false;
 587
 588     if (!rMat.IsValueOrEmpty(nCol, nRow))
 589         return false;
 590
 591     return true;
 592 }
 593
 594 bool isQueryByString(const ScQueryEntry& rEntry, const ScQueryEntry::Item& rItem, const ScMatrix& rMat, SCSIZE nCol, SCSIZE nRow)
 595 {
 596     switch (rEntry.eOp)
 597     {
 598         case SC_EQUAL:
 599         case SC_NOT_EQUAL:
 600         case SC_CONTAINS:
 601         case SC_DOES_NOT_CONTAIN:
 602         case SC_BEGINS_WITH:
 603         case SC_ENDS_WITH:
 604         case SC_DOES_NOT_BEGIN_WITH:
 605         case SC_DOES_NOT_END_WITH:
 606             return true;
 607         default:
 608             ;
 609     }
 610
 611     if (rItem.meType == ScQueryEntry::ByString && rMat.IsString(nCol, nRow))
 612         return true;
 613
 614     return false;
 615 }
 616
 617 }
 618
 619 bool ScDBQueryDataIterator::DataAccessMatrix::isValidQuery(SCROW nRow, const ScMatrix& rMat) const
 620 {
 621     SCSIZE nEntryCount = mpParam->GetEntryCount();
 622     vector<bool> aResults;
 623     aResults.reserve(nEntryCount);
 624
 625     const CollatorWrapper& rCollator =
 626         mpParam->bCaseSens ? *ScGlobal::GetCaseCollator() : *ScGlobal::GetCollator();
 627
 628     for (SCSIZE i = 0; i < nEntryCount; ++i)
 629     {
 630         const ScQueryEntry& rEntry = mpParam->GetEntry(i);
 631         const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
 632         if (!rEntry.bDoQuery)
 633             continue;
 634
 635         switch (rEntry.eOp)
 636         {
 637             case SC_EQUAL:
 638             case SC_LESS:
 639             case SC_GREATER:
 640             case SC_LESS_EQUAL:
 641             case SC_GREATER_EQUAL:
 642             case SC_NOT_EQUAL:
 643                 break;
 644             default:
 645                 // Only the above operators are supported.
 646                 continue;
 647         }
 648
 649         bool bValid = false;
 650
 651         SCSIZE nField = static_cast<SCSIZE>(rEntry.nField);
 652         if (isQueryByValue(rItem, rMat, nField, nRow))
 653         {
 654             // By value
 655             double fMatVal = rMat.GetDouble(nField, nRow);
 656             bool bEqual = approxEqual(fMatVal, rItem.mfVal);
 657             switch (rEntry.eOp)
 658             {
 659                 case SC_EQUAL:
 660                     bValid = bEqual;
 661                 break;
 662                 case SC_LESS:
 663                     bValid = (fMatVal < rItem.mfVal) && !bEqual;
 664                 break;
 665                 case SC_GREATER:
 666                     bValid = (fMatVal > rItem.mfVal) && !bEqual;
 667                 break;
 668                 case SC_LESS_EQUAL:
 669                     bValid = (fMatVal < rItem.mfVal) || bEqual;
 670                 break;
 671                 case SC_GREATER_EQUAL:
 672                     bValid = (fMatVal > rItem.mfVal) || bEqual;
 673                 break;
 674                 case SC_NOT_EQUAL:
 675                     bValid = !bEqual;
 676                 break;
 677                 default:
 678                     ;
 679             }
 680         }
 681         else if (isQueryByString(rEntry, rItem, rMat, nField, nRow))
 682         {
 683             // By string
 684             do
 685             {
 686                 // Equality check first.
 687                 svl::SharedString aMatStr = rMat.GetString(nField, nRow);
 688                 svl::SharedString aQueryStr = rEntry.GetQueryItem().maString;
 689                 bool bDone = false;
 690                 rtl_uString* p1 = mpParam->bCaseSens ? aMatStr.getData() : aMatStr.getDataIgnoreCase();
 691                 rtl_uString* p2 = mpParam->bCaseSens ? aQueryStr.getData() : aQueryStr.getDataIgnoreCase();
 692                 switch (rEntry.eOp)
 693                 {
 694                     case SC_EQUAL:
 695                         bValid = (p1 == p2);
 696                         bDone = true;
 697                     break;
 698                     case SC_NOT_EQUAL:
 699                         bValid = (p1 != p2);
 700                         bDone = true;
 701                     break;
 702                     default:
 703                         ;
 704                 }
 705
 706                 if (bDone)
 707                     break;
 708
 709                 // Unequality check using collator.
 710                 sal_Int32 nCompare = rCollator.compareString(aMatStr.getString(), aQueryStr.getString());
 711                 switch (rEntry.eOp)
 712                 {
 713                     case SC_LESS :
 714                         bValid = (nCompare < 0);
 715                     break;
 716                     case SC_GREATER :
 717                         bValid = (nCompare > 0);
 718                     break;
 719                     case SC_LESS_EQUAL :
 720                         bValid = (nCompare <= 0);
 721                     break;
 722                     case SC_GREATER_EQUAL :
 723                         bValid = (nCompare >= 0);
 724                     break;
 725                     default:
 726                         ;
 727                 }
 728             }
 729             while (false);
 730         }
 731
 732         if (aResults.empty())
 733             // First query entry.
 734             aResults.push_back(bValid);
 735         else if (rEntry.eConnect == SC_AND)
 736         {
 737             // For AND op, tuck the result into the last result value.
 738             size_t n = aResults.size();
 739             aResults[n-1] = aResults[n-1] && bValid;
 740         }
 741         else
 742             // For OR op, store its own result.
 743             aResults.push_back(bValid);
 744     }
 745
 746     // Row is valid as long as there is at least one result being true.
 747     vector<bool>::const_iterator itr = aResults.begin(), itrEnd = aResults.end();
 748     for (; itr != itrEnd; ++itr)
 749         if (*itr)
 750             return true;
 751
 752     return false;
 753 }
 754
 755 // ----------------------------------------------------------------------------
 756
 757 ScDBQueryDataIterator::Value::Value() :
 758     mnError(0), mbIsNumber(true)
 759 {
 760     ::rtl::math::setNan(&mfValue);
 761 }
 762
 763 // ----------------------------------------------------------------------------
 764
 765 ScDBQueryDataIterator::ScDBQueryDataIterator(ScDocument* pDocument, ScDBQueryParamBase* pParam) :
 766     mpParam (pParam)
 767 {
 768     switch (mpParam->GetType())
 769     {
 770         case ScDBQueryParamBase::INTERNAL:
 771         {
 772             ScDBQueryParamInternal* p = static_cast<ScDBQueryParamInternal*>(pParam);
 773             mpData.reset(new DataAccessInternal(this, p, pDocument));
 774         }
 775         break;
 776         case ScDBQueryParamBase::MATRIX:
 777         {
 778             ScDBQueryParamMatrix* p = static_cast<ScDBQueryParamMatrix*>(pParam);
 779             mpData.reset(new DataAccessMatrix(this, p));
 780         }
 781     }
 782 }
 783
 784 bool ScDBQueryDataIterator::GetFirst(Value& rValue)
 785 {
 786     return mpData->getFirst(rValue);
 787 }
 788
 789 bool ScDBQueryDataIterator::GetNext(Value& rValue)
 790 {
 791     return mpData->getNext(rValue);
 792 }
 793
 794 ScCellIterator::ScCellIterator( ScDocument* pDoc, const ScRange& rRange, bool bSTotal ) :
 795     mpDoc(pDoc),
 796     maStartPos(rRange.aStart),
 797     maEndPos(rRange.aEnd),
 798     mbSubTotal(bSTotal)
 799 {
 800     init();
 801 }
 802
 803 void ScCellIterator::incBlock()
 804 {
 805     ++maCurColPos.first;
 806     maCurColPos.second = 0;
 807
 808     maCurPos.SetRow(maCurColPos.first->position);
 809 }
 810
 811 void ScCellIterator::incPos()
 812 {
 813     if (maCurColPos.second + 1 < maCurColPos.first->size)
 814     {
 815         // Move within the same block.
 816         ++maCurColPos.second;
 817         maCurPos.IncRow();
 818     }
 819     else
 820         // Move to the next block.
 821         incBlock();
 822 }
 823
 824 void ScCellIterator::setPos(size_t nPos)
 825 {
 826     maCurColPos = getColumn()->maCells.position(maCurColPos.first, nPos);
 827     maCurPos.SetRow(nPos);
 828 }
 829
 830 const ScColumn* ScCellIterator::getColumn() const
 831 {
 832     return &mpDoc->maTabs[maCurPos.Tab()]->aCol[maCurPos.Col()];
 833 }
 834
 835 void ScCellIterator::init()
 836 {
 837     SCTAB nDocMaxTab = mpDoc->GetTableCount() - 1;
 838
 839     PutInOrder(maStartPos, maEndPos);
 840
 841     if (!ValidCol(maStartPos.Col())) maStartPos.SetCol(MAXCOL);
 842     if (!ValidCol(maEndPos.Col())) maEndPos.SetCol(MAXCOL);
 843     if (!ValidRow(maStartPos.Row())) maStartPos.SetRow(MAXROW);
 844     if (!ValidRow(maEndPos.Row())) maEndPos.SetRow(MAXROW);
 845     if (!ValidTab(maStartPos.Tab(), nDocMaxTab)) maStartPos.SetTab(nDocMaxTab);
 846     if (!ValidTab(maEndPos.Tab(), nDocMaxTab)) maEndPos.SetTab(nDocMaxTab);
 847
 848     while (maEndPos.Tab() > 0 && !mpDoc->maTabs[maEndPos.Tab()])
 849         maEndPos.IncTab(-1); // Only the tables in use
 850
 851     if (maStartPos.Tab() > maEndPos.Tab())
 852         maStartPos.SetTab(maEndPos.Tab());
 853
 854     maCurPos = maStartPos;
 855
 856     if (!mpDoc->maTabs[maCurPos.Tab()])
 857     {
 858         OSL_FAIL("Table not found");
 859         maStartPos = ScAddress(MAXCOL+1, MAXROW+1, MAXTAB+1); // -> Abort on GetFirst.
 860         maCurPos = maStartPos;
 861     }
 862 }
 863
 864 bool ScCellIterator::getCurrent()
 865 {
 866     const ScColumn* pCol = getColumn();
 867
 868     while (true)
 869     {
 870         bool bNextColumn = maCurColPos.first == pCol->maCells.end();
 871         if (!bNextColumn)
 872         {
 873             if (maCurPos.Row() > maEndPos.Row())
 874                 bNextColumn = true;
 875         }
 876
 877         if (bNextColumn)
 878         {
 879             // Move to the next column.
 880             maCurPos.SetRow(maStartPos.Row());
 881             do
 882             {
 883                 maCurPos.IncCol();
 884                 if (maCurPos.Col() > maEndPos.Col())
 885                 {
 886                     maCurPos.SetCol(maStartPos.Col());
 887                     maCurPos.IncTab();
 888                     if (maCurPos.Tab() > maEndPos.Tab())
 889                     {
 890                         maCurCell.clear();
 891                         return false; // Over and out
 892                     }
 893                 }
 894                 pCol = getColumn();
 895             }
 896             while (pCol->IsEmptyData());
 897
 898             maCurColPos = pCol->maCells.position(maCurPos.Row());
 899         }
 900
 901         if (maCurColPos.first->type == sc::element_type_empty)
 902         {
 903             incBlock();
 904             continue;
 905         }
 906
 907         SCROW nLastRow;
 908         if (mbSubTotal && pCol->GetDoc().maTabs[maCurPos.Tab()]->RowFiltered(maCurPos.Row(), NULL, &nLastRow))
 909         {
 910             // Skip all filtered rows for subtotal mode.
 911             setPos(nLastRow+1);
 912             continue;
 913         }
 914
 915         if (maCurColPos.first->type == sc::element_type_formula)
 916         {
 917             const ScFormulaCell* pCell = sc::formula_block::at(*maCurColPos.first->data, maCurColPos.second);
 918             if (pCell->IsSubTotal())
 919             {
 920                 // Skip subtotal formula cells.
 921                 incPos();
 922                 continue;
 923             }
 924         }
 925
 926         maCurCell = sc::toRefCell(maCurColPos.first, maCurColPos.second);
 927         return true;
 928     }
 929     return false;
 930 }
 931
 932 CellType ScCellIterator::getType() const
 933 {
 934     return maCurCell.meType;
 935 }
 936
 937 OUString ScCellIterator::getString()
 938 {
 939     return maCurCell.getString(mpDoc);
 940 }
 941
 942 const EditTextObject* ScCellIterator::getEditText() const
 943 {
 944     return maCurCell.mpEditText;
 945 }
 946
 947 ScFormulaCell* ScCellIterator::getFormulaCell()
 948 {
 949     return maCurCell.mpFormula;
 950 }
 951
 952 const ScFormulaCell* ScCellIterator::getFormulaCell() const
 953 {
 954     return maCurCell.mpFormula;
 955 }
 956
 957 double ScCellIterator::getValue()
 958 {
 959     return maCurCell.getValue();
 960 }
 961
 962 ScCellValue ScCellIterator::getCellValue() const
 963 {
 964     ScCellValue aRet;
 965     aRet.meType = maCurCell.meType;
 966
 967     switch (maCurCell.meType)
 968     {
 969         case CELLTYPE_STRING:
 970             aRet.mpString = new svl::SharedString(*maCurCell.mpString);
 971         break;
 972         case CELLTYPE_EDIT:
 973             aRet.mpEditText = maCurCell.mpEditText->Clone();
 974         break;
 975         case CELLTYPE_VALUE:
 976             aRet.mfValue = maCurCell.mfValue;
 977         break;
 978         case CELLTYPE_FORMULA:
 979             aRet.mpFormula = maCurCell.mpFormula->Clone();
 980         break;
 981         default:
 982             ;
 983     }
 984
 985     return aRet;
 986 }
 987
 988 const ScRefCellValue& ScCellIterator::getRefCellValue() const
 989 {
 990     return maCurCell;
 991 }
 992
 993 bool ScCellIterator::hasString() const
 994 {
 995     return maCurCell.hasString();
 996 }
 997
 998 bool ScCellIterator::hasNumeric() const
 999 {
1000     return maCurCell.hasNumeric();
1001 }
1002
1003 bool ScCellIterator::hasEmptyData() const
1004 {
1005     if (maCurCell.isEmpty())
1006         return true;
1007
1008     if (maCurCell.meType == CELLTYPE_FORMULA)
1009         return maCurCell.mpFormula->IsEmpty();
1010
1011     return false;
1012 }
1013
1014 bool ScCellIterator::isEmpty() const
1015 {
1016     return maCurCell.isEmpty();
1017 }
1018
1019 bool ScCellIterator::equalsWithoutFormat( const ScAddress& rPos ) const
1020 {
1021     ScRefCellValue aOther;
1022     aOther.assign(*mpDoc, rPos);
1023     return maCurCell.equalsWithoutFormat(aOther);
1024 }
1025
1026 bool ScCellIterator::first()
1027 {
1028     if (!ValidTab(maCurPos.Tab()))
1029         return false;
1030
1031     maCurPos = maStartPos;
1032     const ScColumn* pCol = getColumn();
1033
1034     maCurColPos = pCol->maCells.position(maCurPos.Row());
1035     return getCurrent();
1036 }
1037
1038 bool ScCellIterator::next()
1039 {
1040     incPos();
1041     return getCurrent();
1042 }
1043
1044 //-------------------------------------------------------------------------------
1045
1046 ScQueryCellIterator::ScQueryCellIterator(ScDocument* pDocument, SCTAB nTable,
1047              const ScQueryParam& rParam, bool bMod ) :
1048     mpParam(new ScQueryParam(rParam)),
1049     pDoc( pDocument ),
1050     nTab( nTable),
1051     nStopOnMismatch( nStopOnMismatchDisabled ),
1052     nTestEqualCondition( nTestEqualConditionDisabled ),
1053     bAdvanceQuery( false ),
1054     bIgnoreMismatchOnLeadingStrings( false )
1055 {
1056     nCol = mpParam->nCol1;
1057     nRow = mpParam->nRow1;
1058     SCSIZE i;
1059     if (bMod) // Or else it's already inserted
1060     {
1061         SCSIZE nCount = mpParam->GetEntryCount();
1062         for (i = 0; (i < nCount) && (mpParam->GetEntry(i).bDoQuery); ++i)
1063         {
1064             ScQueryEntry& rEntry = mpParam->GetEntry(i);
1065             ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
1066             sal_uInt32 nIndex = 0;
1067             bool bNumber = pDoc->GetFormatTable()->IsNumberFormat(
1068                 rItem.maString.getString(), nIndex, rItem.mfVal);
1069             rItem.meType = bNumber ? ScQueryEntry::ByValue : ScQueryEntry::ByString;
1070         }
1071     }
1072     nNumFormat = 0; // Initialized in GetNumberFormat
1073     pAttrArray = 0;
1074     nAttrEndRow = 0;
1075 }
1076
1077 void ScQueryCellIterator::InitPos()
1078 {
1079     nRow = mpParam->nRow1;
1080     if (mpParam->bHasHeader && mpParam->bByRow)
1081         ++nRow;
1082     ScColumn* pCol = &(pDoc->maTabs[nTab])->aCol[nCol];
1083     maCurPos = pCol->maCells.position(nRow);
1084 }
1085
1086 void ScQueryCellIterator::IncPos()
1087 {
1088     if (maCurPos.second + 1 < maCurPos.first->size)
1089     {
1090         // Move within the same block.
1091         ++maCurPos.second;
1092         ++nRow;
1093     }
1094     else
1095         // Move to the next block.
1096         IncBlock();
1097 }
1098
1099 void ScQueryCellIterator::IncBlock()
1100 {
1101     ++maCurPos.first;
1102     maCurPos.second = 0;
1103
1104     nRow = maCurPos.first->position;
1105 }
1106
1107 bool ScQueryCellIterator::GetThis()
1108 {
1109     if (nTab >= pDoc->GetTableCount())
1110         OSL_FAIL("try to access index out of bounds, FIX IT");
1111     const ScQueryEntry& rEntry = mpParam->GetEntry(0);
1112     const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
1113
1114     SCCOLROW nFirstQueryField = rEntry.nField;
1115     bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings &&
1116         rItem.meType != ScQueryEntry::ByString;
1117     bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
1118         !mpParam->bHasHeader && rItem.meType == ScQueryEntry::ByString &&
1119         ((mpParam->bByRow && nRow == mpParam->nRow1) ||
1120          (!mpParam->bByRow && nCol == mpParam->nCol1));
1121
1122     ScColumn* pCol = &(pDoc->maTabs[nTab])->aCol[nCol];
1123     while (true)
1124     {
1125         bool bNextColumn = maCurPos.first == pCol->maCells.end();
1126         if (!bNextColumn)
1127         {
1128             if (nRow > mpParam->nRow2)
1129                 bNextColumn = true;
1130         }
1131
1132         if (bNextColumn)
1133         {
1134             do
1135             {
1136                 if ( ++nCol > mpParam->nCol2 )
1137                     return false; // Over and out
1138                 if ( bAdvanceQuery )
1139                 {
1140                     AdvanceQueryParamEntryField();
1141                     nFirstQueryField = rEntry.nField;
1142                 }
1143                 pCol = &(pDoc->maTabs[nTab])->aCol[nCol];
1144             }
1145             while (pCol->IsEmptyData());
1146
1147             InitPos();
1148
1149             bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
1150                 !mpParam->bHasHeader && rItem.meType == ScQueryEntry::ByString &&
1151                 mpParam->bByRow;
1152         }
1153
1154         if (maCurPos.first->type == sc::element_type_empty)
1155         {
1156             IncBlock();
1157             continue;
1158         }
1159
1160         ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second);
1161
1162         if (bAllStringIgnore && aCell.hasString())
1163             IncPos();
1164         else
1165         {
1166             bool bTestEqualCondition = false;
1167             if ( pDoc->maTabs[nTab]->ValidQuery( nRow, *mpParam,
1168                     (nCol == static_cast<SCCOL>(nFirstQueryField) ? &aCell : NULL),
1169                     (nTestEqualCondition ? &bTestEqualCondition : NULL) ) )
1170             {
1171                 if ( nTestEqualCondition && bTestEqualCondition )
1172                     nTestEqualCondition |= nTestEqualConditionMatched;
1173                 return !aCell.isEmpty(); // Found it!
1174             }
1175             else if ( nStopOnMismatch )
1176             {
1177                 // Yes, even a mismatch may have a fulfilled equal
1178                 // condition if regular expressions were involved and
1179                 // SC_LESS_EQUAL or SC_GREATER_EQUAL were queried.
1180                 if ( nTestEqualCondition && bTestEqualCondition )
1181                 {
1182                     nTestEqualCondition |= nTestEqualConditionMatched;
1183                     nStopOnMismatch |= nStopOnMismatchOccurred;
1184                     return false;
1185                 }
1186                 bool bStop;
1187                 if (bFirstStringIgnore)
1188                 {
1189                     if (aCell.hasString())
1190                     {
1191                         IncPos();
1192                         bStop = false;
1193                     }
1194                     else
1195                         bStop = true;
1196                 }
1197                 else
1198                     bStop = true;
1199                 if (bStop)
1200                 {
1201                     nStopOnMismatch |= nStopOnMismatchOccurred;
1202                     return false;
1203                 }
1204             }
1205             else
1206                 IncPos();
1207         }
1208         bFirstStringIgnore = false;
1209     }
1210 }
1211
1212 bool ScQueryCellIterator::GetFirst()
1213 {
1214     if (nTab >= pDoc->GetTableCount())
1215         OSL_FAIL("try to access index out of bounds, FIX IT");
1216     nCol = mpParam->nCol1;
1217     InitPos();
1218     return GetThis();
1219 }
1220
1221 bool ScQueryCellIterator::GetNext()
1222 {
1223     IncPos();
1224     if ( nStopOnMismatch )
1225         nStopOnMismatch = nStopOnMismatchEnabled;
1226     if ( nTestEqualCondition )
1227         nTestEqualCondition = nTestEqualConditionEnabled;
1228     return GetThis();
1229 }
1230
1231 void ScQueryCellIterator::AdvanceQueryParamEntryField()
1232 {
1233     SCSIZE nEntries = mpParam->GetEntryCount();
1234     for ( SCSIZE j = 0; j < nEntries; j++  )
1235     {
1236         ScQueryEntry& rEntry = mpParam->GetEntry( j );
1237         if ( rEntry.bDoQuery )
1238         {
1239             if ( rEntry.nField < MAXCOL )
1240                 rEntry.nField++;
1241             else
1242             {
1243                 OSL_FAIL( "AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL" );
1244             }
1245         }
1246         else
1247             break;  // for
1248     }
1249 }
1250
1251
1252 bool ScQueryCellIterator::FindEqualOrSortedLastInRange( SCCOL& nFoundCol,
1253         SCROW& nFoundRow, bool bSearchForEqualAfterMismatch,
1254         bool bIgnoreMismatchOnLeadingStringsP )
1255 {
1256     // Set and automatically reset mpParam->mbRangeLookup when returning. We
1257     // could use comphelper::FlagRestorationGuard, but really, that one is
1258     // overengineered for this simple purpose here.
1259     struct BoolResetter
1260     {
1261         bool& mr;
1262         bool  mb;
1263         BoolResetter( bool& r, bool b ) : mr(r), mb(r) { r = b; }
1264         ~BoolResetter() { mr = mb; }
1265     } aRangeLookupResetter( mpParam->mbRangeLookup, true);
1266
1267     nFoundCol = MAXCOL+1;
1268     nFoundRow = MAXROW+1;
1269     SetStopOnMismatch( true ); // assume sorted keys
1270     SetTestEqualCondition( true );
1271     bIgnoreMismatchOnLeadingStrings = bIgnoreMismatchOnLeadingStringsP;
1272     bool bRegExp = mpParam->bRegExp && mpParam->GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString;
1273     bool bBinary = !bRegExp && mpParam->bByRow && (mpParam->GetEntry(0).eOp ==
1274             SC_LESS_EQUAL || mpParam->GetEntry(0).eOp == SC_GREATER_EQUAL);
1275     bool bFound = false;
1276     if (bBinary)
1277     {
1278         if (BinarySearch())
1279         {
1280             // BinarySearch() already positions correctly and only needs real
1281             // query comparisons afterwards, skip the verification check below.
1282             mpParam->mbRangeLookup = false;
1283             bFound = GetThis();
1284         }
1285     }
1286     else
1287     {
1288         bFound = GetFirst();
1289     }
1290     if (bFound)
1291     {
1292         // First equal entry or last smaller than (greater than) entry.
1293         PositionType aPosSave;
1294         bool bNext = false;
1295         do
1296         {
1297             nFoundCol = GetCol();
1298             nFoundRow = GetRow();
1299             aPosSave = maCurPos;
1300         }
1301         while ( !IsEqualConditionFulfilled() && (bNext = GetNext()));
1302
1303         // There may be no pNext but equal condition fulfilled if regular
1304         // expressions are involved. Keep the found entry and proceed.
1305         if (!bNext && !IsEqualConditionFulfilled())
1306         {
1307             // Step back to last in range and adjust position markers for
1308             // GetNumberFormat() or similar.
1309             SCCOL nColDiff = nCol - nFoundCol;
1310             nCol = nFoundCol;
1311             nRow = nFoundRow;
1312             maCurPos = aPosSave;
1313             if (mpParam->mbRangeLookup)
1314             {
1315                 // Verify that the found entry does not only fulfill the range
1316                 // lookup but also the real query, i.e. not numeric was found
1317                 // if query is ByString and vice versa.
1318                 mpParam->mbRangeLookup = false;
1319                 // Step back the last field advance if GetNext() did one.
1320                 if (bAdvanceQuery && nColDiff)
1321                 {
1322                     SCSIZE nEntries = mpParam->GetEntryCount();
1323                     for (SCSIZE j=0; j < nEntries; ++j)
1324                     {
1325                         ScQueryEntry& rEntry = mpParam->GetEntry( j );
1326                         if (rEntry.bDoQuery)
1327                         {
1328                             if (rEntry.nField - nColDiff >= 0)
1329                                 rEntry.nField -= nColDiff;
1330                             else
1331                             {
1332                                 assert(!"FindEqualOrSortedLastInRange: rEntry.nField -= nColDiff < 0");
1333                             }
1334                         }
1335                         else
1336                             break;  // for
1337                     }
1338                 }
1339                 // Check it.
1340                 if (!GetThis())
1341                 {
1342                     nFoundCol = MAXCOL+1;
1343                     nFoundRow = MAXROW+1;
1344                 }
1345             }
1346         }
1347     }
1348     if ( IsEqualConditionFulfilled() )
1349     {
1350         // Position on last equal entry.
1351         SCSIZE nEntries = mpParam->GetEntryCount();
1352         for ( SCSIZE j = 0; j < nEntries; j++  )
1353         {
1354             ScQueryEntry& rEntry = mpParam->GetEntry( j );
1355             if ( rEntry.bDoQuery )
1356             {
1357                 switch ( rEntry.eOp )
1358                 {
1359                     case SC_LESS_EQUAL :
1360                     case SC_GREATER_EQUAL :
1361                         rEntry.eOp = SC_EQUAL;
1362                     break;
1363                     default:
1364                     {
1365                         // added to avoid warnings
1366                     }
1367                 }
1368             }
1369             else
1370                 break;  // for
1371         }
1372         PositionType aPosSave;
1373         bIgnoreMismatchOnLeadingStrings = false;
1374         SetTestEqualCondition( false );
1375         do
1376         {
1377             nFoundCol = GetCol();
1378             nFoundRow = GetRow();
1379             aPosSave = maCurPos;
1380         } while (GetNext());
1381
1382         // Step back conditions are the same as above
1383         nCol = nFoundCol;
1384         nRow = nFoundRow;
1385         maCurPos = aPosSave;
1386         return true;
1387     }
1388     if ( (bSearchForEqualAfterMismatch || mpParam->bRegExp) &&
1389             StoppedOnMismatch() )
1390     {
1391         // Assume found entry to be the last value less than respectively
1392         // greater than the query. But keep on searching for an equal match.
1393         SCSIZE nEntries = mpParam->GetEntryCount();
1394         for ( SCSIZE j = 0; j < nEntries; j++  )
1395         {
1396             ScQueryEntry& rEntry = mpParam->GetEntry( j );
1397             if ( rEntry.bDoQuery )
1398             {
1399                 switch ( rEntry.eOp )
1400                 {
1401                     case SC_LESS_EQUAL :
1402                     case SC_GREATER_EQUAL :
1403                         rEntry.eOp = SC_EQUAL;
1404                     break;
1405                     default:
1406                     {
1407                         // added to avoid warnings
1408                     }
1409                 }
1410             }
1411             else
1412                 break;  // for
1413         }
1414         SetStopOnMismatch( false );
1415         SetTestEqualCondition( false );
1416         if (GetNext())
1417         {
1418             // Last of a consecutive area, avoid searching the entire parameter
1419             // range as it is a real performance bottleneck in case of regular
1420             // expressions.
1421             PositionType aPosSave;
1422             do
1423             {
1424                 nFoundCol = GetCol();
1425                 nFoundRow = GetRow();
1426                 aPosSave = maCurPos;
1427                 SetStopOnMismatch( true );
1428             } while (GetNext());
1429             nCol = nFoundCol;
1430             nRow = nFoundRow;
1431             maCurPos = aPosSave;
1432         }
1433     }
1434     return (nFoundCol <= MAXCOL) && (nFoundRow <= MAXROW);
1435 }
1436
1437
1438 bool ScQueryCellIterator::BinarySearch()
1439 {
1440     // TODO: This will be extremely slow with mdds::multi_type_vector.
1441
1442     if (nTab >= pDoc->GetTableCount())
1443         OSL_FAIL("try to access index out of bounds, FIX IT");
1444     nCol = mpParam->nCol1;
1445     ScColumn* pCol = &(pDoc->maTabs[nTab])->aCol[nCol];
1446     if (pCol->IsEmptyData())
1447         return false;
1448
1449     PositionType aHiPos, aLoPos;
1450     ScRefCellValue aCell;
1451
1452     CollatorWrapper* pCollator = (mpParam->bCaseSens ? ScGlobal::GetCaseCollator() :
1453         ScGlobal::GetCollator());
1454     SvNumberFormatter& rFormatter = *(pDoc->GetFormatTable());
1455     const ScQueryEntry& rEntry = mpParam->GetEntry(0);
1456     const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
1457     bool bLessEqual = rEntry.eOp == SC_LESS_EQUAL;
1458     bool bByString = rItem.meType == ScQueryEntry::ByString;
1459     bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString;
1460     bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
1461         !mpParam->bHasHeader && bByString;
1462
1463     nRow = mpParam->nRow1;
1464     if (mpParam->bHasHeader)
1465         nRow++;
1466
1467     aLoPos = pCol->maCells.position(nRow);
1468     if (bFirstStringIgnore && aLoPos.first->type == sc::element_type_string)
1469     {
1470         OUString aCellStr;
1471         sal_uLong nFormat = pCol->GetNumberFormat(toLogicalPos(aLoPos));
1472         aCell = sc::toRefCell(aLoPos.first, aLoPos.second);
1473         ScCellFormat::GetInputString(aCell, nFormat, aCellStr, rFormatter, pDoc);
1474         sal_Int32 nTmp = pCollator->compareString(aCellStr, rEntry.GetQueryItem().maString.getString());
1475         if ((rEntry.eOp == SC_LESS_EQUAL && nTmp > 0) ||
1476                 (rEntry.eOp == SC_GREATER_EQUAL && nTmp < 0) ||
1477                 (rEntry.eOp == SC_EQUAL && nTmp != 0))
1478         {
1479             // Skip the first string value at low point.
1480             incPos(aLoPos);
1481         }
1482     }
1483
1484     aHiPos = pCol->maCells.position(mpParam->nRow2);
1485     if (bAllStringIgnore)
1486     {
1487         // Skip all string cells, but never go past the high point.
1488         if (aLoPos.first->type == sc::element_type_string)
1489         {
1490             if (aLoPos.first == pCol->maCells.end())
1491                 // This is the last block. Move to the last element in this block.
1492                 aLoPos.second = aLoPos.first->size - 1;
1493             else
1494                 // Move to the next block.
1495                 incBlock(aLoPos);
1496         }
1497
1498         if (toLogicalPos(aLoPos) > toLogicalPos(aHiPos))
1499             // Never go past the high point.
1500             aLoPos = aHiPos;
1501     }
1502
1503     // Bookkeeping values for breaking up the binary search in case the data
1504     // range isn't strictly sorted.
1505     PositionType aLastInRange = aLoPos;
1506     PositionType aFirstLastInRange = aLastInRange;
1507     double fLastInRangeValue = bLessEqual ?
1508         -(::std::numeric_limits<double>::max()) :
1509             ::std::numeric_limits<double>::max();
1510     OUString aLastInRangeString;
1511     if (!bLessEqual)
1512         aLastInRangeString = OUString(sal_Unicode(0xFFFF));
1513     if (aLastInRange.first != pCol->maCells.end())
1514     {
1515         aCell = sc::toRefCell(aLastInRange.first, aLastInRange.second);
1516         if (aCell.hasString())
1517         {
1518             sal_uLong nFormat = pCol->GetNumberFormat(toLogicalPos(aLastInRange));
1519             OUString aStr;
1520             ScCellFormat::GetInputString(aCell, nFormat, aStr, rFormatter, pDoc);
1521             aLastInRangeString = aStr;
1522         }
1523         else
1524         {
1525             switch (aCell.meType)
1526             {
1527                 case CELLTYPE_VALUE :
1528                     fLastInRangeValue = aCell.mfValue;
1529                 break;
1530                 case CELLTYPE_FORMULA :
1531                     fLastInRangeValue = aCell.mpFormula->GetValue();
1532                 break;
1533                 default:
1534                 {
1535                     // added to avoid warnings
1536                 }
1537             }
1538         }
1539     }
1540
1541     sal_Int32 nRes = 0;
1542     bool bFound = false;
1543     bool bDone = false;
1544     size_t nLogicalLow = toLogicalPos(aLoPos), nLogicalHigh = toLogicalPos(aHiPos);
1545     while (nLogicalLow <= nLogicalHigh && !bDone)
1546     {
1547         size_t nMid = (nLogicalLow+nLogicalHigh)/2;
1548         size_t i = nMid;
1549         if (i > nLogicalHigh)
1550         {
1551             if (nMid > 0)
1552                 nLogicalHigh = nMid - 1;
1553             else
1554                 bDone = true;
1555             continue; // while
1556         }
1557
1558         bool bHaveRefCell = false;
1559         PositionType aPos = pCol->maCells.position(i);
1560         bool bStr;
1561         switch (aPos.first->type)
1562         {
1563             case sc::element_type_formula:
1564                 aCell = sc::toRefCell(aPos.first, aPos.second);
1565                 bHaveRefCell = true;
1566                 bStr = aCell.hasString();
1567                 break;
1568             case sc::element_type_string:
1569             case sc::element_type_edittext:
1570                 bStr = true;
1571                 break;
1572             default:
1573                 bStr = false;
1574                 break;
1575         }
1576         nRes = 0;
1577
1578         // compares are content<query:-1, content>query:1
1579         // Cell value comparison similar to ScTable::ValidQuery()
1580         if (!bStr && !bByString)
1581         {
1582             double nCellVal;
1583             if (!bHaveRefCell)
1584                 aCell = sc::toRefCell(aPos.first, aPos.second);
1585             switch (aCell.meType)
1586             {
1587                 case CELLTYPE_VALUE :
1588                     nCellVal = aCell.mfValue;
1589                     break;
1590                 case CELLTYPE_FORMULA :
1591                     nCellVal = aCell.mpFormula->GetValue();
1592                     break;
1593                 default:
1594                     nCellVal = 0.0;
1595             }
1596             if ((nCellVal < rItem.mfVal) && !::rtl::math::approxEqual(
1597                         nCellVal, rItem.mfVal))
1598             {
1599                 nRes = -1;
1600                 if (bLessEqual)
1601                 {
1602                     if (fLastInRangeValue < nCellVal)
1603                     {
1604                         fLastInRangeValue = nCellVal;
1605                         aLastInRange = aPos;
1606                     }
1607                     else if (fLastInRangeValue > nCellVal)
1608                     {
1609                         // not strictly sorted, continue with GetThis()
1610                         aLastInRange = aFirstLastInRange;
1611                         bDone = true;
1612                     }
1613                 }
1614             }
1615             else if ((nCellVal > rItem.mfVal) && !::rtl::math::approxEqual(
1616                         nCellVal, rItem.mfVal))
1617             {
1618                 nRes = 1;
1619                 if (!bLessEqual)
1620                 {
1621                     if (fLastInRangeValue > nCellVal)
1622                     {
1623                         fLastInRangeValue = nCellVal;
1624                         aLastInRange = aPos;
1625                     }
1626                     else if (fLastInRangeValue < nCellVal)
1627                     {
1628                         // not strictly sorted, continue with GetThis()
1629                         aLastInRange = aFirstLastInRange;
1630                         bDone = true;
1631                     }
1632                 }
1633             }
1634         }
1635         else if (bStr && bByString)
1636         {
1637             OUString aCellStr;
1638             sal_uLong nFormat = pCol->GetNumberFormat(i);
1639             if (!bHaveRefCell)
1640                 aCell = sc::toRefCell(aPos.first, aPos.second);
1641             ScCellFormat::GetInputString(aCell, nFormat, aCellStr, rFormatter, pDoc);
1642
1643             nRes = pCollator->compareString(aCellStr, rEntry.GetQueryItem().maString.getString());
1644             if (nRes < 0 && bLessEqual)
1645             {
1646                 sal_Int32 nTmp = pCollator->compareString( aLastInRangeString,
1647                         aCellStr);
1648                 if (nTmp < 0)
1649                 {
1650                     aLastInRangeString = aCellStr;
1651                     aLastInRange = aPos;
1652                 }
1653                 else if (nTmp > 0)
1654                 {
1655                     // not strictly sorted, continue with GetThis()
1656                     aLastInRange = aFirstLastInRange;
1657                     bDone = true;
1658                 }
1659             }
1660             else if (nRes > 0 && !bLessEqual)
1661             {
1662                 sal_Int32 nTmp = pCollator->compareString( aLastInRangeString,
1663                         aCellStr);
1664                 if (nTmp > 0)
1665                 {
1666                     aLastInRangeString = aCellStr;
1667                     aLastInRange = aPos;
1668                 }
1669                 else if (nTmp < 0)
1670                 {
1671                     // not strictly sorted, continue with GetThis()
1672                     aLastInRange = aFirstLastInRange;
1673                     bDone = true;
1674                 }
1675             }
1676         }
1677         else if (!bStr && bByString)
1678         {
1679             nRes = -1; // numeric < string
1680             if (bLessEqual)
1681                 aLastInRange = aPos;
1682         }
1683         else // if (bStr && !bByString)
1684         {
1685             nRes = 1; // string > numeric
1686             if (!bLessEqual)
1687                 aLastInRange = aPos;
1688         }
1689         if (nRes < 0)
1690         {
1691             if (bLessEqual)
1692                 nLogicalLow = nMid + 1;
1693             else // assumed to be SC_GREATER_EQUAL
1694             {
1695                 if (nMid > 0)
1696                     nLogicalHigh = nMid - 1;
1697                 else
1698                     bDone = true;
1699             }
1700         }
1701         else if (nRes > 0)
1702         {
1703             if (bLessEqual)
1704             {
1705                 if (nMid > 0)
1706                     nLogicalHigh = nMid - 1;
1707                 else
1708                     bDone = true;
1709             }
1710             else // assumed to be SC_GREATER_EQUAL
1711                 nLogicalLow = nMid + 1;
1712         }
1713         else
1714         {
1715             aLoPos = aPos;
1716             bDone = bFound = true;
1717         }
1718     }
1719     if (!bFound)
1720     {
1721         // If all hits didn't result in a moving limit there's something
1722         // strange, e.g. data range not properly sorted, or only identical
1723         // values encountered, which doesn't mean there aren't any others in
1724         // between.. leave it to GetThis(). The condition for this would be
1725         // if (nLastInRange == nFirstLastInRange) nLo = nFirstLastInRange;
1726         // Else, in case no exact match was found, we step back for a
1727         // subsequent GetThis() to find the last in range. Effectively this is
1728         // --nLo with nLastInRange == nLo-1. Both conditions combined yield:
1729         aLoPos = aLastInRange;
1730     }
1731
1732     if (aLoPos.first != pCol->maCells.end() && toLogicalPos(aLoPos) <= static_cast<size_t>(mpParam->nRow2))
1733     {
1734         nRow = toLogicalPos(aLoPos);
1735         maCurPos = aLoPos;
1736         return true;
1737     }
1738     else
1739     {
1740         nRow = mpParam->nRow2 + 1;
1741         // Set current position to the last possible row.
1742         maCurPos.first = pCol->maCells.end();
1743         --maCurPos.first;
1744         maCurPos.second = maCurPos.first->size - 1;
1745         return false;
1746     }
1747 }
1748
1749
1750 //-------------------------------------------------------------------------------
1751
1752 ScHorizontalCellIterator::ScHorizontalCellIterator(ScDocument* pDocument, SCTAB nTable,
1753                                     SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 ) :
1754     maColPositions(nCol2-nCol1+1),
1755     pDoc( pDocument ),
1756     mnTab( nTable ),
1757     nStartCol( nCol1 ),
1758     nEndCol( nCol2 ),
1759     nStartRow( nRow1 ),
1760     nEndRow( nRow2 ),
1761     mnCol( nCol1 ),
1762     mnRow( nRow1 ),
1763     bMore(false)
1764 {
1765     if (mnTab >= pDoc->GetTableCount())
1766         OSL_FAIL("try to access index out of bounds, FIX IT");
1767
1768     pNextRows = new SCROW[ nCol2-nCol1+1 ];
1769     pNextIndices = new SCSIZE[ nCol2-nCol1+1 ];
1770
1771     SetTab( mnTab );
1772 }
1773
1774 ScHorizontalCellIterator::~ScHorizontalCellIterator()
1775 {
1776     delete [] pNextRows;
1777     delete [] pNextIndices;
1778 }
1779
1780 void ScHorizontalCellIterator::SetTab( SCTAB nTabP )
1781 {
1782     bMore = false;
1783     mnTab = nTabP;
1784     mnRow = nStartRow;
1785     mnCol = nStartCol;
1786
1787     // Set the start position in each column.
1788     for (SCCOL i = nStartCol; i <= nEndCol; ++i)
1789     {
1790         ScColumn* pCol = &pDoc->maTabs[mnTab]->aCol[i];
1791         ColParam& rParam = maColPositions[i-nStartCol];
1792         rParam.maPos = pCol->maCells.position(nStartRow).first;
1793         rParam.maEnd = pCol->maCells.end();
1794         if (rParam.maPos != rParam.maEnd)
1795             bMore = true;
1796     }
1797
1798     if (!bMore)
1799         return;
1800
1801     ColParam& rParam = maColPositions[0];
1802     if (rParam.maPos == rParam.maEnd || rParam.maPos->type == sc::element_type_empty)
1803         // Skip to the first non-empty cell.
1804         Advance();
1805 }
1806
1807 ScRefCellValue* ScHorizontalCellIterator::GetNext( SCCOL& rCol, SCROW& rRow )
1808 {
1809     if (!bMore)
1810         return NULL;
1811
1812     // Return the current non-empty cell, and move the cursor to the next one.
1813     rCol = mnCol;
1814     rRow = mnRow;
1815
1816     ColParam& r = maColPositions[mnCol-nStartCol];
1817     size_t nOffset = static_cast<size_t>(mnRow) - r.maPos->position;
1818     maCurCell = sc::toRefCell(r.maPos, nOffset);
1819     Advance();
1820
1821     return &maCurCell;
1822 }
1823
1824 bool ScHorizontalCellIterator::GetPos( SCCOL& rCol, SCROW& rRow )
1825 {
1826     rCol = mnCol;
1827     rRow = mnRow;
1828     return bMore;
1829 }
1830
1831 namespace {
1832
1833 bool advanceBlock(size_t nRow, sc::CellStoreType::const_iterator& rPos, const sc::CellStoreType::const_iterator& rEnd)
1834 {
1835     if (nRow < rPos->position + rPos->size)
1836         // Block already contains the specified row. Nothing to do.
1837         return true;
1838
1839     // This block is behind the current row position. Advance the block.
1840     for (++rPos; rPos != rEnd; ++rPos)
1841     {
1842         if (nRow < rPos->position + rPos->size)
1843             // Found the block that contains the specified row.
1844             return true;
1845     }
1846
1847     // No more blocks.
1848     return false;
1849 }
1850
1851 }
1852
1853 void ScHorizontalCellIterator::Advance()
1854 {
1855     // Find the next non-empty cell in the current row.
1856     for (SCCOL i = mnCol+1; i <= nEndCol; ++i)
1857     {
1858         ColParam& r = maColPositions[i-nStartCol];
1859         if (r.maPos == r.maEnd)
1860             continue;
1861
1862         size_t nRow = static_cast<size_t>(mnRow);
1863         if (nRow < r.maPos->position)
1864             continue;
1865
1866         if (!advanceBlock(nRow, r.maPos, r.maEnd))
1867             continue;
1868
1869         if (r.maPos->type == sc::element_type_empty)
1870             continue;
1871
1872         // Found in the current row.
1873         mnCol = i;
1874         bMore = true;
1875         return;
1876     }
1877
1878     // Move to the next row that has at least one non-empty cell.
1879     ++mnRow;
1880     while (mnRow <= nEndRow)
1881     {
1882         size_t nRow = static_cast<size_t>(mnRow);
1883         size_t nNextRow = MAXROW+1;
1884         size_t nNextRowPos = 0;
1885         for (size_t i = nNextRowPos, n = maColPositions.size(); i < n; ++i)
1886         {
1887             ColParam& r = maColPositions[i];
1888             if (r.maPos == r.maEnd)
1889                 // This column has ended.
1890                 continue;
1891
1892             if (nRow < r.maPos->position)
1893             {
1894                 // This block is ahread of the current row position. Skip it.
1895                 if (r.maPos->position < nNextRow)
1896                 {
1897                     nNextRow = r.maPos->position;
1898                     nNextRowPos = i;
1899                 }
1900                 continue;
1901             }
1902
1903             if (!advanceBlock(nRow, r.maPos, r.maEnd))
1904                 continue;
1905
1906             if (r.maPos->type == sc::element_type_empty)
1907             {
1908                 // Empty block. Move to the next block and try next column.
1909                 ++r.maPos;
1910                 if (r.maPos->position < nNextRow)
1911                 {
1912                     nNextRow = r.maPos->position;
1913                     nNextRowPos = i;
1914                 }
1915                 continue;
1916             }
1917
1918             // Found a non-empty cell block!
1919             mnCol = i + nStartCol;
1920             mnRow = nRow;
1921             bMore = true;
1922             return;
1923         }
1924
1925         if (nNextRow > static_cast<size_t>(MAXROW))
1926         {
1927             // No more blocks to search.
1928             bMore = false;
1929             return;
1930         }
1931
1932         mnRow = nNextRow; // move to the next non-empty row.
1933     }
1934
1935     bMore = false;
1936 }
1937
1938 //------------------------------------------------------------------------
1939
1940 ScHorizontalValueIterator::ScHorizontalValueIterator( ScDocument* pDocument,
1941         const ScRange& rRange, bool bSTotal, bool bTextZero ) :
1942     pDoc( pDocument ),
1943     nNumFmtIndex(0),
1944     nEndTab( rRange.aEnd.Tab() ),
1945     nNumFmtType( NUMBERFORMAT_UNDEFINED ),
1946     bNumValid( false ),
1947     bSubTotal( bSTotal ),
1948     bCalcAsShown( pDocument->GetDocOptions().IsCalcAsShown() ),
1949     bTextAsZero( bTextZero )
1950 {
1951     SCCOL nStartCol = rRange.aStart.Col();
1952     SCROW nStartRow = rRange.aStart.Row();
1953     SCTAB nStartTab = rRange.aStart.Tab();
1954     SCCOL nEndCol = rRange.aEnd.Col();
1955     SCROW nEndRow = rRange.aEnd.Row();
1956     PutInOrder( nStartCol, nEndCol);
1957     PutInOrder( nStartRow, nEndRow);
1958     PutInOrder( nStartTab, nEndTab );
1959
1960     if (!ValidCol(nStartCol)) nStartCol = MAXCOL;
1961     if (!ValidCol(nEndCol)) nEndCol = MAXCOL;
1962     if (!ValidRow(nStartRow)) nStartRow = MAXROW;
1963     if (!ValidRow(nEndRow)) nEndRow = MAXROW;
1964     if (!ValidTab(nStartTab)) nStartTab = MAXTAB;
1965     if (!ValidTab(nEndTab)) nEndTab = MAXTAB;
1966
1967     nCurCol = nStartCol;
1968     nCurRow = nStartRow;
1969     nCurTab = nStartTab;
1970
1971     nNumFormat = 0; // Will be initialized in GetNumberFormat()
1972     pAttrArray = 0;
1973     nAttrEndRow = 0;
1974
1975     pCellIter = new ScHorizontalCellIterator( pDoc, nStartTab, nStartCol,
1976             nStartRow, nEndCol, nEndRow );
1977 }
1978
1979 ScHorizontalValueIterator::~ScHorizontalValueIterator()
1980 {
1981     delete pCellIter;
1982 }
1983
1984 bool ScHorizontalValueIterator::GetNext( double& rValue, sal_uInt16& rErr )
1985 {
1986     bool bFound = false;
1987     while ( !bFound )
1988     {
1989         ScRefCellValue* pCell = pCellIter->GetNext( nCurCol, nCurRow );
1990         while ( !pCell )
1991         {
1992             if ( nCurTab < nEndTab )
1993             {
1994                 pCellIter->SetTab( ++nCurTab);
1995                 pCell = pCellIter->GetNext( nCurCol, nCurRow );
1996             }
1997             else
1998                 return false;
1999         }
2000         if ( !bSubTotal || !pDoc->maTabs[nCurTab]->RowFiltered( nCurRow ) )
2001         {
2002             switch (pCell->meType)
2003             {
2004                 case CELLTYPE_VALUE:
2005                     {
2006                         bNumValid = false;
2007                         rValue = pCell->mfValue;
2008                         rErr = 0;
2009                         if ( bCalcAsShown )
2010                         {
2011                             ScColumn* pCol = &pDoc->maTabs[nCurTab]->aCol[nCurCol];
2012                             ScAttrArray_IterGetNumberFormat( nNumFormat, pAttrArray,
2013                                     nAttrEndRow, pCol->pAttrArray, nCurRow, pDoc );
2014                             rValue = pDoc->RoundValueAsShown( rValue, nNumFormat );
2015                         }
2016                         bFound = true;
2017                     }
2018                     break;
2019                 case CELLTYPE_FORMULA:
2020                     {
2021                         if (!bSubTotal || !pCell->mpFormula->IsSubTotal())
2022                         {
2023                             rErr = pCell->mpFormula->GetErrCode();
2024                             if (rErr || pCell->mpFormula->IsValue())
2025                             {
2026                                 rValue = pCell->mpFormula->GetValue();
2027                                 bNumValid = false;
2028                                 bFound = true;
2029                             }
2030                             else if ( bTextAsZero )
2031                             {
2032                                 rValue = 0.0;
2033                                 bNumValid = false;
2034                                 bFound = true;
2035                             }
2036                         }
2037                     }
2038                     break;
2039                 case CELLTYPE_STRING :
2040                 case CELLTYPE_EDIT :
2041                     {
2042                         if ( bTextAsZero )
2043                         {
2044                             rErr = 0;
2045                             rValue = 0.0;
2046                             nNumFmtType = NUMBERFORMAT_NUMBER;
2047                             nNumFmtIndex = 0;
2048                             bNumValid = true;
2049                             bFound = true;
2050                         }
2051                     }
2052                     break;
2053                 default: ;   // nothing
2054             }
2055         }
2056     }
2057     return bFound;
2058 }
2059
2060 //-------------------------------------------------------------------------------
2061
2062 ScHorizontalAttrIterator::ScHorizontalAttrIterator( ScDocument* pDocument, SCTAB nTable,
2063                             SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 ) :
2064     pDoc( pDocument ),
2065     nTab( nTable ),
2066     nStartCol( nCol1 ),
2067     nStartRow( nRow1 ),
2068     nEndCol( nCol2 ),
2069     nEndRow( nRow2 )
2070 {
2071     if (nTab >= pDoc->GetTableCount())
2072         OSL_FAIL("try to access index out of bounds, FIX IT");
2073     OSL_ENSURE( pDoc->maTabs[nTab], "Table does not exist" );
2074
2075     SCCOL i;
2076
2077     nRow = nStartRow;
2078     nCol = nStartCol;
2079     bRowEmpty = false;
2080
2081     pIndices    = new SCSIZE[nEndCol-nStartCol+1];
2082     pNextEnd    = new SCROW[nEndCol-nStartCol+1];
2083     ppPatterns  = new const ScPatternAttr*[nEndCol-nStartCol+1];
2084
2085     SCROW nSkipTo = MAXROW;
2086     bool bEmpty = true;
2087     for (i=nStartCol; i<=nEndCol; i++)
2088     {
2089         SCCOL nPos = i - nStartCol;
2090         const ScAttrArray* pArray = pDoc->maTabs[nTab]->aCol[i].pAttrArray;
2091         OSL_ENSURE( pArray, "pArray == 0" );
2092
2093         SCSIZE nIndex;
2094         pArray->Search( nStartRow, nIndex );
2095
2096         const ScPatternAttr* pPattern = pArray->pData[nIndex].pPattern;
2097         SCROW nThisEnd = pArray->pData[nIndex].nRow;
2098         if ( IsDefaultItem( pPattern ) )
2099         {
2100             pPattern = NULL;
2101             if ( nThisEnd < nSkipTo )
2102                 nSkipTo = nThisEnd; // nSkipTo can be set here already
2103         }
2104         else
2105             bEmpty = false; // Found attributes
2106
2107         pIndices[nPos] = nIndex;
2108         pNextEnd[nPos] = nThisEnd;
2109         ppPatterns[nPos] = pPattern;
2110     }
2111
2112     if (bEmpty)
2113         nRow = nSkipTo; // Skip until end of next section
2114
2115     bRowEmpty = bEmpty;
2116 }
2117
2118 ScHorizontalAttrIterator::~ScHorizontalAttrIterator()
2119 {
2120     delete[] ppPatterns;
2121     delete[] pNextEnd;
2122     delete[] pIndices;
2123 }
2124
2125 const ScPatternAttr* ScHorizontalAttrIterator::GetNext( SCCOL& rCol1, SCCOL& rCol2, SCROW& rRow )
2126 {
2127     if (nTab >= pDoc->GetTableCount())
2128         OSL_FAIL("try to access index out of bounds, FIX IT");
2129     for (;;)
2130     {
2131         if (!bRowEmpty)
2132         {
2133             // Search in this row
2134             while ( nCol <= nEndCol && !ppPatterns[nCol-nStartCol] )
2135                 ++nCol;
2136
2137             if ( nCol <= nEndCol )
2138             {
2139                 const ScPatternAttr* pPat = ppPatterns[nCol-nStartCol];
2140                 rRow = nRow;
2141                 rCol1 = nCol;
2142                 while ( nCol < nEndCol && ppPatterns[nCol+1-nStartCol] == pPat )
2143                     ++nCol;
2144                 rCol2 = nCol;
2145                 ++nCol; // Count up for next call
2146                 return pPat; // Found it!
2147             }
2148         }
2149
2150         // Next row
2151         ++nRow;
2152         if ( nRow > nEndRow ) // Already at the end?
2153             return NULL; // Found nothing
2154
2155         bool bEmpty = true;
2156         SCCOL i;
2157
2158         for ( i = nStartCol; i <= nEndCol; i++)
2159         {
2160             SCCOL nPos = i-nStartCol;
2161             if ( pNextEnd[nPos] < nRow )
2162             {
2163                 const ScAttrArray* pArray = pDoc->maTabs[nTab]->aCol[i].pAttrArray;
2164
2165                 SCSIZE nIndex = ++pIndices[nPos];
2166                 if ( nIndex < pArray->nCount )
2167                 {
2168                     const ScPatternAttr* pPattern = pArray->pData[nIndex].pPattern;
2169                     SCROW nThisEnd = pArray->pData[nIndex].nRow;
2170                     if ( IsDefaultItem( pPattern ) )
2171                         pPattern = NULL;
2172                     else
2173                         bEmpty = false; // Found attributes
2174
2175                     pNextEnd[nPos] = nThisEnd;
2176                     ppPatterns[nPos] = pPattern;
2177
2178                     OSL_ENSURE( pNextEnd[nPos] >= nRow, "Sequence out of order" );
2179                 }
2180                 else
2181                 {
2182                     OSL_FAIL("AttrArray does not range to MAXROW");
2183                     pNextEnd[nPos] = MAXROW;
2184                     ppPatterns[nPos] = NULL;
2185                 }
2186             }
2187             else if ( ppPatterns[nPos] )
2188                 bEmpty = false; // Area not at the end yet
2189         }
2190
2191         if (bEmpty)
2192         {
2193             SCCOL nCount = nEndCol-nStartCol+1;
2194             SCROW nSkipTo = pNextEnd[0]; // Search next end of area
2195             for (i=1; i<nCount; i++)
2196                 if ( pNextEnd[i] < nSkipTo )
2197                     nSkipTo = pNextEnd[i];
2198             nRow = nSkipTo; // Skip empty rows
2199         }
2200         bRowEmpty = bEmpty;
2201         nCol = nStartCol; // Start at the left again
2202     }
2203 }
2204
2205 //-------------------------------------------------------------------------------
2206
2207 inline bool IsGreater( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 )
2208 {
2209     return ( nRow1 > nRow2 ) || ( nRow1 == nRow2 && nCol1 > nCol2 );
2210 }
2211
2212 ScUsedAreaIterator::ScUsedAreaIterator( ScDocument* pDocument, SCTAB nTable,
2213                             SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 ) :
2214     aCellIter( pDocument, nTable, nCol1, nRow1, nCol2, nRow2 ),
2215     aAttrIter( pDocument, nTable, nCol1, nRow1, nCol2, nRow2 ),
2216     nNextCol( nCol1 ),
2217     nNextRow( nRow1 )
2218 {
2219     pCell    = aCellIter.GetNext( nCellCol, nCellRow );
2220     pPattern = aAttrIter.GetNext( nAttrCol1, nAttrCol2, nAttrRow );
2221 }
2222
2223 ScUsedAreaIterator::~ScUsedAreaIterator()
2224 {
2225 }
2226
2227 bool ScUsedAreaIterator::GetNext()
2228 {
2229     //  Forward iterators
2230     if ( pCell && IsGreater( nNextCol, nNextRow, nCellCol, nCellRow ) )
2231         pCell = aCellIter.GetNext( nCellCol, nCellRow );
2232
2233     while (pCell && pCell->isEmpty())
2234         pCell = aCellIter.GetNext( nCellCol, nCellRow );
2235
2236     if ( pPattern && IsGreater( nNextCol, nNextRow, nAttrCol2, nAttrRow ) )
2237         pPattern = aAttrIter.GetNext( nAttrCol1, nAttrCol2, nAttrRow );
2238
2239     if ( pPattern && nAttrRow == nNextRow && nAttrCol1 < nNextCol )
2240         nAttrCol1 = nNextCol;
2241
2242     // Find next area
2243     bool bFound = true;
2244     bool bUseCell = false;
2245
2246     if ( pCell && pPattern )
2247     {
2248         if ( IsGreater( nCellCol, nCellRow, nAttrCol1, nAttrRow ) ) // Only attributes at the beginning?
2249         {
2250             maFoundCell.clear();
2251             pFoundPattern = pPattern;
2252             nFoundRow = nAttrRow;
2253             nFoundStartCol = nAttrCol1;
2254             if ( nCellRow == nAttrRow && nCellCol <= nAttrCol2 ) // Area also contains cell?
2255                 nFoundEndCol = nCellCol - 1; // Only until right before the cell
2256             else
2257                 nFoundEndCol = nAttrCol2; // Everything
2258         }
2259         else
2260         {
2261             bUseCell = true;
2262             if ( nAttrRow == nCellRow && nAttrCol1 == nCellCol ) // Attributes on the cell?
2263                 pFoundPattern = pPattern;
2264             else
2265                 pFoundPattern = NULL;
2266         }
2267     }
2268     else if ( pCell ) // Just a cell -> take over right away
2269     {
2270         pFoundPattern = NULL;
2271         bUseCell = true; // Cell position
2272     }
2273     else if ( pPattern ) // Just attributes -> take over right away
2274     {
2275         maFoundCell.clear();
2276         pFoundPattern = pPattern;
2277         nFoundRow = nAttrRow;
2278         nFoundStartCol = nAttrCol1;
2279         nFoundEndCol = nAttrCol2;
2280     }
2281     else // Nothing
2282         bFound = false;
2283
2284     if ( bUseCell ) // Cell position
2285     {
2286         if (pCell)
2287             maFoundCell = *pCell;
2288         else
2289             maFoundCell.clear();
2290
2291         nFoundRow = nCellRow;
2292         nFoundStartCol = nFoundEndCol = nCellCol;
2293     }
2294
2295     if (bFound)
2296     {
2297         nNextRow = nFoundRow;
2298         nNextCol = nFoundEndCol + 1;
2299     }
2300
2301     return bFound;
2302 }
2303
2304 const ScRefCellValue& ScUsedAreaIterator::GetCell() const
2305 {
2306     return maFoundCell;
2307 }
2308
2309 //-------------------------------------------------------------------------------
2310
2311 ScDocAttrIterator::ScDocAttrIterator(ScDocument* pDocument, SCTAB nTable,
2312                                     SCCOL nCol1, SCROW nRow1,
2313                                     SCCOL nCol2, SCROW nRow2) :
2314     pDoc( pDocument ),
2315     nTab( nTable ),
2316     nEndCol( nCol2 ),
2317     nStartRow( nRow1 ),
2318     nEndRow( nRow2 ),
2319     nCol( nCol1 )
2320 {
2321     if ( ValidTab(nTab) && nTab < pDoc->GetTableCount() && pDoc->maTabs[nTab] )
2322         pColIter = pDoc->maTabs[nTab]->aCol[nCol].CreateAttrIterator( nStartRow, nEndRow );
2323     else
2324         pColIter = NULL;
2325 }
2326
2327 ScDocAttrIterator::~ScDocAttrIterator()
2328 {
2329     delete pColIter;
2330 }
2331
2332 const ScPatternAttr* ScDocAttrIterator::GetNext( SCCOL& rCol, SCROW& rRow1, SCROW& rRow2 )
2333 {
2334     while ( pColIter )
2335     {
2336         const ScPatternAttr* pPattern = pColIter->Next( rRow1, rRow2 );
2337         if ( pPattern )
2338         {
2339             rCol = nCol;
2340             return pPattern;
2341         }
2342
2343         delete pColIter;
2344         ++nCol;
2345         if ( nCol <= nEndCol )
2346             pColIter = pDoc->maTabs[nTab]->aCol[nCol].CreateAttrIterator( nStartRow, nEndRow );
2347         else
2348             pColIter = NULL;
2349     }
2350     return NULL;  // Nothing anymore
2351 }
2352
2353 // ============================================================================
2354
2355 ScDocRowHeightUpdater::TabRanges::TabRanges(SCTAB nTab) :
2356     mnTab(nTab), mpRanges(new ScFlatBoolRowSegments)
2357 {
2358 }
2359
2360 ScDocRowHeightUpdater::ScDocRowHeightUpdater(ScDocument& rDoc, OutputDevice* pOutDev, double fPPTX, double fPPTY, const vector<TabRanges>* pTabRangesArray) :
2361     mrDoc(rDoc), mpOutDev(pOutDev), mfPPTX(fPPTX), mfPPTY(fPPTY), mpTabRangesArray(pTabRangesArray)
2362 {
2363 }
2364
2365 void ScDocRowHeightUpdater::update()
2366 {
2367     if (!mpTabRangesArray || mpTabRangesArray->empty())
2368     {
2369         // No ranges defined. Update all rows in all tables.
2370         updateAll();
2371         return;
2372     }
2373
2374     sal_uInt32 nCellCount = 0;
2375     vector<TabRanges>::const_iterator itr = mpTabRangesArray->begin(), itrEnd = mpTabRangesArray->end();
2376     for (; itr != itrEnd; ++itr)
2377     {
2378         ScFlatBoolRowSegments::RangeData aData;
2379         ScFlatBoolRowSegments::RangeIterator aRangeItr(*itr->mpRanges);
2380         for (bool bFound = aRangeItr.getFirst(aData); bFound; bFound = aRangeItr.getNext(aData))
2381         {
2382             if (!aData.mbValue)
2383                 continue;
2384
2385             nCellCount += aData.mnRow2 - aData.mnRow1 + 1;
2386         }
2387     }
2388
2389     ScProgress aProgress(mrDoc.GetDocumentShell(), ScGlobal::GetRscString(STR_PROGRESS_HEIGHTING), nCellCount);
2390
2391     Fraction aZoom(1, 1);
2392     itr = mpTabRangesArray->begin();
2393     sal_uInt32 nProgressStart = 0;
2394     for (; itr != itrEnd; ++itr)
2395     {
2396         SCTAB nTab = itr->mnTab;
2397         if (!ValidTab(nTab) || nTab >= mrDoc.GetTableCount() || !mrDoc.maTabs[nTab])
2398             continue;
2399
2400         ScFlatBoolRowSegments::RangeData aData;
2401         ScFlatBoolRowSegments::RangeIterator aRangeItr(*itr->mpRanges);
2402         for (bool bFound = aRangeItr.getFirst(aData); bFound; bFound = aRangeItr.getNext(aData))
2403         {
2404             if (!aData.mbValue)
2405                 continue;
2406
2407             mrDoc.maTabs[nTab]->SetOptimalHeight(
2408                 aData.mnRow1, aData.mnRow2, 0, mpOutDev, mfPPTX, mfPPTY, aZoom, aZoom, false, &aProgress, nProgressStart);
2409
2410             nProgressStart += aData.mnRow2 - aData.mnRow1 + 1;
2411         }
2412     }
2413 }
2414
2415 void ScDocRowHeightUpdater::updateAll()
2416 {
2417     sal_uInt32 nCellCount = 0;
2418     for (SCTAB nTab = 0; nTab < mrDoc.GetTableCount(); ++nTab)
2419     {
2420         if (!ValidTab(nTab) || !mrDoc.maTabs[nTab])
2421             continue;
2422
2423         nCellCount += mrDoc.maTabs[nTab]->GetWeightedCount();
2424     }
2425
2426     ScProgress aProgress(mrDoc.GetDocumentShell(), ScGlobal::GetRscString(STR_PROGRESS_HEIGHTING), nCellCount);
2427
2428     Fraction aZoom(1, 1);
2429     sal_uLong nProgressStart = 0;
2430     for (SCTAB nTab = 0; nTab < mrDoc.GetTableCount(); ++nTab)
2431     {
2432         if (!ValidTab(nTab) || !mrDoc.maTabs[nTab])
2433             continue;
2434
2435         mrDoc.maTabs[nTab]->SetOptimalHeight(
2436             0, MAXROW, 0, mpOutDev, mfPPTX, mfPPTY, aZoom, aZoom, false, &aProgress, nProgressStart);
2437
2438         nProgressStart += mrDoc.maTabs[nTab]->GetWeightedCount();
2439     }
2440 }
2441
2442 //-------------------------------------------------------------------------------
2443
2444 ScAttrRectIterator::ScAttrRectIterator(ScDocument* pDocument, SCTAB nTable,
2445                                     SCCOL nCol1, SCROW nRow1,
2446                                     SCCOL nCol2, SCROW nRow2) :
2447     pDoc( pDocument ),
2448     nTab( nTable ),
2449     nEndCol( nCol2 ),
2450     nStartRow( nRow1 ),
2451     nEndRow( nRow2 ),
2452     nIterStartCol( nCol1 ),
2453     nIterEndCol( nCol1 )
2454 {
2455     if ( ValidTab(nTab) && nTab < pDoc->GetTableCount() && pDoc->maTabs[nTab] )
2456     {
2457         pColIter = pDoc->maTabs[nTab]->aCol[nIterStartCol].CreateAttrIterator( nStartRow, nEndRow );
2458         while ( nIterEndCol < nEndCol &&
2459                 pDoc->maTabs[nTab]->aCol[nIterEndCol].IsAllAttrEqual(
2460                     pDoc->maTabs[nTab]->aCol[nIterEndCol+1], nStartRow, nEndRow ) )
2461             ++nIterEndCol;
2462     }
2463     else
2464         pColIter = NULL;
2465 }
2466
2467 ScAttrRectIterator::~ScAttrRectIterator()
2468 {
2469     delete pColIter;
2470 }
2471
2472 void ScAttrRectIterator::DataChanged()
2473 {
2474     if (pColIter)
2475     {
2476         SCROW nNextRow = pColIter->GetNextRow();
2477         delete pColIter;
2478         pColIter = pDoc->maTabs[nTab]->aCol[nIterStartCol].CreateAttrIterator( nNextRow, nEndRow );
2479     }
2480 }
2481
2482 const ScPatternAttr* ScAttrRectIterator::GetNext( SCCOL& rCol1, SCCOL& rCol2,
2483                                                     SCROW& rRow1, SCROW& rRow2 )
2484 {
2485     while ( pColIter )
2486     {
2487         const ScPatternAttr* pPattern = pColIter->Next( rRow1, rRow2 );
2488         if ( pPattern )
2489         {
2490             rCol1 = nIterStartCol;
2491             rCol2 = nIterEndCol;
2492             return pPattern;
2493         }
2494
2495         delete pColIter;
2496         nIterStartCol = nIterEndCol+1;
2497         if ( nIterStartCol <= nEndCol )
2498         {
2499             nIterEndCol = nIterStartCol;
2500             pColIter = pDoc->maTabs[nTab]->aCol[nIterStartCol].CreateAttrIterator( nStartRow, nEndRow );
2501             while ( nIterEndCol < nEndCol &&
2502                     pDoc->maTabs[nTab]->aCol[nIterEndCol].IsAllAttrEqual(
2503                         pDoc->maTabs[nTab]->aCol[nIterEndCol+1], nStartRow, nEndRow ) )
2504                 ++nIterEndCol;
2505         }
2506         else
2507             pColIter = NULL;
2508     }
2509     return NULL; // Nothing anymore
2510 }
2511
2512 // ============================================================================
2513
2514 SCROW ScRowBreakIterator::NOT_FOUND = -1;
2515
2516 ScRowBreakIterator::ScRowBreakIterator(set<SCROW>& rBreaks) :
2517     mrBreaks(rBreaks),
2518     maItr(rBreaks.begin()), maEnd(rBreaks.end())
2519 {
2520 }
2521
2522 SCROW ScRowBreakIterator::first()
2523 {
2524     maItr = mrBreaks.begin();
2525     return maItr == maEnd ? NOT_FOUND : *maItr;
2526 }
2527
2528 SCROW ScRowBreakIterator::next()
2529 {
2530     ++maItr;
2531     return maItr == maEnd ? NOT_FOUND : *maItr;
2532 }
2533
2534 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */