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