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 <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
  29 RegionBand::RegionBand()
  30 :   mpFirstBand(nullptr),
  31     mpLastCheckedBand(nullptr)
  32 {
  33 }
  34
  35 RegionBand::RegionBand(const RegionBand& rRef)
  36 :   mpFirstBand(nullptr),
  37     mpLastCheckedBand(nullptr)
  38 {
  39     *this = rRef;
  40 }
  41
  42 RegionBand& RegionBand::operator=(const RegionBand& rRef)
  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
  70 RegionBand::RegionBand(const tools::Rectangle& rRect)
  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
  87 void RegionBand::implReset()
  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
 102 RegionBand::~RegionBand()
 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
 203 bool RegionBand::load(SvStream& rIStrm)
 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
 319 bool RegionBand::isSingleRectangle() const
 320 {
 321     // just one band?
 322     if(mpFirstBand && !mpFirstBand->mpNextBand)
 323     {
 324         // just one sep?
 325         if(mpFirstBand->mpFirstSep && !mpFirstBand->mpFirstSep->mpNextSep)
 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
 359 void RegionBand::processPoints()
 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
 372 /** This function is similar to the RegionBand::InsertBands() method.
 373     It creates a minimal set of missing bands so that the entire vertical
 374     interval from nTop to nBottom is covered by bands.
 375 */
 376 void RegionBand::ImplAddMissingBands(const tools::Long nTop, const tools::Long nBottom)
 377 {
 378     // Iterate over already existing bands and add missing bands atop the
 379     // first and between two bands.
 380     ImplRegionBand* pPreviousBand = nullptr;
 381     ImplRegionBand* pBand = ImplGetFirstRegionBand();
 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
 420 void RegionBand::CreateBandRange(tools::Long nYTop, tools::Long nYBottom)
 421 {
 422     // add top band
 423     mpFirstBand = new ImplRegionBand( nYTop-1, nYTop-1 );
 424
 425     // begin first search from the first element
 426     mpLastCheckedBand = mpFirstBand;
 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
 562             mpLastCheckedBand = mpLastCheckedBand->mpNextBand;
 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
 579             mpLastCheckedBand = mpLastCheckedBand->mpPrevBand;
 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!)
 588     mpLastCheckedBand = mpFirstBand;
 589 }
 590
 591 bool RegionBand::OptimizeBandList()
 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
 718 void RegionBand::InsertBands(tools::Long nTop, tools::Long nBottom)
 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
 799 bool RegionBand::InsertSingleBand(ImplRegionBand* pBand, tools::Long nYBandPosition)
 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
 881 void RegionBand::Union(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
 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
 917 void RegionBand::Intersect(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
 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
 977 void RegionBand::Exclude(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
 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
1018 void RegionBand::XOr(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
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
1171 bool RegionBand::CheckConsistency() const
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
1186 tools::Rectangle RegionBand::GetBoundRect() const
1187 {
1188
1189     // get the boundaries of the first band
1190     tools::Long nYTop(mpFirstBand->mnYTop);
1191     tools::Long nYBottom(mpFirstBand->mnYBottom);
1192     tools::Long nXLeft(mpFirstBand->GetXLeftBoundary());
1193     tools::Long nXRight(mpFirstBand->GetXRightBoundary());
1194
1195     // look in the band list (don't test first band again!)
1196     ImplRegionBand* pBand = mpFirstBand->mpNextBand;
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
1253 void RegionBand::GetRegionRectangles(RectangleVector& rTarget) const
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
1279 sal_uInt32 RegionBand::getRectangleCount() const
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: */