/* -*- 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 #include #include #include #include #include #include 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(i) ); } if( pLinePolyPolygon ) { nCount = pLinePolyPolygon->count(); mpLinePolyPolygon.reset( new tools::PolyPolygon() ); 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(i) ); } } else mpLinePolyPolygon = nullptr; } 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 aBoolArr; std::deque* 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* 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* 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 = nRange + nDa * ( nFarRange - nRange ) / sqrt( 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* pOld = pLongArr; pLongArr = new std::deque; aBoolArr.clear(); bInner = false; Calc( *pPoly ); // Note that this updates pLongArr, which is why we swapped it out earlier. std::deque::size_type nCount = pLongArr->size(); std::deque::size_type nIdx = 0; std::deque::size_type i = 0; bool bSubtract = pTextRanger->IsInner(); while( i < nCount ) { std::deque::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::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::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* 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.get() ); //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: */