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