LibreOffice Module vcl (master) 1
regionband.cxx
Go to the documentation of this file.
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 <sal/config.h>
21
22#include <cstdlib>
23
24#include <tools/stream.hxx>
25#include <regionband.hxx>
26#include <o3tl/safeint.hxx>
27#include <osl/diagnose.h>
28#include <sal/log.hxx>
29
31: mpFirstBand(nullptr),
32 mpLastCheckedBand(nullptr)
34}
35
37: mpFirstBand(nullptr),
38 mpLastCheckedBand(nullptr)
39{
40 *this = rRef;
41}
42
44{
45 if (this != &rRef)
46 {
47 ImplRegionBand* pPrevBand = nullptr;
48 ImplRegionBand* pBand = rRef.mpFirstBand;
49
50 while(pBand)
51 {
52 ImplRegionBand* pNewBand = new ImplRegionBand(*pBand);
53
54 // first element? -> set as first into the list
55 if(pBand == rRef.mpFirstBand)
56 {
57 mpFirstBand = pNewBand;
58 }
59 else
60 {
61 pPrevBand->mpNextBand = pNewBand;
62 }
63
64 pPrevBand = pNewBand;
65 pBand = pBand->mpNextBand;
66 }
67 }
68 return *this;
69}
70
72: mpFirstBand(nullptr),
73 mpLastCheckedBand(nullptr)
74{
75 const tools::Long nTop(std::min(rRect.Top(), rRect.Bottom()));
76 const tools::Long nBottom(std::max(rRect.Top(), rRect.Bottom()));
77 const tools::Long nLeft(std::min(rRect.Left(), rRect.Right()));
78 const tools::Long nRight(std::max(rRect.Left(), rRect.Right()));
79
80 // add band with boundaries of the rectangle
81 mpFirstBand = new ImplRegionBand(nTop, nBottom);
82
83 // Set left and right boundaries of the band
84 mpFirstBand->Union(nLeft, nRight);
85
86}
87
89{
91
92 while(pBand)
93 {
94 ImplRegionBand* pTempBand = pBand->mpNextBand;
95 delete pBand;
96 pBand = pTempBand;
97 }
98
99 mpLastCheckedBand = nullptr;
100 mpFirstBand = nullptr;
101}
102
104{
105 implReset();
106}
107
108bool RegionBand::operator==( const RegionBand& rRegionBand ) const
109{
110
111 // initialise pointers
112 ImplRegionBand* pOwnRectBand = mpFirstBand;
113 ImplRegionBandSep* pOwnRectBandSep = pOwnRectBand->mpFirstSep;
114 ImplRegionBand* pSecondRectBand = rRegionBand.mpFirstBand;
115 ImplRegionBandSep* pSecondRectBandSep = pSecondRectBand->mpFirstSep;
116
117 while ( pOwnRectBandSep && pSecondRectBandSep )
118 {
119 // get boundaries of current rectangle
120 tools::Long nOwnXLeft = pOwnRectBandSep->mnXLeft;
121 tools::Long nSecondXLeft = pSecondRectBandSep->mnXLeft;
122
123 if ( nOwnXLeft != nSecondXLeft )
124 {
125 return false;
126 }
127
128 tools::Long nOwnYTop = pOwnRectBand->mnYTop;
129 tools::Long nSecondYTop = pSecondRectBand->mnYTop;
130
131 if ( nOwnYTop != nSecondYTop )
132 {
133 return false;
134 }
135
136 tools::Long nOwnXRight = pOwnRectBandSep->mnXRight;
137 tools::Long nSecondXRight = pSecondRectBandSep->mnXRight;
138
139 if ( nOwnXRight != nSecondXRight )
140 {
141 return false;
142 }
143
144 tools::Long nOwnYBottom = pOwnRectBand->mnYBottom;
145 tools::Long nSecondYBottom = pSecondRectBand->mnYBottom;
146
147 if ( nOwnYBottom != nSecondYBottom )
148 {
149 return false;
150 }
151
152 // get next separation from current band
153 pOwnRectBandSep = pOwnRectBandSep->mpNextSep;
154
155 // no separation found? -> go to next band!
156 if ( !pOwnRectBandSep )
157 {
158 // get next band
159 pOwnRectBand = pOwnRectBand->mpNextBand;
160
161 // get first separation in current band
162 if( pOwnRectBand )
163 {
164 pOwnRectBandSep = pOwnRectBand->mpFirstSep;
165 }
166 }
167
168 // get next separation from current band
169 pSecondRectBandSep = pSecondRectBandSep->mpNextSep;
170
171 // no separation found? -> go to next band!
172 if ( !pSecondRectBandSep )
173 {
174 // get next band
175 pSecondRectBand = pSecondRectBand->mpNextBand;
176
177 // get first separation in current band
178 if( pSecondRectBand )
179 {
180 pSecondRectBandSep = pSecondRectBand->mpFirstSep;
181 }
182 }
183
184 if ( pOwnRectBandSep && !pSecondRectBandSep )
185 {
186 return false;
187 }
188
189 if ( !pOwnRectBandSep && pSecondRectBandSep )
190 {
191 return false;
192 }
193 }
194
195 return true;
196}
197
198namespace {
199
200enum StreamEntryType { STREAMENTRY_BANDHEADER, STREAMENTRY_SEPARATION, STREAMENTRY_END };
201
202}
203
205{
206 // clear this instance data
207 implReset();
208
209 // get all bands
210 ImplRegionBand* pCurrBand = nullptr;
211
212 // get header from first element
213 sal_uInt16 nTmp16(STREAMENTRY_END);
214 rIStrm.ReadUInt16(nTmp16);
215
216 if (STREAMENTRY_END == static_cast<StreamEntryType>(nTmp16))
217 return false;
218
219 size_t nRecordsPossible = rIStrm.remainingSize() / (2*sizeof(sal_Int32));
220 if (!nRecordsPossible)
221 {
222 OSL_ENSURE(false, "premature end of region stream" );
223 implReset();
224 return false;
225 }
226
227 do
228 {
229 // insert new band or new separation?
230 if(STREAMENTRY_BANDHEADER == static_cast<StreamEntryType>(nTmp16))
231 {
232 sal_Int32 nYTop(0);
233 sal_Int32 nYBottom(0);
234
235 rIStrm.ReadInt32( nYTop );
236 rIStrm.ReadInt32( nYBottom );
237
238 // create band
239 ImplRegionBand* pNewBand = new ImplRegionBand( nYTop, nYBottom );
240
241 // first element? -> set as first into the list
242 if ( !pCurrBand )
243 {
244 mpFirstBand = pNewBand;
245 }
246 else
247 {
248 pCurrBand->mpNextBand = pNewBand;
249 }
250
251 // save pointer for next creation
252 pCurrBand = pNewBand;
253 }
254 else
255 {
256 sal_Int32 nXLeft(0);
257 sal_Int32 nXRight(0);
258
259 rIStrm.ReadInt32( nXLeft );
260 rIStrm.ReadInt32( nXRight );
261
262 // add separation
263 if ( pCurrBand )
264 {
265 pCurrBand->Union( nXLeft, nXRight );
266 }
267 }
268
269 if( rIStrm.eof() )
270 {
271 OSL_ENSURE(false, "premature end of region stream" );
272 implReset();
273 return false;
274 }
275
276 // get next header
277 rIStrm.ReadUInt16( nTmp16 );
278 }
279 while (STREAMENTRY_END != static_cast<StreamEntryType>(nTmp16) && rIStrm.good());
280 if (!CheckConsistency())
281 {
282 implReset();
283 return false;
284 }
285 return true;
286}
287
288void RegionBand::save(SvStream& rOStrm) const
289{
291
292 while(pBand)
293 {
294 // put boundaries
295 rOStrm.WriteUInt16( STREAMENTRY_BANDHEADER );
296 rOStrm.WriteInt32( pBand->mnYTop );
297 rOStrm.WriteInt32( pBand->mnYBottom );
298
299 // put separations of current band
300 ImplRegionBandSep* pSep = pBand->mpFirstSep;
301
302 while(pSep)
303 {
304 // put separation
305 rOStrm.WriteUInt16( STREAMENTRY_SEPARATION );
306 rOStrm.WriteInt32( pSep->mnXLeft );
307 rOStrm.WriteInt32( pSep->mnXRight );
308
309 // next separation from current band
310 pSep = pSep->mpNextSep;
311 }
312
313 pBand = pBand->mpNextBand;
314 }
315
316 // put endmarker
317 rOStrm.WriteUInt16( STREAMENTRY_END );
318}
319
321{
322 // just one band?
324 {
325 // just one sep?
327 {
328 return true;
329 }
330 }
331
332 return false;
333}
334
335void RegionBand::InsertBand(ImplRegionBand* pPreviousBand, ImplRegionBand* pBandToInsert)
336{
337 OSL_ASSERT(pBandToInsert!=nullptr);
338
339 if(!pPreviousBand)
340 {
341 // Insert band before all others.
342 if(mpFirstBand)
343 {
344 mpFirstBand->mpPrevBand = pBandToInsert;
345 }
346
347 pBandToInsert->mpNextBand = mpFirstBand;
348 mpFirstBand = pBandToInsert;
349 }
350 else
351 {
352 // Insert band directly after pPreviousBand.
353 pBandToInsert->mpNextBand = pPreviousBand->mpNextBand;
354 pPreviousBand->mpNextBand = pBandToInsert;
355 pBandToInsert->mpPrevBand = pPreviousBand;
356 }
357
358}
359
361{
362 ImplRegionBand* pRegionBand = mpFirstBand;
363
364 while(pRegionBand)
365 {
366 // generate separations from the lines and process union
367 pRegionBand->ProcessPoints();
368 pRegionBand = pRegionBand->mpNextBand;
369 }
370
371}
372
378{
379 // Iterate over already existing bands and add missing bands atop the
380 // first and between two bands.
381 ImplRegionBand* pPreviousBand = nullptr;
383 tools::Long nCurrentTop (nTop);
384
385 while (pBand != nullptr && nCurrentTop<nBottom)
386 {
387 if (nCurrentTop < pBand->mnYTop)
388 {
389 // Create new band above the current band.
390 ImplRegionBand* pAboveBand = new ImplRegionBand(
391 nCurrentTop,
392 ::std::min(nBottom,pBand->mnYTop-1));
393 InsertBand(pPreviousBand, pAboveBand);
394 }
395
396 // Adapt the top of the interval to prevent overlapping bands.
397 nCurrentTop = ::std::max(nTop, pBand->mnYBottom+1);
398
399 // Advance to next band.
400 pPreviousBand = pBand;
401 pBand = pBand->mpNextBand;
402 }
403
404 // We still have to cover two cases:
405 // 1. The region does not yet contain any bands.
406 // 2. The interval nTop->nBottom extends past the bottom most band.
407 if (nCurrentTop <= nBottom
408 && (pBand==nullptr || nBottom>pBand->mnYBottom))
409 {
410 // When there is no previous band then the new one will be the
411 // first. Otherwise the new band is inserted behind the last band.
413 pPreviousBand,
414 new ImplRegionBand(
415 nCurrentTop,
416 nBottom));
417 }
418
419}
420
422{
423 // add top band
424 mpFirstBand = new ImplRegionBand( nYTop-1, nYTop-1 );
425
426 // begin first search from the first element
429
430 for ( tools::Long i = nYTop; i <= nYBottom+1; i++ )
431 {
432 // create new band
433 ImplRegionBand* pNewBand = new ImplRegionBand( i, i );
434 pBand->mpNextBand = pNewBand;
435
436 if ( pBand != mpFirstBand )
437 {
438 pNewBand->mpPrevBand = pBand;
439 }
440
441 pBand = pBand->mpNextBand;
442 }
443
444}
445
446void RegionBand::InsertLine(const Point& rStartPt, const Point& rEndPt, tools::Long nLineId)
447{
448 tools::Long nX, nY;
449
450 // lines consisting of a single point do not interest here
451 if ( rStartPt == rEndPt )
452 {
453 return;
454 }
455
456 LineType eLineType = (rStartPt.Y() > rEndPt.Y()) ? LineType::Descending : LineType::Ascending;
457 if ( rStartPt.X() == rEndPt.X() )
458 {
459 // vertical line
460 const tools::Long nEndY = rEndPt.Y();
461
462 nX = rStartPt.X();
463 nY = rStartPt.Y();
464
465 if( nEndY > nY )
466 {
467 for ( ; nY <= nEndY; nY++ )
468 {
469 Point aNewPoint( nX, nY );
470 InsertPoint( aNewPoint, nLineId,
471 (aNewPoint == rEndPt) || (aNewPoint == rStartPt),
472 eLineType );
473 }
474 }
475 else
476 {
477 for ( ; nY >= nEndY; nY-- )
478 {
479 Point aNewPoint( nX, nY );
480 InsertPoint( aNewPoint, nLineId,
481 (aNewPoint == rEndPt) || (aNewPoint == rStartPt),
482 eLineType );
483 }
484 }
485 }
486 else if ( rStartPt.Y() != rEndPt.Y() )
487 {
488 const tools::Long nDX = std::abs( rEndPt.X() - rStartPt.X() );
489 const tools::Long nDY = std::abs( rEndPt.Y() - rStartPt.Y() );
490 const tools::Long nStartX = rStartPt.X();
491 const tools::Long nStartY = rStartPt.Y();
492 const tools::Long nEndX = rEndPt.X();
493 const tools::Long nEndY = rEndPt.Y();
494 const tools::Long nXInc = ( nStartX < nEndX ) ? 1 : -1;
495 const tools::Long nYInc = ( nStartY < nEndY ) ? 1 : -1;
496
497 if ( nDX >= nDY )
498 {
499 const tools::Long nDYX = ( nDY - nDX ) * 2;
500 const tools::Long nDY2 = nDY << 1;
501 tools::Long nD = nDY2 - nDX;
502
503 for ( nX = nStartX, nY = nStartY; nX != nEndX; nX += nXInc )
504 {
505 InsertPoint( Point( nX, nY ), nLineId, nStartX == nX, eLineType );
506
507 if ( nD < 0 )
508 nD += nDY2;
509 else
510 {
511 nD += nDYX;
512 nY += nYInc;
513 }
514 }
515 }
516 else
517 {
518 const tools::Long nDYX = ( nDX - nDY ) * 2;
519 const tools::Long nDY2 = nDX << 1;
520 tools::Long nD = nDY2 - nDY;
521
522 for ( nX = nStartX, nY = nStartY; nY != nEndY; nY += nYInc )
523 {
524 InsertPoint( Point( nX, nY ), nLineId, nStartY == nY, eLineType );
525
526 if ( nD < 0 )
527 nD += nDY2;
528 else
529 {
530 nD += nDYX;
531 nX += nXInc;
532 }
533 }
534 }
535
536 // last point
537 InsertPoint( Point( nEndX, nEndY ), nLineId, true, eLineType );
538 }
539}
540
541void RegionBand::InsertPoint(const Point &rPoint, tools::Long nLineID, bool bEndPoint, LineType eLineType)
542{
543 SAL_WARN_IF( mpFirstBand == nullptr, "vcl", "RegionBand::InsertPoint - no bands available!" );
544
545 if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
546 {
547 mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
548 return;
549 }
550
551 if ( rPoint.Y() > mpLastCheckedBand->mnYTop )
552 {
553 // Search ascending
554 while ( mpLastCheckedBand )
555 {
556 // Insert point if possible
557 if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
558 {
559 mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
560 return;
561 }
562
564 }
565
566 OSL_ENSURE(false, "RegionBand::InsertPoint reached the end of the list!" );
567 }
568 else
569 {
570 // Search descending
571 while ( mpLastCheckedBand )
572 {
573 // Insert point if possible
574 if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
575 {
576 mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
577 return;
578 }
579
581 }
582
583 OSL_ENSURE(false, "RegionBand::InsertPoint reached the beginning of the list!" );
584 }
585
586 OSL_ENSURE(false, "RegionBand::InsertPoint point not inserted!" );
587
588 // reinitialize pointer (should never be reached!)
590}
591
593{
594 ImplRegionBand* pPrevBand = nullptr;
596
597 while ( pBand )
598 {
599 const bool bBTEqual = pBand->mpNextBand && (pBand->mnYBottom == pBand->mpNextBand->mnYTop);
600
601 // no separation? -> remove!
602 if ( pBand->IsEmpty() || (bBTEqual && (pBand->mnYBottom == pBand->mnYTop)) )
603 {
604 // save pointer
605 ImplRegionBand* pOldBand = pBand;
606
607 // previous element of the list
608 if ( pBand == mpFirstBand )
609 mpFirstBand = pBand->mpNextBand;
610 else
611 pPrevBand->mpNextBand = pBand->mpNextBand;
612
613 pBand = pBand->mpNextBand;
614 delete pOldBand;
615 }
616 else
617 {
618 // fixup
619 if ( bBTEqual )
620 pBand->mnYBottom = pBand->mpNextBand->mnYTop-1;
621
622 // this and next band with equal separations? -> combine!
623 if ( pBand->mpNextBand &&
624 ((pBand->mnYBottom+1) == pBand->mpNextBand->mnYTop) &&
625 (*pBand == *pBand->mpNextBand) )
626 {
627 // expand current height
628 pBand->mnYBottom = pBand->mpNextBand->mnYBottom;
629
630 // remove next band from list
631 ImplRegionBand* pDeletedBand = pBand->mpNextBand;
632 pBand->mpNextBand = pDeletedBand->mpNextBand;
633 delete pDeletedBand;
634
635 // check band again!
636 }
637 else
638 {
639 // count rectangles within band
640 ImplRegionBandSep* pSep = pBand->mpFirstSep;
641 while ( pSep )
642 {
643 pSep = pSep->mpNextSep;
644 }
645
646 pPrevBand = pBand;
647 pBand = pBand->mpNextBand;
648 }
649 }
650 }
651
652#ifdef DBG_UTIL
653 pBand = mpFirstBand;
654 while ( pBand )
655 {
656 SAL_WARN_IF( pBand->mpFirstSep == nullptr, "vcl", "Exiting RegionBand::OptimizeBandList(): empty band in region!" );
657
658 if ( pBand->mnYBottom < pBand->mnYTop )
659 OSL_ENSURE(false, "RegionBand::OptimizeBandList(): YBottomBoundary < YTopBoundary" );
660
661 if ( pBand->mpNextBand && pBand->mnYBottom >= pBand->mpNextBand->mnYTop )
662 OSL_ENSURE(false, "RegionBand::OptimizeBandList(): overlapping bands in region!" );
663
664 pBand = pBand->mpNextBand;
665 }
666#endif
667
668 return (nullptr != mpFirstBand);
669}
670
671void RegionBand::Move(tools::Long nHorzMove, tools::Long nVertMove)
672{
674
675 while(pBand)
676 {
677 // process the vertical move
678 if(nVertMove)
679 {
680 pBand->mnYTop = o3tl::saturating_add(pBand->mnYTop, nVertMove);
681 pBand->mnYBottom = o3tl::saturating_add(pBand->mnYBottom, nVertMove);
682 }
683
684 // process the horizontal move
685 if(nHorzMove)
686 {
687 pBand->MoveX(nHorzMove);
688 }
689
690 pBand = pBand->mpNextBand;
691 }
692
693}
694
695void RegionBand::Scale(double fScaleX, double fScaleY)
696{
698
699 while(pBand)
700 {
701 // process the vertical move
702 if(0.0 != fScaleY)
703 {
704 pBand->mnYTop = basegfx::fround(pBand->mnYTop * fScaleY);
705 pBand->mnYBottom = basegfx::fround(pBand->mnYBottom * fScaleY);
706 }
707
708 // process the horizontal move
709 if(0.0 != fScaleX)
710 {
711 pBand->ScaleX(fScaleX);
712 }
713
714 pBand = pBand->mpNextBand;
715 }
716
717}
718
720{
721 // region empty? -> set rectangle as first entry!
722 if ( !mpFirstBand )
723 {
724 // add band with boundaries of the rectangle
725 mpFirstBand = new ImplRegionBand( nTop, nBottom );
726 return;
727 }
728
729 // find/insert bands for the boundaries of the rectangle
730 bool bTopBoundaryInserted = false;
731 bool bTop2BoundaryInserted = false;
732 bool bBottomBoundaryInserted = false;
733
734 // special case: top boundary is above the first band
735 ImplRegionBand* pNewBand;
736
737 if ( nTop < mpFirstBand->mnYTop )
738 {
739 // create new band above the first in the list
740 pNewBand = new ImplRegionBand( nTop, mpFirstBand->mnYTop );
741
742 if ( nBottom < mpFirstBand->mnYTop )
743 {
744 pNewBand->mnYBottom = nBottom;
745 }
746
747 // insert band into the list
748 pNewBand->mpNextBand = mpFirstBand;
749 mpFirstBand = pNewBand;
750
751 bTopBoundaryInserted = true;
752 }
753
754 // insert band(s) into the list
756
757 while ( pBand )
758 {
759 // Insert Bands if possible
760 if ( !bTopBoundaryInserted )
761 {
762 bTopBoundaryInserted = InsertSingleBand( pBand, nTop - 1 );
763 }
764
765 if ( !bTop2BoundaryInserted )
766 {
767 bTop2BoundaryInserted = InsertSingleBand( pBand, nTop );
768 }
769
770 if ( !bBottomBoundaryInserted && (nTop != nBottom) )
771 {
772 bBottomBoundaryInserted = InsertSingleBand( pBand, nBottom );
773 }
774
775 // both boundaries inserted? -> nothing more to do
776 if ( bTopBoundaryInserted && bTop2BoundaryInserted && bBottomBoundaryInserted )
777 {
778 break;
779 }
780
781 // insert bands between two bands if necessary
782 if ( pBand->mpNextBand )
783 {
784 if ( (pBand->mnYBottom + 1) < pBand->mpNextBand->mnYTop )
785 {
786 // copy band with list and set new boundary
787 pNewBand = new ImplRegionBand( pBand->mnYBottom+1, pBand->mpNextBand->mnYTop-1 );
788
789 // insert band into the list
790 pNewBand->mpNextBand = pBand->mpNextBand;
791 pBand->mpNextBand = pNewBand;
792 }
793 }
794
795 pBand = pBand->mpNextBand;
796 }
797
798}
799
801{
802 // boundary already included in band with height 1? -> nothing to do!
803 if ( (pBand->mnYTop == pBand->mnYBottom) && (nYBandPosition == pBand->mnYTop) )
804 {
805 return true;
806 }
807
808 // insert single height band on top?
809 ImplRegionBand* pNewBand;
810
811 if ( nYBandPosition == pBand->mnYTop )
812 {
813 // copy band with list and set new boundary
814 pNewBand = new ImplRegionBand( *pBand );
815 pNewBand->mnYTop = nYBandPosition+1;
816
817 // insert band into the list
818 pNewBand->mpNextBand = pBand->mpNextBand;
819 pBand->mnYBottom = nYBandPosition;
820 pBand->mpNextBand = pNewBand;
821
822 return true;
823 }
824
825 // top of new rectangle within the current band? -> insert new band and copy data
826 if ( (nYBandPosition > pBand->mnYTop) && (nYBandPosition < pBand->mnYBottom) )
827 {
828 // copy band with list and set new boundary
829 pNewBand = new ImplRegionBand( *pBand );
830 pNewBand->mnYTop = nYBandPosition;
831
832 // insert band into the list
833 pNewBand->mpNextBand = pBand->mpNextBand;
834 pBand->mnYBottom = nYBandPosition;
835 pBand->mpNextBand = pNewBand;
836
837 // copy band with list and set new boundary
838 pNewBand = new ImplRegionBand( *pBand );
839 pNewBand->mnYTop = nYBandPosition;
840
841 // insert band into the list
842 pBand->mpNextBand->mnYTop = nYBandPosition+1;
843
844 pNewBand->mpNextBand = pBand->mpNextBand;
845 pBand->mnYBottom = nYBandPosition - 1;
846 pBand->mpNextBand = pNewBand;
847
848 return true;
849 }
850
851 // create new band behind the current in the list
852 if ( !pBand->mpNextBand )
853 {
854 if ( nYBandPosition == pBand->mnYBottom )
855 {
856 // copy band with list and set new boundary
857 pNewBand = new ImplRegionBand( *pBand );
858 pNewBand->mnYTop = pBand->mnYBottom;
859 pNewBand->mnYBottom = nYBandPosition;
860
861 pBand->mnYBottom = nYBandPosition-1;
862
863 // append band to the list
864 pBand->mpNextBand = pNewBand;
865 return true;
866 }
867
868 if ( nYBandPosition > pBand->mnYBottom )
869 {
870 // create new band
871 pNewBand = new ImplRegionBand( pBand->mnYBottom + 1, nYBandPosition );
872
873 // append band to the list
874 pBand->mpNextBand = pNewBand;
875 return true;
876 }
877 }
878
879 return false;
880}
881
883{
884 SAL_WARN_IF( nLeft > nRight, "vcl", "RegionBand::Union() - nLeft > nRight" );
885 SAL_WARN_IF( nTop > nBottom, "vcl", "RegionBand::Union() - nTop > nBottom" );
886
887 // process union
889 while ( pBand )
890 {
891 if ( pBand->mnYTop >= nTop )
892 {
893 if ( pBand->mnYBottom <= nBottom )
894 pBand->Union( nLeft, nRight );
895 else
896 {
897#ifdef DBG_UTIL
898 tools::Long nCurY = pBand->mnYBottom;
899 pBand = pBand->mpNextBand;
900 while ( pBand )
901 {
902 if ( (pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY) )
903 {
904 OSL_ENSURE(false, "RegionBand::Union() - Bands not sorted!" );
905 }
906 pBand = pBand->mpNextBand;
907 }
908#endif
909 break;
910 }
911 }
912
913 pBand = pBand->mpNextBand;
914 }
915
916}
917
919{
920 // process intersections
921 ImplRegionBand* pPrevBand = nullptr;
923
924 while(pBand)
925 {
926 // band within intersection boundary? -> process. otherwise remove
927 if((pBand->mnYTop >= nTop) && (pBand->mnYBottom <= nBottom))
928 {
929 // process intersection
930 pBand->Intersect(nLeft, nRight);
931 pPrevBand = pBand;
932 pBand = pBand->mpNextBand;
933 }
934 else
935 {
936 ImplRegionBand* pOldBand = pBand;
937
938 if(pBand == mpFirstBand)
939 {
940 mpFirstBand = pBand->mpNextBand;
941 }
942 else
943 {
944 pPrevBand->mpNextBand = pBand->mpNextBand;
945 }
946
947 pBand = pBand->mpNextBand;
948 delete pOldBand;
949 }
950 }
951
952}
953
954void RegionBand::Union(const RegionBand& rSource)
955{
956 // apply all rectangles from rSource to this
957 ImplRegionBand* pBand = rSource.mpFirstBand;
958
959 while ( pBand )
960 {
961 // insert bands if the boundaries are not already in the list
962 InsertBands(pBand->mnYTop, pBand->mnYBottom);
963
964 // process all elements of the list
965 ImplRegionBandSep* pSep = pBand->mpFirstSep;
966
967 while(pSep)
968 {
969 Union(pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom);
970 pSep = pSep->mpNextSep;
971 }
972
973 pBand = pBand->mpNextBand;
974 }
975
976}
977
979{
980 SAL_WARN_IF( nLeft > nRight, "vcl", "RegionBand::Exclude() - nLeft > nRight" );
981 SAL_WARN_IF( nTop > nBottom, "vcl", "RegionBand::Exclude() - nTop > nBottom" );
982
983 // process exclude
985
986 while(pBand)
987 {
988 if(pBand->mnYTop >= nTop)
989 {
990 if(pBand->mnYBottom <= nBottom)
991 {
992 pBand->Exclude(nLeft, nRight);
993 }
994 else
995 {
996#ifdef DBG_UTIL
997 tools::Long nCurY = pBand->mnYBottom;
998 pBand = pBand->mpNextBand;
999
1000 while(pBand)
1001 {
1002 if((pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY))
1003 {
1004 OSL_ENSURE(false, "RegionBand::Exclude() - Bands not sorted!" );
1005 }
1006
1007 pBand = pBand->mpNextBand;
1008 }
1009#endif
1010 break;
1011 }
1012 }
1013
1014 pBand = pBand->mpNextBand;
1015 }
1016
1017}
1018
1020{
1021 SAL_WARN_IF( nLeft > nRight, "vcl", "RegionBand::Exclude() - nLeft > nRight" );
1022 SAL_WARN_IF( nTop > nBottom, "vcl", "RegionBand::Exclude() - nTop > nBottom" );
1023
1024 // process xor
1025 ImplRegionBand* pBand = mpFirstBand;
1026
1027 while(pBand)
1028 {
1029 if(pBand->mnYTop >= nTop)
1030 {
1031 if(pBand->mnYBottom <= nBottom)
1032 {
1033 pBand->XOr(nLeft, nRight);
1034 }
1035 else
1036 {
1037#ifdef DBG_UTIL
1038 tools::Long nCurY = pBand->mnYBottom;
1039 pBand = pBand->mpNextBand;
1040
1041 while(pBand)
1042 {
1043 if((pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY))
1044 {
1045 OSL_ENSURE(false, "RegionBand::XOr() - Bands not sorted!" );
1046 }
1047
1048 pBand = pBand->mpNextBand;
1049 }
1050#endif
1051 break;
1052 }
1053 }
1054
1055 pBand = pBand->mpNextBand;
1056 }
1057
1058}
1059
1061{
1062 // mark all bands as untouched
1063 ImplRegionBand* pBand = mpFirstBand;
1064
1065 while ( pBand )
1066 {
1067 pBand->mbTouched = false;
1068 pBand = pBand->mpNextBand;
1069 }
1070
1071 pBand = rSource.mpFirstBand;
1072
1073 while ( pBand )
1074 {
1075 // insert bands if the boundaries are not already in the list
1076 InsertBands( pBand->mnYTop, pBand->mnYBottom );
1077
1078 // process all elements of the list
1079 ImplRegionBandSep* pSep = pBand->mpFirstSep;
1080
1081 while ( pSep )
1082 {
1083 // left boundary?
1084 if ( pSep == pBand->mpFirstSep )
1085 {
1086 // process intersection and do not remove untouched bands
1087 Exclude( LONG_MIN+1, pBand->mnYTop, pSep->mnXLeft-1, pBand->mnYBottom );
1088 }
1089
1090 // right boundary?
1091 if ( pSep->mpNextSep == nullptr )
1092 {
1093 // process intersection and do not remove untouched bands
1094 Exclude( pSep->mnXRight+1, pBand->mnYTop, LONG_MAX-1, pBand->mnYBottom );
1095 }
1096 else
1097 {
1098 // process intersection and do not remove untouched bands
1099 Exclude( pSep->mnXRight+1, pBand->mnYTop, pSep->mpNextSep->mnXLeft-1, pBand->mnYBottom );
1100 }
1101
1102 pSep = pSep->mpNextSep;
1103 }
1104
1105 pBand = pBand->mpNextBand;
1106 }
1107
1108 // remove all untouched bands if bands already left
1109 ImplRegionBand* pPrevBand = nullptr;
1110 pBand = mpFirstBand;
1111
1112 while ( pBand )
1113 {
1114 if ( !pBand->mbTouched )
1115 {
1116 // save pointer
1117 ImplRegionBand* pOldBand = pBand;
1118
1119 // previous element of the list
1120 if ( pBand == mpFirstBand )
1121 {
1122 mpFirstBand = pBand->mpNextBand;
1123 }
1124 else
1125 {
1126 pPrevBand->mpNextBand = pBand->mpNextBand;
1127 }
1128
1129 pBand = pBand->mpNextBand;
1130 delete pOldBand;
1131 }
1132 else
1133 {
1134 pPrevBand = pBand;
1135 pBand = pBand->mpNextBand;
1136 }
1137 }
1138
1139}
1140
1142{
1143 // apply all rectangles to the region passed to this region
1144 ImplRegionBand* pBand = rSource.mpFirstBand;
1145
1146 while ( pBand )
1147 {
1148 // insert bands if the boundaries are not already in the list
1149 InsertBands( pBand->mnYTop, pBand->mnYBottom );
1150
1151 // process all elements of the list
1152 ImplRegionBandSep* pSep = pBand->mpFirstSep;
1153
1154 while ( pSep )
1155 {
1156 Exclude( pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom );
1157 pSep = pSep->mpNextSep;
1158 }
1159
1160 // to test less bands, already check in the loop
1161 if ( !OptimizeBandList() )
1162 {
1163 return false;
1164 }
1165
1166 pBand = pBand->mpNextBand;
1167 }
1168
1169 return true;
1170}
1171
1173{
1174 if (!mpFirstBand)
1175 return true;
1176 // look in the band list (don't test first band again!)
1177 const ImplRegionBand* pBand = mpFirstBand->mpNextBand;
1178 while (pBand)
1179 {
1180 if (!pBand->mpFirstSep)
1181 return false;
1182 pBand = pBand->mpNextBand;
1183 }
1184 return true;
1185}
1186
1188{
1189
1190 // get the boundaries of the first band
1195
1196 // look in the band list (don't test first band again!)
1198
1199 while ( pBand )
1200 {
1201 nYBottom = pBand->mnYBottom;
1202 nXLeft = std::min( nXLeft, pBand->GetXLeftBoundary() );
1203 nXRight = std::max( nXRight, pBand->GetXRightBoundary() );
1204
1205 pBand = pBand->mpNextBand;
1206 }
1207
1208 return tools::Rectangle( nXLeft, nYTop, nXRight, nYBottom );
1209}
1210
1211void RegionBand::XOr(const RegionBand& rSource)
1212{
1213 ImplRegionBand* pBand = rSource.mpFirstBand;
1214
1215 while ( pBand )
1216 {
1217 // insert bands if the boundaries are not already in the list
1218 InsertBands( pBand->mnYTop, pBand->mnYBottom );
1219
1220 // process all elements of the list
1221 ImplRegionBandSep* pSep = pBand->mpFirstSep;
1222
1223 while ( pSep )
1224 {
1225 XOr( pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom );
1226 pSep = pSep->mpNextSep;
1227 }
1228
1229 pBand = pBand->mpNextBand;
1230 }
1231}
1232
1233bool RegionBand::Contains(const Point& rPoint) const
1234{
1235
1236 // search band list
1237 ImplRegionBand* pBand = mpFirstBand;
1238
1239 while(pBand)
1240 {
1241 // is point within band?
1242 if((pBand->mnYTop <= rPoint.Y()) && (pBand->mnYBottom >= rPoint.Y()))
1243 {
1244 // is point within separation of the band?
1245 return pBand->Contains(rPoint.X());
1246 }
1247
1248 pBand = pBand->mpNextBand;
1249 }
1250
1251 return false;
1252}
1253
1255{
1256 // clear result vector
1257 rTarget.clear();
1258 ImplRegionBand* pCurrRectBand = mpFirstBand;
1259 tools::Rectangle aRectangle;
1260
1261 while(pCurrRectBand)
1262 {
1263 ImplRegionBandSep* pCurrRectBandSep = pCurrRectBand->mpFirstSep;
1264
1265 aRectangle.SetTop( pCurrRectBand->mnYTop );
1266 aRectangle.SetBottom( pCurrRectBand->mnYBottom );
1267
1268 while(pCurrRectBandSep)
1269 {
1270 aRectangle.SetLeft( pCurrRectBandSep->mnXLeft );
1271 aRectangle.SetRight( pCurrRectBandSep->mnXRight );
1272 rTarget.push_back(aRectangle);
1273 pCurrRectBandSep = pCurrRectBandSep->mpNextSep;
1274 }
1275
1276 pCurrRectBand = pCurrRectBand->mpNextBand;
1277 }
1278}
1279
1281{
1282 sal_uInt32 nCount = 0;
1283 const ImplRegionBand* pBand = mpFirstBand;
1284
1285 while(pBand)
1286 {
1287 ImplRegionBandSep* pSep = pBand->mpFirstSep;
1288
1289 while(pSep)
1290 {
1291 nCount++;
1292 pSep = pSep->mpNextSep;
1293 }
1294
1295 pBand = pBand->mpNextBand;
1296 }
1297
1298 return nCount;
1299}
1300
1301#ifdef DBG_UTIL
1302const char* ImplDbgTestRegionBand(const void* pObj)
1303{
1304 const RegionBand* pRegionBand = static_cast< const RegionBand* >(pObj);
1305
1306 if(pRegionBand)
1307 {
1308 const ImplRegionBand* pBand = pRegionBand->ImplGetFirstRegionBand();
1309
1310 while(pBand)
1311 {
1312 if(pBand->mnYBottom < pBand->mnYTop)
1313 {
1314 return "YBottom < YTop";
1315 }
1316
1317 if(pBand->mpNextBand)
1318 {
1319 if(pBand->mnYBottom >= pBand->mpNextBand->mnYTop)
1320 {
1321 return "overlapping bands in region";
1322 }
1323 }
1324
1325 if(pBand->mbTouched)
1326 {
1327 return "Band-mbTouched overwrite";
1328 }
1329
1330 ImplRegionBandSep* pSep = pBand->mpFirstSep;
1331
1332 while(pSep)
1333 {
1334 if(pSep->mnXRight < pSep->mnXLeft)
1335 {
1336 return "XLeft < XRight";
1337 }
1338
1339 if(pSep->mpNextSep)
1340 {
1341 if(pSep->mnXRight >= pSep->mpNextSep->mnXLeft)
1342 {
1343 return "overlapping separations in region";
1344 }
1345 }
1346
1347 if ( pSep->mbRemoved )
1348 {
1349 return "Sep-mbRemoved overwrite";
1350 }
1351
1352 pSep = pSep->mpNextSep;
1353 }
1354
1355 pBand = pBand->mpNextBand;
1356 }
1357 }
1358
1359 return nullptr;
1360}
1361#endif
1362
1363/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
LineType
void Union(tools::Long nXLeft, tools::Long nXRight)
Definition: regband.cxx:364
void Intersect(tools::Long nXLeft, tools::Long nXRight)
Definition: regband.cxx:436
ImplRegionBand * mpPrevBand
Definition: regband.hxx:61
tools::Long GetXRightBoundary() const
Definition: regband.cxx:823
void ProcessPoints()
Definition: regband.cxx:141
bool IsEmpty() const
Definition: regband.hxx:111
tools::Long mnYBottom
Definition: regband.hxx:65
bool InsertPoint(tools::Long nX, tools::Long nLineID, bool bEndPoint, LineType eLineType)
Definition: regband.cxx:192
void XOr(tools::Long nXLeft, tools::Long nXRight)
Definition: regband.cxx:559
void Exclude(tools::Long nXLeft, tools::Long nXRight)
Definition: regband.cxx:481
bool Contains(tools::Long nX)
Definition: regband.cxx:802
bool mbTouched
Definition: regband.hxx:67
tools::Long GetXLeftBoundary() const
Definition: regband.cxx:816
void MoveX(tools::Long nHorzMove)
Definition: regband.cxx:300
ImplRegionBand * mpNextBand
Definition: regband.hxx:60
tools::Long mnYTop
Definition: regband.hxx:64
void ScaleX(double fHorzScale)
Definition: regband.cxx:312
ImplRegionBandSep * mpFirstSep
Definition: regband.hxx:62
void InsertLine(const Point &rStartPt, const Point &rEndPt, tools::Long nLineId)
Definition: regionband.cxx:446
bool OptimizeBandList()
Definition: regionband.cxx:592
bool load(SvStream &rIStrm)
Definition: regionband.cxx:204
void Move(tools::Long nHorzMove, tools::Long nVertMove)
Definition: regionband.cxx:671
bool Contains(const Point &rPoint) const
void Scale(double fScaleX, double fScaleY)
Definition: regionband.cxx:695
void save(SvStream &rIStrm) const
Definition: regionband.cxx:288
ImplRegionBand * mpLastCheckedBand
Definition: regionband.hxx:36
void implReset()
Definition: regionband.cxx:88
void Union(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
Definition: regionband.cxx:882
void GetRegionRectangles(RectangleVector &rTarget) const
ImplRegionBand * mpFirstBand
Definition: regionband.hxx:35
void processPoints()
Definition: regionband.cxx:360
void InsertBand(ImplRegionBand *pPreviousBand, ImplRegionBand *pBandToInsert)
Definition: regionband.cxx:335
void InsertPoint(const Point &rPoint, tools::Long nLineID, bool bEndPoint, LineType eLineType)
Definition: regionband.cxx:541
tools::Rectangle GetBoundRect() const
bool CheckConsistency() const
ImplRegionBand * ImplGetFirstRegionBand() const
Definition: regionband.hxx:54
void InsertBands(tools::Long nTop, tools::Long nBottom)
Definition: regionband.cxx:719
void ImplAddMissingBands(const tools::Long nTop, const tools::Long nBottom)
This function is similar to the RegionBand::InsertBands() method.
Definition: regionband.cxx:377
RegionBand & operator=(const RegionBand &)
Definition: regionband.cxx:43
sal_uInt32 getRectangleCount() const
void XOr(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
void CreateBandRange(tools::Long nYTop, tools::Long nYBottom)
Definition: regionband.cxx:421
void Exclude(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
Definition: regionband.cxx:978
bool isSingleRectangle() const
Definition: regionband.cxx:320
void Intersect(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
Definition: regionband.cxx:918
static bool InsertSingleBand(ImplRegionBand *pBand, tools::Long nYBandPosition)
Definition: regionband.cxx:800
bool operator==(const RegionBand &rRegionBand) const
Definition: regionband.cxx:108
SvStream & WriteInt32(sal_Int32 nInt32)
bool good() const
bool eof() const
SvStream & WriteUInt16(sal_uInt16 nUInt16)
SvStream & ReadInt32(sal_Int32 &rInt32)
SvStream & ReadUInt16(sal_uInt16 &rUInt16)
sal_uInt64 remainingSize()
constexpr void SetLeft(tools::Long v)
constexpr void SetTop(tools::Long v)
constexpr tools::Long Top() const
constexpr void SetRight(tools::Long v)
constexpr tools::Long Right() const
constexpr void SetBottom(tools::Long v)
constexpr tools::Long Left() const
constexpr tools::Long Bottom() const
int nCount
FilterGroup & rTarget
const long LONG_MAX
#define SAL_WARN_IF(condition, area, stream)
B2IRange fround(const B2DRange &rRange)
int i
constexpr T saturating_add(T a, T b)
long Long
std::vector< tools::Rectangle > RectangleVector
Definition: region.hxx:34
const char * ImplDbgTestRegionBand(const void *pObj)
tools::Long mnXLeft
Definition: regband.hxx:40
ImplRegionBandSep * mpNextSep
Definition: regband.hxx:39
tools::Long mnXRight
Definition: regband.hxx:41