vcl/source/gdi/regionband.cxx

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