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