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 neccessary
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 allready 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 allready 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 allready 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 allready 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 allready 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