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