22 #include <rtl/ustrbuf.hxx>
24 #include <osl/diagnose.h>
25 #include <rtl/character.hxx>
37 #include <section.hxx>
44 #include <com/sun/star/document/XDocumentPropertiesSupplier.hpp>
45 #include <com/sun/star/document/XDocumentProperties.hpp>
46 #include <com/sun/star/frame/XModel.hpp>
50 #include <type_traits>
59 class SwCompareLine final
63 explicit SwCompareLine(
const SwNode& rNd ) : m_pNode( &rNd ) {}
64 SwCompareLine() : m_pNode( nullptr ) {}
67 bool Compare(
const SwCompareLine& rLine )
const;
70 static bool CompareNode(
const SwNode& rDstNd,
const SwNode& rSrcNd );
71 static bool CompareTextNd(
const SwTextNode& rDstNd,
74 bool ChangesInLine(
const SwCompareLine& rLine,
75 std::unique_ptr<SwPaM>& rpInsRing, std::unique_ptr<SwPaM>& rpDelRing )
const;
82 OUString GetText()
const;
91 std::unique_ptr<size_t[]> m_pIndex;
92 std::unique_ptr<bool[]> m_pChangedFlag;
94 std::unique_ptr<SwPaM> m_pInsertRing, m_pDelRing;
99 vector<SwCompareLine> m_aLines;
103 void CheckRanges( CompareData& );
105 virtual const SwNode& GetEndOfContent() = 0;
108 CompareData(
SwDoc& rD,
bool bRecordDiff)
110 , m_bRecordDiff(bRecordDiff)
113 virtual ~CompareData();
116 bool HasDiffs(
const CompareData& rData )
const;
119 void CompareLines( CompareData& rData );
123 sal_uLong ShowDiffs(
const CompareData& rData );
128 void CheckForChangesInLine(
const CompareData& rData,
133 void SetIndex(
size_t nLine,
size_t nIndex );
134 size_t GetIndex(
size_t nLine )
const
135 {
return nLine < m_aLines.size() ? m_pIndex[ nLine ] : 0; }
138 void SetChanged(
size_t nLine,
bool bFlag =
true );
139 bool GetChanged(
size_t nLine )
const
141 return (m_pChangedFlag && nLine < m_aLines.size())
142 && m_pChangedFlag[ nLine ];
145 size_t GetLineCount()
const {
return m_aLines.size(); }
146 const SwCompareLine& GetLine(
size_t nLine )
const
147 {
return m_aLines[ nLine ]; }
149 { m_aLines.push_back( aLine ); }
151 void SetRedlinesToDoc(
bool bUseDocInfo );
154 class CompareMainText :
public CompareData
157 CompareMainText(
SwDoc &rD,
bool bRecordDiff)
158 : CompareData(rD, bRecordDiff)
162 virtual const SwNode& GetEndOfContent()
override
168 class CompareFrameFormatText :
public CompareData
173 : CompareData(rD, true)
178 virtual const SwNode& GetEndOfContent()
override
192 : nNext( 0 ), nHash( 0 ) {}
195 std::unique_ptr<sal_uLong[]> m_pHashArr;
196 std::unique_ptr<HashData[]> m_pDataArr;
202 void CalcHashValue( CompareData& rData );
204 sal_uLong GetCount()
const {
return m_nCount; }
212 std::unique_ptr<sal_uLong[]> m_pIndex;
213 std::unique_ptr<sal_uLong[]> m_pLineNum;
217 MovedData( CompareData& rData,
const char* pDiscard );
221 sal_uLong GetCount()
const {
return m_nCount; }
226 class CompareSequence
228 CompareData &m_rData1, &m_rData2;
229 const MovedData &m_rMoved1, &m_rMoved2;
230 std::unique_ptr<tools::Long[]> m_pMemory;
237 CompareSequence( CompareData& rD1, CompareData& rD2,
238 const MovedData& rMD1,
const MovedData& rMD2 );
241 static void CountDifference(
const CompareData& rData,
sal_uLong* pCounts );
242 static void SetDiscard(
const CompareData& rData,
243 char* pDiscard,
const sal_uLong* pCounts );
244 static void CheckDiscard(
sal_uLong nLen,
char* pDiscard );
245 static void ShiftBoundaries( CompareData& rData1, CompareData& rData2 );
248 Compare(
sal_uLong nDiff, CompareData& rData1, CompareData& rData2 );
251 class ArrayComparator
254 virtual bool Compare(
int nIdx1,
int nIdx2 )
const = 0;
255 virtual int GetLen1()
const = 0;
256 virtual int GetLen2()
const = 0;
257 virtual ~ArrayComparator() {}
262 class LineArrayComparator :
public ArrayComparator
265 int m_nLen1, m_nLen2;
266 const CompareData &m_rData1, &m_rData2;
267 int m_nFirst1, m_nFirst2;
270 LineArrayComparator(
const CompareData &rD1,
const CompareData &rD2,
271 int nStt1,
int nEnd1,
int nStt2,
int nEnd2 );
273 virtual bool Compare(
int nIdx1,
int nIdx2 )
const override;
274 virtual int GetLen1()
const override {
return m_nLen1; }
275 virtual int GetLen2()
const override {
return m_nLen2; }
278 class WordArrayComparator :
public ArrayComparator
281 const SwTextNode *m_pTextNode1, *m_pTextNode2;
282 std::unique_ptr<int[]> m_pPos1, m_pPos2;
283 int m_nCount1, m_nCount2;
285 static void CalcPositions(
int *pPos,
const SwTextNode *pTextNd,
int &nCnt );
290 virtual bool Compare(
int nIdx1,
int nIdx2 )
const override;
291 virtual int GetLen1()
const override {
return m_nCount1; }
292 virtual int GetLen2()
const override {
return m_nCount2; }
293 int GetCharSequence(
const int *pWordLcs1,
const int *pWordLcs2,
294 int *pSubseq1,
int *pSubseq2,
int nLcsLen );
297 class CharArrayComparator :
public ArrayComparator
300 const SwTextNode *m_pTextNode1, *m_pTextNode2;
304 : m_pTextNode1( pNode1 ), m_pTextNode2( pNode2 )
308 virtual bool Compare(
int nIdx1,
int nIdx2 )
const override;
309 virtual int GetLen1()
const override {
return m_pTextNode1->
GetText().getLength(); }
310 virtual int GetLen2()
const override {
return m_pTextNode2->
GetText().getLength(); }
314 struct CmpOptionsContainer
330 std::unique_ptr<int[]>
m_pData;
333 ArrayComparator &m_rComparator;
335 CommonSubseq( ArrayComparator &rComparator,
int nMaxSize )
336 : m_rComparator( rComparator )
338 m_pData.reset(
new int[ nMaxSize ] );
341 int FindLCS(
int *pLcs1,
int *pLcs2,
int nStt1,
342 int nEnd1,
int nStt2,
int nEnd2 );
345 static int IgnoreIsolatedPieces(
int *pLcs1,
int *pLcs2,
int nLen1,
int nLen2,
346 int nLcsLen,
int nPieceLen );
350 class LgstCommonSubseq:
public CommonSubseq
353 static const int CUTOFF = 1<<20;
355 std::unique_ptr<int[]> m_pL1, m_pL2;
356 std::unique_ptr<int[]> m_pBuff1, m_pBuff2;
358 void FindL(
int *pL,
int nStt1,
int nEnd1,
int nStt2,
int nEnd2 );
359 int HirschbergLCS(
int *pLcs1,
int *pLcs2,
int nStt1,
int nEnd1,
360 int nStt2,
int nEnd2 );
363 explicit LgstCommonSubseq( ArrayComparator &rComparator );
365 int Find(
int *pSubseq1,
int *pSubseq2 );
369 class FastCommonSubseq:
private CommonSubseq
372 static const int CUTOFF = 2056;
374 int FindFastCS(
int *pSeq1,
int *pSeq2,
int nStt1,
int nEnd1,
375 int nStt2,
int nEnd2 );
378 explicit FastCommonSubseq( ArrayComparator &rComparator )
379 : CommonSubseq( rComparator, CUTOFF )
383 int Find(
int *pSubseq1,
int *pSubseq2 )
385 return FindFastCS( pSubseq1, pSubseq2, 0, m_rComparator.GetLen1(),
386 0, m_rComparator.GetLen2() );
392 CompareData::~CompareData()
396 while( m_pDelRing->GetNext() != m_pDelRing.get() )
397 delete m_pDelRing->GetNext();
402 while( m_pInsertRing->GetNext() != m_pInsertRing.get() )
403 delete m_pInsertRing->GetNext();
404 m_pInsertRing.reset();
408 void CompareData::SetIndex(
size_t nLine,
size_t nIndex )
412 m_pIndex.reset(
new size_t[ m_aLines.size() ] );
413 memset( m_pIndex.get(), 0, m_aLines.size() *
sizeof( size_t ) );
415 if( nLine < m_aLines.size() )
416 m_pIndex[ nLine ] = nIndex;
419 void CompareData::SetChanged(
size_t nLine,
bool bFlag )
421 if( !m_pChangedFlag )
423 m_pChangedFlag.reset(
new bool[ m_aLines.size() +1 ] );
424 memset( m_pChangedFlag.get(), 0, (m_aLines.size() +1) *
sizeof(
bool ) );
426 if( nLine < m_aLines.size() )
427 m_pChangedFlag[ nLine ] = bFlag;
430 void CompareData::CompareLines( CompareData& rData )
432 CheckRanges( rData );
436 Hash aH( GetLineCount() + rData.GetLineCount() + 1 );
437 aH.CalcHashValue( *
this );
438 aH.CalcHashValue( rData );
439 nDifferent = aH.GetCount();
442 Compare aComp( nDifferent, *
this, rData );
446 sal_uLong CompareData::ShowDiffs(
const CompareData& rData )
448 sal_uLong nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
452 while( nStt1 < nLen1 || nStt2 < nLen2 )
454 if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
459 while( nStt1 < nLen1 && rData.GetChanged( nStt1 )) ++nStt1;
460 while( nStt2 < nLen2 && GetChanged( nStt2 )) ++nStt2;
466 CheckForChangesInLine( rData, nSav1, nStt1, nSav2, nStt2 );
477 bool CompareData::HasDiffs(
const CompareData& rData )
const
480 sal_uLong nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
483 while( nStt1 < nLen1 || nStt2 < nLen2 )
485 if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
529 m_pDataArr.reset(
new HashData[ nSize ] );
530 m_pDataArr[0].nNext = 0;
531 m_pDataArr[0].nHash = 0;
532 m_nPrime = primes[0];
534 for( i = 0; primes[i] < nSize / 3; i++)
537 m_pHashArr =
nullptr;
540 m_nPrime = primes[ i ];
541 m_pHashArr.reset(
new sal_uLong[ m_nPrime ] );
542 memset( m_pHashArr.get(), 0, m_nPrime *
sizeof(
sal_uLong ) );
545 void Hash::CalcHashValue( CompareData& rData )
550 for(
size_t n = 0;
n < rData.GetLineCount(); ++
n )
552 const SwCompareLine aLine = rData.GetLine( n );
555 sal_uLong* pFound = &m_pHashArr[ nH % m_nPrime ];
557 for( i = *pFound; ; i = m_pDataArr[i].nNext )
561 m_pDataArr[i].nNext = *pFound;
562 m_pDataArr[i].nHash = nH;
563 m_pDataArr[i].aLine = aLine;
567 else if( m_pDataArr[i].nHash == nH &&
568 m_pDataArr[i].aLine.Compare( aLine ))
571 rData.SetIndex( n, i );
575 Compare::Compare(
sal_uLong nDiff, CompareData& rData1, CompareData& rData2 )
577 std::unique_ptr<MovedData> pMD1, pMD2;
580 std::unique_ptr<char[]> pDiscard1(
new char[ rData1.GetLineCount() ] );
581 std::unique_ptr<char[]> pDiscard2(
new char[ rData2.GetLineCount() ] );
583 std::unique_ptr<sal_uLong[]> pCount1(
new sal_uLong[ nDiff ]);
584 std::unique_ptr<sal_uLong[]> pCount2(
new sal_uLong[ nDiff ]);
585 memset( pCount1.get(), 0, nDiff *
sizeof(
sal_uLong ));
586 memset( pCount2.get(), 0, nDiff *
sizeof(
sal_uLong ));
589 CountDifference( rData1, pCount1.get() );
590 CountDifference( rData2, pCount2.get() );
594 SetDiscard( rData1, pDiscard1.get(), pCount2.get() );
595 SetDiscard( rData2, pDiscard2.get(), pCount1.get() );
597 CheckDiscard( rData1.GetLineCount(), pDiscard1.get() );
598 CheckDiscard( rData2.GetLineCount(), pDiscard2.get() );
600 pMD1.reset(
new MovedData( rData1, pDiscard1.get() ));
601 pMD2.reset(
new MovedData( rData2, pDiscard2.get() ));
605 CompareSequence aTmp( rData1, rData2, *pMD1, *pMD2 );
608 ShiftBoundaries( rData1, rData2 );
611 void Compare::CountDifference(
const CompareData& rData,
sal_uLong* pCounts )
621 void Compare::SetDiscard(
const CompareData& rData,
622 char* pDiscard,
const sal_uLong* pCounts )
624 const sal_uLong nLen = rData.GetLineCount();
629 for(
sal_uLong n = nLen / 64; (
n =
n >> 2 ) > 0; )
637 nIdx = pCounts[ nIdx ];
638 pDiscard[
n ] = !nIdx ? 1 : nIdx > nMax ? 2 : 0;
645 void Compare::CheckDiscard(
sal_uLong nLen,
char* pDiscard )
649 if( 2 == pDiscard[ n ] )
651 else if( pDiscard[ n ] )
659 for (j = n; j < nLen; j++)
663 if( 2 == pDiscard[j] )
668 while( j > n && 2 == pDiscard[j - 1] )
680 if (provisional * 4 > length)
683 if (pDiscard[--j] == 2)
696 while ((tem = tem >> 2) > 0)
702 for (j = 0, consec = 0; j < length; j++)
703 if (pDiscard[n + j] != 2)
705 else if (minimum == ++consec)
708 else if (minimum < consec)
715 for (j = 0, consec = 0; j < length; j++)
717 if (j >= 8 && pDiscard[n + j] == 1)
719 if (pDiscard[n + j] == 2)
724 else if (pDiscard[n + j] == 0)
736 for (j = 0, consec = 0; j < length; j++)
738 if (j >= 8 && pDiscard[n - j] == 1)
740 if (pDiscard[n - j] == 2)
745 else if (pDiscard[n - j] == 0)
757 Compare::MovedData::MovedData( CompareData& rData,
const char* pDiscard )
763 for( n = 0; n < nLen; ++n )
765 rData.SetChanged( n );
771 m_pIndex.reset(
new sal_uLong[ m_nCount ] );
772 m_pLineNum.reset(
new sal_uLong[ m_nCount ] );
774 for( n = 0, m_nCount = 0; n < nLen; ++n )
777 m_pIndex[ m_nCount ] = rData.GetIndex( n );
778 m_pLineNum[ m_nCount++ ] = n;
784 Compare::CompareSequence::CompareSequence(
785 CompareData& rD1, CompareData& rD2,
786 const MovedData& rMD1,
const MovedData& rMD2 )
787 : m_rData1( rD1 ), m_rData2( rD2 ), m_rMoved1( rMD1 ), m_rMoved2( rMD2 )
789 sal_uLong nSize = rMD1.GetCount() + rMD2.GetCount() + 3;
791 m_pFDiag = m_pMemory.get() + ( rMD2.GetCount() + 1 );
792 m_pBDiag = m_pMemory.get() + ( nSize + rMD2.GetCount() + 1 );
794 Compare( 0, rMD1.GetCount(), 0, rMD2.GetCount() );
801 while( nStt1 < nEnd1 && nStt2 < nEnd2 &&
802 m_rMoved1.GetIndex( nStt1 ) == m_rMoved2.GetIndex( nStt2 ))
809 while( nEnd1 > nStt1 && nEnd2 > nStt2 &&
810 m_rMoved1.GetIndex( nEnd1 - 1 ) == m_rMoved2.GetIndex( nEnd2 - 1 ))
818 while( nStt2 < nEnd2 )
819 m_rData2.SetChanged( m_rMoved2.GetLineNum( nStt2++ ));
821 else if (nStt2 == nEnd2)
822 while (nStt1 < nEnd1)
823 m_rData1.SetChanged( m_rMoved1.GetLineNum( nStt1++ ));
831 d = CheckDiag( nStt1, nEnd1, nStt2, nEnd2, &c );
832 b = m_pBDiag[ std::make_signed_t<decltype(d)>(d) ];
837 Compare( nStt1, b, nStt2, b - d );
842 Compare( b, nEnd1, b - d, nEnd2 );
862 m_pFDiag[fmid] = nStt1;
863 m_pBDiag[bmid] = nEnd1;
871 m_pFDiag[--fmin - 1] = -1;
875 m_pFDiag[++fmax + 1] = -1;
878 for (d = fmax; d >= fmin; d -= 2)
880 tools::Long x,
y, tlo = m_pFDiag[d - 1], thi = m_pFDiag[d + 1];
888 m_rMoved1.GetIndex( x ) == m_rMoved2.GetIndex( y ))
894 if( odd && bmin <= d && d <= bmax && m_pBDiag[d] <= m_pFDiag[d] )
903 m_pBDiag[--bmin - 1] = INT_MAX;
907 m_pBDiag[++bmax + 1] = INT_MAX;
910 for (d = bmax; d >= bmin; d -= 2)
912 tools::Long x, y, tlo = m_pBDiag[d - 1], thi = m_pBDiag[d + 1];
920 m_rMoved1.GetIndex( x - 1 ) == m_rMoved2.GetIndex( y - 1 ))
926 if (!odd && fmin <= d && d <= fmax && m_pBDiag[d] <= m_pFDiag[d])
937 void lcl_ShiftBoundariesOneway( CompareData*
const pData, CompareData
const *
const pOtherData)
952 while( i < i_end && !pData->GetChanged( i ) )
954 while( pOtherData->GetChanged( j++ ))
971 while( pData->GetChanged( ++i ))
984 pData->GetIndex( start ) == pData->GetIndex( i ) &&
985 !pOtherData->GetChanged( j ) &&
986 start != preceding && other_start != other_preceding )
988 pData->SetChanged( start++,
false );
989 pData->SetChanged( i );
1000 other_preceding = j;
1005 void Compare::ShiftBoundaries( CompareData& rData1, CompareData& rData2 )
1007 lcl_ShiftBoundariesOneway(&rData1, &rData2);
1008 lcl_ShiftBoundariesOneway(&rData2, &rData1);
1011 sal_uLong SwCompareLine::GetHashValue()
const
1014 switch( m_pNode->GetNodeType() )
1017 nRet = GetTextNodeHashValue( *m_pNode->GetTextNode(), nRet );
1024 while( &aIdx.GetNode() != pEndNd )
1026 if( aIdx.GetNode().IsTextNode() )
1027 nRet = GetTextNodeHashValue( *aIdx.GetNode().GetTextNode(), nRet );
1035 OUString sStr( GetText() );
1036 for( sal_Int32 n = 0; n < sStr.getLength(); ++n )
1037 nRet = (nRet << 1) + sStr[ n ];
1052 const SwNode* pNd = m_pNode;
1053 switch( m_pNode->GetNodeType() )
1072 bool SwCompareLine::Compare(
const SwCompareLine& rLine )
const
1074 return CompareNode( *m_pNode, *rLine.m_pNode );
1079 OUString SimpleTableToText(
const SwNode &rNode)
1081 OUStringBuffer sRet;
1084 while (&aIdx.GetNode() != pEndNd)
1086 if (aIdx.GetNode().IsTextNode())
1088 if (sRet.getLength())
1090 sRet.append(
'\n' );
1092 sRet.append( aIdx.GetNode().GetTextNode()->GetExpandText(
nullptr) );
1096 return sRet.makeStringAndClear();
1100 bool SwCompareLine::CompareNode(
const SwNode& rDstNd,
const SwNode& rSrcNd )
1125 bRet = (SimpleTableToText(rSrcNd) == SimpleTableToText(rDstNd));
1133 & rSDstNd = static_cast<const SwSectionNode&>(rDstNd);
1135 & rDstSect = rSDstNd.GetSection();
1137 eDstSectType = rDstSect.GetType();
1138 switch( eSrcSectType )
1142 rSrcSect.
IsProtect() == rDstSect.IsProtect();
1147 ( rSDstNd.EndOfSectionIndex() - rSDstNd.GetIndex() );
1158 const SwTOXBase* pDstTOX = rDstSect.GetTOXBase();
1159 bRet = pSrcTOX && pDstTOX
1169 bRet = eSrcSectType == eDstSectType &&
1171 rDstSect.GetLinkFileName();
1195 OUString SwCompareLine::GetText()
const
1198 switch( m_pNode->GetNodeType() )
1201 sRet = m_pNode->GetTextNode()->GetExpandText(
nullptr);
1206 sRet =
"Tabelle: " + SimpleTableToText(*m_pNode);
1212 sRet =
"Section - Node:";
1220 sRet += OUString::number(
1230 OUString::number(pTOX->
GetType());
1243 sRet =
"Grafik - Node:";
1246 sRet =
"OLE - Node:";
1256 for( sal_Int32 n = 0; n < sStr.getLength(); ++n )
1257 nVal = (nVal << 1 ) + sStr[ n ];
1261 bool SwCompareLine::CompareTextNd(
const SwTextNode& rDstNd,
1274 bool SwCompareLine::ChangesInLine(
const SwCompareLine& rLine,
1275 std::unique_ptr<SwPaM>& rpInsRing, std::unique_ptr<SwPaM>& rpDelRing )
const
1284 const SwTextNode& rSrcNd = *rLine.GetNode().GetTextNode();
1289 int nDstLen = rDstNd.
GetText().getLength();
1290 int nSrcLen = rSrcNd.
GetText().getLength();
1292 int nMinLen =
std::min( nDstLen , nSrcLen );
1293 int nAvgLen = ( nDstLen + nSrcLen )/2;
1295 std::vector<int> aLcsDst( nMinLen + 1 );
1296 std::vector<int> aLcsSrc( nMinLen + 1 );
1300 std::vector<int> aTmpLcsDst( nMinLen + 1 );
1301 std::vector<int> aTmpLcsSrc( nMinLen + 1 );
1303 WordArrayComparator aCmp( &rDstNd, &rSrcNd );
1305 LgstCommonSubseq
aSeq( aCmp );
1307 nLcsLen =
aSeq.Find( aTmpLcsDst.data(), aTmpLcsSrc.data() );
1309 if( CmpOptions.nIgnoreLen )
1311 nLcsLen = CommonSubseq::IgnoreIsolatedPieces( aTmpLcsDst.data(), aTmpLcsSrc.data(),
1312 aCmp.GetLen1(), aCmp.GetLen2(),
1313 nLcsLen, CmpOptions.nIgnoreLen );
1316 nLcsLen = aCmp.GetCharSequence( aTmpLcsDst.data(), aTmpLcsSrc.data(),
1317 aLcsDst.data(), aLcsSrc.data(), nLcsLen );
1321 CharArrayComparator aCmp( &rDstNd, &rSrcNd );
1322 LgstCommonSubseq
aSeq( aCmp );
1324 nLcsLen =
aSeq.Find( aLcsDst.data(), aLcsSrc.data() );
1326 if( CmpOptions.nIgnoreLen )
1328 nLcsLen = CommonSubseq::IgnoreIsolatedPieces( aLcsDst.data(), aLcsSrc.data(), nDstLen,
1330 CmpOptions.nIgnoreLen );
1337 for(
int i = 0; i < nLcsLen; i++ )
1339 if( i != nLcsLen - 1 && aLcsDst[i] + 1 == aLcsDst[i + 1]
1340 && aLcsSrc[i] + 1 == aLcsSrc[i + 1] )
1346 nSqSum += nCnt*nCnt;
1352 if ( nAvgLen >= 8 && nSqSum*32 < nAvgLen*nAvgLen )
1359 for(
int i = 0; i <= nLcsLen; i++ )
1361 int nDstFrom = i ? (aLcsDst[i - 1] + 1) : 0;
1362 int nDstTo = ( i == nLcsLen ) ? nDstLen : aLcsDst[i];
1363 int nSrcFrom = i ? (aLcsSrc[i - 1] + 1) : 0;
1364 int nSrcTo = ( i == nLcsLen ) ? nSrcLen : aLcsSrc[i];
1366 SwPaM aPam( rDstNd, nDstTo + nSkip );
1368 if ( nDstFrom < nDstTo )
1370 SwPaM* pTmp =
new SwPaM( *aPam.GetPoint(), rpInsRing.get() );
1372 rpInsRing.reset(pTmp);
1377 if ( nSrcFrom < nSrcTo )
1381 SwPaM aCpyPam( rSrcNd, nSrcFrom );
1383 aCpyPam.GetPoint()->nContent = nSrcTo;
1384 aCpyPam.GetDoc().getIDocumentContentOperations().CopyRange( aCpyPam, *aPam.GetPoint(),
1388 SwPaM* pTmp =
new SwPaM( *aPam.GetPoint(), rpDelRing.get() );
1390 rpDelRing.reset(pTmp);
1394 nSkip += nSrcTo - nSrcFrom;
1447 void CompareData::CheckRanges( CompareData& rData )
1449 const SwNodes& rSrcNds = rData.m_rDoc.GetNodes();
1452 const SwNode& rSrcEndNd = rData.GetEndOfContent();
1453 const SwNode& rDstEndNd = GetEndOfContent();
1461 while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1463 const SwNode* pSrcNd = rSrcNds[ nSrcSttIdx ];
1464 const SwNode* pDstNd = rDstNds[ nDstSttIdx ];
1465 if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1468 nSrcSttIdx = NextIdx( pSrcNd );
1469 nDstSttIdx = NextIdx( pDstNd );
1472 nSrcEndIdx = PrevIdx( &rSrcEndNd );
1473 nDstEndIdx = PrevIdx( &rDstEndNd );
1474 while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1476 const SwNode* pSrcNd = rSrcNds[ nSrcEndIdx ];
1477 const SwNode* pDstNd = rDstNds[ nDstEndIdx ];
1478 if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1481 nSrcEndIdx = PrevIdx( pSrcNd );
1482 nDstEndIdx = PrevIdx( pDstNd );
1485 while( nSrcSttIdx <= nSrcEndIdx )
1487 const SwNode* pNd = rSrcNds[ nSrcSttIdx ];
1488 rData.InsertLine( SwCompareLine( *pNd ) );
1489 nSrcSttIdx = NextIdx( pNd );
1492 while( nDstSttIdx <= nDstEndIdx )
1494 const SwNode* pNd = rDstNds[ nDstSttIdx ];
1496 nDstSttIdx = NextIdx( pNd );
1504 m_pInsertRing.get() );
1505 if( !m_pInsertRing )
1506 m_pInsertRing.reset( pTmp );
1511 void CompareData::ShowDelete(
1512 const CompareData& rData,
1519 rData.GetLine( nEnd-1 ).GetEndNode(),
SwNodeOffset(1) );
1522 std::optional<SwCompareLine> xLine;
1525 if( GetLineCount() == nInsPos )
1527 xLine = GetLine( nInsPos-1 );
1531 xLine = GetLine( nInsPos );
1540 pLineNd = &xLine->GetNode();
1544 pLineNd = &GetEndOfContent();
1551 rData.m_rDoc.GetDocumentContentOperationsManager().CopyWithFlyInFly(aRg, aInsPos);
1562 m_pDelRing.reset(pTmp);
1575 void CompareData::CheckForChangesInLine(
const CompareData& rData,
1579 LineArrayComparator aCmp( *
this, rData, nThisStt, nThisEnd,
1582 int nMinLen =
std::min( aCmp.GetLen1(), aCmp.GetLen2() );
1583 std::unique_ptr<int[]> pLcsDst(
new int[ nMinLen ]);
1584 std::unique_ptr<int[]> pLcsSrc(
new int[ nMinLen ]);
1586 FastCommonSubseq subseq( aCmp );
1587 int nLcsLen = subseq.Find( pLcsDst.get(), pLcsSrc.get() );
1588 for (
int i = 0; i <= nLcsLen; i++)
1591 int nDstFrom = i ? pLcsDst[i - 1] + 1 : 0;
1593 int nDstTo = ( i == nLcsLen ) ? aCmp.GetLen1() : pLcsDst[i];
1595 int nSrcFrom = i ? pLcsSrc[i - 1] + 1 : 0;
1597 int nSrcTo = ( i == nLcsLen ) ? aCmp.GetLen2() : pLcsSrc[i];
1601 const SwCompareLine aDstLn = GetLine( nThisStt + nDstFrom - 1 );
1602 const SwCompareLine aSrcLn = rData.GetLine( nStt + nSrcFrom - 1 );
1606 if( !aDstLn.ChangesInLine( aSrcLn, m_pInsertRing, m_pDelRing ) )
1608 ShowInsert( nThisStt + nDstFrom - 1, nThisStt + nDstFrom );
1609 ShowDelete( rData, nStt + nSrcFrom - 1, nStt + nSrcFrom,
1610 nThisStt + nDstFrom );
1615 if( nDstFrom != nDstTo )
1617 ShowInsert( nThisStt + nDstFrom, nThisStt + nDstTo );
1621 if( nSrcFrom != nSrcTo )
1623 ShowDelete( rData, nStt + nSrcFrom, nStt + nSrcTo, nThisStt + nDstTo );
1628 void CompareData::SetRedlinesToDoc(
bool bUseDocInfo )
1630 SwPaM* pTmp = m_pDelRing.get();
1636 OSL_ENSURE(pDocShell,
"no SwDocShell");
1638 uno::Reference<document::XDocumentPropertiesSupplier> xDPS(
1639 pDocShell->GetModel(), uno::UNO_QUERY_THROW);
1640 uno::Reference<document::XDocumentProperties> xDocProps(
1641 xDPS->getDocumentProperties());
1642 OSL_ENSURE(xDocProps.is(),
"Doc has no DocumentProperties");
1644 if( bUseDocInfo && xDocProps.is() ) {
1645 OUString aTmp( 1 == xDocProps->getEditingCycles()
1646 ? xDocProps->getAuthor()
1647 : xDocProps->getModifiedBy() );
1648 util::DateTime uDT( 1 == xDocProps->getEditingCycles()
1649 ? xDocProps->getCreationDate()
1650 : xDocProps->getModificationDate() );
1652 if( !aTmp.isEmpty() )
1662 SwRedlineData aRedlnData( RedlineType::Delete, nAuthor, aTimeStamp,
1663 OUString(),
nullptr );
1673 if (& GetEndOfContent() ==
1679 pContentNode ? pContentNode->Len() : 0 );
1684 if (prev.GetNode().IsTextNode())
1687 *prev.GetNode().GetTextNode(),
1688 prev.GetNode().GetTextNode()->Len());
1698 std::make_unique<SwUndoCompDoc>( *pTmp,
false ));
1702 }
while( m_pDelRing.get() != ( pTmp = pTmp->
GetNext()) );
1705 pTmp = m_pInsertRing.get();
1717 if (& GetEndOfContent() ==
1723 pContentNode ? pContentNode->Len() : 0 );
1728 if (prev.GetNode().IsTextNode())
1731 *prev.GetNode().GetTextNode(),
1732 prev.GetNode().GetTextNode()->Len());
1736 }
while( m_pInsertRing.get() != ( pTmp = pTmp->
GetNext()) );
1737 SwRedlineData aRedlnData( RedlineType::Insert, nAuthor, aTimeStamp,
1738 OUString(),
nullptr );
1741 if( pTmp->
GetNext() != m_pInsertRing.get() )
1747 if( rSttEnd == rEndStt ||
1748 (!rEndStt.nContent.GetIndex() &&
1753 if( pTmp->
GetNext() == m_pInsertRing.get() )
1756 rEndStt = *pTmp->
Start();
1758 pTmp = m_pInsertRing.get();
1769 }
while( m_pInsertRing.get() != pTmp );
1779 std::make_unique<SwUndoCompDoc>( *pTmp,
true ));
1781 }
while( m_pInsertRing.get() != ( pTmp = pTmp->
GetNext()) );
1790 Comparators buildComparators(
SwDoc &rSrcDoc,
SwDoc &rDestDoc)
1792 Comparators aComparisons;
1794 aComparisons.emplace_back(std::make_shared<CompareMainText>(rSrcDoc,
true),
1795 std::make_shared<CompareMainText>(rDestDoc,
true));
1800 if (pSrcFrameFormats->
size() == pDestFrameFormats->
size())
1802 for (
size_t i = 0; i < pSrcFrameFormats->
size(); ++i)
1805 const SwFrameFormat& rDestFormat = *(*pDestFrameFormats)[i];
1808 if (!pSrcIdx && !pDestIdx)
1810 if (!pSrcIdx || !pDestIdx)
1814 if (!pSrcNode && !pDestNode)
1816 if (!pSrcNode || !pDestNode)
1823 aComparisons.emplace_back(std::make_shared<CompareFrameFormatText>(rSrcDoc, *pSrcIdx),
1824 std::make_shared<CompareFrameFormatText>(rDestDoc, *pDestIdx));
1827 return aComparisons;
1840 CmpOptions.eCmpMode =
SW_MOD()->GetCompareMode();
1846 CmpOptions.bUseRsid =
true;
1847 CmpOptions.nIgnoreLen = 2;
1852 CmpOptions.bUseRsid =
false;
1853 CmpOptions.nIgnoreLen = 3;
1859 CmpOptions.nIgnoreLen =
SW_MOD()->IsIgnorePieces() ?
SW_MOD()->GetPieceLen() : 0;
1871 Comparators aComparisons(buildComparators(rSrcDoc, *
this));
1873 for (
auto&
a : aComparisons)
1875 CompareData& rD0 = *
a.first;
1876 CompareData& rD1 = *
a.second;
1877 rD1.CompareLines( rD0 );
1878 nRet |= rD1.ShowDiffs( rD0 );
1886 for (
auto&
a : aComparisons)
1888 CompareData& rD1 = *
a.second;
1889 rD1.SetRedlinesToDoc( !bDocWasModified );
1907 struct SaveMergeRedline
1912 sal_uInt16 InsertRedline(
SwPaM* pLastDestRedline);
1916 SaveMergeRedline::SaveMergeRedline(
const SwNode& rDstNd,
1918 : pSrcRedl( &rSrcRedl )
1927 if( RedlineType::Delete != pDestRedl->GetType() )
1933 pDestRedl->SetMark();
1936 pDestRedl->GetPoint()->nContent.Assign( pDestRedl->GetContentNode(),
1940 sal_uInt16 SaveMergeRedline::InsertRedline(
SwPaM* pLastDestRedline)
1942 sal_uInt16 nIns = 0;
1943 SwDoc& rDoc = pDestRedl->GetDoc();
1945 if( RedlineType::Insert == pDestRedl->GetType() )
1950 SwNodeIndex aSaveNd( pDestRedl->GetPoint()->nNode, -1 );
1951 const sal_Int32 nSaveCnt = pDestRedl->GetPoint()->nContent.
GetIndex();
1956 pSrcRedl->GetDoc().getIDocumentContentOperations().CopyRange(
1957 *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1962 pDestRedl->SetMark();
1964 pDestRedl->GetMark()->nNode = aSaveNd;
1965 pDestRedl->GetMark()->nContent.Assign( aSaveNd.GetNode().GetContentNode(),
1968 if( pLastDestRedline && *pLastDestRedline->
GetPoint() == *pDestRedl->GetPoint() )
1969 *pLastDestRedline->
GetPoint() = *pDestRedl->GetMark();
1976 * pDEnd = pDestRedl->GetPoint();
1984 for( ; n < rRedlineTable.
size(); ++n )
1988 * pREnd = pRedl->
End();
1989 if( RedlineType::Delete == pRedl->
GetType() ||
1990 RedlineType::Insert == pRedl->
GetType() )
2002 pDestRedl =
nullptr;
2007 n = rRedlineTable.
size();
2011 assert(pDestRedl &&
"is this actually impossible");
2015 pDestRedl->GetRedlineData(), *pDStt );
2019 std::unique_ptr<SwUndoCompDoc> pUndo;
2047 else if( *pDEnd <= *pRStt )
2055 std::unique_ptr<SwUndoCompDoc> pUndo;
2071 pDestRedl =
nullptr;
2093 CompareMainText aD0(rSrcDoc,
false);
2094 CompareMainText aD1(*
this,
false);
2095 aD1.CompareLines( aD0 );
2096 if( !aD1.HasDiffs( aD0 ) )
2101 std::vector<SaveMergeRedline> vRedlines;
2109 if( nEndOfExtra < nNd &&
2110 ( RedlineType::Insert == eType || RedlineType::Delete == eType ))
2113 nMyEndOfExtra + nNd - nEndOfExtra ];
2117 vRedlines.emplace_back(*pDstNd, *pRedl);
2121 if( !vRedlines.empty() )
2131 SwPaM* pLastDestRedline(
nullptr);
2132 for(SaveMergeRedline& rRedline: vRedlines)
2134 nRet += rRedline.InsertRedline(pLastDestRedline);
2135 pLastDestRedline = rRedline.pDestRedl;
2151 LineArrayComparator::LineArrayComparator(
const CompareData &rD1,
2152 const CompareData &rD2,
int nStt1,
2153 int nEnd1,
int nStt2,
int nEnd2 )
2154 : m_rData1( rD1 ), m_rData2( rD2 ), m_nFirst1( nStt1 ), m_nFirst2( nStt2 )
2156 m_nLen1 = nEnd1 - nStt1;
2157 m_nLen2 = nEnd2 - nStt2;
2160 bool LineArrayComparator::Compare(
int nIdx1,
int nIdx2 )
const
2162 if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= m_nLen1 || nIdx2 >= m_nLen2 )
2164 OSL_ENSURE(
false,
"Index out of range!" );
2171 if( !pTextNd1 || !pTextNd2
2172 || ( CmpOptions.bUseRsid && !pTextNd1->
CompareParRsid( *pTextNd2 ) ) )
2177 const sal_Int32 nPar1Len = pTextNd1->
Len();
2178 const sal_Int32 nPar2Len = pTextNd2->
Len();
2180 if(
std::min( nPar1Len, nPar2Len ) * 3 < std::max( nPar1Len, nPar2Len ) )
2185 sal_Int32 nBorderLen = ( nPar1Len + nPar2Len )/16;
2187 if( nBorderLen < 3 )
2189 nBorderLen = std::min<sal_Int32>( 3,
std::min( nPar1Len, nPar2Len ) );
2192 std::set<unsigned> aHashes;
2194 unsigned nMul = 251;
2198 for( i = 0; i < nBorderLen - 1; i++ )
2202 for( i = 0; i < nBorderLen; i++ )
2204 nHash = nHash*nMul + pTextNd1->
GetText()[i];
2206 aHashes.insert( nHash );
2207 for( ; i < nPar1Len; i++ )
2209 nHash = nHash - nPow*pTextNd1->
GetText()[ i - nBorderLen ];
2210 nHash = nHash*nMul + pTextNd1->
GetText()[ i ];
2212 aHashes.insert( nHash );
2216 for( i = 0; i < nBorderLen; i++ )
2218 nHash = nHash*nMul + pTextNd2->
GetText()[ i ];
2221 if( aHashes.find( nHash ) != aHashes.end() )
2226 for( ; i < nPar2Len; i++ )
2228 nHash = nHash - nPow*pTextNd2->
GetText()[ i - nBorderLen ];
2229 nHash = nHash*nMul + pTextNd2->
GetText()[ i ];
2230 if( aHashes.find( nHash ) != aHashes.end() )
2238 bool CharArrayComparator::Compare(
int nIdx1,
int nIdx2 )
const
2240 if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= GetLen1() || nIdx2 >= GetLen2() )
2242 OSL_ENSURE(
false,
"Index out of range!" );
2246 return ( !CmpOptions.bUseRsid
2247 || m_pTextNode1->
CompareRsid( *m_pTextNode2, nIdx1 + 1, nIdx2 + 1 ) )
2248 && m_pTextNode1->
GetText()[ nIdx1 ] == m_pTextNode2->
GetText()[ nIdx2 ];
2251 WordArrayComparator::WordArrayComparator(
const SwTextNode *pNode1,
2253 : m_pTextNode1( pNode1 ), m_pTextNode2( pNode2 )
2255 m_pPos1.reset(
new int[ m_pTextNode1->
GetText().getLength() + 1 ] );
2256 m_pPos2.reset(
new int[ m_pTextNode2->
GetText().getLength() + 1 ] );
2258 CalcPositions( m_pPos1.get(), m_pTextNode1, m_nCount1 );
2259 CalcPositions( m_pPos2.get(), m_pTextNode2, m_nCount2 );
2262 bool WordArrayComparator::Compare(
int nIdx1,
int nIdx2 )
const
2264 int nLen = m_pPos1[ nIdx1 + 1 ] - m_pPos1[ nIdx1 ];
2265 if( nLen != m_pPos2[ nIdx2 + 1 ] - m_pPos2[ nIdx2 ] )
2269 for(
int i = 0; i < nLen; i++)
2271 if( m_pTextNode1->
GetText()[ m_pPos1[ nIdx1 ] + i ]
2272 != m_pTextNode2->
GetText()[ m_pPos2[ nIdx2 ] + i ]
2273 || ( CmpOptions.bUseRsid && !m_pTextNode1->
CompareRsid( *m_pTextNode2,
2274 m_pPos1[ nIdx1 ] + i, m_pPos2[ nIdx2 ] + i ) ) )
2282 int WordArrayComparator::GetCharSequence(
const int *pWordLcs1,
2283 const int *pWordLcs2,
int *pSubseq1,
int *pSubseq2,
int nLcsLen )
2286 for(
int i = 0; i < nLcsLen; i++ )
2289 if( m_pPos1[ pWordLcs1[i] + 1 ] - m_pPos1[ pWordLcs1[i] ]
2290 != m_pPos2[ pWordLcs2[i] + 1 ] - m_pPos2[ pWordLcs2[i] ] )
2294 for(
int j = 0; j < m_pPos1[pWordLcs1[i]+1] - m_pPos1[pWordLcs1[i]]; j++)
2296 pSubseq1[ nLen ] = m_pPos1[ pWordLcs1[i] ] + j;
2297 pSubseq2[ nLen ] = m_pPos2[ pWordLcs2[i] ] + j;
2299 if( m_pTextNode1->
GetText()[ m_pPos1[ pWordLcs1[i] ] + j ]
2300 != m_pTextNode2->
GetText()[ m_pPos2[ pWordLcs2[i] ] + j ] )
2312 void WordArrayComparator::CalcPositions(
int *pPos,
const SwTextNode *pTextNd,
2316 for (
int i = 0; i <= pTextNd->
GetText().getLength(); ++i)
2318 if (i == 0 || i == pTextNd->
GetText().getLength()
2319 || !rtl::isAsciiAlphanumeric( pTextNd->
GetText()[ i - 1 ])
2320 || !rtl::isAsciiAlphanumeric( pTextNd->
GetText()[ i ]))
2328 int CommonSubseq::FindLCS(
int *pLcs1,
int *pLcs2,
int nStt1,
int nEnd1,
2329 int nStt2,
int nEnd2 )
2331 int nLen1 = nEnd1 ? nEnd1 - nStt1 : m_rComparator.GetLen1();
2332 int nLen2 = nEnd2 ? nEnd2 - nStt2 : m_rComparator.GetLen2();
2334 assert( nLen1 >= 0 );
2335 assert( nLen2 >= 0 );
2337 std::unique_ptr<int*[]> pLcs(
new int*[ nLen1 + 1 ] );
2340 for(
int i = 1; i < nLen1 + 1; i++ )
2341 pLcs[ i ] = pLcs[ i - 1 ] + nLen2 + 1;
2343 for(
int i = 0; i <= nLen1; i++ )
2346 for(
int j = 0; j <= nLen2; j++ )
2350 for(
int i = 1; i <= nLen1; i++ )
2352 for(
int j = 1; j <= nLen2; j++ )
2354 if( m_rComparator.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2355 pLcs[i][j] = pLcs[i - 1][j - 1] + 1;
2357 pLcs[i][j] = std::max( pLcs[i][j - 1], pLcs[i - 1][j] );
2361 int nLcsLen = pLcs[ nLen1 ][ nLen2 ];
2364 if( pLcs1 && pLcs2 )
2368 int nIdx = nLcsLen - 1;
2370 while( nIdx1 > 0 && nIdx2 > 0 )
2372 if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 - 1 ][ nIdx2 ] )
2374 else if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 ][ nIdx2 - 1 ] )
2380 pLcs1[ nIdx ] = nIdx1 + nStt1;
2381 pLcs2[ nIdx ] = nIdx2 + nStt2;
2390 int CommonSubseq::IgnoreIsolatedPieces(
int *pLcs1,
int *pLcs2,
int nLen1,
2391 int nLen2,
int nLcsLen,
int nPieceLen )
2401 if( pLcs1[ 0 ] == 0 && pLcs2[ 0 ] == 0 )
2403 while( nNext < nLcsLen - 1 && pLcs1[ nNext ] + 1 == pLcs1[ nNext + 1 ]
2404 && pLcs2[ nNext ] + 1 == pLcs2[ nNext + 1 ] )
2413 for(
int i = nNext; i < nLcsLen; i++ )
2415 if( i != nLcsLen - 1 && pLcs1[ i ] + 1 == pLcs1[ i + 1 ]
2416 && pLcs2[ i ] + 1 == pLcs2[ i + 1 ] )
2422 if( nCnt > nPieceLen
2424 || ( i == nLcsLen - 1
2425 && pLcs1[i] == nLen1 - 1 && pLcs2[i] == nLen2 - 1 ))
2427 for(
int j = i + 1 - nCnt; j <= i; j++ )
2429 pLcs2[ nNext ] = pLcs2[ j ];
2430 pLcs1[ nNext ] = pLcs1[ j ];
2441 LgstCommonSubseq::LgstCommonSubseq( ArrayComparator &rComparator )
2442 : CommonSubseq( rComparator, CUTOFF )
2444 m_pBuff1.reset(
new int[ rComparator.GetLen2() + 1 ] );
2445 m_pBuff2.reset(
new int[ rComparator.GetLen2() + 1 ] );
2447 m_pL1.reset(
new int[ rComparator.GetLen2() + 1 ] );
2448 m_pL2.reset(
new int[ rComparator.GetLen2() + 1 ] );
2451 void LgstCommonSubseq::FindL(
int *pL,
int nStt1,
int nEnd1,
2452 int nStt2,
int nEnd2 )
2454 int nLen1 = nEnd1 ? nEnd1 - nStt1 : m_rComparator.GetLen1();
2455 int nLen2 = nEnd2 ? nEnd2 - nStt2 : m_rComparator.GetLen2();
2457 int *currL = m_pBuff1.get();
2458 int *prevL = m_pBuff2.get();
2461 if( nLen2 > m_rComparator.GetLen2() )
2467 memset( m_pBuff1.get(), 0,
sizeof( m_pBuff1[0] ) * ( nLen2 + 1 ) );
2468 memset( m_pBuff2.get(), 0,
sizeof( m_pBuff2[0] ) * ( nLen2 + 1 ) );
2471 for(
int i = 1; i <= nLen1; i++ )
2473 for(
int j = 1; j <= nLen2; j++ )
2475 if( m_rComparator.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2476 currL[j] = prevL[j - 1] + 1;
2478 currL[j] = std::max( currL[j - 1], prevL[j] );
2484 memcpy( pL, prevL, ( nLen2 + 1 ) *
sizeof( *prevL ) );
2487 int LgstCommonSubseq::HirschbergLCS(
int *pLcs1,
int *pLcs2,
int nStt1,
2488 int nEnd1,
int nStt2,
int nEnd2 )
2492 nLen1 = nEnd1 - nStt1;
2493 nLen2 = nEnd2 - nStt2;
2495 if( ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2497 if( !nLen1 || !nLen2 )
2501 return FindLCS(pLcs1, pLcs2, nStt1, nEnd1, nStt2, nEnd2);
2506 FindL( m_pL1.get(), nStt1, nStt1 + nMid, nStt2, nEnd2 );
2507 FindL( m_pL2.get(), nStt1 + nMid, nEnd1, nStt2, nEnd2 );
2514 for( i = 0; i <= nLen2; i++ )
2516 if( m_pL1[i] + ( m_pL2[nLen2] - m_pL2[i] ) > nMaxVal )
2519 nMaxVal = m_pL1[i]+( m_pL2[nLen2] - m_pL2[i] );
2523 int nRet = HirschbergLCS( pLcs1, pLcs2, nStt1, nStt1 + nMid,
2524 nStt2, nStt2 + nMaxPos );
2525 nRet += HirschbergLCS( pLcs1 + nRet, pLcs2 + nRet, nStt1 + nMid, nEnd1,
2526 nStt2 + nMaxPos, nEnd2 );
2531 int LgstCommonSubseq::Find(
int *pSubseq1,
int *pSubseq2 )
2535 int nEnd1 = m_rComparator.GetLen1();
2536 int nEnd2 = m_rComparator.GetLen2();
2539 while( nStt < nEnd1 && nStt < nEnd2 && m_rComparator.Compare( nStt, nStt ) )
2541 pSubseq1[ nStt ] = nStt;
2542 pSubseq2[ nStt ] = nStt;
2550 while( nStt < nEnd1 && nStt < nEnd2
2551 && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2558 int nLen = HirschbergLCS( pSubseq1, pSubseq2, nStt, nEnd1, nStt, nEnd2 );
2560 for(
int i = 0; i < nCutEnd; i++ )
2562 pSubseq1[ nLen + i ] = nEnd1 + i;
2563 pSubseq2[ nLen + i ] = nEnd2 + i;
2566 return nStt + nLen + nCutEnd;
2569 int FastCommonSubseq::FindFastCS(
int *pSeq1,
int *pSeq2,
int nStt1,
2570 int nEnd1,
int nStt2,
int nEnd2 )
2576 while( nStt1 < nEnd1 && nStt2 < nEnd2 && m_rComparator.Compare( nStt1, nStt2 ) )
2578 pSeq1[ nCutBeg ] = nStt1++;
2579 pSeq2[ nCutBeg ] = nStt2++;
2587 while( nStt1 < nEnd1 && nStt2 < nEnd2
2588 && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2595 int nLen1 = nEnd1 - nStt1;
2596 int nLen2 = nEnd2 - nStt2;
2599 if( nLen1 <= 0 || nLen2 <= 0 )
2601 for(
int i = 0; i < nCutEnd; i++ )
2603 pSeq1[ i ] = nEnd1 + i;
2604 pSeq2[ i ] = nEnd2 + i;
2606 return nCutBeg + nCutEnd;
2610 if( nLen1 < 3 || nLen2 < 3 || ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2612 int nLcsLen = FindLCS( pSeq1, pSeq2, nStt1, nEnd1, nStt2, nEnd2);
2614 for(
int i = 0; i < nCutEnd; i++ )
2616 pSeq1[ nLcsLen + i ] = nEnd1 + i;
2617 pSeq2[ nLcsLen + i ] = nEnd2 + i;
2619 return nCutBeg + nLcsLen + nCutEnd;
2622 int nMid1 = nLen1/2;
2623 int nMid2 = nLen2/2;
2626 int nPos1 = -1, nPos2 = -1;
2629 for( nRad = 0; nRad*nRad <
std::min( nMid1, nMid2 ); nRad++ )
2632 for(
int i = nMid1 - nRad; i <= nMid1 + nRad; i++ )
2634 if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 - nRad ) )
2637 nPos2 = nStt2 + nMid2 - nRad;
2640 if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 + nRad ) )
2643 nPos2 = nStt2 + nMid2 - nRad;
2648 for(
int i = nMid2 - nRad; i <= nMid2 + nRad; i++ )
2650 if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2653 nPos1 = nStt1 + nMid1 - nRad;
2656 if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2659 nPos1 = nStt1 + nMid1 - nRad;
2668 for(
int i = 0; i < nCutEnd; i++ )
2670 pSeq1[ i ] = nEnd1 + i;
2671 pSeq2[ i ] = nEnd2 + i;
2673 return nCutBeg + nCutEnd;
2677 int nLen = FindFastCS( pSeq1, pSeq2, nStt1, nPos1, nStt2, nPos2 );
2679 pSeq1[ nLen ] = nPos1;
2680 pSeq2[ nLen ] = nPos2;
2683 nLen += FindFastCS( pSeq1 + nLen + 1, pSeq2 + nLen + 1,
2684 nPos1 + 1, nEnd1, nPos2 + 1, nEnd2 ) + 1;
2686 for(
int i = 0; i < nCutEnd; i++ )
2688 pSeq1[ nLen + i ] = nEnd1 + i;
2689 pSeq2[ nLen + i ] = nEnd2 + i;
2692 return nLen + nCutBeg + nCutEnd;
const SwEndNode * EndOfSectionNode() const
SwNodeOffset min(const SwNodeOffset &a, const SwNodeOffset &b)
tools::Long CompareDoc(const SwDoc &rDoc)
virtual sal_Int32 Len() const
SwNodeOffset EndOfSectionIndex() const
Marks a position in the document model.
SwContentNode * GetNode(SwPaM &rPam, bool &rbFirst, SwMoveFnCollection const &fnMove, bool const bInReadOnly, SwRootFrame const *const i_pLayout)
This function returns the next node in direction of search.
SwComparePosition ComparePosition(const T &rStt1, const T &rEnd1, const T &rStt2, const T &rEnd2)
const OUString & GetText() const
SwDocShell * GetDocShell()
virtual AppendResult AppendRedline(SwRangeRedline *pNewRedl, bool bCallDelete)=0
Append a new redline.
virtual void SetRedlineFlags_intern(RedlineFlags eMode)=0
Set a new redline mode.
sal_uInt32 getRsidRoot() const
virtual sal_Int32 Len() const override
virtual void SetModified()=0
Must be called manually at changes of format.
Pos1 is as large as Pos2.
const SwPosition * GetMark() const
Pos1 completely contained in Pos2.
virtual SwUndoId EndUndo(SwUndoId const eUndoId, SwRewriter const *const pRewriter)=0
Closes undo block.
SwSectionNode is derived from SwStartNode.
OUString const & GetTypeName() const
IDocumentUndoRedo & GetIDocumentUndoRedo()
OUString const & GetLinkFileName() const
const SwFrameFormats * GetSpzFrameFormats() const
const SwSection & GetSection() const
SwContentNode * GetContentNode(bool bPoint=true) const
Pos1 end touches at Pos2 start.
SwNodeType GetNodeType() const
check if target position is in fly anchored at source range
virtual void DoUndo(bool const bDoUndo)=0
Enable/Disable Undo.
Pos2 completely contained in Pos1.
std::pair< CompareDataPtr, CompareDataPtr > CompareDataPtrPair
SwNodeOffset GetIndex() const
virtual bool DoesUndo() const =0
Is Undo enabled?
const SwRedlineData & GetRedlineData(sal_uInt16 nPos=0) const
SwNode & GetEndOfContent() const
Regular ContentSection (i.e. the BodyText).
virtual std::size_t GetRedlineAuthor()=0
bool IsContentNode() const
PaM is Point and Mark: a selection of the document model.
virtual void AppendUndo(std::unique_ptr< SwUndo > pUndo)=0
Add new Undo action.
UNDERLYING_TYPE get() const
virtual SwUndoId StartUndo(SwUndoId const eUndoId, SwRewriter const *const pRewriter)=0
Opens undo block.
const SwStartNode * StartOfSectionNode() const
const SwPosition * GetPoint() const
Pos1 start touches at Pos2 end.
virtual bool IsModified() const =0
Changes of document?
std::vector< CompareDataPtrPair > Comparators
SwIndex & Assign(SwIndexReg *, sal_Int32)
const SwTOXBase * GetTOXBase() const
virtual bool DeleteRedline(const SwPaM &rPam, bool bSaveInUndo, RedlineType nDelType)=0
SwContentNode * GetContentNode()
SwNodeOffset GetIndex() const
vector_type::size_type size_type
constexpr std::enable_if_t< std::is_signed_v< T >, std::make_unsigned_t< T > > make_unsigned(T value)
bool CompareRsid(const SwTextNode &rTextNode, sal_Int32 nStt1, sal_Int32 nStt2) const
IDocumentState const & getIDocumentState() const
Marks a node in the document model.
bool CompareParRsid(const SwTextNode &rTextNode) const
virtual std::size_t InsertRedlineAuthor(const OUString &rAuthor)=0
const OUString & GetTitle() const
const SwPosition * Start() const
const SwNodeIndex * GetContentIdx() const
virtual const SwRangeRedline * GetRedline(const SwPosition &rPos, SwRedlineTable::size_type *pFndPos) const =0
static CmpOptionsContainer CmpOptions
SwTextNode is a paragraph in the document model.
IDocumentRedlineAccess const & getIDocumentRedlineAccess() const
OUString GetExpandText(SwRootFrame const *pLayout, const sal_Int32 nIdx=0, const sal_Int32 nLen=-1, const bool bWithNum=false, const bool bAddSpaceAfterListLabelStr=false, const bool bWithSpacesForLevel=false, const ExpandMode eAdditionalMode=ExpandMode::ExpandFootnote) const
add 4th optional parameter indicating, when that a spa...
Pos1 overlaps Pos2 at the end.
const SwNodes & GetNodes() const
virtual void SetRedlineFlags(RedlineFlags eMode)=0
Set a new redline mode.
sal_Int32 GetIndex() const
const SwPosition * End() const
RedlineType GetType(sal_uInt16 nPos=0) const
SwTableNode is derived from SwStartNode.
Sequence< sal_Int8 > aSeq
o3tl::strong_int< sal_Int32, struct Tag_SwNodeOffset > SwNodeOffset
static SwNode * GetEndNode(SwOutlineNodes const *pOutlNds, int nOutlineLevel, SwOutlineNodes::size_type *nOutl)
std::shared_ptr< CompareData > CompareDataPtr
virtual RedlineFlags GetRedlineFlags() const =0
Query the currently set redline mode.
static void InsertLine(std::vector< SwTableLine * > &rLineArr, SwTableLine *pLine)
SwSectionNode * GetSectionNode()
virtual void SetMark()
Unless this is called, the getter method of Mark will return Point.
SectionType GetType() const
tools::Long MergeDoc(const SwDoc &rDoc)
Merge two documents.
virtual const SwRedlineTable & GetRedlineTable() const =0
SwNode & GetEndOfExtras() const
This is the last EndNode of a special section.
static constexpr size_type npos
Pos1 overlaps Pos2 at the beginning.
SwTextNode * GetTextNode()
Inline methods from Node.hxx.
virtual void ResetModified()=0
Base class of the Writer document model elements.