LCOV - code coverage report
Current view: top level - vcl/source/gdi - regband.cxx (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 281 375 74.9 %
Date: 2015-06-13 12:38:46 Functions: 14 17 82.4 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.11