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