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
  21 #include "segmenttree.hxx"
  22
  23 #include <mdds/flat_segment_tree.hpp>
  24
  25 #include <limits>
  26
  27 using ::std::numeric_limits;
  28
  29 // ============================================================================
  30
  31 template<typename _ValueType, typename _ExtValueType = _ValueType>
  32 class ScFlatSegmentsImpl
  33 {
  34 public:
  35     typedef _ValueType ValueType;
  36     typedef _ExtValueType ExtValueType;
  37
  38     struct RangeData
  39     {
  40         SCCOLROW    mnPos1;
  41         SCCOLROW    mnPos2;
  42         ValueType   mnValue;
  43     };
  44
  45     ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault);
  46     ScFlatSegmentsImpl(const ScFlatSegmentsImpl& r);
  47     ~ScFlatSegmentsImpl();
  48
  49     bool setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
  50     ValueType getValue(SCCOLROW nPos);
  51     ExtValueType getSumValue(SCCOLROW nPos1, SCCOLROW nPos2);
  52     bool getRangeData(SCCOLROW nPos, RangeData& rData);
  53     bool getRangeDataLeaf(SCCOLROW nPos, RangeData& rData);
  54     void removeSegment(SCCOLROW nPos1, SCCOLROW nPos2);
  55     void insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary);
  56
  57     SCROW findLastNotOf(ValueType nValue) const;
  58
  59     // range iteration
  60     bool getFirst(RangeData& rData);
  61     bool getNext(RangeData& rData);
  62
  63     void enableTreeSearch(bool b)
  64     {
  65         mbTreeSearchEnabled = b;
  66     }
  67
  68 private:
  69     typedef ::mdds::flat_segment_tree<SCCOLROW, ValueType> fst_type;
  70     fst_type maSegments;
  71     typename fst_type::const_iterator maItr;
  72
  73     bool mbTreeSearchEnabled:1;
  74 };
  75
  76 template<typename _ValueType, typename _ExtValueType>
  77 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault) :
  78     maSegments(0, nMax+1, nDefault),
  79     mbTreeSearchEnabled(true)
  80 {
  81 }
  82
  83 template<typename _ValueType, typename _ExtValueType>
  84 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ScFlatSegmentsImpl(const ScFlatSegmentsImpl<_ValueType, _ExtValueType>& r) :
  85     maSegments(r.maSegments),
  86     mbTreeSearchEnabled(r.mbTreeSearchEnabled)
  87 {
  88 }
  89
  90 template<typename _ValueType, typename _ExtValueType>
  91 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::~ScFlatSegmentsImpl()
  92 {
  93 }
  94
  95 template<typename _ValueType, typename _ExtValueType>
  96 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue)
  97 {
  98     ::std::pair<typename fst_type::const_iterator, bool> ret;
  99     ret = maSegments.insert(maItr, nPos1, nPos2+1, nValue);
 100     maItr = ret.first;
 101     return ret.second;
 102 }
 103
 104 template<typename _ValueType, typename _ExtValueType>
 105 typename ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ValueType ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getValue(SCCOLROW nPos)
 106 {
 107     ValueType nValue = 0;
 108     if (!mbTreeSearchEnabled)
 109     {
 110         maSegments.search(nPos, nValue);
 111         return nValue;
 112     }
 113
 114     if (!maSegments.is_tree_valid())
 115         maSegments.build_tree();
 116
 117     maSegments.search_tree(nPos, nValue);
 118     return nValue;
 119 }
 120
 121 template<typename _ValueType, typename _ExtValueType>
 122 typename ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ExtValueType
 123 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getSumValue(SCCOLROW nPos1, SCCOLROW nPos2)
 124 {
 125     RangeData aData;
 126     if (!getRangeData(nPos1, aData))
 127         return 0;
 128
 129     sal_uInt32 nValue = 0;
 130
 131     SCROW nCurPos = nPos1;
 132     SCROW nEndPos = aData.mnPos2;
 133     while (nEndPos <= nPos2)
 134     {
 135         nValue += aData.mnValue * (nEndPos - nCurPos + 1);
 136         nCurPos = nEndPos + 1;
 137         if (!getRangeData(nCurPos, aData))
 138             break;
 139
 140         nEndPos = aData.mnPos2;
 141     }
 142     if (nCurPos <= nPos2)
 143     {
 144         nEndPos = ::std::min(nEndPos, nPos2);
 145         nValue += aData.mnValue * (nEndPos - nCurPos + 1);
 146     }
 147     return nValue;
 148 }
 149
 150 template<typename _ValueType, typename _ExtValueType>
 151 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getRangeData(SCCOLROW nPos, RangeData& rData)
 152 {
 153     if (!mbTreeSearchEnabled)
 154         return getRangeDataLeaf(nPos, rData);
 155
 156     if (!maSegments.is_tree_valid())
 157         maSegments.build_tree();
 158
 159     if (!maSegments.search_tree(nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2).second)
 160         return false;
 161
 162     rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
 163     return true;
 164 }
 165
 166 template<typename _ValueType, typename _ExtValueType>
 167 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getRangeDataLeaf(SCCOLROW nPos, RangeData& rData)
 168 {
 169     // Conduct leaf-node only search.  Faster when searching between range insertion.
 170     const ::std::pair<typename fst_type::const_iterator, bool> &ret =
 171         maSegments.search(maItr, nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
 172
 173     if (!ret.second)
 174         return false;
 175
 176     maItr = ret.first;
 177
 178     rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
 179     return true;
 180 }
 181
 182 template<typename _ValueType, typename _ExtValueType>
 183 void ScFlatSegmentsImpl<_ValueType, _ExtValueType>::removeSegment(SCCOLROW nPos1, SCCOLROW nPos2)
 184 {
 185     maSegments.shift_left(nPos1, nPos2);
 186     maItr = maSegments.begin();
 187 }
 188
 189 template<typename _ValueType, typename _ExtValueType>
 190 void ScFlatSegmentsImpl<_ValueType, _ExtValueType>::insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary)
 191 {
 192     maSegments.shift_right(nPos, nSize, bSkipStartBoundary);
 193     maItr = maSegments.begin();
 194 }
 195
 196 template<typename _ValueType, typename _ExtValueType>
 197 SCCOLROW ScFlatSegmentsImpl<_ValueType, _ExtValueType>::findLastNotOf(ValueType nValue) const
 198 {
 199     SCCOLROW nPos = numeric_limits<SCCOLROW>::max(); // position not found.
 200     typename fst_type::const_reverse_iterator itr = maSegments.rbegin(), itrEnd = maSegments.rend();
 201     // Note that when searching in reverse direction, we need to skip the first
 202     // node, since the right-most leaf node does not store a valid value.
 203     for (++itr; itr != itrEnd; ++itr)
 204     {
 205         if (itr->second != nValue)
 206         {
 207             nPos = (--itr)->first - 1;
 208             break;
 209         }
 210     }
 211     return nPos;
 212 }
 213
 214 template<typename _ValueType, typename _ExtValueType>
 215 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getFirst(RangeData& rData)
 216 {
 217     maItr = maSegments.begin();
 218     return getNext(rData);
 219 }
 220
 221 template<typename _ValueType, typename _ExtValueType>
 222 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getNext(RangeData& rData)
 223 {
 224     typename fst_type::const_iterator itrEnd = maSegments.end();
 225     if (maItr == itrEnd)
 226         return false;
 227
 228     rData.mnPos1 = maItr->first;
 229     rData.mnValue = maItr->second;
 230
 231     ++maItr;
 232     if (maItr == itrEnd)
 233         return false;
 234
 235     rData.mnPos2 = maItr->first - 1;
 236     return true;
 237 }
 238
 239 // ============================================================================
 240
 241 class ScFlatUInt16SegmentsImpl : public ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>
 242 {
 243 public:
 244     explicit ScFlatUInt16SegmentsImpl(SCCOLROW nMax, sal_uInt16 nDefault) :
 245         ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>(nMax, nDefault)
 246     {
 247     }
 248 };
 249
 250 // ----------------------------------------------------------------------------
 251
 252 class ScFlatBoolSegmentsImpl : public ScFlatSegmentsImpl<bool>
 253 {
 254 public:
 255     explicit ScFlatBoolSegmentsImpl(SCCOLROW nMax) :
 256         ScFlatSegmentsImpl<bool>(nMax, false)
 257     {
 258     }
 259
 260     bool setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
 261     bool setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
 262 };
 263
 264 bool ScFlatBoolSegmentsImpl::setTrue(SCCOLROW nPos1, SCCOLROW nPos2)
 265 {
 266     return setValue(nPos1, nPos2, true);
 267 }
 268
 269 bool ScFlatBoolSegmentsImpl::setFalse(SCCOLROW nPos1, SCCOLROW nPos2)
 270 {
 271     return setValue(nPos1, nPos2, false);
 272 }
 273
 274 // ============================================================================
 275
 276 ScFlatBoolRowSegments::ForwardIterator::ForwardIterator(ScFlatBoolRowSegments& rSegs) :
 277     mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mbCurValue(false)
 278 {
 279 }
 280
 281 bool ScFlatBoolRowSegments::ForwardIterator::getValue(SCROW nPos, bool& rVal)
 282 {
 283     if (nPos >= mnCurPos)
 284         // It can only go in a forward direction.
 285         mnCurPos = nPos;
 286
 287     if (mnCurPos > mnLastPos)
 288     {
 289         // position not in the current segment.  Update the current value.
 290         ScFlatBoolRowSegments::RangeData aData;
 291         if (!mrSegs.getRangeData(mnCurPos, aData))
 292             return false;
 293
 294         mbCurValue = aData.mbValue;
 295         mnLastPos = aData.mnRow2;
 296     }
 297
 298     rVal = mbCurValue;
 299     return true;
 300 }
 301
 302 SCROW ScFlatBoolRowSegments::ForwardIterator::getLastPos() const
 303 {
 304     return mnLastPos;
 305 }
 306
 307 // ----------------------------------------------------------------------------
 308
 309 ScFlatBoolRowSegments::RangeIterator::RangeIterator(ScFlatBoolRowSegments& rSegs) :
 310     mrSegs(rSegs)
 311 {
 312 }
 313
 314 bool ScFlatBoolRowSegments::RangeIterator::getFirst(RangeData& rRange)
 315 {
 316     ScFlatBoolSegmentsImpl::RangeData aData;
 317     if (!mrSegs.mpImpl->getFirst(aData))
 318         return false;
 319
 320     rRange.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 321     rRange.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 322     rRange.mbValue = static_cast<bool>(aData.mnValue);
 323     return true;
 324 }
 325
 326 bool ScFlatBoolRowSegments::RangeIterator::getNext(RangeData& rRange)
 327 {
 328     ScFlatBoolSegmentsImpl::RangeData aData;
 329     if (!mrSegs.mpImpl->getNext(aData))
 330         return false;
 331
 332     rRange.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 333     rRange.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 334     rRange.mbValue = static_cast<bool>(aData.mnValue);
 335     return true;
 336 }
 337
 338 // ----------------------------------------------------------------------------
 339
 340 ScFlatBoolRowSegments::ScFlatBoolRowSegments() :
 341     mpImpl(new ScFlatBoolSegmentsImpl(static_cast<SCCOLROW>(MAXROW)))
 342 {
 343 }
 344
 345 ScFlatBoolRowSegments::ScFlatBoolRowSegments(const ScFlatBoolRowSegments& r) :
 346     mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
 347 {
 348 }
 349
 350 ScFlatBoolRowSegments::~ScFlatBoolRowSegments()
 351 {
 352 }
 353
 354 bool ScFlatBoolRowSegments::setTrue(SCROW nRow1, SCROW nRow2)
 355 {
 356     return mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 357 }
 358
 359 bool ScFlatBoolRowSegments::setFalse(SCROW nRow1, SCROW nRow2)
 360 {
 361     return mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 362 }
 363
 364 bool ScFlatBoolRowSegments::getValue(SCROW nRow)
 365 {
 366     return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
 367 }
 368
 369 bool ScFlatBoolRowSegments::getRangeData(SCROW nRow, RangeData& rData)
 370 {
 371     ScFlatBoolSegmentsImpl::RangeData aData;
 372     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
 373         return false;
 374
 375     rData.mbValue = aData.mnValue;
 376     rData.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 377     rData.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 378     return true;
 379 }
 380
 381 bool ScFlatBoolRowSegments::getRangeDataLeaf(SCROW nRow, RangeData& rData)
 382 {
 383     ScFlatBoolSegmentsImpl::RangeData aData;
 384     if (!mpImpl->getRangeDataLeaf(static_cast<SCCOLROW>(nRow), aData))
 385         return false;
 386
 387     rData.mbValue = aData.mnValue;
 388     rData.mnRow1  = static_cast<SCROW>(aData.mnPos1);
 389     rData.mnRow2  = static_cast<SCROW>(aData.mnPos2);
 390     return true;
 391 }
 392
 393 void ScFlatBoolRowSegments::removeSegment(SCROW nRow1, SCROW nRow2)
 394 {
 395     mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 396 }
 397
 398 void ScFlatBoolRowSegments::insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary)
 399 {
 400     mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
 401 }
 402
 403 SCROW ScFlatBoolRowSegments::findLastNotOf(bool bValue) const
 404 {
 405     return static_cast<SCROW>(mpImpl->findLastNotOf(bValue));
 406 }
 407
 408 // ============================================================================
 409
 410 ScFlatBoolColSegments::ScFlatBoolColSegments() :
 411     mpImpl(new ScFlatBoolSegmentsImpl(static_cast<SCCOLROW>(MAXCOL)))
 412 {
 413 }
 414
 415 ScFlatBoolColSegments::ScFlatBoolColSegments(const ScFlatBoolColSegments& r) :
 416     mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
 417 {
 418 }
 419
 420 ScFlatBoolColSegments::~ScFlatBoolColSegments()
 421 {
 422 }
 423
 424 bool ScFlatBoolColSegments::setTrue(SCCOL nCol1, SCCOL nCol2)
 425 {
 426     return mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 427 }
 428
 429 bool ScFlatBoolColSegments::setFalse(SCCOL nCol1, SCCOL nCol2)
 430 {
 431     return mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 432 }
 433
 434 bool ScFlatBoolColSegments::getRangeData(SCCOL nCol, RangeData& rData)
 435 {
 436     ScFlatBoolSegmentsImpl::RangeData aData;
 437     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nCol), aData))
 438         return false;
 439
 440     rData.mbValue = aData.mnValue;
 441     rData.mnCol1  = static_cast<SCCOL>(aData.mnPos1);
 442     rData.mnCol2  = static_cast<SCCOL>(aData.mnPos2);
 443     return true;
 444 }
 445
 446 void ScFlatBoolColSegments::removeSegment(SCCOL nCol1, SCCOL nCol2)
 447 {
 448     mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 449 }
 450
 451 void ScFlatBoolColSegments::insertSegment(SCCOL nCol, SCCOL nSize, bool bSkipStartBoundary)
 452 {
 453     mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
 454 }
 455
 456 // ============================================================================
 457
 458 ScFlatUInt16RowSegments::ForwardIterator::ForwardIterator(ScFlatUInt16RowSegments& rSegs) :
 459     mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mnCurValue(0)
 460 {
 461 }
 462
 463 bool ScFlatUInt16RowSegments::ForwardIterator::getValue(SCROW nPos, sal_uInt16& rVal)
 464 {
 465     if (nPos >= mnCurPos)
 466         // It can only go in a forward direction.
 467         mnCurPos = nPos;
 468
 469     if (mnCurPos > mnLastPos)
 470     {
 471         // position not in the current segment.  Update the current value.
 472         ScFlatUInt16RowSegments::RangeData aData;
 473         if (!mrSegs.getRangeData(mnCurPos, aData))
 474             return false;
 475
 476         mnCurValue = aData.mnValue;
 477         mnLastPos = aData.mnRow2;
 478     }
 479
 480     rVal = mnCurValue;
 481     return true;
 482 }
 483
 484 SCROW ScFlatUInt16RowSegments::ForwardIterator::getLastPos() const
 485 {
 486     return mnLastPos;
 487 }
 488
 489 // ----------------------------------------------------------------------------
 490
 491 ScFlatUInt16RowSegments::ScFlatUInt16RowSegments(sal_uInt16 nDefault) :
 492     mpImpl(new ScFlatUInt16SegmentsImpl(static_cast<SCCOLROW>(MAXROW), nDefault))
 493 {
 494 }
 495
 496 ScFlatUInt16RowSegments::ScFlatUInt16RowSegments(const ScFlatUInt16RowSegments& r) :
 497     mpImpl(new ScFlatUInt16SegmentsImpl(*r.mpImpl))
 498 {
 499 }
 500
 501 ScFlatUInt16RowSegments::~ScFlatUInt16RowSegments()
 502 {
 503 }
 504
 505 void ScFlatUInt16RowSegments::setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue)
 506 {
 507     mpImpl->setValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue);
 508 }
 509
 510 sal_uInt16 ScFlatUInt16RowSegments::getValue(SCROW nRow)
 511 {
 512     return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
 513 }
 514
 515 sal_uInt32 ScFlatUInt16RowSegments::getSumValue(SCROW nRow1, SCROW nRow2)
 516 {
 517     return mpImpl->getSumValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 518 }
 519
 520 bool ScFlatUInt16RowSegments::getRangeData(SCROW nRow, RangeData& rData)
 521 {
 522     ScFlatUInt16SegmentsImpl::RangeData aData;
 523     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
 524         return false;
 525
 526     rData.mnRow1  = aData.mnPos1;
 527     rData.mnRow2  = aData.mnPos2;
 528     rData.mnValue = aData.mnValue;
 529     return true;
 530 }
 531
 532 void ScFlatUInt16RowSegments::removeSegment(SCROW nRow1, SCROW nRow2)
 533 {
 534     mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 535 }
 536
 537 void ScFlatUInt16RowSegments::insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary)
 538 {
 539     mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
 540 }
 541
 542 SCROW ScFlatUInt16RowSegments::findLastNotOf(sal_uInt16 nValue) const
 543 {
 544     return static_cast<SCROW>(mpImpl->findLastNotOf(nValue));
 545 }
 546
 547 void ScFlatUInt16RowSegments::enableTreeSearch(bool bEnable)
 548 {
 549     mpImpl->enableTreeSearch(bEnable);
 550 }
 551
 552 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */