vcl/source/gdi/regband.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/helpers.hxx>
  21 #include <osl/diagnose.h>
  22 #include <sal/log.hxx>
  23
  24 #include <regband.hxx>
  25
  26 // ImplRegionBand
  27
  28 // Each band contains all rectangles between upper and lower border.
  29 // For Union, Intersect, Xor and Exclude operations rectangles of
  30 // equal height are evaluated. The borders of the bands should always
  31 // be chosen such that this is possible.
  32
  33 // If possible, rectangles within the bands are condensed.
  34
  35 // When converting polygons all points of the polygon are registered
  36 // in the individual bands (for each band they are stored as
  37 // points in a list). After registration of these points they are
  38 // converted to rectangles and the points in the list are deleted.
  39
  40 ImplRegionBand::ImplRegionBand( long nTop, long nBottom )
  41 {
  42     // save boundaries
  43     mnYTop              = nTop;
  44     mnYBottom           = nBottom;
  45
  46     // initialize lists
  47     mpNextBand          = nullptr;
  48     mpPrevBand          = nullptr;
  49     mpFirstSep          = nullptr;
  50     mpFirstBandPoint    = nullptr;
  51     mbTouched           = false;
  52 }
  53
  54 ImplRegionBand::ImplRegionBand(
  55     const ImplRegionBand& rRegionBand,
  56     const bool bIgnorePoints)
  57 {
  58     // copy boundaries
  59     mnYTop              = rRegionBand.mnYTop;
  60     mnYBottom           = rRegionBand.mnYBottom;
  61     mbTouched           = rRegionBand.mbTouched;
  62
  63     // initialisation
  64     mpNextBand          = nullptr;
  65     mpPrevBand          = nullptr;
  66     mpFirstSep          = nullptr;
  67     mpFirstBandPoint    = nullptr;
  68
  69     // copy all elements of the list with separations
  70     ImplRegionBandSep* pNewSep;
  71     ImplRegionBandSep* pPrevSep = nullptr;
  72     ImplRegionBandSep* pSep = rRegionBand.mpFirstSep;
  73     while ( pSep )
  74     {
  75         // create new and copy data
  76         pNewSep             = new ImplRegionBandSep;
  77         pNewSep->mnXLeft    = pSep->mnXLeft;
  78         pNewSep->mnXRight   = pSep->mnXRight;
  79         pNewSep->mbRemoved  = pSep->mbRemoved;
  80         pNewSep->mpNextSep  = nullptr;
  81         if ( pSep == rRegionBand.mpFirstSep )
  82             mpFirstSep = pNewSep;
  83         else
  84             pPrevSep->mpNextSep = pNewSep;
  85
  86         pPrevSep = pNewSep;
  87         pSep = pSep->mpNextSep;
  88     }
  89
  90     if ( ! bIgnorePoints)
  91     {
  92         // Copy points.
  93         ImplRegionBandPoint* pPoint = rRegionBand.mpFirstBandPoint;
  94         ImplRegionBandPoint* pPrevPointCopy = nullptr;
  95         while (pPoint != nullptr)
  96         {
  97             ImplRegionBandPoint* pPointCopy = new ImplRegionBandPoint;
  98             pPointCopy->mpNextBandPoint = nullptr;
  99             pPointCopy->mnX = pPoint->mnX;
 100             pPointCopy->mnLineId = pPoint->mnLineId;
 101             pPointCopy->mbEndPoint = pPoint->mbEndPoint;
 102             pPointCopy->meLineType = pPoint->meLineType;
 103
 104             if (pPrevPointCopy != nullptr)
 105                 pPrevPointCopy->mpNextBandPoint = pPointCopy;
 106             else
 107                 mpFirstBandPoint = pPointCopy;
 108
 109             pPrevPointCopy = pPointCopy;
 110             pPoint = pPoint->mpNextBandPoint;
 111         }
 112     }
 113 }
 114
 115 ImplRegionBand::~ImplRegionBand()
 116 {
 117     SAL_WARN_IF( mpFirstBandPoint != nullptr, "vcl", "ImplRegionBand::~ImplRegionBand -> pointlist not empty" );
 118
 119     // delete elements of the list
 120     ImplRegionBandSep* pSep = mpFirstSep;
 121     while ( pSep )
 122     {
 123         ImplRegionBandSep* pTempSep = pSep->mpNextSep;
 124         delete pSep;
 125         pSep = pTempSep;
 126     }
 127
 128     // delete elements of the list
 129     ImplRegionBandPoint* pPoint = mpFirstBandPoint;
 130     while ( pPoint )
 131     {
 132         ImplRegionBandPoint* pTempPoint = pPoint->mpNextBandPoint;
 133         delete pPoint;
 134         pPoint = pTempPoint;
 135     }
 136 }
 137
 138 // generate separations from lines and process union with existing
 139 // separations
 140
 141 void ImplRegionBand::ProcessPoints()
 142 {
 143     // check Pointlist
 144     ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
 145     while ( pRegionBandPoint )
 146     {
 147         // within list?
 148         if ( pRegionBandPoint->mpNextBandPoint )
 149         {
 150             // start/stop?
 151             if ( pRegionBandPoint->mbEndPoint && pRegionBandPoint->mpNextBandPoint->mbEndPoint )
 152             {
 153                 // same direction? -> remove next point!
 154                 if ( pRegionBandPoint->meLineType == pRegionBandPoint->mpNextBandPoint->meLineType )
 155                 {
 156                     ImplRegionBandPoint* pSaveRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
 157                     pRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
 158                     delete pSaveRegionBandPoint;
 159                 }
 160             }
 161         }
 162
 163         // continue with next element in the list
 164         pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
 165     }
 166
 167     pRegionBandPoint = mpFirstBandPoint;
 168     while ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint )
 169     {
 170         Union( pRegionBandPoint->mnX, pRegionBandPoint->mpNextBandPoint->mnX );
 171
 172         ImplRegionBandPoint* pNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
 173
 174         // remove already processed points
 175         delete pRegionBandPoint->mpNextBandPoint;
 176         delete pRegionBandPoint;
 177
 178         // continue with next element in the list
 179         pRegionBandPoint = pNextBandPoint;
 180     }
 181
 182     // remove last element if necessary
 183     delete pRegionBandPoint;
 184
 185     // list is now empty
 186     mpFirstBandPoint = nullptr;
 187 }
 188
 189 // generate separations from lines and process union with existing
 190 // separations
 191
 192 bool ImplRegionBand::InsertPoint( long nX, long nLineId,
 193                                   bool bEndPoint, LineType eLineType )
 194 {
 195     if ( !mpFirstBandPoint )
 196     {
 197         mpFirstBandPoint                  = new ImplRegionBandPoint;
 198         mpFirstBandPoint->mnX             = nX;
 199         mpFirstBandPoint->mnLineId        = nLineId;
 200         mpFirstBandPoint->mbEndPoint      = bEndPoint;
 201         mpFirstBandPoint->meLineType      = eLineType;
 202         mpFirstBandPoint->mpNextBandPoint = nullptr;
 203         return true;
 204     }
 205
 206     // look if line already touched the band
 207     ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
 208     ImplRegionBandPoint* pLastTestedRegionBandPoint = nullptr;
 209     while( pRegionBandPoint )
 210     {
 211         if ( pRegionBandPoint->mnLineId == nLineId )
 212         {
 213             if ( bEndPoint )
 214             {
 215                 if( !pRegionBandPoint->mbEndPoint )
 216                 {
 217                     // remove old band point
 218                     if( !mpFirstBandPoint->mpNextBandPoint )
 219                     {
 220                         // if we've only got one point => replace first point
 221                         pRegionBandPoint->mnX = nX;
 222                         pRegionBandPoint->mbEndPoint = true;
 223                         return true;
 224                     }
 225                     else
 226                     {
 227                         // remove current point
 228                         if( !pLastTestedRegionBandPoint )
 229                         {
 230                             // remove and delete old first point
 231                             ImplRegionBandPoint* pSaveBandPoint = mpFirstBandPoint;
 232                             mpFirstBandPoint = mpFirstBandPoint->mpNextBandPoint;
 233                             delete pSaveBandPoint;
 234                         }
 235                         else
 236                         {
 237                             // remove and delete current band point
 238                             pLastTestedRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint;
 239                             delete pRegionBandPoint;
 240                         }
 241
 242                         break;
 243                     }
 244                 }
 245             }
 246             else
 247                 return false;
 248         }
 249
 250         // use next element
 251         pLastTestedRegionBandPoint = pRegionBandPoint;
 252         pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
 253     }
 254
 255     // search appropriate position and insert point into the list
 256     ImplRegionBandPoint* pNewRegionBandPoint;
 257
 258     pRegionBandPoint = mpFirstBandPoint;
 259     pLastTestedRegionBandPoint = nullptr;
 260     while ( pRegionBandPoint )
 261     {
 262         // new point completely left? -> insert as first point
 263         if ( nX <= pRegionBandPoint->mnX )
 264         {
 265             pNewRegionBandPoint                     = new ImplRegionBandPoint;
 266             pNewRegionBandPoint->mnX                = nX;
 267             pNewRegionBandPoint->mnLineId           = nLineId;
 268             pNewRegionBandPoint->mbEndPoint         = bEndPoint;
 269             pNewRegionBandPoint->meLineType         = eLineType;
 270             pNewRegionBandPoint->mpNextBandPoint    = pRegionBandPoint;
 271
 272             // connections to the new point
 273             if ( !pLastTestedRegionBandPoint )
 274                 mpFirstBandPoint = pNewRegionBandPoint;
 275             else
 276                 pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
 277
 278             return true;
 279         }
 280
 281         // use next element
 282         pLastTestedRegionBandPoint = pRegionBandPoint;
 283         pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
 284     }
 285
 286     // not inserted -> add to the end of the list
 287     pNewRegionBandPoint                     = new ImplRegionBandPoint;
 288     pNewRegionBandPoint->mnX                = nX;
 289     pNewRegionBandPoint->mnLineId           = nLineId;
 290     pNewRegionBandPoint->mbEndPoint         = bEndPoint;
 291     pNewRegionBandPoint->meLineType         = eLineType;
 292     pNewRegionBandPoint->mpNextBandPoint    = nullptr;
 293
 294     // connections to the new point
 295     pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
 296
 297     return true;
 298 }
 299
 300 void ImplRegionBand::MoveX( long nHorzMove )
 301 {
 302     // move all x-separations
 303     ImplRegionBandSep* pSep = mpFirstSep;
 304     while ( pSep )
 305     {
 306         pSep->mnXLeft  += nHorzMove;
 307         pSep->mnXRight += nHorzMove;
 308         pSep = pSep->mpNextSep;
 309     }
 310 }
 311
 312 void ImplRegionBand::ScaleX( double fHorzScale )
 313 {
 314     ImplRegionBandSep* pSep = mpFirstSep;
 315     while ( pSep )
 316     {
 317         pSep->mnXLeft   = FRound( pSep->mnXLeft * fHorzScale );
 318         pSep->mnXRight  = FRound( pSep->mnXRight * fHorzScale );
 319         pSep = pSep->mpNextSep;
 320     }
 321 }
 322
 323 // combine overlapping separations
 324
 325 void ImplRegionBand::OptimizeBand()
 326 {
 327     ImplRegionBandSep* pPrevSep = nullptr;
 328     ImplRegionBandSep* pSep = mpFirstSep;
 329     while ( pSep )
 330     {
 331         // remove?
 332         if ( pSep->mbRemoved || (pSep->mnXRight < pSep->mnXLeft) )
 333         {
 334             ImplRegionBandSep* pOldSep = pSep;
 335             if ( pSep == mpFirstSep )
 336                 mpFirstSep = pSep->mpNextSep;
 337             else
 338                 pPrevSep->mpNextSep = pSep->mpNextSep;
 339             pSep = pSep->mpNextSep;
 340             delete pOldSep;
 341             continue;
 342         }
 343
 344         // overlapping separations? -> combine!
 345         if ( pSep->mpNextSep )
 346         {
 347             if ( (pSep->mnXRight+1) >= pSep->mpNextSep->mnXLeft )
 348             {
 349                 if ( pSep->mpNextSep->mnXRight > pSep->mnXRight )
 350                     pSep->mnXRight = pSep->mpNextSep->mnXRight;
 351
 352                 ImplRegionBandSep* pOldSep = pSep->mpNextSep;
 353                 pSep->mpNextSep = pOldSep->mpNextSep;
 354                 delete pOldSep;
 355                 continue;
 356             }
 357         }
 358
 359         pPrevSep = pSep;
 360         pSep = pSep->mpNextSep;
 361     }
 362 }
 363
 364 void ImplRegionBand::Union( long nXLeft, long nXRight )
 365 {
 366     SAL_WARN_IF( nXLeft > nXRight, "vcl", "ImplRegionBand::Union(): nxLeft > nXRight" );
 367
 368     // band empty? -> add element
 369     if ( !mpFirstSep )
 370     {
 371         mpFirstSep              = new ImplRegionBandSep;
 372         mpFirstSep->mnXLeft     = nXLeft;
 373         mpFirstSep->mnXRight    = nXRight;
 374         mpFirstSep->mbRemoved   = false;
 375         mpFirstSep->mpNextSep   = nullptr;
 376         return;
 377     }
 378
 379     // process real union
 380     ImplRegionBandSep* pNewSep;
 381     ImplRegionBandSep* pPrevSep = nullptr;
 382     ImplRegionBandSep* pSep = mpFirstSep;
 383     while ( pSep )
 384     {
 385         // new separation completely inside? nothing to do!
 386         if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
 387             return;
 388
 389         // new separation completely left? -> new separation!
 390         if ( nXRight < pSep->mnXLeft )
 391         {
 392             pNewSep             = new ImplRegionBandSep;
 393             pNewSep->mnXLeft    = nXLeft;
 394             pNewSep->mnXRight   = nXRight;
 395             pNewSep->mbRemoved  = false;
 396
 397             pNewSep->mpNextSep = pSep;
 398             if ( pSep == mpFirstSep )
 399                 mpFirstSep = pNewSep;
 400             else
 401                 pPrevSep->mpNextSep = pNewSep;
 402             break;
 403         }
 404
 405         // new separation overlapping from left? -> extend boundary
 406         if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
 407             pSep->mnXLeft = nXLeft;
 408
 409         // new separation overlapping from right? -> extend boundary
 410         if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
 411         {
 412             pSep->mnXRight = nXRight;
 413             break;
 414         }
 415
 416         // not inserted, but last element? -> add to the end of the list
 417         if ( !pSep->mpNextSep && (nXLeft > pSep->mnXRight) )
 418         {
 419             pNewSep             = new ImplRegionBandSep;
 420             pNewSep->mnXLeft    = nXLeft;
 421             pNewSep->mnXRight   = nXRight;
 422             pNewSep->mbRemoved  = false;
 423
 424             pSep->mpNextSep     = pNewSep;
 425             pNewSep->mpNextSep  = nullptr;
 426             break;
 427         }
 428
 429         pPrevSep = pSep;
 430         pSep = pSep->mpNextSep;
 431     }
 432
 433     OptimizeBand();
 434 }
 435
 436 void ImplRegionBand::Intersect( long nXLeft, long nXRight )
 437 {
 438     SAL_WARN_IF( nXLeft > nXRight, "vcl", "ImplRegionBand::Intersect(): nxLeft > nXRight" );
 439
 440     // band has been touched
 441     mbTouched = true;
 442
 443     // band empty? -> nothing to do
 444     if ( !mpFirstSep )
 445         return;
 446
 447     // process real intersection
 448     ImplRegionBandSep* pSep = mpFirstSep;
 449     while ( pSep )
 450     {
 451         // new separation completely outside? -> remove separation
 452         if ( (nXRight < pSep->mnXLeft) || (nXLeft > pSep->mnXRight) )
 453             // will be removed from the optimizer
 454             pSep->mbRemoved = true;
 455
 456         // new separation overlapping from left? -> reduce right boundary
 457         if ( (nXLeft <= pSep->mnXLeft) &&
 458              (nXRight <= pSep->mnXRight) &&
 459              (nXRight >= pSep->mnXLeft) )
 460             pSep->mnXRight = nXRight;
 461
 462         // new separation overlapping from right? -> reduce right boundary
 463         if ( (nXLeft >= pSep->mnXLeft) &&
 464              (nXLeft <= pSep->mnXRight) &&
 465              (nXRight >= pSep->mnXRight) )
 466             pSep->mnXLeft = nXLeft;
 467
 468         // new separation within the actual one? -> reduce both boundaries
 469         if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
 470         {
 471             pSep->mnXRight = nXRight;
 472             pSep->mnXLeft = nXLeft;
 473         }
 474
 475         pSep = pSep->mpNextSep;
 476     }
 477
 478     OptimizeBand();
 479 }
 480
 481 void ImplRegionBand::Exclude( long nXLeft, long nXRight )
 482 {
 483     SAL_WARN_IF( nXLeft > nXRight, "vcl", "ImplRegionBand::Exclude(): nxLeft > nXRight" );
 484
 485     // band has been touched
 486     mbTouched = true;
 487
 488     // band empty? -> nothing to do
 489     if ( !mpFirstSep )
 490         return;
 491
 492     // process real exclusion
 493     ImplRegionBandSep* pNewSep;
 494     ImplRegionBandSep* pPrevSep = nullptr;
 495     ImplRegionBandSep* pSep = mpFirstSep;
 496     while ( pSep  )
 497     {
 498         bool bSepProcessed = false;
 499
 500         // new separation completely overlapping? -> remove separation
 501         if ( (nXLeft <= pSep->mnXLeft) && (nXRight >= pSep->mnXRight) )
 502         {
 503             // will be removed from the optimizer
 504             pSep->mbRemoved = true;
 505             bSepProcessed = true;
 506         }
 507
 508         // new separation overlapping from left? -> reduce boundary
 509         if ( !bSepProcessed )
 510         {
 511             if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
 512             {
 513                 pSep->mnXLeft = nXRight+1;
 514                 bSepProcessed = true;
 515             }
 516         }
 517
 518         // new separation overlapping from right? -> reduce boundary
 519         if ( !bSepProcessed )
 520         {
 521             if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
 522             {
 523                 pSep->mnXRight = nXLeft-1;
 524                 bSepProcessed = true;
 525             }
 526         }
 527
 528         // new separation within the actual one? -> reduce boundary
 529         // and add new entry for reminder
 530         if ( !bSepProcessed )
 531         {
 532             if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
 533             {
 534                 pNewSep             = new ImplRegionBandSep;
 535                 pNewSep->mnXLeft    = pSep->mnXLeft;
 536                 pNewSep->mnXRight   = nXLeft-1;
 537                 pNewSep->mbRemoved  = false;
 538
 539                 pSep->mnXLeft = nXRight+1;
 540
 541                 // connections from the new separation
 542                 pNewSep->mpNextSep = pSep;
 543
 544                 // connections to the new separation
 545                 if ( pSep == mpFirstSep )
 546                     mpFirstSep = pNewSep;
 547                 else
 548                     pPrevSep->mpNextSep = pNewSep;
 549             }
 550         }
 551
 552         pPrevSep = pSep;
 553         pSep = pSep->mpNextSep;
 554     }
 555
 556     OptimizeBand();
 557 }
 558
 559 void ImplRegionBand::XOr( long nXLeft, long nXRight )
 560 {
 561     SAL_WARN_IF( nXLeft > nXRight, "vcl", "ImplRegionBand::XOr(): nxLeft > nXRight" );
 562
 563     // #i46602# Reworked rectangle Xor
 564
 565     // In general, we can distinguish 11 cases of intersection
 566     // (details below). The old implementation explicitly handled 7
 567     // cases (numbered in the order of appearance, use CVS to get your
 568     // hands on the old version), therefore, I've sticked to that
 569     // order, and added four more cases. The code below references
 570     // those numbers via #1, #2, etc.
 571
 572     // Num Mnem        newX:oldX newY:oldY  Description                                             Result          Can quit?
 573
 574     // #1  Empty band      -         -      The band is empty, thus, simply add new bandSep         just add        Yes
 575
 576     // #2  apart           -         -      The rectangles are disjunct, add new one as is          just add        Yes
 577
 578     // #3  atop            ==        ==     The rectangles are _exactly_ the same, remove existing  just remove     Yes
 579
 580     // #4  around          <         >      The new rectangle extends the old to both sides         intersect       No
 581
 582     // #5  left            <         <      The new rectangle is left of the old (but intersects)   intersect       Yes
 583
 584     // #5b left-atop       <         ==     The new is left of the old, and coincides on the right  intersect       Yes
 585
 586     // #6  right           >         >      The new is right of the old (but intersects)            intersect       No
 587
 588     // #6b right-atop      ==        >      The new is right of the old, and coincides on the left  intersect       No
 589
 590     // #7 inside           >         <      The new is fully inside the old                         intersect       Yes
 591
 592     // #8 inside-right     >         ==     The new is fully inside the old, coincides on the right intersect       Yes
 593
 594     // #9 inside-left      ==        <      The new is fully inside the old, coincides on the left  intersect       Yes
 595
 596     // Then, to correctly perform XOr, the segment that's switched off
 597     // (i.e. the overlapping part of the old and the new segment) must
 598     // be extended by one pixel value at each border:
 599     //           1   1
 600     // 0   4     0   4
 601     // 111100000001111
 602
 603     // Clearly, the leading band sep now goes from 0 to 3, and the
 604     // trailing band sep from 11 to 14. This mimics the xor look of a
 605     // bitmap operation.
 606
 607     // band empty? -> add element
 608     if ( !mpFirstSep )
 609     {
 610         mpFirstSep              = new ImplRegionBandSep;
 611         mpFirstSep->mnXLeft     = nXLeft;
 612         mpFirstSep->mnXRight    = nXRight;
 613         mpFirstSep->mbRemoved   = false;
 614         mpFirstSep->mpNextSep   = nullptr;
 615         return;
 616     }
 617
 618     // process real xor
 619     ImplRegionBandSep* pNewSep;
 620     ImplRegionBandSep* pPrevSep = nullptr;
 621     ImplRegionBandSep* pSep = mpFirstSep;
 622
 623     while ( pSep  )
 624     {
 625         long nOldLeft( pSep->mnXLeft );
 626         long nOldRight( pSep->mnXRight );
 627
 628         // did the current segment actually touch the new rect? If
 629         // not, skip all comparisons, go on, loop and try to find
 630         // intersecting bandSep
 631         if( nXLeft <= nOldRight )
 632         {
 633             if( nXRight < nOldLeft )
 634             {
 635                 // #2
 636
 637                 // add _before_ current bandSep
 638                 pNewSep             = new ImplRegionBandSep;
 639                 pNewSep->mnXLeft    = nXLeft;
 640                 pNewSep->mnXRight   = nXRight;
 641                 pNewSep->mpNextSep  = pSep;
 642                 pNewSep->mbRemoved  = false;
 643
 644                 // connections from the new separation
 645                 pNewSep->mpNextSep = pSep;
 646
 647                 // connections to the new separation
 648                 if ( pSep == mpFirstSep )
 649                     mpFirstSep = pNewSep;
 650                 else
 651                     pPrevSep->mpNextSep = pNewSep;
 652                 pPrevSep = nullptr; // do not run accidentally into the "right" case when breaking the loop
 653                 break;
 654             }
 655             else if( nXLeft == nOldLeft && nXRight == nOldRight )
 656             {
 657                 // #3
 658                 pSep->mbRemoved = true;
 659                 pPrevSep = nullptr; // do not run accidentally into the "right" case when breaking the loop
 660                 break;
 661             }
 662             else if( nXLeft != nOldLeft && nXRight == nOldRight )
 663             {
 664                 // # 5b, 8
 665                 if( nXLeft < nOldLeft )
 666                 {
 667                     nXRight = nOldLeft; // 5b
 668                 }
 669                 else
 670                 {
 671                     nXRight = nXLeft; // 8
 672                     nXLeft = nOldLeft;
 673                 }
 674
 675                 pSep->mnXLeft = nXLeft;
 676                 pSep->mnXRight = nXRight-1;
 677
 678                 pPrevSep = nullptr; // do not run accidentally into the "right" case when breaking the loop
 679                 break;
 680             }
 681             else if( nXLeft == nOldLeft && nXRight != nOldRight )
 682             {
 683                 // # 6b, 9
 684
 685                 if( nXRight > nOldRight )
 686                 {
 687                     nXLeft = nOldRight+1; // 6b
 688
 689                     // cannot break here, simply mark segment as removed,
 690                     // and go on with adapted nXLeft/nXRight
 691                     pSep->mbRemoved = true;
 692                 }
 693                 else
 694                 {
 695                     pSep->mnXLeft = nXRight+1; // 9
 696
 697                     pPrevSep = nullptr; // do not run accidentally into the "right" case when breaking the loop
 698                     break;
 699                 }
 700             }
 701             else // if( nXLeft != nOldLeft && nXRight != nOldRight ) follows automatically
 702             {
 703                 // #4,5,6,7
 704                 SAL_WARN_IF( nXLeft == nOldLeft || nXRight == nOldRight, "vcl",
 705                             "ImplRegionBand::XOr(): Case 4,5,6,7 expected all coordinates to be not equal!" );
 706
 707                 // The plain-jane check would look like this:
 708
 709                 // if( nXLeft < nOldLeft )
 710                 // {
 711                 //     // #4,5
 712                 //     if( nXRight > nOldRight )
 713                 //     {
 714                 //        // #4
 715                 //     }
 716                 //     else
 717                 //     {
 718                 //         // #5 done!
 719                 //     }
 720                 // }
 721                 // else
 722                 // {
 723                 //     // #6,7
 724                 //     if( nXRight > nOldRight )
 725                 //     {
 726                 //         // #6
 727                 //     }
 728                 //     else
 729                 //     {
 730                 //         // #7 done!
 731                 //     }
 732                 // }
 733
 734                 // but since we generally don't have to care whether
 735                 // it's 4 or 6 (only that we must not stop processing
 736                 // here), condensed that in such a way that only the
 737                 // coordinates get shuffled into correct ordering.
 738
 739                 if( nXLeft < nOldLeft )
 740                     ::std::swap( nOldLeft, nXLeft );
 741
 742                 bool bDone( false );
 743
 744                 if( nXRight < nOldRight )
 745                 {
 746                     ::std::swap( nOldRight, nXRight );
 747                     bDone = true;
 748                 }
 749
 750                 // now, nOldLeft<nXLeft<=nOldRight<nXRight always
 751                 // holds. Note that we need the nXLeft<=nOldRight here, as
 752                 // the intersection part might be only one pixel (original
 753                 // nXLeft==nXRight)
 754                 SAL_WARN_IF( nOldLeft==nXLeft || nXLeft>nOldRight || nOldRight>=nXRight, "vcl",
 755                             "ImplRegionBand::XOr(): Case 4,5,6,7 expected coordinates to be ordered now!" );
 756
 757                 pSep->mnXLeft = nOldLeft;
 758                 pSep->mnXRight = nXLeft-1;
 759
 760                 nXLeft = nOldRight+1;
 761                 // nxRight is already setup correctly
 762
 763                 if( bDone )
 764                 {
 765                     // add behind current bandSep
 766                     pNewSep = new ImplRegionBandSep;
 767
 768                     pNewSep->mnXLeft    = nXLeft;
 769                     pNewSep->mnXRight   = nXRight;
 770                     pNewSep->mpNextSep  = pSep->mpNextSep;
 771                     pNewSep->mbRemoved  = false;
 772
 773                     // connections from the new separation
 774                     pSep->mpNextSep = pNewSep;
 775
 776                     pPrevSep = nullptr; // do not run accidentally into the "right" case when breaking the loop
 777                     break;
 778                 }
 779             }
 780         }
 781
 782         pPrevSep = pSep;
 783         pSep = pSep->mpNextSep;
 784     }
 785
 786     // new separation completely right of existing bandSeps ?
 787     if( pPrevSep && nXLeft >= pPrevSep->mnXRight )
 788     {
 789         pNewSep             = new ImplRegionBandSep;
 790         pNewSep->mnXLeft    = nXLeft;
 791         pNewSep->mnXRight   = nXRight;
 792         pNewSep->mpNextSep  = nullptr;
 793         pNewSep->mbRemoved  = false;
 794
 795         // connections from the new separation
 796         pPrevSep->mpNextSep = pNewSep;
 797     }
 798
 799     OptimizeBand();
 800 }
 801
 802 bool ImplRegionBand::IsInside( long nX )
 803 {
 804     ImplRegionBandSep* pSep = mpFirstSep;
 805     while ( pSep )
 806     {
 807         if ( (pSep->mnXLeft <= nX) && (pSep->mnXRight >= nX) )
 808             return true;
 809
 810         pSep = pSep->mpNextSep;
 811     }
 812
 813     return false;
 814 }
 815
 816 long ImplRegionBand::GetXLeftBoundary() const
 817 {
 818     assert(mpFirstSep && "ImplRegionBand::XLeftBoundary -> no separation in band!");
 819
 820     return mpFirstSep->mnXLeft;
 821 }
 822
 823 long ImplRegionBand::GetXRightBoundary() const
 824 {
 825     SAL_WARN_IF( mpFirstSep == nullptr, "vcl", "ImplRegionBand::XRightBoundary -> no separation in band!" );
 826
 827     // search last separation
 828     ImplRegionBandSep* pSep = mpFirstSep;
 829     while ( pSep->mpNextSep )
 830         pSep = pSep->mpNextSep;
 831     return pSep->mnXRight;
 832 }
 833
 834 bool ImplRegionBand::operator==( const ImplRegionBand& rRegionBand ) const
 835 {
 836     ImplRegionBandSep*   pOwnRectBandSep = mpFirstSep;
 837     ImplRegionBandSep*   pSecondRectBandSep = rRegionBand.mpFirstSep;
 838     while ( pOwnRectBandSep && pSecondRectBandSep )
 839     {
 840         // get boundaries of current rectangle
 841         long nOwnXLeft = pOwnRectBandSep->mnXLeft;
 842         long nSecondXLeft = pSecondRectBandSep->mnXLeft;
 843         if ( nOwnXLeft != nSecondXLeft )
 844             return false;
 845
 846         long nOwnXRight = pOwnRectBandSep->mnXRight;
 847         long nSecondXRight = pSecondRectBandSep->mnXRight;
 848         if ( nOwnXRight != nSecondXRight )
 849             return false;
 850
 851         // get next separation from current band
 852         pOwnRectBandSep = pOwnRectBandSep->mpNextSep;
 853
 854         // get next separation from current band
 855         pSecondRectBandSep = pSecondRectBandSep->mpNextSep;
 856     }
 857
 858     // different number of separations?
 859     return !(pOwnRectBandSep || pSecondRectBandSep);
 860 }
 861
 862 ImplRegionBand* ImplRegionBand::SplitBand (const sal_Int32 nY)
 863 {
 864     OSL_ASSERT(nY>mnYTop);
 865     OSL_ASSERT(nY<=mnYBottom);
 866
 867     // Create a copy of the given band (we tell the constructor to copy the points together
 868     // with the seps.)
 869     ImplRegionBand* pLowerBand = new ImplRegionBand(*this, false);
 870
 871     // Adapt vertical coordinates.
 872     mnYBottom = nY-1;
 873     pLowerBand->mnYTop = nY;
 874
 875     // Insert new band into list of bands.
 876     pLowerBand->mpNextBand = mpNextBand;
 877     mpNextBand = pLowerBand;
 878     pLowerBand->mpPrevBand = this;
 879     if (pLowerBand->mpNextBand != nullptr)
 880         pLowerBand->mpNextBand->mpPrevBand = pLowerBand;
 881
 882     return pLowerBand;
 883 }
 884
 885 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */