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