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 450 : RegionBand::RegionBand()
25 : : mpFirstBand(0),
26 450 : mpLastCheckedBand(0)
27 : {
28 450 : }
29 :
30 1411651 : RegionBand::RegionBand(const RegionBand& rRef)
31 : : mpFirstBand(0),
32 1411651 : mpLastCheckedBand(0)
33 : {
34 1411651 : *this = rRef;
35 1411651 : }
36 :
37 1411651 : RegionBand& RegionBand::operator=(const RegionBand& rRef)
38 : {
39 1411651 : ImplRegionBand* pPrevBand = 0;
40 1411651 : ImplRegionBand* pBand = rRef.mpFirstBand;
41 :
42 4317543 : while(pBand)
43 : {
44 1494241 : ImplRegionBand* pNewBand = new ImplRegionBand(*pBand);
45 :
46 : // first element? -> set as first into the list
47 1494241 : if(pBand == rRef.mpFirstBand)
48 : {
49 1411651 : mpFirstBand = pNewBand;
50 : }
51 : else
52 : {
53 82590 : pPrevBand->mpNextBand = pNewBand;
54 : }
55 :
56 1494241 : pPrevBand = pNewBand;
57 1494241 : pBand = pBand->mpNextBand;
58 : }
59 :
60 1411651 : return *this;
61 : }
62 :
63 585633 : RegionBand::RegionBand(const Rectangle& rRect)
64 : : mpFirstBand(0),
65 585633 : mpLastCheckedBand(0)
66 : {
67 585633 : const long nTop(std::min(rRect.Top(), rRect.Bottom()));
68 585633 : const long nBottom(std::max(rRect.Top(), rRect.Bottom()));
69 585633 : const long nLeft(std::min(rRect.Left(), rRect.Right()));
70 585633 : const long nRight(std::max(rRect.Left(), rRect.Right()));
71 :
72 : // add band with boundaries of the rectangle
73 585633 : mpFirstBand = new ImplRegionBand(nTop, nBottom);
74 :
75 : // Set left and right boundaries of the band
76 585633 : mpFirstBand->Union(nLeft, nRight);
77 :
78 585633 : }
79 :
80 1997925 : void RegionBand::implReset()
81 : {
82 1997925 : ImplRegionBand* pBand = mpFirstBand;
83 :
84 5959707 : while(pBand)
85 : {
86 1963857 : ImplRegionBand* pTempBand = pBand->mpNextBand;
87 1963857 : delete pBand;
88 1963857 : pBand = pTempBand;
89 : }
90 :
91 1997925 : mpLastCheckedBand = 0;
92 :
93 1997925 : }
94 :
95 1997476 : RegionBand::~RegionBand()
96 : {
97 1997476 : implReset();
98 1997476 : }
99 :
100 18890 : bool RegionBand::operator==( const RegionBand& rRegionBand ) const
101 : {
102 :
103 : // initialise pointers
104 18890 : ImplRegionBand* pOwnRectBand = mpFirstBand;
105 18890 : ImplRegionBandSep* pOwnRectBandSep = pOwnRectBand->mpFirstSep;
106 18890 : ImplRegionBand* pSecondRectBand = rRegionBand.mpFirstBand;
107 18890 : ImplRegionBandSep* pSecondRectBandSep = pSecondRectBand->mpFirstSep;
108 :
109 38252 : while ( pOwnRectBandSep && pSecondRectBandSep )
110 : {
111 : // get boundaries of current rectangle
112 18890 : long nOwnXLeft = pOwnRectBandSep->mnXLeft;
113 18890 : long nSecondXLeft = pSecondRectBandSep->mnXLeft;
114 :
115 18890 : if ( nOwnXLeft != nSecondXLeft )
116 : {
117 10506 : return false;
118 : }
119 :
120 8384 : long nOwnYTop = pOwnRectBand->mnYTop;
121 8384 : long nSecondYTop = pSecondRectBand->mnYTop;
122 :
123 8384 : if ( nOwnYTop != nSecondYTop )
124 : {
125 3808 : return false;
126 : }
127 :
128 4576 : long nOwnXRight = pOwnRectBandSep->mnXRight;
129 4576 : long nSecondXRight = pSecondRectBandSep->mnXRight;
130 :
131 4576 : if ( nOwnXRight != nSecondXRight )
132 : {
133 2032 : return false;
134 : }
135 :
136 2544 : long nOwnYBottom = pOwnRectBand->mnYBottom;
137 2544 : long nSecondYBottom = pSecondRectBand->mnYBottom;
138 :
139 2544 : if ( nOwnYBottom != nSecondYBottom )
140 : {
141 2072 : return false;
142 : }
143 :
144 : // get next separation from current band
145 472 : pOwnRectBandSep = pOwnRectBandSep->mpNextSep;
146 :
147 : // no separation found? -> go to next band!
148 472 : if ( !pOwnRectBandSep )
149 : {
150 : // get next band
151 472 : pOwnRectBand = pOwnRectBand->mpNextBand;
152 :
153 : // get first separation in current band
154 472 : if( pOwnRectBand )
155 : {
156 0 : pOwnRectBandSep = pOwnRectBand->mpFirstSep;
157 : }
158 : }
159 :
160 : // get next separation from current band
161 472 : pSecondRectBandSep = pSecondRectBandSep->mpNextSep;
162 :
163 : // no separation found? -> go to next band!
164 472 : if ( !pSecondRectBandSep )
165 : {
166 : // get next band
167 472 : pSecondRectBand = pSecondRectBand->mpNextBand;
168 :
169 : // get first separation in current band
170 472 : if( pSecondRectBand )
171 : {
172 0 : pSecondRectBandSep = pSecondRectBand->mpFirstSep;
173 : }
174 : }
175 :
176 472 : if ( pOwnRectBandSep && !pSecondRectBandSep )
177 : {
178 0 : return false;
179 : }
180 :
181 472 : if ( !pOwnRectBandSep && pSecondRectBandSep )
182 : {
183 0 : return false;
184 : }
185 : }
186 :
187 472 : return true;
188 : }
189 :
190 : enum StreamEntryType { STREAMENTRY_BANDHEADER, STREAMENTRY_SEPARATION, STREAMENTRY_END };
191 :
192 449 : void RegionBand::load(SvStream& rIStrm)
193 : {
194 : // clear this nstance's data
195 449 : implReset();
196 :
197 : // get all bands
198 449 : ImplRegionBand* pCurrBand = 0;
199 :
200 : // get header from first element
201 449 : sal_uInt16 nTmp16(0);
202 449 : rIStrm.ReadUInt16( nTmp16 );
203 :
204 1794 : while(STREAMENTRY_END != (StreamEntryType)nTmp16)
205 : {
206 : // insert new band or new separation?
207 896 : if(STREAMENTRY_BANDHEADER == (StreamEntryType)nTmp16)
208 : {
209 448 : sal_Int32 nYTop(0);
210 448 : sal_Int32 nYBottom(0);
211 :
212 448 : rIStrm.ReadInt32( nYTop );
213 448 : rIStrm.ReadInt32( nYBottom );
214 :
215 : // create band
216 448 : ImplRegionBand* pNewBand = new ImplRegionBand( nYTop, nYBottom );
217 :
218 : // first element? -> set as first into the list
219 448 : if ( !pCurrBand )
220 : {
221 448 : mpFirstBand = pNewBand;
222 : }
223 : else
224 : {
225 0 : pCurrBand->mpNextBand = pNewBand;
226 : }
227 :
228 : // save pointer for next creation
229 448 : pCurrBand = pNewBand;
230 : }
231 : else
232 : {
233 448 : sal_Int32 nXLeft(0);
234 448 : sal_Int32 nXRight(0);
235 :
236 448 : rIStrm.ReadInt32( nXLeft );
237 448 : rIStrm.ReadInt32( nXRight );
238 :
239 : // add separation
240 448 : if ( pCurrBand )
241 : {
242 448 : pCurrBand->Union( nXLeft, nXRight );
243 : }
244 : }
245 :
246 896 : 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 896 : rIStrm.ReadUInt16( nTmp16 );
255 : }
256 :
257 : }
258 :
259 749 : void RegionBand::save(SvStream& rOStrm) const
260 : {
261 749 : ImplRegionBand* pBand = mpFirstBand;
262 :
263 2246 : while(pBand)
264 : {
265 : // put boundaries
266 748 : rOStrm.WriteUInt16( (sal_uInt16)STREAMENTRY_BANDHEADER );
267 748 : rOStrm.WriteInt32( static_cast<sal_Int32>(pBand->mnYTop) );
268 748 : rOStrm.WriteInt32( static_cast<sal_Int32>(pBand->mnYBottom) );
269 :
270 : // put separations of current band
271 748 : ImplRegionBandSep* pSep = pBand->mpFirstSep;
272 :
273 2244 : while(pSep)
274 : {
275 : // put separation
276 748 : rOStrm.WriteUInt16( (sal_uInt16)STREAMENTRY_SEPARATION );
277 748 : rOStrm.WriteInt32( static_cast<sal_Int32>(pSep->mnXLeft) );
278 748 : rOStrm.WriteInt32( static_cast<sal_Int32>(pSep->mnXRight) );
279 :
280 : // next separation from current band
281 748 : pSep = pSep->mpNextSep;
282 : }
283 :
284 748 : pBand = pBand->mpNextBand;
285 : }
286 :
287 : // put endmarker
288 749 : rOStrm.WriteUInt16( (sal_uInt16)STREAMENTRY_END );
289 749 : }
290 :
291 748 : bool RegionBand::isSingleRectangle() const
292 : {
293 : // just one band?
294 748 : if(mpFirstBand && !mpFirstBand->mpNextBand)
295 : {
296 : // just one sep?
297 748 : if(mpFirstBand->mpFirstSep && !mpFirstBand->mpFirstSep->mpNextSep)
298 : {
299 748 : return true;
300 : }
301 : }
302 :
303 0 : return false;
304 : }
305 :
306 0 : void RegionBand::InsertBand(ImplRegionBand* pPreviousBand, ImplRegionBand* pBandToInsert)
307 : {
308 : OSL_ASSERT(pBandToInsert!=NULL);
309 :
310 0 : if(!pPreviousBand)
311 : {
312 : // Insert band before all others.
313 0 : if(mpFirstBand)
314 : {
315 0 : mpFirstBand->mpPrevBand = pBandToInsert;
316 : }
317 :
318 0 : pBandToInsert->mpNextBand = mpFirstBand;
319 0 : 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 0 : }
330 :
331 0 : void RegionBand::processPoints()
332 : {
333 0 : ImplRegionBand* pRegionBand = mpFirstBand;
334 :
335 0 : while(pRegionBand)
336 : {
337 : // generate separations from the lines and process union
338 0 : pRegionBand->ProcessPoints();
339 0 : pRegionBand = pRegionBand->mpNextBand;
340 : }
341 :
342 0 : }
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 0 : 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 0 : ImplRegionBand* pPreviousBand = NULL;
353 0 : ImplRegionBand* pBand = ImplGetFirstRegionBand();
354 0 : long nCurrentTop (nTop);
355 :
356 0 : while (pBand != NULL && nCurrentTop<nBottom)
357 : {
358 0 : 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 0 : nCurrentTop = ::std::max(nTop, pBand->mnYBottom+1);
369 :
370 : // Advance to next band.
371 0 : pPreviousBand = pBand;
372 0 : 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 0 : if (nCurrentTop <= nBottom
379 0 : && (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 0 : nBottom));
388 : }
389 :
390 0 : }
391 :
392 0 : void RegionBand::CreateBandRange(long nYTop, long nYBottom)
393 : {
394 : // add top band
395 0 : mpFirstBand = new ImplRegionBand( nYTop-1, nYTop-1 );
396 :
397 : // begin first search from the first element
398 0 : mpLastCheckedBand = mpFirstBand;
399 0 : ImplRegionBand* pBand = mpFirstBand;
400 :
401 0 : for ( int i = nYTop; i <= nYBottom+1; i++ )
402 : {
403 : // create new band
404 0 : ImplRegionBand* pNewBand = new ImplRegionBand( i, i );
405 0 : pBand->mpNextBand = pNewBand;
406 :
407 0 : if ( pBand != mpFirstBand )
408 : {
409 0 : pNewBand->mpPrevBand = pBand;
410 : }
411 :
412 0 : pBand = pBand->mpNextBand;
413 : }
414 :
415 0 : }
416 :
417 0 : 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 0 : if ( rStartPt == rEndPt )
423 : {
424 0 : return true;
425 : }
426 :
427 0 : LineType eLineType = (rStartPt.Y() > rEndPt.Y()) ? LINE_DESCENDING : LINE_ASCENDING;
428 0 : if ( rStartPt.X() == rEndPt.X() )
429 : {
430 : // vertical line
431 0 : const long nEndY = rEndPt.Y();
432 :
433 0 : nX = rStartPt.X();
434 0 : nY = rStartPt.Y();
435 :
436 0 : if( nEndY > nY )
437 : {
438 0 : for ( ; nY <= nEndY; nY++ )
439 : {
440 0 : Point aNewPoint( nX, nY );
441 : InsertPoint( aNewPoint, nLineId,
442 0 : (aNewPoint == rEndPt) || (aNewPoint == rStartPt),
443 0 : eLineType );
444 : }
445 : }
446 : else
447 : {
448 0 : for ( ; nY >= nEndY; nY-- )
449 : {
450 0 : Point aNewPoint( nX, nY );
451 : InsertPoint( aNewPoint, nLineId,
452 0 : (aNewPoint == rEndPt) || (aNewPoint == rStartPt),
453 0 : eLineType );
454 : }
455 : }
456 : }
457 0 : else if ( rStartPt.Y() != rEndPt.Y() )
458 : {
459 0 : const long nDX = labs( rEndPt.X() - rStartPt.X() );
460 0 : const long nDY = labs( rEndPt.Y() - rStartPt.Y() );
461 0 : const long nStartX = rStartPt.X();
462 0 : const long nStartY = rStartPt.Y();
463 0 : const long nEndX = rEndPt.X();
464 0 : const long nEndY = rEndPt.Y();
465 0 : const long nXInc = ( nStartX < nEndX ) ? 1L : -1L;
466 0 : const long nYInc = ( nStartY < nEndY ) ? 1L : -1L;
467 :
468 0 : if ( nDX >= nDY )
469 : {
470 0 : const long nDYX = ( nDY - nDX ) << 1;
471 0 : const long nDY2 = nDY << 1;
472 0 : long nD = nDY2 - nDX;
473 :
474 0 : for ( nX = nStartX, nY = nStartY; nX != nEndX; nX += nXInc )
475 : {
476 0 : InsertPoint( Point( nX, nY ), nLineId, nStartX == nX, eLineType );
477 :
478 0 : if ( nD < 0L )
479 0 : nD += nDY2;
480 : else
481 0 : nD += nDYX, nY += nYInc;
482 : }
483 : }
484 : else
485 : {
486 0 : const long nDYX = ( nDX - nDY ) << 1;
487 0 : const long nDY2 = nDX << 1;
488 0 : long nD = nDY2 - nDY;
489 :
490 0 : for ( nX = nStartX, nY = nStartY; nY != nEndY; nY += nYInc )
491 : {
492 0 : InsertPoint( Point( nX, nY ), nLineId, nStartY == nY, eLineType );
493 :
494 0 : if ( nD < 0L )
495 0 : nD += nDY2;
496 : else
497 0 : nD += nDYX, nX += nXInc;
498 : }
499 : }
500 :
501 : // last point
502 0 : InsertPoint( Point( nEndX, nEndY ), nLineId, true, eLineType );
503 : }
504 :
505 0 : return true;
506 : }
507 :
508 0 : 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 0 : if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
513 : {
514 0 : mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
515 0 : return true;
516 : }
517 :
518 0 : if ( rPoint.Y() > mpLastCheckedBand->mnYTop )
519 : {
520 : // Search ascending
521 0 : while ( mpLastCheckedBand )
522 : {
523 : // Insert point if possible
524 0 : if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
525 : {
526 0 : mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
527 0 : return true;
528 : }
529 :
530 0 : 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 0 : while ( mpLastCheckedBand )
539 : {
540 : // Insert point if possible
541 0 : if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
542 : {
543 0 : mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
544 0 : return true;
545 : }
546 :
547 0 : 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 977340 : bool RegionBand::OptimizeBandList()
562 : {
563 977340 : ImplRegionBand* pPrevBand = 0;
564 977340 : ImplRegionBand* pBand = mpFirstBand;
565 :
566 5258491 : while ( pBand )
567 : {
568 3303811 : const bool bBTEqual = pBand->mpNextBand && (pBand->mnYBottom == pBand->mpNextBand->mnYTop);
569 :
570 : // no separation? -> remove!
571 3303811 : if ( pBand->IsEmpty() || (bBTEqual && (pBand->mnYBottom == pBand->mnYTop)) )
572 : {
573 : // save pointer
574 1244536 : ImplRegionBand* pOldBand = pBand;
575 :
576 : // previous element of the list
577 1244536 : if ( pBand == mpFirstBand )
578 914950 : mpFirstBand = pBand->mpNextBand;
579 : else
580 329586 : pPrevBand->mpNextBand = pBand->mpNextBand;
581 :
582 1244536 : pBand = pBand->mpNextBand;
583 1244536 : delete pOldBand;
584 : }
585 : else
586 : {
587 : // fixup
588 2059275 : if ( bBTEqual )
589 3149 : pBand->mnYBottom = pBand->mpNextBand->mnYTop-1;
590 :
591 : // this and next band with equal separations? -> combine!
592 3549706 : if ( pBand->mpNextBand &&
593 3548859 : ((pBand->mnYBottom+1) == pBand->mpNextBand->mnYTop) &&
594 1489584 : (*pBand == *pBand->mpNextBand) )
595 : {
596 : // expand current height
597 1124307 : pBand->mnYBottom = pBand->mpNextBand->mnYBottom;
598 :
599 : // remove next band from list
600 1124307 : ImplRegionBand* pDeletedBand = pBand->mpNextBand;
601 1124307 : pBand->mpNextBand = pDeletedBand->mpNextBand;
602 1124307 : delete pDeletedBand;
603 :
604 : // check band again!
605 : }
606 : else
607 : {
608 : // count rectangles within band
609 934968 : ImplRegionBandSep* pSep = pBand->mpFirstSep;
610 2862316 : while ( pSep )
611 : {
612 992380 : pSep = pSep->mpNextSep;
613 : }
614 :
615 934968 : pPrevBand = pBand;
616 934968 : 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 977340 : return (0 != mpFirstBand);
641 : }
642 :
643 434317 : void RegionBand::Move(long nHorzMove, long nVertMove)
644 : {
645 434317 : ImplRegionBand* pBand = mpFirstBand;
646 :
647 1311745 : while(pBand)
648 : {
649 : // process the vertical move
650 443111 : if(nVertMove)
651 : {
652 443084 : pBand->mnYTop = pBand->mnYTop + nVertMove;
653 443084 : pBand->mnYBottom = pBand->mnYBottom + nVertMove;
654 : }
655 :
656 : // process the horizontal move
657 443111 : if(nHorzMove)
658 : {
659 52254 : pBand->MoveX(nHorzMove);
660 : }
661 :
662 443111 : pBand = pBand->mpNextBand;
663 : }
664 :
665 434317 : }
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 988250 : void RegionBand::InsertBands(long nTop, long nBottom)
692 : {
693 : // region empty? -> set rectagle as first entry!
694 988250 : if ( !mpFirstBand )
695 : {
696 : // add band with boundaries of the rectangle
697 0 : mpFirstBand = new ImplRegionBand( nTop, nBottom );
698 988250 : return;
699 : }
700 :
701 : // find/insert bands for the boundaries of the rectangle
702 988250 : bool bTopBoundaryInserted = false;
703 988250 : bool bTop2BoundaryInserted = false;
704 988250 : bool bBottomBoundaryInserted = false;
705 :
706 : // special case: top boundary is above the first band
707 : ImplRegionBand* pNewBand;
708 :
709 988250 : if ( nTop < mpFirstBand->mnYTop )
710 : {
711 : // create new band above the first in the list
712 296880 : pNewBand = new ImplRegionBand( nTop, mpFirstBand->mnYTop );
713 :
714 296880 : if ( nBottom < mpFirstBand->mnYTop )
715 : {
716 25381 : pNewBand->mnYBottom = nBottom;
717 : }
718 :
719 : // insert band into the list
720 296880 : pNewBand->mpNextBand = mpFirstBand;
721 296880 : mpFirstBand = pNewBand;
722 :
723 296880 : bTopBoundaryInserted = true;
724 : }
725 :
726 : // insert band(s) into the list
727 988250 : ImplRegionBand* pBand = mpFirstBand;
728 :
729 4737624 : while ( pBand )
730 : {
731 : // Insert Bands if possible
732 3365668 : if ( !bTopBoundaryInserted )
733 : {
734 1532717 : bTopBoundaryInserted = InsertSingleBand( pBand, nTop - 1 );
735 : }
736 :
737 3365668 : if ( !bTop2BoundaryInserted )
738 : {
739 1639692 : bTop2BoundaryInserted = InsertSingleBand( pBand, nTop );
740 : }
741 :
742 3365668 : if ( !bBottomBoundaryInserted && (nTop != nBottom) )
743 : {
744 2983539 : bBottomBoundaryInserted = InsertSingleBand( pBand, nBottom );
745 : }
746 :
747 : // both boundaries inserted? -> nothing more to do
748 3365668 : if ( bTopBoundaryInserted && bTop2BoundaryInserted && bBottomBoundaryInserted )
749 : {
750 604544 : break;
751 : }
752 :
753 : // insert bands between two bands if necessary
754 2761124 : if ( pBand->mpNextBand )
755 : {
756 2377418 : if ( (pBand->mnYBottom + 1) < pBand->mpNextBand->mnYTop )
757 : {
758 : // copy band with list and set new boundary
759 30821 : pNewBand = new ImplRegionBand( pBand->mnYBottom+1, pBand->mpNextBand->mnYTop-1 );
760 :
761 : // insert band into the list
762 30821 : pNewBand->mpNextBand = pBand->mpNextBand;
763 30821 : pBand->mpNextBand = pNewBand;
764 : }
765 : }
766 :
767 2761124 : pBand = pBand->mpNextBand;
768 : }
769 :
770 : }
771 :
772 6155948 : bool RegionBand::InsertSingleBand(ImplRegionBand* pBand, long nYBandPosition)
773 : {
774 : // boundary already included in band with height 1? -> nothing to do!
775 6155948 : if ( (pBand->mnYTop == pBand->mnYBottom) && (nYBandPosition == pBand->mnYTop) )
776 : {
777 11022 : return true;
778 : }
779 :
780 : // insert single height band on top?
781 : ImplRegionBand* pNewBand;
782 :
783 6144926 : if ( nYBandPosition == pBand->mnYTop )
784 : {
785 : // copy band with list and set new boundary
786 909352 : pNewBand = new ImplRegionBand( *pBand );
787 909352 : pNewBand->mnYTop = nYBandPosition+1;
788 :
789 : // insert band into the list
790 909352 : pNewBand->mpNextBand = pBand->mpNextBand;
791 909352 : pBand->mnYBottom = nYBandPosition;
792 909352 : pBand->mpNextBand = pNewBand;
793 :
794 909352 : return true;
795 : }
796 :
797 : // top of new rectangle within the current band? -> insert new band and copy data
798 5235574 : if ( (nYBandPosition > pBand->mnYTop) && (nYBandPosition < pBand->mnYBottom) )
799 : {
800 : // copy band with list and set new boundary
801 512215 : pNewBand = new ImplRegionBand( *pBand );
802 512215 : pNewBand->mnYTop = nYBandPosition;
803 :
804 : // insert band into the list
805 512215 : pNewBand->mpNextBand = pBand->mpNextBand;
806 512215 : pBand->mnYBottom = nYBandPosition;
807 512215 : pBand->mpNextBand = pNewBand;
808 :
809 : // copy band with list and set new boundary
810 512215 : pNewBand = new ImplRegionBand( *pBand );
811 512215 : pNewBand->mnYTop = nYBandPosition;
812 :
813 : // insert band into the list
814 512215 : pBand->mpNextBand->mnYTop = nYBandPosition+1;
815 :
816 512215 : pNewBand->mpNextBand = pBand->mpNextBand;
817 512215 : pBand->mnYBottom = nYBandPosition - 1;
818 512215 : pBand->mpNextBand = pNewBand;
819 :
820 512215 : return true;
821 : }
822 :
823 : // create new band behind the current in the list
824 4723359 : if ( !pBand->mpNextBand )
825 : {
826 1901733 : if ( nYBandPosition == pBand->mnYBottom )
827 : {
828 : // copy band with list and set new boundary
829 319665 : pNewBand = new ImplRegionBand( *pBand );
830 319665 : pNewBand->mnYTop = pBand->mnYBottom;
831 319665 : pNewBand->mnYBottom = nYBandPosition;
832 :
833 319665 : pBand->mnYBottom = nYBandPosition-1;
834 :
835 : // append band to the list
836 319665 : pBand->mpNextBand = pNewBand;
837 319665 : return true;
838 : }
839 :
840 1582068 : if ( nYBandPosition > pBand->mnYBottom )
841 : {
842 : // create new band
843 517249 : pNewBand = new ImplRegionBand( pBand->mnYBottom + 1, nYBandPosition );
844 :
845 : // append band to the list
846 517249 : pBand->mpNextBand = pNewBand;
847 517249 : return true;
848 : }
849 : }
850 :
851 3886445 : return false;
852 : }
853 :
854 58924 : 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 58924 : ImplRegionBand* pBand = mpFirstBand;
861 335761 : while ( pBand )
862 : {
863 235585 : if ( pBand->mnYTop >= nTop )
864 : {
865 192240 : if ( pBand->mnYBottom <= nBottom )
866 174568 : 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 17672 : break;
882 : }
883 : }
884 :
885 217913 : pBand = pBand->mpNextBand;
886 : }
887 :
888 58924 : }
889 :
890 202931 : void RegionBand::Intersect(long nLeft, long nTop, long nRight, long nBottom)
891 : {
892 : // process intersections
893 202931 : ImplRegionBand* pPrevBand = 0;
894 202931 : ImplRegionBand* pBand = mpFirstBand;
895 :
896 1190718 : while(pBand)
897 : {
898 : // band within intersection boundary? -> process. otherwise remove
899 784856 : if((pBand->mnYTop >= nTop) && (pBand->mnYBottom <= nBottom))
900 : {
901 : // process intersection
902 633008 : pBand->Intersect(nLeft, nRight);
903 633008 : pPrevBand = pBand;
904 633008 : pBand = pBand->mpNextBand;
905 : }
906 : else
907 : {
908 151848 : ImplRegionBand* pOldBand = pBand;
909 :
910 151848 : if(pBand == mpFirstBand)
911 : {
912 148739 : mpFirstBand = pBand->mpNextBand;
913 : }
914 : else
915 : {
916 3109 : pPrevBand->mpNextBand = pBand->mpNextBand;
917 : }
918 :
919 151848 : pBand = pBand->mpNextBand;
920 151848 : delete pOldBand;
921 : }
922 : }
923 :
924 202931 : }
925 :
926 49323 : void RegionBand::Union(const RegionBand& rSource)
927 : {
928 : // apply all rectangles from rSource to this
929 49323 : ImplRegionBand* pBand = rSource.mpFirstBand;
930 :
931 150486 : while ( pBand )
932 : {
933 : // insert bands if the boundaries are not already in the list
934 51840 : InsertBands(pBand->mnYTop, pBand->mnYBottom);
935 :
936 : // process all elements of the list
937 51840 : ImplRegionBandSep* pSep = pBand->mpFirstSep;
938 :
939 155858 : while(pSep)
940 : {
941 52178 : Union(pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom);
942 52178 : pSep = pSep->mpNextSep;
943 : }
944 :
945 51840 : pBand = pBand->mpNextBand;
946 : }
947 :
948 49323 : }
949 :
950 1452183 : 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 1452183 : ImplRegionBand* pBand = mpFirstBand;
957 :
958 8584488 : while(pBand)
959 : {
960 6223448 : if(pBand->mnYTop >= nTop)
961 : {
962 5189926 : if(pBand->mnYBottom <= nBottom)
963 : {
964 4646600 : 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 543326 : break;
983 : }
984 : }
985 :
986 5680122 : pBand = pBand->mpNextBand;
987 : }
988 :
989 1452183 : }
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 622179 : void RegionBand::Intersect(const RegionBand& rSource)
1033 : {
1034 : // mark all bands as untouched
1035 622179 : ImplRegionBand* pBand = mpFirstBand;
1036 :
1037 1879623 : while ( pBand )
1038 : {
1039 635265 : pBand->mbTouched = false;
1040 635265 : pBand = pBand->mpNextBand;
1041 : }
1042 :
1043 622179 : pBand = rSource.mpFirstBand;
1044 :
1045 1874930 : while ( pBand )
1046 : {
1047 : // insert bands if the boundaries are not already in the list
1048 630572 : InsertBands( pBand->mnYTop, pBand->mnYBottom );
1049 :
1050 : // process all elements of the list
1051 630572 : ImplRegionBandSep* pSep = pBand->mpFirstSep;
1052 :
1053 1986594 : while ( pSep )
1054 : {
1055 : // left boundary?
1056 725450 : if ( pSep == pBand->mpFirstSep )
1057 : {
1058 : // process intersection and do not remove untouched bands
1059 630572 : Exclude( LONG_MIN+1, pBand->mnYTop, pSep->mnXLeft-1, pBand->mnYBottom );
1060 : }
1061 :
1062 : // right boundary?
1063 725450 : if ( pSep->mpNextSep == NULL )
1064 : {
1065 : // process intersection and do not remove untouched bands
1066 630572 : 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 94878 : Exclude( pSep->mnXRight+1, pBand->mnYTop, pSep->mpNextSep->mnXLeft-1, pBand->mnYBottom );
1072 : }
1073 :
1074 725450 : pSep = pSep->mpNextSep;
1075 : }
1076 :
1077 630572 : pBand = pBand->mpNextBand;
1078 : }
1079 :
1080 : // remove all untouched bands if bands already left
1081 622179 : ImplRegionBand* pPrevBand = 0;
1082 622179 : pBand = mpFirstBand;
1083 :
1084 3979896 : while ( pBand )
1085 : {
1086 2735538 : if ( !pBand->mbTouched )
1087 : {
1088 : // save pointer
1089 693878 : ImplRegionBand* pOldBand = pBand;
1090 :
1091 : // previous element of the list
1092 693878 : if ( pBand == mpFirstBand )
1093 : {
1094 438639 : mpFirstBand = pBand->mpNextBand;
1095 : }
1096 : else
1097 : {
1098 255239 : pPrevBand->mpNextBand = pBand->mpNextBand;
1099 : }
1100 :
1101 693878 : pBand = pBand->mpNextBand;
1102 693878 : delete pOldBand;
1103 : }
1104 : else
1105 : {
1106 2041660 : pPrevBand = pBand;
1107 2041660 : pBand = pBand->mpNextBand;
1108 : }
1109 : }
1110 :
1111 622179 : }
1112 :
1113 2349 : bool RegionBand::Exclude(const RegionBand& rSource)
1114 : {
1115 : // apply all rectangles to the region passed to this region
1116 2349 : ImplRegionBand* pBand = rSource.mpFirstBand;
1117 :
1118 7002 : while ( pBand )
1119 : {
1120 : // insert bands if the boundaries are not already in the list
1121 2355 : InsertBands( pBand->mnYTop, pBand->mnYBottom );
1122 :
1123 : // process all elements of the list
1124 2355 : ImplRegionBandSep* pSep = pBand->mpFirstSep;
1125 :
1126 7065 : while ( pSep )
1127 : {
1128 2355 : Exclude( pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom );
1129 2355 : pSep = pSep->mpNextSep;
1130 : }
1131 :
1132 : // to test less bands, already check in the loop
1133 2355 : if ( !OptimizeBandList() )
1134 : {
1135 51 : return false;
1136 : }
1137 :
1138 2304 : pBand = pBand->mpNextBand;
1139 : }
1140 :
1141 2298 : return true;
1142 : }
1143 :
1144 224685 : Rectangle RegionBand::GetBoundRect() const
1145 : {
1146 :
1147 : // get the boundaries of the first band
1148 224685 : long nYTop(mpFirstBand->mnYTop);
1149 224685 : long nYBottom(mpFirstBand->mnYBottom);
1150 224685 : long nXLeft(mpFirstBand->GetXLeftBoundary());
1151 224685 : long nXRight(mpFirstBand->GetXRightBoundary());
1152 :
1153 : // look in the band list (don't test first band again!)
1154 224685 : ImplRegionBand* pBand = mpFirstBand->mpNextBand;
1155 :
1156 457663 : while ( pBand )
1157 : {
1158 8293 : nYBottom = pBand->mnYBottom;
1159 8293 : nXLeft = std::min( nXLeft, pBand->GetXLeftBoundary() );
1160 8293 : nXRight = std::max( nXRight, pBand->GetXRightBoundary() );
1161 :
1162 8293 : pBand = pBand->mpNextBand;
1163 : }
1164 :
1165 224685 : 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 598225 : void RegionBand::GetRegionRectangles(RectangleVector& rTarget) const
1219 : {
1220 : // clear result vector
1221 598225 : rTarget.clear();
1222 598225 : ImplRegionBand* mpCurrRectBand = mpFirstBand;
1223 598225 : Rectangle aRectangle;
1224 :
1225 1820076 : while(mpCurrRectBand)
1226 : {
1227 623626 : ImplRegionBandSep* mpCurrRectBandSep = mpCurrRectBand->mpFirstSep;
1228 :
1229 623626 : aRectangle.Top() = mpCurrRectBand->mnYTop;
1230 623626 : aRectangle.Bottom() = mpCurrRectBand->mnYBottom;
1231 :
1232 2138470 : while(mpCurrRectBandSep)
1233 : {
1234 891218 : aRectangle.Left() = mpCurrRectBandSep->mnXLeft;
1235 891218 : aRectangle.Right() = mpCurrRectBandSep->mnXRight;
1236 891218 : rTarget.push_back(aRectangle);
1237 891218 : mpCurrRectBandSep = mpCurrRectBandSep->mpNextSep;
1238 : }
1239 :
1240 623626 : mpCurrRectBand = mpCurrRectBand->mpNextBand;
1241 : }
1242 598225 : }
1243 :
1244 1244358 : sal_uInt32 RegionBand::getRectangleCount() const
1245 : {
1246 1244358 : sal_uInt32 nCount = 0;
1247 1244358 : const ImplRegionBand* pBand = mpFirstBand;
1248 :
1249 3754553 : while(pBand)
1250 : {
1251 1265837 : ImplRegionBandSep* pSep = pBand->mpFirstSep;
1252 :
1253 4046998 : while(pSep)
1254 : {
1255 1515324 : nCount++;
1256 1515324 : pSep = pSep->mpNextSep;
1257 : }
1258 :
1259 1265837 : pBand = pBand->mpNextBand;
1260 : }
1261 :
1262 1244358 : 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: */
|
