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