xref: /trunk/main/vcl/source/gdi/regband.cxx (revision cf6516809c57e1bb0a940545cca99cdad54d4ce2)

/**************************************************************
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *************************************************************/



// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_vcl.hxx"
#include <tools/debug.hxx>
#include <vcl/salbtype.hxx>
#include <vcl/regband.hxx>

#include <algorithm>


// =======================================================================
//
// ImplRegionBand
//
// Jedes Band enthaelt die zwischen der enthaltenen Ober- und Untergrenze
// enthaltenen Rechtecke. Bei den Operationen Union, Intersect, XOr und
// Exclude werden immer Rechtecke der gleichen Hoehe ausgewerte; die
// Grenzen der Baender sind immer so zu waehlen, dasz dies moeglich ist.
//
// Die Rechtecke in den Baendern werden nach Moeglichkeit zusammengefaszt.
//
// Bei der Umwandlung von Polygonen werden alle Punkte des Polygons
// in die einzelnen Baender eingetragen (sie stehen fuer jedes Band als
// Punkte in einer Liste). Nach dem Eintragen der Punkte werden diese
// in Rechtecke umgewandelt und die Liste der Punkte geloescht.
//
// -----------------------------------------------------------------------

ImplRegionBand::ImplRegionBand( long nTop, long nBottom )
{
    // save boundaries
    mnYTop              = nTop;
    mnYBottom           = nBottom;

    // initialize lists
    mpNextBand          = NULL;
    mpPrevBand          = NULL;
    mpFirstSep          = NULL;
    mpFirstBandPoint    = NULL;
    mbTouched           = false;
}

// -----------------------------------------------------------------------

ImplRegionBand::ImplRegionBand(
    const ImplRegionBand& rRegionBand,
    const bool bIgnorePoints)
{
    // copy boundaries
    mnYTop              = rRegionBand.mnYTop;
    mnYBottom           = rRegionBand.mnYBottom;
    mbTouched           = rRegionBand.mbTouched;

    // initialisation
    mpNextBand          = NULL;
    mpPrevBand          = NULL;
    mpFirstSep          = NULL;
    mpFirstBandPoint    = NULL;

    // copy all elements of the list with separations
    ImplRegionBandSep* pNewSep;
    ImplRegionBandSep* pPrevSep = 0;
    ImplRegionBandSep* pSep = rRegionBand.mpFirstSep;
    while ( pSep )
    {
        // create new and copy data
        pNewSep             = new ImplRegionBandSep;
        pNewSep->mnXLeft    = pSep->mnXLeft;
        pNewSep->mnXRight   = pSep->mnXRight;
        pNewSep->mbRemoved  = pSep->mbRemoved;
        pNewSep->mpNextSep  = NULL;
        if ( pSep == rRegionBand.mpFirstSep )
            mpFirstSep = pNewSep;
        else
            pPrevSep->mpNextSep = pNewSep;

        pPrevSep = pNewSep;
        pSep = pSep->mpNextSep;
    }

    if ( ! bIgnorePoints)
    {
        // Copy points.
        ImplRegionBandPoint* pPoint = rRegionBand.mpFirstBandPoint;
        ImplRegionBandPoint* pPrevPointCopy = NULL;
        while (pPoint != NULL)
        {
            ImplRegionBandPoint* pPointCopy = new ImplRegionBandPoint();
            pPointCopy->mnX = pPoint->mnX;
            pPointCopy->mnLineId = pPoint->mnLineId;
            pPointCopy->mbEndPoint = pPoint->mbEndPoint;
            pPointCopy->meLineType = pPoint->meLineType;

            if (pPrevPointCopy != NULL)
                pPrevPointCopy->mpNextBandPoint = pPointCopy;
            else
                mpFirstBandPoint = pPointCopy;

            pPrevPointCopy = pPointCopy;
            pPoint = pPoint->mpNextBandPoint;
        }
    }
}

// -----------------------------------------------------------------------

ImplRegionBand::~ImplRegionBand()
{
    DBG_ASSERT( mpFirstBandPoint == NULL, "ImplRegionBand::~ImplRegionBand -> pointlist not empty" );

    // delete elements of the list
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        ImplRegionBandSep* pTempSep = pSep->mpNextSep;
        delete pSep;
        pSep = pTempSep;
    }

    // delete elements of the list
    ImplRegionBandPoint* pPoint = mpFirstBandPoint;
    while ( pPoint )
    {
        ImplRegionBandPoint* pTempPoint = pPoint->mpNextBandPoint;
        delete pPoint;
        pPoint = pTempPoint;
    }
}

// -----------------------------------------------------------------------
//
// generate separations from lines and process union with existing
// separations

void ImplRegionBand::ProcessPoints()
{
    // check Pointlist
    ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
    while ( pRegionBandPoint )
    {
        // within list?
        if ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint )
        {
            // start/stop?
            if ( pRegionBandPoint->mbEndPoint && pRegionBandPoint->mpNextBandPoint->mbEndPoint )
            {
                // same direction? -> remove next point!
                if ( pRegionBandPoint->meLineType == pRegionBandPoint->mpNextBandPoint->meLineType )
                {
                    ImplRegionBandPoint* pSaveRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
                    pRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
                    delete pSaveRegionBandPoint;
                }
            }
        }

        // continue with next element in the list
        pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
    }

    pRegionBandPoint = mpFirstBandPoint;
    while ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint )
    {
        Union( pRegionBandPoint->mnX, pRegionBandPoint->mpNextBandPoint->mnX );

        ImplRegionBandPoint* pNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;

        // remove already processed points
        delete pRegionBandPoint->mpNextBandPoint;
        delete pRegionBandPoint;

        // continue with next element in the list
        pRegionBandPoint = pNextBandPoint;
    }

    // remove last element if necessary
    if ( pRegionBandPoint )
        delete pRegionBandPoint;

    // list is now empty
    mpFirstBandPoint = NULL;
}

// -----------------------------------------------------------------------
//
// generate separations from lines and process union with existing
// separations

bool ImplRegionBand::InsertPoint( long nX, long nLineId,
                                  bool bEndPoint, LineType eLineType )
{
    if ( !mpFirstBandPoint )
    {
        mpFirstBandPoint                  = new ImplRegionBandPoint;
        mpFirstBandPoint->mnX             = nX;
        mpFirstBandPoint->mnLineId        = nLineId;
        mpFirstBandPoint->mbEndPoint      = bEndPoint;
        mpFirstBandPoint->meLineType      = eLineType;
        mpFirstBandPoint->mpNextBandPoint = NULL;
        return true;
    }

    // look if line already touched the band
    ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
    ImplRegionBandPoint* pLastTestedRegionBandPoint = NULL;
    while( pRegionBandPoint )
    {
        if ( pRegionBandPoint->mnLineId == nLineId )
        {
            if ( bEndPoint )
            {
                if( !pRegionBandPoint->mbEndPoint )
                {
                    // remove old band point
                    if( !mpFirstBandPoint->mpNextBandPoint )
                    {
                        // if we've only got one point => replace first point
                        pRegionBandPoint->mnX = nX;
                        pRegionBandPoint->mbEndPoint = true;
                        return true;
                    }
                    else
                    {
                        // remove current point
                        if( !pLastTestedRegionBandPoint )
                        {
                            // remove and delete old first point
                            ImplRegionBandPoint* pSaveBandPoint = mpFirstBandPoint;
                            mpFirstBandPoint = mpFirstBandPoint->mpNextBandPoint;
                            delete pSaveBandPoint;
                        }
                        else
                        {
                            // remove and delete current band point
                            pLastTestedRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint;
                            delete pRegionBandPoint;
                        }

                        break;
                    }
                }
            }
            else
                return false;
        }

        // use next element
        pLastTestedRegionBandPoint = pRegionBandPoint;
        pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
    }

    // search appropriate position and insert point into the list
    ImplRegionBandPoint* pNewRegionBandPoint;

    pRegionBandPoint = mpFirstBandPoint;
    pLastTestedRegionBandPoint = NULL;
    while ( pRegionBandPoint )
    {
        // new point completely left? -> insert as first point
        if ( nX <= pRegionBandPoint->mnX )
        {
            pNewRegionBandPoint                     = new ImplRegionBandPoint;
            pNewRegionBandPoint->mnX                = nX;
            pNewRegionBandPoint->mnLineId           = nLineId;
            pNewRegionBandPoint->mbEndPoint         = bEndPoint;
            pNewRegionBandPoint->meLineType         = eLineType;
            pNewRegionBandPoint->mpNextBandPoint    = pRegionBandPoint;

            // connections to the new point
            if ( !pLastTestedRegionBandPoint )
                mpFirstBandPoint = pNewRegionBandPoint;
            else
                pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;

            return true;
        }

        // use next element
        pLastTestedRegionBandPoint = pRegionBandPoint;
        pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
    }

    // not inserted -> add to the end of the list
    pNewRegionBandPoint                     = new ImplRegionBandPoint;
    pNewRegionBandPoint->mnX                = nX;
    pNewRegionBandPoint->mnLineId           = nLineId;
    pNewRegionBandPoint->mbEndPoint         = bEndPoint;
    pNewRegionBandPoint->meLineType         = eLineType;
    pNewRegionBandPoint->mpNextBandPoint    = NULL;

    // connections to the new point
    pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;

    return true;
}

// -----------------------------------------------------------------------

void ImplRegionBand::MoveX( long nHorzMove )
{
    // move all x-separations
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        pSep->mnXLeft  += nHorzMove;
        pSep->mnXRight += nHorzMove;
        pSep = pSep->mpNextSep;
    }
}

// -----------------------------------------------------------------------

void ImplRegionBand::ScaleX( double fHorzScale )
{
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        pSep->mnXLeft   = FRound( pSep->mnXLeft * fHorzScale );
        pSep->mnXRight  = FRound( pSep->mnXRight * fHorzScale );
        pSep = pSep->mpNextSep;
    }
}

// -----------------------------------------------------------------------
//
// combine overlapping separations

bool ImplRegionBand::OptimizeBand()
{
    ImplRegionBandSep* pPrevSep = 0;
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        // remove?
        if ( pSep->mbRemoved || (pSep->mnXRight < pSep->mnXLeft) )
        {
            ImplRegionBandSep* pOldSep = pSep;
            if ( pSep == mpFirstSep )
                mpFirstSep = pSep->mpNextSep;
            else
                pPrevSep->mpNextSep = pSep->mpNextSep;
            pSep = pSep->mpNextSep;
            delete pOldSep;
            continue;
        }

        // overlapping separations? -> combine!
        if ( pSep->mpNextSep )
        {
            if ( (pSep->mnXRight+1) >= pSep->mpNextSep->mnXLeft )
            {
                if ( pSep->mpNextSep->mnXRight > pSep->mnXRight )
                    pSep->mnXRight = pSep->mpNextSep->mnXRight;

                ImplRegionBandSep* pOldSep = pSep->mpNextSep;
                pSep->mpNextSep = pOldSep->mpNextSep;
                delete pOldSep;
                continue;
            }
        }

        pPrevSep = pSep;
        pSep = pSep->mpNextSep;
    }

    return true;
}

// -----------------------------------------------------------------------

void ImplRegionBand::Union( long nXLeft, long nXRight )
{
    DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Union(): nxLeft > nXRight" );

    // band empty? -> add element
    if ( !mpFirstSep )
    {
        mpFirstSep              = new ImplRegionBandSep;
        mpFirstSep->mnXLeft     = nXLeft;
        mpFirstSep->mnXRight    = nXRight;
        mpFirstSep->mbRemoved   = false;
        mpFirstSep->mpNextSep   = NULL;
        return;
    }

    // process real union
    ImplRegionBandSep* pNewSep;
    ImplRegionBandSep* pPrevSep = 0;
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        // new separation completely inside? nothing to do!
        if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
            return;

        // new separation completely left? -> new separation!
        if ( nXRight < pSep->mnXLeft )
        {
            pNewSep             = new ImplRegionBandSep;
            pNewSep->mnXLeft    = nXLeft;
            pNewSep->mnXRight   = nXRight;
            pNewSep->mbRemoved  = false;

            pNewSep->mpNextSep = pSep;
            if ( pSep == mpFirstSep )
                mpFirstSep = pNewSep;
            else
                pPrevSep->mpNextSep = pNewSep;
            break;
        }

        // new separation overlapping from left? -> extend boundary
        if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
            pSep->mnXLeft = nXLeft;

        // new separation overlapping from right? -> extend boundary
        if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
        {
            pSep->mnXRight = nXRight;
            break;
        }

        // not inserted, but last element? -> add to the end of the list
        if ( !pSep->mpNextSep && (nXLeft > pSep->mnXRight) )
        {
            pNewSep             = new ImplRegionBandSep;
            pNewSep->mnXLeft    = nXLeft;
            pNewSep->mnXRight   = nXRight;
            pNewSep->mbRemoved  = false;

            pSep->mpNextSep     = pNewSep;
            pNewSep->mpNextSep  = NULL;
            break;
        }

        pPrevSep = pSep;
        pSep = pSep->mpNextSep;
    }

    OptimizeBand();
}

// -----------------------------------------------------------------------

void ImplRegionBand::Intersect( long nXLeft, long nXRight )
{
    DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Intersect(): nxLeft > nXRight" );

    // band has been touched
    mbTouched = true;

    // band empty? -> nothing to do
    if ( !mpFirstSep )
        return;

    // process real intersection
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        // new separation completely outside? -> remove separation
        if ( (nXRight < pSep->mnXLeft) || (nXLeft > pSep->mnXRight) )
            // will be removed from the optimizer
            pSep->mbRemoved = true;

        // new separation overlapping from left? -> reduce right boundary
        if ( (nXLeft <= pSep->mnXLeft) &&
             (nXRight <= pSep->mnXRight) &&
             (nXRight >= pSep->mnXLeft) )
            pSep->mnXRight = nXRight;

        // new separation overlapping from right? -> reduce right boundary
        if ( (nXLeft >= pSep->mnXLeft) &&
             (nXLeft <= pSep->mnXRight) &&
             (nXRight >= pSep->mnXRight) )
            pSep->mnXLeft = nXLeft;

        // new separation within the actual one? -> reduce both boundaries
        if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
        {
            pSep->mnXRight = nXRight;
            pSep->mnXLeft = nXLeft;
        }

        pSep = pSep->mpNextSep;
    }

    OptimizeBand();
}

// -----------------------------------------------------------------------

void ImplRegionBand::Exclude( long nXLeft, long nXRight )
{
    DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Exclude(): nxLeft > nXRight" );

    // band has been touched
    mbTouched = true;

    // band empty? -> nothing to do
    if ( !mpFirstSep )
        return;

    // process real exclusion
    ImplRegionBandSep* pNewSep;
    ImplRegionBandSep* pPrevSep = 0;
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep  )
    {
        bool bSepProcessed = false;

        // new separation completely overlapping? -> remove separation
        if ( (nXLeft <= pSep->mnXLeft) && (nXRight >= pSep->mnXRight) )
        {
            // will be removed from the optimizer
            pSep->mbRemoved = true;
            bSepProcessed = true;
        }

        // new separation overlapping from left? -> reduce boundary
        if ( !bSepProcessed )
        {
            if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
            {
                pSep->mnXLeft = nXRight+1;
                bSepProcessed = true;
            }
        }

        // new separation overlapping from right? -> reduce boundary
        if ( !bSepProcessed )
        {
            if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
            {
                pSep->mnXRight = nXLeft-1;
                bSepProcessed = true;
            }
        }

        // new separation within the actual one? -> reduce boundary
        // and add new entry for reminder
        if ( !bSepProcessed )
        {
            if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
            {
                pNewSep             = new ImplRegionBandSep;
                pNewSep->mnXLeft    = pSep->mnXLeft;
                pNewSep->mnXRight   = nXLeft-1;
                pNewSep->mbRemoved  = false;

                pSep->mnXLeft = nXRight+1;

                // connections from the new separation
                pNewSep->mpNextSep = pSep;

                // connections to the new separation
                if ( pSep == mpFirstSep )
                    mpFirstSep = pNewSep;
                else
                    pPrevSep->mpNextSep = pNewSep;
            }
        }

        pPrevSep = pSep;
        pSep = pSep->mpNextSep;
    }

    OptimizeBand();
}

// -----------------------------------------------------------------------

void ImplRegionBand::XOr( long nXLeft, long nXRight )
{
    DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::XOr(): nxLeft > nXRight" );

    // #i46602# Reworked rectangle Xor
    //
    // In general, we can distinguish 11 cases of intersection
    // (details below). The old implementation explicitly handled 7
    // cases (numbered in the order of appearance, use CVS to get your
    // hands on the old version), therefore, I've sticked to that
    // order, and added four more cases. The code below references
    // those numbers via #1, #2, etc.
    //
    // Num Mnem        newX:oldX newY:oldY  Description                                             Result          Can quit?
    //
    // #1  Empty band      -         -      The band is empty, thus, simply add new bandSep         just add        Yes
    //
    // #2  apart           -         -      The rectangles are disjunct, add new one as is          just add        Yes
    //
    // #3  atop            ==        ==     The rectangles are _exactly_ the same, remove existing  just remove     Yes
    //
    // #4  around          <         >      The new rectangle extends the old to both sides         intersect       No
    //
    // #5  left            <         <      The new rectangle is left of the old (but intersects)   intersect       Yes
    //
    // #5b left-atop       <         ==     The new is left of the old, and coincides on the right  intersect       Yes
    //
    // #6  right           >         >      The new is right of the old (but intersects)            intersect       No
    //
    // #6b right-atop      ==        >      The new is right of the old, and coincides on the left  intersect       No
    //
    // #7 inside           >         <      The new is fully inside the old                         intersect       Yes
    //
    // #8 inside-right     >         ==     The new is fully inside the old, coincides on the right intersect       Yes
    //
    // #9 inside-left      ==        <      The new is fully inside the old, coincides on the left  intersect       Yes
    //
    //
    // Then, to correctly perform XOr, the segment that's switched off
    // (i.e. the overlapping part of the old and the new segment) must
    // be extended by one pixel value at each border:
    //           1   1
    // 0   4     0   4
    // 111100000001111
    //
    // Clearly, the leading band sep now goes from 0 to 3, and the
    // trailing band sep from 11 to 14. This mimicks the xor look of a
    // bitmap operation.
    //

    // band empty? -> add element
    if ( !mpFirstSep )
    {
        mpFirstSep              = new ImplRegionBandSep;
        mpFirstSep->mnXLeft     = nXLeft;
        mpFirstSep->mnXRight    = nXRight;
        mpFirstSep->mbRemoved   = false;
        mpFirstSep->mpNextSep   = NULL;
        return;
    }

    // process real xor
    ImplRegionBandSep* pNewSep;
    ImplRegionBandSep* pPrevSep = 0;
    ImplRegionBandSep* pSep = mpFirstSep;

    while ( pSep  )
    {
        long nOldLeft( pSep->mnXLeft );
        long nOldRight( pSep->mnXRight );

        // did the current segment actually touch the new rect? If
        // not, skip all comparisons, go on, loop and try to find
        // intersecting bandSep
        if( nXLeft <= nOldRight )
        {
            if( nXRight < nOldLeft )
            {
                // #2

                // add _before_ current bandSep
                pNewSep             = new ImplRegionBandSep;
                pNewSep->mnXLeft    = nXLeft;
                pNewSep->mnXRight   = nXRight;
                pNewSep->mpNextSep  = pSep;
                pNewSep->mbRemoved  = false;

                // connections from the new separation
                pNewSep->mpNextSep = pSep;

                // connections to the new separation
                if ( pSep == mpFirstSep )
                    mpFirstSep = pNewSep;
                else
                    pPrevSep->mpNextSep = pNewSep;
                pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
                break;
            }
            else if( nXLeft == nOldLeft && nXRight == nOldRight )
            {
                // #3
                pSep->mbRemoved = true;
                pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
                break;
            }
            else if( nXLeft != nOldLeft && nXRight == nOldRight )
            {
                // # 5b, 8
                if( nXLeft < nOldLeft )
                {
                    nXRight = nOldLeft; // 5b
                }
                else
                {
                    nXRight = nXLeft; // 8
                    nXLeft = nOldLeft;
                }

                pSep->mnXLeft = nXLeft;
                pSep->mnXRight = nXRight-1;

                pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
                break;
            }
            else if( nXLeft == nOldLeft && nXRight != nOldRight )
            {
                // # 6b, 9

                if( nXRight > nOldRight )
                {
                    nXLeft = nOldRight+1; // 6b

                    // cannot break here, simply mark segment as removed,
                    // and go on with adapted nXLeft/nXRight
                    pSep->mbRemoved = true;
                }
                else
                {
                    pSep->mnXLeft = nXRight+1; // 9

                    pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
                    break;
                }
            }
            else // if( nXLeft != nOldLeft && nXRight != nOldRight ) follows automatically
            {
                // #4,5,6,7
                DBG_ASSERT( nXLeft != nOldLeft && nXRight != nOldRight,
                            "ImplRegionBand::XOr(): Case 4,5,6,7 expected all coordinates to be not equal!" );

                // The plain-jane check would look like this:
                //
                // if( nXLeft < nOldLeft )
                // {
                //     // #4,5
                //     if( nXRight > nOldRight )
                //     {
                //        // #4
                //     }
                //     else
                //     {
                //         // #5 done!
                //     }
                // }
                // else
                // {
                //     // #6,7
                //     if( nXRight > nOldRight )
                //     {
                //         // #6
                //     }
                //     else
                //     {
                //         // #7 done!
                //     }
                // }
                //
                // but since we generally don't have to care whether
                // it's 4 or 6 (only that we must not stop processing
                // here), condensed that in such a way that only the
                // coordinates get shuffled into correct ordering.

                if( nXLeft < nOldLeft )
                    ::std::swap( nOldLeft, nXLeft );

                bool bDone( false );

                if( nXRight < nOldRight )
                {
                    ::std::swap( nOldRight, nXRight );
                    bDone = true;
                }

                // now, nOldLeft<nXLeft<=nOldRight<nXRight always
                // holds. Note that we need the nXLeft<=nOldRight here, as
                // the intersection part might be only one pixel (original
                // nXLeft==nXRight)
                DBG_ASSERT( nOldLeft<nXLeft && nXLeft<=nOldRight && nOldRight<nXRight,
                            "ImplRegionBand::XOr(): Case 4,5,6,7 expected coordinates to be ordered now!" );

                pSep->mnXLeft = nOldLeft;
                pSep->mnXRight = nXLeft-1;

                nXLeft = nOldRight+1;
                // nxRight is already setup correctly

                if( bDone )
                {
                    // add behind current bandSep
                    pNewSep = new ImplRegionBandSep;

                    pNewSep->mnXLeft    = nXLeft;
                    pNewSep->mnXRight   = nXRight;
                    pNewSep->mpNextSep  = pSep->mpNextSep;
                    pNewSep->mbRemoved  = false;

                    // connections from the new separation
                    pSep->mpNextSep = pNewSep;

                    pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
                    break;
                }
            }
        }

        pPrevSep = pSep;
        pSep = pSep->mpNextSep;
    }

    // new separation completely right of existing bandSeps ?
    if( pPrevSep && nXLeft >= pPrevSep->mnXRight )
    {
        pNewSep             = new ImplRegionBandSep;
        pNewSep->mnXLeft    = nXLeft;
        pNewSep->mnXRight   = nXRight;
        pNewSep->mpNextSep  = NULL;
        pNewSep->mbRemoved  = false;

        // connections from the new separation
        pPrevSep->mpNextSep = pNewSep;
    }

    OptimizeBand();
}

// -----------------------------------------------------------------------

bool ImplRegionBand::IsInside( long nX )
{
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        if ( (pSep->mnXLeft <= nX) && (pSep->mnXRight >= nX) )
            return true;

        pSep = pSep->mpNextSep;
    }

    return false;
}

// -----------------------------------------------------------------------

bool ImplRegionBand::IsOver( long nLeft, long nRight )
{
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        if ( (pSep->mnXLeft < nRight) && (pSep->mnXRight > nLeft) )
            return true;

        pSep = pSep->mpNextSep;
    }

    return false;
}

// -----------------------------------------------------------------------

bool ImplRegionBand::IsInside( long nLeft, long nRight )
{
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep )
    {
        if ( (pSep->mnXLeft >= nLeft) && (nRight <= pSep->mnXRight) )
            return true;

        pSep = pSep->mpNextSep;
    }

    return false;
}

// -----------------------------------------------------------------------

long ImplRegionBand::GetXLeftBoundary() const
{
    DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XLeftBoundary -> no separation in band!" );

    return mpFirstSep->mnXLeft;
}

// -----------------------------------------------------------------------

long ImplRegionBand::GetXRightBoundary() const
{
    DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XRightBoundary -> no separation in band!" );

    // search last separation
    ImplRegionBandSep* pSep = mpFirstSep;
    while ( pSep->mpNextSep )
        pSep = pSep->mpNextSep;
    return pSep->mnXRight;
}

// -----------------------------------------------------------------------

bool ImplRegionBand::operator==( const ImplRegionBand& rRegionBand ) const
{
    ImplRegionBandSep*   pOwnRectBandSep = mpFirstSep;
    ImplRegionBandSep*   pSecondRectBandSep = rRegionBand.mpFirstSep;
    while ( pOwnRectBandSep && pSecondRectBandSep )
    {
        // get boundaries of current rectangle
        long nOwnXLeft = pOwnRectBandSep->mnXLeft;
        long nSecondXLeft = pSecondRectBandSep->mnXLeft;
        if ( nOwnXLeft != nSecondXLeft )
            return false;

        long nOwnXRight = pOwnRectBandSep->mnXRight;
        long nSecondXRight = pSecondRectBandSep->mnXRight;
        if ( nOwnXRight != nSecondXRight )
            return false;

        // get next separation from current band
        pOwnRectBandSep = pOwnRectBandSep->mpNextSep;

        // get next separation from current band
        pSecondRectBandSep = pSecondRectBandSep->mpNextSep;
    }

    // different number of separations?
    if ( pOwnRectBandSep || pSecondRectBandSep )
        return false;

    return true;
}

// -----------------------------------------------------------------------

ImplRegionBand* ImplRegionBand::SplitBand (const sal_Int32 nY)
{
    OSL_ASSERT(nY>mnYTop);
    OSL_ASSERT(nY<=mnYBottom);

    // Create a copy of the given band (we tell the constructor to copy the points together
    // with the seps.)
    ImplRegionBand* pLowerBand = new ImplRegionBand(*this, false);

    // Adapt vertical coordinates.
    mnYBottom = nY-1;
    pLowerBand->mnYTop = nY;

    // Insert new band into list of bands.
    pLowerBand->mpNextBand = mpNextBand;
    mpNextBand = pLowerBand;
    pLowerBand->mpPrevBand = this;
    if (pLowerBand->mpNextBand != NULL)
        pLowerBand->mpNextBand->mpPrevBand = pLowerBand;

    return pLowerBand;
}