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