Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #include <hintids.hxx>
21 : #include <vcl/vclenum.hxx>
22 : #include <editeng/crossedoutitem.hxx>
23 : #include <editeng/colritem.hxx>
24 : #include <editeng/boxitem.hxx>
25 : #include <editeng/svxenum.hxx>
26 : #include <editeng/udlnitem.hxx>
27 : #include <swmodule.hxx>
28 : #include <doc.hxx>
29 : #include <IDocumentUndoRedo.hxx>
30 : #include <DocumentContentOperationsManager.hxx>
31 : #include <IDocumentRedlineAccess.hxx>
32 : #include <IDocumentState.hxx>
33 : #include <docary.hxx>
34 : #include <pam.hxx>
35 : #include <ndtxt.hxx>
36 : #include <redline.hxx>
37 : #include <UndoRedline.hxx>
38 : #include <section.hxx>
39 : #include <tox.hxx>
40 : #include <docsh.hxx>
41 :
42 : #include <com/sun/star/document/XDocumentPropertiesSupplier.hpp>
43 : #include <com/sun/star/document/XDocumentProperties.hpp>
44 :
45 : #include <vector>
46 :
47 : #include <set>
48 : #include <cctype>
49 :
50 : #include <boost/scoped_array.hpp>
51 :
52 : using namespace ::com::sun::star;
53 :
54 : using ::std::vector;
55 :
56 : class CompareLine
57 : {
58 : public:
59 0 : CompareLine() {}
60 : virtual ~CompareLine();
61 :
62 : virtual sal_uLong GetHashValue() const = 0;
63 : virtual bool Compare( const CompareLine& rLine ) const = 0;
64 : };
65 :
66 : class CompareData
67 : {
68 : size_t* pIndex;
69 : bool* pChangedFlag;
70 :
71 : protected:
72 : vector< CompareLine* > aLines;
73 : sal_uLong nSttLineNum;
74 :
75 : // Truncate beginning and end and add all others to the LinesArray
76 : virtual void CheckRanges( CompareData& ) = 0;
77 :
78 : public:
79 : CompareData();
80 : virtual ~CompareData();
81 :
82 : // Are there differences?
83 : bool HasDiffs( const CompareData& rData ) const;
84 :
85 : // Triggers the comparison and creation of two documents
86 : void CompareLines( CompareData& rData );
87 : // Display the differences - calls the methods ShowInsert and ShowDelete.
88 : // These are passed the start and end line number.
89 : // Displaying the actually content is to be handled by the subclass!
90 : sal_uLong ShowDiffs( const CompareData& rData );
91 :
92 : virtual void ShowInsert( sal_uLong nStt, sal_uLong nEnd );
93 : virtual void ShowDelete( const CompareData& rData, sal_uLong nStt,
94 : sal_uLong nEnd, sal_uLong nInsPos );
95 : virtual void CheckForChangesInLine( const CompareData& rData,
96 : sal_uLong& nStt, sal_uLong& nEnd,
97 : sal_uLong& nThisStt, sal_uLong& nThisEnd );
98 :
99 : // Set non-ambiguous index for a line. Same lines have the same index, even in the other CompareData!
100 : void SetIndex( size_t nLine, size_t nIndex );
101 0 : size_t GetIndex( size_t nLine ) const
102 0 : { return nLine < aLines.size() ? pIndex[ nLine ] : 0; }
103 :
104 : // Set/get of a line has changed
105 : void SetChanged( size_t nLine, bool bFlag = true );
106 0 : bool GetChanged( size_t nLine ) const
107 : {
108 0 : return (pChangedFlag && nLine < aLines.size())
109 0 : && pChangedFlag[ nLine ];
110 : }
111 :
112 0 : size_t GetLineCount() const { return aLines.size(); }
113 0 : const CompareLine* GetLine( size_t nLine ) const
114 0 : { return aLines[ nLine ]; }
115 0 : void InsertLine( CompareLine* pLine )
116 0 : { aLines.push_back( pLine ); }
117 : };
118 :
119 : class Hash
120 : {
121 : struct _HashData
122 : {
123 : sal_uLong nNext, nHash;
124 : const CompareLine* pLine;
125 :
126 0 : _HashData()
127 0 : : nNext( 0 ), nHash( 0 ), pLine(0) {}
128 : };
129 :
130 : sal_uLong* pHashArr;
131 : _HashData* pDataArr;
132 : sal_uLong nCount, nPrime;
133 :
134 : public:
135 : Hash( sal_uLong nSize );
136 : ~Hash();
137 :
138 : void CalcHashValue( CompareData& rData );
139 :
140 0 : sal_uLong GetCount() const { return nCount; }
141 : };
142 :
143 : class Compare
144 : {
145 : public:
146 : class MovedData
147 : {
148 : sal_uLong* pIndex;
149 : sal_uLong* pLineNum;
150 : sal_uLong nCount;
151 :
152 : public:
153 : MovedData( CompareData& rData, sal_Char* pDiscard );
154 : ~MovedData();
155 :
156 0 : sal_uLong GetIndex( sal_uLong n ) const { return pIndex[ n ]; }
157 0 : sal_uLong GetLineNum( sal_uLong n ) const { return pLineNum[ n ]; }
158 0 : sal_uLong GetCount() const { return nCount; }
159 : };
160 :
161 : private:
162 : /// Look for the moved lines
163 : class CompareSequence
164 : {
165 : CompareData &rData1, &rData2;
166 : const MovedData &rMoved1, &rMoved2;
167 : long *pMemory, *pFDiag, *pBDiag;
168 :
169 : void Compare( sal_uLong nStt1, sal_uLong nEnd1, sal_uLong nStt2, sal_uLong nEnd2 );
170 : sal_uLong CheckDiag( sal_uLong nStt1, sal_uLong nEnd1,
171 : sal_uLong nStt2, sal_uLong nEnd2, sal_uLong* pCost );
172 : public:
173 : CompareSequence( CompareData& rData1, CompareData& rData2,
174 : const MovedData& rD1, const MovedData& rD2 );
175 : ~CompareSequence();
176 : };
177 :
178 : static void CountDifference( const CompareData& rData, sal_uLong* pCounts );
179 : static void SetDiscard( const CompareData& rData,
180 : sal_Char* pDiscard, sal_uLong* pCounts );
181 : static void CheckDiscard( sal_uLong nLen, sal_Char* pDiscard );
182 : static void ShiftBoundaries( CompareData& rData1, CompareData& rData2 );
183 :
184 : public:
185 : Compare( sal_uLong nDiff, CompareData& rData1, CompareData& rData2 );
186 : };
187 :
188 0 : class ArrayComparator
189 : {
190 : public:
191 : virtual bool Compare( int nIdx1, int nIdx2 ) const = 0;
192 : virtual int GetLen1() const = 0;
193 : virtual int GetLen2() const = 0;
194 0 : virtual ~ArrayComparator() {}
195 : };
196 :
197 : /// Consider two lines equal if similar enough (e.g. look like different
198 : /// versions of the same paragraph)
199 0 : class LineArrayComparator : public ArrayComparator
200 : {
201 : private:
202 : int nLen1, nLen2;
203 : const CompareData &rData1, &rData2;
204 : int nFirst1, nFirst2;
205 :
206 : public:
207 : LineArrayComparator( const CompareData &rD1, const CompareData &rD2,
208 : int nStt1, int nEnd1, int nStt2, int nEnd2 );
209 :
210 : virtual bool Compare( int nIdx1, int nIdx2 ) const SAL_OVERRIDE;
211 0 : virtual int GetLen1() const SAL_OVERRIDE { return nLen1; }
212 0 : virtual int GetLen2() const SAL_OVERRIDE { return nLen2; }
213 : };
214 :
215 : class WordArrayComparator : public ArrayComparator
216 : {
217 : private:
218 : const SwTxtNode *pTxtNd1, *pTxtNd2;
219 : int *pPos1, *pPos2;
220 : int nCnt1, nCnt2; // number of words
221 :
222 : void CalcPositions( int *pPos, const SwTxtNode *pTxtNd, int &nCnt );
223 :
224 : public:
225 : WordArrayComparator( const SwTxtNode *pNode1, const SwTxtNode *pNode2 );
226 : virtual ~WordArrayComparator();
227 :
228 : virtual bool Compare( int nIdx1, int nIdx2 ) const SAL_OVERRIDE;
229 0 : virtual int GetLen1() const SAL_OVERRIDE { return nCnt1; }
230 0 : virtual int GetLen2() const SAL_OVERRIDE { return nCnt2; }
231 : int GetCharSequence( const int *pWordLcs1, const int *pWordLcs2,
232 : int *pSubseq1, int *pSubseq2, int nLcsLen );
233 : };
234 :
235 0 : class CharArrayComparator : public ArrayComparator
236 : {
237 : private:
238 : const SwTxtNode *pTxtNd1, *pTxtNd2;
239 :
240 : public:
241 0 : CharArrayComparator( const SwTxtNode *pNode1, const SwTxtNode *pNode2 )
242 0 : : pTxtNd1( pNode1 ), pTxtNd2( pNode2 )
243 : {
244 0 : }
245 :
246 : virtual bool Compare( int nIdx1, int nIdx2 ) const SAL_OVERRIDE;
247 0 : virtual int GetLen1() const SAL_OVERRIDE { return pTxtNd1->GetTxt().getLength(); }
248 0 : virtual int GetLen2() const SAL_OVERRIDE { return pTxtNd2->GetTxt().getLength(); }
249 : };
250 :
251 : /// Options set in Tools->Options->Writer->Comparison
252 : struct CmpOptionsContainer
253 : {
254 : SvxCompareMode eCmpMode;
255 : int nIgnoreLen;
256 : bool bUseRsid;
257 : } CmpOptions;
258 :
259 : class CommonSubseq
260 : {
261 : private:
262 : int *pData;
263 : int nSize;
264 :
265 : protected:
266 : ArrayComparator &rCmp;
267 :
268 0 : CommonSubseq( ArrayComparator &rComparator, int nMaxSize )
269 0 : : nSize( nMaxSize ), rCmp( rComparator )
270 : {
271 0 : pData = new int[ nSize ];
272 0 : }
273 :
274 0 : ~CommonSubseq()
275 : {
276 0 : delete[] pData;
277 0 : }
278 :
279 : int FindLCS( int *pLcs1 = 0, int *pLcs2 = 0, int nStt1 = 0,
280 : int nEnd1 = 0, int nStt2 = 0, int nEnd2 = 0 );
281 :
282 : public:
283 : int IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1, int nLen2,
284 : int nLcsLen, int nPieceLen );
285 : };
286 :
287 : /// Use Hirschberg's algorithm to find LCS in linear space
288 : class LgstCommonSubseq: public CommonSubseq
289 : {
290 : private:
291 : static const int CUTOFF = 1<<20; // Stop recursion at this value
292 :
293 : int *pL1, *pL2;
294 : int *pBuff1, *pBuff2;
295 :
296 : void FindL( int *pL, int nStt1, int nEnd1, int nStt2, int nEnd2 );
297 : int HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1, int nEnd1,
298 : int nStt2, int nEnd2 );
299 :
300 : public:
301 : LgstCommonSubseq( ArrayComparator &rComparator );
302 : ~LgstCommonSubseq();
303 :
304 : int Find( int *pSubseq1, int *pSubseq2 );
305 : };
306 :
307 : /// Find a common subsequence in linear time
308 0 : class FastCommonSubseq: private CommonSubseq
309 : {
310 : private:
311 : static const int CUTOFF = 2056;
312 :
313 : int FindFastCS( int *pSeq1, int *pSeq2, int nStt1, int nEnd1,
314 : int nStt2, int nEnd2 );
315 :
316 : public:
317 0 : FastCommonSubseq( ArrayComparator &rComparator )
318 0 : : CommonSubseq( rComparator, CUTOFF )
319 : {
320 0 : }
321 :
322 0 : int Find( int *pSubseq1, int *pSubseq2 )
323 : {
324 0 : return FindFastCS( pSubseq1, pSubseq2, 0, rCmp.GetLen1(),
325 0 : 0, rCmp.GetLen2() );
326 : }
327 : };
328 :
329 0 : CompareLine::~CompareLine() {}
330 :
331 0 : CompareData::CompareData()
332 0 : : pIndex( 0 ), pChangedFlag( 0 ), nSttLineNum( 0 )
333 : {
334 0 : }
335 :
336 0 : CompareData::~CompareData()
337 : {
338 0 : delete[] pIndex;
339 0 : delete[] pChangedFlag;
340 0 : }
341 :
342 0 : void CompareData::SetIndex( size_t nLine, size_t nIndex )
343 : {
344 0 : if( !pIndex )
345 : {
346 0 : pIndex = new size_t[ aLines.size() ];
347 0 : memset( pIndex, 0, aLines.size() * sizeof( size_t ) );
348 : }
349 0 : if( nLine < aLines.size() )
350 0 : pIndex[ nLine ] = nIndex;
351 0 : }
352 :
353 0 : void CompareData::SetChanged( size_t nLine, bool bFlag )
354 : {
355 0 : if( !pChangedFlag )
356 : {
357 0 : pChangedFlag = new bool[ aLines.size() +1 ];
358 0 : memset( pChangedFlag, 0, (aLines.size() +1) * sizeof( bool ) );
359 : }
360 0 : if( nLine < aLines.size() )
361 0 : pChangedFlag[ nLine ] = bFlag;
362 0 : }
363 :
364 0 : void CompareData::CompareLines( CompareData& rData )
365 : {
366 0 : CheckRanges( rData );
367 :
368 : sal_uLong nDifferent;
369 : {
370 0 : Hash aH( GetLineCount() + rData.GetLineCount() + 1 );
371 0 : aH.CalcHashValue( *this );
372 0 : aH.CalcHashValue( rData );
373 0 : nDifferent = aH.GetCount();
374 : }
375 : {
376 0 : Compare aComp( nDifferent, *this, rData );
377 : }
378 0 : }
379 :
380 0 : sal_uLong CompareData::ShowDiffs( const CompareData& rData )
381 : {
382 0 : sal_uLong nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
383 0 : sal_uLong nStt1 = 0, nStt2 = 0;
384 0 : sal_uLong nCnt = 0;
385 :
386 0 : while( nStt1 < nLen1 || nStt2 < nLen2 )
387 : {
388 0 : if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
389 : {
390 : // Find a region of different lines between two pairs of identical
391 : // lines.
392 0 : sal_uLong nSav1 = nStt1, nSav2 = nStt2;
393 0 : while( nStt1 < nLen1 && rData.GetChanged( nStt1 )) ++nStt1;
394 0 : while( nStt2 < nLen2 && GetChanged( nStt2 )) ++nStt2;
395 :
396 : // Check if there are changed lines (only slightly different) and
397 : // compare them in detail.
398 0 : CheckForChangesInLine( rData, nSav1, nStt1, nSav2, nStt2 );
399 :
400 0 : ++nCnt;
401 : }
402 0 : ++nStt1, ++nStt2;
403 : }
404 0 : return nCnt;
405 : }
406 :
407 0 : bool CompareData::HasDiffs( const CompareData& rData ) const
408 : {
409 0 : bool bRet = false;
410 0 : sal_uLong nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
411 0 : sal_uLong nStt1 = 0, nStt2 = 0;
412 :
413 0 : while( nStt1 < nLen1 || nStt2 < nLen2 )
414 : {
415 0 : if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
416 : {
417 0 : bRet = true;
418 0 : break;
419 : }
420 0 : ++nStt1, ++nStt2;
421 : }
422 0 : return bRet;
423 : }
424 :
425 0 : void CompareData::ShowInsert( sal_uLong, sal_uLong )
426 : {
427 0 : }
428 :
429 0 : void CompareData::ShowDelete( const CompareData&, sal_uLong, sal_uLong, sal_uLong )
430 : {
431 0 : }
432 :
433 0 : void CompareData::CheckForChangesInLine( const CompareData& ,
434 : sal_uLong&, sal_uLong&, sal_uLong&, sal_uLong& )
435 : {
436 0 : }
437 :
438 0 : Hash::Hash( sal_uLong nSize )
439 0 : : nCount(1)
440 : {
441 :
442 : static const sal_uLong primes[] =
443 : {
444 : 509,
445 : 1021,
446 : 2039,
447 : 4093,
448 : 8191,
449 : 16381,
450 : 32749,
451 : 65521,
452 : 131071,
453 : 262139,
454 : 524287,
455 : 1048573,
456 : 2097143,
457 : 4194301,
458 : 8388593,
459 : 16777213,
460 : 33554393,
461 : 67108859, /* Preposterously large . . . */
462 : 134217689,
463 : 268435399,
464 : 536870909,
465 : 1073741789,
466 : 2147483647,
467 : 0
468 : };
469 : int i;
470 :
471 0 : pDataArr = new _HashData[ nSize ];
472 0 : pDataArr[0].nNext = 0;
473 0 : pDataArr[0].nHash = 0,
474 0 : pDataArr[0].pLine = 0;
475 0 : nPrime = primes[0];
476 :
477 0 : for( i = 0; primes[i] < nSize / 3; i++)
478 0 : if( !primes[i] )
479 : {
480 0 : pHashArr = 0;
481 0 : return;
482 : }
483 0 : nPrime = primes[ i ];
484 0 : pHashArr = new sal_uLong[ nPrime ];
485 0 : memset( pHashArr, 0, nPrime * sizeof( sal_uLong ) );
486 : }
487 :
488 0 : Hash::~Hash()
489 : {
490 0 : delete[] pHashArr;
491 0 : delete[] pDataArr;
492 0 : }
493 :
494 0 : void Hash::CalcHashValue( CompareData& rData )
495 : {
496 0 : if( pHashArr )
497 : {
498 0 : for( size_t n = 0; n < rData.GetLineCount(); ++n )
499 : {
500 0 : const CompareLine* pLine = rData.GetLine( n );
501 : OSL_ENSURE( pLine, "where is the line?" );
502 0 : sal_uLong nH = pLine->GetHashValue();
503 :
504 0 : sal_uLong* pFound = &pHashArr[ nH % nPrime ];
505 : size_t i;
506 0 : for( i = *pFound; ; i = pDataArr[i].nNext )
507 0 : if( !i )
508 : {
509 0 : i = nCount++;
510 0 : pDataArr[i].nNext = *pFound;
511 0 : pDataArr[i].nHash = nH;
512 0 : pDataArr[i].pLine = pLine;
513 0 : *pFound = i;
514 0 : break;
515 : }
516 0 : else if( pDataArr[i].nHash == nH &&
517 0 : pDataArr[i].pLine->Compare( *pLine ))
518 0 : break;
519 :
520 0 : rData.SetIndex( n, i );
521 0 : }
522 : }
523 0 : }
524 :
525 0 : Compare::Compare( sal_uLong nDiff, CompareData& rData1, CompareData& rData2 )
526 : {
527 : MovedData *pMD1, *pMD2;
528 : // Look for the differing lines
529 : {
530 0 : sal_Char* pDiscard1 = new sal_Char[ rData1.GetLineCount() ];
531 0 : sal_Char* pDiscard2 = new sal_Char[ rData2.GetLineCount() ];
532 :
533 0 : sal_uLong* pCount1 = new sal_uLong[ nDiff ];
534 0 : sal_uLong* pCount2 = new sal_uLong[ nDiff ];
535 0 : memset( pCount1, 0, nDiff * sizeof( sal_uLong ));
536 0 : memset( pCount2, 0, nDiff * sizeof( sal_uLong ));
537 :
538 : // find indices in CompareData which have been assigned multiple times
539 0 : CountDifference( rData1, pCount1 );
540 0 : CountDifference( rData2, pCount2 );
541 :
542 : // All which occur only once now have either been inserted or deleted.
543 : // All which are also contained in the other one have been moved.
544 0 : SetDiscard( rData1, pDiscard1, pCount2 );
545 0 : SetDiscard( rData2, pDiscard2, pCount1 );
546 :
547 : // forget the arrays again
548 0 : delete [] pCount1; delete [] pCount2;
549 :
550 0 : CheckDiscard( rData1.GetLineCount(), pDiscard1 );
551 0 : CheckDiscard( rData2.GetLineCount(), pDiscard2 );
552 :
553 0 : pMD1 = new MovedData( rData1, pDiscard1 );
554 0 : pMD2 = new MovedData( rData2, pDiscard2 );
555 :
556 : // forget the arrays again
557 0 : delete [] pDiscard1; delete [] pDiscard2;
558 : }
559 :
560 : {
561 0 : CompareSequence aTmp( rData1, rData2, *pMD1, *pMD2 );
562 : }
563 :
564 0 : ShiftBoundaries( rData1, rData2 );
565 :
566 0 : delete pMD1;
567 0 : delete pMD2;
568 0 : }
569 :
570 0 : void Compare::CountDifference( const CompareData& rData, sal_uLong* pCounts )
571 : {
572 0 : sal_uLong nLen = rData.GetLineCount();
573 0 : for( sal_uLong n = 0; n < nLen; ++n )
574 : {
575 0 : sal_uLong nIdx = rData.GetIndex( n );
576 0 : ++pCounts[ nIdx ];
577 : }
578 0 : }
579 :
580 0 : void Compare::SetDiscard( const CompareData& rData,
581 : sal_Char* pDiscard, sal_uLong* pCounts )
582 : {
583 0 : sal_uLong nLen = rData.GetLineCount();
584 :
585 : // calculate Max with respect to the line count
586 0 : sal_uInt16 nMax = 5;
587 : sal_uLong n;
588 :
589 0 : for( n = nLen / 64; ( n = n >> 2 ) > 0; )
590 0 : nMax <<= 1;
591 :
592 0 : for( n = 0; n < nLen; ++n )
593 : {
594 0 : sal_uLong nIdx = rData.GetIndex( n );
595 0 : if( nIdx )
596 : {
597 0 : nIdx = pCounts[ nIdx ];
598 0 : pDiscard[ n ] = !nIdx ? 1 : nIdx > nMax ? 2 : 0;
599 : }
600 : else
601 0 : pDiscard[ n ] = 0;
602 : }
603 0 : }
604 :
605 0 : void Compare::CheckDiscard( sal_uLong nLen, sal_Char* pDiscard )
606 : {
607 0 : for( sal_uLong n = 0; n < nLen; ++n )
608 : {
609 0 : if( 2 == pDiscard[ n ] )
610 0 : pDiscard[n] = 0;
611 0 : else if( pDiscard[ n ] )
612 : {
613 : sal_uLong j;
614 : sal_uLong length;
615 0 : sal_uLong provisional = 0;
616 :
617 : /* Find end of this run of discardable lines.
618 : Count how many are provisionally discardable. */
619 0 : for (j = n; j < nLen; j++)
620 : {
621 0 : if( !pDiscard[j] )
622 0 : break;
623 0 : if( 2 == pDiscard[j] )
624 0 : ++provisional;
625 : }
626 :
627 : /* Cancel provisional discards at end, and shrink the run. */
628 0 : while( j > n && 2 == pDiscard[j - 1] )
629 0 : pDiscard[ --j ] = 0, --provisional;
630 :
631 : /* Now we have the length of a run of discardable lines
632 : whose first and last are not provisional. */
633 0 : length = j - n;
634 :
635 : /* If 1/4 of the lines in the run are provisional,
636 : cancel discarding of all provisional lines in the run. */
637 0 : if (provisional * 4 > length)
638 : {
639 0 : while (j > n)
640 0 : if (pDiscard[--j] == 2)
641 0 : pDiscard[j] = 0;
642 : }
643 : else
644 : {
645 : sal_uLong consec;
646 0 : sal_uLong minimum = 1;
647 0 : sal_uLong tem = length / 4;
648 :
649 : /* MINIMUM is approximate square root of LENGTH/4.
650 : A subrun of two or more provisionals can stand
651 : when LENGTH is at least 16.
652 : A subrun of 4 or more can stand when LENGTH >= 64. */
653 0 : while ((tem = tem >> 2) > 0)
654 0 : minimum *= 2;
655 0 : minimum++;
656 :
657 : /* Cancel any subrun of MINIMUM or more provisionals
658 : within the larger run. */
659 0 : for (j = 0, consec = 0; j < length; j++)
660 0 : if (pDiscard[n + j] != 2)
661 0 : consec = 0;
662 0 : else if (minimum == ++consec)
663 : /* Back up to start of subrun, to cancel it all. */
664 0 : j -= consec;
665 0 : else if (minimum < consec)
666 0 : pDiscard[n + j] = 0;
667 :
668 : /* Scan from beginning of run
669 : until we find 3 or more nonprovisionals in a row
670 : or until the first nonprovisional at least 8 lines in.
671 : Until that point, cancel any provisionals. */
672 0 : for (j = 0, consec = 0; j < length; j++)
673 : {
674 0 : if (j >= 8 && pDiscard[n + j] == 1)
675 0 : break;
676 0 : if (pDiscard[n + j] == 2)
677 0 : consec = 0, pDiscard[n + j] = 0;
678 0 : else if (pDiscard[n + j] == 0)
679 0 : consec = 0;
680 : else
681 0 : consec++;
682 0 : if (consec == 3)
683 0 : break;
684 : }
685 :
686 : /* I advances to the last line of the run. */
687 0 : n += length - 1;
688 :
689 : /* Same thing, from end. */
690 0 : for (j = 0, consec = 0; j < length; j++)
691 : {
692 0 : if (j >= 8 && pDiscard[n - j] == 1)
693 0 : break;
694 0 : if (pDiscard[n - j] == 2)
695 0 : consec = 0, pDiscard[n - j] = 0;
696 0 : else if (pDiscard[n - j] == 0)
697 0 : consec = 0;
698 : else
699 0 : consec++;
700 0 : if (consec == 3)
701 0 : break;
702 : }
703 : }
704 : }
705 : }
706 0 : }
707 :
708 0 : Compare::MovedData::MovedData( CompareData& rData, sal_Char* pDiscard )
709 0 : : pIndex( 0 ), pLineNum( 0 ), nCount( 0 )
710 : {
711 0 : sal_uLong nLen = rData.GetLineCount();
712 : sal_uLong n;
713 :
714 0 : for( n = 0; n < nLen; ++n )
715 0 : if( pDiscard[ n ] )
716 0 : rData.SetChanged( n );
717 : else
718 0 : ++nCount;
719 :
720 0 : if( nCount )
721 : {
722 0 : pIndex = new sal_uLong[ nCount ];
723 0 : pLineNum = new sal_uLong[ nCount ];
724 :
725 0 : for( n = 0, nCount = 0; n < nLen; ++n )
726 0 : if( !pDiscard[ n ] )
727 : {
728 0 : pIndex[ nCount ] = rData.GetIndex( n );
729 0 : pLineNum[ nCount++ ] = n;
730 : }
731 : }
732 0 : }
733 :
734 0 : Compare::MovedData::~MovedData()
735 : {
736 0 : delete [] pIndex;
737 0 : delete [] pLineNum;
738 0 : }
739 :
740 : /// Find the differing lines
741 0 : Compare::CompareSequence::CompareSequence(
742 : CompareData& rD1, CompareData& rD2,
743 : const MovedData& rMD1, const MovedData& rMD2 )
744 0 : : rData1( rD1 ), rData2( rD2 ), rMoved1( rMD1 ), rMoved2( rMD2 )
745 : {
746 0 : sal_uLong nSize = rMD1.GetCount() + rMD2.GetCount() + 3;
747 0 : pMemory = new long[ nSize * 2 ];
748 0 : pFDiag = pMemory + ( rMD2.GetCount() + 1 );
749 0 : pBDiag = pMemory + ( nSize + rMD2.GetCount() + 1 );
750 :
751 0 : Compare( 0, rMD1.GetCount(), 0, rMD2.GetCount() );
752 0 : }
753 :
754 0 : Compare::CompareSequence::~CompareSequence()
755 : {
756 0 : delete [] pMemory;
757 0 : }
758 :
759 0 : void Compare::CompareSequence::Compare( sal_uLong nStt1, sal_uLong nEnd1,
760 : sal_uLong nStt2, sal_uLong nEnd2 )
761 : {
762 : /* Slide down the bottom initial diagonal. */
763 0 : while( nStt1 < nEnd1 && nStt2 < nEnd2 &&
764 0 : rMoved1.GetIndex( nStt1 ) == rMoved2.GetIndex( nStt2 ))
765 0 : ++nStt1, ++nStt2;
766 :
767 : /* Slide up the top initial diagonal. */
768 0 : while( nEnd1 > nStt1 && nEnd2 > nStt2 &&
769 0 : rMoved1.GetIndex( nEnd1 - 1 ) == rMoved2.GetIndex( nEnd2 - 1 ))
770 0 : --nEnd1, --nEnd2;
771 :
772 : /* Handle simple cases. */
773 0 : if( nStt1 == nEnd1 )
774 0 : while( nStt2 < nEnd2 )
775 0 : rData2.SetChanged( rMoved2.GetLineNum( nStt2++ ));
776 :
777 0 : else if (nStt2 == nEnd2)
778 0 : while (nStt1 < nEnd1)
779 0 : rData1.SetChanged( rMoved1.GetLineNum( nStt1++ ));
780 :
781 : else
782 : {
783 : sal_uLong c, d, b;
784 :
785 : /* Find a point of correspondence in the middle of the files. */
786 :
787 0 : d = CheckDiag( nStt1, nEnd1, nStt2, nEnd2, &c );
788 0 : b = pBDiag[ d ];
789 :
790 0 : if( 1 != c )
791 : {
792 : /* Use that point to split this problem into two subproblems. */
793 0 : Compare( nStt1, b, nStt2, b - d );
794 : /* This used to use f instead of b,
795 : but that is incorrect!
796 : It is not necessarily the case that diagonal d
797 : has a snake from b to f. */
798 0 : Compare( b, nEnd1, b - d, nEnd2 );
799 : }
800 : }
801 0 : }
802 :
803 0 : sal_uLong Compare::CompareSequence::CheckDiag( sal_uLong nStt1, sal_uLong nEnd1,
804 : sal_uLong nStt2, sal_uLong nEnd2, sal_uLong* pCost )
805 : {
806 0 : const long dmin = nStt1 - nEnd2; /* Minimum valid diagonal. */
807 0 : const long dmax = nEnd1 - nStt2; /* Maximum valid diagonal. */
808 0 : const long fmid = nStt1 - nStt2; /* Center diagonal of top-down search. */
809 0 : const long bmid = nEnd1 - nEnd2; /* Center diagonal of bottom-up search. */
810 :
811 0 : long fmin = fmid, fmax = fmid; /* Limits of top-down search. */
812 0 : long bmin = bmid, bmax = bmid; /* Limits of bottom-up search. */
813 :
814 : long c; /* Cost. */
815 0 : long odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
816 : diagonal with respect to the northwest. */
817 :
818 0 : pFDiag[fmid] = nStt1;
819 0 : pBDiag[bmid] = nEnd1;
820 :
821 0 : for (c = 1;; ++c)
822 : {
823 : long d; /* Active diagonal. */
824 :
825 : /* Extend the top-down search by an edit step in each diagonal. */
826 0 : fmin > dmin ? pFDiag[--fmin - 1] = -1 : ++fmin;
827 0 : fmax < dmax ? pFDiag[++fmax + 1] = -1 : --fmax;
828 0 : for (d = fmax; d >= fmin; d -= 2)
829 : {
830 0 : long x, y, tlo = pFDiag[d - 1], thi = pFDiag[d + 1];
831 :
832 0 : if (tlo >= thi)
833 0 : x = tlo + 1;
834 : else
835 0 : x = thi;
836 0 : y = x - d;
837 0 : while( sal_uLong(x) < nEnd1 && sal_uLong(y) < nEnd2 &&
838 0 : rMoved1.GetIndex( x ) == rMoved2.GetIndex( y ))
839 0 : ++x, ++y;
840 0 : pFDiag[d] = x;
841 0 : if( odd && bmin <= d && d <= bmax && pBDiag[d] <= pFDiag[d] )
842 : {
843 0 : *pCost = 2 * c - 1;
844 0 : return d;
845 : }
846 : }
847 :
848 : /* Similar extend the bottom-up search. */
849 0 : bmin > dmin ? pBDiag[--bmin - 1] = INT_MAX : ++bmin;
850 0 : bmax < dmax ? pBDiag[++bmax + 1] = INT_MAX : --bmax;
851 0 : for (d = bmax; d >= bmin; d -= 2)
852 : {
853 0 : long x, y, tlo = pBDiag[d - 1], thi = pBDiag[d + 1];
854 :
855 0 : if (tlo < thi)
856 0 : x = tlo;
857 : else
858 0 : x = thi - 1;
859 0 : y = x - d;
860 0 : while( sal_uLong(x) > nStt1 && sal_uLong(y) > nStt2 &&
861 0 : rMoved1.GetIndex( x - 1 ) == rMoved2.GetIndex( y - 1 ))
862 0 : --x, --y;
863 0 : pBDiag[d] = x;
864 0 : if (!odd && fmin <= d && d <= fmax && pBDiag[d] <= pFDiag[d])
865 : {
866 0 : *pCost = 2 * c;
867 0 : return d;
868 : }
869 : }
870 0 : }
871 : }
872 :
873 0 : void Compare::ShiftBoundaries( CompareData& rData1, CompareData& rData2 )
874 : {
875 0 : for( int iz = 0; iz < 2; ++iz )
876 : {
877 0 : CompareData* pData = &rData1;
878 0 : CompareData* pOtherData = &rData2;
879 :
880 0 : sal_uLong i = 0;
881 0 : sal_uLong j = 0;
882 0 : sal_uLong i_end = pData->GetLineCount();
883 0 : sal_uLong preceding = ULONG_MAX;
884 0 : sal_uLong other_preceding = ULONG_MAX;
885 :
886 : while (true)
887 : {
888 : sal_uLong start, other_start;
889 :
890 : /* Scan forwards to find beginning of another run of changes.
891 : Also keep track of the corresponding point in the other file. */
892 :
893 0 : while( i < i_end && !pData->GetChanged( i ) )
894 : {
895 0 : while( pOtherData->GetChanged( j++ ))
896 : /* Non-corresponding lines in the other file
897 : will count as the preceding batch of changes. */
898 0 : other_preceding = j;
899 0 : i++;
900 : }
901 :
902 0 : if (i == i_end)
903 0 : break;
904 :
905 0 : start = i;
906 0 : other_start = j;
907 :
908 : while (true)
909 : {
910 : /* Now find the end of this run of changes. */
911 :
912 0 : while( pData->GetChanged( ++i ))
913 : ;
914 :
915 : /* If the first changed line matches the following unchanged one,
916 : and this run does not follow right after a previous run,
917 : and there are no lines deleted from the other file here,
918 : then classify the first changed line as unchanged
919 : and the following line as changed in its place. */
920 :
921 : /* You might ask, how could this run follow right after another?
922 : Only because the previous run was shifted here. */
923 :
924 0 : if( i != i_end &&
925 0 : pData->GetIndex( start ) == pData->GetIndex( i ) &&
926 0 : !pOtherData->GetChanged( j ) &&
927 0 : !( start == preceding || other_start == other_preceding ))
928 : {
929 0 : pData->SetChanged( start++, false );
930 0 : pData->SetChanged( i );
931 : /* Since one line-that-matches is now before this run
932 : instead of after, we must advance in the other file
933 : to keep in sync. */
934 0 : ++j;
935 : }
936 : else
937 0 : break;
938 : }
939 :
940 0 : preceding = i;
941 0 : other_preceding = j;
942 0 : }
943 :
944 0 : pData = &rData2;
945 0 : pOtherData = &rData1;
946 0 : }
947 0 : }
948 :
949 : class SwCompareLine : public CompareLine
950 : {
951 : const SwNode& rNode;
952 : public:
953 : SwCompareLine( const SwNode& rNd );
954 : virtual ~SwCompareLine();
955 :
956 : virtual sal_uLong GetHashValue() const SAL_OVERRIDE;
957 : virtual bool Compare( const CompareLine& rLine ) const SAL_OVERRIDE;
958 :
959 : static sal_uLong GetTxtNodeHashValue( const SwTxtNode& rNd, sal_uLong nVal );
960 : static bool CompareNode( const SwNode& rDstNd, const SwNode& rSrcNd );
961 : static bool CompareTxtNd( const SwTxtNode& rDstNd,
962 : const SwTxtNode& rSrcNd );
963 :
964 : bool ChangesInLine( const SwCompareLine& rLine,
965 : SwPaM *& rpInsRing, SwPaM*& rpDelRing ) const;
966 :
967 0 : const SwNode& GetNode() const { return rNode; }
968 :
969 : const SwNode& GetEndNode() const;
970 :
971 : // for debugging
972 : OUString GetText() const;
973 : };
974 :
975 : class SwCompareData : public CompareData
976 : {
977 : SwDoc& rDoc;
978 : SwPaM *pInsRing, *pDelRing;
979 :
980 : sal_uLong PrevIdx( const SwNode* pNd );
981 : sal_uLong NextIdx( const SwNode* pNd );
982 :
983 : virtual void CheckRanges( CompareData& ) SAL_OVERRIDE;
984 : virtual void ShowInsert( sal_uLong nStt, sal_uLong nEnd ) SAL_OVERRIDE;
985 : virtual void ShowDelete( const CompareData& rData, sal_uLong nStt,
986 : sal_uLong nEnd, sal_uLong nInsPos ) SAL_OVERRIDE;
987 :
988 : virtual void CheckForChangesInLine( const CompareData& rData,
989 : sal_uLong& nStt, sal_uLong& nEnd,
990 : sal_uLong& nThisStt, sal_uLong& nThisEnd ) SAL_OVERRIDE;
991 :
992 : public:
993 0 : SwCompareData( SwDoc& rD ) : rDoc( rD ), pInsRing(0), pDelRing(0) {}
994 : virtual ~SwCompareData();
995 :
996 : void SetRedlinesToDoc( bool bUseDocInfo );
997 : };
998 :
999 0 : SwCompareLine::SwCompareLine( const SwNode& rNd )
1000 0 : : rNode( rNd )
1001 : {
1002 0 : }
1003 :
1004 0 : SwCompareLine::~SwCompareLine()
1005 : {
1006 0 : }
1007 :
1008 0 : sal_uLong SwCompareLine::GetHashValue() const
1009 : {
1010 0 : sal_uLong nRet = 0;
1011 0 : switch( rNode.GetNodeType() )
1012 : {
1013 : case ND_TEXTNODE:
1014 0 : nRet = GetTxtNodeHashValue( (SwTxtNode&)rNode, nRet );
1015 0 : break;
1016 :
1017 : case ND_TABLENODE:
1018 : {
1019 0 : const SwNode* pEndNd = rNode.EndOfSectionNode();
1020 0 : SwNodeIndex aIdx( rNode );
1021 0 : while( &aIdx.GetNode() != pEndNd )
1022 : {
1023 0 : if( aIdx.GetNode().IsTxtNode() )
1024 0 : nRet = GetTxtNodeHashValue( (SwTxtNode&)aIdx.GetNode(), nRet );
1025 0 : ++aIdx;
1026 0 : }
1027 : }
1028 0 : break;
1029 :
1030 : case ND_SECTIONNODE:
1031 : {
1032 0 : OUString sStr( GetText() );
1033 0 : for( sal_Int32 n = 0; n < sStr.getLength(); ++n )
1034 0 : ( nRet <<= 1 ) += sStr[ n ];
1035 : }
1036 0 : break;
1037 :
1038 : case ND_GRFNODE:
1039 : case ND_OLENODE:
1040 : // Fixed ID? Should never occur ...
1041 0 : break;
1042 : }
1043 0 : return nRet;
1044 : }
1045 :
1046 0 : const SwNode& SwCompareLine::GetEndNode() const
1047 : {
1048 0 : const SwNode* pNd = &rNode;
1049 0 : switch( rNode.GetNodeType() )
1050 : {
1051 : case ND_TABLENODE:
1052 0 : pNd = rNode.EndOfSectionNode();
1053 0 : break;
1054 :
1055 : case ND_SECTIONNODE:
1056 : {
1057 0 : const SwSectionNode& rSNd = (SwSectionNode&)rNode;
1058 0 : const SwSection& rSect = rSNd.GetSection();
1059 0 : if( CONTENT_SECTION != rSect.GetType() || rSect.IsProtect() )
1060 0 : pNd = rNode.EndOfSectionNode();
1061 : }
1062 0 : break;
1063 : }
1064 0 : return *pNd;
1065 : }
1066 :
1067 0 : bool SwCompareLine::Compare( const CompareLine& rLine ) const
1068 : {
1069 0 : return CompareNode( rNode, ((SwCompareLine&)rLine).rNode );
1070 : }
1071 :
1072 : namespace
1073 : {
1074 0 : static OUString SimpleTableToText(const SwNode &rNode)
1075 : {
1076 0 : OUStringBuffer sRet;
1077 0 : const SwNode* pEndNd = rNode.EndOfSectionNode();
1078 0 : SwNodeIndex aIdx( rNode );
1079 0 : while (&aIdx.GetNode() != pEndNd)
1080 : {
1081 0 : if (aIdx.GetNode().IsTxtNode())
1082 : {
1083 0 : if (sRet.getLength())
1084 : {
1085 0 : sRet.append( '\n' );
1086 : }
1087 0 : sRet.append( aIdx.GetNode().GetTxtNode()->GetExpandTxt() );
1088 : }
1089 0 : ++aIdx;
1090 : }
1091 0 : return sRet.makeStringAndClear();
1092 : }
1093 : }
1094 :
1095 0 : bool SwCompareLine::CompareNode( const SwNode& rDstNd, const SwNode& rSrcNd )
1096 : {
1097 0 : if( rSrcNd.GetNodeType() != rDstNd.GetNodeType() )
1098 0 : return false;
1099 :
1100 0 : bool bRet = false;
1101 :
1102 0 : switch( rDstNd.GetNodeType() )
1103 : {
1104 : case ND_TEXTNODE:
1105 0 : bRet = CompareTxtNd( (SwTxtNode&)rDstNd, (SwTxtNode&)rSrcNd )
1106 0 : && ( !CmpOptions.bUseRsid || ((SwTxtNode&)rDstNd).CompareParRsid( (SwTxtNode&)rSrcNd ) );
1107 0 : break;
1108 :
1109 : case ND_TABLENODE:
1110 : {
1111 0 : const SwTableNode& rTSrcNd = (SwTableNode&)rSrcNd;
1112 0 : const SwTableNode& rTDstNd = (SwTableNode&)rDstNd;
1113 :
1114 0 : bRet = ( rTSrcNd.EndOfSectionIndex() - rTSrcNd.GetIndex() ) ==
1115 0 : ( rTDstNd.EndOfSectionIndex() - rTDstNd.GetIndex() );
1116 :
1117 : // --> #i107826#: compare actual table content
1118 0 : if (bRet)
1119 : {
1120 0 : bRet = (SimpleTableToText(rSrcNd) == SimpleTableToText(rDstNd));
1121 : }
1122 : }
1123 0 : break;
1124 :
1125 : case ND_SECTIONNODE:
1126 : {
1127 0 : const SwSectionNode& rSSrcNd = (SwSectionNode&)rSrcNd,
1128 0 : & rSDstNd = (SwSectionNode&)rDstNd;
1129 0 : const SwSection& rSrcSect = rSSrcNd.GetSection(),
1130 0 : & rDstSect = rSDstNd.GetSection();
1131 0 : SectionType eSrcSectType = rSrcSect.GetType(),
1132 0 : eDstSectType = rDstSect.GetType();
1133 0 : switch( eSrcSectType )
1134 : {
1135 : case CONTENT_SECTION:
1136 0 : bRet = CONTENT_SECTION == eDstSectType &&
1137 0 : rSrcSect.IsProtect() == rDstSect.IsProtect();
1138 0 : if( bRet && rSrcSect.IsProtect() )
1139 : {
1140 : // the only have they both the same size
1141 0 : bRet = ( rSSrcNd.EndOfSectionIndex() - rSSrcNd.GetIndex() ) ==
1142 0 : ( rSDstNd.EndOfSectionIndex() - rSDstNd.GetIndex() );
1143 : }
1144 0 : break;
1145 :
1146 : case TOX_HEADER_SECTION:
1147 : case TOX_CONTENT_SECTION:
1148 0 : if( TOX_HEADER_SECTION == eDstSectType ||
1149 : TOX_CONTENT_SECTION == eDstSectType )
1150 : {
1151 : // the same type of TOX?
1152 0 : const SwTOXBase* pSrcTOX = rSrcSect.GetTOXBase();
1153 0 : const SwTOXBase* pDstTOX = rDstSect.GetTOXBase();
1154 0 : bRet = pSrcTOX && pDstTOX
1155 0 : && pSrcTOX->GetType() == pDstTOX->GetType()
1156 0 : && pSrcTOX->GetTitle() == pDstTOX->GetTitle()
1157 0 : && pSrcTOX->GetTypeName() == pDstTOX->GetTypeName()
1158 0 : ;
1159 : }
1160 0 : break;
1161 :
1162 : case DDE_LINK_SECTION:
1163 : case FILE_LINK_SECTION:
1164 0 : bRet = eSrcSectType == eDstSectType &&
1165 0 : rSrcSect.GetLinkFileName() ==
1166 0 : rDstSect.GetLinkFileName();
1167 0 : break;
1168 : }
1169 : }
1170 0 : break;
1171 :
1172 : case ND_ENDNODE:
1173 0 : bRet = rSrcNd.StartOfSectionNode()->GetNodeType() ==
1174 0 : rDstNd.StartOfSectionNode()->GetNodeType();
1175 :
1176 : // --> #i107826#: compare actual table content
1177 0 : if (bRet && rSrcNd.StartOfSectionNode()->GetNodeType() == ND_TABLENODE)
1178 : {
1179 : bRet = CompareNode(
1180 0 : *rSrcNd.StartOfSectionNode(), *rDstNd.StartOfSectionNode());
1181 : }
1182 :
1183 0 : break;
1184 : }
1185 0 : return bRet;
1186 : }
1187 :
1188 0 : OUString SwCompareLine::GetText() const
1189 : {
1190 0 : OUString sRet;
1191 0 : switch( rNode.GetNodeType() )
1192 : {
1193 : case ND_TEXTNODE:
1194 0 : sRet = ((SwTxtNode&)rNode).GetExpandTxt();
1195 0 : break;
1196 :
1197 : case ND_TABLENODE:
1198 : {
1199 0 : sRet = "Tabelle: " + SimpleTableToText(rNode);
1200 : }
1201 0 : break;
1202 :
1203 : case ND_SECTIONNODE:
1204 : {
1205 0 : sRet = "Section - Node:";
1206 :
1207 0 : const SwSectionNode& rSNd = (SwSectionNode&)rNode;
1208 0 : const SwSection& rSect = rSNd.GetSection();
1209 0 : switch( rSect.GetType() )
1210 : {
1211 : case CONTENT_SECTION:
1212 0 : if( rSect.IsProtect() )
1213 0 : sRet += OUString::number(
1214 0 : rSNd.EndOfSectionIndex() - rSNd.GetIndex() );
1215 0 : break;
1216 :
1217 : case TOX_HEADER_SECTION:
1218 : case TOX_CONTENT_SECTION:
1219 : {
1220 0 : const SwTOXBase* pTOX = rSect.GetTOXBase();
1221 0 : if( pTOX )
1222 0 : sRet += pTOX->GetTitle() + pTOX->GetTypeName() +
1223 0 : OUString::number(pTOX->GetType());
1224 : }
1225 0 : break;
1226 :
1227 : case DDE_LINK_SECTION:
1228 : case FILE_LINK_SECTION:
1229 0 : sRet += rSect.GetLinkFileName();
1230 0 : break;
1231 : }
1232 : }
1233 0 : break;
1234 :
1235 : case ND_GRFNODE:
1236 0 : sRet = "Grafik - Node:";
1237 0 : break;
1238 : case ND_OLENODE:
1239 0 : sRet = "OLE - Node:";
1240 0 : break;
1241 : }
1242 0 : return sRet;
1243 : }
1244 :
1245 0 : sal_uLong SwCompareLine::GetTxtNodeHashValue( const SwTxtNode& rNd, sal_uLong nVal )
1246 : {
1247 0 : OUString sStr( rNd.GetExpandTxt() );
1248 0 : for( sal_Int32 n = 0; n < sStr.getLength(); ++n )
1249 0 : ( nVal <<= 1 ) += sStr[ n ];
1250 0 : return nVal;
1251 : }
1252 :
1253 0 : bool SwCompareLine::CompareTxtNd( const SwTxtNode& rDstNd,
1254 : const SwTxtNode& rSrcNd )
1255 : {
1256 0 : bool bRet = false;
1257 : // Very simple at first
1258 0 : if( rDstNd.GetTxt() == rSrcNd.GetTxt() )
1259 : {
1260 : // The text is the same, but are the "special attributes" (0xFF) also the same?
1261 0 : bRet = true;
1262 : }
1263 0 : return bRet;
1264 : }
1265 :
1266 0 : bool SwCompareLine::ChangesInLine( const SwCompareLine& rLine,
1267 : SwPaM *& rpInsRing, SwPaM*& rpDelRing ) const
1268 : {
1269 0 : bool bRet = false;
1270 :
1271 : // Only compare textnodes
1272 0 : if( ND_TEXTNODE == rNode.GetNodeType() &&
1273 0 : ND_TEXTNODE == rLine.GetNode().GetNodeType() )
1274 : {
1275 0 : SwTxtNode& rDstNd = *(SwTxtNode*)rNode.GetTxtNode();
1276 0 : const SwTxtNode& rSrcNd = *rLine.GetNode().GetTxtNode();
1277 0 : SwDoc* pDstDoc = rDstNd.GetDoc();
1278 :
1279 0 : int nLcsLen = 0;
1280 :
1281 0 : int nDstLen = rDstNd.GetTxt().getLength();
1282 0 : int nSrcLen = rSrcNd.GetTxt().getLength();
1283 :
1284 0 : int nMinLen = std::min( nDstLen , nSrcLen );
1285 0 : int nAvgLen = ( nDstLen + nSrcLen )/2;
1286 :
1287 0 : std::vector<int> aLcsDst( nMinLen + 1 );
1288 0 : std::vector<int> aLcsSrc( nMinLen + 1 );
1289 :
1290 0 : if( CmpOptions.eCmpMode == SVX_CMP_BY_WORD )
1291 : {
1292 0 : std::vector<int> aTmpLcsDst( nMinLen + 1 );
1293 0 : std::vector<int> aTmpLcsSrc( nMinLen + 1 );
1294 :
1295 0 : WordArrayComparator aCmp( &rDstNd, &rSrcNd );
1296 :
1297 0 : LgstCommonSubseq aSeq( aCmp );
1298 :
1299 0 : nLcsLen = aSeq.Find( &aTmpLcsDst[0], &aTmpLcsSrc[0] );
1300 :
1301 0 : if( CmpOptions.nIgnoreLen )
1302 : {
1303 0 : nLcsLen = aSeq.IgnoreIsolatedPieces( &aTmpLcsDst[0], &aTmpLcsSrc[0],
1304 : aCmp.GetLen1(), aCmp.GetLen2(),
1305 0 : nLcsLen, CmpOptions.nIgnoreLen );
1306 : }
1307 :
1308 0 : nLcsLen = aCmp.GetCharSequence( &aTmpLcsDst[0], &aTmpLcsSrc[0],
1309 0 : &aLcsDst[0], &aLcsSrc[0], nLcsLen );
1310 : }
1311 : else
1312 : {
1313 0 : CharArrayComparator aCmp( &rDstNd, &rSrcNd );
1314 0 : LgstCommonSubseq aSeq( aCmp );
1315 :
1316 0 : nLcsLen = aSeq.Find( &aLcsDst[0], &aLcsSrc[0] );
1317 :
1318 0 : if( CmpOptions.nIgnoreLen )
1319 : {
1320 0 : nLcsLen = aSeq.IgnoreIsolatedPieces( &aLcsDst[0], &aLcsSrc[0], nDstLen,
1321 : nSrcLen, nLcsLen,
1322 0 : CmpOptions.nIgnoreLen );
1323 0 : }
1324 : }
1325 :
1326 : // find the sum of the squares of the continuous substrings
1327 0 : int nSqSum = 0;
1328 0 : int nCnt = 1;
1329 0 : for( int i = 0; i < nLcsLen; i++ )
1330 : {
1331 0 : if( i != nLcsLen - 1 && aLcsDst[i] + 1 == aLcsDst[i + 1]
1332 0 : && aLcsSrc[i] + 1 == aLcsSrc[i + 1] )
1333 : {
1334 0 : nCnt++;
1335 : }
1336 : else
1337 : {
1338 0 : nSqSum += nCnt*nCnt;
1339 0 : nCnt = 1;
1340 : }
1341 : }
1342 :
1343 : // Don't compare if there aren't enough similarities
1344 0 : if ( nAvgLen >= 8 && nSqSum*32 < nAvgLen*nAvgLen )
1345 : {
1346 0 : return false;
1347 : }
1348 :
1349 : // Show the differences
1350 0 : int nSkip = 0;
1351 0 : for( int i = 0; i <= nLcsLen; i++ )
1352 : {
1353 0 : int nDstFrom = i ? (aLcsDst[i - 1] + 1) : 0;
1354 0 : int nDstTo = ( i == nLcsLen ) ? nDstLen : aLcsDst[i];
1355 0 : int nSrcFrom = i ? (aLcsSrc[i - 1] + 1) : 0;
1356 0 : int nSrcTo = ( i == nLcsLen ) ? nSrcLen : aLcsSrc[i];
1357 :
1358 0 : SwPaM aPam( rDstNd, nDstTo + nSkip );
1359 :
1360 0 : if ( nDstFrom < nDstTo )
1361 : {
1362 0 : SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpInsRing );
1363 0 : if( !rpInsRing )
1364 0 : rpInsRing = pTmp;
1365 0 : pTmp->SetMark();
1366 0 : pTmp->GetMark()->nContent = nDstFrom + nSkip;
1367 : }
1368 :
1369 0 : if ( nSrcFrom < nSrcTo )
1370 : {
1371 0 : bool bUndo = pDstDoc->GetIDocumentUndoRedo().DoesUndo();
1372 0 : pDstDoc->GetIDocumentUndoRedo().DoUndo( false );
1373 0 : SwPaM aCpyPam( rSrcNd, nSrcFrom );
1374 0 : aCpyPam.SetMark();
1375 0 : aCpyPam.GetPoint()->nContent = nSrcTo;
1376 0 : aCpyPam.GetDoc()->getIDocumentContentOperations().CopyRange( aCpyPam, *aPam.GetPoint(),
1377 0 : false );
1378 0 : pDstDoc->GetIDocumentUndoRedo().DoUndo( bUndo );
1379 :
1380 0 : SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpDelRing );
1381 0 : if( !rpDelRing )
1382 0 : rpDelRing = pTmp;
1383 :
1384 0 : pTmp->SetMark();
1385 0 : pTmp->GetMark()->nContent = nDstTo + nSkip;
1386 0 : nSkip += nSrcTo - nSrcFrom;
1387 :
1388 0 : if( rpInsRing )
1389 : {
1390 0 : SwPaM* pCorr = (SwPaM*)rpInsRing->GetPrev();
1391 0 : if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1392 0 : *pCorr->GetPoint() = *pTmp->GetMark();
1393 0 : }
1394 : }
1395 0 : }
1396 :
1397 0 : bRet = true;
1398 : }
1399 :
1400 0 : return bRet;
1401 : }
1402 :
1403 0 : SwCompareData::~SwCompareData()
1404 : {
1405 0 : if( pDelRing )
1406 : {
1407 0 : while( pDelRing->GetNext() != pDelRing )
1408 0 : delete pDelRing->GetNext();
1409 0 : delete pDelRing;
1410 : }
1411 0 : if( pInsRing )
1412 : {
1413 0 : while( pInsRing->GetNext() != pInsRing )
1414 0 : delete pInsRing->GetNext();
1415 0 : delete pInsRing;
1416 : }
1417 0 : }
1418 :
1419 0 : sal_uLong SwCompareData::NextIdx( const SwNode* pNd )
1420 : {
1421 0 : if( pNd->IsStartNode() )
1422 : {
1423 : const SwSectionNode* pSNd;
1424 0 : if( pNd->IsTableNode() ||
1425 0 : ( 0 != (pSNd = pNd->GetSectionNode() ) &&
1426 0 : ( CONTENT_SECTION != pSNd->GetSection().GetType() ||
1427 0 : pSNd->GetSection().IsProtect() ) ) )
1428 0 : pNd = pNd->EndOfSectionNode();
1429 : }
1430 0 : return pNd->GetIndex() + 1;
1431 : }
1432 :
1433 0 : sal_uLong SwCompareData::PrevIdx( const SwNode* pNd )
1434 : {
1435 0 : if( pNd->IsEndNode() )
1436 : {
1437 : const SwSectionNode* pSNd;
1438 0 : if( pNd->StartOfSectionNode()->IsTableNode() ||
1439 0 : ( 0 != (pSNd = pNd->StartOfSectionNode()->GetSectionNode() ) &&
1440 0 : ( CONTENT_SECTION != pSNd->GetSection().GetType() ||
1441 0 : pSNd->GetSection().IsProtect() ) ) )
1442 0 : pNd = pNd->StartOfSectionNode();
1443 : }
1444 0 : return pNd->GetIndex() - 1;
1445 : }
1446 :
1447 0 : void SwCompareData::CheckRanges( CompareData& rData )
1448 : {
1449 0 : const SwNodes& rSrcNds = ((SwCompareData&)rData).rDoc.GetNodes();
1450 0 : const SwNodes& rDstNds = rDoc.GetNodes();
1451 :
1452 0 : const SwNode& rSrcEndNd = rSrcNds.GetEndOfContent();
1453 0 : const SwNode& rDstEndNd = rDstNds.GetEndOfContent();
1454 :
1455 0 : sal_uLong nSrcSttIdx = NextIdx( rSrcEndNd.StartOfSectionNode() );
1456 0 : sal_uLong nSrcEndIdx = rSrcEndNd.GetIndex();
1457 :
1458 0 : sal_uLong nDstSttIdx = NextIdx( rDstEndNd.StartOfSectionNode() );
1459 0 : sal_uLong nDstEndIdx = rDstEndNd.GetIndex();
1460 :
1461 0 : while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1462 : {
1463 0 : const SwNode* pSrcNd = rSrcNds[ nSrcSttIdx ];
1464 0 : const SwNode* pDstNd = rDstNds[ nDstSttIdx ];
1465 0 : if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1466 0 : break;
1467 :
1468 0 : nSrcSttIdx = NextIdx( pSrcNd );
1469 0 : nDstSttIdx = NextIdx( pDstNd );
1470 : }
1471 :
1472 0 : nSrcEndIdx = PrevIdx( &rSrcEndNd );
1473 0 : nDstEndIdx = PrevIdx( &rDstEndNd );
1474 0 : while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1475 : {
1476 0 : const SwNode* pSrcNd = rSrcNds[ nSrcEndIdx ];
1477 0 : const SwNode* pDstNd = rDstNds[ nDstEndIdx ];
1478 0 : if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1479 0 : break;
1480 :
1481 0 : nSrcEndIdx = PrevIdx( pSrcNd );
1482 0 : nDstEndIdx = PrevIdx( pDstNd );
1483 : }
1484 :
1485 0 : while( nSrcSttIdx <= nSrcEndIdx )
1486 : {
1487 0 : const SwNode* pNd = rSrcNds[ nSrcSttIdx ];
1488 0 : rData.InsertLine( new SwCompareLine( *pNd ) );
1489 0 : nSrcSttIdx = NextIdx( pNd );
1490 : }
1491 :
1492 0 : while( nDstSttIdx <= nDstEndIdx )
1493 : {
1494 0 : const SwNode* pNd = rDstNds[ nDstSttIdx ];
1495 0 : InsertLine( new SwCompareLine( *pNd ) );
1496 0 : nDstSttIdx = NextIdx( pNd );
1497 : }
1498 0 : }
1499 :
1500 0 : void SwCompareData::ShowInsert( sal_uLong nStt, sal_uLong nEnd )
1501 : {
1502 0 : SwPaM* pTmp = new SwPaM( ((SwCompareLine*)GetLine( nStt ))->GetNode(), 0,
1503 0 : ((SwCompareLine*)GetLine( nEnd-1 ))->GetEndNode(), 0,
1504 0 : pInsRing );
1505 0 : if( !pInsRing )
1506 0 : pInsRing = pTmp;
1507 :
1508 : // #i65201#: These SwPaMs are calculated smaller than needed, see comment below
1509 0 : }
1510 :
1511 0 : void SwCompareData::ShowDelete(
1512 : const CompareData& rData,
1513 : sal_uLong nStt,
1514 : sal_uLong nEnd,
1515 : sal_uLong nInsPos )
1516 : {
1517 : SwNodeRange aRg(
1518 0 : ((SwCompareLine*)rData.GetLine( nStt ))->GetNode(), 0,
1519 0 : ((SwCompareLine*)rData.GetLine( nEnd-1 ))->GetEndNode(), 1 );
1520 :
1521 0 : sal_uInt16 nOffset = 0;
1522 0 : const CompareLine* pLine = 0;
1523 0 : if( nInsPos >= 1 )
1524 : {
1525 0 : if( GetLineCount() == nInsPos )
1526 : {
1527 0 : pLine = GetLine( nInsPos-1 );
1528 0 : nOffset = 1;
1529 : }
1530 : else
1531 0 : pLine = GetLine( nInsPos );
1532 : }
1533 :
1534 : const SwNode* pLineNd;
1535 0 : if( pLine )
1536 : {
1537 0 : if( nOffset )
1538 0 : pLineNd = &((SwCompareLine*)pLine)->GetEndNode();
1539 : else
1540 0 : pLineNd = &((SwCompareLine*)pLine)->GetNode();
1541 : }
1542 : else
1543 : {
1544 0 : pLineNd = &rDoc.GetNodes().GetEndOfContent();
1545 0 : nOffset = 0;
1546 : }
1547 :
1548 0 : SwNodeIndex aInsPos( *pLineNd, nOffset );
1549 0 : SwNodeIndex aSavePos( aInsPos, -1 );
1550 :
1551 0 : ((SwCompareData&)rData).rDoc.GetDocumentContentOperationsManager().CopyWithFlyInFly( aRg, 0, aInsPos );
1552 0 : rDoc.getIDocumentState().SetModified();
1553 0 : ++aSavePos;
1554 :
1555 : // #i65201#: These SwPaMs are calculated when the (old) delete-redlines are hidden,
1556 : // they will be inserted when the delete-redlines are shown again.
1557 : // To avoid unwanted insertions of delete-redlines into these new redlines, what happens
1558 : // especially at the end of the document, I reduce the SwPaM by one node.
1559 : // Before the new redlines are inserted, they have to expand again.
1560 0 : SwPaM* pTmp = new SwPaM( aSavePos.GetNode(), aInsPos.GetNode(), 0, -1, pDelRing );
1561 0 : if( !pDelRing )
1562 0 : pDelRing = pTmp;
1563 :
1564 0 : if( pInsRing )
1565 : {
1566 0 : SwPaM* pCorr = (SwPaM*)pInsRing->GetPrev();
1567 0 : if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1568 : {
1569 0 : SwNodeIndex aTmpPos( pTmp->GetMark()->nNode, -1 );
1570 0 : *pCorr->GetPoint() = SwPosition( aTmpPos );
1571 : }
1572 0 : }
1573 0 : }
1574 :
1575 0 : void SwCompareData::CheckForChangesInLine( const CompareData& rData,
1576 : sal_uLong& rStt, sal_uLong& rEnd,
1577 : sal_uLong& rThisStt, sal_uLong& rThisEnd )
1578 : {
1579 : LineArrayComparator aCmp( (CompareData&)*this, rData, rThisStt, rThisEnd,
1580 0 : rStt, rEnd );
1581 :
1582 0 : int nMinLen = std::min( aCmp.GetLen1(), aCmp.GetLen2() );
1583 0 : boost::scoped_array<int> pLcsDst(new int[ nMinLen ]);
1584 0 : boost::scoped_array<int> pLcsSrc(new int[ nMinLen ]);
1585 :
1586 0 : FastCommonSubseq subseq( aCmp );
1587 0 : int nLcsLen = subseq.Find( pLcsDst.get(), pLcsSrc.get() );
1588 0 : for (int i = 0; i <= nLcsLen; i++)
1589 : {
1590 : // Beginning of inserted lines (inclusive)
1591 0 : int nDstFrom = i ? pLcsDst[i - 1] + 1 : 0;
1592 : // End of inserted lines (exclusive)
1593 0 : int nDstTo = ( i == nLcsLen ) ? aCmp.GetLen1() : pLcsDst[i];
1594 : // Beginning of deleted lines (inclusive)
1595 0 : int nSrcFrom = i ? pLcsSrc[i - 1] + 1 : 0;
1596 : // End of deleted lines (exclusive)
1597 0 : int nSrcTo = ( i == nLcsLen ) ? aCmp.GetLen2() : pLcsSrc[i];
1598 :
1599 0 : if( i )
1600 : {
1601 0 : SwCompareLine* pDstLn = (SwCompareLine*)GetLine( rThisStt + nDstFrom - 1 );
1602 0 : SwCompareLine* pSrcLn = (SwCompareLine*)rData.GetLine( rStt + nSrcFrom - 1 );
1603 :
1604 : // Show differences in detail for lines that
1605 : // were matched as only slightly different
1606 0 : if( !pDstLn->ChangesInLine( *pSrcLn, pInsRing, pDelRing ) )
1607 : {
1608 0 : ShowInsert( rThisStt + nDstFrom - 1, rThisStt + nDstFrom );
1609 0 : ShowDelete( rData, rStt + nSrcFrom - 1, rStt + nSrcFrom,
1610 0 : rThisStt + nDstFrom );
1611 : }
1612 : }
1613 :
1614 : // Lines missing from source are inserted
1615 0 : if( nDstFrom != nDstTo )
1616 : {
1617 0 : ShowInsert( rThisStt + nDstFrom, rThisStt + nDstTo );
1618 : }
1619 :
1620 : // Lines missing from destination are deleted
1621 0 : if( nSrcFrom != nSrcTo )
1622 : {
1623 0 : ShowDelete( rData, rStt + nSrcFrom, rStt + nSrcTo, rThisStt + nDstTo );
1624 : }
1625 0 : }
1626 0 : }
1627 :
1628 0 : void SwCompareData::SetRedlinesToDoc( bool bUseDocInfo )
1629 : {
1630 0 : SwPaM* pTmp = pDelRing;
1631 :
1632 : // get the Author / TimeStamp from the "other" document info
1633 0 : sal_uInt16 nAuthor = rDoc.getIDocumentRedlineAccess().GetRedlineAuthor();
1634 0 : DateTime aTimeStamp( DateTime::SYSTEM );
1635 0 : SwDocShell *pDocShell(rDoc.GetDocShell());
1636 : OSL_ENSURE(pDocShell, "no SwDocShell");
1637 0 : if (pDocShell) {
1638 : uno::Reference<document::XDocumentPropertiesSupplier> xDPS(
1639 0 : pDocShell->GetModel(), uno::UNO_QUERY_THROW);
1640 : uno::Reference<document::XDocumentProperties> xDocProps(
1641 0 : xDPS->getDocumentProperties());
1642 : OSL_ENSURE(xDocProps.is(), "Doc has no DocumentProperties");
1643 :
1644 0 : if( bUseDocInfo && xDocProps.is() ) {
1645 0 : OUString aTmp( 1 == xDocProps->getEditingCycles()
1646 0 : ? xDocProps->getAuthor()
1647 0 : : xDocProps->getModifiedBy() );
1648 0 : util::DateTime uDT( 1 == xDocProps->getEditingCycles()
1649 0 : ? xDocProps->getCreationDate()
1650 0 : : xDocProps->getModificationDate() );
1651 0 : Date d(uDT.Day, uDT.Month, uDT.Year);
1652 0 : tools::Time t(uDT.Hours, uDT.Minutes, uDT.Seconds, uDT.NanoSeconds);
1653 0 : DateTime aDT(d,t);
1654 :
1655 0 : if( !aTmp.isEmpty() )
1656 : {
1657 0 : nAuthor = rDoc.getIDocumentRedlineAccess().InsertRedlineAuthor( aTmp );
1658 0 : aTimeStamp = aDT;
1659 0 : }
1660 0 : }
1661 : }
1662 :
1663 0 : if( pTmp )
1664 : {
1665 : SwRedlineData aRedlnData( nsRedlineType_t::REDLINE_DELETE, nAuthor, aTimeStamp,
1666 0 : OUString(), 0, 0 );
1667 0 : do {
1668 : // #i65201#: Expand again, see comment above.
1669 0 : if( pTmp->GetPoint()->nContent == 0 )
1670 : {
1671 0 : pTmp->GetPoint()->nNode++;
1672 0 : pTmp->GetPoint()->nContent.Assign( pTmp->GetCntntNode(), 0 );
1673 : }
1674 : // #i101009#
1675 : // prevent redlines that end on structural end node
1676 0 : if (& rDoc.GetNodes().GetEndOfContent() ==
1677 0 : & pTmp->GetPoint()->nNode.GetNode())
1678 : {
1679 0 : pTmp->GetPoint()->nNode--;
1680 0 : SwCntntNode *const pContentNode( pTmp->GetCntntNode() );
1681 0 : pTmp->GetPoint()->nContent.Assign( pContentNode,
1682 0 : (pContentNode) ? pContentNode->Len() : 0 );
1683 : }
1684 :
1685 0 : rDoc.getIDocumentRedlineAccess().DeleteRedline( *pTmp, false, USHRT_MAX );
1686 :
1687 0 : if (rDoc.GetIDocumentUndoRedo().DoesUndo())
1688 : {
1689 0 : SwUndo *const pUndo(new SwUndoCompDoc( *pTmp, false )) ;
1690 0 : rDoc.GetIDocumentUndoRedo().AppendUndo(pUndo);
1691 : }
1692 0 : rDoc.getIDocumentRedlineAccess().AppendRedline( new SwRangeRedline( aRedlnData, *pTmp ), true );
1693 :
1694 0 : } while( pDelRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1695 : }
1696 :
1697 0 : pTmp = pInsRing;
1698 0 : if( pTmp )
1699 : {
1700 0 : do {
1701 0 : if( pTmp->GetPoint()->nContent == 0 )
1702 : {
1703 0 : pTmp->GetPoint()->nNode++;
1704 0 : pTmp->GetPoint()->nContent.Assign( pTmp->GetCntntNode(), 0 );
1705 : }
1706 : // #i101009#
1707 : // prevent redlines that end on structural end node
1708 0 : if (& rDoc.GetNodes().GetEndOfContent() ==
1709 0 : & pTmp->GetPoint()->nNode.GetNode())
1710 : {
1711 0 : pTmp->GetPoint()->nNode--;
1712 0 : SwCntntNode *const pContentNode( pTmp->GetCntntNode() );
1713 0 : pTmp->GetPoint()->nContent.Assign( pContentNode,
1714 0 : (pContentNode) ? pContentNode->Len() : 0 );
1715 : }
1716 0 : } while( pInsRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1717 : SwRedlineData aRedlnData( nsRedlineType_t::REDLINE_INSERT, nAuthor, aTimeStamp,
1718 0 : OUString(), 0, 0 );
1719 :
1720 : // combine consecutive
1721 0 : if( pTmp->GetNext() != pInsRing )
1722 : {
1723 : const SwCntntNode* pCNd;
1724 0 : do {
1725 0 : SwPosition& rSttEnd = *pTmp->End(),
1726 0 : & rEndStt = *((SwPaM*)pTmp->GetNext())->Start();
1727 0 : if( rSttEnd == rEndStt ||
1728 0 : (!rEndStt.nContent.GetIndex() &&
1729 0 : rEndStt.nNode.GetIndex() - 1 == rSttEnd.nNode.GetIndex() &&
1730 0 : 0 != ( pCNd = rSttEnd.nNode.GetNode().GetCntntNode() ) &&
1731 0 : rSttEnd.nContent.GetIndex() == pCNd->Len()))
1732 : {
1733 0 : if( pTmp->GetNext() == pInsRing )
1734 : {
1735 : // are consecutive, so combine
1736 0 : rEndStt = *pTmp->Start();
1737 0 : delete pTmp;
1738 0 : pTmp = pInsRing;
1739 : }
1740 : else
1741 : {
1742 : // are consecutive, so combine
1743 0 : rSttEnd = *((SwPaM*)pTmp->GetNext())->End();
1744 0 : delete pTmp->GetNext();
1745 : }
1746 : }
1747 : else
1748 0 : pTmp = (SwPaM*)pTmp->GetNext();
1749 0 : } while( pInsRing != pTmp );
1750 : }
1751 :
1752 0 : do {
1753 0 : if( rDoc.getIDocumentRedlineAccess().AppendRedline( new SwRangeRedline( aRedlnData, *pTmp ), true) &&
1754 0 : rDoc.GetIDocumentUndoRedo().DoesUndo())
1755 : {
1756 0 : SwUndo *const pUndo(new SwUndoCompDoc( *pTmp, true ));
1757 0 : rDoc.GetIDocumentUndoRedo().AppendUndo(pUndo);
1758 : }
1759 0 : } while( pInsRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1760 : }
1761 0 : }
1762 :
1763 : // Returns (the difference count?) if something is different
1764 0 : long SwDoc::CompareDoc( const SwDoc& rDoc )
1765 : {
1766 0 : if( &rDoc == this )
1767 0 : return 0;
1768 :
1769 0 : long nRet = 0;
1770 :
1771 : // Get comparison options
1772 0 : CmpOptions.eCmpMode = SW_MOD()->GetCompareMode();
1773 0 : if( CmpOptions.eCmpMode == SVX_CMP_AUTO )
1774 : {
1775 0 : if( getRsidRoot() == rDoc.getRsidRoot() )
1776 : {
1777 0 : CmpOptions.eCmpMode = SVX_CMP_BY_CHAR;
1778 0 : CmpOptions.bUseRsid = true;
1779 0 : CmpOptions.nIgnoreLen = 2;
1780 : }
1781 : else
1782 : {
1783 0 : CmpOptions.eCmpMode = SVX_CMP_BY_WORD;
1784 0 : CmpOptions.bUseRsid = false;
1785 0 : CmpOptions.nIgnoreLen = 3;
1786 : }
1787 : }
1788 : else
1789 : {
1790 0 : CmpOptions.bUseRsid = getRsidRoot() == rDoc.getRsidRoot() && SW_MOD()->IsUseRsid();
1791 0 : CmpOptions.nIgnoreLen = SW_MOD()->IsIgnorePieces() ? SW_MOD()->GetPieceLen() : 0;
1792 : }
1793 :
1794 0 : GetIDocumentUndoRedo().StartUndo(UNDO_EMPTY, NULL);
1795 0 : bool bDocWasModified = getIDocumentState().IsModified();
1796 0 : SwDoc& rSrcDoc = (SwDoc&)rDoc;
1797 0 : bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
1798 :
1799 0 : RedlineMode_t eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineMode();
1800 0 : rSrcDoc.getIDocumentRedlineAccess().SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_INSERT );
1801 0 : getIDocumentRedlineAccess().SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_ON | nsRedlineMode_t::REDLINE_SHOW_INSERT));
1802 :
1803 0 : SwCompareData aD0( rSrcDoc );
1804 0 : SwCompareData aD1( *this );
1805 :
1806 0 : aD1.CompareLines( aD0 );
1807 :
1808 0 : nRet = aD1.ShowDiffs( aD0 );
1809 :
1810 0 : if( nRet )
1811 : {
1812 0 : getIDocumentRedlineAccess().SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_ON |
1813 0 : nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1814 :
1815 0 : aD1.SetRedlinesToDoc( !bDocWasModified );
1816 0 : getIDocumentState().SetModified();
1817 : }
1818 :
1819 0 : rSrcDoc.getIDocumentRedlineAccess().SetRedlineMode( eSrcRedlMode );
1820 0 : getIDocumentRedlineAccess().SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1821 :
1822 0 : if( !bSrcModified )
1823 0 : rSrcDoc.getIDocumentState().ResetModified();
1824 :
1825 0 : GetIDocumentUndoRedo().EndUndo(UNDO_EMPTY, NULL);
1826 :
1827 0 : return nRet;
1828 : }
1829 :
1830 0 : class _SaveMergeRedlines : public Ring
1831 : {
1832 : const SwRangeRedline* pSrcRedl;
1833 : SwRangeRedline* pDestRedl;
1834 : public:
1835 : _SaveMergeRedlines( const SwNode& rDstNd,
1836 : const SwRangeRedline& rSrcRedl, Ring* pRing );
1837 : sal_uInt16 InsertRedline();
1838 : };
1839 :
1840 0 : _SaveMergeRedlines::_SaveMergeRedlines( const SwNode& rDstNd,
1841 : const SwRangeRedline& rSrcRedl, Ring* pRing )
1842 0 : : Ring( pRing ), pSrcRedl( &rSrcRedl )
1843 : {
1844 0 : SwPosition aPos( rDstNd );
1845 :
1846 0 : const SwPosition* pStt = rSrcRedl.Start();
1847 0 : if( rDstNd.IsCntntNode() )
1848 0 : aPos.nContent.Assign( ((SwCntntNode*)&rDstNd), pStt->nContent.GetIndex() );
1849 0 : pDestRedl = new SwRangeRedline( rSrcRedl.GetRedlineData(), aPos );
1850 :
1851 0 : if( nsRedlineType_t::REDLINE_DELETE == pDestRedl->GetType() )
1852 : {
1853 : // mark the area as deleted
1854 0 : const SwPosition* pEnd = pStt == rSrcRedl.GetPoint()
1855 0 : ? rSrcRedl.GetMark()
1856 0 : : rSrcRedl.GetPoint();
1857 :
1858 0 : pDestRedl->SetMark();
1859 0 : pDestRedl->GetPoint()->nNode += pEnd->nNode.GetIndex() -
1860 0 : pStt->nNode.GetIndex();
1861 0 : pDestRedl->GetPoint()->nContent.Assign( pDestRedl->GetCntntNode(),
1862 0 : pEnd->nContent.GetIndex() );
1863 0 : }
1864 0 : }
1865 :
1866 0 : sal_uInt16 _SaveMergeRedlines::InsertRedline()
1867 : {
1868 0 : sal_uInt16 nIns = 0;
1869 0 : SwDoc* pDoc = pDestRedl->GetDoc();
1870 :
1871 0 : if( nsRedlineType_t::REDLINE_INSERT == pDestRedl->GetType() )
1872 : {
1873 : // the part was inserted so copy it from the SourceDoc
1874 0 : ::sw::UndoGuard const undoGuard(pDoc->GetIDocumentUndoRedo());
1875 :
1876 0 : SwNodeIndex aSaveNd( pDestRedl->GetPoint()->nNode, -1 );
1877 0 : const sal_Int32 nSaveCnt = pDestRedl->GetPoint()->nContent.GetIndex();
1878 :
1879 0 : RedlineMode_t eOld = pDoc->getIDocumentRedlineAccess().GetRedlineMode();
1880 0 : pDoc->getIDocumentRedlineAccess().SetRedlineMode_intern((RedlineMode_t)(eOld | nsRedlineMode_t::REDLINE_IGNORE));
1881 :
1882 0 : pSrcRedl->GetDoc()->getIDocumentContentOperations().CopyRange(
1883 : *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1884 0 : *pDestRedl->GetPoint(), false );
1885 :
1886 0 : pDoc->getIDocumentRedlineAccess().SetRedlineMode_intern( eOld );
1887 :
1888 0 : pDestRedl->SetMark();
1889 0 : ++aSaveNd;
1890 0 : pDestRedl->GetMark()->nNode = aSaveNd;
1891 0 : pDestRedl->GetMark()->nContent.Assign( aSaveNd.GetNode().GetCntntNode(),
1892 0 : nSaveCnt );
1893 :
1894 0 : if( GetPrev() != this )
1895 : {
1896 0 : SwPaM* pTmpPrev = ((_SaveMergeRedlines*)GetPrev())->pDestRedl;
1897 0 : if( pTmpPrev && *pTmpPrev->GetPoint() == *pDestRedl->GetPoint() )
1898 0 : *pTmpPrev->GetPoint() = *pDestRedl->GetMark();
1899 0 : }
1900 : }
1901 : else
1902 : {
1903 : //JP 21.09.98: Bug 55909
1904 : // If there already is a deleted or inserted one at the same position, we have to split it!
1905 0 : SwPosition* pDStt = pDestRedl->GetMark(),
1906 0 : * pDEnd = pDestRedl->GetPoint();
1907 0 : sal_uInt16 n = 0;
1908 :
1909 : // find the first redline for StartPos
1910 0 : if( !pDoc->getIDocumentRedlineAccess().GetRedline( *pDStt, &n ) && n )
1911 0 : --n;
1912 :
1913 0 : const SwRedlineTbl& rRedlineTbl = pDoc->getIDocumentRedlineAccess().GetRedlineTbl();
1914 0 : for( ; n < rRedlineTbl.size(); ++n )
1915 : {
1916 0 : SwRangeRedline* pRedl = rRedlineTbl[ n ];
1917 0 : SwPosition* pRStt = pRedl->Start(),
1918 0 : * pREnd = pRStt == pRedl->GetPoint() ? pRedl->GetMark()
1919 0 : : pRedl->GetPoint();
1920 0 : if( nsRedlineType_t::REDLINE_DELETE == pRedl->GetType() ||
1921 0 : nsRedlineType_t::REDLINE_INSERT == pRedl->GetType() )
1922 : {
1923 0 : SwComparePosition eCmpPos = ComparePosition( *pDStt, *pDEnd, *pRStt, *pREnd );
1924 0 : switch( eCmpPos )
1925 : {
1926 : case POS_COLLIDE_START:
1927 : case POS_BEHIND:
1928 0 : break;
1929 :
1930 : case POS_INSIDE:
1931 : case POS_EQUAL:
1932 0 : delete pDestRedl, pDestRedl = 0;
1933 : // break; -> no break !!!!
1934 :
1935 : case POS_COLLIDE_END:
1936 : case POS_BEFORE:
1937 0 : n = rRedlineTbl.size();
1938 0 : break;
1939 :
1940 : case POS_OUTSIDE:
1941 : {
1942 : SwRangeRedline* pCpyRedl = new SwRangeRedline(
1943 0 : pDestRedl->GetRedlineData(), *pDStt );
1944 0 : pCpyRedl->SetMark();
1945 0 : *pCpyRedl->GetPoint() = *pRStt;
1946 :
1947 : SwUndoCompDoc *const pUndo =
1948 0 : (pDoc->GetIDocumentUndoRedo().DoesUndo())
1949 0 : ? new SwUndoCompDoc( *pCpyRedl ) : 0;
1950 :
1951 : // now modify doc: append redline, undo (and count)
1952 0 : pDoc->getIDocumentRedlineAccess().AppendRedline( pCpyRedl, true );
1953 0 : if( pUndo )
1954 : {
1955 0 : pDoc->GetIDocumentUndoRedo().AppendUndo(pUndo);
1956 : }
1957 0 : ++nIns;
1958 :
1959 0 : *pDStt = *pREnd;
1960 :
1961 : // we should start over now
1962 0 : n = USHRT_MAX;
1963 : }
1964 0 : break;
1965 :
1966 : case POS_OVERLAP_BEFORE:
1967 0 : *pDEnd = *pRStt;
1968 0 : break;
1969 :
1970 : case POS_OVERLAP_BEHIND:
1971 0 : *pDStt = *pREnd;
1972 0 : break;
1973 : }
1974 : }
1975 0 : else if( *pDEnd <= *pRStt )
1976 0 : break;
1977 : }
1978 :
1979 : }
1980 :
1981 0 : if( pDestRedl )
1982 : {
1983 0 : SwUndoCompDoc *const pUndo = (pDoc->GetIDocumentUndoRedo().DoesUndo())
1984 0 : ? new SwUndoCompDoc( *pDestRedl ) : 0;
1985 :
1986 : // now modify doc: append redline, undo (and count)
1987 0 : bool bRedlineAccepted = pDoc->getIDocumentRedlineAccess().AppendRedline( pDestRedl, true );
1988 0 : if( pUndo )
1989 : {
1990 0 : pDoc->GetIDocumentUndoRedo().AppendUndo( pUndo );
1991 : }
1992 0 : ++nIns;
1993 :
1994 : // if AppendRedline has deleted our redline, we may not keep a
1995 : // reference to it
1996 0 : if( ! bRedlineAccepted )
1997 0 : pDestRedl = NULL;
1998 : }
1999 0 : return nIns;
2000 : }
2001 :
2002 : /// Merge two documents
2003 0 : long SwDoc::MergeDoc( const SwDoc& rDoc )
2004 : {
2005 0 : if( &rDoc == this )
2006 0 : return 0;
2007 :
2008 0 : long nRet = 0;
2009 :
2010 0 : GetIDocumentUndoRedo().StartUndo(UNDO_EMPTY, NULL);
2011 :
2012 0 : SwDoc& rSrcDoc = (SwDoc&)rDoc;
2013 0 : bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
2014 :
2015 0 : RedlineMode_t eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineMode();
2016 0 : rSrcDoc.getIDocumentRedlineAccess().SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_DELETE );
2017 0 : getIDocumentRedlineAccess().SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_DELETE );
2018 :
2019 0 : SwCompareData aD0( rSrcDoc );
2020 0 : SwCompareData aD1( *this );
2021 :
2022 0 : aD1.CompareLines( aD0 );
2023 :
2024 0 : if( !aD1.HasDiffs( aD0 ) )
2025 : {
2026 : // we want to get all redlines from the SourceDoc
2027 :
2028 : // look for all insert redlines from the SourceDoc and determine their position in the DestDoc
2029 0 : _SaveMergeRedlines* pRing = 0;
2030 0 : const SwRedlineTbl& rSrcRedlTbl = rSrcDoc.getIDocumentRedlineAccess().GetRedlineTbl();
2031 0 : sal_uLong nEndOfExtra = rSrcDoc.GetNodes().GetEndOfExtras().GetIndex();
2032 0 : sal_uLong nMyEndOfExtra = GetNodes().GetEndOfExtras().GetIndex();
2033 0 : for( sal_uInt16 n = 0; n < rSrcRedlTbl.size(); ++n )
2034 : {
2035 0 : const SwRangeRedline* pRedl = rSrcRedlTbl[ n ];
2036 0 : sal_uLong nNd = pRedl->GetPoint()->nNode.GetIndex();
2037 0 : RedlineType_t eType = pRedl->GetType();
2038 0 : if( nEndOfExtra < nNd &&
2039 0 : ( nsRedlineType_t::REDLINE_INSERT == eType || nsRedlineType_t::REDLINE_DELETE == eType ))
2040 : {
2041 0 : const SwNode* pDstNd = GetNodes()[
2042 0 : nMyEndOfExtra + nNd - nEndOfExtra ];
2043 :
2044 : // Found the position.
2045 : // Then we also have to insert the redline to the line in the DestDoc.
2046 : _SaveMergeRedlines* pTmp = new _SaveMergeRedlines(
2047 0 : *pDstNd, *pRedl, pRing );
2048 0 : if( !pRing )
2049 0 : pRing = pTmp;
2050 : }
2051 : }
2052 :
2053 0 : if( pRing )
2054 : {
2055 : // Carry over all into DestDoc
2056 0 : rSrcDoc.getIDocumentRedlineAccess().SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
2057 :
2058 0 : getIDocumentRedlineAccess().SetRedlineMode((RedlineMode_t)(
2059 : nsRedlineMode_t::REDLINE_ON |
2060 : nsRedlineMode_t::REDLINE_SHOW_INSERT |
2061 0 : nsRedlineMode_t::REDLINE_SHOW_DELETE));
2062 :
2063 0 : _SaveMergeRedlines* pTmp = pRing;
2064 :
2065 0 : do {
2066 0 : nRet += pTmp->InsertRedline();
2067 0 : } while( pRing != ( pTmp = (_SaveMergeRedlines*)pTmp->GetNext() ));
2068 :
2069 0 : while( pRing != pRing->GetNext() )
2070 0 : delete pRing->GetNext();
2071 0 : delete pRing;
2072 : }
2073 : }
2074 :
2075 0 : rSrcDoc.getIDocumentRedlineAccess().SetRedlineMode( eSrcRedlMode );
2076 0 : if( !bSrcModified )
2077 0 : rSrcDoc.getIDocumentState().ResetModified();
2078 :
2079 0 : getIDocumentRedlineAccess().SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
2080 :
2081 0 : GetIDocumentUndoRedo().EndUndo(UNDO_EMPTY, NULL);
2082 :
2083 0 : return nRet;
2084 : }
2085 :
2086 0 : LineArrayComparator::LineArrayComparator( const CompareData &rD1,
2087 : const CompareData &rD2, int nStt1,
2088 : int nEnd1, int nStt2, int nEnd2 )
2089 0 : : rData1( rD1 ), rData2( rD2 ), nFirst1( nStt1 ), nFirst2( nStt2 )
2090 : {
2091 0 : nLen1 = nEnd1 - nStt1;
2092 0 : nLen2 = nEnd2 - nStt2;
2093 0 : }
2094 :
2095 0 : bool LineArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2096 : {
2097 0 : if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= nLen1 || nIdx2 >= nLen2 )
2098 : {
2099 : OSL_ENSURE( false, "Index out of range!" );
2100 0 : return false;
2101 : }
2102 :
2103 0 : const SwTxtNode *pTxtNd1 = ( ( SwCompareLine* )rData1.GetLine( nFirst1 + nIdx1 ) )->GetNode().GetTxtNode();
2104 0 : const SwTxtNode *pTxtNd2 = ( ( SwCompareLine* )rData2.GetLine( nFirst2 + nIdx2 ) )->GetNode().GetTxtNode();
2105 :
2106 0 : if( !pTxtNd1 || !pTxtNd2
2107 0 : || ( CmpOptions.bUseRsid && !pTxtNd1->CompareParRsid( *pTxtNd2 ) ) )
2108 : {
2109 0 : return false;
2110 : }
2111 :
2112 0 : const sal_Int32 nPar1Len = pTxtNd1->Len();
2113 0 : const sal_Int32 nPar2Len = pTxtNd2->Len();
2114 :
2115 0 : if( std::min( nPar1Len, nPar2Len ) * 3 < std::max( nPar1Len, nPar2Len ) )
2116 : {
2117 0 : return false;
2118 : }
2119 :
2120 0 : sal_Int32 nBorderLen = ( nPar1Len + nPar2Len )/16;
2121 :
2122 0 : if( nBorderLen < 3 )
2123 : {
2124 0 : nBorderLen = std::min<sal_Int32>( 3, std::min( nPar1Len, nPar2Len ) );
2125 : }
2126 :
2127 0 : std::set<unsigned> aHashes;
2128 0 : unsigned nHash = 0;
2129 0 : unsigned nMul = 251;
2130 0 : unsigned nPow = 1;
2131 : sal_Int32 i;
2132 :
2133 0 : for( i = 0; i < nBorderLen - 1; i++ )
2134 : {
2135 0 : nPow *= nMul;
2136 : }
2137 0 : for( i = 0; i < nBorderLen; i++ )
2138 : {
2139 0 : nHash = nHash*nMul + pTxtNd1->GetTxt()[i];
2140 : }
2141 0 : aHashes.insert( nHash );
2142 0 : for( ; i < nPar1Len; i++ )
2143 : {
2144 0 : nHash = nHash - nPow*pTxtNd1->GetTxt()[ i - nBorderLen ];
2145 0 : nHash = nHash*nMul + pTxtNd1->GetTxt()[ i ];
2146 :
2147 0 : aHashes.insert( nHash );
2148 : }
2149 :
2150 0 : nHash = 0;
2151 0 : for( i = 0; i < nBorderLen; i++ )
2152 : {
2153 0 : nHash = nHash*nMul + pTxtNd2->GetTxt()[ i ];
2154 : }
2155 :
2156 0 : if( aHashes.find( nHash ) != aHashes.end() )
2157 : {
2158 0 : return true;
2159 : }
2160 :
2161 0 : for( ; i < nPar2Len; i++ )
2162 : {
2163 0 : nHash = nHash - nPow*pTxtNd2->GetTxt()[ i - nBorderLen ];
2164 0 : nHash = nHash*nMul + pTxtNd2->GetTxt()[ i ];
2165 0 : if( aHashes.find( nHash ) != aHashes.end() )
2166 : {
2167 0 : return true;
2168 : }
2169 : }
2170 0 : return false;
2171 : }
2172 :
2173 0 : bool CharArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2174 : {
2175 0 : if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= GetLen1() || nIdx2 >= GetLen2() )
2176 : {
2177 : OSL_ENSURE( false, "Index out of range!" );
2178 0 : return false;
2179 : }
2180 :
2181 0 : return ( !CmpOptions.bUseRsid
2182 0 : || pTxtNd1->CompareRsid( *pTxtNd2, nIdx1 + 1, nIdx2 + 1 ) )
2183 0 : && pTxtNd1->GetTxt()[ nIdx1 ] == pTxtNd2->GetTxt()[ nIdx2 ];
2184 : }
2185 :
2186 0 : WordArrayComparator::WordArrayComparator( const SwTxtNode *pNode1,
2187 : const SwTxtNode *pNode2 )
2188 0 : : pTxtNd1( pNode1 ), pTxtNd2( pNode2 )
2189 : {
2190 0 : pPos1 = new int[ pTxtNd1->GetTxt().getLength() + 1 ];
2191 0 : pPos2 = new int[ pTxtNd2->GetTxt().getLength() + 1 ];
2192 :
2193 0 : CalcPositions( pPos1, pTxtNd1, nCnt1 );
2194 0 : CalcPositions( pPos2, pTxtNd2, nCnt2 );
2195 0 : }
2196 :
2197 0 : WordArrayComparator::~WordArrayComparator()
2198 : {
2199 0 : delete[] pPos1;
2200 0 : delete[] pPos2;
2201 0 : }
2202 :
2203 0 : bool WordArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2204 : {
2205 0 : int nLen = pPos1[ nIdx1 + 1 ] - pPos1[ nIdx1 ];
2206 0 : if( nLen != pPos2[ nIdx2 + 1 ] - pPos2[ nIdx2 ] )
2207 : {
2208 0 : return false;
2209 : }
2210 0 : for( int i = 0; i < nLen; i++)
2211 : {
2212 0 : if( pTxtNd1->GetTxt()[ pPos1[ nIdx1 ] + i ]
2213 0 : != pTxtNd2->GetTxt()[ pPos2[ nIdx2 ] + i ]
2214 0 : || ( CmpOptions.bUseRsid && !pTxtNd1->CompareRsid( *pTxtNd2,
2215 0 : pPos1[ nIdx1 ] + i, pPos2[ nIdx2 ] + i ) ) )
2216 : {
2217 0 : return false;
2218 : }
2219 : }
2220 0 : return true;
2221 : }
2222 :
2223 0 : int WordArrayComparator::GetCharSequence( const int *pWordLcs1,
2224 : const int *pWordLcs2, int *pSubseq1, int *pSubseq2, int nLcsLen )
2225 : {
2226 0 : int nLen = 0;
2227 0 : for( int i = 0; i < nLcsLen; i++ )
2228 : {
2229 : // Check for hash collisions
2230 0 : if( pPos1[ pWordLcs1[i] + 1 ] - pPos1[ pWordLcs1[i] ]
2231 0 : != pPos2[ pWordLcs2[i] + 1 ] - pPos2[ pWordLcs2[i] ] )
2232 : {
2233 0 : continue;
2234 : }
2235 0 : for( int j = 0; j < pPos1[pWordLcs1[i]+1] - pPos1[pWordLcs1[i]]; j++)
2236 : {
2237 0 : pSubseq1[ nLen ] = pPos1[ pWordLcs1[i] ] + j;
2238 0 : pSubseq2[ nLen ] = pPos2[ pWordLcs2[i] ] + j;
2239 :
2240 0 : if( pTxtNd1->GetTxt()[ pPos1[ pWordLcs1[i] ] + j ]
2241 0 : != pTxtNd2->GetTxt()[ pPos2[ pWordLcs2[i] ] + j ] )
2242 : {
2243 0 : nLen -= j;
2244 0 : break;
2245 : }
2246 :
2247 0 : nLen++;
2248 : }
2249 : }
2250 0 : return nLen;
2251 : }
2252 :
2253 0 : void WordArrayComparator::CalcPositions( int *pPos, const SwTxtNode *pTxtNd,
2254 : int &nCnt )
2255 : {
2256 0 : nCnt = -1;
2257 0 : for (int i = 0; i <= pTxtNd->GetTxt().getLength(); ++i)
2258 : {
2259 0 : if (i == 0 || i == pTxtNd->GetTxt().getLength()
2260 0 : || !isalnum( pTxtNd->GetTxt()[ i - 1 ])
2261 0 : || !isalnum( pTxtNd->GetTxt()[ i ]))
2262 : { // Begin new word
2263 0 : nCnt++;
2264 0 : pPos[ nCnt ] = i;
2265 : }
2266 : }
2267 0 : }
2268 :
2269 0 : int CommonSubseq::FindLCS( int *pLcs1, int *pLcs2, int nStt1, int nEnd1,
2270 : int nStt2, int nEnd2 )
2271 : {
2272 0 : int nLen1 = nEnd1 ? nEnd1 - nStt1 : rCmp.GetLen1();
2273 0 : int nLen2 = nEnd2 ? nEnd2 - nStt2 : rCmp.GetLen2();
2274 :
2275 : OSL_ASSERT( nLen1 >= 0 );
2276 : OSL_ASSERT( nLen2 >= 0 );
2277 :
2278 0 : int **pLcs = new int*[ nLen1 + 1 ];
2279 0 : pLcs[ 0 ] = pData;
2280 :
2281 0 : for( int i = 1; i < nLen1 + 1; i++ )
2282 0 : pLcs[ i ] = pLcs[ i - 1 ] + nLen2 + 1;
2283 :
2284 0 : for( int i = 0; i <= nLen1; i++ )
2285 0 : pLcs[i][0] = 0;
2286 :
2287 0 : for( int j = 0; j <= nLen2; j++ )
2288 0 : pLcs[0][j] = 0;
2289 :
2290 : // Find lcs
2291 0 : for( int i = 1; i <= nLen1; i++ )
2292 : {
2293 0 : for( int j = 1; j <= nLen2; j++ )
2294 : {
2295 0 : if( rCmp.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2296 0 : pLcs[i][j] = pLcs[i - 1][j - 1] + 1;
2297 : else
2298 0 : pLcs[i][j] = std::max( pLcs[i][j - 1], pLcs[i - 1][j] );
2299 : }
2300 : }
2301 :
2302 0 : int nLcsLen = pLcs[ nLen1 ][ nLen2 ];
2303 :
2304 : // Recover the lcs in the two sequences
2305 0 : if( pLcs1 && pLcs2 )
2306 : {
2307 0 : int nIdx1 = nLen1;
2308 0 : int nIdx2 = nLen2;
2309 0 : int nIdx = nLcsLen - 1;
2310 :
2311 0 : while( nIdx1 > 0 && nIdx2 > 0 )
2312 : {
2313 0 : if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 - 1 ][ nIdx2 ] )
2314 0 : nIdx1--;
2315 0 : else if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 ][ nIdx2 - 1 ] )
2316 0 : nIdx2--;
2317 : else
2318 : {
2319 0 : nIdx1--, nIdx2--;
2320 0 : pLcs1[ nIdx ] = nIdx1 + nStt1;
2321 0 : pLcs2[ nIdx ] = nIdx2 + nStt2;
2322 0 : nIdx--;
2323 : }
2324 : }
2325 : }
2326 :
2327 0 : delete[] pLcs;
2328 :
2329 0 : return nLcsLen;
2330 : }
2331 :
2332 0 : int CommonSubseq::IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1,
2333 : int nLen2, int nLcsLen, int nPieceLen )
2334 : {
2335 0 : if( !nLcsLen )
2336 : {
2337 0 : return 0;
2338 : }
2339 :
2340 0 : int nNext = 0;
2341 :
2342 : // Don't ignore text at the beginning of the paragraphs
2343 0 : if( pLcs1[ 0 ] == 0 && pLcs2[ 0 ] == 0 )
2344 : {
2345 0 : while( nNext < nLcsLen - 1 && pLcs1[ nNext ] + 1 == pLcs1[ nNext + 1 ]
2346 0 : && pLcs2[ nNext ] + 1 == pLcs2[ nNext + 1 ] )
2347 : {
2348 0 : nNext++;
2349 : }
2350 0 : nNext++;
2351 : }
2352 :
2353 0 : int nCnt = 1;
2354 :
2355 0 : for( int i = nNext; i < nLcsLen; i++ )
2356 : {
2357 0 : if( i != nLcsLen - 1 && pLcs1[ i ] + 1 == pLcs1[ i + 1 ]
2358 0 : && pLcs2[ i ] + 1 == pLcs2[ i + 1 ] )
2359 : {
2360 0 : nCnt++;
2361 : }
2362 : else
2363 : {
2364 0 : if( nCnt > nPieceLen
2365 : // Don't ignore text at the end of the paragraphs
2366 0 : || ( i == nLcsLen - 1
2367 0 : && pLcs1[i] == nLen1 - 1 && pLcs2[i] == nLen2 - 1 ))
2368 : {
2369 0 : for( int j = i + 1 - nCnt; j <= i; j++ )
2370 : {
2371 0 : pLcs2[ nNext ] = pLcs2[ j ];
2372 0 : pLcs1[ nNext ] = pLcs1[ j ];
2373 0 : nNext++;
2374 : }
2375 : }
2376 0 : nCnt = 1;
2377 : }
2378 : }
2379 :
2380 0 : return nNext;
2381 : }
2382 :
2383 0 : LgstCommonSubseq::LgstCommonSubseq( ArrayComparator &rComparator )
2384 0 : : CommonSubseq( rComparator, CUTOFF )
2385 : {
2386 0 : pBuff1 = new int[ rComparator.GetLen2() + 1 ];
2387 0 : pBuff2 = new int[ rComparator.GetLen2() + 1 ];
2388 :
2389 0 : pL1 = new int[ rComparator.GetLen2() + 1 ];
2390 0 : pL2 = new int[ rComparator.GetLen2() + 1 ];
2391 0 : }
2392 :
2393 0 : LgstCommonSubseq::~LgstCommonSubseq()
2394 : {
2395 0 : delete[] pBuff1;
2396 0 : delete[] pBuff2;
2397 :
2398 0 : delete[] pL1;
2399 0 : delete[] pL2;
2400 0 : }
2401 :
2402 0 : void LgstCommonSubseq::FindL( int *pL, int nStt1, int nEnd1,
2403 : int nStt2, int nEnd2 )
2404 : {
2405 0 : int nLen1 = nEnd1 ? nEnd1 - nStt1 : rCmp.GetLen1();
2406 0 : int nLen2 = nEnd2 ? nEnd2 - nStt2 : rCmp.GetLen2();
2407 :
2408 0 : int *currL = pBuff1;
2409 0 : int *prevL = pBuff2;
2410 :
2411 : // Avoid memory corruption
2412 0 : if( nLen2 > rCmp.GetLen2() )
2413 : {
2414 : assert( false );
2415 0 : return;
2416 : }
2417 :
2418 0 : memset( pBuff1, 0, sizeof( *pBuff1 ) * ( nLen2 + 1 ) );
2419 0 : memset( pBuff2, 0, sizeof( *pBuff2 ) * ( nLen2 + 1 ) );
2420 :
2421 : // Find lcs
2422 0 : for( int i = 1; i <= nLen1; i++ )
2423 : {
2424 0 : for( int j = 1; j <= nLen2; j++ )
2425 : {
2426 0 : if( rCmp.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2427 0 : currL[j] = prevL[j - 1] + 1;
2428 : else
2429 0 : currL[j] = std::max( currL[j - 1], prevL[j] );
2430 : }
2431 0 : int *tmp = currL;
2432 0 : currL = prevL;
2433 0 : prevL = tmp;
2434 : }
2435 0 : memcpy( pL, prevL, ( nLen2 + 1 ) * sizeof( *prevL ) );
2436 : }
2437 :
2438 0 : int LgstCommonSubseq::HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1,
2439 : int nEnd1, int nStt2, int nEnd2 )
2440 : {
2441 : static int nLen1;
2442 : static int nLen2;
2443 0 : nLen1 = nEnd1 - nStt1;
2444 0 : nLen2 = nEnd2 - nStt2;
2445 :
2446 0 : if( ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2447 : {
2448 0 : if( !nLen1 || !nLen2 )
2449 : {
2450 0 : return 0;
2451 : }
2452 0 : return FindLCS(pLcs1, pLcs2, nStt1, nEnd1, nStt2, nEnd2);
2453 : }
2454 :
2455 0 : int nMid = nLen1/2;
2456 :
2457 0 : FindL( pL1, nStt1, nStt1 + nMid, nStt2, nEnd2 );
2458 0 : FindL( pL2, nStt1 + nMid, nEnd1, nStt2, nEnd2 );
2459 :
2460 0 : int nMaxPos = 0;
2461 : static int nMaxVal;
2462 0 : nMaxVal = -1;
2463 :
2464 : static int i;
2465 0 : for( i = 0; i <= nLen2; i++ )
2466 : {
2467 0 : if( pL1[i] + ( pL2[nLen2] - pL2[i] ) > nMaxVal )
2468 : {
2469 0 : nMaxPos = i;
2470 0 : nMaxVal = pL1[i]+( pL2[nLen2] - pL2[i] );
2471 : }
2472 : }
2473 :
2474 : int nRet = HirschbergLCS( pLcs1, pLcs2, nStt1, nStt1 + nMid,
2475 0 : nStt2, nStt2 + nMaxPos );
2476 : nRet += HirschbergLCS( pLcs1 + nRet, pLcs2 + nRet, nStt1 + nMid, nEnd1,
2477 0 : nStt2 + nMaxPos, nEnd2 );
2478 :
2479 0 : return nRet;
2480 : }
2481 :
2482 0 : int LgstCommonSubseq::Find( int *pSubseq1, int *pSubseq2 )
2483 : {
2484 0 : int nStt = 0;
2485 0 : int nCutEnd = 0;
2486 0 : int nEnd1 = rCmp.GetLen1();
2487 0 : int nEnd2 = rCmp.GetLen2();
2488 :
2489 : // Check for corresponding lines in the beginning of the sequences
2490 0 : while( nStt < nEnd1 && nStt < nEnd2 && rCmp.Compare( nStt, nStt ) )
2491 : {
2492 0 : pSubseq1[ nStt ] = nStt;
2493 0 : pSubseq2[ nStt ] = nStt;
2494 0 : nStt++;
2495 : }
2496 :
2497 0 : pSubseq1 += nStt;
2498 0 : pSubseq2 += nStt;
2499 :
2500 : // Check for corresponding lines in the end of the sequences
2501 0 : while( nStt < nEnd1 && nStt < nEnd2
2502 0 : && rCmp.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2503 : {
2504 0 : nCutEnd++;
2505 0 : nEnd1--;
2506 0 : nEnd2--;
2507 : }
2508 :
2509 0 : int nLen = HirschbergLCS( pSubseq1, pSubseq2, nStt, nEnd1, nStt, nEnd2 );
2510 :
2511 0 : for( int i = 0; i < nCutEnd; i++ )
2512 : {
2513 0 : pSubseq1[ nLen + i ] = nEnd1 + i;
2514 0 : pSubseq2[ nLen + i ] = nEnd2 + i;
2515 : }
2516 :
2517 0 : return nStt + nLen + nCutEnd;
2518 : }
2519 :
2520 0 : int FastCommonSubseq::FindFastCS( int *pSeq1, int *pSeq2, int nStt1,
2521 : int nEnd1, int nStt2, int nEnd2 )
2522 : {
2523 0 : int nCutBeg = 0;
2524 0 : int nCutEnd = 0;
2525 :
2526 : // Check for corresponding lines in the beginning of the sequences
2527 0 : while( nStt1 < nEnd1 && nStt2 < nEnd2 && rCmp.Compare( nStt1, nStt2 ) )
2528 : {
2529 0 : pSeq1[ nCutBeg ] = nStt1++;
2530 0 : pSeq2[ nCutBeg ] = nStt2++;
2531 0 : nCutBeg++;
2532 : }
2533 :
2534 0 : pSeq1 += nCutBeg;
2535 0 : pSeq2 += nCutBeg;
2536 :
2537 : // Check for corresponding lines in the end of the sequences
2538 0 : while( nStt1 < nEnd1 && nStt2 < nEnd2
2539 0 : && rCmp.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2540 : {
2541 0 : nCutEnd++;
2542 0 : nEnd1--;
2543 0 : nEnd2--;
2544 : }
2545 :
2546 0 : int nLen1 = nEnd1 - nStt1;
2547 0 : int nLen2 = nEnd2 - nStt2;
2548 :
2549 : // Return if a sequence is empty
2550 0 : if( nLen1 <= 0 || nLen2 <= 0 )
2551 : {
2552 0 : for( int i = 0; i < nCutEnd; i++ )
2553 : {
2554 0 : pSeq1[ i ] = nEnd1 + i;
2555 0 : pSeq2[ i ] = nEnd2 + i;
2556 : }
2557 0 : return nCutBeg + nCutEnd;
2558 : }
2559 :
2560 : // Cut to LCS for small values
2561 0 : if( nLen1 < 3 || nLen2 < 3 || ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2562 : {
2563 0 : int nLcsLen = FindLCS( pSeq1, pSeq2, nStt1, nEnd1, nStt2, nEnd2);
2564 :
2565 0 : for( int i = 0; i < nCutEnd; i++ )
2566 : {
2567 0 : pSeq1[ nLcsLen + i ] = nEnd1 + i;
2568 0 : pSeq2[ nLcsLen + i ] = nEnd2 + i;
2569 : }
2570 0 : return nCutBeg + nLcsLen + nCutEnd;
2571 : }
2572 :
2573 0 : int nMid1 = nLen1/2;
2574 0 : int nMid2 = nLen2/2;
2575 :
2576 : int nRad;
2577 0 : int nPos1 = -1, nPos2 = -1;
2578 :
2579 : // Find a point of correspondence in the middle of the sequences
2580 0 : for( nRad = 0; nRad*nRad < std::min( nMid1, nMid2 ); nRad++ )
2581 : {
2582 : // Search to the left and to the right of the middle of the first sequence
2583 0 : for( int i = nMid1 - nRad; i <= nMid1 + nRad; i++ )
2584 : {
2585 0 : if( rCmp.Compare( nStt1 + i, nStt2 + nMid2 - nRad ) )
2586 : {
2587 0 : nPos1 = nStt1 + i;
2588 0 : nPos2 = nStt2 + nMid2 - nRad;
2589 0 : break;
2590 : }
2591 0 : if( rCmp.Compare( nStt1 + i, nStt2 + nMid2 + nRad ) )
2592 : {
2593 0 : nPos1 = nStt1 + i;
2594 0 : nPos2 = nStt2 + nMid2 - nRad;
2595 0 : break;
2596 : }
2597 : }
2598 : // Search to the left and to the right of the middle of the second sequence
2599 0 : for( int i = nMid2 - nRad; i <= nMid2 + nRad; i++ )
2600 : {
2601 0 : if( rCmp.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2602 : {
2603 0 : nPos2 = nStt2 + i;
2604 0 : nPos1 = nStt1 + nMid1 - nRad;
2605 0 : break;
2606 : }
2607 0 : if( rCmp.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2608 : {
2609 0 : nPos2 = nStt2 + i;
2610 0 : nPos1 = nStt1 + nMid1 - nRad;
2611 0 : break;
2612 : }
2613 : }
2614 : }
2615 :
2616 : // return if no point of correspondence found
2617 0 : if( nPos1 == -1 )
2618 : {
2619 0 : for( int i = 0; i < nCutEnd; i++ )
2620 : {
2621 0 : pSeq1[ i ] = nEnd1 + i;
2622 0 : pSeq2[ i ] = nEnd2 + i;
2623 : }
2624 0 : return nCutBeg + nCutEnd;
2625 : }
2626 :
2627 : // Run the same on the sequences to the left of the correspondence point
2628 0 : int nLen = FindFastCS( pSeq1, pSeq2, nStt1, nPos1, nStt2, nPos2 );
2629 :
2630 0 : pSeq1[ nLen ] = nPos1;
2631 0 : pSeq2[ nLen ] = nPos2;
2632 :
2633 : // Run the same on the sequences to the right of the correspondence point
2634 0 : nLen += FindFastCS( pSeq1 + nLen + 1, pSeq2 + nLen + 1,
2635 0 : nPos1 + 1, nEnd1, nPos2 + 1, nEnd2 ) + 1;
2636 :
2637 0 : for( int i = 0; i < nCutEnd; i++ )
2638 : {
2639 0 : pSeq1[ nLen + i ] = nEnd1 + i;
2640 0 : pSeq2[ nLen + i ] = nEnd2 + i;
2641 : }
2642 :
2643 0 : return nLen + nCutBeg + nCutEnd;
2644 270 : }
2645 :
2646 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
