Quelle  regband.cxx   Sprache: C

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
 * This file is part of the LibreOffice project.
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * This file incorporates work covered by the following license notice:
 *
 *   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 .
 */

#include <sal/config.h>

#include <basegfx/numeric/ftools.hxx>
#include <tools/helpers.hxx>
#include <osl/diagnose.h>
#include <sal/log.hxx>

#include <regband.hxx>

// ImplRegionBand

// Each band contains all rectangles between upper and lower border.
// For Union, Intersect, Xor and Exclude operations rectangles of
// equal height are evaluated. The borders of the bands should always
// be chosen such that this is possible.

// If possible, rectangles within the bands are condensed.

// When converting polygons all points of the polygon are registered
// in the individual bands (for each band they are stored as
// points in a list). After registration of these points they are
// converted to rectangles and the points in the list are deleted.

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

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

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

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

    // copy all elements of the list with separations
    ImplRegionBandSep* pNewSep;
    ImplRegionBandSep* pPrevSep = nullptr;
    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  = nullptr;
        if ( pSep == rRegionBand.mpFirstSep )
            mpFirstSep = pNewSep;
        else
            pPrevSep->mpNextSep = pNewSep;

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

    if (  bIgnorePoints)
        return;

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

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

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

ImplRegionBand::~ImplRegionBand()
{
    SAL_WARN_IF( mpFirstBandPoint != nullptr, "vcl", "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->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
    delete pRegionBandPoint;

    // list is now empty
    mpFirstBandPoint = nullptr;
}

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

bool ImplRegionBand::InsertPoint( tools::Long nX, tools::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 = nullptr;
        return true;
    }

    // look if line already touched the band
    ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
    ImplRegionBandPoint* pLastTestedRegionBandPoint = nullptr;
    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 = nullptr;
    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    = nullptr;

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

    return true;
}

void ImplRegionBand::MoveX( tools::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 = basegfx::fround<tools::Long>(pSep->mnXLeft * fHorzScale);
        pSep->mnXRight = basegfx::fround<tools::Long>(pSep->mnXRight * fHorzScale);
        pSep = pSep->mpNextSep;
    }
}

// combine overlapping separations

void ImplRegionBand::OptimizeBand()
{
    ImplRegionBandSep* pPrevSep = nullptr;
    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;
    }
}

void ImplRegionBand::Union( tools::Long nXLeft, tools::Long nXRight )
{
    SAL_WARN_IF( nXLeft > nXRight, "vcl", "ImplRegionBand::Union(): nxLeft > nXRight" );

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

    // process real union
    ImplRegionBandSep* pNewSep;
    ImplRegionBandSep* pPrevSep = nullptr;
    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  = nullptr;
            break;
        }

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

    OptimizeBand();
}

void ImplRegionBand::Intersect( tools::Long nXLeft, tools::Long nXRight )
{
    SAL_WARN_IF( nXLeft > nXRight, "vcl", "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( tools::Long nXLeft, tools::Long nXRight )
{
    SAL_WARN_IF( nXLeft > nXRight, "vcl", "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 = nullptr;
    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( tools::Long nXLeft, tools::Long nXRight )
{
    SAL_WARN_IF( nXLeft > nXRight, "vcl", "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 mimics 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   = nullptr;
        return;
    }

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

    while ( pSep  )
    {
        tools::Long nOldLeft( pSep->mnXLeft );
        tools::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 = nullptr; // do not run accidentally into the "right" case when breaking the loop
                break;
            }
            else if( nXLeft == nOldLeft && nXRight == nOldRight )
            {
                // #3
                pSep->mbRemoved = true;
                pPrevSep = nullptr; // 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 = nullptr; // 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 = nullptr; // 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
                SAL_WARN_IF( nXLeft == nOldLeft || nXRight == nOldRight, "vcl",
                            "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)
                SAL_WARN_IF( nOldLeft==nXLeft || nXLeft>nOldRight || nOldRight>=nXRight, "vcl",
                            "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 = nullptr; // 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  = nullptr;
        pNewSep->mbRemoved  = false;

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

    OptimizeBand();
}

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

        pSep = pSep->mpNextSep;
    }

    return false;
}

tools::Long ImplRegionBand::GetXLeftBoundary() const
{
    SAL_WARN_IF(mpFirstSep == nullptr, "vcl", "ImplRegionBand::XLeftBoundary -> no separation in band!");

    return mpFirstSep ? mpFirstSep->mnXLeft : 0;
}

tools::Long ImplRegionBand::GetXRightBoundary() const
{
    SAL_WARN_IF( mpFirstSep == nullptr, "vcl", "ImplRegionBand::XRightBoundary -> no separation in band!" );
    if (!mpFirstSep)
        return 0;
    // 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
        tools::Long nOwnXLeft = pOwnRectBandSep->mnXLeft;
        tools::Long nSecondXLeft = pSecondRectBandSep->mnXLeft;
        if ( nOwnXLeft != nSecondXLeft )
            return false;

        tools::Long nOwnXRight = pOwnRectBandSep->mnXRight;
        tools::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?
    return !(pOwnRectBandSep || pSecondRectBandSep);
}

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 != nullptr)
        pLowerBand->mpNextBand->mpPrevBand = pLowerBand;

    return pLowerBand;
}

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */