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 
27 using ::std::numeric_limits;
28 
29 namespace {
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 
48  bool setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
49  void setValueIf(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue, const std::function<bool(ValueType)>& rPredicate);
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  SCCOLROW findLastTrue(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 }
77 
78 template<typename ValueType_, typename ExtValueType_>
79 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault) :
80  maSegments(0, nMax+1, nDefault),
81  mbTreeSearchEnabled(true)
82 {
83 }
84 
85 template<typename ValueType_, typename ExtValueType_>
86 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(const ScFlatSegmentsImpl<ValueType_, ExtValueType_>& r) :
87  maSegments(r.maSegments),
88  mbTreeSearchEnabled(r.mbTreeSearchEnabled)
89 {
90 }
91 
92 template<typename ValueType_, typename ExtValueType_>
93 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue)
94 {
95  ::std::pair<typename fst_type::const_iterator, bool> ret;
96  ret = maSegments.insert(maItr, nPos1, nPos2+1, nValue);
97  maItr = ret.first;
98  return ret.second;
99 }
100 
101 template<typename ValueType_, typename ExtValueType_>
102 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValueIf(SCCOLROW nPos1, SCCOLROW nPos2,
103  ValueType nValue, const std::function<bool(ValueType)>& rPredicate)
104 {
105  SCCOLROW nCurrentStartRow = nPos1;
106  while (nCurrentStartRow <= nPos2)
107  {
108  RangeData aRangeData;
109  getRangeData(nCurrentStartRow, aRangeData);
110  if (rPredicate(aRangeData.mnValue))
111  {
112  // set value from current iteration point on, til end of range.
113  // Note that aRangeData may well contain much lower values for nPos1
114  setValue(nCurrentStartRow, std::min<SCCOLROW>(nPos2, aRangeData.mnPos2), nValue);
115  }
116 
117  // even if nPos2 is bigger than nPos2 this should terminate the loop
118  nCurrentStartRow = aRangeData.mnPos2 + 1;
119  }
120 }
121 
122 template<typename ValueType_, typename ExtValueType_>
123 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ValueType ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getValue(SCCOLROW nPos)
124 {
125  ValueType nValue = 0;
126  if (!mbTreeSearchEnabled)
127  {
128  maSegments.search(nPos, nValue);
129  return nValue;
130  }
131 
132  if (!maSegments.is_tree_valid())
133  maSegments.build_tree();
134 
135  maSegments.search_tree(nPos, nValue);
136  return nValue;
137 }
138 
139 template<typename ValueType_, typename ExtValueType_>
140 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ExtValueType
141 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getSumValue(SCCOLROW nPos1, SCCOLROW nPos2)
142 {
143  RangeData aData;
144  if (!getRangeData(nPos1, aData))
145  return 0;
146 
147  sal_uInt32 nValue = 0;
148 
149  SCROW nCurPos = nPos1;
150  SCROW nEndPos = aData.mnPos2;
151  while (nEndPos <= nPos2)
152  {
153  sal_uInt32 nRes;
154  if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
155  {
156  SAL_WARN("sc.core", "row height overflow");
157  nRes = SAL_MAX_INT32;
158  }
159  nValue = o3tl::saturating_add(nValue, nRes);
160  nCurPos = nEndPos + 1;
161  if (!getRangeData(nCurPos, aData))
162  break;
163 
164  nEndPos = aData.mnPos2;
165  }
166  if (nCurPos <= nPos2)
167  {
168  nEndPos = ::std::min(nEndPos, nPos2);
169  sal_uInt32 nRes;
170  if (o3tl::checked_multiply<sal_uInt32>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
171  {
172  SAL_WARN("sc.core", "row height overflow");
173  nRes = SAL_MAX_INT32;
174  }
175  nValue = o3tl::saturating_add(nValue, nRes);
176  }
177  return nValue;
178 }
179 
180 template<typename ValueType_, typename ExtValueType_>
181 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeData(SCCOLROW nPos, RangeData& rData)
182 {
183  if (!mbTreeSearchEnabled)
184  return getRangeDataLeaf(nPos, rData);
185 
186  if (!maSegments.is_tree_valid())
187  maSegments.build_tree();
188 
189  if (!maSegments.search_tree(nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2).second)
190  return false;
191 
192  rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
193  return true;
194 }
195 
196 template<typename ValueType_, typename ExtValueType_>
197 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeDataLeaf(SCCOLROW nPos, RangeData& rData)
198 {
199  // Conduct leaf-node only search. Faster when searching between range insertion.
200  const ::std::pair<typename fst_type::const_iterator, bool> &ret =
201  maSegments.search(maItr, nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
202 
203  if (!ret.second)
204  return false;
205 
206  maItr = ret.first;
207 
208  rData.mnPos2 = rData.mnPos2-1; // end point is not inclusive.
209  return true;
210 }
211 
212 template<typename ValueType_, typename ExtValueType_>
213 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::removeSegment(SCCOLROW nPos1, SCCOLROW nPos2)
214 {
215  maSegments.shift_left(nPos1, nPos2);
216  maItr = maSegments.begin();
217 }
218 
219 template<typename ValueType_, typename ExtValueType_>
220 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary)
221 {
222  maSegments.shift_right(nPos, nSize, bSkipStartBoundary);
223  maItr = maSegments.begin();
224 }
225 
226 template<typename ValueType_, typename ExtValueType_>
227 SCCOLROW ScFlatSegmentsImpl<ValueType_, ExtValueType_>::findLastTrue(ValueType nValue) const
228 {
229  SCCOLROW nPos = numeric_limits<SCCOLROW>::max(); // position not found.
230  typename fst_type::const_reverse_iterator itr = maSegments.rbegin(), itrEnd = maSegments.rend();
231  // Note that when searching in reverse direction, we need to skip the first
232  // node, since the right-most leaf node does not store a valid value.
233  for (++itr; itr != itrEnd; ++itr)
234  {
235  if (itr->second != nValue)
236  {
237  nPos = (--itr)->first - 1;
238  break;
239  }
240  }
241  return nPos;
242 }
243 
244 template<typename ValueType_, typename ExtValueType_>
245 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getFirst(RangeData& rData)
246 {
247  maItr = maSegments.begin();
248  return getNext(rData);
249 }
250 
251 template<typename ValueType_, typename ExtValueType_>
252 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getNext(RangeData& rData)
253 {
254  typename fst_type::const_iterator itrEnd = maSegments.end();
255  if (maItr == itrEnd)
256  return false;
257 
258  rData.mnPos1 = maItr->first;
259  rData.mnValue = maItr->second;
260 
261  ++maItr;
262  if (maItr == itrEnd)
263  return false;
264 
265  rData.mnPos2 = maItr->first - 1;
266  return true;
267 }
268 
269 class ScFlatUInt16SegmentsImpl : public ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>
270 {
271 public:
272  explicit ScFlatUInt16SegmentsImpl(SCCOLROW nMax, sal_uInt16 nDefault) :
273  ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>(nMax, nDefault)
274  {
275  }
276 };
277 
278 class ScFlatBoolSegmentsImpl : public ScFlatSegmentsImpl<bool>
279 {
280 public:
282  ScFlatSegmentsImpl<bool>(nMax, false)
283  {
284  }
285 
286  bool setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
287  bool setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
288 };
289 
291 {
292  return setValue(nPos1, nPos2, true);
293 }
294 
296 {
297  return setValue(nPos1, nPos2, false);
298 }
299 
301  mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mbCurValue(false)
302 {
303 }
304 
306 {
307  if (nPos >= mnCurPos)
308  // It can only go in a forward direction.
309  mnCurPos = nPos;
310 
311  if (mnCurPos > mnLastPos)
312  {
313  // position not in the current segment. Update the current value.
315  if (!mrSegs.getRangeData(mnCurPos, aData))
316  return false;
317 
318  mbCurValue = aData.mbValue;
319  mnLastPos = aData.mnRow2;
320  }
321 
322  rVal = mbCurValue;
323  return true;
324 }
325 
327  mrSegs(rSegs)
328 {
329 }
330 
332 {
333  ScFlatBoolSegmentsImpl::RangeData aData;
334  if (!mrSegs.mpImpl->getFirst(aData))
335  return false;
336 
337  rRange.mnRow1 = static_cast<SCROW>(aData.mnPos1);
338  rRange.mnRow2 = static_cast<SCROW>(aData.mnPos2);
339  rRange.mbValue = static_cast<bool>(aData.mnValue);
340  return true;
341 }
342 
344 {
345  ScFlatBoolSegmentsImpl::RangeData aData;
346  if (!mrSegs.mpImpl->getNext(aData))
347  return false;
348 
349  rRange.mnRow1 = static_cast<SCROW>(aData.mnPos1);
350  rRange.mnRow2 = static_cast<SCROW>(aData.mnPos2);
351  rRange.mbValue = static_cast<bool>(aData.mnValue);
352  return true;
353 }
354 
356  mpImpl(new ScFlatBoolSegmentsImpl(nMaxRow))
357 {
358 }
359 
361  mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
362 {
363 }
364 
366 {
367 }
368 
370 {
371  return mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
372 }
373 
375 {
376  return mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
377 }
378 
380 {
381  ScFlatBoolSegmentsImpl::RangeData aData;
382  if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
383  return false;
384 
385  rData.mbValue = aData.mnValue;
386  rData.mnRow1 = static_cast<SCROW>(aData.mnPos1);
387  rData.mnRow2 = static_cast<SCROW>(aData.mnPos2);
388  return true;
389 }
390 
392 {
393  ScFlatBoolSegmentsImpl::RangeData aData;
394  if (!mpImpl->getRangeDataLeaf(static_cast<SCCOLROW>(nRow), aData))
395  return false;
396 
397  rData.mbValue = aData.mnValue;
398  rData.mnRow1 = static_cast<SCROW>(aData.mnPos1);
399  rData.mnRow2 = static_cast<SCROW>(aData.mnPos2);
400  return true;
401 }
402 
404 {
405  mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
406 }
407 
409 {
410  mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), true/*bSkipStartBoundary*/);
411 }
412 
414 {
415  return mpImpl->findLastTrue(false);
416 }
417 
419 {
420  OString aOutput;
421  OString aSegment;
422  RangeData aRange;
423  SCROW nRow = 0;
424  while (getRangeData(nRow, aRange))
425  {
426  if (!nRow)
427  aSegment = (aRange.mbValue ? OStringLiteral("1") : OStringLiteral("0")) + OStringLiteral(":");
428  else
429  aSegment.clear();
430 
431  aSegment += OString::number(aRange.mnRow2) + " ";
432  aOutput += aSegment;
433  nRow = aRange.mnRow2 + 1;
434  }
435 
436  return aOutput;
437 }
438 
440  mpImpl(new ScFlatBoolSegmentsImpl(nMaxCol))
441 {
442 }
443 
445  mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
446 {
447 }
448 
450 {
451 }
452 
454 {
455  return mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
456 }
457 
459 {
460  return mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
461 }
462 
464 {
465  ScFlatBoolSegmentsImpl::RangeData aData;
466  if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nCol), aData))
467  return false;
468 
469  rData.mbValue = aData.mnValue;
470  rData.mnCol1 = static_cast<SCCOL>(aData.mnPos1);
471  rData.mnCol2 = static_cast<SCCOL>(aData.mnPos2);
472  return true;
473 }
474 
476 {
477  mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
478 }
479 
481 {
482  mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize), true/*bSkipStartBoundary*/);
483 }
484 
486 {
487  OString aOutput;
488  OString aSegment;
489  RangeData aRange;
490  SCCOL nCol = 0;
491  while (getRangeData(nCol, aRange))
492  {
493  if (!nCol)
494  aSegment = (aRange.mbValue ? OStringLiteral("1") : OStringLiteral("0")) + OStringLiteral(":");
495  else
496  aSegment.clear();
497 
498  aSegment += OString::number(aRange.mnCol2) + " ";
499  aOutput += aSegment;
500  nCol = aRange.mnCol2 + 1;
501  }
502 
503  return aOutput;
504 }
505 
507  mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mnCurValue(0)
508 {
509 }
510 
512 {
513  if (nPos >= mnCurPos)
514  // It can only go in a forward direction.
515  mnCurPos = nPos;
516 
517  if (mnCurPos > mnLastPos)
518  {
519  // position not in the current segment. Update the current value.
521  if (!mrSegs.getRangeData(mnCurPos, aData))
522  return false;
523 
524  mnCurValue = aData.mnValue;
525  mnLastPos = aData.mnRow2;
526  }
527 
528  rVal = mnCurValue;
529  return true;
530 }
531 
533  mpImpl(new ScFlatUInt16SegmentsImpl(nMaxRow, nDefault))
534 {
535 }
536 
538  mpImpl(new ScFlatUInt16SegmentsImpl(*r.mpImpl))
539 {
540 }
541 
543 {
544 }
545 
546 void ScFlatUInt16RowSegments::setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue)
547 {
548  mpImpl->setValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue);
549 }
550 
552 {
553  return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
554 }
555 
557 {
558  return mpImpl->getSumValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
559 }
560 
562 {
563  ScFlatUInt16SegmentsImpl::RangeData aData;
564  if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
565  return false;
566 
567  rData.mnRow1 = aData.mnPos1;
568  rData.mnRow2 = aData.mnPos2;
569  rData.mnValue = aData.mnValue;
570  return true;
571 }
572 
574 {
575  mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
576 }
577 
579 {
580  mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), false/*bSkipStartBoundary*/);
581 }
582 
584 {
585  return mpImpl->findLastTrue(nValue);
586 }
587 
589 {
590  mpImpl->enableTreeSearch(bEnable);
591 }
592 
593 void ScFlatUInt16RowSegments::setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function<bool(sal_uInt16)>& rPredicate)
594 {
595  mpImpl->setValueIf(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue, rPredicate);
596 }
597 
599 {
600  OString aOutput;
601  OString aSegment;
602  RangeData aRange;
603  SCROW nRow = 0;
604  while (getRangeData(nRow, aRange))
605  {
606  aSegment = OString::number(aRange.mnValue) + ":" +
607  OString::number(aRange.mnRow2) + " ";
608  aOutput += aSegment;
609  nRow = aRange.mnRow2 + 1;
610  }
611 
612  return aOutput;
613 }
614 
615 /* 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)
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)
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)
constexpr OUStringLiteral aData
::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)
css::beans::Optional< css::uno::Any > getValue(std::u16string_view id)
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