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