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