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