22 #include <mdds/flat_segment_tree.hpp>
26 #include <string_view>
29 using ::std::numeric_limits;
33 template<
typename ValueType_,
typename ExtValueType_ = ValueType_>
34 class ScFlatSegmentsImpl
38 typedef ExtValueType_ ExtValueType;
47 ScFlatSegmentsImpl(
SCCOLROW nMax, ValueType nDefault);
48 ScFlatSegmentsImpl(
const ScFlatSegmentsImpl& r);
51 void setValueIf(
SCCOLROW nPos1,
SCCOLROW nPos2, ValueType nValue,
const std::function<
bool(ValueType)>& rPredicate);
54 bool getRangeData(
SCCOLROW nPos, RangeData& rData);
55 bool getRangeDataLeaf(
SCCOLROW nPos, RangeData& rData);
59 SCCOLROW findLastTrue(ValueType nValue)
const;
62 bool getFirst(RangeData& rData);
63 bool getNext(RangeData& rData);
65 void enableTreeSearch(
bool b)
67 mbTreeSearchEnabled = b;
73 typedef ::mdds::flat_segment_tree<SCCOLROW, ValueType> fst_type;
75 typename fst_type::const_iterator maItr;
77 bool mbTreeSearchEnabled:1;
82 template<
typename ValueType_,
typename ExtValueType_>
83 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(
SCCOLROW nMax,
ValueType nDefault) :
84 maSegments(0, nMax+1, nDefault),
85 mbTreeSearchEnabled(true)
89 template<
typename ValueType_,
typename ExtValueType_>
90 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ScFlatSegmentsImpl(
const ScFlatSegmentsImpl<ValueType_, ExtValueType_>& r) :
91 maSegments(r.maSegments),
92 mbTreeSearchEnabled(r.mbTreeSearchEnabled)
96 template<
typename ValueType_,
typename ExtValueType_>
99 ::std::pair<typename fst_type::const_iterator, bool> ret;
100 ret = maSegments.insert(maItr, nPos1, nPos2+1, nValue);
105 template<
typename ValueType_,
typename ExtValueType_>
106 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValueIf(
SCCOLROW nPos1,
SCCOLROW nPos2,
110 while (nCurrentStartRow <= nPos2)
112 RangeData aRangeData;
113 getRangeData(nCurrentStartRow, aRangeData);
114 if (rPredicate(aRangeData.mnValue))
118 setValue(nCurrentStartRow, std::min<SCCOLROW>(nPos2, aRangeData.mnPos2), nValue);
122 nCurrentStartRow = aRangeData.mnPos2 + 1;
126 template<
typename ValueType_,
typename ExtValueType_>
127 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ValueType ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getValue(
SCCOLROW nPos)
130 if (!mbTreeSearchEnabled)
132 maSegments.search(nPos, nValue);
136 if (!maSegments.is_tree_valid())
139 maSegments.build_tree();
142 maSegments.search_tree(nPos, nValue);
146 template<
typename ValueType_,
typename ExtValueType_>
147 sal_uInt64 ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getSumValue(
SCCOLROW nPos1,
SCCOLROW nPos2)
149 if (mbTreeSearchEnabled)
152 if (!maSegments.is_tree_valid())
155 maSegments.build_tree();
159 auto [it, found] = maSegments.search_tree(nPos1, aData.mnValue, &aData.mnPos1, &aData.mnPos2);
162 aData.mnPos2 = aData.mnPos2-1;
164 sal_uInt64 nValue = 0;
166 SCROW nCurPos = nPos1;
167 SCROW nEndPos = aData.mnPos2;
168 while (nEndPos <= nPos2)
171 if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
173 SAL_WARN(
"sc.core",
"row height overflow");
177 nCurPos = nEndPos + 1;
178 auto itPair = maSegments.search(it, nCurPos, aData.mnValue, &aData.mnPos1, &aData.mnPos2);
182 aData.mnPos2 = aData.mnPos2-1;
183 nEndPos = aData.mnPos2;
185 if (nCurPos <= nPos2)
187 nEndPos = ::std::min(nEndPos, nPos2);
189 if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
191 SAL_WARN(
"sc.core",
"row height overflow");
201 if (!getRangeDataLeaf(nPos1, aData))
204 sal_uInt64 nValue = 0;
206 SCROW nCurPos = nPos1;
207 SCROW nEndPos = aData.mnPos2;
208 while (nEndPos <= nPos2)
211 if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
213 SAL_WARN(
"sc.core",
"row height overflow");
217 nCurPos = nEndPos + 1;
218 if (!getRangeDataLeaf(nCurPos, aData))
221 nEndPos = aData.mnPos2;
223 if (nCurPos <= nPos2)
225 nEndPos = ::std::min(nEndPos, nPos2);
227 if (o3tl::checked_multiply<sal_uInt64>(aData.mnValue, nEndPos - nCurPos + 1, nRes))
229 SAL_WARN(
"sc.core",
"row height overflow");
238 template<
typename ValueType_,
typename ExtValueType_>
239 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeData(
SCCOLROW nPos, RangeData& rData)
241 if (!mbTreeSearchEnabled)
242 return getRangeDataLeaf(nPos, rData);
244 if (!maSegments.is_tree_valid())
247 maSegments.build_tree();
250 auto [it,found] = maSegments.search_tree(nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
254 rData.mnPos2 = rData.mnPos2-1;
258 template<
typename ValueType_,
typename ExtValueType_>
259 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getRangeDataLeaf(
SCCOLROW nPos, RangeData& rData)
262 const ::std::pair<typename fst_type::const_iterator, bool> &ret =
263 maSegments.search(maItr, nPos, rData.mnValue, &rData.mnPos1, &rData.mnPos2);
270 rData.mnPos2 = rData.mnPos2-1;
274 template<
typename ValueType_,
typename ExtValueType_>
275 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::removeSegment(
SCCOLROW nPos1,
SCCOLROW nPos2)
277 maSegments.shift_left(nPos1, nPos2);
278 maItr = maSegments.begin();
281 template<
typename ValueType_,
typename ExtValueType_>
282 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::insertSegment(
SCCOLROW nPos,
SCCOLROW nSize,
bool bSkipStartBoundary)
284 maSegments.shift_right(nPos, nSize, bSkipStartBoundary);
285 maItr = maSegments.begin();
288 template<
typename ValueType_,
typename ExtValueType_>
289 SCCOLROW ScFlatSegmentsImpl<ValueType_, ExtValueType_>::findLastTrue(
ValueType nValue)
const
291 SCCOLROW nPos = numeric_limits<SCCOLROW>::max();
292 typename fst_type::const_reverse_iterator itr = maSegments.rbegin(), itrEnd = maSegments.rend();
295 for (++itr; itr != itrEnd; ++itr)
297 if (itr->second != nValue)
299 nPos = (--itr)->first - 1;
306 template<
typename ValueType_,
typename ExtValueType_>
307 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getFirst(RangeData& rData)
309 maItr = maSegments.begin();
310 return getNext(rData);
313 template<
typename ValueType_,
typename ExtValueType_>
314 bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getNext(RangeData& rData)
316 typename fst_type::const_iterator itrEnd = maSegments.end();
320 rData.mnPos1 = maItr->first;
321 rData.mnValue = maItr->second;
327 rData.mnPos2 = maItr->first - 1;
331 template<
typename ValueType_,
typename ExtValueType_>
332 void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::makeReady()
335 if (!maSegments.is_tree_valid())
336 maSegments.build_tree();
343 ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>(nMax, nDefault)
352 ScFlatSegmentsImpl<bool>(nMax,
false)
362 return setValue(nPos1, nPos2,
true);
367 return setValue(nPos1, nPos2,
false);
371 mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mbCurValue(
false)
377 if (nPos >= mnCurPos)
381 if (mnCurPos > mnLastPos)
385 if (!mrSegs.getRangeData(mnCurPos, aData))
403 ScFlatBoolSegmentsImpl::RangeData aData;
404 if (!mrSegs.mpImpl->getFirst(aData))
407 rRange.mnRow1 =
static_cast<SCROW>(aData.mnPos1);
408 rRange.mnRow2 =
static_cast<SCROW>(aData.mnPos2);
409 rRange.mbValue =
static_cast<bool>(aData.mnValue);
415 ScFlatBoolSegmentsImpl::RangeData aData;
416 if (!mrSegs.mpImpl->getNext(aData))
419 rRange.mnRow1 =
static_cast<SCROW>(aData.mnPos1);
420 rRange.mnRow2 =
static_cast<SCROW>(aData.mnPos2);
421 rRange.mbValue =
static_cast<bool>(aData.mnValue);
441 return mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
446 return mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
451 ScFlatBoolSegmentsImpl::RangeData aData;
452 if (!
mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
455 rData.mbValue = aData.mnValue;
456 rData.mnRow1 =
static_cast<SCROW>(aData.mnPos1);
457 rData.mnRow2 =
static_cast<SCROW>(aData.mnPos2);
463 ScFlatBoolSegmentsImpl::RangeData aData;
464 if (!
mpImpl->getRangeDataLeaf(static_cast<SCCOLROW>(nRow), aData))
467 rData.mbValue = aData.mnValue;
468 rData.mnRow1 =
static_cast<SCROW>(aData.mnPos1);
469 rData.mnRow2 =
static_cast<SCROW>(aData.mnPos2);
475 mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
480 mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize),
true);
485 return mpImpl->findLastTrue(
false);
502 aSegment = (aRange.mbValue ? std::string_view(
"1") : std::string_view(
"0")) + OString::Concat(
":");
506 aSegment += OString::number(aRange.mnRow2) +
" ";
508 nRow = aRange.mnRow2 + 1;
530 return mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
535 return mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
540 ScFlatBoolSegmentsImpl::RangeData aData;
541 if (!
mpImpl->getRangeData(static_cast<SCCOLROW>(nCol), aData))
544 rData.mbValue = aData.mnValue;
545 rData.mnCol1 =
static_cast<SCCOL>(aData.mnPos1);
546 rData.mnCol2 =
static_cast<SCCOL>(aData.mnPos2);
552 mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
557 mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize),
true);
574 aSegment = (aRange.mbValue ? OString::Concat(
"1") : OString::Concat(
"0")) + OString::Concat(
":");
578 aSegment += OString::number(aRange.mnCol2) +
" ";
580 nCol = aRange.mnCol2 + 1;
587 mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mnCurValue(0)
593 if (nPos >= mnCurPos)
597 if (mnCurPos > mnLastPos)
600 ScFlatUInt16SegmentsImpl::RangeData aData;
604 if (!mrSegs.mpImpl->getRangeData(mnCurPos, aData))
611 if (!mrSegs.mpImpl->getRangeDataLeaf(mnCurPos, aData))
615 mnCurValue = aData.mnValue;
616 mnLastPos = aData.mnPos2;
639 mpImpl->setValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue);
644 return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
649 return mpImpl->getSumValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
654 ScFlatUInt16SegmentsImpl::RangeData aData;
655 if (!
mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
658 rData.mnRow1 = aData.mnPos1;
659 rData.mnRow2 = aData.mnPos2;
660 rData.mnValue = aData.mnValue;
666 mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
671 mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize),
false);
676 return mpImpl->findLastTrue(nValue);
681 mpImpl->enableTreeSearch(bEnable);
686 mpImpl->setValueIf(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue, rPredicate);
702 aSegment = OString::number(aRange.mnValue) +
":" +
703 OString::number(aRange.mnRow2) +
" ";
705 nRow = aRange.mnRow2 + 1;
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)
static SC_DLLPUBLIC bool bThreadedGroupCalcInProgress
Calc's threaded group calculation is in progress.
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
bool setTrue(SCROW nRow1, SCROW nRow2)
~ScFlatUInt16RowSegments()
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)
void enableTreeSearch(bool bEnable)
ForwardIterator(ScFlatBoolRowSegments &rSegs)
ScFlatBoolSegmentsImpl(SCCOLROW nMax)
ScFlatBoolColSegments(SCCOL nMaxCol)
css::beans::Optional< css::uno::Any > getValue(std::u16string_view id)
SCROW findLastTrue() const
sal_uInt64 getSumValue(SCROW nRow1, SCROW nRow2)
ScFlatUInt16SegmentsImpl(SCCOLROW nMax, sal_uInt16 nDefault)
SCROW findLastTrue(sal_uInt16 nValue) const
T saturating_add(T a, T b)
::std::unique_ptr< ScFlatBoolSegmentsImpl > mpImpl
::std::unique_ptr< ScFlatBoolSegmentsImpl > mpImpl
bool getRangeData(SCROW nRow, RangeData &rData)
RangeIterator(ScFlatBoolRowSegments const &rSegs)
#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)
bool m_bDetectedRangeSegmentation false