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