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