xref: /AOO41X/main/sc/source/core/data/segmenttree.cxx (revision 1584ef184807553913c97bf89f2e8c8f542b818f) 
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_sc.hxx"
26 
27 #include "segmenttree.hxx"
28 
29 #include <mdds/flat_segment_tree.hpp>
30 
31 #include <limits>
32 
33 using ::std::numeric_limits;
34 
35 // ============================================================================
36 
37 template<typename _ValueType, typename _ExtValueType = _ValueType>
38 class ScFlatSegmentsImpl
39 {
40 public:
41     typedef _ValueType ValueType;
42     typedef _ExtValueType ExtValueType;
43 
44     struct RangeData
45     {
46         SCCOLROW    mnPos1;
47         SCCOLROW    mnPos2;
48         ValueType   mnValue;
49     };
50 
51     ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault);
52     ScFlatSegmentsImpl(const ScFlatSegmentsImpl& r);
53     ~ScFlatSegmentsImpl();
54 
55     void setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
56     ValueType getValue(SCCOLROW nPos);
57     ExtValueType getSumValue(SCCOLROW nPos1, SCCOLROW nPos2);
58     bool getRangeData(SCCOLROW nPos, RangeData& rData);
59     void removeSegment(SCCOLROW nPos1, SCCOLROW nPos2);
60     void insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary);
61 
62     SCROW findLastNotOf(ValueType nValue) const;
63 
64     // range iteration
65     bool getFirst(RangeData& rData);
66     bool getNext(RangeData& rData);
67 
68     void enableTreeSearch(bool b)
69     {
70         mbTreeSearchEnabled = b;
71     }
72 
73     void setInsertFromBack(bool b)
74     {
75         mbInsertFromBack = b;
76     }
77 
78 private:
79     typedef ::mdds::flat_segment_tree<SCCOLROW, ValueType> fst_type;
80     fst_type maSegments;
81     typename fst_type::const_iterator maItr;
82 
83     bool mbTreeSearchEnabled:1;
84     bool mbInsertFromBack:1;
85 };
86 
87 template<typename _ValueType, typename _ExtValueType>
88 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault) :
89     maSegments(0, nMax+1, nDefault),
90     mbTreeSearchEnabled(true),
91     mbInsertFromBack(false)
92 {
93 }
94 
95 template<typename _ValueType, typename _ExtValueType>
96 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ScFlatSegmentsImpl(const ScFlatSegmentsImpl<_ValueType, _ExtValueType>& r) :
97     maSegments(r.maSegments),
98     mbTreeSearchEnabled(r.mbTreeSearchEnabled),
99     mbInsertFromBack(r.mbInsertFromBack)
100 {
101 }
102 
103 template<typename _ValueType, typename _ExtValueType>
104 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::~ScFlatSegmentsImpl()
105 {
106 }
107 
108 template<typename _ValueType, typename _ExtValueType>
109 void ScFlatSegmentsImpl<_ValueType, _ExtValueType>::setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue)
110 {
111     if (mbInsertFromBack)
112         maSegments.insert_back(nPos1, nPos2+1, nValue);
113     else
114         maSegments.insert_front(nPos1, nPos2+1, nValue);
115 }
116 
117 template<typename _ValueType, typename _ExtValueType>
118 typename ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ValueType ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getValue(SCCOLROW nPos)
119 {
120     ValueType nValue = 0;
121     if (!mbTreeSearchEnabled)
122     {
123         maSegments.search(nPos, nValue);
124         return nValue;
125     }
126 
127     if (!maSegments.is_tree_valid())
128         maSegments.build_tree();
129 
130     maSegments.search_tree(nPos, nValue);
131     return nValue;
132 }
133 
134 template<typename _ValueType, typename _ExtValueType>
135 typename ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ExtValueType
136 ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getSumValue(SCCOLROW nPos1, SCCOLROW nPos2)
137 {
138     RangeData aData;
139     if (!getRangeData(nPos1, aData))
140         return 0;
141 
142     sal_uInt32 nValue = 0;
143 
144     SCROW nCurPos = nPos1;
145     SCROW nEndPos = aData.mnPos2;
146     while (nEndPos <= nPos2)
147     {
148         nValue += aData.mnValue * (nEndPos - nCurPos + 1);
149         nCurPos = nEndPos + 1;
150         if (!getRangeData(nCurPos, aData))
151             break;
152 
153         nEndPos = aData.mnPos2;
154     }
155     if (nCurPos <= nPos2)
156     {
157         nEndPos = ::std::min(nEndPos, nPos2);
158         nValue += aData.mnValue * (nEndPos - nCurPos + 1);
159     }
160     return nValue;
161 }
162 
163 template<typename _ValueType, typename _ExtValueType>
164 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getRangeData(SCCOLROW nPos, RangeData& rData)
165 {
166     ValueType nValue;
167     SCCOLROW nPos1, nPos2;
168 
169     if (mbTreeSearchEnabled)
170     {
171         if (!maSegments.is_tree_valid())
172             maSegments.build_tree();
173 
174         if (!maSegments.search_tree(nPos, nValue, &nPos1, &nPos2))
175             return false;
176     }
177     else
178     {
179         // Conduct leaf-node only search.  Faster when searching between range insertion.
180         if (!maSegments.search(nPos, nValue, &nPos1, &nPos2))
181             return false;
182     }
183 
184     rData.mnPos1 = nPos1;
185     rData.mnPos2 = nPos2-1; // end point is not inclusive.
186     rData.mnValue = nValue;
187     return true;
188 }
189 
190 template<typename _ValueType, typename _ExtValueType>
191 void ScFlatSegmentsImpl<_ValueType, _ExtValueType>::removeSegment(SCCOLROW nPos1, SCCOLROW nPos2)
192 {
193     maSegments.shift_left(nPos1, nPos2);
194 }
195 
196 template<typename _ValueType, typename _ExtValueType>
197 void ScFlatSegmentsImpl<_ValueType, _ExtValueType>::insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary)
198 {
199     maSegments.shift_right(nPos, nSize, bSkipStartBoundary);
200 }
201 
202 template<typename _ValueType, typename _ExtValueType>
203 SCCOLROW ScFlatSegmentsImpl<_ValueType, _ExtValueType>::findLastNotOf(ValueType nValue) const
204 {
205     SCCOLROW nPos = numeric_limits<SCCOLROW>::max(); // position not found.
206     typename fst_type::const_reverse_iterator itr = maSegments.rbegin(), itrEnd = maSegments.rend();
207     // Note that when searching in reverse direction, we need to skip the first
208     // node, since the right-most leaf node does not store a valid value.
209     for (++itr; itr != itrEnd; ++itr)
210     {
211         if (itr->second != nValue)
212         {
213             nPos = (--itr)->first - 1;
214             break;
215         }
216     }
217     return nPos;
218 }
219 
220 template<typename _ValueType, typename _ExtValueType>
221 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getFirst(RangeData& rData)
222 {
223     maItr = maSegments.begin();
224     return getNext(rData);
225 }
226 
227 template<typename _ValueType, typename _ExtValueType>
228 bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getNext(RangeData& rData)
229 {
230     typename fst_type::const_iterator itrEnd = maSegments.end();
231     if (maItr == itrEnd)
232         return false;
233 
234     rData.mnPos1 = maItr->first;
235     rData.mnValue = maItr->second;
236 
237     ++maItr;
238     if (maItr == itrEnd)
239         return false;
240 
241     rData.mnPos2 = maItr->first - 1;
242     return true;
243 }
244 
245 // ============================================================================
246 
247 class ScFlatUInt16SegmentsImpl : public ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>
248 {
249 public:
250     explicit ScFlatUInt16SegmentsImpl(SCCOLROW nMax, sal_uInt16 nDefault) :
251         ScFlatSegmentsImpl<sal_uInt16, sal_uInt32>(nMax, nDefault)
252     {
253     }
254 };
255 
256 // ----------------------------------------------------------------------------
257 
258 class ScFlatBoolSegmentsImpl : public ScFlatSegmentsImpl<bool>
259 {
260 public:
261     explicit ScFlatBoolSegmentsImpl(SCCOLROW nMax) :
262         ScFlatSegmentsImpl<bool>(nMax, false)
263     {
264     }
265 
266     void setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
267     void setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
268 };
269 
270 void ScFlatBoolSegmentsImpl::setTrue(SCCOLROW nPos1, SCCOLROW nPos2)
271 {
272     setValue(nPos1, nPos2, true);
273 }
274 
275 void ScFlatBoolSegmentsImpl::setFalse(SCCOLROW nPos1, SCCOLROW nPos2)
276 {
277     setValue(nPos1, nPos2, false);
278 }
279 
280 // ============================================================================
281 
282 ScFlatBoolRowSegments::ForwardIterator::ForwardIterator(ScFlatBoolRowSegments& rSegs) :
283     mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mbCurValue(false)
284 {
285 }
286 
287 bool ScFlatBoolRowSegments::ForwardIterator::getValue(SCROW nPos, bool& rVal)
288 {
289     if (nPos >= mnCurPos)
290         // It can only go in a forward direction.
291         mnCurPos = nPos;
292 
293     if (mnCurPos > mnLastPos)
294     {
295         // position not in the current segment.  Update the current value.
296         ScFlatBoolRowSegments::RangeData aData;
297         if (!mrSegs.getRangeData(mnCurPos, aData))
298             return false;
299 
300         mbCurValue = aData.mbValue;
301         mnLastPos = aData.mnRow2;
302     }
303 
304     rVal = mbCurValue;
305     return true;
306 }
307 
308 SCROW ScFlatBoolRowSegments::ForwardIterator::getLastPos() const
309 {
310     return mnLastPos;
311 }
312 
313 // ----------------------------------------------------------------------------
314 
315 ScFlatBoolRowSegments::RangeIterator::RangeIterator(ScFlatBoolRowSegments& rSegs) :
316     mrSegs(rSegs)
317 {
318 }
319 
320 bool ScFlatBoolRowSegments::RangeIterator::getFirst(RangeData& rRange)
321 {
322     ScFlatBoolSegmentsImpl::RangeData aData;
323     if (!mrSegs.mpImpl->getFirst(aData))
324         return false;
325 
326     rRange.mnRow1  = static_cast<SCROW>(aData.mnPos1);
327     rRange.mnRow2  = static_cast<SCROW>(aData.mnPos2);
328     rRange.mbValue = static_cast<bool>(aData.mnValue);
329     return true;
330 }
331 
332 bool ScFlatBoolRowSegments::RangeIterator::getNext(RangeData& rRange)
333 {
334     ScFlatBoolSegmentsImpl::RangeData aData;
335     if (!mrSegs.mpImpl->getNext(aData))
336         return false;
337 
338     rRange.mnRow1  = static_cast<SCROW>(aData.mnPos1);
339     rRange.mnRow2  = static_cast<SCROW>(aData.mnPos2);
340     rRange.mbValue = static_cast<bool>(aData.mnValue);
341     return true;
342 }
343 
344 // ----------------------------------------------------------------------------
345 
346 ScFlatBoolRowSegments::ScFlatBoolRowSegments() :
347     mpImpl(new ScFlatBoolSegmentsImpl(static_cast<SCCOLROW>(MAXROW)))
348 {
349 }
350 
351 ScFlatBoolRowSegments::ScFlatBoolRowSegments(const ScFlatBoolRowSegments& r) :
352     mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
353 {
354 }
355 
356 ScFlatBoolRowSegments::~ScFlatBoolRowSegments()
357 {
358 }
359 
360 void ScFlatBoolRowSegments::setTrue(SCROW nRow1, SCROW nRow2)
361 {
362     mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
363 }
364 
365 void ScFlatBoolRowSegments::setFalse(SCROW nRow1, SCROW nRow2)
366 {
367     mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
368 }
369 
370 bool ScFlatBoolRowSegments::getValue(SCROW nRow)
371 {
372     return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
373 }
374 
375 bool ScFlatBoolRowSegments::getRangeData(SCROW nRow, RangeData& rData)
376 {
377     ScFlatBoolSegmentsImpl::RangeData aData;
378     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
379         return false;
380 
381     rData.mbValue = aData.mnValue;
382     rData.mnRow1  = static_cast<SCROW>(aData.mnPos1);
383     rData.mnRow2  = static_cast<SCROW>(aData.mnPos2);
384     return true;
385 }
386 
387 void ScFlatBoolRowSegments::removeSegment(SCROW nRow1, SCROW nRow2)
388 {
389     mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
390 }
391 
392 void ScFlatBoolRowSegments::insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary)
393 {
394     mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
395 }
396 
397 SCROW ScFlatBoolRowSegments::findLastNotOf(bool bValue) const
398 {
399     return static_cast<SCROW>(mpImpl->findLastNotOf(bValue));
400 }
401 
402 void ScFlatBoolRowSegments::enableTreeSearch(bool bEnable)
403 {
404     mpImpl->enableTreeSearch(bEnable);
405 }
406 
407 void ScFlatBoolRowSegments::setInsertFromBack(bool bInsertFromBack)
408 {
409     mpImpl->setInsertFromBack(bInsertFromBack);
410 }
411 
412 // ============================================================================
413 
414 ScFlatBoolColSegments::ScFlatBoolColSegments() :
415     mpImpl(new ScFlatBoolSegmentsImpl(static_cast<SCCOLROW>(MAXCOL)))
416 {
417 }
418 
419 ScFlatBoolColSegments::ScFlatBoolColSegments(const ScFlatBoolColSegments& r) :
420     mpImpl(new ScFlatBoolSegmentsImpl(*r.mpImpl))
421 {
422 }
423 
424 ScFlatBoolColSegments::~ScFlatBoolColSegments()
425 {
426 }
427 
428 void ScFlatBoolColSegments::setTrue(SCCOL nCol1, SCCOL nCol2)
429 {
430     mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
431 }
432 
433 void ScFlatBoolColSegments::setFalse(SCCOL nCol1, SCCOL nCol2)
434 {
435     mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
436 }
437 
438 bool ScFlatBoolColSegments::getValue(SCCOL nCol)
439 {
440     return mpImpl->getValue(static_cast<SCCOLROW>(nCol));
441 }
442 
443 bool ScFlatBoolColSegments::getRangeData(SCCOL nCol, RangeData& rData)
444 {
445     ScFlatBoolSegmentsImpl::RangeData aData;
446     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nCol), aData))
447         return false;
448 
449     rData.mbValue = aData.mnValue;
450     rData.mnCol1  = static_cast<SCCOL>(aData.mnPos1);
451     rData.mnCol2  = static_cast<SCCOL>(aData.mnPos2);
452     return true;
453 }
454 
455 void ScFlatBoolColSegments::removeSegment(SCCOL nCol1, SCCOL nCol2)
456 {
457     mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
458 }
459 
460 void ScFlatBoolColSegments::insertSegment(SCCOL nCol, SCCOL nSize, bool bSkipStartBoundary)
461 {
462     mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
463 }
464 
465 void ScFlatBoolColSegments::enableTreeSearch(bool bEnable)
466 {
467     mpImpl->enableTreeSearch(bEnable);
468 }
469 
470 void ScFlatBoolColSegments::setInsertFromBack(bool bInsertFromBack)
471 {
472     mpImpl->setInsertFromBack(bInsertFromBack);
473 }
474 
475 // ============================================================================
476 
477 
478 // ============================================================================
479 
480 ScFlatUInt16RowSegments::ForwardIterator::ForwardIterator(ScFlatUInt16RowSegments& rSegs) :
481     mrSegs(rSegs), mnCurPos(0), mnLastPos(-1), mnCurValue(0)
482 {
483 }
484 
485 bool ScFlatUInt16RowSegments::ForwardIterator::getValue(SCROW nPos, sal_uInt16& rVal)
486 {
487     if (nPos >= mnCurPos)
488         // It can only go in a forward direction.
489         mnCurPos = nPos;
490 
491     if (mnCurPos > mnLastPos)
492     {
493         // position not in the current segment.  Update the current value.
494         ScFlatUInt16RowSegments::RangeData aData;
495         if (!mrSegs.getRangeData(mnCurPos, aData))
496             return false;
497 
498         mnCurValue = aData.mnValue;
499         mnLastPos = aData.mnRow2;
500     }
501 
502     rVal = mnCurValue;
503     return true;
504 }
505 
506 SCROW ScFlatUInt16RowSegments::ForwardIterator::getLastPos() const
507 {
508     return mnLastPos;
509 }
510 
511 // ----------------------------------------------------------------------------
512 
513 ScFlatUInt16RowSegments::ScFlatUInt16RowSegments(sal_uInt16 nDefault) :
514     mpImpl(new ScFlatUInt16SegmentsImpl(static_cast<SCCOLROW>(MAXROW), nDefault))
515 {
516 }
517 
518 ScFlatUInt16RowSegments::ScFlatUInt16RowSegments(const ScFlatUInt16RowSegments& r) :
519     mpImpl(new ScFlatUInt16SegmentsImpl(*r.mpImpl))
520 {
521 }
522 
523 ScFlatUInt16RowSegments::~ScFlatUInt16RowSegments()
524 {
525 }
526 
527 void ScFlatUInt16RowSegments::setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue)
528 {
529     mpImpl->setValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue);
530 }
531 
532 sal_uInt16 ScFlatUInt16RowSegments::getValue(SCROW nRow)
533 {
534     return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
535 }
536 
537 sal_uInt32 ScFlatUInt16RowSegments::getSumValue(SCROW nRow1, SCROW nRow2)
538 {
539     return mpImpl->getSumValue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
540 }
541 
542 bool ScFlatUInt16RowSegments::getRangeData(SCROW nRow, RangeData& rData)
543 {
544     ScFlatUInt16SegmentsImpl::RangeData aData;
545     if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
546         return false;
547 
548     rData.mnRow1  = aData.mnPos1;
549     rData.mnRow2  = aData.mnPos2;
550     rData.mnValue = aData.mnValue;
551     return true;
552 }
553 
554 void ScFlatUInt16RowSegments::removeSegment(SCROW nRow1, SCROW nRow2)
555 {
556     mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
557 }
558 
559 void ScFlatUInt16RowSegments::insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary)
560 {
561     mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
562 }
563 
564 SCROW ScFlatUInt16RowSegments::findLastNotOf(sal_uInt16 nValue) const
565 {
566     return static_cast<SCROW>(mpImpl->findLastNotOf(nValue));
567 }
568 
569 void ScFlatUInt16RowSegments::enableTreeSearch(bool bEnable)
570 {
571     mpImpl->enableTreeSearch(bEnable);
572 }
573 
574 void ScFlatUInt16RowSegments::setInsertFromBack(bool bInsertFromBack)
575 {
576     mpImpl->setInsertFromBack(bInsertFromBack);
577 }
578 
579