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