CWS-TOOLING: integrate CWS impress162

2009-02-19 13:02:17 +0100 af  r268275 : #i93945# Stop forcing long into sal_Int32.
2009-01-16 15:24:01 +0100 af  r266424 : CWS-TOOLING: rebase CWS impress162 to trunk@265758 (milestone: DEV300:m38)
2008-11-21 15:17:22 +0100 af  r264143 : CWS-TOOLING: rebase CWS impress162 to trunk@263288 (milestone: DEV300:m35)
2008-11-20 16:29:33 +0100 af  r264067 : Merge in latest fixes to the cws command.
2008-11-20 16:25:36 +0100 af  r264066 : Merge in latest fixes to the cws command.
2008-11-20 14:37:15 +0100 af  r264054 : Merge in latest fixes to the cws command.
2008-11-20 14:01:36 +0100 af  r264051 : Resolved merge conflicts.
2008-11-20 14:01:16 +0100 af  r264050 : Resolved merge conflicts.
2008-11-19 15:45:05 +0100 af  r263998 : Migrate CWS impress162 to SVN.

1 files changed, 310 insertions, 31 deletions

diff --git a/vcl/source/gdi/region.cxx b/vcl/source/gdi/region.cxx
index fd14b5224206..b98712419cf1 100644
--- a/vcl/source/gdi/region.cxx
+++ b/vcl/source/gdi/region.cxx
@@ -7,7 +7,7 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: region.cxx,v $
- * $Revision: 1.18 $
+ * $Revision: 1.18.36.1 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -77,6 +77,247 @@ DBG_NAME( Region )
 DBG_NAMEEX( Polygon )
 DBG_NAMEEX( PolyPolygon )
 
+namespace {
+
+/** Return <TRUE/> when the given polygon is rectiliner and oriented so that
+    all sides are either horizontal or vertical.
+*/
+bool ImplIsPolygonRectilinear (const PolyPolygon& rPolyPoly)
+{
+    // Iterate over all polygons.
+    const USHORT nPolyCount = rPolyPoly.Count();
+    for (USHORT nPoly = 0; nPoly < nPolyCount; ++nPoly)
+    {
+        const Polygon&  aPoly = rPolyPoly.GetObject(nPoly);
+
+        // Iterate over all edges of the current polygon.
+        const USHORT nSize = aPoly.GetSize();
+
+        if (nSize < 2)
+            continue;
+        Point aPoint (aPoly.GetPoint(0));
+        const Point aLastPoint (aPoint);
+        for (USHORT nPoint = 1; nPoint < nSize; ++nPoint)
+        {
+            const Point aNextPoint (aPoly.GetPoint(nPoint));
+            // When there is at least one edge that is neither vertical nor
+            // horizontal then the entire polygon is not rectilinear (and
+            // oriented along primary axes.)
+            if (aPoint.X() != aNextPoint.X() && aPoint.Y() != aNextPoint.Y())
+                return false;
+
+            aPoint = aNextPoint;
+        }
+        // Compare closing edge.
+        if (aLastPoint.X() != aPoint.X() && aLastPoint.Y() != aPoint.Y())
+            return false;
+    }
+    return true;
+}
+
+
+
+/** This function is similar to the ImplRegion::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 ImplAddMissingBands (
+    ImplRegion* pImplRegion,
+    const long nTop,
+    const long nBottom)
+{
+    // Iterate over already existing bands and add missing bands atop the
+    // first and between two bands.
+    ImplRegionBand* pPreviousBand = NULL;
+    ImplRegionBand* pBand = pImplRegion->ImplGetFirstRegionBand();
+    long nCurrentTop (nTop);
+    while (pBand != NULL && nCurrentTop<nBottom)
+    {
+        if (nCurrentTop < pBand->mnYTop)
+        {
+            // Create new band above the current band.
+            ImplRegionBand* pAboveBand = new ImplRegionBand(
+                nCurrentTop,
+                ::std::min(nBottom,pBand->mnYTop-1));
+            pImplRegion->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 intervall nTop->nBottom extends past the bottom most band.
+    if (nCurrentTop < nBottom && (pBand==NULL || 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.
+        pImplRegion->InsertBand(
+            pPreviousBand,
+            new ImplRegionBand(
+                nCurrentTop,
+                nBottom));
+    }
+}
+
+
+
+/** Convert a rectilinear polygon (that is oriented along the primary axes)
+    to a list of bands.  For this special form of polygon we can use an
+    optimization that prevents the creation of one band per y value.
+    However, it still is possible that some temporary bands are created that
+    later can be optimized away.
+    @param rPolyPolygon
+        A set of zero, one, or more polygons, nested or not, that are
+        converted into a list of bands.
+    @return
+        A new ImplRegion object is returned that contains the bands that
+        represent the given poly-polygon.
+*/
+ImplRegion* ImplRectilinearPolygonToBands (const PolyPolygon& rPolyPoly)
+{
+    OSL_ASSERT(ImplIsPolygonRectilinear (rPolyPoly));
+
+    // Create a new ImplRegion object as container of the bands.
+    ImplRegion* pImplRegion = new ImplRegion();
+    long nLineId = 0L;
+
+    // Iterate over all polygons.
+    const USHORT nPolyCount = rPolyPoly.Count();
+    for (USHORT nPoly = 0; nPoly < nPolyCount; ++nPoly)
+    {
+        const Polygon&  aPoly = rPolyPoly.GetObject(nPoly);
+
+        // Iterate over all edges of the current polygon.
+        const USHORT nSize = aPoly.GetSize();
+        if (nSize < 2)
+            continue;
+        // Avoid fetching every point twice (each point is the start point
+        // of one and the end point of another edge.)
+        Point aStart (aPoly.GetPoint(0));
+        Point aEnd;
+        for (USHORT nPoint = 1; nPoint <= nSize; ++nPoint, aStart=aEnd)
+        {
+            // We take the implicit closing edge into account by mapping
+            // index nSize to 0.
+            aEnd = aPoly.GetPoint(nPoint%nSize);
+            if (aStart.Y() == aEnd.Y())
+            {
+                // Horizontal lines are ignored.
+                continue;
+            }
+
+            // At this point the line has to be vertical.
+            OSL_ASSERT(aStart.X() == aEnd.X());
+
+            // Sort y-coordinates to simplify the algorithm and store the
+            // direction seperately.  The direction is calculated as it is
+            // in other places (but seems to be the wrong way.)
+            const long nTop (::std::min(aStart.Y(), aEnd.Y()));
+            const long nBottom (::std::max(aStart.Y(), aEnd.Y()));
+            const LineType eLineType (aStart.Y() > aEnd.Y() ? LINE_DESCENDING : LINE_ASCENDING);
+
+            // Make sure that the current line is covered by bands.
+            ImplAddMissingBands(pImplRegion, nTop,nBottom);
+
+            // Find top-most band that may contain nTop.
+            ImplRegionBand* pBand = pImplRegion->ImplGetFirstRegionBand();
+            while (pBand!=NULL && pBand->mnYBottom < nTop)
+                pBand = pBand->mpNextBand;
+            ImplRegionBand* pTopBand = pBand;
+            // If necessary split the band at nTop so that nTop is contained
+            // in the lower band.
+            if (   // Prevent the current band from becoming 0 pixel high
+                pBand->mnYTop<nTop
+                   // this allows the lowest pixel of the band to be split off
+                && pBand->mnYBottom>=nTop
+                   // do not split a band that is just one pixel high
+                && pBand->mnYTop<pBand->mnYBottom)
+            {
+                // Split the top band.
+                pTopBand = pBand->SplitBand(nTop);
+            }
+
+            // Advance to band that may contain nBottom.
+            while (pBand!=NULL && pBand->mnYBottom < nBottom)
+                pBand = pBand->mpNextBand;
+            // The lowest band may have to be split at nBottom so that
+            // nBottom itself remains in the upper band.
+            if (   // allow the current band becoming 1 pixel high
+                pBand->mnYTop<=nBottom
+                   // prevent splitting off a band that is 0 pixel high
+                && pBand->mnYBottom>nBottom
+                   // do not split a band that is just one pixel high
+                && pBand->mnYTop<pBand->mnYBottom)
+            {
+                // Split the bottom band.
+                pBand->SplitBand(nBottom+1);
+            }
+
+            // Note that we remember the top band (in pTopBand) but not the
+            // bottom band.  The later can be determined by comparing y
+            // coordinates.
+
+            // Add the x-value as point to all bands in the nTop->nBottom range.
+            for (pBand=pTopBand; pBand!=NULL&&pBand->mnYTop<=nBottom; pBand=pBand->mpNextBand)
+                pBand->InsertPoint(aStart.X(), nLineId++, TRUE, eLineType);
+        }
+    }
+
+    return pImplRegion;
+}
+
+
+
+
+/** Convert a general polygon (one for which ImplIsPolygonRectilinear()
+    returns <FALSE/>) to bands.
+*/
+ImplRegion* ImplGeneralPolygonToBands (
+    const PolyPolygon& rPolyPoly,
+    const Rectangle& rPolygonBoundingBox)
+{
+    long nLineID = 0L;
+
+    // initialisation and creation of Bands
+    ImplRegion* pImplRegion = new ImplRegion();
+    pImplRegion->CreateBandRange( rPolygonBoundingBox.Top(), rPolygonBoundingBox.Bottom() );
+
+    // insert polygons
+    const USHORT nPolyCount = rPolyPoly.Count();
+    for ( USHORT nPoly = 0; nPoly < nPolyCount; nPoly++ )
+    {
+        // get reference to current polygon
+        const Polygon&  aPoly = rPolyPoly.GetObject( nPoly );
+        const USHORT    nSize = aPoly.GetSize();
+
+        // not enough points ( <= 2 )? -> nothing to do!
+        if ( nSize <= 2 )
+            continue;
+
+        // band the polygon
+        for ( USHORT nPoint = 1; nPoint < nSize; nPoint++ )
+            pImplRegion->InsertLine( aPoly.GetPoint(nPoint-1), aPoly.GetPoint(nPoint), nLineID++ );
+
+        // close polygon with line from first point to last point, if neccesary
+        const Point rLastPoint = aPoly.GetPoint(nSize-1);
+        const Point rFirstPoint = aPoly.GetPoint(0);
+        if ( rLastPoint != rFirstPoint )
+            pImplRegion->InsertLine( rLastPoint, rFirstPoint, nLineID++ );
+    }
+
+    return pImplRegion;
+}
+
+
+} // end of anonymous namespace
+
+
 // -----------------------------------------------------------------------
 
 #ifdef DBG_UTIL
@@ -140,6 +381,35 @@ const char* ImplDbgTestRegion( const void* pObj )
 
     return NULL;
 }
+
+void TraceBands (const ImplRegionBand* pFirstBand)
+{
+    int nBandIndex  (0);
+    const ImplRegionBand* pBand = pFirstBand;
+    while (pBand != NULL)
+    {
+        OSL_TRACE("            band %d  %d->%d : ", nBandIndex++,
+            pBand->mnYTop, pBand->mnYBottom);
+
+        ImplRegionBandPoint* pPoint = pBand->mpFirstBandPoint;
+        while (pPoint != NULL)
+        {
+            OSL_TRACE(" %d ", pPoint->mnX);
+            pPoint = pPoint->mpNextBandPoint;
+        }
+        OSL_TRACE("  |  ");
+
+        ImplRegionBandSep* pSep = pBand->mpFirstSep;
+        while (pSep != NULL)
+        {
+            OSL_TRACE(" %d->%d ", pSep->mnXLeft, pSep->mnXRight);
+            pSep = pSep->mpNextSep;
+        }
+        OSL_TRACE("\n");
+
+        pBand = pBand->mpNextBand;
+    }
+}
 #endif
 
 // =======================================================================
@@ -577,6 +847,29 @@ BOOL ImplRegion::InsertSingleBand( ImplRegionBand* pBand,
 
 // ------------------------------------------------------------------------
 
+void ImplRegion::InsertBand (ImplRegionBand* pPreviousBand, ImplRegionBand* pBandToInsert)
+{
+    OSL_ASSERT(pBandToInsert!=NULL);
+
+    if (pPreviousBand == NULL)
+    {
+        // Insert band before all others.
+        if (mpFirstBand != NULL)
+            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 ImplRegion::Union( long nLeft, long nTop, long nRight, long nBottom )
 {
     DBG_ASSERT( nLeft <= nRight, "ImplRegion::Union() - nLeft > nRight" );
@@ -918,8 +1211,12 @@ void Region::ImplCreatePolyPolyRegion( const PolyPolygon& rPolyPoly )
         if ( !aRect.IsEmpty() )
         {
             // width OR height == 1 ? => Rectangular region
-            if ( (aRect.GetWidth() == 1) || (aRect.GetHeight() == 1) )
+            if ( (aRect.GetWidth() == 1)
+                || (aRect.GetHeight() == 1)
+                || rPolyPoly.IsRect() )
+            {
                 ImplCreateRectRegion( aRect );
+            }
             else
                 mpImplRegion = new ImplRegion( rPolyPoly );
         }
@@ -944,43 +1241,24 @@ void Region::ImplPolyPolyRegionToBandRegionFunc()
     else
         delete mpImplRegion;
 
-    const USHORT nPolyCount = aPolyPoly.Count();
-    if ( nPolyCount )
+    if ( aPolyPoly.Count() )
     {
         // polypolygon empty? -> empty region
         const Rectangle aRect( aPolyPoly.GetBoundRect() );
 
         if ( !aRect.IsEmpty() )
         {
-            long nLineID = 0L;
-
-            // initialisation and creation of Bands
-            mpImplRegion = new ImplRegion();
-            mpImplRegion->CreateBandRange( aRect.Top(), aRect.Bottom() );
-
-            // insert polygons
-            for ( USHORT nPoly = 0; nPoly < nPolyCount; nPoly++ )
+            if (ImplIsPolygonRectilinear(aPolyPoly))
+            {
+                // For rectilinear polygons there is an optimized band conversion.
+                mpImplRegion = ImplRectilinearPolygonToBands(aPolyPoly);
+            }
+            else
             {
-                // get reference to current polygon
-                const Polygon&  aPoly = aPolyPoly.GetObject( nPoly );
-                const USHORT    nSize = aPoly.GetSize();
-
-                // not enough points ( <= 2 )? -> nothing to do!
-                if ( nSize <= 2 )
-                    continue;
-
-                // band the polygon
-                for ( USHORT nPoint = 1; nPoint < nSize; nPoint++ )
-                    mpImplRegion->InsertLine( aPoly.GetPoint(nPoint-1), aPoly.GetPoint(nPoint), nLineID++ );
-
-                // close polygon with line from first point to last point, if neccesary
-                const Point rLastPoint = aPoly.GetPoint(nSize-1);
-                const Point rFirstPoint = aPoly.GetPoint(0);
-                if ( rLastPoint != rFirstPoint )
-                    mpImplRegion->InsertLine( rLastPoint, rFirstPoint, nLineID++ );
+                mpImplRegion = ImplGeneralPolygonToBands(aPolyPoly, aRect);
             }
 
-            // process bands with lines
+            // Convert points into seps.
             ImplRegionBand* pRegionBand = mpImplRegion->mpFirstBand;
             while ( pRegionBand )
             {
@@ -989,7 +1267,8 @@ void Region::ImplPolyPolyRegionToBandRegionFunc()
                 pRegionBand = pRegionBand->mpNextBand;
             }
 
-            // cleanup
+            // Optimize list of bands.  Adjacent bands with identical lists
+            // of seps are joined.
             if ( !mpImplRegion->OptimizeBandList() )
             {
                 delete mpImplRegion;