sc/source/core/data/segmenttree.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 <segmenttree.hxx>
  21 #include <o3tl/safeint.hxx>
  22 #include <mdds/flat_segment_tree.hpp>
  23 #include <sal/log.hxx>
  24 #include <algorithm>
  25 #include <limits>
  26 #include <string_view>
  27 #include <global.hxx>
  28 #include <rtl/strbuf.hxx>
  29
  30 using ::std::numeric_limits;
  31
  32 namespace {
  33
  34 template<typename ValueType_, typename ExtValueType_ = ValueType_>
  35 class ScFlatSegmentsImpl
  36 {
  37 public:
  38     typedef ValueType_ ValueType;
  39     typedef ExtValueType_ ExtValueType;
  40
  41     struct RangeData
  42     {
  43         SCCOLROW    mnPos1;
  44         SCCOLROW    mnPos2;
  45         ValueType   mnValue;
  46     };
  47
  48     ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault);
  49     ScFlatSegmentsImpl(const ScFlatSegmentsImpl& r);
  50
  51     bool setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
  52     void setValueIf(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue, const std::function<bool(ValueType)>& rPredicate);
  53     ValueType getValue(SCCOLROW nPos);
  54     sal_uInt64 getSumValue(SCCOLROW nPos1, SCCOLROW nPos2);
  55     bool getRangeData(SCCOLROW nPos, RangeData& rData);
  56     bool getRangeDataLeaf(SCCOLROW nPos, RangeData& rData);
  57     void removeSegment(SCCOLROW nPos1, SCCOLROW nPos2);
  58     void insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary);
  59
  60     SCCOLROW findLastTrue(ValueType nValue) const;
  61
  62     // range iteration
  63     bool getFirst(RangeData& rData);
  64     bool getNext(RangeData& rData);
  65
  66     void enableTreeSearch(bool b)
  67     {
  68         mbTreeSearchEnabled = b;
  69     }
  70
  71     void makeReady();
  72
  73 private:
  74     typedef ::mdds::flat_segment_tree<SCCOLROW, ValueType> fst_type;
  75     fst_type maSegments;
  76     typename fst_type::const_iterator maItr;
  77
  78     bool mbTreeSearchEnabled:1;
  79 };
  80
  81 }
  82
  83 template<typename ValueType_, typename ExtValueType_>
  84 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault) :
  85     maSegments(0, nMax+1, nDefault),
  86     mbTreeSearchEnabled(true)
  87 {
  88 }
  89
  90 template<typename ValueType_, typename ExtValueType_>
  91 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(const ScFlatSegmentsImpl<ValueType_, ExtValueType_>& r) :
  92     maSegments(r.maSegments),
  93     mbTreeSearchEnabled(r.mbTreeSearchEnabled)
  94 {
  95 }
  96
  97 template<typename ValueType_, typename ExtValueType_>
  98 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue)
  99 {
 100     ::std::pair<typename fst_type::const_iterator, bool> ret;
 101     ret = maSegments.insert(maItr, nPos1, nPos2+1, nValue);
 102     maItr = ret.first;
 103     return ret.second;
 104 }
 105
 106 template<typename ValueType_, typename ExtValueType_>
 107 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValueIf(SCCOLROW nPos1, SCCOLROW nPos2,
 108         ValueType nValue, const std::function<bool(ValueType)>& rPredicate)
 109 {
 110     SCCOLROW nCurrentStartRow = nPos1;
 111     while (nCurrentStartRow <= nPos2)
 112     {
 113         RangeData aRangeData;
 114         getRangeData(nCurrentStartRow, aRangeData);
 115         if (rPredicate(aRangeData.mnValue))
 116         {
 117             // set value from current iteration point on, til end of range.
 118             // Note that aRangeData may well contain much lower values for nPos1
 119             setValue(nCurrentStartRow, std::min<SCCOLROW>(nPos2, aRangeData.mnPos2), nValue);
 120         }
 121
 122         // even if nPos2 is bigger than nPos2 this should terminate the loop
 123         nCurrentStartRow = aRangeData.mnPos2 + 1;
 124     }
 125 }
 126
 127 template<typename ValueType_, typename ExtValueType_>
 128 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ValueType ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getValue(SCCOLROW nPos)
 129 {
 130     ValueType nValue = 0;
 131     if (!mbTreeSearchEnabled)
 132     {
 133         maSegments.search(nPos, nValue);
 134         return nValue;
 135     }
 136
 137     if (!maSegments.is_tree_valid())
 138     {
 139         assert(!ScGlobal::bThreadedGroupCalcInProgress);
 140         maSegments.build_tree();
 141     }
 142
 143     maSegments.search_tree(nPos, nValue);
 144     return nValue;
 145 }
 146
 147 template<typename ValueType_, typename ExtValueType_>
 148 sal_uInt64 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getSumValue(SCCOLROW nPos1, SCCOLROW nPos2)
 149 {
 150     if (mbTreeSearchEnabled)
 151     {
 152
 153         if (!maSegments.is_tree_valid())
 154         {
 155             assert(!ScGlobal::bThreadedGroupCalcInProgress);
 156             maSegments.build_tree();
 157         }
 158
 159         RangeData aData;
 160         auto [it, found] = maSegments.search_tree(nPos1, aData.mnValue, &aData.mnPos1, &aData.mnPos2);
 161         if (!found)
 162             return 0;
 163         aData.mnPos2 = aData.mnPos2-1; // end point is not inclusive.
 164
 165         sal_uInt64 nValue = 0;
 166
 167         SCROW nCurPos = nPos1;
 168         SCROW nEndPos = aData.mnPos2;
 169         while (nEndPos <= nPos2)
 170         {
 171             sal_uInt64 nRes;
 172             if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
 173             {
 174                 SAL_WARN("sc.core", "row height overflow");
 175                 nRes = SAL_MAX_INT64;
 176             }
 177             nValue = o3tl::saturating_add(nValue, nRes);
 178             nCurPos = nEndPos + 1;
 179             auto itPair = maSegments.search(it, nCurPos, aData.mnValue, &aData.mnPos1, &aData.mnPos2);
 180             if (!itPair.second)
 181                 break;
 182             it = itPair.first;
 183             aData.mnPos2 = aData.mnPos2-1; // end point is not inclusive.
 184             nEndPos = aData.mnPos2;
 185         }
 186         if (nCurPos <= nPos2)
 187         {
 188             nEndPos = ::std::min(nEndPos, nPos2);
 189             sal_uInt64 nRes;
 190             if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
 191             {
 192                 SAL_WARN("sc.core", "row height overflow");
 193                 nRes = SAL_MAX_INT64;
 194             }
 195             nValue = o3tl::saturating_add(nValue, nRes);
 196         }
 197         return nValue;
 198     }
 199     else
 200     {
 201         RangeData aData;
 202         if (!getRangeDataLeaf(nPos1, aData))
 203             return 0;
 204
 205         sal_uInt64 nValue = 0;
 206
 207         SCROW nCurPos = nPos1;
 208         SCROW nEndPos = aData.mnPos2;
 209         while (nEndPos <= nPos2)
 210         {
 211             sal_uInt64 nRes;
 212             if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
 213             {
 214                 SAL_WARN("sc.core", "row height overflow");
 215                 nRes = SAL_MAX_INT64;
 216             }
 217             nValue = o3tl::saturating_add(nValue, nRes);
 218             nCurPos = nEndPos + 1;
 219             if (!getRangeDataLeaf(nCurPos, aData))
 220                 break;
 221
 222             nEndPos = aData.mnPos2;
 223         }
 224         if (nCurPos <= nPos2)
 225         {
 226             nEndPos = ::std::min(nEndPos, nPos2);
 227             sal_uInt64 nRes;
 228             if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
 229             {
 230                 SAL_WARN("sc.core", "row height overflow");
 231                 nRes = SAL_MAX_INT64;
 232             }
 233             nValue = o3tl::saturating_add(nValue, nRes);
 234         }
 235         return nValue;
 236     }
 237 }
 238
 239 template<typename ValueType_, typename ExtValueType_>
 240 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeData(SCCOLROW nPos, RangeData& rData)
 241 {
 242     if (!mbTreeSearchEnabled)
 243         return getRangeDataLeaf(nPos, rData);
 244
 245     if (!maSegments.is_tree_valid())
 246     {
 247         assert(!ScGlobal::bThreadedGroupCalcInProgress);
 248         maSegments.build_tree();
 249     }
 250
 251     auto [it,found] = maSegments.search_tree(nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
 252     if (!found)
 253         return false;
 254     maItr = std::move(it); // cache the iterator to speed up ForwardIterator.
 255     rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
 256     return true;
 257 }
 258
 259 template<typename ValueType_, typename ExtValueType_>
 260 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeDataLeaf(SCCOLROW nPos, RangeData& rData)
 261 {
 262     // Conduct leaf-node only search.  Faster when searching between range insertion.
 263     const ::std::pair<typename fst_type::const_iterator, bool> &ret =
 264         maSegments.search(maItr, nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
 265
 266     if (!ret.second)
 267         return false;
 268
 269     maItr = ret.first;
 270
 271     rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
 272     return true;
 273 }
 274
 275 template<typename ValueType_, typename ExtValueType_>
 276 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::removeSegment(SCCOLROW nPos1, SCCOLROW nPos2)
 277 {
 278     maSegments.shift_left(nPos1, nPos2);
 279     maItr = maSegments.begin();
 280 }
 281
 282 template<typename ValueType_, typename ExtValueType_>
 283 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary)
 284 {
 285     maSegments.shift_right(nPos, nSize, bSkipStartBoundary);
 286     maItr = maSegments.begin();
 287 }
 288
 289 template<typename ValueType_, typename ExtValueType_>
 290 SCCOLROW ScFlatSegmentsImpl<ValueType_, ExtValueType_>::findLastTrue(ValueType nValue) const
 291 {
 292     SCCOLROW nPos = numeric_limits<SCCOLROW>::max(); // position not found.
 293     typename fst_type::const_reverse_iterator itr = maSegments.rbegin(), itrEnd = maSegments.rend();
 294     // Note that when searching in reverse direction, we need to skip the first
 295     // node, since the right-most leaf node does not store a valid value.
 296     for (++itr; itr != itrEnd; ++itr)
 297     {
 298         if (itr->second != nValue)
 299         {
 300             nPos = (--itr)->first - 1;
 301             break;
 302         }
 303     }
 304     return nPos;
 305 }
 306
 307 template<typename ValueType_, typename ExtValueType_>
 308 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getFirst(RangeData& rData)
 309 {
 310     maItr = maSegments.begin();
 311     return getNext(rData);
 312 }
 313
 314 template<typename ValueType_, typename ExtValueType_>
 315 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getNext(RangeData& rData)
 316 {
 317     typename fst_type::const_iterator itrEnd = maSegments.end();
 318     if (maItr == itrEnd)
 319         return false;
 320
 321     rData.mnPos1 = maItr->first;
 322     rData.mnValue = maItr->second;
 323
 324     ++maItr;
 325     if (maItr == itrEnd)
 326         return false;
 327
 328     rData.mnPos2 = maItr->first - 1;
 329     return true;
 330 }
 331
 332 template<typename ValueType_, typename ExtValueType_>
 333 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::makeReady()
 334 {
 335     assert(!ScGlobal::bThreadedGroupCalcInProgress);
 336     if (!maSegments.is_tree_valid())
 337         maSegments.build_tree();
 338 }
 339
 340 class ScFlatUInt16SegmentsImpl : public ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>
 341 {
 342 public:
 343     explicit ScFlatUInt16SegmentsImpl(SCCOLROW nMax, sal_uInt16 nDefault) :
 344         ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>(nMax, nDefault)
 345     {
 346     }
 347 };
 348
 349 class ScFlatBoolSegmentsImpl : public ScFlatSegmentsImpl<bool>
 350 {
 351 public:
 352     explicit ScFlatBoolSegmentsImpl(SCCOLROW nMax) :
 353         ScFlatSegmentsImpl<bool>(nMax, false)
 354     {
 355     }
 356
 357     bool setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
 358     bool setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
 359 };
 360
 361 bool ScFlatBoolSegmentsImpl::setTrue(SCCOLROW nPos1, SCCOLROW nPos2)
 362 {
 363     return setValue(nPos1, nPos2, true);
 364 }
 365
 366 bool ScFlatBoolSegmentsImpl::setFalse(SCCOLROW nPos1, SCCOLROW nPos2)
 367 {
 368     return setValue(nPos1, nPos2, false);
 369 }
 370
 371 ScFlatBoolRowSegments::ForwardIterator::ForwardIterator(ScFlatBoolRowSegments& rSegs) :
 372     mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mbCurValue(false)
 373 {
 374 }
 375
 376 bool ScFlatBoolRowSegments::ForwardIterator::getValue(SCROW nPos, bool& rVal)
 377 {
 378     if (nPos >= mnCurPos)
 379         // It can only go in a forward direction.
 380         mnCurPos = nPos;
 381
 382     if (mnCurPos > mnLastPos)
 383     {
 384         // position not in the current segment.  Update the current value.
 385         ScFlatBoolRowSegments::RangeData aData;
 386         if (!mrSegs.getRangeData(mnCurPos, aData))
 387             return false;
 388
 389         mbCurValue = aData.mbValue;
 390         mnLastPos = aData.mnRow2;
 391     }
 392
 393     rVal = mbCurValue;
 394     return true;
 395 }
 396
 397 ScFlatBoolRowSegments::RangeIterator::RangeIterator(ScFlatBoolRowSegments const & rSegs) :
 398     mrSegs(rSegs)
 399 {
 400 }
 401
 402 bool ScFlatBoolRowSegments::RangeIterator::getFirst(RangeData& rRange)
 403 {
 404     ScFlatBoolSegmentsImpl::RangeData aData;
 405     if (!mrSegs.mpImpl->getFirst(aData))
 406         return false;
 407
 408     rRange.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 409     rRange.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 410     rRange.mbValue = static_cast<bool>(aData.mnValue);
 411     return true;
 412 }
 413
 414 bool ScFlatBoolRowSegments::RangeIterator::getNext(RangeData& rRange)
 415 {
 416     ScFlatBoolSegmentsImpl::RangeData aData;
 417     if (!mrSegs.mpImpl->getNext(aData))
 418         return false;
 419
 420     rRange.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 421     rRange.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 422     rRange.mbValue = static_cast<bool>(aData.mnValue);
 423     return true;
 424 }
 425
 426 ScFlatBoolRowSegments::ScFlatBoolRowSegments(SCROW nMaxRow) :
 427     mpImpl(new ScFlatBoolSegmentsImpl(nMaxRow))
 428 {
 429 }
 430
 431 ScFlatBoolRowSegments::ScFlatBoolRowSegments(const ScFlatBoolRowSegments& r) :
 432     mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
 433 {
 434 }
 435
 436 ScFlatBoolRowSegments::~ScFlatBoolRowSegments()
 437 {
 438 }
 439
 440 bool ScFlatBoolRowSegments::setTrue(SCROW nRow1, SCROW nRow2)
 441 {
 442     return mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 443 }
 444
 445 bool ScFlatBoolRowSegments::setFalse(SCROW nRow1, SCROW nRow2)
 446 {
 447     return mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 448 }
 449
 450 bool ScFlatBoolRowSegments::getRangeData(SCROW nRow, RangeData& rData) const
 451 {
 452     ScFlatBoolSegmentsImpl::RangeData aData;
 453     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
 454         return false;
 455
 456     rData.mbValue = aData.mnValue;
 457     rData.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 458     rData.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 459     return true;
 460 }
 461
 462 bool ScFlatBoolRowSegments::getRangeDataLeaf(SCROW nRow, RangeData& rData)
 463 {
 464     ScFlatBoolSegmentsImpl::RangeData aData;
 465     if (!mpImpl->getRangeDataLeaf(static_cast<SCCOLROW>(nRow), aData))
 466         return false;
 467
 468     rData.mbValue = aData.mnValue;
 469     rData.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 470     rData.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 471     return true;
 472 }
 473
 474 void ScFlatBoolRowSegments::removeSegment(SCROW nRow1, SCROW nRow2)
 475 {
 476     mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 477 }
 478
 479 void ScFlatBoolRowSegments::insertSegment(SCROW nRow, SCROW nSize)
 480 {
 481     mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), true/*bSkipStartBoundary*/);
 482 }
 483
 484 SCROW ScFlatBoolRowSegments::findLastTrue() const
 485 {
 486     return mpImpl->findLastTrue(false);
 487 }
 488
 489 void ScFlatBoolRowSegments::makeReady()
 490 {
 491     mpImpl->makeReady();
 492 }
 493
 494 OString ScFlatBoolRowSegments::dumpAsString()
 495 {
 496     OStringBuffer aOutput(4096);
 497     RangeData aRange;
 498     SCROW nRow = 0;
 499     while (getRangeData(nRow, aRange))
 500     {
 501         if (!nRow)
 502             aOutput.append(aRange.mbValue ? '1' : '0').append(':');
 503
 504         aOutput.append(OString::number(aRange.mnRow2) + " ");
 505         nRow = aRange.mnRow2 + 1;
 506     }
 507
 508     return aOutput.makeStringAndClear();
 509 }
 510
 511 ScFlatBoolColSegments::ScFlatBoolColSegments(SCCOL nMaxCol) :
 512     mpImpl(new ScFlatBoolSegmentsImpl(nMaxCol))
 513 {
 514 }
 515
 516 ScFlatBoolColSegments::ScFlatBoolColSegments(const ScFlatBoolColSegments& r) :
 517     mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
 518 {
 519 }
 520
 521 ScFlatBoolColSegments::~ScFlatBoolColSegments()
 522 {
 523 }
 524
 525 bool ScFlatBoolColSegments::setTrue(SCCOL nCol1, SCCOL nCol2)
 526 {
 527     return mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 528 }
 529
 530 bool ScFlatBoolColSegments::setFalse(SCCOL nCol1, SCCOL nCol2)
 531 {
 532     return mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 533 }
 534
 535 bool ScFlatBoolColSegments::getRangeData(SCCOL nCol, RangeData& rData)
 536 {
 537     ScFlatBoolSegmentsImpl::RangeData aData;
 538     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nCol), aData))
 539         return false;
 540
 541     rData.mbValue = aData.mnValue;
 542     rData.mnCol1  = static_cast<SCCOL>(aData.mnPos1);
 543     rData.mnCol2  = static_cast<SCCOL>(aData.mnPos2);
 544     return true;
 545 }
 546
 547 void ScFlatBoolColSegments::removeSegment(SCCOL nCol1, SCCOL nCol2)
 548 {
 549     mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 550 }
 551
 552 void ScFlatBoolColSegments::insertSegment(SCCOL nCol, SCCOL nSize)
 553 {
 554     mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize), true/*bSkipStartBoundary*/);
 555 }
 556
 557 void ScFlatBoolColSegments::makeReady()
 558 {
 559     mpImpl->makeReady();
 560 }
 561
 562 OString ScFlatBoolColSegments::dumpAsString()
 563 {
 564     OStringBuffer aOutput(4096);
 565     RangeData aRange;
 566     SCCOL nCol = 0;
 567     while (getRangeData(nCol, aRange))
 568     {
 569         if (!nCol)
 570             aOutput.append(aRange.mbValue ? '1' : '0').append(':');
 571
 572         aOutput.append(OString::number(aRange.mnCol2) + " ");
 573         nCol = aRange.mnCol2 + 1;
 574     }
 575
 576     return aOutput.makeStringAndClear();
 577 }
 578
 579 ScFlatUInt16RowSegments::ForwardIterator::ForwardIterator(ScFlatUInt16RowSegments& rSegs) :
 580     mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mnCurValue(0)
 581 {
 582 }
 583
 584 bool ScFlatUInt16RowSegments::ForwardIterator::getValue(SCROW nPos, sal_uInt16& rVal)
 585 {
 586     if (nPos >= mnCurPos)
 587         // It can only go in a forward direction.
 588         mnCurPos = nPos;
 589
 590     if (mnCurPos > mnLastPos)
 591     {
 592         // position not in the current segment.  Update the current value.
 593         ScFlatUInt16SegmentsImpl::RangeData aData;
 594         if (mnLastPos == -1)
 595         {
 596             // first time in this method, use the tree search based method
 597             if (!mrSegs.mpImpl->getRangeData(mnCurPos, aData))
 598                 return false;
 599         }
 600         else
 601         {
 602             // but on subsequent calls, use the leaf method, which is faster
 603             // because we have a cached iterator.
 604             if (!mrSegs.mpImpl->getRangeDataLeaf(mnCurPos, aData))
 605                 return false;
 606         }
 607
 608         mnCurValue = aData.mnValue;
 609         mnLastPos = aData.mnPos2;
 610     }
 611
 612     rVal = mnCurValue;
 613     return true;
 614 }
 615
 616 ScFlatUInt16RowSegments::ScFlatUInt16RowSegments(SCROW nMaxRow, sal_uInt16 nDefault) :
 617     mpImpl(new ScFlatUInt16SegmentsImpl(nMaxRow, nDefault))
 618 {
 619 }
 620
 621 ScFlatUInt16RowSegments::ScFlatUInt16RowSegments(const ScFlatUInt16RowSegments& r) :
 622     mpImpl(new ScFlatUInt16SegmentsImpl(*r.mpImpl))
 623 {
 624 }
 625
 626 ScFlatUInt16RowSegments::~ScFlatUInt16RowSegments()
 627 {
 628 }
 629
 630 void ScFlatUInt16RowSegments::setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue)
 631 {
 632     mpImpl->setValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue);
 633 }
 634
 635 sal_uInt16 ScFlatUInt16RowSegments::getValue(SCROW nRow)
 636 {
 637     return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
 638 }
 639
 640 sal_uInt64 ScFlatUInt16RowSegments::getSumValue(SCROW nRow1, SCROW nRow2)
 641 {
 642     return mpImpl->getSumValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 643 }
 644
 645 bool ScFlatUInt16RowSegments::getRangeData(SCROW nRow, RangeData& rData)
 646 {
 647     ScFlatUInt16SegmentsImpl::RangeData aData;
 648     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
 649         return false;
 650
 651     rData.mnRow1  = aData.mnPos1;
 652     rData.mnRow2  = aData.mnPos2;
 653     rData.mnValue = aData.mnValue;
 654     return true;
 655 }
 656
 657 void ScFlatUInt16RowSegments::removeSegment(SCROW nRow1, SCROW nRow2)
 658 {
 659     mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 660 }
 661
 662 void ScFlatUInt16RowSegments::insertSegment(SCROW nRow, SCROW nSize)
 663 {
 664     mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), false/*bSkipStartBoundary*/);
 665 }
 666
 667 SCROW ScFlatUInt16RowSegments::findLastTrue(sal_uInt16 nValue) const
 668 {
 669     return mpImpl->findLastTrue(nValue);
 670 }
 671
 672 void ScFlatUInt16RowSegments::enableTreeSearch(bool bEnable)
 673 {
 674     mpImpl->enableTreeSearch(bEnable);
 675 }
 676
 677 void ScFlatUInt16RowSegments::setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function<bool(sal_uInt16)>& rPredicate)
 678 {
 679     mpImpl->setValueIf(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue, rPredicate);
 680 }
 681
 682 void ScFlatUInt16RowSegments::makeReady()
 683 {
 684     mpImpl->makeReady();
 685 }
 686
 687 OString ScFlatUInt16RowSegments::dumpAsString()
 688 {
 689     OStringBuffer aOutput(4096);
 690     RangeData aRange;
 691     SCROW nRow = 0;
 692     while (getRangeData(nRow, aRange))
 693     {
 694         aOutput.append(OString::number(aRange.mnValue) + ":" + OString::number(aRange.mnRow2) + " ");
 695         nRow = aRange.mnRow2 + 1;
 696     }
 697
 698     return aOutput.makeStringAndClear();
 699 }
 700
 701 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */