vcl/source/gdi/regband.cxx

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