diff options
Diffstat (limited to '')
| -rw-r--r-- | editeng/source/misc/txtrange.cxx | 666 |
1 files changed, 666 insertions, 0 deletions
diff --git a/editeng/source/misc/txtrange.cxx b/editeng/source/misc/txtrange.cxx new file mode 100644 index 000000000..6374747be --- /dev/null +++ b/editeng/source/misc/txtrange.cxx @@ -0,0 +1,666 @@ +/* -*- 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 <editeng/txtrange.hxx> +#include <math.h> +#include <tools/poly.hxx> +#include <tools/debug.hxx> +#include <basegfx/polygon/b2dpolygon.hxx> +#include <basegfx/polygon/b2dpolypolygon.hxx> + +#include <vector> + +TextRanger::TextRanger( const basegfx::B2DPolyPolygon& rPolyPolygon, + const basegfx::B2DPolyPolygon* pLinePolyPolygon, + sal_uInt16 nCacheSz, sal_uInt16 nLft, sal_uInt16 nRght, + bool bSimpl, bool bInnr, bool bVert ) : + maPolyPolygon( rPolyPolygon.count() ), + nCacheSize( nCacheSz ), + nRight( nRght ), + nLeft( nLft ), + nUpper( 0 ), + nLower( 0 ), + nPointCount( 0 ), + bSimple( bSimpl ), + bInner( bInnr ), + bVertical( bVert ) +{ + sal_uInt32 nCount(rPolyPolygon.count()); + + for(sal_uInt32 i(0); i < nCount; i++) + { + const basegfx::B2DPolygon aCandidate(rPolyPolygon.getB2DPolygon(i).getDefaultAdaptiveSubdivision()); + nPointCount += aCandidate.count(); + maPolyPolygon.Insert( tools::Polygon(aCandidate), static_cast<sal_uInt16>(i) ); + } + + if( pLinePolyPolygon ) + { + nCount = pLinePolyPolygon->count(); + mpLinePolyPolygon = tools::PolyPolygon(nCount); + + for(sal_uInt32 i(0); i < nCount; i++) + { + const basegfx::B2DPolygon aCandidate(pLinePolyPolygon->getB2DPolygon(i).getDefaultAdaptiveSubdivision()); + nPointCount += aCandidate.count(); + mpLinePolyPolygon->Insert( tools::Polygon(aCandidate), static_cast<sal_uInt16>(i) ); + } + } + else + mpLinePolyPolygon.reset(); +} + + +TextRanger::~TextRanger() +{ + mRangeCache.clear(); +} + +/* TextRanger::SetVertical(..) + If there's is a change in the writing direction, + the cache has to be cleared. +*/ +void TextRanger::SetVertical( bool bNew ) +{ + if( IsVertical() != bNew ) + { + bVertical = bNew; + mRangeCache.clear(); + } +} + +namespace { + +//! SvxBoundArgs is used to perform temporary calculations on a range array. +//! Temporary instances are created in TextRanger::GetTextRanges() +class SvxBoundArgs +{ + std::vector<bool> aBoolArr; + std::deque<tools::Long>* pLongArr; + TextRanger *pTextRanger; + tools::Long nMin; + tools::Long nMax; + tools::Long nTop; + tools::Long nBottom; + tools::Long nUpDiff; + tools::Long nLowDiff; + tools::Long nUpper; + tools::Long nLower; + tools::Long nStart; + tools::Long nEnd; + sal_uInt16 nCut; + sal_uInt16 nLast; + sal_uInt16 nNext; + sal_uInt8 nAct; + sal_uInt8 nFirst; + bool bClosed : 1; + bool bInner : 1; + bool bMultiple : 1; + bool bConcat : 1; + bool bRotate : 1; + void NoteRange( bool bToggle ); + tools::Long Cut( tools::Long nY, const Point& rPt1, const Point& rPt2 ); + void Add(); + void NoteFarPoint_( tools::Long nPx, tools::Long nPyDiff, tools::Long nDiff ); + void NoteFarPoint( tools::Long nPx, tools::Long nPyDiff, tools::Long nDiff ) + { if( nDiff ) NoteFarPoint_( nPx, nPyDiff, nDiff ); } + tools::Long CalcMax( const Point& rPt1, const Point& rPt2, tools::Long nRange, tools::Long nFar ); + void CheckCut( const Point& rLst, const Point& rNxt ); + tools::Long A( const Point& rP ) const { return bRotate ? rP.Y() : rP.X(); } + tools::Long B( const Point& rP ) const { return bRotate ? rP.X() : rP.Y(); } +public: + SvxBoundArgs( TextRanger* pRanger, std::deque<tools::Long>* pLong, const Range& rRange ); + void NotePoint( const tools::Long nA ) { NoteMargin( nA - nStart, nA + nEnd ); } + void NoteMargin( const tools::Long nL, const tools::Long nR ) + { if( nMin > nL ) nMin = nL; if( nMax < nR ) nMax = nR; } + sal_uInt16 Area( const Point& rPt ); + void NoteUpLow( tools::Long nA, const sal_uInt8 nArea ); + void Calc( const tools::PolyPolygon& rPoly ); + void Concat( const tools::PolyPolygon* pPoly ); + // inlines + void NoteLast() { if( bMultiple ) NoteRange( nAct == nFirst ); } + void SetConcat( const bool bNew ){ bConcat = bNew; } + bool IsConcat() const { return bConcat; } +}; + +} + +SvxBoundArgs::SvxBoundArgs( TextRanger* pRanger, std::deque<tools::Long>* pLong, + const Range& rRange ) + : pLongArr(pLong) + , pTextRanger(pRanger) + , nMin(0) + , nMax(0) + , nTop(rRange.Min()) + , nBottom(rRange.Max()) + , nCut(0) + , nLast(0) + , nNext(0) + , nAct(0) + , nFirst(0) + , bClosed(false) + , bInner(pRanger->IsInner()) + , bMultiple(bInner || !pRanger->IsSimple()) + , bConcat(false) + , bRotate(pRanger->IsVertical()) +{ + if( bRotate ) + { + nStart = pRanger->GetUpper(); + nEnd = pRanger->GetLower(); + nLowDiff = pRanger->GetLeft(); + nUpDiff = pRanger->GetRight(); + } + else + { + nStart = pRanger->GetLeft(); + nEnd = pRanger->GetRight(); + nLowDiff = pRanger->GetUpper(); + nUpDiff = pRanger->GetLower(); + } + nUpper = nTop - nUpDiff; + nLower = nBottom + nLowDiff; + pLongArr->clear(); +} + +tools::Long SvxBoundArgs::CalcMax( const Point& rPt1, const Point& rPt2, + tools::Long nRange, tools::Long nFarRange ) +{ + double nDa = Cut( nRange, rPt1, rPt2 ) - Cut( nFarRange, rPt1, rPt2 ); + double nB; + if( nDa < 0 ) + { + nDa = -nDa; + nB = nEnd; + } + else + nB = nStart; + nB *= nB; + nB += nDa * nDa; + nB = sqrt( nB ); + if (nB == 0) // avoid div / 0 + return 0; + nB = nRange + nDa * ( nFarRange - nRange ) / nB; + + bool bNote; + if( nB < B(rPt2) ) + bNote = nB > B(rPt1); + else + bNote = nB < B(rPt1); + if( bNote ) + return( tools::Long( nB ) ); + return 0; +} + +void SvxBoundArgs::CheckCut( const Point& rLst, const Point& rNxt ) +{ + if( nCut & 1 ) + NotePoint( Cut( nBottom, rLst, rNxt ) ); + if( nCut & 2 ) + NotePoint( Cut( nTop, rLst, rNxt ) ); + if( rLst.X() == rNxt.X() || rLst.Y() == rNxt.Y() ) + return; + + tools::Long nYps; + if( nLowDiff && ( ( nCut & 1 ) || nLast == 1 || nNext == 1 ) ) + { + nYps = CalcMax( rLst, rNxt, nBottom, nLower ); + if( nYps ) + NoteFarPoint_( Cut( nYps, rLst, rNxt ), nLower-nYps, nLowDiff ); + } + if( nUpDiff && ( ( nCut & 2 ) || nLast == 2 || nNext == 2 ) ) + { + nYps = CalcMax( rLst, rNxt, nTop, nUpper ); + if( nYps ) + NoteFarPoint_( Cut( nYps, rLst, rNxt ), nYps-nUpper, nUpDiff ); + } +} + +void SvxBoundArgs::NoteFarPoint_( tools::Long nPa, tools::Long nPbDiff, tools::Long nDiff ) +{ + tools::Long nTmpA; + double nQuot = 2 * nDiff - nPbDiff; + nQuot *= nPbDiff; + nQuot = sqrt( nQuot ); + nQuot /= nDiff; + nTmpA = nPa - tools::Long( nStart * nQuot ); + nPbDiff = nPa + tools::Long( nEnd * nQuot ); + NoteMargin( nTmpA, nPbDiff ); +} + +void SvxBoundArgs::NoteRange( bool bToggle ) +{ + DBG_ASSERT( nMax >= nMin || bInner, "NoteRange: Min > Max?"); + if( nMax < nMin ) + return; + if( !bClosed ) + bToggle = false; + sal_uInt16 nIdx = 0; + sal_uInt16 nCount = pLongArr->size(); + DBG_ASSERT( nCount == 2 * aBoolArr.size(), "NoteRange: Incompatible Sizes" ); + while( nIdx < nCount && (*pLongArr)[ nIdx ] < nMin ) + ++nIdx; + bool bOdd = (nIdx % 2) != 0; + // No overlap with existing intervals? + if( nIdx == nCount || ( !bOdd && nMax < (*pLongArr)[ nIdx ] ) ) + { // Then a new one is inserted ... + pLongArr->insert( pLongArr->begin() + nIdx, nMin ); + pLongArr->insert( pLongArr->begin() + nIdx + 1, nMax ); + aBoolArr.insert( aBoolArr.begin() + (nIdx/2), bToggle ); + } + else + { // expand an existing interval ... + sal_uInt16 nMaxIdx = nIdx; + // If we end up on a left interval boundary, it must be reduced to nMin. + if( bOdd ) + --nIdx; + else + (*pLongArr)[ nIdx ] = nMin; + while( nMaxIdx < nCount && (*pLongArr)[ nMaxIdx ] < nMax ) + ++nMaxIdx; + DBG_ASSERT( nMaxIdx > nIdx || nMin == nMax, "NoteRange: Funny Situation." ); + if( nMaxIdx ) + --nMaxIdx; + if( nMaxIdx < nIdx ) + nMaxIdx = nIdx; + // If we end up on a right interval boundary, it must be raised to nMax. + if( nMaxIdx % 2 ) + (*pLongArr)[ nMaxIdx-- ] = nMax; + // Possible merge of intervals. + sal_uInt16 nDiff = nMaxIdx - nIdx; + nMaxIdx = nIdx / 2; // From here on is nMaxIdx the Index in BoolArray. + if( nDiff ) + { + pLongArr->erase( pLongArr->begin() + nIdx + 1, pLongArr->begin() + nIdx + 1 + nDiff ); + nDiff /= 2; + sal_uInt16 nStop = nMaxIdx + nDiff; + for( sal_uInt16 i = nMaxIdx; i < nStop; ++i ) + bToggle ^= aBoolArr[ i ]; + aBoolArr.erase( aBoolArr.begin() + nMaxIdx, aBoolArr.begin() + (nMaxIdx + nDiff) ); + } + DBG_ASSERT( nMaxIdx < aBoolArr.size(), "NoteRange: Too much deleted" ); + aBoolArr[ nMaxIdx ] = aBoolArr[ nMaxIdx ] != bToggle; + } +} + +void SvxBoundArgs::Calc( const tools::PolyPolygon& rPoly ) +{ + sal_uInt16 nCount; + nAct = 0; + for( sal_uInt16 i = 0; i < rPoly.Count(); ++i ) + { + const tools::Polygon& rPol = rPoly[ i ]; + nCount = rPol.GetSize(); + if( nCount ) + { + const Point& rNull = rPol[ 0 ]; + bClosed = IsConcat() || ( rNull == rPol[ nCount - 1 ] ); + nLast = Area( rNull ); + if( nLast & 12 ) + { + nFirst = 3; + if( bMultiple ) + nAct = 0; + } + else + { + // The first point of the polygon is within the line. + if( nLast ) + { + if( bMultiple || !nAct ) + { + nMin = USHRT_MAX; + nMax = 0; + } + if( nLast & 1 ) + NoteFarPoint( A(rNull), nLower - B(rNull), nLowDiff ); + else + NoteFarPoint( A(rNull), B(rNull) - nUpper, nUpDiff ); + } + else + { + if( bMultiple || !nAct ) + { + nMin = A(rNull); + nMax = nMin + nEnd; + nMin -= nStart; + } + else + NotePoint( A(rNull) ); + } + nFirst = 0; // leaving the line in which direction? + nAct = 3; // we are within the line at the moment. + } + if( nCount > 1 ) + { + sal_uInt16 nIdx = 1; + while( true ) + { + const Point& rLast = rPol[ nIdx - 1 ]; + if( nIdx == nCount ) + nIdx = 0; + const Point& rNext = rPol[ nIdx ]; + nNext = Area( rNext ); + nCut = nNext ^ nLast; + sal_uInt16 nOldAct = nAct; + if( nAct ) + CheckCut( rLast, rNext ); + if( nCut & 4 ) + { + NoteUpLow( Cut( nLower, rLast, rNext ), 2 ); + if( nAct && nAct != nOldAct ) + { + nOldAct = nAct; + CheckCut( rLast, rNext ); + } + } + if( nCut & 8 ) + { + NoteUpLow( Cut( nUpper, rLast, rNext ), 1 ); + if( nAct && nAct != nOldAct ) + CheckCut( rLast, rNext ); + } + if( !nIdx ) + { + if( !( nNext & 12 ) ) + NoteLast(); + break; + } + if( !( nNext & 12 ) ) + { + if( !nNext ) + NotePoint( A(rNext) ); + else if( nNext & 1 ) + NoteFarPoint( A(rNext), nLower-B(rNext), nLowDiff ); + else + NoteFarPoint( A(rNext), B(rNext)-nUpper, nUpDiff ); + } + nLast = nNext; + if( ++nIdx == nCount && !bClosed ) + { + if( !( nNext & 12 ) ) + NoteLast(); + break; + } + } + } + if( bMultiple && IsConcat() ) + { + Add(); + nAct = 0; + } + } + } + if( !bMultiple ) + { + DBG_ASSERT( pLongArr->empty(), "I said: Simple!" ); + if( nAct ) + { + if( bInner ) + { + tools::Long nTmpMin = nMin + 2 * nStart; + tools::Long nTmpMax = nMax - 2 * nEnd; + if( nTmpMin <= nTmpMax ) + { + pLongArr->push_front(nTmpMax); + pLongArr->push_front(nTmpMin); + } + } + else + { + pLongArr->push_front(nMax); + pLongArr->push_front(nMin); + } + } + } + else if( !IsConcat() ) + Add(); +} + +void SvxBoundArgs::Add() +{ + size_t nCount = aBoolArr.size(); + if( nCount && ( !bInner || !pTextRanger->IsSimple() ) ) + { + bool bDelete = aBoolArr.front(); + if( bInner ) + bDelete = !bDelete; + sal_uInt16 nLongIdx = 1; + for( size_t nBoolIdx = 1; nBoolIdx < nCount; ++nBoolIdx ) + { + if( bDelete ) + { + sal_uInt16 next = 2; + while( nBoolIdx < nCount && !aBoolArr[ nBoolIdx++ ] && + (!bInner || nBoolIdx < nCount ) ) + next += 2; + pLongArr->erase( pLongArr->begin() + nLongIdx, pLongArr->begin() + nLongIdx + next ); + next /= 2; + nBoolIdx = nBoolIdx - next; + nCount = nCount - next; + aBoolArr.erase( aBoolArr.begin() + nBoolIdx, aBoolArr.begin() + (nBoolIdx + next) ); + if( nBoolIdx ) + aBoolArr[ nBoolIdx - 1 ] = false; +#if OSL_DEBUG_LEVEL > 1 + else + ++next; +#endif + } + bDelete = nBoolIdx < nCount && aBoolArr[ nBoolIdx ]; + nLongIdx += 2; + DBG_ASSERT( nLongIdx == 2*nBoolIdx+1, "BoundArgs: Array-Idx Confusion" ); + DBG_ASSERT( aBoolArr.size()*2 == pLongArr->size(), + "BoundArgs: Array-Count: Confusion" ); + } + } + if( pLongArr->empty() ) + return; + + if( !bInner ) + return; + + pLongArr->pop_front(); + pLongArr->pop_back(); + + // Here the line is held inside a large rectangle for "simple" + // contour wrap. Currently (April 1999) the EditEngine evaluates + // only the first rectangle. If it one day is able to output a line + // in several parts, it may be advisable to delete the following lines. + if( pTextRanger->IsSimple() && pLongArr->size() > 2 ) + pLongArr->erase( pLongArr->begin() + 1, pLongArr->end() - 1 ); +} + +void SvxBoundArgs::Concat( const tools::PolyPolygon* pPoly ) +{ + SetConcat( true ); + DBG_ASSERT( pPoly, "Nothing to do?" ); + std::deque<tools::Long>* pOld = pLongArr; + pLongArr = new std::deque<tools::Long>; + aBoolArr.clear(); + bInner = false; + Calc( *pPoly ); // Note that this updates pLongArr, which is why we swapped it out earlier. + std::deque<tools::Long>::size_type nCount = pLongArr->size(); + std::deque<tools::Long>::size_type nIdx = 0; + std::deque<tools::Long>::size_type i = 0; + bool bSubtract = pTextRanger->IsInner(); + while( i < nCount ) + { + std::deque<tools::Long>::size_type nOldCount = pOld->size(); + if( nIdx == nOldCount ) + { // Reached the end of the old Array... + if( !bSubtract ) + pOld->insert( pOld->begin() + nIdx, pLongArr->begin() + i, pLongArr->end() ); + break; + } + tools::Long nLeft = (*pLongArr)[ i++ ]; + tools::Long nRight = (*pLongArr)[ i++ ]; + std::deque<tools::Long>::size_type nLeftPos = nIdx + 1; + while( nLeftPos < nOldCount && nLeft > (*pOld)[ nLeftPos ] ) + nLeftPos += 2; + if( nLeftPos >= nOldCount ) + { // The current interval belongs to the end of the old array ... + if( !bSubtract ) + pOld->insert( pOld->begin() + nOldCount, pLongArr->begin() + i - 2, pLongArr->end() ); + break; + } + std::deque<tools::Long>::size_type nRightPos = nLeftPos - 1; + while( nRightPos < nOldCount && nRight >= (*pOld)[ nRightPos ] ) + nRightPos += 2; + if( nRightPos < nLeftPos ) + { // The current interval belongs between two old intervals + if( !bSubtract ) + pOld->insert( pOld->begin() + nRightPos, pLongArr->begin() + i - 2, pLongArr->begin() + i ); + } + else if( bSubtract ) // Subtract, if necessary separate + { + const tools::Long nOld = (*pOld)[nLeftPos - 1]; + if (nLeft > nOld) + { // Now we split the left part... + if( nLeft - 1 > nOld ) + { + pOld->insert( pOld->begin() + nLeftPos - 1, nOld ); + pOld->insert( pOld->begin() + nLeftPos, nLeft - 1 ); + nLeftPos += 2; + nRightPos += 2; + } + } + if( nRightPos - nLeftPos > 1 ) + pOld->erase( pOld->begin() + nLeftPos, pOld->begin() + nRightPos - 1 ); + if (++nRight >= (*pOld)[nLeftPos]) + pOld->erase( pOld->begin() + nLeftPos - 1, pOld->begin() + nLeftPos + 1 ); + else + (*pOld)[ nLeftPos - 1 ] = nRight; + } + else // Merge + { + if( nLeft < (*pOld)[ nLeftPos - 1 ] ) + (*pOld)[ nLeftPos - 1 ] = nLeft; + if( nRight > (*pOld)[ nRightPos - 1 ] ) + (*pOld)[ nRightPos - 1 ] = nRight; + if( nRightPos - nLeftPos > 1 ) + pOld->erase( pOld->begin() + nLeftPos, pOld->begin() + nRightPos - 1 ); + + } + nIdx = nLeftPos - 1; + } + delete pLongArr; +} + +/************************************************************************* + * SvxBoundArgs::Area returns the area in which the point is located. + * 0 = within the line + * 1 = below, but within the upper edge + * 2 = above, but within the lower edge + * 5 = below the upper edge + *10 = above the lower edge + *************************************************************************/ + +sal_uInt16 SvxBoundArgs::Area( const Point& rPt ) +{ + tools::Long nB = B( rPt ); + if( nB >= nBottom ) + { + if( nB >= nLower ) + return 5; + return 1; + } + if( nB <= nTop ) + { + if( nB <= nUpper ) + return 10; + return 2; + } + return 0; +} + +/************************************************************************* + * lcl_Cut calculates the X-Coordinate of the distance (Pt1-Pt2) at the + * Y-Coordinate nY. + * It is assumed that the one of the points are located above and the other + * one below the Y-Coordinate. + *************************************************************************/ + +tools::Long SvxBoundArgs::Cut( tools::Long nB, const Point& rPt1, const Point& rPt2 ) +{ + if( pTextRanger->IsVertical() ) + { + double nQuot = nB - rPt1.X(); + nQuot /= ( rPt2.X() - rPt1.X() ); + nQuot *= ( rPt2.Y() - rPt1.Y() ); + return tools::Long( rPt1.Y() + nQuot ); + } + double nQuot = nB - rPt1.Y(); + nQuot /= ( rPt2.Y() - rPt1.Y() ); + nQuot *= ( rPt2.X() - rPt1.X() ); + return tools::Long( rPt1.X() + nQuot ); +} + +void SvxBoundArgs::NoteUpLow( tools::Long nA, const sal_uInt8 nArea ) +{ + if( nAct ) + { + NoteMargin( nA, nA ); + if( bMultiple ) + { + NoteRange( nArea != nAct ); + nAct = 0; + } + if( !nFirst ) + nFirst = nArea; + } + else + { + nAct = nArea; + nMin = nA; + nMax = nA; + } +} + +std::deque<tools::Long>* TextRanger::GetTextRanges( const Range& rRange ) +{ + DBG_ASSERT( rRange.Min() || rRange.Max(), "Zero-Range not allowed, Bye Bye" ); + //Can we find the result we need in the cache? + for (auto & elem : mRangeCache) + { + if (elem.range == rRange) + return &(elem.results); + } + //Calculate a new result + RangeCacheItem rngCache(rRange); + SvxBoundArgs aArg( this, &(rngCache.results), rRange ); + aArg.Calc( maPolyPolygon ); + if( mpLinePolyPolygon ) + aArg.Concat( &*mpLinePolyPolygon ); + //Add new result to the cache + mRangeCache.push_back(std::move(rngCache)); + if (mRangeCache.size() > nCacheSize) + mRangeCache.pop_front(); + return &(mRangeCache.back().results); +} + +const tools::Rectangle& TextRanger::GetBoundRect_() const +{ + DBG_ASSERT( !mxBound, "Don't call twice." ); + mxBound = maPolyPolygon.GetBoundRect(); + return *mxBound; +} + + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |