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