diff options
Diffstat (limited to 'vcl/source/gdi/regionband.cxx')
| -rw-r--r-- | vcl/source/gdi/regionband.cxx | 1365 |
1 files changed, 1365 insertions, 0 deletions
diff --git a/vcl/source/gdi/regionband.cxx b/vcl/source/gdi/regionband.cxx new file mode 100644 index 0000000000..7b48df7a09 --- /dev/null +++ b/vcl/source/gdi/regionband.cxx @@ -0,0 +1,1365 @@ +/* -*- 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 <o3tl/safeint.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; + } + +} + +/** This function is similar to the RegionBand::InsertBands() method. + It creates a minimal set of missing bands so that the entire vertical + interval from nTop to nBottom is covered by bands. +*/ +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 = o3tl::saturating_add(pBand->mnYTop, nVertMove); + pBand->mnYBottom = o3tl::saturating_add(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 +{ + if (!mpFirstBand) + return tools::Rectangle(); + + // 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: */ |