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