regionband.cxx

Go to the documentation of this file.

/* -*- 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 <cstdlib>

#include <tools/stream.hxx>
#include <regionband.hxx>
#include <osl/diagnose.h>
#include <sal/log.hxx>

RegionBand::RegionBand()
:   mpFirstBand(nullptr),
    mpLastCheckedBand(nullptr)
{
}

RegionBand::RegionBand(const RegionBand& rRef)
:   mpFirstBand(nullptr),
    mpLastCheckedBand(nullptr)
{
    *this = rRef;
}

RegionBand& RegionBand::operator=(const RegionBand& rRef)
{
    if (this != &rRef)
    {
        ImplRegionBand* pPrevBand = nullptr;
        ImplRegionBand* pBand = rRef.mpFirstBand;

        while(pBand)
        {
            ImplRegionBand* pNewBand = new ImplRegionBand(*pBand);

            // first element? -> set as first into the list
            if(pBand == rRef.mpFirstBand)
            {
                mpFirstBand = pNewBand;
            }
            else
            {
                pPrevBand->mpNextBand = pNewBand;
            }

            pPrevBand = pNewBand;
            pBand = pBand->mpNextBand;
        }
    }
    return *this;
}

RegionBand::RegionBand(const tools::Rectangle& rRect)
:   mpFirstBand(nullptr),
    mpLastCheckedBand(nullptr)
{
    const tools::Long nTop(std::min(rRect.Top(), rRect.Bottom()));
    const tools::Long nBottom(std::max(rRect.Top(), rRect.Bottom()));
    const tools::Long nLeft(std::min(rRect.Left(), rRect.Right()));
    const tools::Long nRight(std::max(rRect.Left(), rRect.Right()));

    // add band with boundaries of the rectangle
    mpFirstBand = new ImplRegionBand(nTop, nBottom);

    // Set left and right boundaries of the band
    mpFirstBand->Union(nLeft, nRight);

}

void RegionBand::implReset()
{
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        ImplRegionBand* pTempBand = pBand->mpNextBand;
        delete pBand;
        pBand = pTempBand;
    }

    mpLastCheckedBand = nullptr;
    mpFirstBand = nullptr;
}

RegionBand::~RegionBand()
{
    implReset();
}

bool RegionBand::operator==( const RegionBand& rRegionBand ) const
{

    // initialise pointers
    ImplRegionBand*      pOwnRectBand = mpFirstBand;
    ImplRegionBandSep*   pOwnRectBandSep = pOwnRectBand->mpFirstSep;
    ImplRegionBand*      pSecondRectBand = rRegionBand.mpFirstBand;
    ImplRegionBandSep*   pSecondRectBandSep = pSecondRectBand->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 nOwnYTop = pOwnRectBand->mnYTop;
        tools::Long nSecondYTop = pSecondRectBand->mnYTop;

        if ( nOwnYTop != nSecondYTop )
        {
            return false;
        }

        tools::Long nOwnXRight = pOwnRectBandSep->mnXRight;
        tools::Long nSecondXRight = pSecondRectBandSep->mnXRight;

        if ( nOwnXRight != nSecondXRight )
        {
            return false;
        }

        tools::Long nOwnYBottom = pOwnRectBand->mnYBottom;
        tools::Long nSecondYBottom = pSecondRectBand->mnYBottom;

        if ( nOwnYBottom != nSecondYBottom )
        {
            return false;
        }

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

        // no separation found? -> go to next band!
        if ( !pOwnRectBandSep )
        {
            // get next band
            pOwnRectBand = pOwnRectBand->mpNextBand;

            // get first separation in current band
            if( pOwnRectBand )
            {
                pOwnRectBandSep = pOwnRectBand->mpFirstSep;
            }
        }

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

        // no separation found? -> go to next band!
        if ( !pSecondRectBandSep )
        {
            // get next band
            pSecondRectBand = pSecondRectBand->mpNextBand;

            // get first separation in current band
            if( pSecondRectBand )
            {
                pSecondRectBandSep = pSecondRectBand->mpFirstSep;
            }
        }

        if ( pOwnRectBandSep && !pSecondRectBandSep )
        {
            return false;
        }

        if ( !pOwnRectBandSep && pSecondRectBandSep )
        {
            return false;
        }
    }

    return true;
}

namespace {

enum StreamEntryType { STREAMENTRY_BANDHEADER, STREAMENTRY_SEPARATION, STREAMENTRY_END };

}

bool RegionBand::load(SvStream& rIStrm)
{
    // clear this instance data
    implReset();

    // get all bands
    ImplRegionBand* pCurrBand = nullptr;

    // get header from first element
    sal_uInt16 nTmp16(STREAMENTRY_END);
    rIStrm.ReadUInt16(nTmp16);

    if (STREAMENTRY_END == static_cast<StreamEntryType>(nTmp16))
        return false;

    size_t nRecordsPossible = rIStrm.remainingSize() / (2*sizeof(sal_Int32));
    if (!nRecordsPossible)
    {
        OSL_ENSURE(false, "premature end of region stream" );
        implReset();
        return false;
    }

    do
    {
        // insert new band or new separation?
        if(STREAMENTRY_BANDHEADER == static_cast<StreamEntryType>(nTmp16))
        {
            sal_Int32 nYTop(0);
            sal_Int32 nYBottom(0);

            rIStrm.ReadInt32( nYTop );
            rIStrm.ReadInt32( nYBottom );

            // create band
            ImplRegionBand* pNewBand = new ImplRegionBand( nYTop, nYBottom );

            // first element? -> set as first into the list
            if ( !pCurrBand )
            {
                mpFirstBand = pNewBand;
            }
            else
            {
                pCurrBand->mpNextBand = pNewBand;
            }

            // save pointer for next creation
            pCurrBand = pNewBand;
        }
        else
        {
            sal_Int32 nXLeft(0);
            sal_Int32 nXRight(0);

            rIStrm.ReadInt32( nXLeft );
            rIStrm.ReadInt32( nXRight );

            // add separation
            if ( pCurrBand )
            {
                pCurrBand->Union( nXLeft, nXRight );
            }
        }

        if( rIStrm.eof() )
        {
            OSL_ENSURE(false, "premature end of region stream" );
            implReset();
            return false;
        }

        // get next header
        rIStrm.ReadUInt16( nTmp16 );
    }
    while (STREAMENTRY_END != static_cast<StreamEntryType>(nTmp16) && rIStrm.good());
    if (!CheckConsistency())
    {
        implReset();
        return false;
    }
    return true;
}

void RegionBand::save(SvStream& rOStrm) const
{
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        // put boundaries
        rOStrm.WriteUInt16( STREAMENTRY_BANDHEADER );
        rOStrm.WriteInt32( pBand->mnYTop );
        rOStrm.WriteInt32( pBand->mnYBottom );

        // put separations of current band
        ImplRegionBandSep* pSep = pBand->mpFirstSep;

        while(pSep)
        {
            // put separation
            rOStrm.WriteUInt16( STREAMENTRY_SEPARATION );
            rOStrm.WriteInt32( pSep->mnXLeft );
            rOStrm.WriteInt32( pSep->mnXRight );

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

        pBand = pBand->mpNextBand;
    }

    // put endmarker
    rOStrm.WriteUInt16( STREAMENTRY_END );
}

bool RegionBand::isSingleRectangle() const
{
    // just one band?
    if(mpFirstBand && !mpFirstBand->mpNextBand)
    {
        // just one sep?
        if(mpFirstBand->mpFirstSep && !mpFirstBand->mpFirstSep->mpNextSep)
        {
            return true;
        }
    }

    return false;
}

void RegionBand::InsertBand(ImplRegionBand* pPreviousBand, ImplRegionBand* pBandToInsert)
{
    OSL_ASSERT(pBandToInsert!=nullptr);

    if(!pPreviousBand)
    {
        // Insert band before all others.
        if(mpFirstBand)
        {
            mpFirstBand->mpPrevBand = pBandToInsert;
        }

        pBandToInsert->mpNextBand = mpFirstBand;
        mpFirstBand = pBandToInsert;
    }
    else
    {
        // Insert band directly after pPreviousBand.
        pBandToInsert->mpNextBand = pPreviousBand->mpNextBand;
        pPreviousBand->mpNextBand = pBandToInsert;
        pBandToInsert->mpPrevBand = pPreviousBand;
    }

}

void RegionBand::processPoints()
{
    ImplRegionBand* pRegionBand = mpFirstBand;

    while(pRegionBand)
    {
        // generate separations from the lines and process union
        pRegionBand->ProcessPoints();
        pRegionBand = pRegionBand->mpNextBand;
    }

}

void RegionBand::ImplAddMissingBands(const tools::Long nTop, const tools::Long nBottom)
{
    // Iterate over already existing bands and add missing bands atop the
    // first and between two bands.
    ImplRegionBand* pPreviousBand = nullptr;
    ImplRegionBand* pBand = ImplGetFirstRegionBand();
    tools::Long nCurrentTop (nTop);

    while (pBand != nullptr && nCurrentTop<nBottom)
    {
        if (nCurrentTop < pBand->mnYTop)
        {
            // Create new band above the current band.
            ImplRegionBand* pAboveBand = new ImplRegionBand(
                nCurrentTop,
                ::std::min(nBottom,pBand->mnYTop-1));
            InsertBand(pPreviousBand, pAboveBand);
        }

        // Adapt the top of the interval to prevent overlapping bands.
        nCurrentTop = ::std::max(nTop, pBand->mnYBottom+1);

        // Advance to next band.
        pPreviousBand = pBand;
        pBand = pBand->mpNextBand;
    }

    // We still have to cover two cases:
    // 1. The region does not yet contain any bands.
    // 2. The interval nTop->nBottom extends past the bottom most band.
    if (nCurrentTop <= nBottom
        && (pBand==nullptr || nBottom>pBand->mnYBottom))
    {
        // When there is no previous band then the new one will be the
        // first.  Otherwise the new band is inserted behind the last band.
        InsertBand(
            pPreviousBand,
            new ImplRegionBand(
                nCurrentTop,
                nBottom));
    }

}

void RegionBand::CreateBandRange(tools::Long nYTop, tools::Long nYBottom)
{
    // add top band
    mpFirstBand = new ImplRegionBand( nYTop-1, nYTop-1 );

    // begin first search from the first element
    mpLastCheckedBand = mpFirstBand;
    ImplRegionBand* pBand = mpFirstBand;

    for ( tools::Long i = nYTop; i <= nYBottom+1; i++ )
    {
        // create new band
        ImplRegionBand* pNewBand = new ImplRegionBand( i, i );
        pBand->mpNextBand = pNewBand;

        if ( pBand != mpFirstBand )
        {
            pNewBand->mpPrevBand = pBand;
        }

        pBand = pBand->mpNextBand;
    }

}

void RegionBand::InsertLine(const Point& rStartPt, const Point& rEndPt, tools::Long nLineId)
{
    tools::Long nX, nY;

    // lines consisting of a single point do not interest here
    if ( rStartPt == rEndPt )
    {
        return;
    }

    LineType eLineType = (rStartPt.Y() > rEndPt.Y()) ? LineType::Descending : LineType::Ascending;
    if ( rStartPt.X() == rEndPt.X() )
    {
        // vertical line
        const tools::Long nEndY = rEndPt.Y();

        nX = rStartPt.X();
        nY = rStartPt.Y();

        if( nEndY > nY )
        {
            for ( ; nY <= nEndY; nY++ )
            {
                Point aNewPoint( nX, nY );
                InsertPoint( aNewPoint, nLineId,
                             (aNewPoint == rEndPt) || (aNewPoint == rStartPt),
                             eLineType );
            }
        }
        else
        {
            for ( ; nY >= nEndY; nY-- )
            {
                Point aNewPoint( nX, nY );
                InsertPoint( aNewPoint, nLineId,
                             (aNewPoint == rEndPt) || (aNewPoint == rStartPt),
                             eLineType );
            }
        }
    }
    else if ( rStartPt.Y() != rEndPt.Y() )
    {
        const tools::Long  nDX = std::abs( rEndPt.X() - rStartPt.X() );
        const tools::Long  nDY = std::abs( rEndPt.Y() - rStartPt.Y() );
        const tools::Long  nStartX = rStartPt.X();
        const tools::Long  nStartY = rStartPt.Y();
        const tools::Long  nEndX = rEndPt.X();
        const tools::Long  nEndY = rEndPt.Y();
        const tools::Long  nXInc = ( nStartX < nEndX ) ? 1 : -1;
        const tools::Long  nYInc = ( nStartY < nEndY ) ? 1 : -1;

        if ( nDX >= nDY )
        {
            const tools::Long  nDYX = ( nDY - nDX ) * 2;
            const tools::Long  nDY2 = nDY << 1;
            tools::Long        nD = nDY2 - nDX;

            for ( nX = nStartX, nY = nStartY; nX != nEndX; nX += nXInc )
            {
                InsertPoint( Point( nX, nY ), nLineId, nStartX == nX, eLineType );

                if ( nD < 0 )
                    nD += nDY2;
                else
                {
                    nD += nDYX;
                    nY += nYInc;
                }
            }
        }
        else
        {
            const tools::Long  nDYX = ( nDX - nDY ) * 2;
            const tools::Long  nDY2 = nDX << 1;
            tools::Long        nD = nDY2 - nDY;

            for ( nX = nStartX, nY = nStartY; nY != nEndY; nY += nYInc )
            {
                InsertPoint( Point( nX, nY ), nLineId, nStartY == nY, eLineType );

                if ( nD < 0 )
                    nD += nDY2;
                else
                {
                    nD += nDYX;
                    nX += nXInc;
                }
            }
        }

        // last point
        InsertPoint( Point( nEndX, nEndY ), nLineId, true, eLineType );
    }
}

void RegionBand::InsertPoint(const Point &rPoint, tools::Long nLineID, bool bEndPoint, LineType eLineType)
{
    SAL_WARN_IF( mpFirstBand == nullptr, "vcl", "RegionBand::InsertPoint - no bands available!" );

    if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
    {
        mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
        return;
    }

    if ( rPoint.Y() > mpLastCheckedBand->mnYTop )
    {
        // Search ascending
        while ( mpLastCheckedBand )
        {
            // Insert point if possible
            if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
            {
                mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
                return;
            }

            mpLastCheckedBand = mpLastCheckedBand->mpNextBand;
        }

        OSL_ENSURE(false, "RegionBand::InsertPoint reached the end of the list!" );
    }
    else
    {
        // Search descending
        while ( mpLastCheckedBand )
        {
            // Insert point if possible
            if ( rPoint.Y() == mpLastCheckedBand->mnYTop )
            {
                mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType );
                return;
            }

            mpLastCheckedBand = mpLastCheckedBand->mpPrevBand;
        }

        OSL_ENSURE(false, "RegionBand::InsertPoint reached the beginning of the list!" );
    }

    OSL_ENSURE(false, "RegionBand::InsertPoint point not inserted!" );

    // reinitialize pointer (should never be reached!)
    mpLastCheckedBand = mpFirstBand;
}

bool RegionBand::OptimizeBandList()
{
    ImplRegionBand* pPrevBand = nullptr;
    ImplRegionBand* pBand = mpFirstBand;

    while ( pBand )
    {
        const bool bBTEqual = pBand->mpNextBand && (pBand->mnYBottom == pBand->mpNextBand->mnYTop);

        // no separation? -> remove!
        if ( pBand->IsEmpty() || (bBTEqual && (pBand->mnYBottom == pBand->mnYTop)) )
        {
            // save pointer
            ImplRegionBand* pOldBand = pBand;

            // previous element of the list
            if ( pBand == mpFirstBand )
                mpFirstBand = pBand->mpNextBand;
            else
                pPrevBand->mpNextBand = pBand->mpNextBand;

            pBand = pBand->mpNextBand;
            delete pOldBand;
        }
        else
        {
            // fixup
            if ( bBTEqual )
                pBand->mnYBottom = pBand->mpNextBand->mnYTop-1;

            // this and next band with equal separations? -> combine!
            if ( pBand->mpNextBand &&
                 ((pBand->mnYBottom+1) == pBand->mpNextBand->mnYTop) &&
                 (*pBand == *pBand->mpNextBand) )
            {
                // expand current height
                pBand->mnYBottom = pBand->mpNextBand->mnYBottom;

                // remove next band from list
                ImplRegionBand* pDeletedBand = pBand->mpNextBand;
                pBand->mpNextBand = pDeletedBand->mpNextBand;
                delete pDeletedBand;

                // check band again!
            }
            else
            {
                // count rectangles within band
                ImplRegionBandSep* pSep = pBand->mpFirstSep;
                while ( pSep )
                {
                    pSep = pSep->mpNextSep;
                }

                pPrevBand = pBand;
                pBand = pBand->mpNextBand;
            }
        }
    }

#ifdef DBG_UTIL
    pBand = mpFirstBand;
    while ( pBand )
    {
        SAL_WARN_IF( pBand->mpFirstSep == nullptr, "vcl", "Exiting RegionBand::OptimizeBandList(): empty band in region!" );

        if ( pBand->mnYBottom < pBand->mnYTop )
            OSL_ENSURE(false, "RegionBand::OptimizeBandList(): YBottomBoundary < YTopBoundary" );

        if ( pBand->mpNextBand && pBand->mnYBottom >= pBand->mpNextBand->mnYTop )
            OSL_ENSURE(false, "RegionBand::OptimizeBandList(): overlapping bands in region!" );

        pBand = pBand->mpNextBand;
    }
#endif

    return (nullptr != mpFirstBand);
}

void RegionBand::Move(tools::Long nHorzMove, tools::Long nVertMove)
{
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        // process the vertical move
        if(nVertMove)
        {
            pBand->mnYTop = pBand->mnYTop + nVertMove;
            pBand->mnYBottom = pBand->mnYBottom + nVertMove;
        }

        // process the horizontal move
        if(nHorzMove)
        {
            pBand->MoveX(nHorzMove);
        }

        pBand = pBand->mpNextBand;
    }

}

void RegionBand::Scale(double fScaleX, double fScaleY)
{
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        // process the vertical move
        if(0.0 != fScaleY)
        {
            pBand->mnYTop = basegfx::fround(pBand->mnYTop * fScaleY);
            pBand->mnYBottom = basegfx::fround(pBand->mnYBottom * fScaleY);
        }

        // process the horizontal move
        if(0.0 != fScaleX)
        {
            pBand->ScaleX(fScaleX);
        }

        pBand = pBand->mpNextBand;
    }

}

void RegionBand::InsertBands(tools::Long nTop, tools::Long nBottom)
{
    // region empty? -> set rectangle as first entry!
    if ( !mpFirstBand )
    {
        // add band with boundaries of the rectangle
        mpFirstBand = new ImplRegionBand( nTop, nBottom );
        return;
    }

    // find/insert bands for the boundaries of the rectangle
    bool bTopBoundaryInserted = false;
    bool bTop2BoundaryInserted = false;
    bool bBottomBoundaryInserted = false;

    // special case: top boundary is above the first band
    ImplRegionBand* pNewBand;

    if ( nTop < mpFirstBand->mnYTop )
    {
        // create new band above the first in the list
        pNewBand = new ImplRegionBand( nTop, mpFirstBand->mnYTop );

        if ( nBottom < mpFirstBand->mnYTop )
        {
            pNewBand->mnYBottom = nBottom;
        }

        // insert band into the list
        pNewBand->mpNextBand = mpFirstBand;
        mpFirstBand = pNewBand;

        bTopBoundaryInserted = true;
    }

    // insert band(s) into the list
    ImplRegionBand* pBand = mpFirstBand;

    while ( pBand )
    {
        // Insert Bands if possible
        if ( !bTopBoundaryInserted )
        {
            bTopBoundaryInserted = InsertSingleBand( pBand, nTop - 1 );
        }

        if ( !bTop2BoundaryInserted )
        {
            bTop2BoundaryInserted = InsertSingleBand( pBand, nTop );
        }

        if ( !bBottomBoundaryInserted && (nTop != nBottom) )
        {
            bBottomBoundaryInserted = InsertSingleBand( pBand, nBottom );
        }

        // both boundaries inserted? -> nothing more to do
        if ( bTopBoundaryInserted && bTop2BoundaryInserted && bBottomBoundaryInserted )
        {
            break;
        }

        // insert bands between two bands if necessary
        if ( pBand->mpNextBand )
        {
            if ( (pBand->mnYBottom + 1) < pBand->mpNextBand->mnYTop )
            {
                // copy band with list and set new boundary
                pNewBand = new ImplRegionBand( pBand->mnYBottom+1, pBand->mpNextBand->mnYTop-1 );

                // insert band into the list
                pNewBand->mpNextBand = pBand->mpNextBand;
                pBand->mpNextBand = pNewBand;
            }
        }

        pBand = pBand->mpNextBand;
    }

}

bool RegionBand::InsertSingleBand(ImplRegionBand* pBand, tools::Long nYBandPosition)
{
    // boundary already included in band with height 1? -> nothing to do!
    if ( (pBand->mnYTop == pBand->mnYBottom) && (nYBandPosition == pBand->mnYTop) )
    {
        return true;
    }

    // insert single height band on top?
    ImplRegionBand* pNewBand;

    if ( nYBandPosition == pBand->mnYTop )
    {
        // copy band with list and set new boundary
        pNewBand = new ImplRegionBand( *pBand );
        pNewBand->mnYTop = nYBandPosition+1;

        // insert band into the list
        pNewBand->mpNextBand = pBand->mpNextBand;
        pBand->mnYBottom = nYBandPosition;
        pBand->mpNextBand = pNewBand;

        return true;
    }

    // top of new rectangle within the current band? -> insert new band and copy data
    if ( (nYBandPosition > pBand->mnYTop) && (nYBandPosition < pBand->mnYBottom) )
    {
        // copy band with list and set new boundary
        pNewBand = new ImplRegionBand( *pBand );
        pNewBand->mnYTop = nYBandPosition;

        // insert band into the list
        pNewBand->mpNextBand = pBand->mpNextBand;
        pBand->mnYBottom = nYBandPosition;
        pBand->mpNextBand = pNewBand;

        // copy band with list and set new boundary
        pNewBand = new ImplRegionBand( *pBand );
        pNewBand->mnYTop = nYBandPosition;

        // insert band into the list
        pBand->mpNextBand->mnYTop = nYBandPosition+1;

        pNewBand->mpNextBand = pBand->mpNextBand;
        pBand->mnYBottom = nYBandPosition - 1;
        pBand->mpNextBand = pNewBand;

        return true;
    }

    // create new band behind the current in the list
    if ( !pBand->mpNextBand )
    {
        if ( nYBandPosition == pBand->mnYBottom )
        {
            // copy band with list and set new boundary
            pNewBand = new ImplRegionBand( *pBand );
            pNewBand->mnYTop = pBand->mnYBottom;
            pNewBand->mnYBottom = nYBandPosition;

            pBand->mnYBottom = nYBandPosition-1;

            // append band to the list
            pBand->mpNextBand = pNewBand;
            return true;
        }

        if ( nYBandPosition > pBand->mnYBottom )
        {
            // create new band
            pNewBand = new ImplRegionBand( pBand->mnYBottom + 1, nYBandPosition );

            // append band to the list
            pBand->mpNextBand = pNewBand;
            return true;
        }
    }

    return false;
}

void RegionBand::Union(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
{
    SAL_WARN_IF( nLeft > nRight, "vcl", "RegionBand::Union() - nLeft > nRight" );
    SAL_WARN_IF( nTop > nBottom, "vcl", "RegionBand::Union() - nTop > nBottom" );

    // process union
    ImplRegionBand* pBand = mpFirstBand;
    while ( pBand )
    {
        if ( pBand->mnYTop >= nTop )
        {
            if ( pBand->mnYBottom <= nBottom )
                pBand->Union( nLeft, nRight );
            else
            {
#ifdef DBG_UTIL
                tools::Long nCurY = pBand->mnYBottom;
                pBand = pBand->mpNextBand;
                while ( pBand )
                {
                    if ( (pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY) )
                    {
                        OSL_ENSURE(false, "RegionBand::Union() - Bands not sorted!" );
                    }
                    pBand = pBand->mpNextBand;
                }
#endif
                break;
            }
        }

        pBand = pBand->mpNextBand;
    }

}

void RegionBand::Intersect(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
{
    // process intersections
    ImplRegionBand* pPrevBand = nullptr;
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        // band within intersection boundary? -> process. otherwise remove
        if((pBand->mnYTop >= nTop) && (pBand->mnYBottom <= nBottom))
        {
            // process intersection
            pBand->Intersect(nLeft, nRight);
            pPrevBand = pBand;
            pBand = pBand->mpNextBand;
        }
        else
        {
            ImplRegionBand* pOldBand = pBand;

            if(pBand == mpFirstBand)
            {
                mpFirstBand = pBand->mpNextBand;
            }
            else
            {
                pPrevBand->mpNextBand = pBand->mpNextBand;
            }

            pBand = pBand->mpNextBand;
            delete pOldBand;
        }
    }

}

void RegionBand::Union(const RegionBand& rSource)
{
    // apply all rectangles from rSource to this
    ImplRegionBand* pBand = rSource.mpFirstBand;

    while ( pBand )
    {
        // insert bands if the boundaries are not already in the list
        InsertBands(pBand->mnYTop, pBand->mnYBottom);

        // process all elements of the list
        ImplRegionBandSep* pSep = pBand->mpFirstSep;

        while(pSep)
        {
            Union(pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom);
            pSep = pSep->mpNextSep;
        }

        pBand = pBand->mpNextBand;
    }

}

void RegionBand::Exclude(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
{
    SAL_WARN_IF( nLeft > nRight, "vcl", "RegionBand::Exclude() - nLeft > nRight" );
    SAL_WARN_IF( nTop > nBottom, "vcl", "RegionBand::Exclude() - nTop > nBottom" );

    // process exclude
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        if(pBand->mnYTop >= nTop)
        {
            if(pBand->mnYBottom <= nBottom)
            {
                pBand->Exclude(nLeft, nRight);
            }
            else
            {
#ifdef DBG_UTIL
                tools::Long nCurY = pBand->mnYBottom;
                pBand = pBand->mpNextBand;

                while(pBand)
                {
                    if((pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY))
                    {
                        OSL_ENSURE(false, "RegionBand::Exclude() - Bands not sorted!" );
                    }

                    pBand = pBand->mpNextBand;
                }
#endif
                break;
            }
        }

        pBand = pBand->mpNextBand;
    }

}

void RegionBand::XOr(tools::Long nLeft, tools::Long nTop, tools::Long nRight, tools::Long nBottom)
{
    SAL_WARN_IF( nLeft > nRight, "vcl", "RegionBand::Exclude() - nLeft > nRight" );
    SAL_WARN_IF( nTop > nBottom, "vcl", "RegionBand::Exclude() - nTop > nBottom" );

    // process xor
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        if(pBand->mnYTop >= nTop)
        {
            if(pBand->mnYBottom <= nBottom)
            {
                pBand->XOr(nLeft, nRight);
            }
            else
            {
#ifdef DBG_UTIL
                tools::Long nCurY = pBand->mnYBottom;
                pBand = pBand->mpNextBand;

                while(pBand)
                {
                    if((pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY))
                    {
                        OSL_ENSURE(false, "RegionBand::XOr() - Bands not sorted!" );
                    }

                    pBand = pBand->mpNextBand;
                }
#endif
                break;
            }
        }

        pBand = pBand->mpNextBand;
    }

}

void RegionBand::Intersect(const RegionBand& rSource)
{
    // mark all bands as untouched
    ImplRegionBand* pBand = mpFirstBand;

    while ( pBand )
    {
        pBand->mbTouched = false;
        pBand = pBand->mpNextBand;
    }

    pBand = rSource.mpFirstBand;

    while ( pBand )
    {
        // insert bands if the boundaries are not already in the list
        InsertBands( pBand->mnYTop, pBand->mnYBottom );

        // process all elements of the list
        ImplRegionBandSep* pSep = pBand->mpFirstSep;

        while ( pSep )
        {
            // left boundary?
            if ( pSep == pBand->mpFirstSep )
            {
                // process intersection and do not remove untouched bands
                Exclude( LONG_MIN+1, pBand->mnYTop, pSep->mnXLeft-1, pBand->mnYBottom );
            }

            // right boundary?
            if ( pSep->mpNextSep == nullptr )
            {
                // process intersection and do not remove untouched bands
                Exclude( pSep->mnXRight+1, pBand->mnYTop, LONG_MAX-1, pBand->mnYBottom );
            }
            else
            {
                // process intersection and do not remove untouched bands
                Exclude( pSep->mnXRight+1, pBand->mnYTop, pSep->mpNextSep->mnXLeft-1, pBand->mnYBottom );
            }

            pSep = pSep->mpNextSep;
        }

        pBand = pBand->mpNextBand;
    }

    // remove all untouched bands if bands already left
    ImplRegionBand* pPrevBand = nullptr;
    pBand = mpFirstBand;

    while ( pBand )
    {
        if ( !pBand->mbTouched )
        {
            // save pointer
            ImplRegionBand* pOldBand = pBand;

            // previous element of the list
            if ( pBand == mpFirstBand )
            {
                mpFirstBand = pBand->mpNextBand;
            }
            else
            {
                pPrevBand->mpNextBand = pBand->mpNextBand;
            }

            pBand = pBand->mpNextBand;
            delete pOldBand;
        }
        else
        {
            pPrevBand = pBand;
            pBand = pBand->mpNextBand;
        }
    }

}

bool RegionBand::Exclude(const RegionBand& rSource)
{
    // apply all rectangles to the region passed to this region
    ImplRegionBand* pBand = rSource.mpFirstBand;

    while ( pBand )
    {
        // insert bands if the boundaries are not already in the list
        InsertBands( pBand->mnYTop, pBand->mnYBottom );

        // process all elements of the list
        ImplRegionBandSep* pSep = pBand->mpFirstSep;

        while ( pSep )
        {
            Exclude( pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom );
            pSep = pSep->mpNextSep;
        }

        // to test less bands, already check in the loop
        if ( !OptimizeBandList() )
        {
            return false;
        }

        pBand = pBand->mpNextBand;
    }

    return true;
}

bool RegionBand::CheckConsistency() const
{
    if (!mpFirstBand)
        return true;
    // look in the band list (don't test first band again!)
    const ImplRegionBand* pBand = mpFirstBand->mpNextBand;
    while (pBand)
    {
        if (!pBand->mpFirstSep)
            return false;
        pBand = pBand->mpNextBand;
    }
    return true;
}

tools::Rectangle RegionBand::GetBoundRect() const
{

    // get the boundaries of the first band
    tools::Long nYTop(mpFirstBand->mnYTop);
    tools::Long nYBottom(mpFirstBand->mnYBottom);
    tools::Long nXLeft(mpFirstBand->GetXLeftBoundary());
    tools::Long nXRight(mpFirstBand->GetXRightBoundary());

    // look in the band list (don't test first band again!)
    ImplRegionBand* pBand = mpFirstBand->mpNextBand;

    while ( pBand )
    {
        nYBottom = pBand->mnYBottom;
        nXLeft = std::min( nXLeft, pBand->GetXLeftBoundary() );
        nXRight = std::max( nXRight, pBand->GetXRightBoundary() );

        pBand = pBand->mpNextBand;
    }

    return tools::Rectangle( nXLeft, nYTop, nXRight, nYBottom );
}

void RegionBand::XOr(const RegionBand& rSource)
{
    ImplRegionBand* pBand = rSource.mpFirstBand;

    while ( pBand )
    {
        // insert bands if the boundaries are not already in the list
        InsertBands( pBand->mnYTop, pBand->mnYBottom );

        // process all elements of the list
        ImplRegionBandSep* pSep = pBand->mpFirstSep;

        while ( pSep )
        {
            XOr( pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom );
            pSep = pSep->mpNextSep;
        }

        pBand = pBand->mpNextBand;
    }
}

bool RegionBand::Contains(const Point& rPoint) const
{

    // search band list
    ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        // is point within band?
        if((pBand->mnYTop <= rPoint.Y()) && (pBand->mnYBottom >= rPoint.Y()))
        {
            // is point within separation of the band?
            return pBand->Contains(rPoint.X());
        }

        pBand = pBand->mpNextBand;
    }

    return false;
}

void RegionBand::GetRegionRectangles(RectangleVector& rTarget) const
{
    // clear result vector
    rTarget.clear();
    ImplRegionBand* pCurrRectBand = mpFirstBand;
    tools::Rectangle aRectangle;

    while(pCurrRectBand)
    {
        ImplRegionBandSep* pCurrRectBandSep = pCurrRectBand->mpFirstSep;

        aRectangle.SetTop( pCurrRectBand->mnYTop );
        aRectangle.SetBottom( pCurrRectBand->mnYBottom );

        while(pCurrRectBandSep)
        {
            aRectangle.SetLeft( pCurrRectBandSep->mnXLeft );
            aRectangle.SetRight( pCurrRectBandSep->mnXRight );
            rTarget.push_back(aRectangle);
            pCurrRectBandSep = pCurrRectBandSep->mpNextSep;
        }

        pCurrRectBand = pCurrRectBand->mpNextBand;
    }
}

sal_uInt32 RegionBand::getRectangleCount() const
{
    sal_uInt32 nCount = 0;
    const ImplRegionBand* pBand = mpFirstBand;

    while(pBand)
    {
        ImplRegionBandSep* pSep = pBand->mpFirstSep;

        while(pSep)
        {
            nCount++;
            pSep = pSep->mpNextSep;
        }

        pBand = pBand->mpNextBand;
    }

    return nCount;
}

#ifdef DBG_UTIL
const char* ImplDbgTestRegionBand(const void* pObj)
{
    const RegionBand* pRegionBand = static_cast< const RegionBand* >(pObj);

    if(pRegionBand)
    {
        const ImplRegionBand* pBand = pRegionBand->ImplGetFirstRegionBand();

        while(pBand)
        {
            if(pBand->mnYBottom < pBand->mnYTop)
            {
                return "YBottom < YTop";
            }

            if(pBand->mpNextBand)
            {
                if(pBand->mnYBottom >= pBand->mpNextBand->mnYTop)
                {
                    return "overlapping bands in region";
                }
            }

            if(pBand->mbTouched)
            {
                return "Band-mbTouched overwrite";
            }

            ImplRegionBandSep* pSep = pBand->mpFirstSep;

            while(pSep)
            {
                if(pSep->mnXRight < pSep->mnXLeft)
                {
                    return "XLeft < XRight";
                }

                if(pSep->mpNextSep)
                {
                    if(pSep->mnXRight >= pSep->mpNextSep->mnXLeft)
                    {
                        return "overlapping separations in region";
                    }
                }

                if ( pSep->mbRemoved )
                {
                    return "Sep-mbRemoved overwrite";
                }

                pSep = pSep->mpNextSep;
            }

            pBand = pBand->mpNextBand;
        }
    }

    return nullptr;
}
#endif

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