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 :
21 : #include <hintids.hxx>
22 : #include <vcl/vclenum.hxx>
23 : #include <editeng/crsditem.hxx>
24 : #include <editeng/colritem.hxx>
25 : #include <editeng/boxitem.hxx>
26 : #include <editeng/svxenum.hxx>
27 : #include <editeng/udlnitem.hxx>
28 : #include <swmodule.hxx>
29 : #include <doc.hxx>
30 : #include <IDocumentUndoRedo.hxx>
31 : #include <docary.hxx>
32 : #include <pam.hxx>
33 : #include <ndtxt.hxx>
34 : #include <redline.hxx>
35 : #include <UndoRedline.hxx>
36 : #include <section.hxx>
37 : #include <tox.hxx>
38 : #include <docsh.hxx>
39 :
40 : #include <com/sun/star/document/XDocumentPropertiesSupplier.hpp>
41 : #include <com/sun/star/document/XDocumentProperties.hpp>
42 :
43 : #include <vector>
44 :
45 : #include <set>
46 : #include <cctype>
47 :
48 : using namespace ::com::sun::star;
49 :
50 : using ::std::vector;
51 :
52 : class CompareLine
53 : {
54 : public:
55 0 : CompareLine() {}
56 : virtual ~CompareLine();
57 :
58 : virtual sal_uLong GetHashValue() const = 0;
59 : virtual bool Compare( const CompareLine& rLine ) const = 0;
60 : };
61 :
62 : class CompareData
63 : {
64 : size_t* pIndex;
65 : bool* pChangedFlag;
66 :
67 : protected:
68 : vector< CompareLine* > aLines;
69 : sal_uLong nSttLineNum;
70 :
71 : // Truncate beginning and end and add all others to the LinesArray
72 : virtual void CheckRanges( CompareData& ) = 0;
73 :
74 : public:
75 : CompareData();
76 : virtual ~CompareData();
77 :
78 : // Are there differences?
79 : bool HasDiffs( const CompareData& rData ) const;
80 :
81 : // Triggers the comparison and creation of two documents
82 : void CompareLines( CompareData& rData );
83 : // Display the differences - calls the methods ShowInsert and ShowDelete.
84 : // These are passed the start and end line number.
85 : // Displaying the actually content is to be handled by the subclass!
86 : sal_uLong ShowDiffs( const CompareData& rData );
87 :
88 : virtual void ShowInsert( sal_uLong nStt, sal_uLong nEnd );
89 : virtual void ShowDelete( const CompareData& rData, sal_uLong nStt,
90 : sal_uLong nEnd, sal_uLong nInsPos );
91 : virtual void CheckForChangesInLine( const CompareData& rData,
92 : sal_uLong& nStt, sal_uLong& nEnd,
93 : sal_uLong& nThisStt, sal_uLong& nThisEnd );
94 :
95 : // Set non-ambiguous index for a line. Same lines have the same index, even in the other CompareData!
96 : void SetIndex( size_t nLine, size_t nIndex );
97 0 : size_t GetIndex( size_t nLine ) const
98 0 : { return nLine < aLines.size() ? pIndex[ nLine ] : 0; }
99 :
100 : // Set/get of a line has changed
101 : void SetChanged( size_t nLine, bool bFlag = true );
102 0 : bool GetChanged( size_t nLine ) const
103 : {
104 0 : return (pChangedFlag && nLine < aLines.size())
105 0 : ? pChangedFlag[ nLine ]
106 0 : : 0;
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 :
177 : static void CountDifference( const CompareData& rData, sal_uLong* pCounts );
178 : static void SetDiscard( const CompareData& rData,
179 : sal_Char* pDiscard, sal_uLong* pCounts );
180 : static void CheckDiscard( sal_uLong nLen, sal_Char* pDiscard );
181 : static sal_uLong SetChangedFlag( CompareData& rData, sal_Char* pDiscard, int bFirst );
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;
211 0 : virtual int GetLen1() const { return nLen1; }
212 0 : virtual int GetLen2() const { 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 : ~WordArrayComparator();
227 :
228 : virtual bool Compare( int nIdx1, int nIdx2 ) const;
229 0 : virtual int GetLen1() const { return nCnt1; }
230 0 : virtual int GetLen2() const { 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;
247 0 : virtual int GetLen1() const { return pTxtNd1->GetTxt().Len(); }
248 0 : virtual int GetLen2() const { return pTxtNd2->GetTxt().Len(); }
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 algrithm 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 :
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, "wo ist die 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 : }
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 : }
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 0 : while (1)
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 0 : while (1)
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++, 0 );
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 : }
942 :
943 0 : pData = &rData2;
944 0 : pOtherData = &rData1;
945 : }
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;
956 : virtual bool Compare( const CompareLine& rLine ) const;
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 : String 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& );
983 : virtual void ShowInsert( sal_uLong nStt, sal_uLong nEnd );
984 : virtual void ShowDelete( const CompareData& rData, sal_uLong nStt,
985 : sal_uLong nEnd, sal_uLong nInsPos );
986 :
987 : virtual void CheckForChangesInLine( const CompareData& rData,
988 : sal_uLong& nStt, sal_uLong& nEnd,
989 : sal_uLong& nThisStt, sal_uLong& nThisEnd );
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 : String sStr( GetText() );
1032 0 : for( xub_StrLen n = 0; n < sStr.Len(); ++n )
1033 0 : ( nRet <<= 1 ) += sStr.GetChar( 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 String SimpleTableToText(const SwNode &rNode)
1074 : {
1075 0 : String 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.Len())
1083 : {
1084 0 : sRet.Append( '\n' );
1085 : }
1086 0 : sRet.Append( aIdx.GetNode().GetTxtNode()->GetExpandTxt() );
1087 : }
1088 0 : ++aIdx;
1089 : }
1090 0 : return sRet;
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 : 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 : bRet = pSrcTOX && pDstTOX
1154 0 : && pSrcTOX->GetType() == pDstTOX->GetType()
1155 0 : && pSrcTOX->GetTitle() == pDstTOX->GetTitle()
1156 0 : && pSrcTOX->GetTypeName() == pDstTOX->GetTypeName()
1157 : // && pSrcTOX->GetTOXName() == pDstTOX->GetTOXName()
1158 0 : ;
1159 : }
1160 0 : break;
1161 :
1162 : case DDE_LINK_SECTION:
1163 : case FILE_LINK_SECTION:
1164 : 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 : String SwCompareLine::GetText() const
1189 : {
1190 0 : String 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 = SimpleTableToText(rNode);
1200 0 : sRet.InsertAscii( "Tabelle: ", 0 );
1201 : }
1202 0 : break;
1203 :
1204 : case ND_SECTIONNODE:
1205 : {
1206 0 : sRet.AssignAscii( RTL_CONSTASCII_STRINGPARAM( "Section - Node:" ));
1207 :
1208 0 : const SwSectionNode& rSNd = (SwSectionNode&)rNode;
1209 0 : const SwSection& rSect = rSNd.GetSection();
1210 0 : switch( rSect.GetType() )
1211 : {
1212 : case CONTENT_SECTION:
1213 0 : if( rSect.IsProtect() )
1214 : sRet.Append( String::CreateFromInt32(
1215 0 : rSNd.EndOfSectionIndex() - rSNd.GetIndex() ));
1216 0 : break;
1217 :
1218 : case TOX_HEADER_SECTION:
1219 : case TOX_CONTENT_SECTION:
1220 : {
1221 0 : const SwTOXBase* pTOX = rSect.GetTOXBase();
1222 0 : if( pTOX )
1223 0 : sRet.Append( pTOX->GetTitle() )
1224 0 : .Append( pTOX->GetTypeName() )
1225 : // .Append( pTOX->GetTOXName() )
1226 0 : .Append( String::CreateFromInt32( pTOX->GetType() ));
1227 : }
1228 0 : break;
1229 :
1230 : case DDE_LINK_SECTION:
1231 : case FILE_LINK_SECTION:
1232 0 : sRet += rSect.GetLinkFileName();
1233 0 : break;
1234 : }
1235 : }
1236 0 : break;
1237 :
1238 : case ND_GRFNODE:
1239 0 : sRet.AssignAscii( RTL_CONSTASCII_STRINGPARAM( "Grafik - Node:" ));
1240 0 : break;
1241 : case ND_OLENODE:
1242 0 : sRet.AssignAscii( RTL_CONSTASCII_STRINGPARAM( "OLE - Node:" ));
1243 0 : break;
1244 : }
1245 0 : return sRet;
1246 : }
1247 :
1248 0 : sal_uLong SwCompareLine::GetTxtNodeHashValue( const SwTxtNode& rNd, sal_uLong nVal )
1249 : {
1250 0 : String sStr( rNd.GetExpandTxt() );
1251 0 : for( xub_StrLen n = 0; n < sStr.Len(); ++n )
1252 0 : ( nVal <<= 1 ) += sStr.GetChar( n );
1253 0 : return nVal;
1254 : }
1255 :
1256 0 : bool SwCompareLine::CompareTxtNd( const SwTxtNode& rDstNd,
1257 : const SwTxtNode& rSrcNd )
1258 : {
1259 0 : bool bRet = false;
1260 : // Very simple at first
1261 0 : if( rDstNd.GetTxt() == rSrcNd.GetTxt() )
1262 : {
1263 : // The text is the same, but are the "special attributes" (0xFF) also the same?
1264 0 : bRet = true;
1265 : }
1266 0 : return bRet;
1267 : }
1268 :
1269 0 : bool SwCompareLine::ChangesInLine( const SwCompareLine& rLine,
1270 : SwPaM *& rpInsRing, SwPaM*& rpDelRing ) const
1271 : {
1272 0 : bool bRet = false;
1273 :
1274 : // Only compare textnodes
1275 0 : if( ND_TEXTNODE == rNode.GetNodeType() &&
1276 0 : ND_TEXTNODE == rLine.GetNode().GetNodeType() )
1277 : {
1278 0 : SwTxtNode& rDstNd = *(SwTxtNode*)rNode.GetTxtNode();
1279 0 : const SwTxtNode& rSrcNd = *rLine.GetNode().GetTxtNode();
1280 0 : SwDoc* pDstDoc = rDstNd.GetDoc();
1281 :
1282 0 : int nLcsLen = 0;
1283 :
1284 0 : int nDstLen = rDstNd.GetTxt().Len();
1285 0 : int nSrcLen = rSrcNd.GetTxt().Len();
1286 :
1287 0 : int nMinLen = std::min( nDstLen , nSrcLen );
1288 0 : int nAvgLen = ( nDstLen + nSrcLen )/2;
1289 :
1290 0 : int *pLcsDst = new int[ nMinLen + 1 ];
1291 0 : int *pLcsSrc = new int[ nMinLen + 1 ];
1292 :
1293 0 : if( CmpOptions.eCmpMode == SVX_CMP_BY_WORD )
1294 : {
1295 0 : int *pTmpLcsDst = new int[ nMinLen + 1 ];
1296 0 : int *pTmpLcsSrc = new int[ nMinLen + 1 ];
1297 :
1298 0 : WordArrayComparator aCmp( &rDstNd, &rSrcNd );
1299 :
1300 0 : LgstCommonSubseq aSeq( aCmp );
1301 :
1302 0 : nLcsLen = aSeq.Find( pTmpLcsDst, pTmpLcsSrc );
1303 :
1304 0 : if( CmpOptions.nIgnoreLen )
1305 : {
1306 : nLcsLen = aSeq.IgnoreIsolatedPieces( pTmpLcsDst, pTmpLcsSrc,
1307 : aCmp.GetLen1(), aCmp.GetLen2(),
1308 0 : nLcsLen, CmpOptions.nIgnoreLen );
1309 : }
1310 :
1311 : nLcsLen = aCmp.GetCharSequence( pTmpLcsDst, pTmpLcsSrc,
1312 0 : pLcsDst, pLcsSrc, nLcsLen );
1313 :
1314 0 : delete[] pTmpLcsDst;
1315 0 : delete[] pTmpLcsSrc;
1316 : }
1317 : else
1318 : {
1319 0 : CharArrayComparator aCmp( &rDstNd, &rSrcNd );
1320 0 : LgstCommonSubseq aSeq( aCmp );
1321 :
1322 0 : nLcsLen = aSeq.Find( pLcsDst, pLcsSrc );
1323 :
1324 0 : if( CmpOptions.nIgnoreLen )
1325 : {
1326 : nLcsLen = aSeq.IgnoreIsolatedPieces( pLcsDst, pLcsSrc, nDstLen,
1327 : nSrcLen, nLcsLen,
1328 0 : CmpOptions.nIgnoreLen );
1329 0 : }
1330 : }
1331 :
1332 : // find the sum of the squares of the continuous substrings
1333 0 : int nSqSum = 0;
1334 0 : int nCnt = 1;
1335 0 : for( int i = 0; i < nLcsLen; i++ )
1336 : {
1337 0 : if( i != nLcsLen - 1 && pLcsDst[i] + 1 == pLcsDst[i + 1]
1338 0 : && pLcsSrc[i] + 1 == pLcsSrc[i + 1] )
1339 : {
1340 0 : nCnt++;
1341 : }
1342 : else
1343 : {
1344 0 : nSqSum += nCnt*nCnt;
1345 0 : nCnt = 1;
1346 : }
1347 : }
1348 :
1349 : // Don't compare if there aren't enough similarities
1350 0 : if ( nAvgLen >= 8 && nSqSum*32 < nAvgLen*nAvgLen )
1351 : {
1352 0 : return false;
1353 : }
1354 :
1355 : // Show the differences
1356 0 : int nSkip = 0;
1357 0 : for( int i = 0; i <= nLcsLen; i++ )
1358 : {
1359 0 : int nDstFrom = i ? (pLcsDst[i - 1] + 1) : 0;
1360 0 : int nDstTo = ( i == nLcsLen ) ? nDstLen : pLcsDst[i];
1361 0 : int nSrcFrom = i ? (pLcsSrc[i - 1] + 1) : 0;
1362 0 : int nSrcTo = ( i == nLcsLen ) ? nSrcLen : pLcsSrc[i];
1363 :
1364 0 : SwPaM aPam( rDstNd, nDstTo + nSkip );
1365 :
1366 0 : if ( nDstFrom < nDstTo )
1367 : {
1368 0 : SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpInsRing );
1369 0 : if( !rpInsRing )
1370 0 : rpInsRing = pTmp;
1371 0 : pTmp->SetMark();
1372 0 : pTmp->GetMark()->nContent = nDstFrom + nSkip;
1373 : }
1374 :
1375 0 : if ( nSrcFrom < nSrcTo )
1376 : {
1377 0 : sal_Bool bUndo = pDstDoc->GetIDocumentUndoRedo().DoesUndo();
1378 0 : pDstDoc->GetIDocumentUndoRedo().DoUndo( sal_False );
1379 0 : SwPaM aCpyPam( rSrcNd, nSrcFrom );
1380 0 : aCpyPam.SetMark();
1381 0 : aCpyPam.GetPoint()->nContent = nSrcTo;
1382 0 : aCpyPam.GetDoc()->CopyRange( aCpyPam, *aPam.GetPoint(),
1383 0 : false );
1384 0 : pDstDoc->GetIDocumentUndoRedo().DoUndo( bUndo );
1385 :
1386 0 : SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpDelRing );
1387 0 : if( !rpDelRing )
1388 0 : rpDelRing = pTmp;
1389 :
1390 0 : pTmp->SetMark();
1391 0 : pTmp->GetMark()->nContent = nDstTo + nSkip;
1392 0 : nSkip += nSrcTo - nSrcFrom;
1393 :
1394 0 : if( rpInsRing )
1395 : {
1396 0 : SwPaM* pCorr = (SwPaM*)rpInsRing->GetPrev();
1397 0 : if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1398 0 : *pCorr->GetPoint() = *pTmp->GetMark();
1399 0 : }
1400 : }
1401 0 : }
1402 :
1403 0 : delete[] pLcsDst;
1404 0 : delete[] pLcsSrc;
1405 :
1406 0 : bRet = true;
1407 : }
1408 :
1409 0 : return bRet;
1410 : }
1411 :
1412 0 : SwCompareData::~SwCompareData()
1413 : {
1414 0 : if( pDelRing )
1415 : {
1416 0 : while( pDelRing->GetNext() != pDelRing )
1417 0 : delete pDelRing->GetNext();
1418 0 : delete pDelRing;
1419 : }
1420 0 : if( pInsRing )
1421 : {
1422 0 : while( pInsRing->GetNext() != pInsRing )
1423 0 : delete pInsRing->GetNext();
1424 0 : delete pInsRing;
1425 : }
1426 0 : }
1427 :
1428 0 : sal_uLong SwCompareData::NextIdx( const SwNode* pNd )
1429 : {
1430 0 : if( pNd->IsStartNode() )
1431 : {
1432 : const SwSectionNode* pSNd;
1433 0 : if( pNd->IsTableNode() ||
1434 : ( 0 != (pSNd = pNd->GetSectionNode() ) &&
1435 0 : ( CONTENT_SECTION != pSNd->GetSection().GetType() ||
1436 0 : pSNd->GetSection().IsProtect() ) ) )
1437 0 : pNd = pNd->EndOfSectionNode();
1438 : }
1439 0 : return pNd->GetIndex() + 1;
1440 : }
1441 :
1442 0 : sal_uLong SwCompareData::PrevIdx( const SwNode* pNd )
1443 : {
1444 0 : if( pNd->IsEndNode() )
1445 : {
1446 : const SwSectionNode* pSNd;
1447 0 : if( pNd->StartOfSectionNode()->IsTableNode() ||
1448 0 : ( 0 != (pSNd = pNd->StartOfSectionNode()->GetSectionNode() ) &&
1449 0 : ( CONTENT_SECTION != pSNd->GetSection().GetType() ||
1450 0 : pSNd->GetSection().IsProtect() ) ) )
1451 0 : pNd = pNd->StartOfSectionNode();
1452 : }
1453 0 : return pNd->GetIndex() - 1;
1454 : }
1455 :
1456 0 : void SwCompareData::CheckRanges( CompareData& rData )
1457 : {
1458 0 : const SwNodes& rSrcNds = ((SwCompareData&)rData).rDoc.GetNodes();
1459 0 : const SwNodes& rDstNds = rDoc.GetNodes();
1460 :
1461 0 : const SwNode& rSrcEndNd = rSrcNds.GetEndOfContent();
1462 0 : const SwNode& rDstEndNd = rDstNds.GetEndOfContent();
1463 :
1464 0 : sal_uLong nSrcSttIdx = NextIdx( rSrcEndNd.StartOfSectionNode() );
1465 0 : sal_uLong nSrcEndIdx = rSrcEndNd.GetIndex();
1466 :
1467 0 : sal_uLong nDstSttIdx = NextIdx( rDstEndNd.StartOfSectionNode() );
1468 0 : sal_uLong nDstEndIdx = rDstEndNd.GetIndex();
1469 :
1470 0 : while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1471 : {
1472 0 : const SwNode* pSrcNd = rSrcNds[ nSrcSttIdx ];
1473 0 : const SwNode* pDstNd = rDstNds[ nDstSttIdx ];
1474 0 : if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1475 0 : break;
1476 :
1477 0 : nSrcSttIdx = NextIdx( pSrcNd );
1478 0 : nDstSttIdx = NextIdx( pDstNd );
1479 : }
1480 :
1481 0 : nSrcEndIdx = PrevIdx( &rSrcEndNd );
1482 0 : nDstEndIdx = PrevIdx( &rDstEndNd );
1483 0 : while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1484 : {
1485 0 : const SwNode* pSrcNd = rSrcNds[ nSrcEndIdx ];
1486 0 : const SwNode* pDstNd = rDstNds[ nDstEndIdx ];
1487 0 : if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1488 0 : break;
1489 :
1490 0 : nSrcEndIdx = PrevIdx( pSrcNd );
1491 0 : nDstEndIdx = PrevIdx( pDstNd );
1492 : }
1493 :
1494 0 : while( nSrcSttIdx <= nSrcEndIdx )
1495 : {
1496 0 : const SwNode* pNd = rSrcNds[ nSrcSttIdx ];
1497 0 : rData.InsertLine( new SwCompareLine( *pNd ) );
1498 0 : nSrcSttIdx = NextIdx( pNd );
1499 : }
1500 :
1501 0 : while( nDstSttIdx <= nDstEndIdx )
1502 : {
1503 0 : const SwNode* pNd = rDstNds[ nDstSttIdx ];
1504 0 : InsertLine( new SwCompareLine( *pNd ) );
1505 0 : nDstSttIdx = NextIdx( pNd );
1506 : }
1507 0 : }
1508 :
1509 0 : void SwCompareData::ShowInsert( sal_uLong nStt, sal_uLong nEnd )
1510 : {
1511 0 : SwPaM* pTmp = new SwPaM( ((SwCompareLine*)GetLine( nStt ))->GetNode(), 0,
1512 0 : ((SwCompareLine*)GetLine( nEnd-1 ))->GetEndNode(), 0,
1513 0 : pInsRing );
1514 0 : if( !pInsRing )
1515 0 : pInsRing = pTmp;
1516 :
1517 : // #i65201#: These SwPaMs are calculated smaller than needed, see comment below
1518 :
1519 0 : }
1520 :
1521 0 : void SwCompareData::ShowDelete( const CompareData& rData, sal_uLong nStt,
1522 : sal_uLong nEnd, sal_uLong nInsPos )
1523 : {
1524 : SwNodeRange aRg(
1525 0 : ((SwCompareLine*)rData.GetLine( nStt ))->GetNode(), 0,
1526 0 : ((SwCompareLine*)rData.GetLine( nEnd-1 ))->GetEndNode(), 1 );
1527 :
1528 0 : sal_uInt16 nOffset = 0;
1529 0 : const CompareLine* pLine = 0;
1530 0 : if( nInsPos >= 1 )
1531 : {
1532 0 : if( GetLineCount() == nInsPos )
1533 : {
1534 0 : pLine = GetLine( nInsPos-1 );
1535 0 : nOffset = 1;
1536 : }
1537 : else
1538 0 : pLine = GetLine( nInsPos );
1539 : }
1540 :
1541 : const SwNode* pLineNd;
1542 0 : if( pLine )
1543 : {
1544 0 : if( nOffset )
1545 0 : pLineNd = &((SwCompareLine*)pLine)->GetEndNode();
1546 : else
1547 0 : pLineNd = &((SwCompareLine*)pLine)->GetNode();
1548 : }
1549 : else
1550 : {
1551 0 : pLineNd = &rDoc.GetNodes().GetEndOfContent();
1552 0 : nOffset = 0;
1553 : }
1554 :
1555 0 : SwNodeIndex aInsPos( *pLineNd, nOffset );
1556 0 : SwNodeIndex aSavePos( aInsPos, -1 );
1557 :
1558 0 : ((SwCompareData&)rData).rDoc.CopyWithFlyInFly( aRg, 0, aInsPos );
1559 0 : rDoc.SetModified();
1560 0 : ++aSavePos;
1561 :
1562 : // #i65201#: These SwPaMs are calculated when the (old) delete-redlines are hidden,
1563 : // they will be inserted when the delete-redlines are shown again.
1564 : // To avoid unwanted insertions of delete-redlines into these new redlines, what happens
1565 : // especially at the end of the document, I reduce the SwPaM by one node.
1566 : // Before the new redlines are inserted, they have to expand again.
1567 0 : SwPaM* pTmp = new SwPaM( aSavePos.GetNode(), aInsPos.GetNode(), 0, -1, pDelRing );
1568 0 : if( !pDelRing )
1569 0 : pDelRing = pTmp;
1570 :
1571 0 : if( pInsRing )
1572 : {
1573 0 : SwPaM* pCorr = (SwPaM*)pInsRing->GetPrev();
1574 0 : if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1575 : {
1576 0 : SwNodeIndex aTmpPos( pTmp->GetMark()->nNode, -1 );
1577 0 : *pCorr->GetPoint() = SwPosition( aTmpPos );
1578 : }
1579 0 : }
1580 0 : }
1581 :
1582 0 : void SwCompareData::CheckForChangesInLine( const CompareData& rData,
1583 : sal_uLong& rStt, sal_uLong& rEnd,
1584 : sal_uLong& rThisStt, sal_uLong& rThisEnd )
1585 : {
1586 : LineArrayComparator aCmp( (CompareData&)*this, rData, rThisStt, rThisEnd,
1587 0 : rStt, rEnd );
1588 :
1589 0 : int nMinLen = std::min( aCmp.GetLen1(), aCmp.GetLen2() );
1590 0 : int *pLcsDst = new int[ nMinLen ];
1591 0 : int *pLcsSrc = new int[ nMinLen ];
1592 :
1593 0 : FastCommonSubseq subseq( aCmp );
1594 0 : int nLcsLen = subseq.Find( pLcsDst, pLcsSrc );
1595 0 : for (int i = 0; i <= nLcsLen; i++)
1596 : {
1597 : // Beginning of inserted lines (inclusive)
1598 0 : int nDstFrom = i ? pLcsDst[i - 1] + 1 : 0;
1599 : // End of inserted lines (exclusive)
1600 0 : int nDstTo = ( i == nLcsLen ) ? aCmp.GetLen1() : pLcsDst[i];
1601 : // Begining of deleted lines (inclusive)
1602 0 : int nSrcFrom = i ? pLcsSrc[i - 1] + 1 : 0;
1603 : // End of deleted lines (exclusive)
1604 0 : int nSrcTo = ( i == nLcsLen ) ? aCmp.GetLen2() : pLcsSrc[i];
1605 :
1606 0 : if( i )
1607 : {
1608 0 : SwCompareLine* pDstLn = (SwCompareLine*)GetLine( rThisStt + nDstFrom - 1 );
1609 0 : SwCompareLine* pSrcLn = (SwCompareLine*)rData.GetLine( rStt + nSrcFrom - 1 );
1610 :
1611 : // Show differences in detail for lines that
1612 : // were matched as only slightly different
1613 0 : if( !pDstLn->ChangesInLine( *pSrcLn, pInsRing, pDelRing ) )
1614 : {
1615 0 : ShowInsert( rThisStt + nDstFrom - 1, rThisStt + nDstFrom );
1616 : ShowDelete( rData, rStt + nSrcFrom - 1, rStt + nSrcFrom,
1617 0 : rThisStt + nDstFrom );
1618 : }
1619 : }
1620 :
1621 : // Lines missing from source are inserted
1622 0 : if( nDstFrom != nDstTo )
1623 : {
1624 0 : ShowInsert( rThisStt + nDstFrom, rThisStt + nDstTo );
1625 : }
1626 :
1627 : // Lines missing from destination are deleted
1628 0 : if( nSrcFrom != nSrcTo )
1629 : {
1630 0 : ShowDelete( rData, rStt + nSrcFrom, rStt + nSrcTo, rThisStt + nDstTo );
1631 : }
1632 0 : }
1633 0 : }
1634 :
1635 0 : void SwCompareData::SetRedlinesToDoc( sal_Bool bUseDocInfo )
1636 : {
1637 0 : SwPaM* pTmp = pDelRing;
1638 :
1639 : // get the Author / TimeStamp from the "other" document info
1640 0 : sal_uInt16 nAuthor = rDoc.GetRedlineAuthor();
1641 0 : DateTime aTimeStamp( DateTime::SYSTEM );
1642 0 : SwDocShell *pDocShell(rDoc.GetDocShell());
1643 : OSL_ENSURE(pDocShell, "no SwDocShell");
1644 0 : if (pDocShell) {
1645 : uno::Reference<document::XDocumentPropertiesSupplier> xDPS(
1646 0 : pDocShell->GetModel(), uno::UNO_QUERY_THROW);
1647 : uno::Reference<document::XDocumentProperties> xDocProps(
1648 0 : xDPS->getDocumentProperties());
1649 : OSL_ENSURE(xDocProps.is(), "Doc has no DocumentProperties");
1650 :
1651 0 : if( bUseDocInfo && xDocProps.is() ) {
1652 0 : String aTmp( 1 == xDocProps->getEditingCycles()
1653 0 : ? xDocProps->getAuthor()
1654 0 : : xDocProps->getModifiedBy() );
1655 0 : util::DateTime uDT( 1 == xDocProps->getEditingCycles()
1656 0 : ? xDocProps->getCreationDate()
1657 0 : : xDocProps->getModificationDate() );
1658 0 : Date d(uDT.Day, uDT.Month, uDT.Year);
1659 0 : Time t(uDT.Hours, uDT.Minutes, uDT.Seconds, uDT.HundredthSeconds);
1660 0 : DateTime aDT(d,t);
1661 :
1662 0 : if( aTmp.Len() )
1663 : {
1664 0 : nAuthor = rDoc.InsertRedlineAuthor( aTmp );
1665 0 : aTimeStamp = aDT;
1666 0 : }
1667 0 : }
1668 : }
1669 :
1670 0 : if( pTmp )
1671 : {
1672 : SwRedlineData aRedlnData( nsRedlineType_t::REDLINE_DELETE, nAuthor, aTimeStamp,
1673 0 : aEmptyStr, 0, 0 );
1674 0 : do {
1675 : // #i65201#: Expand again, see comment above.
1676 0 : if( pTmp->GetPoint()->nContent == 0 )
1677 : {
1678 0 : pTmp->GetPoint()->nNode++;
1679 0 : pTmp->GetPoint()->nContent.Assign( pTmp->GetCntntNode(), 0 );
1680 : }
1681 : // #i101009#
1682 : // prevent redlines that end on structural end node
1683 0 : if (& rDoc.GetNodes().GetEndOfContent() ==
1684 0 : & pTmp->GetPoint()->nNode.GetNode())
1685 : {
1686 0 : pTmp->GetPoint()->nNode--;
1687 0 : SwCntntNode *const pContentNode( pTmp->GetCntntNode() );
1688 0 : pTmp->GetPoint()->nContent.Assign( pContentNode,
1689 0 : (pContentNode) ? pContentNode->Len() : 0 );
1690 : }
1691 :
1692 0 : rDoc.DeleteRedline( *pTmp, false, USHRT_MAX );
1693 :
1694 0 : if (rDoc.GetIDocumentUndoRedo().DoesUndo())
1695 : {
1696 0 : SwUndo *const pUndo(new SwUndoCompDoc( *pTmp, sal_False )) ;
1697 0 : rDoc.GetIDocumentUndoRedo().AppendUndo(pUndo);
1698 : }
1699 0 : rDoc.AppendRedline( new SwRedline( aRedlnData, *pTmp ), true );
1700 :
1701 0 : } while( pDelRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1702 : }
1703 :
1704 0 : pTmp = pInsRing;
1705 0 : if( pTmp )
1706 : {
1707 0 : do {
1708 0 : if( pTmp->GetPoint()->nContent == 0 )
1709 : {
1710 0 : pTmp->GetPoint()->nNode++;
1711 0 : pTmp->GetPoint()->nContent.Assign( pTmp->GetCntntNode(), 0 );
1712 : }
1713 : // #i101009#
1714 : // prevent redlines that end on structural end node
1715 0 : if (& rDoc.GetNodes().GetEndOfContent() ==
1716 0 : & pTmp->GetPoint()->nNode.GetNode())
1717 : {
1718 0 : pTmp->GetPoint()->nNode--;
1719 0 : SwCntntNode *const pContentNode( pTmp->GetCntntNode() );
1720 0 : pTmp->GetPoint()->nContent.Assign( pContentNode,
1721 0 : (pContentNode) ? pContentNode->Len() : 0 );
1722 : }
1723 0 : } while( pInsRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1724 : SwRedlineData aRedlnData( nsRedlineType_t::REDLINE_INSERT, nAuthor, aTimeStamp,
1725 0 : aEmptyStr, 0, 0 );
1726 :
1727 : // combine consecutive
1728 0 : if( pTmp->GetNext() != pInsRing )
1729 : {
1730 : const SwCntntNode* pCNd;
1731 0 : do {
1732 0 : SwPosition& rSttEnd = *pTmp->End(),
1733 0 : & rEndStt = *((SwPaM*)pTmp->GetNext())->Start();
1734 0 : if( rSttEnd == rEndStt ||
1735 0 : (!rEndStt.nContent.GetIndex() &&
1736 0 : rEndStt.nNode.GetIndex() - 1 == rSttEnd.nNode.GetIndex() &&
1737 0 : 0 != ( pCNd = rSttEnd.nNode.GetNode().GetCntntNode() )
1738 0 : ? rSttEnd.nContent.GetIndex() == pCNd->Len()
1739 0 : : 0 ))
1740 : {
1741 0 : if( pTmp->GetNext() == pInsRing )
1742 : {
1743 : // are consecutive, so combine
1744 0 : rEndStt = *pTmp->Start();
1745 0 : delete pTmp;
1746 0 : pTmp = pInsRing;
1747 : }
1748 : else
1749 : {
1750 : // are consecutive, so combine
1751 0 : rSttEnd = *((SwPaM*)pTmp->GetNext())->End();
1752 0 : delete pTmp->GetNext();
1753 : }
1754 : }
1755 : else
1756 0 : pTmp = (SwPaM*)pTmp->GetNext();
1757 : } while( pInsRing != pTmp );
1758 : }
1759 :
1760 0 : do {
1761 0 : if( rDoc.AppendRedline( new SwRedline( aRedlnData, *pTmp ), true) &&
1762 0 : rDoc.GetIDocumentUndoRedo().DoesUndo())
1763 : {
1764 0 : SwUndo *const pUndo(new SwUndoCompDoc( *pTmp, sal_True ));
1765 0 : rDoc.GetIDocumentUndoRedo().AppendUndo(pUndo);
1766 : }
1767 0 : } while( pInsRing != ( pTmp = (SwPaM*)pTmp->GetNext() ));
1768 : }
1769 0 : }
1770 :
1771 : // Returns (the difference count?) if something is different
1772 0 : long SwDoc::CompareDoc( const SwDoc& rDoc )
1773 : {
1774 0 : if( &rDoc == this )
1775 0 : return 0;
1776 :
1777 0 : long nRet = 0;
1778 :
1779 : // Get comparison options
1780 0 : CmpOptions.eCmpMode = SW_MOD()->GetCompareMode();
1781 0 : if( CmpOptions.eCmpMode == SVX_CMP_AUTO )
1782 : {
1783 0 : if( getRsidRoot() == rDoc.getRsidRoot() )
1784 : {
1785 0 : CmpOptions.eCmpMode = SVX_CMP_BY_CHAR;
1786 0 : CmpOptions.bUseRsid = true;
1787 0 : CmpOptions.nIgnoreLen = 2;
1788 : }
1789 : else
1790 : {
1791 0 : CmpOptions.eCmpMode = SVX_CMP_BY_WORD;
1792 0 : CmpOptions.bUseRsid = false;
1793 0 : CmpOptions.nIgnoreLen = 3;
1794 : }
1795 : }
1796 : else
1797 : {
1798 0 : CmpOptions.bUseRsid = getRsidRoot() == rDoc.getRsidRoot() && SW_MOD()->IsUseRsid();
1799 0 : CmpOptions.nIgnoreLen = SW_MOD()->IsIgnorePieces() ? SW_MOD()->GetPieceLen() : 0;
1800 : }
1801 :
1802 0 : GetIDocumentUndoRedo().StartUndo(UNDO_EMPTY, NULL);
1803 0 : sal_Bool bDocWasModified = IsModified();
1804 0 : SwDoc& rSrcDoc = (SwDoc&)rDoc;
1805 0 : sal_Bool bSrcModified = rSrcDoc.IsModified();
1806 :
1807 0 : RedlineMode_t eSrcRedlMode = rSrcDoc.GetRedlineMode();
1808 0 : rSrcDoc.SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_INSERT );
1809 0 : SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_ON | nsRedlineMode_t::REDLINE_SHOW_INSERT));
1810 :
1811 0 : SwCompareData aD0( rSrcDoc );
1812 0 : SwCompareData aD1( *this );
1813 :
1814 0 : aD1.CompareLines( aD0 );
1815 :
1816 0 : nRet = aD1.ShowDiffs( aD0 );
1817 :
1818 0 : if( nRet )
1819 : {
1820 : SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_ON |
1821 0 : nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1822 :
1823 0 : aD1.SetRedlinesToDoc( !bDocWasModified );
1824 0 : SetModified();
1825 : }
1826 :
1827 0 : rSrcDoc.SetRedlineMode( eSrcRedlMode );
1828 0 : SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
1829 :
1830 0 : if( !bSrcModified )
1831 0 : rSrcDoc.ResetModified();
1832 :
1833 0 : GetIDocumentUndoRedo().EndUndo(UNDO_EMPTY, NULL);
1834 :
1835 0 : return nRet;
1836 : }
1837 :
1838 0 : class _SaveMergeRedlines : public Ring
1839 : {
1840 : const SwRedline* pSrcRedl;
1841 : SwRedline* pDestRedl;
1842 : public:
1843 : _SaveMergeRedlines( const SwNode& rDstNd,
1844 : const SwRedline& rSrcRedl, Ring* pRing );
1845 : sal_uInt16 InsertRedline();
1846 :
1847 : SwRedline* GetDestRedline() { return pDestRedl; }
1848 : };
1849 :
1850 0 : _SaveMergeRedlines::_SaveMergeRedlines( const SwNode& rDstNd,
1851 : const SwRedline& rSrcRedl, Ring* pRing )
1852 0 : : Ring( pRing ), pSrcRedl( &rSrcRedl )
1853 : {
1854 0 : SwPosition aPos( rDstNd );
1855 :
1856 0 : const SwPosition* pStt = rSrcRedl.Start();
1857 0 : if( rDstNd.IsCntntNode() )
1858 0 : aPos.nContent.Assign( ((SwCntntNode*)&rDstNd), pStt->nContent.GetIndex() );
1859 0 : pDestRedl = new SwRedline( rSrcRedl.GetRedlineData(), aPos );
1860 :
1861 0 : if( nsRedlineType_t::REDLINE_DELETE == pDestRedl->GetType() )
1862 : {
1863 : // mark the area as deleted
1864 0 : const SwPosition* pEnd = pStt == rSrcRedl.GetPoint()
1865 0 : ? rSrcRedl.GetMark()
1866 0 : : rSrcRedl.GetPoint();
1867 :
1868 0 : pDestRedl->SetMark();
1869 0 : pDestRedl->GetPoint()->nNode += pEnd->nNode.GetIndex() -
1870 0 : pStt->nNode.GetIndex();
1871 0 : pDestRedl->GetPoint()->nContent.Assign( pDestRedl->GetCntntNode(),
1872 0 : pEnd->nContent.GetIndex() );
1873 0 : }
1874 0 : }
1875 :
1876 0 : sal_uInt16 _SaveMergeRedlines::InsertRedline()
1877 : {
1878 0 : sal_uInt16 nIns = 0;
1879 0 : SwDoc* pDoc = pDestRedl->GetDoc();
1880 :
1881 0 : if( nsRedlineType_t::REDLINE_INSERT == pDestRedl->GetType() )
1882 : {
1883 : // the part was inserted so copy it from the SourceDoc
1884 0 : ::sw::UndoGuard const undoGuard(pDoc->GetIDocumentUndoRedo());
1885 :
1886 0 : SwNodeIndex aSaveNd( pDestRedl->GetPoint()->nNode, -1 );
1887 0 : xub_StrLen nSaveCnt = pDestRedl->GetPoint()->nContent.GetIndex();
1888 :
1889 0 : RedlineMode_t eOld = pDoc->GetRedlineMode();
1890 0 : pDoc->SetRedlineMode_intern((RedlineMode_t)(eOld | nsRedlineMode_t::REDLINE_IGNORE));
1891 :
1892 0 : pSrcRedl->GetDoc()->CopyRange(
1893 : *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1894 0 : *pDestRedl->GetPoint(), false );
1895 :
1896 0 : pDoc->SetRedlineMode_intern( eOld );
1897 :
1898 0 : pDestRedl->SetMark();
1899 0 : ++aSaveNd;
1900 0 : pDestRedl->GetMark()->nNode = aSaveNd;
1901 0 : pDestRedl->GetMark()->nContent.Assign( aSaveNd.GetNode().GetCntntNode(),
1902 0 : nSaveCnt );
1903 :
1904 0 : if( GetPrev() != this )
1905 : {
1906 0 : SwPaM* pTmpPrev = ((_SaveMergeRedlines*)GetPrev())->pDestRedl;
1907 0 : if( pTmpPrev && *pTmpPrev->GetPoint() == *pDestRedl->GetPoint() )
1908 0 : *pTmpPrev->GetPoint() = *pDestRedl->GetMark();
1909 0 : }
1910 : }
1911 : else
1912 : {
1913 : //JP 21.09.98: Bug 55909
1914 : // If there already is a deleted or inserted one at the same position, we have to split it!
1915 0 : SwPosition* pDStt = pDestRedl->GetMark(),
1916 0 : * pDEnd = pDestRedl->GetPoint();
1917 0 : sal_uInt16 n = 0;
1918 :
1919 : // find the first redline for StartPos
1920 0 : if( !pDoc->GetRedline( *pDStt, &n ) && n )
1921 0 : --n;
1922 :
1923 0 : const SwRedlineTbl& rRedlineTbl = pDoc->GetRedlineTbl();
1924 0 : for( ; n < rRedlineTbl.size(); ++n )
1925 : {
1926 0 : SwRedline* pRedl = rRedlineTbl[ n ];
1927 0 : SwPosition* pRStt = pRedl->Start(),
1928 0 : * pREnd = pRStt == pRedl->GetPoint() ? pRedl->GetMark()
1929 0 : : pRedl->GetPoint();
1930 0 : if( nsRedlineType_t::REDLINE_DELETE == pRedl->GetType() ||
1931 0 : nsRedlineType_t::REDLINE_INSERT == pRedl->GetType() )
1932 : {
1933 0 : SwComparePosition eCmpPos = ComparePosition( *pDStt, *pDEnd, *pRStt, *pREnd );
1934 0 : switch( eCmpPos )
1935 : {
1936 : case POS_COLLIDE_START:
1937 : case POS_BEHIND:
1938 0 : break;
1939 :
1940 : case POS_INSIDE:
1941 : case POS_EQUAL:
1942 0 : delete pDestRedl, pDestRedl = 0;
1943 : // break; -> no break !!!!
1944 :
1945 : case POS_COLLIDE_END:
1946 : case POS_BEFORE:
1947 0 : n = rRedlineTbl.size();
1948 0 : break;
1949 :
1950 : case POS_OUTSIDE:
1951 : {
1952 : SwRedline* pCpyRedl = new SwRedline(
1953 0 : pDestRedl->GetRedlineData(), *pDStt );
1954 0 : pCpyRedl->SetMark();
1955 0 : *pCpyRedl->GetPoint() = *pRStt;
1956 :
1957 : SwUndoCompDoc *const pUndo =
1958 0 : (pDoc->GetIDocumentUndoRedo().DoesUndo())
1959 0 : ? new SwUndoCompDoc( *pCpyRedl ) : 0;
1960 :
1961 : // now modify doc: append redline, undo (and count)
1962 0 : pDoc->AppendRedline( pCpyRedl, true );
1963 0 : if( pUndo )
1964 : {
1965 0 : pDoc->GetIDocumentUndoRedo().AppendUndo(pUndo);
1966 : }
1967 0 : ++nIns;
1968 :
1969 0 : *pDStt = *pREnd;
1970 :
1971 : // we should start over now
1972 0 : n = USHRT_MAX;
1973 : }
1974 0 : break;
1975 :
1976 : case POS_OVERLAP_BEFORE:
1977 0 : *pDEnd = *pRStt;
1978 0 : break;
1979 :
1980 : case POS_OVERLAP_BEHIND:
1981 0 : *pDStt = *pREnd;
1982 0 : break;
1983 : }
1984 : }
1985 0 : else if( *pDEnd <= *pRStt )
1986 0 : break;
1987 : }
1988 :
1989 : }
1990 :
1991 0 : if( pDestRedl )
1992 : {
1993 0 : SwUndoCompDoc *const pUndo = (pDoc->GetIDocumentUndoRedo().DoesUndo())
1994 0 : ? new SwUndoCompDoc( *pDestRedl ) : 0;
1995 :
1996 : // now modify doc: append redline, undo (and count)
1997 0 : bool bRedlineAccepted = pDoc->AppendRedline( pDestRedl, true );
1998 0 : if( pUndo )
1999 : {
2000 0 : pDoc->GetIDocumentUndoRedo().AppendUndo( pUndo );
2001 : }
2002 0 : ++nIns;
2003 :
2004 : // if AppendRedline has deleted our redline, we may not keep a
2005 : // reference to it
2006 0 : if( ! bRedlineAccepted )
2007 0 : pDestRedl = NULL;
2008 : }
2009 0 : return nIns;
2010 : }
2011 :
2012 : // Merge two documents
2013 0 : long SwDoc::MergeDoc( const SwDoc& rDoc )
2014 : {
2015 0 : if( &rDoc == this )
2016 0 : return 0;
2017 :
2018 0 : long nRet = 0;
2019 :
2020 0 : GetIDocumentUndoRedo().StartUndo(UNDO_EMPTY, NULL);
2021 :
2022 0 : SwDoc& rSrcDoc = (SwDoc&)rDoc;
2023 0 : sal_Bool bSrcModified = rSrcDoc.IsModified();
2024 :
2025 0 : RedlineMode_t eSrcRedlMode = rSrcDoc.GetRedlineMode();
2026 0 : rSrcDoc.SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_DELETE );
2027 0 : SetRedlineMode( nsRedlineMode_t::REDLINE_SHOW_DELETE );
2028 :
2029 0 : SwCompareData aD0( rSrcDoc );
2030 0 : SwCompareData aD1( *this );
2031 :
2032 0 : aD1.CompareLines( aD0 );
2033 :
2034 0 : if( !aD1.HasDiffs( aD0 ) )
2035 : {
2036 : // we want to get all redlines from the SourceDoc
2037 :
2038 : // look for all insert redlines from the SourceDoc and determine their position in the DestDoc
2039 0 : _SaveMergeRedlines* pRing = 0;
2040 0 : const SwRedlineTbl& rSrcRedlTbl = rSrcDoc.GetRedlineTbl();
2041 0 : sal_uLong nEndOfExtra = rSrcDoc.GetNodes().GetEndOfExtras().GetIndex();
2042 0 : sal_uLong nMyEndOfExtra = GetNodes().GetEndOfExtras().GetIndex();
2043 0 : for( sal_uInt16 n = 0; n < rSrcRedlTbl.size(); ++n )
2044 : {
2045 0 : const SwRedline* pRedl = rSrcRedlTbl[ n ];
2046 0 : sal_uLong nNd = pRedl->GetPoint()->nNode.GetIndex();
2047 0 : RedlineType_t eType = pRedl->GetType();
2048 0 : if( nEndOfExtra < nNd &&
2049 : ( nsRedlineType_t::REDLINE_INSERT == eType || nsRedlineType_t::REDLINE_DELETE == eType ))
2050 : {
2051 0 : const SwNode* pDstNd = GetNodes()[
2052 0 : nMyEndOfExtra + nNd - nEndOfExtra ];
2053 :
2054 : // Found the positon.
2055 : // Then we also have to insert the redline to the line in the DestDoc.
2056 : _SaveMergeRedlines* pTmp = new _SaveMergeRedlines(
2057 0 : *pDstNd, *pRedl, pRing );
2058 0 : if( !pRing )
2059 0 : pRing = pTmp;
2060 : }
2061 : }
2062 :
2063 0 : if( pRing )
2064 : {
2065 : // Carry over all into DestDoc
2066 0 : rSrcDoc.SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
2067 :
2068 : SetRedlineMode((RedlineMode_t)(
2069 : nsRedlineMode_t::REDLINE_ON |
2070 : nsRedlineMode_t::REDLINE_SHOW_INSERT |
2071 0 : nsRedlineMode_t::REDLINE_SHOW_DELETE));
2072 :
2073 0 : _SaveMergeRedlines* pTmp = pRing;
2074 :
2075 0 : do {
2076 0 : nRet += pTmp->InsertRedline();
2077 0 : } while( pRing != ( pTmp = (_SaveMergeRedlines*)pTmp->GetNext() ));
2078 :
2079 0 : while( pRing != pRing->GetNext() )
2080 0 : delete pRing->GetNext();
2081 0 : delete pRing;
2082 : }
2083 : }
2084 :
2085 0 : rSrcDoc.SetRedlineMode( eSrcRedlMode );
2086 0 : if( !bSrcModified )
2087 0 : rSrcDoc.ResetModified();
2088 :
2089 0 : SetRedlineMode((RedlineMode_t)(nsRedlineMode_t::REDLINE_SHOW_INSERT | nsRedlineMode_t::REDLINE_SHOW_DELETE));
2090 :
2091 0 : GetIDocumentUndoRedo().EndUndo(UNDO_EMPTY, NULL);
2092 :
2093 0 : return nRet;
2094 : }
2095 :
2096 0 : LineArrayComparator::LineArrayComparator( const CompareData &rD1,
2097 : const CompareData &rD2, int nStt1,
2098 : int nEnd1, int nStt2, int nEnd2 )
2099 0 : : rData1( rD1 ), rData2( rD2 ), nFirst1( nStt1 ), nFirst2( nStt2 )
2100 : {
2101 0 : nLen1 = nEnd1 - nStt1;
2102 0 : nLen2 = nEnd2 - nStt2;
2103 0 : }
2104 :
2105 0 : bool LineArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2106 : {
2107 0 : if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= nLen1 || nIdx2 >= nLen2 )
2108 : {
2109 : OSL_ENSURE( 0, "Index out of range!" );
2110 0 : return false;
2111 : }
2112 :
2113 0 : const SwTxtNode *pTxtNd1 = ( ( SwCompareLine* )rData1.GetLine( nFirst1 + nIdx1 ) )->GetNode().GetTxtNode();
2114 0 : const SwTxtNode *pTxtNd2 = ( ( SwCompareLine* )rData2.GetLine( nFirst2 + nIdx2 ) )->GetNode().GetTxtNode();
2115 :
2116 0 : if( !pTxtNd1 || !pTxtNd2
2117 0 : || ( CmpOptions.bUseRsid && !pTxtNd1->CompareParRsid( *pTxtNd2 ) ) )
2118 : {
2119 0 : return false;
2120 : }
2121 :
2122 0 : int nPar1Len = pTxtNd1->Len();
2123 0 : int nPar2Len = pTxtNd2->Len();
2124 :
2125 0 : if( std::min( nPar1Len, nPar2Len ) * 3 < std::max( nPar1Len, nPar2Len ) )
2126 : {
2127 0 : return false;
2128 : }
2129 :
2130 0 : int nBorderLen = ( nPar1Len + nPar2Len )/16;
2131 :
2132 0 : if( nBorderLen < 3 )
2133 : {
2134 0 : nBorderLen = std::min( 3, std::min( nPar1Len, nPar2Len ) );
2135 : }
2136 :
2137 0 : std::set<unsigned> aHashes;
2138 0 : unsigned nHash = 0;
2139 0 : unsigned nMul = 251;
2140 0 : unsigned nPow = 1;
2141 : int i;
2142 :
2143 0 : for( i = 0; i < nBorderLen - 1; i++ )
2144 : {
2145 0 : nPow *= nMul;
2146 : }
2147 0 : for( i = 0; i < nBorderLen; i++ )
2148 : {
2149 0 : nHash = nHash*nMul + pTxtNd1->GetTxt().GetChar( i );
2150 : }
2151 0 : aHashes.insert( nHash );
2152 0 : for( ; i < nPar1Len; i++ )
2153 : {
2154 0 : nHash = nHash - nPow*pTxtNd1->GetTxt().GetChar( i - nBorderLen );
2155 0 : nHash = nHash*nMul + pTxtNd1->GetTxt().GetChar( i );
2156 :
2157 0 : aHashes.insert( nHash );
2158 : }
2159 :
2160 0 : nHash = 0;
2161 0 : for( i = 0; i < nBorderLen; i++ )
2162 : {
2163 0 : nHash = nHash*nMul + pTxtNd2->GetTxt().GetChar( i );
2164 : }
2165 :
2166 0 : if( aHashes.find( nHash ) != aHashes.end() )
2167 : {
2168 0 : return true;
2169 : }
2170 :
2171 0 : for( ; i < nPar2Len; i++ )
2172 : {
2173 0 : nHash = nHash - nPow*pTxtNd2->GetTxt().GetChar( i - nBorderLen );
2174 0 : nHash = nHash*nMul + pTxtNd2->GetTxt().GetChar( i );
2175 0 : if( aHashes.find( nHash ) != aHashes.end() )
2176 : {
2177 0 : return true;
2178 : }
2179 : }
2180 0 : return false;
2181 : }
2182 :
2183 0 : bool CharArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2184 : {
2185 0 : if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= GetLen1() || nIdx2 >= GetLen2() )
2186 : {
2187 : OSL_ENSURE( 0, "Index out of range!" );
2188 0 : return false;
2189 : }
2190 :
2191 0 : return ( !CmpOptions.bUseRsid
2192 0 : || pTxtNd1->CompareRsid( *pTxtNd2, nIdx1 + 1, nIdx2 + 1 ) )
2193 0 : && pTxtNd1->GetTxt().GetChar( nIdx1 )
2194 0 : == pTxtNd2->GetTxt().GetChar( nIdx2 );
2195 : }
2196 :
2197 0 : WordArrayComparator::WordArrayComparator( const SwTxtNode *pNode1,
2198 : const SwTxtNode *pNode2 )
2199 0 : : pTxtNd1( pNode1 ), pTxtNd2( pNode2 )
2200 : {
2201 0 : pPos1 = new int[ pTxtNd1->GetTxt().Len() + 1 ];
2202 0 : pPos2 = new int[ pTxtNd2->GetTxt().Len() + 1 ];
2203 :
2204 0 : CalcPositions( pPos1, pTxtNd1, nCnt1 );
2205 0 : CalcPositions( pPos2, pTxtNd2, nCnt2 );
2206 0 : }
2207 :
2208 0 : WordArrayComparator::~WordArrayComparator()
2209 : {
2210 0 : delete[] pPos1;
2211 0 : delete[] pPos2;
2212 0 : }
2213 :
2214 0 : bool WordArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2215 : {
2216 0 : int nLen = pPos1[ nIdx1 + 1 ] - pPos1[ nIdx1 ];
2217 0 : if( nLen != pPos2[ nIdx2 + 1 ] - pPos2[ nIdx2 ] )
2218 : {
2219 0 : return false;
2220 : }
2221 0 : for( int i = 0; i < nLen; i++)
2222 : {
2223 0 : if( pTxtNd1->GetTxt().GetChar( pPos1[ nIdx1 ] + i )
2224 0 : != pTxtNd2->GetTxt().GetChar( pPos2[ nIdx2 ] + i )
2225 : || ( CmpOptions.bUseRsid && !pTxtNd1->CompareRsid( *pTxtNd2,
2226 0 : pPos1[ nIdx1 ] + i, pPos2[ nIdx2 ] + i ) ) )
2227 : {
2228 0 : return false;
2229 : }
2230 : }
2231 0 : return true;
2232 : }
2233 :
2234 0 : int WordArrayComparator::GetCharSequence( const int *pWordLcs1,
2235 : const int *pWordLcs2, int *pSubseq1, int *pSubseq2, int nLcsLen )
2236 : {
2237 0 : int nLen = 0;
2238 0 : for( int i = 0; i < nLcsLen; i++ )
2239 : {
2240 : // Check for hash collisions
2241 0 : if( pPos1[ pWordLcs1[i] + 1 ] - pPos1[ pWordLcs1[i] ]
2242 0 : != pPos2[ pWordLcs2[i] + 1 ] - pPos2[ pWordLcs2[i] ] )
2243 : {
2244 0 : continue;
2245 : }
2246 0 : for( int j = 0; j < pPos1[pWordLcs1[i]+1] - pPos1[pWordLcs1[i]]; j++)
2247 : {
2248 0 : pSubseq1[ nLen ] = pPos1[ pWordLcs1[i] ] + j;
2249 0 : pSubseq2[ nLen ] = pPos2[ pWordLcs2[i] ] + j;
2250 :
2251 0 : if( pTxtNd1->GetTxt().GetChar( pPos1[ pWordLcs1[i] ] + j )
2252 0 : != pTxtNd2->GetTxt().GetChar( pPos2[ pWordLcs2[i] ] + j ) )
2253 : {
2254 0 : nLen -= j;
2255 0 : break;
2256 : }
2257 :
2258 0 : nLen++;
2259 : }
2260 : }
2261 0 : return nLen;
2262 : }
2263 :
2264 0 : void WordArrayComparator::CalcPositions( int *pPos, const SwTxtNode *pTxtNd,
2265 : int &nCnt )
2266 : {
2267 0 : nCnt = -1;
2268 0 : for( int i = 0; i <= pTxtNd->GetTxt().Len(); i++ )
2269 : {
2270 0 : if( i == 0 || i == pTxtNd->GetTxt().Len()
2271 0 : || !isalnum( pTxtNd->GetTxt().GetChar( i - 1 ) )
2272 0 : || !isalnum( pTxtNd->GetTxt().GetChar( i ) ) )
2273 : { // Begin new word
2274 0 : nCnt++;
2275 0 : pPos[ nCnt ] = i;
2276 : }
2277 : }
2278 0 : }
2279 :
2280 :
2281 0 : int CommonSubseq::FindLCS( int *pLcs1, int *pLcs2, int nStt1, int nEnd1,
2282 : int nStt2, int nEnd2 )
2283 : {
2284 0 : int nLen1 = nEnd1 ? nEnd1 - nStt1 : rCmp.GetLen1();
2285 0 : int nLen2 = nEnd2 ? nEnd2 - nStt2 : rCmp.GetLen2();
2286 :
2287 : OSL_ASSERT( nLen1 >= 0 );
2288 : OSL_ASSERT( nLen2 >= 0 );
2289 :
2290 0 : int **pLcs = new int*[ nLen1 + 1 ];
2291 0 : pLcs[ 0 ] = pData;
2292 :
2293 0 : for( int i = 1; i < nLen1 + 1; i++ )
2294 0 : pLcs[ i ] = pLcs[ i - 1 ] + nLen2 + 1;
2295 :
2296 0 : for( int i = 0; i <= nLen1; i++ )
2297 0 : pLcs[i][0] = 0;
2298 :
2299 0 : for( int j = 0; j <= nLen2; j++ )
2300 0 : pLcs[0][j] = 0;
2301 :
2302 : // Find lcs
2303 0 : for( int i = 1; i <= nLen1; i++ )
2304 : {
2305 0 : for( int j = 1; j <= nLen2; j++ )
2306 : {
2307 0 : if( rCmp.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2308 0 : pLcs[i][j] = pLcs[i - 1][j - 1] + 1;
2309 : else
2310 0 : pLcs[i][j] = std::max( pLcs[i][j - 1], pLcs[i - 1][j] );
2311 : }
2312 : }
2313 :
2314 0 : int nLcsLen = pLcs[ nLen1 ][ nLen2 ];
2315 :
2316 : // Recover the lcs in the two sequences
2317 0 : if( pLcs1 && pLcs2 )
2318 : {
2319 0 : int nIdx1 = nLen1;
2320 0 : int nIdx2 = nLen2;
2321 0 : int nIdx = nLcsLen - 1;
2322 :
2323 0 : while( nIdx1 > 0 && nIdx2 > 0 )
2324 : {
2325 0 : if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 - 1 ][ nIdx2 ] )
2326 0 : nIdx1--;
2327 0 : else if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 ][ nIdx2 - 1 ] )
2328 0 : nIdx2--;
2329 : else
2330 : {
2331 0 : nIdx1--, nIdx2--;
2332 0 : pLcs1[ nIdx ] = nIdx1 + nStt1;
2333 0 : pLcs2[ nIdx ] = nIdx2 + nStt2;
2334 0 : nIdx--;
2335 : }
2336 : }
2337 : }
2338 :
2339 0 : delete[] pLcs;
2340 :
2341 0 : return nLcsLen;
2342 : }
2343 :
2344 0 : int CommonSubseq::IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1,
2345 : int nLen2, int nLcsLen, int nPieceLen )
2346 : {
2347 0 : if( !nLcsLen )
2348 : {
2349 0 : return 0;
2350 : }
2351 :
2352 0 : int nNext = 0;
2353 :
2354 : // Don't ignore text at the beginning of the paragraphs
2355 0 : if( pLcs1[ 0 ] == 0 && pLcs2[ 0 ] == 0 )
2356 : {
2357 0 : while( nNext < nLcsLen - 1 && pLcs1[ nNext ] + 1 == pLcs1[ nNext + 1 ]
2358 0 : && pLcs2[ nNext ] + 1 == pLcs2[ nNext + 1 ] )
2359 : {
2360 0 : nNext++;
2361 : }
2362 0 : nNext++;
2363 : }
2364 :
2365 0 : int nCnt = 1;
2366 :
2367 0 : for( int i = nNext; i < nLcsLen; i++ )
2368 : {
2369 0 : if( i != nLcsLen - 1 && pLcs1[ i ] + 1 == pLcs1[ i + 1 ]
2370 0 : && pLcs2[ i ] + 1 == pLcs2[ i + 1 ] )
2371 : {
2372 0 : nCnt++;
2373 : }
2374 : else
2375 : {
2376 0 : if( nCnt > nPieceLen
2377 : // Don't ignore text at the end of the paragraphs
2378 : || ( i == nLcsLen - 1
2379 0 : && pLcs1[i] == nLen1 - 1 && pLcs2[i] == nLen2 - 1 ))
2380 : {
2381 0 : for( int j = i + 1 - nCnt; j <= i; j++ )
2382 : {
2383 0 : pLcs2[ nNext ] = pLcs2[ j ];
2384 0 : pLcs1[ nNext ] = pLcs1[ j ];
2385 0 : nNext++;
2386 : }
2387 : }
2388 0 : nCnt = 1;
2389 : }
2390 : }
2391 :
2392 0 : return nNext;
2393 : }
2394 :
2395 0 : LgstCommonSubseq::LgstCommonSubseq( ArrayComparator &rComparator )
2396 0 : : CommonSubseq( rComparator, CUTOFF )
2397 : {
2398 0 : pBuff1 = new int[ rComparator.GetLen2() + 1 ];
2399 0 : pBuff2 = new int[ rComparator.GetLen2() + 1 ];
2400 :
2401 0 : pL1 = new int[ rComparator.GetLen2() + 1 ];
2402 0 : pL2 = new int[ rComparator.GetLen2() + 1 ];
2403 0 : }
2404 :
2405 0 : LgstCommonSubseq::~LgstCommonSubseq()
2406 : {
2407 0 : delete[] pBuff1;
2408 0 : delete[] pBuff2;
2409 :
2410 0 : delete[] pL1;
2411 0 : delete[] pL2;
2412 0 : }
2413 :
2414 0 : void LgstCommonSubseq::FindL( int *pL, int nStt1, int nEnd1,
2415 : int nStt2, int nEnd2 )
2416 : {
2417 0 : int nLen1 = nEnd1 ? nEnd1 - nStt1 : rCmp.GetLen1();
2418 0 : int nLen2 = nEnd2 ? nEnd2 - nStt2 : rCmp.GetLen2();
2419 :
2420 0 : int *currL = pBuff1;
2421 0 : int *prevL = pBuff2;
2422 :
2423 : // Avoid memory corruption
2424 0 : if( nLen2 > rCmp.GetLen2() )
2425 : {
2426 : assert( false );
2427 0 : return;
2428 : }
2429 :
2430 0 : memset( pBuff1, 0, sizeof( *pBuff1 ) * ( nLen2 + 1 ) );
2431 0 : memset( pBuff2, 0, sizeof( *pBuff2 ) * ( nLen2 + 1 ) );
2432 :
2433 : // Find lcs
2434 0 : for( int i = 1; i <= nLen1; i++ )
2435 : {
2436 0 : for( int j = 1; j <= nLen2; j++ )
2437 : {
2438 0 : if( rCmp.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2439 0 : currL[j] = prevL[j - 1] + 1;
2440 : else
2441 0 : currL[j] = std::max( currL[j - 1], prevL[j] );
2442 : }
2443 0 : int *tmp = currL;
2444 0 : currL = prevL;
2445 0 : prevL = tmp;
2446 : }
2447 0 : memcpy( pL, prevL, ( nLen2 + 1 ) * sizeof( *prevL ) );
2448 : }
2449 :
2450 0 : int LgstCommonSubseq::HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1,
2451 : int nEnd1, int nStt2, int nEnd2 )
2452 : {
2453 : static int nLen1;
2454 : static int nLen2;
2455 0 : nLen1 = nEnd1 - nStt1;
2456 0 : nLen2 = nEnd2 - nStt2;
2457 :
2458 0 : if( ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2459 : {
2460 0 : if( !nLen1 || !nLen2 )
2461 : {
2462 0 : return 0;
2463 : }
2464 0 : return FindLCS(pLcs1, pLcs2, nStt1, nEnd1, nStt2, nEnd2);
2465 : }
2466 :
2467 0 : int nMid = nLen1/2;
2468 :
2469 0 : FindL( pL1, nStt1, nStt1 + nMid, nStt2, nEnd2 );
2470 0 : FindL( pL2, nStt1 + nMid, nEnd1, nStt2, nEnd2 );
2471 :
2472 0 : int nMaxPos = 0;
2473 : static int nMaxVal;
2474 0 : nMaxVal = -1;
2475 :
2476 : static int i;
2477 0 : for( i = 0; i <= nLen2; i++ )
2478 : {
2479 0 : if( pL1[i] + ( pL2[nLen2] - pL2[i] ) > nMaxVal )
2480 : {
2481 0 : nMaxPos = i;
2482 0 : nMaxVal = pL1[i]+( pL2[nLen2] - pL2[i] );
2483 : }
2484 : }
2485 :
2486 : int nRet = HirschbergLCS( pLcs1, pLcs2, nStt1, nStt1 + nMid,
2487 0 : nStt2, nStt2 + nMaxPos );
2488 : nRet += HirschbergLCS( pLcs1 + nRet, pLcs2 + nRet, nStt1 + nMid, nEnd1,
2489 0 : nStt2 + nMaxPos, nEnd2 );
2490 :
2491 0 : return nRet;
2492 : }
2493 :
2494 0 : int LgstCommonSubseq::Find( int *pSubseq1, int *pSubseq2 )
2495 : {
2496 0 : int nStt = 0;
2497 0 : int nCutEnd = 0;
2498 0 : int nEnd1 = rCmp.GetLen1();
2499 0 : int nEnd2 = rCmp.GetLen2();
2500 :
2501 : // Check for corresponding lines in the beginning of the sequences
2502 0 : while( nStt < nEnd1 && nStt < nEnd2 && rCmp.Compare( nStt, nStt ) )
2503 : {
2504 0 : pSubseq1[ nStt ] = nStt;
2505 0 : pSubseq2[ nStt ] = nStt;
2506 0 : nStt++;
2507 : }
2508 :
2509 0 : pSubseq1 += nStt;
2510 0 : pSubseq2 += nStt;
2511 :
2512 : // Check for corresponding lines in the end of the sequences
2513 0 : while( nStt < nEnd1 && nStt < nEnd2
2514 0 : && rCmp.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2515 : {
2516 0 : nCutEnd++;
2517 0 : nEnd1--;
2518 0 : nEnd2--;
2519 : }
2520 :
2521 0 : int nLen = HirschbergLCS( pSubseq1, pSubseq2, nStt, nEnd1, nStt, nEnd2 );
2522 :
2523 0 : for( int i = 0; i < nCutEnd; i++ )
2524 : {
2525 0 : pSubseq1[ nLen + i ] = nEnd1 + i;
2526 0 : pSubseq2[ nLen + i ] = nEnd2 + i;
2527 : }
2528 :
2529 0 : return nStt + nLen + nCutEnd;
2530 : }
2531 :
2532 0 : int FastCommonSubseq::FindFastCS( int *pSeq1, int *pSeq2, int nStt1,
2533 : int nEnd1, int nStt2, int nEnd2 )
2534 : {
2535 0 : int nCutBeg = 0;
2536 0 : int nCutEnd = 0;
2537 :
2538 : // Check for corresponding lines in the beginning of the sequences
2539 0 : while( nStt1 < nEnd1 && nStt2 < nEnd2 && rCmp.Compare( nStt1, nStt2 ) )
2540 : {
2541 0 : pSeq1[ nCutBeg ] = nStt1++;
2542 0 : pSeq2[ nCutBeg ] = nStt2++;
2543 0 : nCutBeg++;
2544 : }
2545 :
2546 0 : pSeq1 += nCutBeg;
2547 0 : pSeq2 += nCutBeg;
2548 :
2549 : // Check for corresponding lines in the end of the sequences
2550 0 : while( nStt1 < nEnd1 && nStt2 < nEnd2
2551 0 : && rCmp.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2552 : {
2553 0 : nCutEnd++;
2554 0 : nEnd1--;
2555 0 : nEnd2--;
2556 : }
2557 :
2558 0 : int nLen1 = nEnd1 - nStt1;
2559 0 : int nLen2 = nEnd2 - nStt2;
2560 :
2561 : // Return if a sequence is empty
2562 0 : if( nLen1 <= 0 || nLen2 <= 0 )
2563 : {
2564 0 : for( int i = 0; i < nCutEnd; i++ )
2565 : {
2566 0 : pSeq1[ i ] = nEnd1 + i;
2567 0 : pSeq2[ i ] = nEnd2 + i;
2568 : }
2569 0 : return nCutBeg + nCutEnd;
2570 : }
2571 :
2572 : // Cut to LCS for small values
2573 0 : if( nLen1 < 3 || nLen2 < 3 || ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2574 : {
2575 0 : int nLcsLen = FindLCS( pSeq1, pSeq2, nStt1, nEnd1, nStt2, nEnd2);
2576 :
2577 0 : for( int i = 0; i < nCutEnd; i++ )
2578 : {
2579 0 : pSeq1[ nLcsLen + i ] = nEnd1 + i;
2580 0 : pSeq2[ nLcsLen + i ] = nEnd2 + i;
2581 : }
2582 0 : return nCutBeg + nLcsLen + nCutEnd;
2583 : }
2584 :
2585 0 : int nMid1 = nLen1/2;
2586 0 : int nMid2 = nLen2/2;
2587 :
2588 : int nRad;
2589 0 : int nPos1 = -1, nPos2 = -1;
2590 :
2591 : // Find a point of correspondence in the middle of the sequences
2592 0 : for( nRad = 0; nRad*nRad < std::min( nMid1, nMid2 ); nRad++ )
2593 : {
2594 : // Search to the left and to the right of the middle of the first sequence
2595 0 : for( int i = nMid1 - nRad; i <= nMid1 + nRad; i++ )
2596 : {
2597 0 : if( rCmp.Compare( nStt1 + i, nStt2 + nMid2 - nRad ) )
2598 : {
2599 0 : nPos1 = nStt1 + i;
2600 0 : nPos2 = nStt2 + nMid2 - nRad;
2601 0 : break;
2602 : }
2603 0 : if( rCmp.Compare( nStt1 + i, nStt2 + nMid2 + nRad ) )
2604 : {
2605 0 : nPos1 = nStt1 + i;
2606 0 : nPos2 = nStt2 + nMid2 - nRad;
2607 0 : break;
2608 : }
2609 : }
2610 : // Search to the left and to the right of the middle of the second sequence
2611 0 : for( int i = nMid2 - nRad; i <= nMid2 + nRad; i++ )
2612 : {
2613 0 : if( rCmp.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2614 : {
2615 0 : nPos2 = nStt2 + i;
2616 0 : nPos1 = nStt1 + nMid1 - nRad;
2617 0 : break;
2618 : }
2619 0 : if( rCmp.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2620 : {
2621 0 : nPos2 = nStt2 + i;
2622 0 : nPos1 = nStt1 + nMid1 - nRad;
2623 0 : break;
2624 : }
2625 : }
2626 : }
2627 :
2628 : // return if no point of correspondence found
2629 0 : if( nPos1 == -1 )
2630 : {
2631 0 : for( int i = 0; i < nCutEnd; i++ )
2632 : {
2633 0 : pSeq1[ i ] = nEnd1 + i;
2634 0 : pSeq2[ i ] = nEnd2 + i;
2635 : }
2636 0 : return nCutBeg + nCutEnd;
2637 : }
2638 :
2639 : // Run the same on the sequences to the left of the correspondence point
2640 0 : int nLen = FindFastCS( pSeq1, pSeq2, nStt1, nPos1, nStt2, nPos2 );
2641 :
2642 0 : pSeq1[ nLen ] = nPos1;
2643 0 : pSeq2[ nLen ] = nPos2;
2644 :
2645 : // Run the same on the sequences to the right of the correspondence point
2646 0 : nLen += FindFastCS( pSeq1 + nLen + 1, pSeq2 + nLen + 1,
2647 0 : nPos1 + 1, nEnd1, nPos2 + 1, nEnd2 ) + 1;
2648 :
2649 0 : for( int i = 0; i < nCutEnd; i++ )
2650 : {
2651 0 : pSeq1[ nLen + i ] = nEnd1 + i;
2652 0 : pSeq2[ nLen + i ] = nEnd2 + i;
2653 : }
2654 :
2655 0 : return nLen + nCutBeg + nCutEnd;
2656 : }
2657 :
2658 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
