LibreOffice Module sc (master)  1
segmenttree.cxx
Go to the documentation of this file.
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 <address.hxx>
27 
28 using ::std::numeric_limits;
29 
30 namespace {
31 
32 template<typename ValueType_, typename ExtValueType_ = ValueType_>
33 class ScFlatSegmentsImpl
34 {
35 public:
36  typedef ValueType_ ValueType;
37  typedef ExtValueType_ ExtValueType;
38 
39  struct RangeData
40  {
41  SCCOLROW mnPos1;
42  SCCOLROW mnPos2;
43  ValueType mnValue;
44  };
45 
46  ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault);
47  ScFlatSegmentsImpl(const ScFlatSegmentsImpl& r);
48 
49  bool setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
50  void setValueIf(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue, const std::function<bool(ValueType)>& rPredicate);
51  ValueType getValue(SCCOLROW nPos);
52  ExtValueType getSumValue(SCCOLROW nPos1, SCCOLROW nPos2);
53  bool getRangeData(SCCOLROW nPos, RangeData& rData);
54  bool getRangeDataLeaf(SCCOLROW nPos, RangeData& rData);
55  void removeSegment(SCCOLROW nPos1, SCCOLROW nPos2);
56  void insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary);
57 
58  SCCOLROW findLastTrue(ValueType nValue) const;
59 
60  // range iteration
61  bool getFirst(RangeData& rData);
62  bool getNext(RangeData& rData);
63 
64  void enableTreeSearch(bool b)
65  {
66  mbTreeSearchEnabled = b;
67  }
68 
69 private:
70  typedef ::mdds::flat_segment_tree<SCCOLROW, ValueType> fst_type;
71  fst_type maSegments;
72  typename fst_type::const_iterator maItr;
73 
74  bool mbTreeSearchEnabled:1;
75 };
76 
77 }
78 
79 template<typename ValueType_, typename ExtValueType_>
80 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault) :
81  maSegments(0, nMax+1, nDefault),
82  mbTreeSearchEnabled(true)
83 {
84 }
85 
86 template<typename ValueType_, typename ExtValueType_>
87 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(const ScFlatSegmentsImpl<ValueType_, ExtValueType_>& r) :
88  maSegments(r.maSegments),
89  mbTreeSearchEnabled(r.mbTreeSearchEnabled)
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 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValueIf(SCCOLROW nPos1, SCCOLROW nPos2,
104  ValueType nValue, const std::function<bool(ValueType)>& rPredicate)
105 {
106  SCCOLROW nCurrentStartRow = nPos1;
107  while (nCurrentStartRow <= nPos2)
108  {
109  RangeData aRangeData;
110  getRangeData(nCurrentStartRow, aRangeData);
111  if (rPredicate(aRangeData.mnValue))
112  {
113  // set value from current iteration point on, til end of range.
114  // Note that aRangeData may well contain much lower values for nPos1
115  setValue(nCurrentStartRow, std::min<SCCOLROW>(nPos2, aRangeData.mnPos2), nValue);
116  }
117 
118  // even if nPos2 is bigger than nPos2 this should terminate the loop
119  nCurrentStartRow = aRangeData.mnPos2 + 1;
120  }
121 }
122 
123 template<typename ValueType_, typename ExtValueType_>
124 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ValueType ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getValue(SCCOLROW nPos)
125 {
126  ValueType nValue = 0;
127  if (!mbTreeSearchEnabled)
128  {
129  maSegments.search(nPos, nValue);
130  return nValue;
131  }
132 
133  if (!maSegments.is_tree_valid())
134  maSegments.build_tree();
135 
136  maSegments.search_tree(nPos, nValue);
137  return nValue;
138 }
139 
140 template<typename ValueType_, typename ExtValueType_>
141 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ExtValueType
142 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getSumValue(SCCOLROW nPos1, SCCOLROW nPos2)
143 {
144  RangeData aData;
145  if (!getRangeData(nPos1, aData))
146  return 0;
147 
148  sal_uInt32 nValue = 0;
149 
150  SCROW nCurPos = nPos1;
151  SCROW nEndPos = aData.mnPos2;
152  while (nEndPos <= nPos2)
153  {
154  sal_uInt32 nRes;
155  if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
156  {
157  SAL_WARN("sc.core", "row height overflow");
158  nRes = SAL_MAX_INT32;
159  }
160  nValue = o3tl::saturating_add(nValue, nRes);
161  nCurPos = nEndPos + 1;
162  if (!getRangeData(nCurPos, aData))
163  break;
164 
165  nEndPos = aData.mnPos2;
166  }
167  if (nCurPos <= nPos2)
168  {
169  nEndPos = ::std::min(nEndPos, nPos2);
170  sal_uInt32 nRes;
171  if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
172  {
173  SAL_WARN("sc.core", "row height overflow");
174  nRes = SAL_MAX_INT32;
175  }
176  nValue = o3tl::saturating_add(nValue, nRes);
177  }
178  return nValue;
179 }
180 
181 template<typename ValueType_, typename ExtValueType_>
182 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeData(SCCOLROW nPos, RangeData& rData)
183 {
184  if (!mbTreeSearchEnabled)
185  return getRangeDataLeaf(nPos, rData);
186 
187  if (!maSegments.is_tree_valid())
188  maSegments.build_tree();
189 
190  if (!maSegments.search_tree(nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2).second)
191  return false;
192 
193  rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
194  return true;
195 }
196 
197 template<typename ValueType_, typename ExtValueType_>
198 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeDataLeaf(SCCOLROW nPos, RangeData& rData)
199 {
200  // Conduct leaf-node only search. Faster when searching between range insertion.
201  const ::std::pair<typename fst_type::const_iterator, bool> &ret =
202  maSegments.search(maItr, nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
203 
204  if (!ret.second)
205  return false;
206 
207  maItr = ret.first;
208 
209  rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
210  return true;
211 }
212 
213 template<typename ValueType_, typename ExtValueType_>
214 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::removeSegment(SCCOLROW nPos1, SCCOLROW nPos2)
215 {
216  maSegments.shift_left(nPos1, nPos2);
217  maItr = maSegments.begin();
218 }
219 
220 template<typename ValueType_, typename ExtValueType_>
221 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary)
222 {
223  maSegments.shift_right(nPos, nSize, bSkipStartBoundary);
224  maItr = maSegments.begin();
225 }
226 
227 template<typename ValueType_, typename ExtValueType_>
228 SCCOLROW ScFlatSegmentsImpl<ValueType_, ExtValueType_>::findLastTrue(ValueType nValue) const
229 {
230  SCCOLROW nPos = numeric_limits<SCCOLROW>::max(); // position not found.
231  typename fst_type::const_reverse_iterator itr = maSegments.rbegin(), itrEnd = maSegments.rend();
232  // Note that when searching in reverse direction, we need to skip the first
233  // node, since the right-most leaf node does not store a valid value.
234  for (++itr; itr != itrEnd; ++itr)
235  {
236  if (itr->second != nValue)
237  {
238  nPos = (--itr)->first - 1;
239  break;
240  }
241  }
242  return nPos;
243 }
244 
245 template<typename ValueType_, typename ExtValueType_>
246 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getFirst(RangeData& rData)
247 {
248  maItr = maSegments.begin();
249  return getNext(rData);
250 }
251 
252 template<typename ValueType_, typename ExtValueType_>
253 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getNext(RangeData& rData)
254 {
255  typename fst_type::const_iterator itrEnd = maSegments.end();
256  if (maItr == itrEnd)
257  return false;
258 
259  rData.mnPos1 = maItr->first;
260  rData.mnValue = maItr->second;
261 
262  ++maItr;
263  if (maItr == itrEnd)
264  return false;
265 
266  rData.mnPos2 = maItr->first - 1;
267  return true;
268 }
269 
270 class ScFlatUInt16SegmentsImpl : public ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>
271 {
272 public:
273  explicit ScFlatUInt16SegmentsImpl(SCCOLROW nMax, sal_uInt16 nDefault) :
274  ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>(nMax, nDefault)
275  {
276  }
277 };
278 
279 class ScFlatBoolSegmentsImpl : public ScFlatSegmentsImpl<bool>
280 {
281 public:
283  ScFlatSegmentsImpl<bool>(nMax, false)
284  {
285  }
286 
287  bool setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
288  bool setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
289 };
290 
292 {
293  return setValue(nPos1, nPos2, true);
294 }
295 
297 {
298  return setValue(nPos1, nPos2, false);
299 }
300 
302  mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mbCurValue(false)
303 {
304 }
305 
307 {
308  if (nPos >= mnCurPos)
309  // It can only go in a forward direction.
310  mnCurPos = nPos;
311 
312  if (mnCurPos > mnLastPos)
313  {
314  // position not in the current segment. Update the current value.
316  if (!mrSegs.getRangeData(mnCurPos, aData))
317  return false;
318 
319  mbCurValue = aData.mbValue;
320  mnLastPos = aData.mnRow2;
321  }
322 
323  rVal = mbCurValue;
324  return true;
325 }
326 
328  mrSegs(rSegs)
329 {
330 }
331 
333 {
334  ScFlatBoolSegmentsImpl::RangeData aData;
335  if (!mrSegs.mpImpl->getFirst(aData))
336  return false;
337 
338  rRange.mnRow1 = static_cast<SCROW>(aData.mnPos1);
339  rRange.mnRow2 = static_cast<SCROW>(aData.mnPos2);
340  rRange.mbValue = static_cast<bool>(aData.mnValue);
341  return true;
342 }
343 
345 {
346  ScFlatBoolSegmentsImpl::RangeData aData;
347  if (!mrSegs.mpImpl->getNext(aData))
348  return false;
349 
350  rRange.mnRow1 = static_cast<SCROW>(aData.mnPos1);
351  rRange.mnRow2 = static_cast<SCROW>(aData.mnPos2);
352  rRange.mbValue = static_cast<bool>(aData.mnValue);
353  return true;
354 }
355 
357  mpImpl(new ScFlatBoolSegmentsImpl(nMaxRow))
358 {
359 }
360 
362  mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
363 {
364 }
365 
367 {
368 }
369 
371 {
372  return mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
373 }
374 
376 {
377  return mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
378 }
379 
381 {
382  ScFlatBoolSegmentsImpl::RangeData aData;
383  if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
384  return false;
385 
386  rData.mbValue = aData.mnValue;
387  rData.mnRow1 = static_cast<SCROW>(aData.mnPos1);
388  rData.mnRow2 = static_cast<SCROW>(aData.mnPos2);
389  return true;
390 }
391 
393 {
394  ScFlatBoolSegmentsImpl::RangeData aData;
395  if (!mpImpl->getRangeDataLeaf(static_cast<SCCOLROW>(nRow), aData))
396  return false;
397 
398  rData.mbValue = aData.mnValue;
399  rData.mnRow1 = static_cast<SCROW>(aData.mnPos1);
400  rData.mnRow2 = static_cast<SCROW>(aData.mnPos2);
401  return true;
402 }
403 
405 {
406  mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
407 }
408 
410 {
411  mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), true/*bSkipStartBoundary*/);
412 }
413 
415 {
416  return mpImpl->findLastTrue(false);
417 }
418 
420 {
421  OString aOutput;
422  OString aSegment;
423  RangeData aRange;
424  SCROW nRow = 0;
425  while (getRangeData(nRow, aRange))
426  {
427  if (!nRow)
428  aSegment = (aRange.mbValue ? OStringLiteral("1") : OStringLiteral("0")) + OStringLiteral(":");
429  else
430  aSegment.clear();
431 
432  aSegment += OString::number(aRange.mnRow2) + " ";
433  aOutput += aSegment;
434  nRow = aRange.mnRow2 + 1;
435  }
436 
437  return aOutput;
438 }
439 
441  mpImpl(new ScFlatBoolSegmentsImpl(nMaxCol))
442 {
443 }
444 
446  mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
447 {
448 }
449 
451 {
452 }
453 
455 {
456  return mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
457 }
458 
460 {
461  return mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
462 }
463 
465 {
466  ScFlatBoolSegmentsImpl::RangeData aData;
467  if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nCol), aData))
468  return false;
469 
470  rData.mbValue = aData.mnValue;
471  rData.mnCol1 = static_cast<SCCOL>(aData.mnPos1);
472  rData.mnCol2 = static_cast<SCCOL>(aData.mnPos2);
473  return true;
474 }
475 
477 {
478  mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
479 }
480 
482 {
483  mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize), true/*bSkipStartBoundary*/);
484 }
485 
487 {
488  OString aOutput;
489  OString aSegment;
490  RangeData aRange;
491  SCCOL nCol = 0;
492  while (getRangeData(nCol, aRange))
493  {
494  if (!nCol)
495  aSegment = (aRange.mbValue ? OStringLiteral("1") : OStringLiteral("0")) + OStringLiteral(":");
496  else
497  aSegment.clear();
498 
499  aSegment += OString::number(aRange.mnCol2) + " ";
500  aOutput += aSegment;
501  nCol = aRange.mnCol2 + 1;
502  }
503 
504  return aOutput;
505 }
506 
508  mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mnCurValue(0)
509 {
510 }
511 
513 {
514  if (nPos >= mnCurPos)
515  // It can only go in a forward direction.
516  mnCurPos = nPos;
517 
518  if (mnCurPos > mnLastPos)
519  {
520  // position not in the current segment. Update the current value.
522  if (!mrSegs.getRangeData(mnCurPos, aData))
523  return false;
524 
525  mnCurValue = aData.mnValue;
526  mnLastPos = aData.mnRow2;
527  }
528 
529  rVal = mnCurValue;
530  return true;
531 }
532 
534  mpImpl(new ScFlatUInt16SegmentsImpl(nMaxRow, nDefault))
535 {
536 }
537 
539  mpImpl(new ScFlatUInt16SegmentsImpl(*r.mpImpl))
540 {
541 }
542 
544 {
545 }
546 
547 void ScFlatUInt16RowSegments::setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue)
548 {
549  mpImpl->setValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue);
550 }
551 
553 {
554  return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
555 }
556 
558 {
559  return mpImpl->getSumValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
560 }
561 
563 {
564  ScFlatUInt16SegmentsImpl::RangeData aData;
565  if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
566  return false;
567 
568  rData.mnRow1 = aData.mnPos1;
569  rData.mnRow2 = aData.mnPos2;
570  rData.mnValue = aData.mnValue;
571  return true;
572 }
573 
575 {
576  mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
577 }
578 
580 {
581  mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), false/*bSkipStartBoundary*/);
582 }
583 
585 {
586  return mpImpl->findLastTrue(nValue);
587 }
588 
590 {
591  mpImpl->enableTreeSearch(bEnable);
592 }
593 
594 void ScFlatUInt16RowSegments::setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function<bool(sal_uInt16)>& rPredicate)
595 {
596  mpImpl->setValueIf(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue, rPredicate);
597 }
598 
600 {
601  OString aOutput;
602  OString aSegment;
603  RangeData aRange;
604  SCROW nRow = 0;
605  while (getRangeData(nRow, aRange))
606  {
607  aSegment = OString::number(aRange.mnValue) + ":" +
608  OString::number(aRange.mnRow2) + " ";
609  aOutput += aSegment;
610  nRow = aRange.mnRow2 + 1;
611  }
612 
613  return aOutput;
614 }
615 
616 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
RegError REGISTRY_CALLTYPE setValue(RegKeyHandle hKey, rtl_uString *keyName, RegValueType valueType, RegValue pData, sal_uInt32 valueSize)
bool getFirst(RangeData &rRange)
bool getRangeDataLeaf(SCROW nRow, RangeData &rData)
sal_uInt32 getSumValue(SCROW nRow1, SCROW nRow2)
const char aData[]
void removeSegment(SCROW nRow1, SCROW nRow2)
bool getValue(SCROW nPos, bool &rVal)
void insertSegment(SCROW nRow, SCROW nSize)
bool setFalse(SCROW nRow1, SCROW nRow2)
ScFlatBoolRowSegments(SCROW nMaxRow)
css::beans::Optional< css::uno::Any > getValue(OUString const &id)
void removeSegment(SCCOL nCol1, SCCOL nCol2)
bool getNext(RangeData &rRange)
ScFlatUInt16RowSegments(SCROW nMaxRow, sal_uInt16 nDefault)
void setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function< bool(sal_uInt16)> &rPredicate)
sal_Int32 SCCOLROW
a type capable of holding either SCCOL or SCROW
Definition: types.hxx:24
bool setTrue(SCROW nRow1, SCROW nRow2)
bool setFalse(SCCOL nCol1, SCCOL nCol2)
void setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue)
::std::unique_ptr< ScFlatUInt16SegmentsImpl > mpImpl
void insertSegment(SCCOL nCol, SCCOL nSize)
#define SAL_MAX_INT32
void enableTreeSearch(bool bEnable)
ForwardIterator(ScFlatBoolRowSegments &rSegs)
sal_Int16 SCCOL
Definition: types.hxx:22
std::enable_if< std::is_signed< T >::value, T >::type saturating_add(T a, T b)
ScFlatBoolSegmentsImpl(SCCOLROW nMax)
ScFlatBoolColSegments(SCCOL nMaxCol)
SCROW findLastTrue() const
ScFlatUInt16SegmentsImpl(SCCOLROW nMax, sal_uInt16 nDefault)
SCROW findLastTrue(sal_uInt16 nValue) const
sal_Int32 SCROW
Definition: types.hxx:18
::std::unique_ptr< ScFlatBoolSegmentsImpl > mpImpl
::std::unique_ptr< ScFlatBoolSegmentsImpl > mpImpl
Definition: segmenttree.hxx:83
bool getRangeData(SCROW nRow, RangeData &rData)
RangeIterator(ScFlatBoolRowSegments const &rSegs)
ValueType
#define SAL_WARN(area, stream)
sal_uInt16 getValue(SCROW nRow)
void insertSegment(SCROW nRow, SCROW nSize)
bool getRangeData(SCROW nRow, RangeData &rData) const
bool getRangeData(SCCOL nCol, RangeData &rData)
bool getValue(SCROW nPos, sal_uInt16 &rVal)
void removeSegment(SCROW nRow1, SCROW nRow2)
ForwardIterator(ScFlatUInt16RowSegments &rSegs)
bool setFalse(SCCOLROW nPos1, SCCOLROW nPos2)
bool setTrue(SCCOLROW nPos1, SCCOLROW nPos2)
bool setTrue(SCCOL nCol1, SCCOL nCol2)
const double mnValue